Recurrent Looped Transformer

Recurrent Looped Transformer. By Yifan Zhang and two others, from Princeton University and the University of Pennsylvania. Published on the sixth of October. Its code repository is a placeholder: a readme, and nothing to run yet.

Tracking state means updating it at every input. Keep a running parity of a bit string, follow a sequence of swaps, carry a sum: each new token changes what came before. A Transformer, though, applies a fixed depth to every token, whatever the length of the sequence. The amount of computation available to any one position does not grow as the sequence does, and that mismatch is the problem this work starts from.

The Recurrent Looped Transformer, or RLT, splits its layers into two groups. Some form a parallel causal encoder. The rest form a recurrent decoder. At each token, the decoder merges the encoder's output with the final decoder state from the previous token. The consequence is that the computation path grows with sequence length, while the cost per token stays fixed.

The experiments are deliberately controlled. Across six algorithmic tasks, the authors compare five different ways of splitting eight layers between encoder and decoder against an ordinary eight-layer Transformer, each run over three seeds. Training uses short sequences and testing goes well beyond them, so the question is whether a model has learned the update rule or only the lengths it was shown.

Parity is the starkest case. Trained on at most forty bits, two of the RLT splits generalize parity to two hundred and fifty-six bits with one hundred percent accuracy in every seed. The Transformer stays at chance. On swap-based S five permutation tracking, at eight times the training length, RLT reaches ninety-seven percent final-state accuracy against under one percent for the Transformer, and accuracy rises as the decoder gets deeper.

On modular arithmetic beyond the training lengths, RLT reaches up to ninety-three percent, where the Transformer reaches thirty-three. Ablations point to the source of these gains: the feedback from one token's decoder state to the next. Remove it, and parity and swap-based permutation tracking both drop to chance at every split.

The authors also test a cheaper variant that updates the feedback only once per four-token chunk, which lets the known tokens inside a chunk run in parallel. Parity tolerates this well: sixty-four-bit parity stays at ninety-nine percent. Permutation tracking does not. It depends on per-token feedback, and chunking lowers length sixty-four swap-based tracking from one hundred percent to twenty.

The results line up with the opening diagnosis. Where a task needs an update at every input, a model whose path deepens with the sequence succeeds and a fixed-depth one does not, and taking the recurrence away undoes the gain. The chunking result marks the trade-off precisely: some tasks let the recurrence be coarsened for parallelism, and others need it at every step.