acceptodds
Under review as a conference paper at ICLR 2027

Exact-Solution Volume and Length Generalization in Transformers

Abstract

Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through *normalized exact-solution volume (NESV)*: the fraction of a bounded parameter region that achieves an exact solution on every input of length . For fixed-width, single-layer transformers with -scaled attention, we establish asymptotic bounds on NESV for four tasks: FIRST (), MAJORITY (), INDEX (), and PARITY (). These results are consistent with previous empirical results: the faster the NESV decays with input length, the harder it is to length-generalize on that task. Looking deeper into INDEX, our volume analysis reveals two error sources that grow with . Consequently, we study a transformer model that would structurally eliminate one of the terms, theoretically improving the NESV bound to , and empirically achieving 85% accuracy when tested at 10 times the training length, compared with the 60% accuracy of the original model. We conclude that volume analysis may be a useful approach to identify concrete sources of length sensitivity and thus provide insights into task-specific model refinements.

Primary area:
learning theory
Keywords:
transformer, learning theory, length generalization, parameter-space geometry

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_9GYpOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces a new metric/notion to predict when length generalization happens in single layer Transformers without residual connections and without layer normalization. This new metric called NESV is a function of input length nn and measures the fraction of parameters (where the parameter values are bounded) that achieve an exact solution on every input of length nn. They derive asymptotic bounds for various formal languages - FIRST, MAJORITY, INDEX and PARITY, and find that empirically the exact volume metric as a function of nn is predictive of how well Transformers length generalize. Further, on one of the tasks where Transformers do struggle, i.e. INDEX (return symbol at a position specified by one of the input tokens), they find two things which cause a worse NESV, and consider a slightly altered Transformer that is designed to eliminate one of the sources causing the error, and this said Transformer (by design improves NESV) empirically length generalizes better.

Critical strengths
  • NESV is an interesting way to think about length generalization: This new notion introduced by the authors, while in some indirect ways can be inferred from past papers, especially Kövér et al 2026[1] and Hahn & Rofin 2024 [2]. is still quite valid, and it is worth working this out formally. The fact that, this line of work that can side step the complexity of gradient descent and still be able to say something useful about models, is quite nice.

  • NESV helping in designing dedicated improvements in the architecture as seen in the INDEX task is quite promising as well.

  • The proofs look correct to me.

  • The experiments across 20 seeds on each of these tasks and multiple positional encodings, shows that there is some correlation between length generalization and this metric.

[1] Kövér et al ICML 2026: Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

[2] Hahn & Rofin ACL 2024: Why are sensitive functions hard for Transformers?

Critical weaknesses

Some bigger problems --

  • This notion of exact volume solution and length generalization are correlating for now, but there are no formal links that are established between these completely different notions. This correlation exists, but without any formal link, this correlation may not always hold. In fact, the authors themselves find a counterexample in the case of MAJORITY, where the NESV is not as predictive across the model types considered in the paper.

  • This piggybacks on the last point, the authors also have currently ignored what afaik is the most successful formal framework for studying length generalization: which are all RASP based [1, 2]. The wealth of tasks on which these RASP based variants are predictive seems much higher than this NESV. I understand that this NESV could potentially could help in getting more fine grained perspectives, instead of just the binary answers that one usually gets from [1,2], however for now, a stronger formal link, or more experiments on a wider variety of tasks would be required to convincingly establish the utility of this method. Without that, this paper feels like a good first step, but one that is not enough.

  • The results are also only for very toy models -- single layer, no residuals, no layer norm, very specific kind of positional embeddings which are not naturally used. While these assumptions are understandable, as this paper is the first one to introduce this notion. The no residuals and no layer norm could easily be missed by someone skimming the paper, this detail only appears when the authors mathematically write out the equations. Such critical assumptions should be more clearly highlighted in the abstract and introduction. Also, somewhere providing some discussion / remarks on these assumptions also feel missing to me.

Some minor problems --

  • The 'Kover et al' 2026 citation should be spelled more carefully (Kövér). There are non-English characters in the name.

  • The current paper is ignoring a lot of work that has been done in understanding length generalization in Transformers, the RASP line of work was an example, which itself has some critical papers. The related works section should more adequately address papers in this area.

