Pith. sign in

REVIEW 4 major objections 4 minor 2 cited by

The paper proves that no algorithm can compute a length generalization bound for two-layer C-RASP programs and hence for a corresponding class of transformers.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 23:42 UTC pith:OCVXYMHP

load-bearing objection Closes Chen et al.'s open problem with an uncomputability result for depth-2 C-RASP (via Hilbert's 10th) plus a tight exponential bound for C-RASP+; the core reductions hold, but the transformer transfer leans on an unverified cited equivalence and two lemmas need patching. the 4 major comments →

arxiv 2603.02238 v2 pith:OCVXYMHP submitted 2026-02-13 cs.LG cs.FLcs.LO

Length Generalization Bounds for Transformers

Andy Yang , Pascal Bergstr\"a{\ss}er , Georg Zetzsche , David Chiang , Anthony W. Lin This is my paper
classification cs.LG cs.FLcs.LO MSC 03B7003D3568Q3268Q45
keywords length generalizationC-RASPtransformersundecidabilitylength complexityfixed-precision transformersTL[-3] temporal logicHilbert's 10th problem
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper settles an open question about when a transformer can be guaranteed, from finite training data, to behave correctly on arbitrarily longer inputs. It proves that for C-RASP, a counting and temporal logic tightly connected to transformer encoders, no terminating algorithm can compute a length generalization bound even with only two layers; because of an existing depth-preserving equivalence, the same uncomputability transfers to two-layer transformers that round arithmetic outside attention. The proof encodes any system of Diophantine equations as a C-RASP language whose emptiness is equivalent to solvability, linking training-data sufficiency to Hilbert's tenth problem. Complementing this, the paper shows that the positive fragment C-RASP+, equivalent to fixed-precision transformers, does admit a computable bound, that the bound is exponential in program size, and that this exponential is worst-case necessary. The upshot: for general transformers, length generalization cannot be certified by any finite data bound; for fixed-precision transformers, it can, but only with exponentially long examples.

Core claim

On the paper's own terms, the central discovery is twofold. First, language emptiness is undecidable for depth-two C-RASP: the authors show that C-RASP formulas can be normalized to depth two while preserving satisfiability, and that solvability of a Diophantine system is equivalent to nonemptiness of an encoded counting language. Since a computable length bound exists if and only if language equivalence is decidable, it follows that the length complexity of C-RASP—and of the (1, log n)-precision transformers that define the same language class—grows faster than every computable function. Second, for C-RASP+, where counting is threshold-based and coefficients are nonnegative, the paper gives

What carries the argument

The argument's load-bearing objects are two encodings. The negative result uses a symbol-count encoding: variables of a Diophantine system become letters, a solution becomes a string whose per-letter counts are the variable values, and equations of the forms x=c, x+y=z, and x·y=z become C-RASP formulas over prefix-count terms; concatenating the encodings with separators and equating counts across blocks yields a C-RASP formula that is satisfiable exactly when the equation has a solution. The positive result uses a threshold decomposition: every C-RASP+ counting comparison can be rewritten as a disjunction of threshold predicates of the form #[φ] ≥ c, which are then compiled into the strict-p

Load-bearing premise

The transfer from C-RASP to transformers relies on a previously published depth-preserving equivalence between C-RASP and a specific class of (1, log n)-precision transformers, assumed without re-derivation here; if that equivalence is lossy for the future-masked, rounding-based transformer variant used in the appendix, the impossibility would attach to C-RASP but not to transformers.

What would settle it

