acceptodds
Under review as a conference paper at ICLR 2027

On the Capability and Limitation of Hard Prompt

Abstract

Prompt engineering has become an indispensable tool for using large language models (LLMs), turning LLMs into task-specific experts without changing their weights. Despite notable theoretical advances in prompt engineering, the theory for the more practical hard or discrete prompts is largely open. In this paper, we try to fill this gap either by providing a complete solution or by making substantial progress on the three core theoretical questions regarding hard prompts. First, we show that determining the existence of a hard prompt for a transformer to solve a downstream task is NP-complete and that finding an optimal hard prompt is NP-hard, which is the first computational complexity result for hard prompting, as far as we know. Second, we show that, unlike soft or continuous prompts, hard prompts have essential limitations: hard prompts are not complete; short hard prompts do not significantly enhance the ability of transformers; and long hard prompts exhibit the “prompt dominating answer phenomenon,” meaning that, with high probability, the same answer is given for all queries of the same length. On the other hand, linear hard prompts do not have the limitations of short or long prompts. Third, we provide a tight bound on the size of the task in terms of the prompt length for the performance of prompts on the finite task to generalize to the entire data distribution, leading to a necessary and sufficient condition for generalizability. This is the first result on generalization for prompting, as far as we know. Our findings not only offer the first theoretical insights into hard prompts but also provide provably reliable practical guidance for real-world LLM usage.

Primary area:
interpretability and explainable AI
Keywords:
Prompt Engineering, Theory, Generalization, Computational Complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7B5eOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

this paper studies hard prompts for transformers. It studies 3 domains: the computation complexity, expressive limitation, and the generalization. Overall this paper is of good writing and solid results.

Critical strengths
  1. The coverage of this paper is comprehensive; it covers the computation complexity, expressive limitation, and the generalization of hard prompts.
  2. Many of the results are meaningful and informative. For example, in Theorem 4.2 it studies the search of prompt with a length constraint; Theorem 5.4 describes the failure cases where the prompt is short and sufficiently long. They are all valuable for empirical prompt engineering.
  3. The presentation of this paper is good.
Critical weaknesses
  1. The domain, “interpretability and explainable AI”, seems not quite match the scope of this paper. Maybe Learning theory or Optimization or related areas would be a better fit. I would like to invite AC to check this.
  2. This paper claims that ‘This is the first result on generalization for prompting’. Frankly, I am not able to check the novelty of this domain so I asked AI check the novelty of this contribution. This is what AI told me “Akinwande et al. (2023), Understanding prompt engineering may not require rethinking generalization, already derived bounds for discrete prompts. Madras et al. (2025), Prompts Generalize with Low Data: Non-vacuous Generalization Bounds for Optimizing Prompts with More Informative Priors, provided further results.” I checked the evidence and I think what AI said is correct. I believe this paper do have its unique contribution on the generalization of prompt; more detailed explanation on what is newly proposed would make the contribution of this paper more clear.
Questions for authors

Please check the weaknesses mentioned.

1 comment

Thank you for your insights. We will now carefully respond to all the questions you have raised one by one.

For W1.

We use many theoretical tools, and consider that prompt engineering is a key means of understanding the behavior of LLMs, we believe it is reasonable to classify it as “interpretability and explainable AI”.

For W2.

To clarify our theoretical contributions, we provide the following detailed response:

Core Contribution: The primary theoretical contribution of our work in section 6 is the tight generalizaiton bound(ignore small quantities), by matching upper and lower generalization bounds. (As said in line 121-122(old version)). We want to emphasize that papers [1,2] only give upper generalization bounds, but lower bound like the one in Theorem 6.3 is not provided.

Theorem 6.1 (Generalization Upper Bound): The core contribution of this theorem is extending the generalization bound theory from the discrete setting to the hard prompting scenario, and derive upper bound of tight generalization bounds(ignore small quantities) for hard prompting. As the reviewer correctly pointed out, like [1], use discrete theory to prove the prompting generalization theory has precedents, because the generalization theory in the discrete setting is already well-established and widely used. In fact, in the previous sections, we have provided many new proof ideas to prove the NP and limitation of hard prompt, but as common in theoretical research, not every theorem requires the introduction of entirely new techniques, existing theories have already provided a wealth of advanced tools and technologies to solve the upper bound problem under our setting, so further refining or developing the discrete theory itself is not an important task for this work.

