PAR: Progress-Aligned Recurrence for Length Generalization in State Tracking

PAR. Progress-Aligned Recurrence for Length Generalization in State Tracking. By Pan Wang and ten others, from Ant International and the National University of Singapore. Published on the twentieth of October. No code repository is linked to it.

A looped language model can run more iterations at test time than it did in training, which looks like a way to handle longer problems. The extra iterations, though, need not help. For sequential state tracking the authors point to two reasons. Supervision on the final answer alone says nothing about how far any individual iteration ought to advance the computation. And repeated updates can change the scale of the recurrent state, so the loop drifts away from the regime it was trained in.

Progress-Aligned Recurrence answers each reason with one change. The prediction at iteration k is trained to match the state after the first k operations, which gives every iteration a target of its own and fixes how much progress it should make. And recurrent states are rescaled to their first-iteration norms, which holds the scale still as the loop runs.

Two further pieces make the method practical. A learned completion readout decides when to answer, so no stopping depth has to be supplied from outside. And when intermediate labels are not available, prefix self-distillation induces the iteration-to-progress correspondence from shorter problem prefixes, using only final answers.

The headline test is swap on the symmetric group of degree five. A Qwen2.5 model at the zero point five billion parameter size is trained on at most thirty-two moves and reaches ninety-five point five percent mean full-state accuracy at five hundred and twelve moves. That is sixteen times the training length. Reported on the same backbone, RLT reaches fifty-five point seven percent and explicit chain of thought zero point eight percent.

Controlled ablations separate the two ingredients. Removing norm anchoring drops the extrapolation factor from sixteen times to below two point two times. Replacing the progress-aligned targets with final-answer supervision drops it to at most eight times. Both components are doing real work, and the anchoring is doing more of it.

The gains hold across sequential state-tracking tasks, which lets the authors say what task structure depth extrapolation requires. Their reading of the evidence is that intermediate predictions and state scale have to be trained together. Tell each loop how far to get, keep its magnitude steady, and the extra depth finally buys longer problems.