Push, Pop, Parallelize: Stack-Augmented Linear Attention via the Delta Rule

Linear attention architectures based on the Delta rule, such as DeltaNet and RWKV-7, combine Transformer-level performance with RNN-like efficiency and provably solve regular language tasks. However, their fixed-size states struggle to capture the recursive, hierarchical structures intrinsic to natural languages. To bridge this gap, we introduce DeltaStack, which augments DeltaNet's associative memory with a lightweight, differentiable stack. Unlike prior approaches that rely on sequential recurrence, DeltaStack formulates stack operations as linear delta-rule updates, enabling a hardware-aware implementation fully parallelizable over sequence length. Theoretically, we prove DeltaStack extends DeltaNet's expressivity to model both regular and hierarchical languages. Empirically, DeltaStack outperforms DeltaNet and Stack-Attention on formal language benchmarks and consistently surpasses DeltaNet baselines in language modeling perplexity and zero-shot performance across scales up to 760M parameters. Our code is publicly available at https://github.com/teeann/DeltaStack.