Theorem 6.3 (Generalization Lower Bound): This theorem derives a lower bound of tight generalization bound(ignore small quantities) based on the expressivity theory of Transformers. The technical approach involves constructing worst-case scenarios and using Transformer expressivity theory to demonstrate the rationality of construction. This methodology of utilizing expressivity to derive lower bounds is a standard and effective technique in theoretical analysis.

We thank the review for providing the new references and will add these new references in the new version.

[1]: Understanding Prompt Engineering May Not Require Rethinking Generalization. [2] Madras et al. (2025), Prompts Generalize with Low Data: Non-vacuous Generalization Bounds for Optimizing Prompts with More Informative Priors.

Reviewer_cBWVOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the problem of prompt engineering / compression / hard prompts from the perspective of a complexity theorist. This seems to be the first work that takes such an approach. They show, among other things, that finding the best prompt is NP-hard, and obtain bounds on the prompt length that allow "generalizability".

Critical strengths
  1. The paper is well-written (objectively certainly, but it was a breath of fresh air in my batch of papers to review): the problem formulation is extremely clear, the approach, results, motivation, all are presented exceptionally well.
  2. The problem studied is one that is of significant interest: prompt engineering has attracted attention from even general public, so having a good theoretical handle on the problem is something that has been due for a long time.
  3. The theoretical results seem correct and are insightful.
Critical weaknesses

None.

Questions for authors

None.

1 comment

Thank you for your review. If you have any further questions, please ask and we are happy to answer and discuss with you.

Reviewer_8vJhOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2(+1)
Soundness
2(+1)
Read review
Paper summary

This paper investigates the theoretical capabilities and limitations of hard prompts for fixed-weight Transformers. It addresses three questions: the computational complexity of hard prompt optimization, the expressive limitations associated with prompt length, and the generalization of prompts from finite datasets. The authors derive several theoretical results and provide preliminary experiments on mathematical reasoning tasks.

Critical strengths

Important and well-motivated research questions.

The paper addresses fundamental questions about hard prompting from the perspectives of computational complexity, expressivity, and generalization. These questions are theoretically meaningful and relevant to understanding prompt-based adaptation.

Critical weaknesses

W1. Significant gaps and inconsistencies in the theoretical proofs.

  • Theorem 4.2 (Appendix B.2): The claimed attention output does not follow from the specified construction. With the given token embeddings and Q1K1=IQ_1K_1=I, the attention scores depend on token identity, and softmax(4I+M)\mathrm{softmax}(4I+M) does not produce the uniform averaging used in the subsequent derivation. Moreover, the threshold condition with denominator ∣P∣+j|P|+j does not imply the required condition with denominator ∣P∣+M|P|+M. These issues leave essential steps of the 3-SAT reduction unjustified.

  • Proposition 5.13 (Appendix F.2): The proof constructs x=σ1kx=\sigma_1^k and x′=σ2kx'=\sigma_2^k, violating the proposition's assumption that xx and x′x' have the same last token. Furthermore, the final loss comparison reverses the direction established by the preceding inequalities. The proposition also quantifies β\beta but uses an undefined ϵ\epsilon in its conclusion.

These issues affect essential steps in the proofs and leave the corresponding theoretical claims insufficiently established.

W2. Overstated novelty and insufficient discussion of closely related work.

The novelty of the generalization analysis is overstated. Akinwande et al. [1] already established generalization bounds for discrete prompts using uniform convergence and PAC-Bayes analysis. Their uniform convergence bound has essentially the same dependence on prompt length, vocabulary size, and sample size as Theorem 6.1, directly challenging the paper's claim of providing the first generalization result for prompting.

Although the underlying settings differ, the authors do not adequately distinguish their contribution from this prior result. In particular, Theorem 6.1 relies on standard finite-hypothesis-space generalization analysis, while the potential novelty of the lower bound in Theorem 6.3 is not sufficiently emphasized.

Petrov et al. [2] is cited, but its relationship to the present expressivity results is not examined in depth. Zhang et al. [3], which studies the complexity of prompt search spaces in CoT reasoning, is not discussed. Although these works address different settings, they are relevant to positioning the paper's theoretical contributions.

The authors should more precisely identify their genuinely new contributions and qualify the claims of providing the first generalization result and the first theoretical insights into hard prompting.

[1] Victor Akinwande, Yiding Jiang, Dylan Sam, and J. Zico Kolter. Understanding Prompt Engineering May Not Require Rethinking Generalization. International Conference on Learning Representations (ICLR), 2024.