Either exhibit a two-layer transformer of the specified future-masked, rounding-based kind whose language is not definable in depth-two C-RASP, breaking the cited equivalence; or, for the positive claim, exhibit a family of C-RASP+ programs of size polynomial in n whose shortest accepted string is more than exponential in n, contradicting Proposition 4.6. A more direct falsifier would be a terminating algorithm that decides nonemptiness for the specific depth-two C-RASP formulas produced by the Diophantine encoding, bypassing Hilbert's tenth problem only if the encoding is flawed.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • No terminating learning algorithm can output a certified length-generalizing transformer for the general class, even when it receives all strings up to any chosen length and optimizes perfectly on them.
  • The minimal training length needed for guaranteed generalization grows faster than every computable function for two-layer (1, log n)-precision transformers and for any transformer class that contains C-RASP.
  • For fixed-precision (1,1)-precision transformers, training on all strings up to an exponential length in model size is sufficient to identify the target language among programs of bounded size, and some languages genuinely require exponential-length evidence, such as the set of strings with at least 2^p occurrences of a.
  • Existing positive bounds for restricted two-layer classes do not contradict the undecidability: those classes omit constant bias terms and are strictly weaker than full C-RASP2, so bounded-depth Dyck languages escape them.
  • Because the negative result holds under ideal access to all training examples and perfect optimization, practical gradient-based training of general transformers cannot expect a stronger formal guarantee.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the uncomputability transfers faithfully to practiced transformer definitions, then exact, certified length generalization is not merely empirically elusive but formally unobtainable without restricting precision, architecture, or training objective.
  • The exponential lower bound suggests a qualitative separation: fixed-precision transformers are learnable in principle, but the guaranteed training-data length can be prohibitively large; the number of examples needed might still be polynomial, an open direction the paper flags.
  • The threshold-based positive fragment suggests a concrete recipe for engineering length-generalizing behavior: express a task as threshold counts over bounded precision rather than unrestricted counting. One could test this by training fixed-precision transformers on threshold-count tasks and observing whether generalization appears at the predicted training lengths.
  • The Hilbert-style encoding implies that the decidable-undecidable boundary for length generalization runs through counting with constant bias terms; removing bias (restricting to nonnegative coefficients and thresholds) restores computability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies the computability of non-asymptotic length generalization bounds for C-RASP, a counting-based programming formalism tied to transformers, and for two precision-restricted transformer families. The main negative result is undecidability of emptiness for C-RASP programs of depth two (Theorem 3.1), obtained by encoding Diophantine equations in a regular-looking string language; by the Chen et al. equivalence between computable length-complexity bounds and decidable language equivalence, the paper concludes that C-RASP2 has no computable length-complexity bound (Corollary 3.6). It then asserts the same for (1, log n)-precision transformers via a depth-preserving expressive equivalence to C-RASP (Theorem 5.1). The positive contribution is for the fragment C-RASP+ and (1,1)-precision transformers: each satisfiable program is shown to have a witnessing string of at most exponential length, with an exponential lower bound, yielding a tight exponential length-complexity bound (Propositions 4.6, 5.5, Theorem 4.7). The paper also gives size bounds for translations between C-RASP+ and fixed-precision transformers in Appendix B.

Significance. If the proof issues identified below are repaired, this is a significant contribution. It closes an open problem raised by Chen et al. (2025) by showing that non-asymptotic length generalization fails for a natural class capturing transformers, and it provides the first tight positive length-complexity bound for a meaningful positive fragment. The negative reduction from Hilbert's Tenth Problem is elegant and has no fitted parameters or data-dependent assumptions; the positive side connects C-RASP+ to the small-model property of TL[-3] and to fixed-precision transformers. The paper is written in a largely self-contained manner and its high-level architectural claims are plausible. However, several load-bearing proofs currently contain formal errors or rely on an unstated black-box equivalence, so the advertised theorems are not yet established as written.

major comments (4)
  1. [§3.2, proof of Theorem 3.1] The formula defining the combined language is φ := φ_L ∧ ⋁_{x∈V} ψ_x. Correctness of the reduction requires that every variable has the same count in every equation block; that is a conjunction over x. With the disjunction as written, a string is accepted when only one variable's counts agree across blocks, so L(φ) can be nonempty even if the Diophantine system has no solution. For example, for the unsolvable system {x=c1, y=c2} with c1≠c2, a string with x-counts 1 and 5 but equal y-counts satisfies φ_L and ψ_y, hence is accepted. Please change to ⋀, or justify why the disjunction suffices.
  2. [§4, Lemma 4.2 and Proposition 4.4] The proof of Lemma 4.2 states that the set S of tuples has size (c+1)^k, 'i.e., exponential in the precision p and girth g', and then concludes that the decomposed program has size O(n^2 poly(p,g,d)). Since constants are encoded in binary, c can be as large as 2^p, so |S| is 2^{Ω(pg)}, not polynomial. The same inconsistency appears in Proposition 4.4: the translation of #[Q]≥c has size O(c·|ψ|), which is exponential in p, yet the proposition concludes a polynomial total size. These claims are load-bearing for the stated exponential upper bound. The final bound may still be recoverable if the exponential factors are tracked correctly, but the proofs as written are mathematically incorrect.
  3. [§4, Lemma 4.5] The small-model property is applied to a formula ψ over the set-letter alphabet 2^Γ, where Γ = Σ ∪ {P_1,...,P_k}. The proof asserts that from the accepted enriched word w' there is a word w∈Σ* with w_i∈w'_i. This is unjustified: the adapted semantics imposes no requirement that w'_i contain a symbol of Σ, so a position may have w'_i∩Σ = ∅. The gap is fixable by adding to ψ a conjunct forcing exactly one σ∈Σ at every position (expressible in the set-letter semantics); any plain accepting string lifts to singleton sets, so satisfiability of P is preserved. As written, the polynomial-witness bound does not transfer to plain strings.
  4. [§5, Definition B.2 / Theorem 5.1] The transfer from C-RASP to (1, log n)-precision transformers rests entirely on the cited 'Yang et al., 2025, Theorem 3.1' depth-preserving expressive equivalence. The paper neither states the theorem nor verifies that it applies to the specific future-masked transformer defined in Definition B.2, which uses scores s_ij = q_i·k_j, attention contributions round(exp(s_ij)), and a special denominator-zero convention. Since Theorem 1.1's 'transformers of depth two or beyond' depends on depth preservation for this exact model, this is a load-bearing black box. Please either state and prove the equivalence for Definition B.2 or reformulate Theorem 5.1 for the class for which the cited equivalence is actually established.
