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=I, the attention scores depend on token identity, and softmax(4I+M) does not produce the uniform averaging used in the subsequent derivation. Moreover, the threshold condition with denominator ∣P∣+j does not imply the required condition with denominator ∣P∣+M. These issues leave essential steps of the 3-SAT reduction unjustified.
-
Proposition 5.13 (Appendix F.2): The proof constructs x=σ1k and x′=σ2k, violating the proposition's assumption that x and x′ have the same last token. Furthermore, the final loss comparison reverses the direction established by the preceding inequalities. The proposition also quantifies β but uses an undefined ϵ 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.
Rebuttal
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.