# Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer arXiv: https://arxiv.org/abs/2409.09239 ยท HTML: https://mlsanity.com/paper/2409.09239/ ## Key facts - Cited by 16 papers in the map (data through 14 Oct 2026). - Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. - Builds on 18 of its 39 references that are in the map. - First posted on arXiv 14 Sep 2024. ## Placed in - LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/) ## Builds on (most cited first, 18 of 18) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023) - [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020) - [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023) - [SciBERT: A Pretrained Language Model for Scientific Text](https://mlsanity.com/paper/1903.10676/) (2019) - [BloombergGPT: A Large Language Model for Finance](https://mlsanity.com/paper/2303.17564/) (2023) - [Quantifying Attention Flow in Transformers](https://mlsanity.com/paper/2005.00928/) (2020) - [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018) - [Large Language Models Fail on Trivial Alterations to Theory-of-Mind Tasks](https://mlsanity.com/paper/2302.08399/) (2023) - [Physics of Language Models: Part 3.1, Knowledge Storage and Extraction](https://mlsanity.com/paper/2309.14316/) (2023) - [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024) - [Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Future](https://mlsanity.com/paper/2309.15402/) (2023) - [Don't Trust ChatGPT when Your Question is not in English: A Study of Multilingual Abilities and Types of LLMs](https://mlsanity.com/paper/2305.16339/) (2023) - [ProLLaMA: A Protein Large Language Model for Multi-Task Protein Language Processing](https://mlsanity.com/paper/2402.16445/) (2024) - [Addressing Some Limitations of Transformers with Feedback Memory](https://mlsanity.com/paper/2002.09402/) (2020) - [An Analysis of the Expressiveness of Deep Neural Network Architectures Based on Their Lipschitz Constants](https://mlsanity.com/paper/1912.11511/) (2019) - [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024) - [Lower Bounds for Multiplication via Network Coding](https://mlsanity.com/paper/1902.10935/) (2019) ## Built on by (most cited first, 16 of 16) - [OctoNav: Towards Generalist Embodied Navigation](https://mlsanity.com/paper/2506.09839/) (2025) - [Latent Thinking Optimization: Your Latent Reasoning Language Model Secretly Encodes Reward Signals in Its Latent Thoughts](https://mlsanity.com/paper/2509.26314/) (2025) - [Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Tracking](https://mlsanity.com/paper/2502.20129/) (2025) - [SpiralFormer: Looped Transformers Can Learn Hierarchical Dependencies via Multi-Resolution Recursion](https://mlsanity.com/paper/2602.11698/) (2026) - [PosterGen: Aesthetic-Aware Multi-Modal Paper-to-Poster Generation via Multi-Agent LLMs](https://mlsanity.com/paper/2508.17188/) (2025) - [Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits](https://mlsanity.com/paper/2505.14178/) (2025) - [MeSH: Memory-as-State-Highways for Recursive Transformers](https://mlsanity.com/paper/2510.07739/) (2025) - [Supervised Chain of Thought](https://mlsanity.com/paper/2410.14198/) (2024) - [Retrieval is Not Enough: Enhancing RAG Reasoning through Test-Time Critique and Optimization](https://mlsanity.com/paper/2504.14858/) (2025) - [Universal Biological Sequence Reranking for Improved De Novo Peptide Sequencing](https://mlsanity.com/paper/2505.17552/) (2025) - [Prompt-Based One-Shot Exact Length-Controlled Generation with LLMs](https://mlsanity.com/paper/2508.13805/) (2025) - [Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling](https://mlsanity.com/paper/2508.16745/) (2025) - [Limited Reasoning Space: The cage of long-horizon reasoning in LLMs](https://mlsanity.com/paper/2602.19281/) (2026) - [Recurrence-Complete Frame-based Action Models](https://mlsanity.com/paper/2510.06828/) (2025) - [Is my model "mind blurting"? Interpreting the dynamics of reasoning tokens with Recurrence Quantification Analysis (RQA)](https://mlsanity.com/paper/2602.06266/) (2026) - [Reflection Pretraining Enables Token-Level Self-Correction in Biological Sequence Models](https://mlsanity.com/paper/2512.20954/) (2025) ## Abstract (arXiv) The Transformer architecture excels in a variety of language modeling tasks, outperforming traditional neural architectures such as RNN and LSTM. This is partially due to its elimination of recurrent connections, which allows for parallel training and a smoother flow of gradients. However, this move away from recurrent structures places the Transformer model at the lower end of Chomsky's computational hierarchy, imposing limitations on its computational abilities. Consequently, even advanced Transformer-based models face considerable difficulties in tasks like counting, string reversal, and multiplication. These tasks, though seemingly elementary, require a level of computational complexity that exceeds the capabilities of the Transformer architecture. Concurrently, the emergence of ``Chain of Thought" (CoT) prompting has enabled Transformer-based language models to tackle tasks that were previously impossible or poorly executed. In this work, we thoroughly investigate the influence of recurrent structures in neural models on their reasoning abilities and computability, contrasting the role autoregression plays in the neural models' computational power. We then shed light on how the CoT approach can mimic recurrent computation and act as a bridge between autoregression and recurrence in the context of language models. It is this approximated recurrence that notably improves the model's performance and computational capacity. Moreover, we revisit recent recurrent-based Transformer model designs, focusing on their computational abilities through our proposed concept of ``recurrence-completeness" and identify key theoretical limitations in models like Linear Transformer and RWKV. Through this, we aim to provide insight into the neural model architectures and prompt better model design.