acceptodds
Under review as a conference paper at ICLR 2027

Beyond Training Lengths: Conditions for Generalization

Abstract

A key challenge in learning-to-reason tasks is that models trained on shorter sequences often fail to handle longer instances at test time. This phenomenon, known as length generalization (LG), requires extrapolation beyond the training length, whereas most learning paradigms are designed for interpolation under the i.i.d. assumption. For this reason, LG is also referred to as length extrapolation. Despite substantial empirical progress in recent years, LG remains largely unresolved. While prior theoretical work has examined learning to reason, relatively little attention has been paid to reasoning under LG. In this paper, we study necessary and sufficient conditions for achieving LG in a manner that is independent of specific learning algorithms or model architectures. This perspective is important, as it avoids limiting the analysis to the capabilities and constraints of existing learning algorithms. Finally, we analyze two empirically successful LG approaches based on the proposed necessary and sufficient conditions, providing initial evidence for the relevance of our theoretical framework.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Length Generalization or Extrapolation

Reviews

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

This paper studies length generalization, where a model trained on shorter problem instances is tested on longer instances. The authors model chain-of-thought as a stochastic process and introduce a measure N(S,P)N(S,P) intended to quantify non-Markovianity, based on whether distances between state distributions can increase over successive reasoning steps. The paper develops necessary and functional sufficiency results relating this condition to the existence of a one-step dynamic function. The current reasoning state must contain sufficient information to determine the next state, while a reusable time-independent transition is able to take the current state to the next. Finally, the framework is used to reinterpret two existing approaches to length generalization, (n,r)(n,r)-consistency and position coupling, arguing that their successful reasoning representations satisfy the proposed Markov/time-consistency conditions.

Critical strengths
  1. The paper targets an understudied question in length generalization. Rather than analyzing a particular architecture or encoding, the paper tries to identify structural conditions on reasoning itself that could support length extrapolation. I found the distinction between the existence of a valid transition rule and the separate question of whether a learner can actually discover that rule conceptually useful. Abstractly, the whole framing of the paper I find interesting.

  2. The framework provides a useful lens on existing successful methods. The paper analyzed (n,r)(n,r)-consistency and position coupling and explains both concretely in terms of how they can be explained by their framing. The addition examples help clarify why tags or aligned positional information can improve extrapolation.

Critical weaknesses
  1. Theorem 3.2 seems false. The paper defines the time-dependent hypothesis class as maps f:N×Δ(S)→Δ(S)f:\mathbb N\times\Delta(S)\to\Delta(S), and then claims that N(S,P)>0N(S,P)>0 implies that no such ff can achieve μ(f)=0\mu(f)=0.

Consider the two-state space S={0,1}S=\{0,1\}, with S0∼Bernoulli(x)S_0\sim\mathrm{Bernoulli}(x). Let S1=S0⊕ES_1=S_0\oplus E, where E∼Bernoulli(1/4)E\sim\mathrm{Bernoulli}(1/4), and then let S2=S0S_2=S_0 (and St=S2S_t=S_2 afterwards). Writing ptp_t for the marginal law, the probability of state 1 is xx at t=0t=0, 1/4+x/21/4+x/2 at t=1t=1, and xx again at t=2t=2. For two initial parameters x≠yx\neq y,

\|p_2-q_2\|_1=2|x-y|,$$ so the distance increases and therefore $N(S,P)>0$. However, an exact time-dependent one-step map on distributions exists. At $t=1$, map a Bernoulli parameter $x$ to $1/4+x/2$; at $t=2$, map the current parameter $z\in[1/4,3/4]$ to $2z-1/2$; and thereafter use the identity. Extending these maps arbitrarily outside the reachable set gives an $f:\mathbb N\times\Delta(S)\to\Delta(S)$ that exactly reproduces the dynamics and hence has $\mu(f)=0$. Thus, the implication $N(S,P)>0\Rightarrow\min_f\mu(f)>0$ doesn't hold. Separately, the proof also derives an identity only almost everywhere in $p_0$ and then applies it specifically at Dirac measures $\delta_s$, which is not justified. The Dirac distributions are measure-zero boundary points of the simplex so an almost-everywhere statement is not enough. 2. The formal results characterize existence of one-step dynamics more than actual length generalization, and they currently have limited useful consequences. The theorems do not model training on lengths up to $L$, finite-sample learning, or test error at lengths $>L$. Functional sufficiency does not imply learnability (which the authors acknowledge), and the empirical part just reinterprets two methods already known to work rather than predicting new success/failure cases. Moreover, the condition depends on the chosen state/CoT representation, which can be changed by adding more history to the state. As a result, it is not yet clear to me how much the framework tells us beyond the intuitive requirement that a length-generalizing reasoning representation should contain enough information for the next step with a reusable transition.
Questions for authors
  1. Please fix the issues brought up in weakness 1, or explain to me if I'm misinterpreting something. Given that this is a purely theoretical paper, unless I'm sure of the soundness of the results, I can't give this a better score.

  2. What's the formal connection between the existence results for one-step dynamic functions and the learning problem of length generalization? I would like to understand exactly what claim about length generalization is established by the theory, as opposed to what is an interpretation of the existence of a reusable transition rule.

  3. Does the proposed framework yield a nontrivial, falsifiable prediction that was not already known from the existing length-generalization methods it analyzes? This is probably the most important question to me. I want to understand if your paper is just reframing previous results or if it's doing so in a way that's meaningful to the machine learning community.

