acceptodds
Under review as a conference paper at ICLR 2027

Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones

Abstract

Transformer-based language models exhibit an astonishing capacity to generalize to longer and more difficult problem instances than those seen in training. However, theoretical understanding of this phenomenon still lags behind. Unlike most machine learning models, the generalisation abilities of transformers inherently require considering two axes. On one hand, one must examine in-distribution statistical generalisation, which concerns the ability of a model to broaden a function from training samples to novel samples of the same distribution. On the other hand, given the sequential nature of language data, one must also consider length generalisation, which reflects whether a model trained on inputs of a given length can extrapolate to longer ones. These two notions have mostly been studied separately, leaving open how they interact. In this work, we give a joint treatment of both axes for fixed-precision transformers. We provide bounds for generalisation guarantees in terms of the parameter sizes of the involved models, as well as the quantization space and the alphabet size that supply the sequences. Finally, we illustrate how the requirements interact between number and length of training samples. In particular, we find that increasing training length can be exponentially more efficient than increasing the sample size. Experiments support predictions of the theory.

Primary area:
learning theory
Keywords:
transformers, learning theory, length generalization

Reviews

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

This paper presents new generalization results for transformers along two different axes: in-distribution generalization and out-of-distribution generalization in terms of length. The paper provides a very novel proof for length generalization for transformers and combine it with statistical proofs for in-distribution generalization bounds to obtain novel bounds for length as well as in-distribution generalization. In particular, the paper shows that in compute budget constrained settings, length generalization comes when the transformer has seen a certain minimum length of data, and in-distribution generalization comes when we add more data. The paper provides the proofs in the setting where a student transformer learns from a teacher transformer model, and it provides experiments validating the conclusions from the bound that training on longer traces helps generalization in compute constrained setting.

Critical strengths
  • This paper provides a novel generalization bound across two axes of in-distribution generalization and length generalization. The bounds are in the setting of distillation from teacher to student, where in the length generalization bound it is shown that if the student and teacher agree on all possible words of certain finite length C (computed in the paper), then they also agree on all words of any length. This bound combined with the in-distribution generalization gives a novel generalization bound that accounts for both in-distribution and out-of-distribution data.
  • The bounds lead to the conclusion that in compute constrained settings using longer training data helps length-generalization to certain length of data, beyond which more samples help generalization. This is very insightful and likely to be useful for training of models.
  • The paper provides experiments with small transformer models that validate the claim of generalization for length generalization in compute constrained setting.
Critical weaknesses
  • Although the theory in the paper is very novel and useful, the experiments are very weak and needs further work. In particular, the experiments done are with transformers of number of layers 1 or 2 for the student transformer, which is very small compared to regularly used transformers.
  • The paper assumes in Remark 2.1 that the dimensions of the student are bigger than the teacher. It is unclear if this is a necessary assumption and if so, is it a practical one where the student is bigger than the teacher?
Questions for authors
  • Please address the concerns in the weaknesses.
1 comment

We thank the reviewer for the close reading and the positive assessment.

W1: the experiments are very weak and needs further work. In particular, the experiments done are with transformers of number of layers 1 or 2 for the student transformer, which is very small compared to regularly used transformers

We'd like to point out that, for the Alternating languages, we have substantially deeper teacher transformers (up to 6 layers -- Appendix H.1.1, H.3.1) and deeper student transformers (up to 20 layers -- Appendix H.3.2). These Alternating languages in particular are noteworthy for provably requiring increasing depth (Yang et al, NeurIPS 2025, cited in the paper); their inclusion is thus especially well-suited to understanding the role of depth.

W2: The paper assumes in Remark 2.1 that the dimensions of the student are bigger than the teacher. It is unclear if this is a necessary assumption and if so, is it a practical one where the student is bigger than the teacher?

Importantly, the student architecture needs to be able to represent the teacher’s function. The componentwise size inequalities in Remark 2.1 provide sufficient conditions for this through our explicit embedding construction. These conditions might not be necessary, as other realizations may trade off depth, width, and number of heads.

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

Generalization usually refers to whether a model performs well on unseen examples from the same distribution. For sequence models such as transformers, there is a second question: does the model still work on inputs longer than those seen during training (length generalization)? Earlier work has mostly studied generalization bounds that assume a fixed sequence length. This paper instead asks: given a fixed token budget of (number of samples) × (sequence length), how should it be split between the two? Figure 1 illustrates the main finding: increasing the training sequence length improves accuracy on 5x longer sequences much more than increasing the sample size while keeping training sequences short.