[UPDATE] During the rebuttal period, the authors productively engaged, made important clarifications and incorporated what I think is some useful hedging in many places, making the technical claims more well scoped and accurate. Despite the hedging, I think that the idea deserves merit, and would be valuable to the community. I have therefore increased my score to reflect this.

[1] Zhou et al ICLR 2024: What Algorithms can Transformers Learn? A Study in Length Generalization

[2] Huang et al ICLR 2025: A Formal Framework for Understanding Length Generalization in Transformers

Questions for authors
  • The current Figure 2 is also very unintuitive to me, could you explain what you wanted to show with that Figure here ?

  • How would things like Chain of Thought, looping, padding etc. fit in with NESV ?

  • The results across seeds was not clear to me. What does seed bootstrap 95% mean in Table 2? And for such results, the seed variance maybe should be reported more clearly in the main paper.

5 comments

Thank you very much for your thoughtful review! We apologize for misspelling Blanka Kövér's name. We will correct it in the final version.

You asked for a more extensive discussion of previous work on length generalization, especially related to RASP. Our discussion and related-work section were shortened because of the page limit at submission. We would be happy to extend this section to discuss the broader literature on length generalization.

We agree with you that NESV provides fine-grained answers instead of the binary answers one gets by hypothesizing that expressivity in a RASP variant is equivalent to length generalization in a transformer. The two papers cited [1,2] argue for equivalence with two different RASP variants, and one might also add the work of [Li and Cotterell 2025], which argues that expressivity in LTL[P] is equivalent to length generalization in a fixed-precision transformer. One way to reconcile these results is to say that weaker logics/RASPs define languages that are "more" length-generalizable, but there isn't yet a unifying framework. While we would welcome such a framework, we propose that NESV gives a simple way to talk about how some languages are more learnable than others.

We also agree that at present, the connection between NESV and learnability is intuitive and only empirically supported. We acknowledge that developing a formal, mathematical account of when and how solution volume relates to learnability is an important direction for future work.

Regarding the omission of LayerNorm and residual connections: If we follow the placement of layer normalization in the original transformers paper (that is, post-norm), adding LayerNorm alone would not affect our bounds. Adding LayerNorm together with a residual connection would introduce an additional n−1n^{-1} factor for both the unnormalized and normalized models, changing the bounds to Θ(n−4)\Theta(n^{-4}) and Θ(n−2)\Theta(n^{-2}), respectively. This is because the residual path carries the query index kk directly into the downstream representation, creating an additional length-dependent constraint that must hold uniformly for all k≤nk \leq n. We would be happy to add this discussion to the final version of the paper if desired.

Answers to the questions:

  1. The current Figure 2 is also very unintuitive to me, could you explain what you wanted to show with that Figure here ?

The intention of Figure 2 is to show the difference in length-generalization performance between the normalized and unnormalized models on INDEX. We would be happy to clarify the figure and its caption further if any aspect remains confusing.

  1. How would things like Chain of Thought, looping, padding etc. fit in with NESV ?

The notion of NESV should extend to these settings as long as there is a defined parameter space and a criterion for final-answer correctness. We don't make any claims, however, about how difficult it would be to derive NESV bounds in these settings. In particular, a prerequisite for studying looping would be NESV bounds for multi-layer transformers, which is our priority for future work.

  1. The results across seeds was not clear to me. What does seed bootstrap 95% mean in Table 2? And for such results, the seed variance maybe should be reported more clearly in the main paper.

For Table 2, we resample the 20 seed-level accuracies with replacement, compute the mean accuracy for each sample, and report the 2.5th and 97.5th percentiles as the pointwise 95% confidence interval for the mean accuracy across seeds. If the reviewer would prefer an additional measure of between-seed variability, we would be happy to add it to the appendix.

Thank you for your response. Could you actually make the changes you are promising here and update the PDF? It would be much more helpful for me to see those changes actually reflected in the PDF. ICLR allows an extra page for the rebuttal, so hopefully that's plenty space to add most things.

Also, it seems that the authors missed responding in full to weakness 3 that I listed.

Such critical assumptions should be more clearly highlighted in the abstract and introduction. Also, somewhere providing some discussion / remarks on these assumptions also feel missing to me.

Essentially I have no issues with the assumptions, I would just think that the title of the paper, abstract and introduction was not very clear in managing expectations about what's to come. The fact that the results for extremely toy models is alright, but I definitely think that the authors need to be upfront about it in the paper.