minor comments (4)
  1. [§3.2, Lemma 3.5] The displayed condition '|u|_$ = i−2' appears to have an indexing error; for i=1 it would require a negative dollar count. It should likely be '|u|_$ = i−1' (or the numbering of segments adjusted consistently).
  2. [Appendix A.1, Figure 1] The variables d_a and d_b appear in the figure caption but are not defined in the surrounding text; please define them.
  3. [§3.1, Lemma 3.4] The overbar notation for barred symbols is not visually rendered in several places (e.g., 'y's and y's strictly alternate'), which makes the multiplication encoding hard to follow. Please ensure the typeset version distinguishes x, y, z from their barred counterparts.
  4. [§4, Proposition 4.6] The lower-bound example states that L(P_n) has a unique string of length n; this is correct for the unary alphabet, but the wording 'the smallest (and only) string' could be clarified by noting the alphabet is {a}.

Circularity Check

0 steps flagged

No significant circularity; the C-RASP uncomputability and C-RASP+ exponential bounds are proved from external anchors, with the transformer transfer citing an independent earlier equivalence rather than assuming the conclusion.

full rationale

The claimed derivation chain is not circular. Theorem 3.1/Corollary 3.6 is proved internally by encoding Diophantine equations as regulated C-RASP formulas (Lemmas 3.4, 3.5) and reducing from Matiyasevich's theorem; the 'and hence for transformers' step cites Yang et al. (2025, Thm. 3.1) as a previously published depth-preserving expressive equivalence. Although that citation shares authors with the present paper, it is a parameter-free theorem with stated assumptions (C-RASP vs. (1,logn)-precision transformers) that does not assume the uncomputable length complexity result; it is therefore independent support, not a self-citation that constructs the conclusion. The positive results (Theorem 4.7, Propositions 5.3-5.5) similarly rest on a direct Appendix B translation and on Etessami et al.'s TL[-3] polynomial-witness bound, an external anchor; the exponential lower bound is witnessed concretely by P_n = (#[a] = n), so it is not an artifact of the translation. The possible mismatch between Definition B.2's future-masked rounded-attention transformer and the transformer model in the cited Yang et al. equivalence, and the projection step in Lemma 4.5 from set-letter witnesses to plain strings, are correctness risks rather than definitional reductions: neither makes a claimed result equal to its own input. There are no fitted parameters, no empirical data, and no renaming of known results in the derivation chain. Finding: no significant circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No fitted numbers or invented entities: the paper is proof-theoretic and anchors externally to Matiyasevich's theorem, Etessami et al., Chen et al., and published C-RASP/transformer equivalences. The two most load-bearing cited inputs are the Yang et al. (2025) expressivity bridge (carries the impossibility to transformers) and the Etessami et al. witness bound (carries the positive upper bound).

axioms (5)
  • standard math Hilbert's 10th problem is undecidable, and every Diophantine equation reduces to a system of equations x=c, x+y=z, x*y=z over N with distinct variables.
    The foundation of Theorem 3.1's reduction in Section 3; Matiyasevich's theorem is used as an external undecidability anchor.
  • domain assumption C-RASP is depth-preservingly expressively equivalent to (1,logn)-precision transformers (Yang et al., 2025, Theorem 3.1).
    Cited, not re-proved; this bridge carries the negative result from C-RASP to transformers in Theorem 5.1. Two present authors overlap with the cited work.
  • domain assumption A computable upper bound on length complexity exists iff language equivalence is decidable for the hypothesis class (Chen et al., 2025, Lemma 3.4).
    The bridge converting emptiness undecidability into non-existence of learning algorithms (Corollary 3.6); cited, not re-proved.
  • domain assumption Every satisfiable TL[-3] formula has a witness string of length polynomial in the formula size under set-letter semantics (Etessami et al., 2002).
    Load-bearing for the exponential upper bound in Lemma 4.5 and Propositions 4.6/5.5; cited, not re-proved, and the lemma's projection step is where the assumption is applied.
  • domain assumption (1,1)-precision transformers are expressively equivalent to TL[-3] (Li & Cotterell, 2025, Theorems 3.2-3.3).
    Basis of Theorem 5.2's transfer of the exponential bound to fixed-precision transformers; cited.

pith-pipeline@v1.3.0-alltime-deepseek · 23016 in / 40231 out tokens · 363315 ms · 2026-08-02T23:42:03.642728+00:00 · methodology

0 comments
read the original abstract

Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a guarantee, one needs to be able to compute a length generalization bound, beyond which the model is guaranteed to generalize. This paper concerns the open problem of the computability of such generalization bounds for C-RASP, a class of languages which is closely linked to transformers. A positive partial result was recently shown by Chen et al. for C-RASP with only one layer and, under some restrictions, also with two layers. We provide complete answers to the above open problem. Our main result is the non-existence of computable length generalization bounds for C-RASP (already with two layers) and hence for transformers. To complement this, we provide a computable bound for the positive fragment of C-RASP, which we show equivalent to fixed-precision transformers. For both positive C-RASP and fixed-precision transformers, we show that the length complexity is exponential, and prove optimality of the bounds.

Figures

Figures reproduced from arXiv: 2603.02238 by Andy Yang, Anthony W. Lin, David Chiang, Georg Zetzsche, Pascal Bergstr\"a{\ss}er.

Figure 1
Figure 1. Figure 1: A visualization of the proof idea. ℓ1 and ℓ2 are the two lines above and below the line ↼ #a = ↼ #b, the horizontal band contains all strings in Dk, and ϵk,Ψ = da + db. (which are satisfied at ±ϵk,Ψ positions) over strings in Dk+1. We can plug these values into the definition of ϕ to find that the truth value of ϕ is equivalent to: X i : ψ∈Ψ⊤ λψ(|w| ± ϵk,Ψ) + X i : ψ∈Ψ⊥ λψ(±ϵk,Ψ) > z|w|. Here, the truth va… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Any-Dimensional Learning by Sampling

    math.ST 2026-07 accept novelty 7.0

    Random sampling maps (with-replacement, binning, species) induce metrics that give uniform any-dimensional generalization and sketching rates for continuous functions on sequences, graphs and tensors.

  2. Hierarchical Domain Generalization

    cs.LG 2026-07 conditional novelty 6.0

    Over infinite domains, hierarchy-uniform domain generalization is impossible for every nontrivial hypothesis class; a length-generalization bound is a property of the length hierarchy, not a hierarchy-free guarantee.

Reference graph

Works this paper leans on

11 extracted references · 2 linked inside Pith · cited by 2 Pith papers

  1. [5]

    Izzo, Z., Nichani, E., and Lee, J

    URL https://openreview.net/forum? id=U49N5V51rU. Izzo, Z., Nichani, E., and Lee, J. D. Quantitative bounds for length generalization in transformers. InProceedings of the 14th International Conference on Learning Represen- tations (ICLR), 2026. URL https://openreview. net/forum?id=TLSUIyBIfs. Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, ...

    2026

  2. [7]

    Nogueira, R., Jiang, Z., and Lin, J

    URL https://openreview.net/forum? id=O1abxStFcy. Nogueira, R., Jiang, Z., and Lin, J. Investigating the limi- tations of transformers with simple arithmetic tasks. In Proceedings of Math-AI: ICLR Workshop on the Role of Mathematical Reasoning in General Artificial Intel- ligence, 2021. URL https://arxiv.org/abs/ 2102.13019. Nye, M., Andreassen, A. J., Gur...

    Pith/arXiv arXiv 2021

  3. [8]

    S¨alzer, M., K ¨ocher, C., Kozachinskiy, A., Zetzsche, G., and Lin, A

    URL https://openreview.net/forum? id=VVO3ApdMUE. S¨alzer, M., K ¨ocher, C., Kozachinskiy, A., Zetzsche, G., and Lin, A. W. The counting power of transformers. InProceedings of the 14th International Conference on Learning Representations (ICLR), 2026. URL https: //openreview.net/forum?id=IAFwK6NyrP. Strobl, L., Merrill, W., Weiss, G., Chiang, D., and An- ...

    2026

  4. [9]

    Wang, Z., Nichani, E., Bietti, A., Damian, A., Hsu, D., Lee, J

    URL https://proceedings.mlr.press/ v267/varre25a.html. Wang, Z., Nichani, E., Bietti, A., Damian, A., Hsu, D., Lee, J. D., and Wu, D. Learning compositional functions with transformers from easy-to-hard data. InProceed- ings of the 38th Conference on Learning Theory (COLT), pp. 5632–5711, 2025. URL https://proceedings. mlr.press/v291/wang25a.html. Weiss, ...

    2025

  5. [11]

    Yang, A., Strobl, L., Chiang, D., and Angluin, D

    URL https://openreview.net/forum? id=jPduiyxyfw. Yang, A., Strobl, L., Chiang, D., and Angluin, D. Simu- lating hard attention using soft attention.Transactions of the Association for Computational Linguistics, 2026a. doi:10.1162/TACL.a.597. Yang, A., Watson, C., Xue, A., Bhattamishra, S., Llarena, J., Merrill, W., Ferreira, E. D. S., Svete, A., and Chi- ...

    doi:10.1162/tacl.a.597 2024

  6. [1978]

    Gr¨adel, E., Kolaitis, P

    doi:10.1016/S0019-9958(78)90562-4. Gr¨adel, E., Kolaitis, P. G., and Vardi, M. Y . On the decision problem for two-variable first-order logic.Bulletin of Symbolic Logic, 3(1):53–69, 1997. doi:10.2307/421196. Hilbert, D. Mathematical Problems.Bulletin of the American Mathematical Society, 8(10):437–479, 1902. doi:10.1090/S0002-9904-1902-00923-3. Hoffmann, ...

    doi:10.1016/s0019-9958(78)90562-4 1997

  7. [2010]

    doi:10.1109/TIME.2010.20. Li, J. and Cotterell, R. Characterizing the expressiv- ity of fixed-precision transformer language models. InAdvances in Neural Information Processing Sys- tems (NeurIPS), 2025. URL https://openreview. net/forum?id=29LwAgLFpj. Matiyasevich, Y . V .Hilbert’s 10th Problem. Foun- dations of Computing. MIT Press, Cambridge, MA, 1993....

    arXiv 2010

  8. [2021]

    URL https://proceedings.mlr.press/ v139/weiss21a.html. Yang, A. and Chiang, D. Counting like transformers: Com- piling temporal counting logic into softmax transformers. InProceedings of the First Conference on Language Mod- eling (CoLM), 2024. URL https://openreview. net/forum?id=FmhPg4UJ9K. Yang, A., Chiang, D., and Angluin, D. Masked hard- attention tr...

    2024

  9. [2023]

    Etessami, K., Vardi, M

    URL https://openreview.net/forum? id=WbxHAzkeQcn. Etessami, K., Vardi, M. Y ., and Wilke, T. First-order logic with two variables and unary temporal logic. Information and Computation, 179(2):279–295, 2002. doi:10.1006/inco.2001.2953. Gold, E. M. Language identification in the limit. Information and Control, 10(5):447–474, 1967. doi:10.1016/S0019-9958(67)...

    arXiv 2002

  10. [2024]

    Bergstr¨aßer, P., Cotterell, R., and Lin, A

    URL https://openreview.net/forum? id=gbrHZq07mq. Bergstr¨aßer, P., Cotterell, R., and Lin, A. W. Transform- ers are inherently succinct. InProceedings of the 14th International Conference on Learning Representations (ICLR), 2026. URL https://openreview.net/ forum?id=Yxz92UuPLQ. arXiv:2510.19315. Chen, T., Ma, T., and Li, Z. Non-asymptotic length generaliz...

    Pith/arXiv arXiv 2026

  11. [2025]

    Del´etang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wen- liang, L

    URL https://proceedings.mlr.press/ v267/chen25ar.html. Del´etang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wen- liang, L. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Veness, J., and Ortega, P. A. Neural networks and the Chomsky hierarchy. InProceedings of the 11th Interna- tional Conference on Learning Representations (ICLR),