The main contribution is a set of generalization bounds for fixed-precision transformers that depend on both sample size and input length:

  1. Deterministic length generalization (Lemma 3.1). There is a number C, depending on the model size, the precision |F|, and the alphabet size |Σ|, such that if the student and teacher agree on every string of length up to C, they agree on all strings of any length. This assumes that the student sees all strings up to length C, which is unrealistic, so the paper extends the result to a more realistic probabilistic setting.
  2. Probabilistic length generalization (Lemma 3.2). This relaxes Lemma 3.1 so that the student and teacher only need to agree on most strings of length up to K, where the data distribution is uniform over all strings of length up to K. If K is large enough (roughly |Σ|·C, with the same C as in Lemma 3.1), the error stays small at every longer length.
  3. Data complexity (Proposition 4.1). This is a statistical generalization result at a fixed length, partially based on existing work (Buzaglo et al., 2024b). It bounds the number of samples needed for the student and teacher to agree, with high probability, on strings of a fixed length, for both the Guess & Check (G&C) and ERM learners.

Key result: Joint statistical and length generalization (Theorem 4.1). The main result combines Proposition 4.1 and Lemma 3.2. The key takeaway is that generalization happens when the training length is long enough to expose all representative behaviors of the task, and the sample size is large enough to reach low test error at that length. In short, examples must be long enough for the relevant behaviors to show up, and numerous enough to learn those behaviors reliably.

The authors then experimentally test the trade-off between the number of training samples and their length. The experiments use three task families: alternating languages (have we seen k alternating blocks of a's and b's?), alphabet languages (has every one of k known symbols appeared?), and induction-head tasks (for the current token, which tokens have followed it earlier in the context?). The key results are:

  1. Figure 4. Larger teachers (i.e., harder tasks) require longer and more training examples (larger K and N) for similar length-generalization performance, as predicted by the theory. Changing the student size has little impact, suggesting that the theoretical bounds are too pessimistic with respect to student size.
  2. Figures 1 and 5. There is a clear non-linear trade-off between the number of samples and their length. Allocating more of the budget to length reaches higher accuracy with fewer total tokens on all tasks. Intuitively, longer examples are more informative.
Critical strengths
  1. Important, underexplored problem of practical relevance. In real applications, LLMs and video generators are known to struggle with out-of-distribution length generalization. Insight into how to balance a training budget (number of samples vs. their length) is very valuable and potentially useful in practice.
  2. Representative setup. The setup is representative of real transformers, except that it assumes no positional encodings. Fixed precision does not seem like a major limitation, since real hardware also has finite precision.
  3. Clarity. The paper is clearly written. The figures, especially Figure 2b, convey intuition and help explain constructions used in the proofs, such as the difference function. The paper's structure follows the reasoning and derivation, which makes it easy to read and understand.
  4. Experimental validation. The experimental results are consistent with the theoretical results.
Critical weaknesses
  1. Fixed-precision regime without positional encodings. However, real transformers heavily rely on positional encodings.
  2. Idealized learners. G&C and ERM are not the Adam/SGD optimizers used in practice.
  3. Too simple tasks for the experimental evaluation. All three task families are small formal languages with small alphabets. However, the constant C depends on the alphabet size, and real language models have much larger vocabularies.
Questions for authors

Real transformers heavily rely on positional encodings. How would your results change if one assumes (absolute/relative) positional encodings in the setup?

2 comments

We thank the reviewer for the close reading and the positive assessment.

W1: Fixed-precision regime without positional encodings. However, real transformers heavily rely on positional encodings

We agree. We note that, interestingly, there is recent evidence that, while positional embeddings may be important during training, real-world LLMs might not require positional embeddings for expressivity [1].

[1] Gelberg, et al. Extending the context of pretrained LLMs by dropping their positional embedding, ICLR 2026.

W2: Idealized learners. G&C and ERM are not the Adam/SGD optimizers used in practice

We agree. Theory for multi-layer transformers learning with such optimizers is an exciting but very challenging problem for the future.

W3: Too simple tasks for the experimental evaluation. All three task families are small formal languages with small alphabets. However, the constant C depends on the alphabet size, and real language models have much larger vocabularies.

Indeed, our treatment focuses on algorithmic/formal-language tasks with small vocabularies. We hypothesize that learning theory for real-world language models will also need to take into account the inherent structure of their very large vocabularies, e.g. coming from the semantic and grammatical structure of the lexicon. Our work provides foundations for potentially tackling this in the future.

Q1: Real transformers heavily rely on positional encodings. How would your results change if one assumes (absolute/relative) positional encodings in the setup?