For instance, the following detail needs to be mentioned way earlier -- We do not use residual connections or layer normalization.

We also agree that at present, the connection between NESV and learnability is intuitive and only empirically supported. We acknowledge that developing a formal, mathematical account of when and how solution volume relates to learnability is an important direction for future work.

Great, no problem with that. Again please be more upfront about it in the introduction/ abstract. Essentially I am happy with your response, the major thing I would like to see is that the 'advertisement' of the results of the paper should be correct and not misleading. When I was personally going through the paper, I felt a bit deceived when finding out the actual results, vs what the introduction setup. This is not an issue as this is easily fixable and therefore I would really want to see this reflected in the PDF, so that we hopefully can have another back and forth during the rebuttal period itself.

If updating all the things is too difficult in this short period, then kindly at least give the abstract + intro another pass, I would be happy to have another round of back and forth after (at least) some updates in the PDF. Also kindly mark the new things in blue / any color so that it's easy to quickly check what changed.

Thank you again.

Thank you for the clarification. We have now updated the PDF to make the scope and assumptions of our study clearer from the outset. In particular, we have made the architectural assumptions more explicit in the abstract and introduction, and clarified the current empirical nature of the connection between NESV and learnability. We have also corrected the typos. The changes are marked in blue.

We have not yet expanded the related work discussion on RASP and the broader length-generalization literature, but plan to include this in subsequent revisions. We hope these changes address your main concerns, and would be happy to hear your thoughts on the updated PDF.

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

The paper studies why transformers that can, in principle, express a task often fail to generalize to longer inputs. Instead of asking whether a solving parameter configuration exists (expressivity), it asks how large the set of exactly-solving parameters is and how fast this set shrinks with input length n. The analysis covers fixed-width, single-layer transformers with log n-scaled attention on four binary-string tasks (FIRST, MAJORITY, INDEX, PARITY).

The key contributions are:

  1. Normalized exact-solution volume (NESV) framework. NESV is the fraction of a bounded parameter box [-B, B]^D whose parameters solve the task exactly on every input of length n, i.e., the probability that uniformly sampled weights give a perfect solution. Its dependence on n is proposed as a measure of how hard a task is to length-generalize.
  2. Asymptotic NESV bounds with empirical validation. Matching upper and lower bounds are derived, with sinusoidal-encoding variants in the appendix. Training experiments show that tasks whose volume shrinks faster generalize worse to longer inputs (Table 1).
  3. Volume analysis as a diagnostic, shown on INDEX. The INDEX proof identifies two parameter combinations whose errors are amplified by k^2 and k, respectively. These must lie in intervals of width O(n^-2) and O(n^-1), which gives the n^-3 volume. Their magnitudes in trained models correlate with out-of-distribution accuracy. Guided by this, the authors propose a parameter-free "normalized" positional model that bounds the k-dependent query component in the quadratic channel. This removes the k^2 term, improves the NESV to Theta(1/n), and raises accuracy at 10x the training length from ~60% to ~85% (Section 4.3).
Critical strengths
  1. Important, well-motivated question. Prior work mostly studies expressivity (whether a solution exists). This paper asks how large the set of exact solutions is and how it shrinks with input length, which brings it a step closer to learnability and length generalization.
  2. Simple, intuitive measure of solution volume. NESV is just the probability that uniformly sampled weights in [-B, B] solve the task exactly at length n. It is easy to state and to compare across tasks and architectures.
  3. Clear writing and elegant setup. The minimal one-layer model keeps the analysis tractable, and the proof sketches give real intuition (e.g., the k^2 / k drift terms for INDEX).
  4. Volume analysis identifies the problem and leads to a concrete fix. The INDEX analysis pinpoints the parameter combinations responsible for the volume decay, and those combinations correlate with OOD accuracy in trained models. The resulting parameter-free normalized model improves the bound from Theta(n^-3) to Theta(n^-1) (Theorem 2) and raises accuracy at 10x the training length from ~60% to ~85%. This shows that volume analysis can serve as a diagnostic tool, not just a hardness measure.
  5. Careful, reproducible experiments. The protocol is fully specified: 20 seeds with 95% bootstrap intervals, checkpoint selection that never uses lengths beyond the training length, shared test banks, and paired seeds for model comparisons.
