- 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 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, -consistency and position coupling, arguing that their successful reasoning representations satisfy the proposed Markov/time-consistency conditions.
Critical strengths
-
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.
-
The framework provides a useful lens on existing successful methods. The paper analyzed -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
- Theorem 3.2 seems false. The paper defines the time-dependent hypothesis class as maps , and then claims that implies that no such can achieve .
Consider the two-state space , with . Let , where , and then let (and afterwards). Writing for the marginal law, the probability of state 1 is at , at , and again at . For two initial parameters ,
\|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
-
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.
-
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.
-
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.