This will depend on the structures that these encodings will induce in the underlying DFA. For instance, RoPE might create loops in the DFA, and likely new techniques will be needed to understand generalization.

Thank you for the clarifications. I am keeping my current rating (max).

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

This paper develops joint length- and sample-complexity bounds for fixed-precision, strictly causal, multi-layer transformers by representing the student–teacher disagreement as a partially ordered automaton. The resulting bounds quantify a length threshold and a sample/length tradeoff, including a token-budget argument in which longer examples can be exponentially more effective near the automaton-coverage threshold; synthetic experiments on alternating, alphabet, and induction-head tasks show qualitatively similar trends. The theory is interesting and technically motivated, but the current evidence does not yet establish how directly the headline claim transfers to the training distribution and optimization setup used in the experiments or to standard transformer models.

Critical strengths
  1. The paper addresses an important gap between statistical generalization at a fixed sequence length and length generalization, and gives a unified statement rather than treating the two phenomena independently. Lemma 3.1 and Theorems 4.1–4.2 make the dependence on student/teacher sizes, alphabet size, precision, sample count, and training length explicit.
  2. The disagreement-automaton construction provides a useful proof mechanism: the two alternative height bounds, the probabilistic absorption argument, and the lower-bound construction in Appendix G connect the sufficient tradeoff to a concrete coverage event instead of only invoking a generic capacity bound. The token-allocation corollary is a clear, testable consequence of this mechanism.
  3. The experimental section uses three task families that vary sequential depth, alphabet/head/width requirements, and local attention, and reports both absolute- and relative-length evaluations. The protocol is described in detail, includes multiple seeds and a supervised-token-budget control, and the observed length/sample tradeoff is visually consistent with the proposed qualitative mechanism.
Critical weaknesses
  1. The main guarantees have a narrow scope: fixed finite precision, no global positional encodings, strict causal masking, realizable teacher–student containment, and ERM or the idealized Guess-and-Check learner. Local attention is handled only through an additional construction. These assumptions are sufficient for the theorem, but the framing around “transformers” and the title’s broad claim should distinguish this class from the positional, non-realizable, gradient-trained models to which the motivating discussion refers.
  2. The theorem and the experiments use different training distributions and learning criteria. The main bounds are stated for DK=Unif(Σ≤K)D_K=\mathrm{Unif}(\Sigma^{\le K}) (with a separate uniform-over-length corollary), whereas the experiments sample words of exactly length KK; the experiments also use FP32 Adam and per-coordinate BCE/logit-sign agreement, then retain only runs with perfect training accuracy, rather than sampling the Guess-and-Check posterior or requiring exact vector equality. Thus Figures 4–12 support a qualitative analogy, but they do not directly validate the stated aC(K)a_C(K), NKNK token accounting, or finite-δ guarantees.
  3. The empirical design does not isolate the claimed scaling sufficiently to support an “exponential” efficiency conclusion. In the Alphabet and Induction-Head families, teacher depth/width/head count, alphabet size, and (for induction heads) output dimension change together; KK is also adjusted by task-specific coverage rules. Means are reported after a success-conditioned, learning-rate-selected subset of at most ten seeds, with blank cells when no seed fits, but no uncertainty intervals or retained-seed counts are shown. The plots therefore cannot separate optimization failure from generalization or establish asymptotic scaling of the theoretical bound.

Justification of Recommendation

I recommend weak rejection despite the valuable unified length-and-sample complexity results and disagreement-automaton mechanism, because the experiments do not directly test the stated theoretical guarantees. The main reservations are the mismatch between theorem and experimental distributions and learning criteria, together with success-conditioned seed selection and confounded complexity sweeps. I would rate the paper higher with experiments aligned to the theorem’s sampling and evaluation definitions, complete seed and uncertainty reporting, and controlled sweeps that isolate the claimed efficiency scaling within the stated model class.

Questions for authors
  1. Can the authors state and prove a counterpart of Theorem 4.2 for the exact-length training distribution used in the experiments (or explain precisely why the existing DKD_K/uniform-length corollaries apply), and recompute the corresponding token budget and coverage probability aC(K)a_C(K)?
  2. How does per-coordinate logit-sign agreement in the FP32 experiments map to the exact vector-output disagreement used in Lemma 3.1 and Theorem 4.1? Please report, for every plotted cell, the number of attempted and retained seeds and the unconditioned results before filtering, so that optimization success and generalization can be distinguished.
  3. Can the authors add an ablation that varies one complexity axis at a time (for example, fixed alphabet and output dimension while varying teacher depth), with confidence intervals and a matched-budget baseline, and report numerical estimates of CC and aC(K)a_C(K) for the plotted tasks? This would test whether the observed tradeoff follows the predicted scaling rather than task-specific coverage heuristics.
5 comments

We thank the reviewer for the careful reading and constructive feedback.

I would rate the paper higher with experiments aligned to the theorem’s sampling and evaluation definitions, complete seed and uncertainty reporting, and controlled sweeps that isolate the claimed efficiency scaling within the stated model class.

Thank you for the helpful feedback! We have carried this out thoroughly:

  • new proofs and extensive new control experiments aligning experiments and theory in sampling and evaluation definitions (Appendix F.4.1; Corollary F.1; lines 468--485, Appendix H.4.1)
  • complete seed and uncertainty reporting (Figures 7, 8, 10, 11, 13, 15, 17, 18, 27, 29, 31, 33, 35, 37, 39, 41, 43, 44).
  • controlled sweeps: Figures 4,5 and Appendix H.3.2 does what is possible here given our task set (see more below)

We address the Weaknesses and Questions point-by-point below, including details on these revisions.

Response to Weaknesses

W1: The main guarantees have a narrow scope

We have rephrased the introduction (line 074-075) to explicitly distinguish the motivating discussion from the specific class studied.

W2: theorem and experiments use different distributions: Unif(Σ≤K)Unif(\Sigma^{\leq K}) vs Unif(Σ=K)Unif(\Sigma^{= K})

First, we now refer the reader (in line 415-417) to Corollaries F.3 and F.4: our main results also hold when sampling words of length =K=K. In fact, the result is slightly stronger, as we can remove the factor ρ\rho present in Theorem 4.2 in the corresponding Corollary F.4.

Second, we have added four control experiments (Section 5 and Appendix H.4) to address the reviewer's concerns. In Appendix H.4.1, we reproduce our results when inputs are sampled from DK=Unif(Σ≤K)D_K = Unif(\Sigma^{\leq K}). Results are highly similar (Figures 26, 28, 30).

experiments use BCE/logit-sign agreement, not exact equality

We can theoretically model BCE/logit-sign-agreement by adding a sign operation on top of the transformer (BCE is a differentiable surrogate of that); the theory carries over (Corollary F.1). This shows that our experiments can be viewed as a learnable approximation of a setting covered by our theory.

Also, as a trainable relaxation of exact vector equality (which is not differentiable), we added control experiments with L2 loss and requiring predicted outputs to be close to the target up to some tolerance. Results in Appendix H.4.3 show that results are similar, except that this is hard to train to interpolation (which echoes some prior observations on training with CE/L2 for categorical output, as we discuss there).

Figures 4–12 support a qualitative analogy, but they do not validate predictions numerically

We'd like to clarify that our theory does not aim to make numerically exact predictions (lines 518 and 1011). The point of the experiments is to illustrate qualitative analogy with asymptotically predicted patterns, as is commonly done to complement asymptotic analysis. We have changed the last sentence of the abstract (line 028) to make this division of labor more prominent, and are happy to do more if the reviewer thinks this would help.

W3: Experiments do not fully isolate the scaling

We agree that the experiments do not establish an exponential efficiency rate. That conclusion is theoretical (Theorem 4.2; Appendix G.2; Theorem G.3); the experiments examine whether longer examples improve token efficiency at practical scales. We have carefully gone through the text to ensure the phrasing is in line with this.

Note that it is infeasible to freely vary teacher size dimensions independently, as these sizes are constrained by the target task. Our experimental results do show that, within each task family, increasing the teacher size does increase NN and KK, qualitatively in line with theory (Figure 4). That's all we claim in Figure 4; we expressly do not claim testing separate predictions about D,H,LD, H, L.

no uncertainty intervals or retained-seed counts shown

We have changed the protocol so that plots use exactly 10 seeds that fit the training set (Figures 1, 4, 5), and we report standard errors over those (Figures 7, 10, 18) as well as the number of attempted runs in order to find the 10 fitting seeds (Figures 8, 11, 18). In addition, we added control experiments where we compare results with filtering and without filtering (Figures 32, 34, 36), as well as giving the number of fitting seeds among 10 unfiltered seeds for each combination (Figures 33, 35, 37). Results are very similar with or without filtering (Figures 32, 34, 36).

The plots therefore cannot separate optimization failure from generalization

This is addressed by our new control studies without filtering.

or establish asymptotic scaling of the theoretical bound.

We agree. As mentioned above, the experiments are meant to illustrate qualitative analogy with theory.

Response to Questions

Q1: Can the authors state and prove a counterpart of Theorem 4.2 for the exact-length training distribution used in the experiments and recompute the corresponding token budget and coverage probability a_C(K)?

Yes, we now include Corollaries F.3, F.4 in appendix section F.4, which provide a counterpart of Theorem 4.2 for the exact-length training distribution used in the experiments. We discuss the corresponding token budget and coverage probability with Remark F.1 in Appendix F.4.1.

Q2: How does per-coordinate logit-sign agreement in the FP32 experiments map to the exact vector-output disagreement used in Lemma 3.1 and Theorem 4.1?

Per-coordinate logit-sign agreement is covered by our theory if one adds a sign operation on top of the transformer (Corollary F.1). The sigmoid implied by training with Binary CE Loss can be viewed as a trainable relaxation of such a sign operation. Thus, our theory extends to a case close to the experimental loss/accuracy definition.

Furthermore, as described above, we have done a control study training with L2 loss and evaluating for match up to a small tolerance (Appendix H.4.3), finding models harder to train but obtaining qualitatively similar results.

Please report, for every plotted cell, the number of attempted and retained seeds and the unconditioned results before filtering, so that optimization success and generalization can be distinguished

For the main paper figures (Figures 1, 4, 5), we now report for all plotted cells, the number of attempted runs in order to achieve 10 fitting seeds: see Figures 8, 11 and 18. When the experiments don't follow our standard framework of exactly 10 fitting retained seeds, we then report the number of fitting seeds among the retained seeds (Figures 13, 15, 17, 33, 35, 37, 39, 41, 43).

Q3: Can the authors add an ablation that varies one complexity axis at a time (for example, fixed alphabet and output dimension while varying teacher depth),

For varying student complexity, we have already done this for D, H, L in Appendix H.3.2. Note that the alphabet is determined by each task and can't be controlled as other student parameters. Varying teacher complexity corresponds to varying the target function; this imposes strict limits on the axes along which teacher complexity can be varied. As for the Reviewer's example, "fixed alphabet and output dimension while varying teacher depth", this corresponds to varying between the different alternating languages (Figures 4, 6 and 9); their teachers only differ in depth. The other two language families likewise vary teacher properties (lines 397--406). Note that our experimental claim is that increasing teacher size increases the required N,KN, K in each task family; we avoid empirical claims about the separate scaling with D,H,LD, H, L.

with confidence intervals and a matched-budget baseline,

We now provide uncertainty quantification in Figures (7, 10, 13, 15, 17, 18, 27, 29, 31, 33, 35, 37, 39, 41, 43, 44).

Regarding matched-budget baseline, Figures 24 and 25 explicitly fixes the supervised-token budget; Figures 1, 22 and 23 also examine the token-budget allocation.

Numerical estimates of C and a_C(K)? This would test whether the observed tradeoff follows the predicted scaling rather than task-specific coverage heuristics.

As clarified above, numerical estimates are beyond the ambition of the present theory. We have however added informal discussion of CC and aC(K)a_C(K) in Appendix H.3.3.

Response to Justification of Recommendation

The main reservations are the mismatch between theorem and experimental distributions and learning criteria, together with success-conditioned seed selection and confounded complexity sweeps

As detailed above, we have addressed this by: (i) new corollaries, (ii) four control studies, (iii) clarifying the purpose of the experiments in the abstract. We also explain above (under W3 and Q3) why the complexity sweeps are as comprehensive as is feasible given the constraints tasks place on teacher sizes, and are sufficient to support our empirical claims.

Dear Reviewer, thanks again for your constructive input! We hope that, with the new control experiments, theoretical results, and rephrasings in the paper, we have resolved your reservations. As the end of the discussion period approaches, we are happy to answer questions as you consider our responses. Thank you for your consideration and time.

Comments on the paper

2 comments

We thank all three reviewers for the careful reading and constructive feedback.

We have conducted the following main changes addressing the concerns:

  • We provide new proofs (Appendix F.4.1; Corollary F.1) that closely align theory with the setup of our main experiments
  • We have conducted extensive control experiments to align experiments with the setup of the theory, and report results without filtering of seeds. This is now discussed in lines 468--485.
  • We have edited abstract to clarify the purpose of the experiments, and state the specific setup of our theory in the introduction.

We also throughout have made smaller edits for clarity, and added an appendix section discussing of how logit scaling and LayerNorm could be incorporated into the analysis.

Dear Reviewers,

Thank you for your time in evaluating this paper. Since there is only one day left for this stage, could you please read the rebuttal and provide a response? This is important for the review process.

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.