DeltaFugue: Orchestrating Spatial and Associative Memory for Algorithmic Length Generalization

Linear attention models offer a highly efficient alternative to Transformers, leveraging fixed-size memory for robust state-tracking and retrieval. However, relying strictly on fixed-capacity associative states bottlenecks their ability to resolve precise structural dependencies that may grow unboundedly in multi-step algorithmic reasoning - especially within deterministic context-free and context-sensitive formal languages. Inspired by the decoupled computation of Turing Machines, we introduce DeltaFugue: a hardware-aware architecture that orchestrates a continuous linear attention controller alongside a differentiable 1D spatial tape. Unlike traditional memory-augmented RNNs that sacrifice sequence-level parallelism, DeltaFugue executes read and write operations natively via delta-rule updates, preserving the training parallelism of linear transformers. Theoretically, we prove that this decoupled spatial routing allows DeltaFugue to recognize regular, hierarchical, and context-sensitive formal languages. Empirically, extensive length generalization evaluations demonstrate that DeltaFugue achieves state-of-the-art accuracy among fully parallelizable models. Scaling to natural language, a 340M-parameter DeltaFugue model matches the performance of strong DeltaNet baselines while exhibiting markedly superior length extrapolation in reasoning-heavy domains like mathematics and code generation.