PoFormer: Recurrent Pointer Addressing for Length Generalization

Length generalization requires a model trained on short sequences to apply the same algorithm to longer inputs, enabling compact, reusable computational subcircuits rather than length-specific behaviors. Looped Transformers provide recurrent computation but do not explicitly retain previously attended locations, making precise traversal difficult when repeated symbols render content matching ambiguous or when the next address depends on the current state or retrieved content. We introduce PoFormer, a recurrent Transformer whose recurrent state is factorized into a controller state that carries intermediate computation and a pointer state that tracks the active memory location. Selected attention heads act as pointer heads that maintain and update active addresses over the input, enabling local address shifts and global content-conditioned jumps while preserving content-based retrieval. We formalize this mechanism with P_RASP, a recurrent pointer extension of RASP, and constructively show that PoFormer can simulate P_RASP programs over finite execution horizons. Across controlled algorithmic tasks, PoFormer substantially improves OOD length generalization over standard and looped Transformer baselines. Its interpretable pointer trajectories reveal stable traversal strategies and expose address-level failures such as pointer drift and positional aliasing. Together, these results establish explicit recurrent address state as an effective inductive bias for length generalization in tasks requiring precise, stateful addressing.