Lune

EMNLP Findings2023

Transformer Working Memory Enables Regular Language Reasoning And Natural Language Length Extrapolation

Ta-Chung Chi, Ting-Han Fan, Alexander Rudnicky, Peter J. Ramadge

Abstract

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 Regu-larGPT. 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability cites Resurrecting Recurrent Neural Networks for Long Sequences
  • Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Exploring Length Generalization in Large Language Models cites Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation
  • Exploring Length Generalization in Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Generalizing Reasoning Problems to Longer Lengths cites Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation
  • Generalizing Reasoning Problems to Longer Lengths cites Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability
  • Generalizing Reasoning Problems to Longer Lengths cites Exploring Length Generalization in Large Language Models
  • Generalizing Reasoning Problems to Longer Lengths cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths AggregationXinyi Wang, Alfonso Amayuelas, Kexun Zhang, Liangming Pan et al.ICML 2024 · 27 citations
  2. Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with ScalabilityJishnu Ray Chowdhury, Cornelia CarageaNeurIPS 2023 · 7 citations
  3. CARMA: Enhanced Compositionality in LLMs via Advanced Regularisation and Mutual Information AlignmentNura Aljaafari, Danilo S. Carvalho, André FreitasEMNLP 2025
  4. Generalizing Reasoning Problems to Longer LengthsChangnan Xiao, Bing LiuICLR 2025

Builds on14

  1. Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
  2. ALBERT: A Lite BERT for Self-supervised Learning of Language RepresentationsZhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel et al.ICLR 2020 · 7,418 citations
  3. Train Short, Test Long: Attention with Linear Biases Enables Input Length ExtrapolationOfir Press, Noah A. Smith, Mike LewisICLR 2022 · 1,168 citations
  4. Resurrecting Recurrent Neural Networks for Long SequencesAntonio Orvieto, Samuel L. Smith, Albert Gu, Anushan Fernando et al.ICML 2023 · 474 citations
  5. Exploring Length Generalization in Large Language ModelsCem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz et al.NeurIPS 2022 · 267 citations

Related papers

  1. DAPE V2: Process Attention Score as Feature Map for Length ExtrapolationChuanyang Zheng, Yihang Gao, Han Shi, Jing Xiong et al.ACL 2025 · 12 citations
  2. Recurrent Memory TransformerAydar Bulatov, Yuri Kuratov, Mikhail BurtsevNeurIPS 2022 · 252 citations
  3. On the Ability and Limitations of Transformers to Recognize Formal LanguagesSatwik Bhattamishra, Kabir Ahuja, Navin GoyalEMNLP 2020 · 7 citations
  4. A Little Depth Goes a Long Way: The Expressive Power of Log-Depth TransformersWilliam Merrill, Ashish SabharwalNeurIPS 2025 · 62 citations
  5. Characterizing the Expressivity of Local Attention in TransformersJiaoda Li, Ryan CotterellACL 2026 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines