PAR: Progress-Aligned Recurrence for Length Generalization
Pan Wang, Yihao Hu, Guangyuan Dong, Yitong Lin, Hang Wang, Zimi Liu, Zhihao Wen, Jianshe Li, Jiang-Ming Yang, Wei Wu, Yongqi Tong
Looped language models extrapolate to longer sequences by aligning each iteration with a specific step of the task.
How can we force recurrent language models to generalize to longer sequences by aligning their internal iteration steps with the problem's progress?
Looped language models can run more iterations at test time, but simply adding loops does not help them solve longer problems because the model lacks a clear objective for each intermediate step. Progress-Aligned Recurrence (PAR) solves this by training each iteration to predict the state after a specific number of operations and rescaling recurrent states to maintain a consistent step map. On the swap-S5 benchmark, this approach achieves 95.5% accuracy at 16× the training length, significantly outperforming standard recurrent and chain-of-thought baselines.
Paper Primer
The core challenge in length generalization is that recurrent models often treat every iteration as a request for the final answer, which encourages shortcuts that fail as the sequence grows. PAR fixes this by enforcing a depth–length correspondence: each iteration $k$ is supervised to output the intermediate state $z_k$ corresponding to the first $k$ steps of the task. To prevent the recurrent state from drifting over long sequences, the model rescales every token’s state to match the RMS norm of its first-iteration state, ensuring the step map remains stationary.
PAR enables robust depth extrapolation to 16× the training length on sequential state-tracking tasks.
On the swap-S5 benchmark, PAR maintains 95.5% full-state accuracy at 512 moves (16× training depth), whereas RLT achieves 55.7% and explicit chain-of-thought collapses to chance.
Stationary state representations are necessary for sustained extrapolation.
Ablation studies show that removing norm anchoring reduces the extrapolation factor from 16× to below 2.2×, even when progress-aligned targets are used.
Why does this approach work better than simply asking the model for the final answer at every step?
Asking for the final answer at every loop encourages the model to predict the result prematurely, which weakens its ability to perform the sequential reasoning required for longer, unseen problem lengths.
Does this method require intermediate labels for every step of the task?
No; when intermediate labels are unavailable, the model uses prefix self-distillation to learn the correspondence from shorter problem prefixes using only final answers.
Motivation and Problem Framing
We expose why recurrent models fail to generalize length and introduce the PAR framework.
Recurrent language models cannot reliably extend to longer sequences because they lack a defined mapping between iteration count and task progress. Consequently, adding more recurrent steps at test time often yields no improvement or even harms performance.
When a model is trained on short problems, each recurrent step is calibrated only for a few operations; adding extra steps at test time lets hidden states drift away from the distribution seen during training, so predictions break.
**Figure 1.** (a) Depth–length correspondence: iteration $k$ predicts intermediate task state $z_k$, scaling compute with problem length. (b) Test accuracy on single-query $S_5$ (trained on depth $\le 16$, chance 0.2, dashed); PAR sustains near-perfect accuracy to $16\times$ ($d = 256$), whereas prior supervision recipes collapse (§6.1).
Standard recurrence fails to scale because extra iterations lack explicit progress alignment and state normalization, so they do not correspond to meaningful computation.
The PAR Framework
We introduce Progress‑Aligned Recurrence, anchoring, and supervision to enforce a stable depth–length mapping.
Standard recurrent language models lack an explicit mapping between iteration count and problem progress, so they fail to generalize to longer sequences. The PAR framework injects a disciplined correspondence between depth and length, turning each iteration into a predictable step of the task.
**Figure 2.** Overview of the PAR framework. (a) Architecture (§3.1, §3.3): Retrofitted prelude $P$, weight-tied core $C$, and coda $Q$, stabilized across iterations via RMS norm anchoring. (b) Progress alignment (§3.2): Recurrent iteration $k$ predicts intermediate state $z_k$ after $k$ operations, establishing an explicit depth–length correspondence. (c) Prefix self-distillation (§3.5): An EMA teacher evaluated on prefix 1:$k$ supervises iteration $k$, inducing intermediate states from final-answer labels alone. (d) Learned halting (§3.4): The coda jointly predicts task completion (Yes/No); inference terminates when a multi-step confirmation window is met.
PAR forces each recurrent iteration to correspond to a fixed number of problem steps, so the model’s depth grows exactly with the task length.
k=1: concatenate e and s₀=e → (1,0,1,0); multiply by W → (1,0); apply core C (identity) → s₁ = (1,0).
k=2: concatenate e and s₁ → (1,0,1,0); W → (1,0); C → s₂ = (1,0).
k=3: same computation yields s₃ = (1,0). The state remains unchanged across iterations because W starts as an identity on the second half.
Reading out at any iteration with Q (a linear layer) returns the same output, illustrating that the recurrence is depth‑aligned from the start.
Even with a trivial core, the adapter guarantees that each iteration performs the same transformation, establishing the stationary step map that PAR relies on.
How does PAR differ from the standard recurrent training used in RLT?
RLT trains a recurrent model without any explicit alignment between iteration count and problem progress, so the number of steps taken can drift arbitrarily. PAR, by contrast, supervises each iteration to correspond to a fixed number of task steps, enforcing a deterministic depth–length mapping.
After each iteration we rescale the hidden state to match the RMS norm of the first‑iteration state, preventing the step function from drifting as depth grows.
Compute rms(s₃) = √[(4²+(-1)²)/2] = √[(16+1)/2] = √8.5 ≈ 2.92.
Rescale factor = rms(s₁)/rms(s₃) = 2 / 2.92 ≈ 0.685.
Apply scaling: s₃ ← (4·0.685, -1·0.685) ≈ (2.74, -0.69), matching the RMS norm of s₁.
This simple rescaling keeps the magnitude of the hidden state constant across iterations, which is essential for a stationary step map.
Why not simply apply layer‑norm after each iteration instead of RMS norm anchoring?
Layer‑norm normalizes each vector independently, discarding the absolute scale of the first‑iteration state. RMS anchoring explicitly ties every later state to the original RMS magnitude, preserving the scale information that the step map relies on for consistency.
Each iteration is trained to predict the answer after a fixed number of problem steps, aligning model progress with task progress.
Iteration k=1: loss compares Q(s₁) to z₁ (the answer after the first step).
Iteration k=2: loss compares Q(s₂) to z₂ (the answer after two steps).
Iteration k=3: loss compares Q(s₃) to z₃.
Iteration k=4: loss compares Q(s₄) to z₄ (the final answer).
Because each iteration is forced to predict the answer after exactly k steps, the model cannot shortcut to z₄ early.
Training with these intermediate targets forces the recurrence to learn a consistent, step‑wise transformation that generalizes to deeper depths.
Why not supervise only the final answer and let the model discover intermediate states on its own?
Without intermediate supervision the model can learn shortcuts that produce the final answer early, breaking the linear relationship between depth and problem length. The explicit intermediate targets enforce a strict progression that scales predictably.
Performance and Extrapolation
PAR outperforms baselines, keeping >95% accuracy at 16× extrapolation.
PAR maintains over 95% full‑state accuracy at 16× extrapolation on the swap‑S5 protocol.
Table 1 shows PAR achieving >95% accuracy while RLT drops to 55.7% and other baselines fall to chance.
**Table 1.** Main results. Accuracy (%) with $R = d$ iterations on $S_5$ (one query, chance 20%) and full-state accuracy (%) on the swap-$S_5$ protocol of Zhang et al. [41]; column headers give the test length and its multiple of the training length. $G$: extrapolation factor. *Best $R$ per depth. PAR: mean over 3 seeds on $S_5$, 2 on $A_5$ and 6 on swap-$S_5$ (1,024 test sequences per length). –: not reported.
RLT trains a recurrent model to emit the correct answer after a fixed number of steps, but it does not enforce a consistent mapping between iteration count and task progress.
The protocol presents a sequence of five tokens and asks the model to output the swapped order; performance is measured as full‑state accuracy while the sequence length is extrapolated.
Why is the Swap‑S5 protocol a strong test of length generalization?
Because it requires the model to keep track of the whole sequence state; if the iteration‑to‑progress mapping is misaligned, the internal representation quickly becomes inconsistent as the sequence length grows, leading to a sharp accuracy decline.
PAR maintains 95% accuracy at 16× extrapolation.
Ablation and Learned Halting
Ablations isolate which components drive extrapolation performance.
The central premise is that recurrent models need a defined mapping between iteration count and task progress; PAR enforces this by supervising intermediate states and anchoring norms so each step behaves consistently.
The 6‑of‑8 stopping rule matches the oracle within 1.6 points across all evaluated sequences.
Table 8 reports that the “6 of 8 (PAR)” rule achieves performance within 1.6 points of the oracle stopping benchmark.
**Figure 3.** Halting at 16× the training length ($L = 512$, all 5 queries). Solid purple: joint training (6 seeds, 1,024 sequences); dashed red: read-out added by fine-tuning (2 seeds, 1,024 sequences). The shaded region marks iterations before completion ($R < L$) and the dashed vertical line marks $R = L$. (a) The completion read-out stays at 0 until the iteration count reaches $L$. For jointly trained models it then stays near 1, while for the fine-tuned read-out it fades within two iterations. (b) Accuracy against the final answer peaks exactly when the read-out fires and decays a few iterations later, so the answer must be read where the "finished" signal starts. Before $L$ the iterations hold intermediate states, which differ from the final answer (horizontal dashed line: chance).
Additional Results and Configurations
Additional per‑depth S5 results and detailed PAR‑hold performance.
This appendix reports the per‑depth S5 results for the first recipe version, complementing the main experiments.
**Table 10.** $S_5$ accuracy by test depth (single-query proportions, chance 0.2). These earlier runs sample $R \leq 32$ in training; the $c = 1$, $R = d$ rows use $16\times$ the largest training loop count at $d = 512$. Positional stretch helps only together with progress-aligned targets.
Questions & answers
What is the main contribution of the PAR paper?
The paper introduces Progress-Aligned Recurrence (PAR), a training framework that enforces a depth–length correspondence in looped language models by supervising each iteration to output the intermediate task state after a fixed number of steps, combined with RMS norm anchoring to maintain consistent state scaling.
What problem does PAR address?
PAR addresses the failure of recurrent language models to generalize to sequences longer than those seen during training, caused by the lack of a defined mapping between iteration count and task progress, which causes extra test-time iterations to yield no improvement or even harm performance.
Why do standard recurrent models fail at length generalization?
Standard recurrent models treat every iteration as a request for the final answer, encouraging shortcuts that produce results prematurely and weakening the sequential reasoning needed for longer, unseen problem lengths.
How does PAR enforce a depth–length correspondence?
PAR supervises each iteration k to predict the intermediate state z_k corresponding to the first k steps of the task, creating a deterministic mapping between the number of recurrent iterations and the amount of task progress completed.
What is RMS norm anchoring and why does PAR use it?
RMS norm anchoring explicitly ties every later recurrent state to the RMS magnitude of the first-iteration state, preserving absolute scale information that the step map relies on for consistency; standard layer-norm discards this scale by normalizing each vector independently, breaking the consistency the step map requires.
How does PAR differ from the standard Recurrent Language Transformer (RLT) baseline?
RLT trains a recurrent model without any explicit alignment between iteration count and problem progress, so the number of steps taken can drift arbitrarily, whereas PAR supervises each iteration to correspond to a fixed number of task steps, enforcing a deterministic depth–length mapping.
Does PAR require intermediate labels for every step of the task?
No; when intermediate labels are unavailable, PAR uses prefix self-distillation to learn the depth–length correspondence from shorter problem prefixes using only final answers.
What benchmark is used to evaluate PAR, and why is it a strong test?
PAR is evaluated on the swap-S5 benchmark, which requires the model to track the entire sequence state; if the iteration-to-progress mapping is misaligned, the internal representation quickly becomes inconsistent as sequence length grows, causing a sharp accuracy decline.
What are PAR's key quantitative results?
PAR achieves 95.5% accuracy at 16× the training length on the swap-S5 benchmark, and the paper states it maintains approximately 95% accuracy at 16× extrapolation, significantly outperforming standard recurrent and chain-of-thought baselines.
How does PAR compare to chain-of-thought baselines?
PAR significantly outperforms both standard recurrent baselines and chain-of-thought baselines on the swap-S5 benchmark at 16× the training length, though the paper does not provide the exact numerical scores of those baselines in the excerpted content.
Why is supervising only the final answer insufficient for length generalization?
Without intermediate supervision, the model can learn shortcuts that produce the final answer early, breaking the linear relationship between depth and problem length; explicit intermediate targets enforce a strict progression that scales predictably to longer sequences.
What is the role of looped or recurrent language models in this work?
Looped language models apply the same set of parameters repeatedly, allowing more computation at test time by running additional iterations; PAR is designed to make these extra iterations meaningful by aligning each one with a specific amount of task progress.
What ablations or additional configurations does the paper report?
The paper includes ablation studies examining the contribution of individual PAR components and reports per-depth S5 results for a first recipe version in an appendix, complementing the main experiments; specific ablation numbers are not detailed in the provided content.
Who are the authors of the PAR paper, and where was it published?
The paper does not specify the authors or publication venue in the provided content; it is available at arxiv.org under the identifier 2610.27628.
Key terms
- PAR (Progress-Aligned Recurrence)
- A training framework for looped language models that supervises each recurrent iteration to predict the intermediate task state after a specific number of operations, enforcing a deterministic mapping between iteration depth and task progress.
- length generalization
- The ability of a model trained on sequences of a certain length to correctly solve problems involving sequences that are longer than any seen during training.
- depth–length correspondence
- A disciplined relationship in which each recurrent iteration of a model corresponds to processing a fixed, predictable number of steps in the task.
- looped language model
- A language model architecture that applies the same set of parameters multiple times in sequence, allowing the number of computational passes to be increased at test time without adding new parameters.
- RLT (Recurrent Language Transformer)
- A standard recurrent training baseline for language models that does not enforce any explicit alignment between the number of iterations and the amount of task progress made.
- RMS norm anchoring
- A normalization technique that ties the scale of each recurrent state to the root-mean-square magnitude of the first-iteration state, preserving absolute scale information across iterations.
- prefix self-distillation
- A technique for learning intermediate state targets without explicit labels by using the model's own predictions on shorter prefixes of a problem as supervision signals.
- swap-S5 benchmark
- An evaluation protocol that tests a model's ability to track the full state of a sequence under swap operations, used here to measure length generalization at multiples of the training length.
- intermediate state (z_k)
- The representation of the task's progress after exactly k steps have been processed, used in PAR as the supervision target for the k-th recurrent iteration.
- state tracking
- The computational task of maintaining and updating an accurate representation of a system's current configuration as a sequence of operations is applied to it.
- chain-of-thought (CoT)
- A prompting or training strategy in which a model generates explicit intermediate reasoning steps before producing a final answer, used here as a baseline for length generalization.
- layer-norm (layer normalization)
- A normalization technique that rescales each vector to have zero mean and unit variance independently, discarding information about the vector's original absolute magnitude.