Work on Stacks: Transformers Can Do Pushdown Updates but Struggle to Learn Them

Transformers are remarkably capable sequence models, but reliably maintaining and updating state over long contexts remains challenging. In this paper, we show that while Transformers can represent exact pushdown state-update computations, learning and executing these computations reliably can be substantially more difficult. We study bounded pushdown updates with complete action–state histories retained in context, without any external symbolic memory or retrieval, and construct a Transformer that implements the update exactly. Empirically, we find that learning succeeds reliably when the required routing computation is provided, but becomes much less reliable when the model must acquire that computation itself. A separate end-to-end study finds increasing training requirements with stack depth and alphabet size, extending the acquisition difficulty beyond unary stacks. Finally, we evaluate pretrained language models and find that pushdown state updates become unreliable in long contexts even when the relevant state can still be recovered. Overall, these experiments show a fundamental gap between representing state and reliably using it for sequential computation.