Quality answers to all three questions would likely raise my score to a 3.

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

The paper studies length generalization in reasoning through a stochastic-process formulation of CoT. It introduces a quantity, N(S,P), that measures increases in the L1 distance between distributions evolved from different initial distributions. The main claims are: (i) N(S,P) = 0 is presented as necessary for the existence of both time-dependent and time-independent one-step dynamic function, and (ii) N(S,P)=0 is also sufficient for the existence of a time independent one-step dynamic function if the dynamic process (S,P) itself is time-independent. At the same time, the authors point out that this does not imply that the existence of a function satisfying μ(f)=0μ(f)=0 can always be learned. Then they interprets two existing approaches, (n,r)-consistency and position coupling, through this framework using addition and parity.

Critical strengths

The case illustrations in Sections 4.1 and 4.2 are very detailed and clear. They demonstrate that the (3,3)-context is not consistent in the design scenario of addition[1], whereas when the operation position is marked in the CoT state, it becomes an available (3,3)-context. If the authors intend to use this example to show that the state design of CoT needs to include certain necessary information so as to ensure the existence of an observable ff , then this example is highly appropriate.

Critical weaknesses

Since equation (5), this requires an update of the form p→Tpp \to Tp, where TT is a nonnegative, column-stochastic matrix. Nonincrease of pairwise L1L_1 distances does not guarantee that such a matrix exists. Define

2/3 & 1/6 & 1/6; \\ 1/6 & 2/3 & 1/6; \\ 1/6 & 1/6 & 2/3 \end{array}\right)$$ and $$B=\left(\begin{array}{ccc} 0 & 1/2 & 1/2; \\ 1/2 & 0 & 1/2; \\ 1/2 & 1/2 & 0 \end{array}\right)$$ Construct a process by sampling $S_1$ and $S_2$ conditionally independently given $S_0$ using $A$ and $B$, respectively, that is, $p_1=Ap_0$ and $p_2=Bp_0$. It's easy to check $N(S,P)=0$. Nevertheless, an exact state-level update at time 2 would require $TA=B$, whose unique solution is $$T=BA^{-1}=\left(\begin{array}{ccc} -1/3 & 2/3 & 2/3; \\ 2/3 & -1/3 & 2/3; \\ 2/3 & 2/3 & -1/3 \end{array}\right).$$ Therefore, I am uncertain whether this is reasonable with respect to the authors' claim, given that it is a one-step transition function whose probabilities may become negative. 2. **The established contribution is substantially narrower than the claimed characterization of LG.** The main formal objective concerns exact representation of dynamics across initial distributions and time steps. It does not specify training and test lengths, finite-data identifiability, or assumptions ensuring that observations at short lengths determine behavior at longer lengths. Even a correct existence theorem would therefore leave the central extrapolation question unresolved. The proposed condition is also strongly dependent on the state representation. Retaining the full history can make a process Markov, and both addition-[1] and addition-[2] satisfy N(S,P) = 0 despite their different reported LG behavior. Without constraints on state size, access to history, or computational structure, the condition has limited discriminatory power. The concern is that neither the current theory nor the explanatory examples establish sufficient new, reliable knowledge to support the paper's broad claims.
Questions for authors
  1. Does H^N retain the state-level averaging constraint in Equation (5), or, does it allows arbitrary maps between distributions? Under the former interpretation, how is the counterexample (mentioned above) excluded?

  2. Does the core contribution of the authors derive from Theorems 3.2-3.5? If so, I fail to understand how this contributes to Chapters 4 and 5. I don't think there is high relevance between them unless the authors provide further explanation of their connection.

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

This paper studies length generalization through conditions independent of a particular architecture or learning algorithm. It models chain-of-thought reasoning as a stochastic process and defines a quantity NN based on increases in the L1L_1 distance between distributions evolved from different initial distributions. The authors claim that N=0N=0 is necessary for an exact one-step representation and sufficient when the representation may depend on time, while a time-independent representation requires more. They then use this framework to discuss (n,r)(n,r)-consistency and position coupling.

Critical strengths
  1. The paper tries to address an important problem. Providing theoretical analysis on length generalization and looking for conditions beyond a particular architecture could provide useful insight on the mechanism of language models and help designing more efficient algorithm.

  2. Asking whether the current reasoning state keeps the information needed for the next step is a useful starting point. The addition, parity, and position-tagging examples make the connection easier to follow.

Critical weaknesses

My biggest concern is that the two main theorems (Theorem 3.2 and Theorem 3.4) seem to use different interpretations of a one-step dynamic function.

Section 3.2 defines a one-step dynamic function f:S→Δ(S)f:S\to\Delta(S), and Equation (5) defines its induced distribution map by averaging f(s)f(s) over the input distribution. In the finite-state setting, this induced map is affine and represented by a stochastic matrix. Later, however, f(t,p)f(t,p) appears to be treated as a general map between distributions. The distinction matters for both theorems.

Under the interpretation given by Equation (5), there seems to be a two-state counterexample to Theorem 3.4. Let rt(x)r_t(x) be the probability of state 11 at time tt when its initial probability is xx, and take

r_1(x)=\frac{1}{4}+\frac{x}{2},\qquad r_t(x)=\frac{x}{2}\quad\text{for }t\geq 2.$$ This is a valid history-dependent process: flip the initial bit with probability $1/4$ at the first step, multiply the initial bit by an independent fair bit at the second step, and then keep the state fixed. For any two initial probabilities $x,y\in[0,1]$, the corresponding $L_1$ distances are $$2|x-y|,\quad |x-y|,\quad |x-y|,\quad\ldots$$ so $N=0$. According to Theorem 3.4, there should therefore exist an $f$ such that $\mu(f)=0$. If its action on distributions is required to follow Equation (5), let the second-step transition probabilities be $$a=\Pr(\text{output}=1\mid\text{input}=1), \qquad b=\Pr(\text{output}=1\mid\text{input}=0).$$ These probabilities must be fixed across initial distributions. To match the second-step distribution for every $x\in[0,1]$, they would have to satisfy $$a\left(\frac{1}{4}+\frac{x}{2}\right) +b\left(\frac{3}{4}-\frac{x}{2}\right) =\frac{x}{2}.$$ Matching the constant term and the coefficient of $x$ gives $$a+3b=0,\qquad a-b=1,$$ forcing $$a=\frac{3}{4},\qquad b=-\frac{1}{4},$$ which is impossible for a probability. Thus, $N=0$ does not appear sufficient under the interpretation of Equation (5). Conversely, if arbitrary distribution maps are allowed, change the second step to recover the initial state and keep that state fixed afterward. Then $$r_0(x)=x,\qquad r_1(x)=\frac{1}{4}+\frac{x}{2},\qquad r_t(x)=x\quad\text{for }t\geq2.$$ Writing a Bernoulli distribution by its probability $r$ of state $1$, define $$f(1,r)=\frac{1}{4}+\frac{r}{2}.$$ $$f(2,r)=\operatorname{clip}\left(2r-\frac{1}{2},\,0,\,1\right).$$ $$f(t,r)=r,\qquad t\geq3.$$ Here, $\operatorname{clip}(z,0,1)=\min\{1,\max\{0,z\}\}$. At the second step, every reachable input lies in $[1/4,3/4]$, so clipping does not affect the inverse map. This function reproduces every step exactly for every initial probability $x$, giving $\mu(f)=0$. However, the $L_1$ distances now follow $$2|x-y|,\quad |x-y|,\quad 2|x-y|,\quad 2|x-y|,\quad\ldots$$ and therefore $$N_0(x,y)=|x-y|, \qquad N=\max_{x,y\in[0,1]}|x-y|=1>0.$$ This contradicts Theorem 3.2 under the broader interpretation. The two claims therefore cannot both hold with the definitions as written. The paper needs to clarify which function class is intended and revise the corresponding necessity or sufficiency claim.
Questions for authors

See weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.