Critical weaknesses
  1. Simplified architectural assumptions. All results are for a fixed-width, single-layer, single-head transformer with log n-scaled attention and a heavily constrained positional model. Practical language and video models are deep and multi-head, and most do not use log n scaling. It is unclear whether the bounds or the INDEX fix carry over (as acknowledged in Sec. 6).
  2. No residual connections or normalization layers. The model omits residual connections and LayerNorm, which are standard in practice. The authors note that these "could alter the size and geometry of the exact-solution set" (Sec. 2.2) but do not study them. How would the bounds, and the benefit of the normalized model, change if these components were included?
  3. Limited improvement from the normalized variant on FIRST and MAJORITY (Table 1). Performance on these tasks does not change, so the improvement appears limited to the INDEX task.
Questions for authors

The authors note these "could alter the size and geometry of the exact-solution set" (Sec. 2.2) but do not study them. How would the bounds, and the benefit of the normalized model, change once they are included?

1 comment

Thank you for your careful review.

The authors note [residual connections or layer normalization] "could alter the size and geometry of the exact-solution set" (Sec. 2.2) but do not study them. How would the bounds, and the benefit of the normalized model, change once they are included?

If we follow the placement of layer normalization in the original transformers paper (that is, post-norm), adding LayerNorm alone would not affect our bounds. Adding LayerNorm together with a residual connection would introduce an additional n−1n^{-1} factor for both the unnormalized and normalized models, changing the bounds to Θ(n−4)\Theta(n^{-4}) and Θ(n−2)\Theta(n^{-2}), respectively. This is because the residual path carries the query index kk directly into the downstream representation, creating an additional length-dependent constraint that must hold uniformly for all k≤nk \leq n. We would be happy to add this discussion to the final version of the paper if desired.

This study is a first step toward developing NESV as a diagnostic framework, and the targeted improvement for INDEX is intended to serve as an example of how the framework could inspire model design. The current study focuses on limited models for the sake of clarity and analytical simplicity. Extending the framework to deeper and multi-head models would be an important next step.

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

The authors study the learnability of length-generalizing transformers. Specifically, they examine the relationship between the volume of the set of parameters for the transformer which would length generalize and the likelihood that a length generalizing solution is learned using standard optimization techniques. They consider four tasks (First, Index, Majority, and Parity) and derive bounds on the volume of the length-generalizing parameter sets for each vs. the input length nn. They show empirically that the asymptotic bounds on the volume of these sets correlates with the learnability of a length-generalizing solution. Finally, based on insights gained from the proofs of one of the volume bounds, they propose a modification to the transformer architecture which results in a larger-volume solution set and translates into better length generalization empirically.

Critical strengths

This is an interesting extension of the "volume of valid solutions" approach of Kover et al. to length generalization. The proof sketches for the main theoretical result supply helpful intuition, and in general the paper is clear and easy to follow. The experiments stress-test the theory and show good if not perfect agreement with the theoretical predictions. Finally, the authors are able to use their theoretical insights to propose a practically effective change to the one-layer transformer architecture.

Critical weaknesses

The main weakness is that the setting studied is rather limited, including only single-layer transformers and sometimes with bespoke architectural modifications which makes the connection to practice more tenuous. In addition, the theoretical contribution establishes bounds on the volume of the solution sets, but the direct connection to learnability of a length-generalizing solution is verified only empirically. Given that single layer models are considered, it would be desirable to have results establishing the volume/learnability connection theoretically.

Typo: uju_j in equation (2) should be vjv_j

Questions for authors

N/A

2 comments

Thank you for your review, and thank you for pointing out the typo in equation (2). We will correct it.

We agree that the current setting is limited to single-layer transformers and, in the case of INDEX, includes a task-specific architectural modification. As noted in Section 6, extending the analysis to deeper and more standard architectures is a natural and critical next step.

We also agree that at present, the connection between NESV and learnability is intuitive and only empirically supported. We acknowledge that developing a formal, mathematical account of when and how solution volume relates to learnability is an important direction for future work.

Thanks to the authors for the acknowledgement of the limitations. It seems that the other reviewers also had a positive impression of the paper and had their questions answered, so I will maintain my score and recommend acceptance.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.