[2] Aleksandar Petrov, Philip H. S. Torr, and Adel Bibi. When Do Prompting and Prefix-Tuning Work? A Theory of Capabilities and Limitations. International Conference on Learning Representations (ICLR), 2024.

[3] Xiang Zhang, Juntai Cao, Chenyu You, and Dujian Ding. Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 32525–32555, 2025.

W3. Several conclusions are stronger than what the theoretical results establish.

The paper frequently extends conclusions derived under specific assumptions into broad claims about practical prompting.

  • Theorem 5.7 bounds the difference in negative log-likelihood for a specified answer across queries satisfying particular conditions. Without an additional requirement that the loss threshold is sufficiently small, this does not establish that different queries generate identical answers with high probability. Nor does it establish that the answer is copied from the prompt itself.
  • Propositions 5.11 and 5.13 establish existence results for particular Transformers and tasks. They do not demonstrate a general advantage of linear-length prompts for arbitrary Transformers, despite the broader claim in the abstract.
  • Corollary 6.4 concerns uniform, worst-case generalization guarantees. However, the introduction and conclusion present this result as a broadly applicable sample-size requirement without clearly preserving these qualifications.

Similarly, the claim that no scaling law exists for hard prompts is not established by the presented worst-case limitations, which do not rule out scaling relationships under other settings.

These overstatements weaken the connection between the formal theoretical results and the paper's claimed practical implications.

W4. Experimental evidence does not adequately validate the theoretical conclusions.

In Appendix J, the linear prompts are constructed by extracting key ideas from the reference answers of individual test problems. This introduces answer-dependent information unavailable in ordinary test-time prompting.

Furthermore, the linear-prompt condition uses question-specific prompts, whereas the theoretical analysis considers a shared prompt for a task. Although individual questions could be treated as singleton tasks, this setup does not directly evaluate the shared-prompt setting for a multi-example task.

The long-prompt condition combines answer-derived hints from all 90 test problems, making it difficult to separate prompt-length effects from potential interference caused by irrelevant information.

Moreover, the three experimental prompt conditions do not directly test the asymptotic length regimes analyzed in Section 5.

Consequently, the observed improvements cannot be attributed solely to prompt length, and the experiments provide limited evidence for the claimed practical advantages of linear prompts.

Questions for authors

Q1. Could the authors provide corrected proofs of Theorem 4.2 and Proposition 5.13, addressing the attention computation, threshold implication, violated assumptions, and inconsistent loss inequalities identified in W1?

Q2. How does Theorem 6.1 differ technically from the discrete-prompt generalization bound in Akinwande et al. [1]? What is the main theoretical novelty of Theorem 6.3 relative to existing generalization analyses?

[1] Victor Akinwande, Yiding Jiang, Dylan Sam, and J. Zico Kolter. Understanding Prompt Engineering May Not Require Rethinking Generalization. International Conference on Learning Representations (ICLR), 2024.

Q3. Could the authors clarify how Theorem 5.7 supports the claimed high-probability identical-answer behavior, and how the existential results in Propositions 5.11/5.13 justify the broader claims about linear prompts? Could they also clarify the worst-case scope of Corollary 6.4?

Q4. Could the authors provide controlled experiments that isolate the effects of prompt length from answer-dependent information, particularly by constructing prompts without access to the reference answers of the evaluated questions?

8 comments
AuthorsOpenReview ↗

Rebuttal Part 1

Thank you for your insights. We will now carefully respond to all the questions you have raised one by one.

Answer for Q1 and W1.

Firstly, we would like to confirm that all the conclusion of our paper is correct. However, we acknowledge that there are some minor errors in the proof, mostly typos. We are sorry for these minor affected your understanding, all the proof was entirely handwritten, we would appreciate your understanding. These errors can be easily corrected and do not affect the validity of our results, as following.

1: About QK=IQK=I. We are sorry for this typo error, it should have been QK=I1QK=I_1(all-ones matrix), we mistakenly lost the index. The core conclusion F1(x)=v(x)+softmax(4Ilen(x)+M)v(x)F_1(x)=v(x)+softmax(4I_{len(x)}+M)v(x) is correct, because when we take QK=I1QK=I_1, and consider the definition of embedding layer, it is easy to get such result.

