# Transformer Working Memory Enables Regular Language Reasoning and Natural Language Length Extrapolation

arXiv: https://arxiv.org/abs/2305.03796 · HTML: https://mlsanity.com/paper/2305.03796/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 46 references that are in the map.
- First posted on arXiv 5 May 2023.

## Builds on (most cited first, 26 of 26)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Depth-Adaptive Transformer](https://mlsanity.com/paper/1910.10073/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Parallelizing Linear Recurrent Neural Nets Over Sequence Length](https://mlsanity.com/paper/1709.04057/) (2017)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation](https://mlsanity.com/paper/2205.09921/) (2022)
- [Adaptive Semiparametric Language Models](https://mlsanity.com/paper/2102.02557/) (2021)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Do Transformers Need Deep Long-Range Memory](https://mlsanity.com/paper/2007.03356/) (2020)
- [Characterizing Verbatim Short-Term Memory in Neural Language Models](https://mlsanity.com/paper/2210.13569/) (2022)

## Built on by (most cited first, 13 of 13)

- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Guiding Language Model Reasoning with Planning Tokens](https://mlsanity.com/paper/2310.05707/) (2023)
- [Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation](https://mlsanity.com/paper/2402.03268/) (2024)
- [A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practices](https://mlsanity.com/paper/2406.08787/) (2024)
- [A Theory for Length Generalization in Learning to Reason](https://mlsanity.com/paper/2404.00560/) (2024)
- [A Review of Incorporating Psychological Theories in LLMs](https://mlsanity.com/paper/2505.00003/) (2025)
- [Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability](https://mlsanity.com/paper/2311.04449/) (2023)
- [Investigating Recurrent Transformers with Dynamic Halt](https://mlsanity.com/paper/2402.00976/) (2024)
- [CARMA: Enhanced Compositionality in LLMs via Advanced Regularisation and Mutual Information Alignment](https://mlsanity.com/paper/2502.11066/) (2025)
- [Rethinking Memorization Measures and their Implications in Large Language Models](https://mlsanity.com/paper/2507.14777/) (2025)
- [Fine-tuning vs. In-context Learning in Large Language Models: A Formal Language Learning Perspective](https://mlsanity.com/paper/2604.23267/) (2026)
- [Length Generalization with Log-Depth Recurrent Units](https://mlsanity.com/paper/2605.26035/) (2026)
- [Log-Depth Recurrent Language Modeling](https://mlsanity.com/paper/2609.28212/) (2026)

## Abstract (arXiv)

Unlike recurrent models, conventional wisdom has it that Transformers cannot perfectly model regular languages. Inspired by the notion of working memory, we propose a new Transformer variant named RegularGPT. With its novel combination of Weight-Sharing, Adaptive-Depth, and Sliding-Dilated-Attention, RegularGPT constructs working memory along the depth dimension, thereby enabling efficient and successful modeling of regular languages such as PARITY. We further test RegularGPT on the task of natural language length extrapolation and surprisingly find that it rediscovers the local windowed attention effect deemed necessary in prior work for length extrapolation.