{"id":"06bced6e-2d33-4d0b-9ea3-29e6dcbf185e","arxiv_id":"2509.00421","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Prompt tuning in transformers is shown, via covering and Lipschitz arguments, to memorize at most linearly many examples in the prompt length.","lead":"A theory preprint proves that prompt tuning can only memorize a number of input-output pairs that grows linearly with the prompt length, no matter how large the transformer. It also argues this explains why long-context transformers lose performance, though that link is an interpretation rather than a direct consequence.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.10's packing argument inverts the covering scale: the proof counts ε/3-separated outputs as if they were 3ε-separated, so the stated O(exp(-k 3^d/ε^d)) rate is not established.","rationale":"The reader's conditional verdict is appropriate, but the load-bearing technical weakness is not primarily the provenance of Proposition 3.6. Even if Kloeckner's metric-entropy bound is accepted, the proof of Theorem 4.10 misuses it: it builds the output-space denominator from a packing at scale ε/3 while claiming 3ε-separated targets. This is an internal inconsistency, not a disagreement with the optimal transport literature. Theorem 4.7, which gives the linear-in-prompt-length memorization bound, uses a similar packing argument but with the correct (r/(3ε))^{dmk} denominator, so the issue is specific to the mean-field theorem. The identity-transformer thought experiment shows the strong rate is implausible, though a full counterexample requires tracking metric-entropy constants. The central qualitative claim—that the accessible fraction decays exponentially in k—is likely true and would survive with a corrected constant, so the work should not be rejected outright. However, the exact statement of Theorem 4.10 and its threshold need to be corrected before the result can be endorsed as stated. The Section 5 dimension-formula issue noted by the reader is separate and also supports a conditional verdict. I give partial agreement with the reader because they pointed to the covering-number estimate itself, whereas the more decisive problem is the scale at which that estimate is applied.","tokens_in":20124,"tokens_out":38112,"duration_ms":515584,"concrete_test":"Recompute the proof of Theorem 4.10 using δ=3ε in Proposition 3.6: set Cout = (C^{-1} exp(1/(3ε)^d))^k and rerun the counting argument. If the resulting fraction is O(exp(-c k/(3ε)^d)) rather than O(exp(-k 3^d/ε^d)), the stated rate is wrong. Also instantiate τ as the identity transformer and compute the accessible-set packing for a fixed input X; the accessible output set is dense in P(B), so for k above the theorem's threshold the fraction cannot be as small as exp(-k 3^d/ε^d) once dimension-independent constants are tracked.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main exponential-decay theorem (Theorem 4.10) rests on a scale error in Appendix D. To bound the proportion of ε-accessible output distributions, the proof needs a family of target output tuples that are 3ε-separated: if one transformer output is within ε of two targets, the targets must be at least 2ε apart (they use 3ε). The correct lower bound on the number of 3ε-separated output distributions follows from Proposition 3.6 at scale δ=3ε: M(G,3ε) ≥ N(G,3ε) ≥ C^{-1} exp(1/(3ε)^d). Appendix D instead uses exp(3^d/ε^d), which is the covering-number lower bound at scale δ=ε/3. Points separated by only ε/3 are not 3ε-distinct, and one prompt can lie within ε of many of them, so Cout in the proof is not a valid 3ε-packing. This inflates the denominator by roughly exp(k(3^d-3^{-d})/ε^d), making the claimed O(exp(-k 3^d/ε^d)) rate stronger than the packing argument can support. The corrected rate from the same argument is O(exp(-c k/(3ε)^d)), still exponential in k but with a different ε-dependence. The identity transformer (a valid transformer with L=1) illustrates the issue: varying the prompt makes the accessible output set dense in the space of distributions, so the true fraction cannot decay as fast as exp(-k 3^d/ε^d) for large k. The qualitative conclusion—exponential decay for large k—may survive, but the theorem as stated is quantitatively unsupported and needs repair.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies memorization through prompt tuning in transformers. It introduces a notion of ε-accessibility for output sequences and output distributions and proves two main results. Theorem 4.7 states that the number k of input/output pairs of length m that a transformer can memorize via a prompt of length m_p is at most O(m_p/m): the proportion of ε-accessible output sequences decays exponentially with k. Theorem 4.10, in a mean-field/Wasserstein formulation, claims that the proportion of output distributions accessible via arbitrary-length prompts decays as O(exp(-k 3^d/ε^d)), independent of prompt length, for a transformer with Lipschitz constant L, embedding radius r, and dimension d. Section 5 adds statements that single-layer transformers have very limited prompt-tuning expressivity. Theorems 4.7 and 4.10 are also claimed to hold for masked self-attention.","tokens_in":20497,"tokens_out":22439,"duration_ms":273334,"significance":"If correct, the paper would be a valuable theoretical complement to empirical observations of long-context degradation: it would show that prompt-based memorization is bounded by prompt length and that the fraction of target distributions accessible by prompt tuning shrinks exponentially in the number of stored items. The use of mean-field transformers and Wasserstein metric entropy is appropriate, and the main derivations are explicit in L, r, d, and ε, with no fitted constants. However, the central quantitative claim of Theorem 4.10 is currently not established as stated because of a packing-scale error in Appendix D, and Section 5 contains statements that are internally inconsistent. The qualitative conclusion may survive after repair, but the paper requires substantial revision before the advertised results can be accepted.","major_comments":[{"comment":"The packing step inverts the covering scale. To count 3ε-separated target distributions one needs M(G,3ε) ≥ N(G,3ε) ≥ C^{-1} exp(1/(3ε)^d) = C^{-1} exp(3^{-d}/ε^d). The proof instead uses the lower bound exp(3^d/ε^d), which corresponds to scale ε/3. An ε/3-separated family is not a 3ε-packing: one accessible output can lie within ε of many such targets, so the Cin/Cout counting in the proof is invalid. Consequently Theorem 4.10's rate O(exp(-k 3^d/ε^d)) and the displayed threshold are not established. The same argument, after repair, yields at best O(exp(-k/(3ε)^d)) (up to constants), still exponential in k but with different ε-dependence.","section":"Appendix D / Theorem 4.10"},{"comment":"The object counted in Theorem 4.10 is ambiguous. Definition 4.5 defines accessibility for a single output distribution μY, but the proof in Appendix D counts k-tuples of independent output spaces, since Cout is the k-th power of the single-space packing number. If the intended statement is about k-tuples (μY_1,...,μY_k), the definition and theorem should say so. Moreover, 'proportion' over P_c has no canonical volume; it must be defined explicitly as a metric-entropy/packing ratio. Without this clarification the theorem is not a well-defined quantitative claim.","section":"Definitions 4.4–4.5 and Theorem 4.10"},{"comment":"The dimension formula is inconsistent. For h=1 and d=5, the formula gives (d-2)!/(d-4)! = 6, but R^5 has no 6-dimensional subspace. The formula appears to count ordered orthogonal frames rather than the dimension of a vector space. In addition, the statement quantifies (y1,...,y_{h+1}) but the conclusion only refers to i∈{1,2}. The proof of Lemma E.1 is a chain of unexplained identities and does not rigorously establish the advertised accessibility statement. Theorem 5.7 needs to be restated and reproved.","section":"Theorem 5.7 / Appendix E"},{"comment":"Theorem 5.8 uses invertibility of the MLP via Behrmann et al. (the condition ∥W1∥2·∥W2∥2<1) in its proof, but this assumption is absent from the theorem statement. The conclusion 'τ([P,xi,x0])^{-1} ≥ (1−∥W1∥2·∥W2∥2)r/2' compares a vector to a scalar; presumably a norm is intended. The hypotheses and conclusion of the theorem must be stated precisely.","section":"Theorem 5.8 / Assumption 5.5"}],"minor_comments":[{"comment":"Typos and wording issues include 'refered' in the Introduction, 'independant' in §4.3, and 'Lipshitz' in the footnote; a careful proofreading pass is needed.","section":"Throughout"},{"comment":"The notation τ([P,xi,x0])^{-1} uses -1 as a last-column index per Section 1.3, but in Section 5 it appears without recalling this convention and is easy to misread as an inverse; define it explicitly at first use.","section":"Section 5 notation"},{"comment":"The phrase 'proportion (in terms of volume)' should be formalized: the proof counts packing balls inside B^{dm}(0,r) and uses Cin/Cout as a volume-ratio surrogate. The reference measure and possible boundary effects should be stated.","section":"Theorem 4.7"},{"comment":"The proof imports Kloeckner's critical-exponent result without stating the theorem or verifying its hypotheses for the set G of empirical measures. Since this lower bound is load-bearing for Theorem 4.10, please state the external theorem precisely and justify that G has the required critical exponent.","section":"Proposition 3.6 / Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The paper contains promising ideas and the linear scaling result (Theorem 4.7) appears plausible, but the current version is not internally consistent. The packing-scale error in Theorem 4.10 and the impossible dimension formula in Theorem 5.7 need to be fixed before the claims can be taken at face value. I recommend a major revision rather than rejection because the main qualitative conclusions may be salvageable with corrected constants and a careful restatement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the clean result here is Theorem 4.7: the number of input/output pairs a transformer can memorize via prompt tuning is at most linear in prompt length. The covering/Lipschitz argument is elementary but appears correct, and extending it to arbitrary multi-layer, multi-head transformers and to masked self-attention is a genuine advance over the single-layer, assumption-heavy results of Wang et al. Second, the flagship Theorem 4.10 has a quantitative error: the proof counts epsilon/3-separated output distributions as if they were 3epsilon-separated. Proposition 3.6 gives a covering-number lower bound at scale epsilon, which yields a packing at scale 2epsilon at best, not 3epsilon. Using the correct scale gives roughly O(exp(-k/(3epsilon)^d)) instead of the claimed O(exp(-k 3^d/epsilon^d)). The exponential-in-k decay survives, but the epsilon-dependence is much weaker and the theorem as stated is not supported. The identity-transformer thought experiment in the stress-test is consistent with this: the qualitative decay can hold, but not at the claimed rate. The paper also overreaches in the abstract and intro by calling this the first formal proof of empirically observed long-context performance degradation. The theorems bound the set of reachable outputs for an arbitrary transformer; they do not say that trained models will fail on long prompts. That is a meaningful limitation that should be stated. Section 5 has a clear dimension bug: for h=1, d=5, the stated dimension formula gives 6, which is impossible in R^5. The single-layer expressivity result may be repairable, but as written it is wrong. There is also some ambiguity about whether G in the mean-field section includes all empirical measures or a fixed-length family; the imported metric-entropy estimates from Kloeckner and Nguyen are standard, but the paper should be explicit about the closure issues. Despite these problems, this is a paper worth engaging with. The linear scaling theorem is novel and likely correct; the mean-field framework for prompt tuning is a useful perspective; and the packing error is fixable. It is not a desk reject. Send it to peer review, but expect the authors to correct the packing scale, fix the dimension formula, and temper the claims about long-context degradation.","headline":"New linear-scaling bound for prompt tuning is solid; the exponential-decay theorem has a real packing-scale error that inflates the rate, but the qualitative point likely survives.","tokens_in":662,"tokens_out":757,"would_cite":true,"duration_ms":119846,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","60B05","52C17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Prompt tuning in transformers can store at most linearly as much information as the prompt length, and beyond that the fraction of reachable outputs decays exponentially.","keywords":["prompt tuning","transformer memorization","in-context learning","long-context degradation","Lipschitz continuity","covering numbers","Wasserstein distance","mean-field transformer"],"falsifier":"Compute or lower-bound the Wasserstein covering number of the set of empirical measures with n atoms in the d-dimensional ball for fixed n; if it grows only polynomially in 1/ε rather than exponentially, Theorem 4.10's exponential decay cannot hold for outputs with n atoms. Alternately, exhibit a fixed transformer whose prompt of length mp reliably reproduces k ≫ mp/m prescribed input/output pairs within tolerance ε—Theorem 4.7 says such a transformer can succeed only on a vanishingly small fraction of output sequences.","tokens_in":19985,"feed_emoji":"🧠","tokens_out":8894,"duration_ms":100913,"temperature":0.7,"pith_summary":"This paper tries to prove that prompt tuning—adapting a fixed transformer by prepending a learnable prompt instead of changing weights—has a hard information bottleneck. It claims the number of input/output pairs a transformer can reliably memorize through a prompt of length mp scales at most linearly with mp, no matter how large the model or the context window is. In the mean-field limit it further claims that the set of output distributions reachable by any prompt shrinks exponentially as the number of stored pairs grows, which would formally explain the long-context degradation observed in large language models. If correct, the limitation is architectural rather than an optimization artifact: longer prompts cannot rescue memorization.","feed_headline":"Prompt tuning can memorize only linearly with prompt length","feed_subtitle":"Theorems show the reachable-output share collapses exponentially with stored examples, explaining long-context failure.","key_machinery":"The key mechanism is a volume-versus-Lipschitz counting argument. A transformer, or its mean-field generalization as a map between Wasserstein spaces of probability measures, is L-Lipschitz on bounded inputs, so any ε/L-ball of prompts can only produce outputs within ε of one another. The number of distinguishable output sequences or distributions is therefore bounded by how many such balls fit in the output space, measured through covering and packing numbers. For the mean-field theorem, the crucial lower bound is that the set of discrete output distributions has Wasserstein covering number at least exp(1/ε^d), giving the exponential decay in k.","core_discovery":"The central claim is that prompt tuning has an inherent memory ceiling. Theorem 4.7 bounds, in volume terms, the fraction of output sequences that a fixed transformer can approximately produce by varying only the prepended prompt: once the number k of stored input/output pairs exceeds a constant multiple of mp/m, that fraction decays exponentially in k. Theorem 4.10 removes dependence on prompt length by passing to the mean-field transformer acting on probability measures; it states that the proportion of output distributions that are ε-accessible through any prompt is at most O(exp(-k 3^d / ε^d)) once k is large enough relative to the Lipschitz constant, embedding radius, dimension, and tol","pith_inferences":["A testable corollary the authors do not draw: measuring how many random key-value pairs a fixed LLM can retrieve through prompt search as mp grows should show a sharp threshold with slope about 1/m, set by the effective Lipschitz constant and embedding radius of the model.","The exponential factor in embedding dimension d suggests that high-dimensional token embeddings amplify this memorization bottleneck: they make the total output space huge while the set reachable by any prompt stays relatively small.","If the bound is tight, retrieval-augmented generation or weight updates are not merely conveniences but structural necessities: external memory changes the input distribution or the map itself, bypassing the covering-number constraint that limits prompt-only memorization.","The mean-field theorem counts prompts as empirical distributions, so its exponential decay rate should hold regardless of prompt token count once the prompt distribution is rich enough; a natural extension would be to make the pre-exponential dependence on prompt length explicit."],"forward_implications":["For in-context learning, a pre-prompt listing k example pairs can reliably memorize at most k ≈ C·mp/m pairs; adding more examples cannot make all of them reliably recallable through the prompt alone.","Long-context performance degradation is not merely a training or optimization artifact: for a fixed trained transformer, the fraction of output distributions reachable by any prompt shrinks exponentially in the number of stored pairs, independent of context size.","The linear scaling k ∈ O(mp/m) is optimal for encoding information as input/output pairs in the prompt, which implies soft-prompt optimization can gain at most linearly over discrete prompt engineering in this memorization setting.","The main results also hold for masked (causal) self-attention, so decoder-only transformer language models are covered by the limitation.","For single-layer transformers, the reachable output set is essentially a low-dimensional subspace, so even approximate memorization of two input/output pairs sharing a token fails for generic transformers."],"supporting_citations":[{"why":"Defines the transformer layers (self-attention plus MLP) whose prompt-tuning memory is analyzed.","marker":"Vaswani et al. [2017]"},{"why":"Supplies the L-Lipschitz bounds for finite and masked self-attention and the mean-field Lipschitz framework used in the main proofs.","marker":"Castin et al. [2024]"},{"why":"Supplies the mean-field self-attention Lipschitz bound and position-aware distance used for masked attention.","marker":"Geshkovski et al. [2023]"},{"why":"Gives volume-based covering and packing estimates used to count how many output sequences the prompt balls can reach in Theorem 4.7.","marker":"Vershynin [2025]"},{"why":"Gives the upper bound on the covering number of discrete probability measures used to cover prompt distributions in Theorem 4.10.","marker":"Nguyen [2013, Lemma 4.b]"},{"why":"Gives the Wasserstein-space covering lower bound exp(1/ε^d) that drives the exponential decay in Theorem 4.10.","marker":"Kloeckner [2014, Theorem 1.3]"},{"why":"Establishes the Polish-space structure of (G, W_q) used in the covering-number lower bound lemma.","marker":"Villani [2008, Chapter 6]"},{"why":"Provides the earlier single-layer prompt-tuning limitation under restrictive assumptions that Section 5 generalizes.","marker":"Wang et al. [2023a]"},{"why":"Defines pushforward maps and q-Wasserstein distance used to state the mean-field transformer.","marker":"Santambrogio [2015]"}],"fun_headline_variants":["Prompt tuning memory capped: linear scaling proven","Transformers can't memorize beyond linear prompt length","Formal proof: prompt tuning only stores linearly","Long context won't help: transformer memory capped","Prompt tuning's memory limit: linear, not more"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that the space of possible prompt-produced output distributions is as large as the Wasserstein covering lower bound N(G, W_q, ε) ≥ exp(1/ε^d)/C; if finite-atom empirical measures actually have smaller metric entropy, the exponential unaccessibility of Theorem 4.10 collapses to a weaker polynomial decay.","fun_headline_variants_meta":{"raw":{"variants":["Prompt tuning memory capped: linear scaling proven","Transformers can't memorize beyond linear prompt length","Formal proof: prompt tuning only stores linearly","Long context won't help: transformer memory capped","Prompt tuning's memory limit: linear, not more"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000172,"raw_usage":{"total_tokens":1075,"prompt_tokens":667,"completion_tokens":408,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":411,"completion_tokens_details":{"reasoning_tokens":351}},"tokens_in":411,"tokens_out":408,"duration_ms":5576,"temperature":1.0,"reasoning_tokens":351,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:38:16.991301+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute or lower-bound the Wasserstein covering number of the set of empirical measures with n atoms in the d-dimensional ball for fixed n; if it grows only polynomially in 1/ε rather than exponentially, Theorem 4.10's exponential decay cannot hold for outputs with n atoms. Alternately, exhibit a fixed transformer whose prompt of length mp reliably reproduces k ≫ mp/m prescribed input/output pairs within tolerance ε—Theorem 4.7 says such a transformer can succeed only on a vanishingly small fraction of output sequences.","supporting_citations":[{"cited_title":"The emergence of clusters in self-attention dynamics","cited_arxiv_id":null,"evidence_quote":"Supplies the mean-field self-attention Lipschitz bound and position-aware distance used for masked attention."},{"cited_title":"High-Dimensional Probability: An Introduction with Applications in Data Science","cited_arxiv_id":null,"evidence_quote":"Gives volume-based covering and packing estimates used to count how many output sequences the prompt balls can reach in Theorem 4.7."},{"cited_title":"Convergence of latent mixing measures in finite and infinite mixture models","cited_arxiv_id":null,"evidence_quote":"Gives the upper bound on the covering number of discrete probability measures used to cover prompt distributions in Theorem 4.10."},{"cited_title":"Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften","cited_arxiv_id":null,"evidence_quote":"Establishes the Polish-space structure of (G, W_q) used in the covering-number lower bound lemma."},{"cited_title":"Optimal transport for applied mathematicians","cited_arxiv_id":null,"evidence_quote":"Defines pushforward maps and q-Wasserstein distance used to state the mean-field transformer."}],"review_version":1}