2: About ∣P∣+i|P|+i. We are sorry for this typo error, in line 753-754(old version) it should have been: zi=1z_i=1 if Numσi(P)/(len(P)+1)≥1/NNum_{\sigma_i}(P)/(len(P)+1)\ge 1/N where i∈[N]i\in[N], we mistakenly write the denominator. The following deduction is completely correctly. Because if Numσi(P)/(len(P)+i)≥1/NNum_{\sigma_i}(P)/(len(P)+i)\ge 1/N, consider that i≥1i\ge 1, then it can derive that Numσi(P)/(len(P)+1)≥1/NNum_{\sigma_i}(P)/(len(P)+1)\ge 1/N, which can imply that zi′=1z_{i'}=1 or zj′=1z_{j'}=1 or zk′=1z_{k'}=1.

3: About the last token. We are sorry for the oversight here, we forgot to align the last token, but this problem can be easily corrected. We need to refine the proof in the following points:

(3.1): In line 1582(old version), change it to: (x′,y)=(σ2k,σ2k+L)(x',y)=(\sigma^k_2,\sigma_2^{k+L}) and (x,y)=(σ1k−1⊕σ2,σ2k+L)(x,y)=(\sigma^{k-1}_1\oplus\sigma_2,\sigma_2^{k+L}), where k=2Lk=2L and L≥6L\ge 6, this will align the last token. Please note that the case of L≤5L\le 5 can be reduced to the situation L≥6L\ge 6.

(3.2): In line 1579(old version), change it to: FN(x)=ln⁡(3/(eα1−1))F_N(x)=\ln(3/(e^{\alpha_1}-1)) when x≥29/48x\ge 29/48. Because 29/48>3/529/48>3/5, such definition is reasonable.

(3.3): In line 1591(old version), change it to: Fl(P⊕x⊕σ2m)[1]≥(k+L)+k−1m+k+(k+L)≥(k+L)+k−1L+k+k+(k+L)=5L−18L≥2948F_l(P\oplus x\oplus\sigma_2^m)[1]\ge \frac{(k+L)+k-1}{m+k+(k+L)}\ge \frac{(k+L)+k-1}{L+k+k+(k+L)}=\frac{5L-1}{8L}\ge \frac{29}{48}.

Adjustments in (3.2) and (3.3) are essentially just minor adjustments made to the threshold and do not affect the proof idea itself.

4: About ϵ\epsilon and β\beta in Proposition 5.13. We are sorry for this typo error, in line 412, it should be α+β\alpha+\beta not α+ϵ\alpha+\epsilon.

5: In line 1601-1602(old version), we are sorry for this typo error, it should be LNnll(F,P⊕x,σ2k+L)≤LNnll(F,P⊕x′,σ2k+L)−βL_{\text{Nnll}}(F,P\oplus x,\sigma_2^{k+L})\le L_{\text{Nnll}}(F,P\oplus x',\sigma_2^{k+L})-\beta and Lnll(F,P⊕x,σ2k+L)≤Lnll(F,P⊕x′,σ2k+L)−βL_{\text{nll}}(F,P\oplus x,\sigma_2^{k+L})\le L_{\text{nll}}(F,P\oplus x',\sigma_2^{k+L})-\beta. We mistakenly reversed the positions of xx and x′x', but this does not affect the final result being correct.

These errors will be corrected in the next version.

AuthorsOpenReview ↗

Rebuttal Part 2

Thank you for your insights. We will now carefully respond to all the questions you have raised one by one.

For Q2 and W2.

1: We acknowledge that our conclusion is established under the hard prompt word and only applies to the hard prompt word. In fact, our title has already made it clear that we are doing research on hard prompts. We will make it more clear in the Question 3 in the introduction.

2: To clarify our theoretical contributions, we provide the following detailed response:

Core Contribution: The primary theoretical contribution of our work in section 6 is the tight generalizaiton bound(ignore small quantities), by matching upper and lower generalization bounds. (As said in line 121-122(old version)). We want to emphasize that papers [1,2] only give upper generalization bounds, but lower bound like the one in Theorem 6.3 is not provided.

Theorem 6.1 (Generalization Upper Bound): The core contribution of this theorem is extending the generalization bound theory from the discrete setting to the hard prompting scenario, and derive upper bound of tight generalization bounds(ignore small quantities) for hard prompting. As the reviewer correctly pointed out, like [1], use discrete theory to prove the prompting generalization theory has precedents, because the generalization theory in the discrete setting is already well-established and widely used. In fact, in the previous sections, we have provided many new proof ideas to prove the NP and limitation of hard prompt, but as common in theoretical research, not every theorem requires the introduction of entirely new techniques, existing theories have already provided a wealth of advanced tools and technologies to solve the upper bound problem under our setting, so further refining or developing the discrete theory itself is not an important task for this work.

Theorem 6.3 (Generalization Lower Bound): This theorem derives a lower bound of tight generalization bound(ignore small quantities) based on the expressivity theory of Transformers. The technical approach involves constructing worst-case scenarios and using Transformer expressivity theory to demonstrate the rationality of construction. This methodology of utilizing expressivity to derive lower bounds is a standard and effective technique in theoretical analysis.

We thank the review for providing the new references and will add these new references in the new version.

[1]: Understanding Prompt Engineering May Not Require Rethinking Generalization. [2] Madras et al. (2025), Prompts Generalize with Low Data: Non-vacuous Generalization Bounds for Optimizing Prompts with More Informative Priors.

Specifically, we noticed that the reviewer also cited two other references, but these two paper did not provide clear generalization theory or provide clear theoretical answers to the questions we raised. We will add them into the related work.

AuthorsOpenReview ↗

Rebuttal Part 3

Q3 and W3.

We believe that our theorem essentially answers the questions we described in the introduction. Reviewer has some questions of the scope of application of constructive conclusions, and we will answer them one by one.

(1) For Th5.7. Theorem 5.7 describes that when the prompt is long enough, the probability of the transformer generating the given answer on two different questions is similar(this can be clearly obtained from Theorem 5.7 by replacing the positions of xx and x′x' in Theorem 5.7). The key is that this conclusion holds for every answer, which means that the overall output distribution itself tends to be close. This is precisely the essential meaning of “Long Prompt Dominating Answer Phenomenon", itself is the object that the theorem wants to express. As for the reviewer's mention of "the loss threshold needs to be small enough", we believe that this is an obvious inference of the similarity of the above distributions, rather than a gap in the theorem: under the premise that two distributions are arbitrarily close, once an answer has a high probability on one of the distributions, we immediately know from Theorem 5.7 that it has the same high probability on the other distribution, so the model will naturally output this answer stably.

(2) For Propositions 5.11 and 5.13. Firstly, we need to clarify that these two theories cannot hold for any transformer, so we can only prove them in some cases, as mentioned in line 97, 393 and 407(old version). This is not a gap, but the logical form that the proposition should have. We have previously demonstrated that both short and long prompts have universal worst-case limitations, which apply to all Transformers, propositions 5.11 and 5.13 prove that these limitations are not universal, i.e. there are certain Transformers and tasks that linear prompts can avoid these problem. That is, we have demonstrated is that linear prompts can escape universal barriers that exclude short/long prompts, which is a theoretically based advantage of linear prompt.

(3) For corollary 6.4. The constructive proof in Theorem 6.3 serves as a matching lower bound for the upper bounds in Theorems 6.1. Essentially, this construction explores the other side of the boundary of generalization theory: there are indeed certain situations where the number of samples requires so much. We respectfully clarify that this constructive proof is a theoretical boundary exploration under our setting, without more assumptions, these worst-case scenarios correspond to another boundary of generalization theory, and thus we use it to obtain the tight theoretical under hard prompt setting. The reviewers are concerned that most data distributions and transformers cannot reach this bound, this is a common problem in most theoretical boundary studies, because different data distributions and transformer have different characteristics, it's impossible for everyone to be on the theoretical boundary, and it is difficult to clearly indicate which situations are at the boundary, this question is also the same for our research. However, we need to point out that the core value of the bound theoretical lies in revealing the worst-case complexity of the problem, and provides a ultimate bound for understanding the generalization ability of the hard prompt.

(4) For scaling law. Proposition 5.10 holds true for any transformer under our setting, any hard prompt, dataset with certain assumptions(same length and last token), not relying on unrealistic assumptions. We have clearly identified the situations where there is no scaling law in the proposition. In fact, if a dataset contains a subset that fits the assumptions, our theory can also prove that there is no scaling law. The reviewer is concerned about, if these assumptions are removed(i.e. for other situations), this results will not hold true. We respectfully clarify that the result of scaling law is an additional conclusion for proposition 5.10, a comprehensive characterization of all scenarios (i.e. where scaling laws hold, where they do not) is beyond the scope of this work, this is not in the three questions raised, this can serve as a future research direction.

Finally, as requested, we have further clarified the scope of applicability of our theory in the revised manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.