# Implicit Language Models are RNNs: Balancing Parallelization and Expressivity

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 48 of its 64 references that are in the map.
- First posted on arXiv 10 Feb 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 48)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [PIQA: Reasoning about Physical Commonsense in Natural Language](https://mlsanity.com/paper/1911.11641/) (2019)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [The LAMBADA dataset: Word prediction requiring a broad discourse context](https://mlsanity.com/paper/1606.06031/) (2016)
- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Emergent World Representations: Exploring a Sequence Model Trained on a Synthetic Task](https://mlsanity.com/paper/2210.13382/) (2022)
- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [xLSTM: Extended Long Short-Term Memory](https://mlsanity.com/paper/2405.04517/) (2024)
- [Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks](https://mlsanity.com/paper/1502.05698/) (2015)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Implicit Representations of Meaning in Neural Language Models](https://mlsanity.com/paper/2106.00737/) (2021)
- [Scaling Laws and Compute-Optimal Training Beyond Fixed Training Durations](https://mlsanity.com/paper/2405.18392/) (2024)

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

- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [ATLAS: Learning to Optimally Memorize the Context at Test Time](https://mlsanity.com/paper/2505.23735/) (2025)
- [It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimization](https://mlsanity.com/paper/2504.13173/) (2025)
- [MesaNet: Sequence Modeling by Locally Optimal Test-Time Training](https://mlsanity.com/paper/2506.05233/) (2025)
- [Memory Caching: RNNs with Growing Memory](https://mlsanity.com/paper/2602.24281/) (2026)
- [TNT: Improving Chunkwise Training for Test-Time Memorization](https://mlsanity.com/paper/2511.07343/) (2025)
- [SCOUT: Teaching Pre-trained Language Models to Enhance Reasoning via Flow Chain-of-Thought](https://mlsanity.com/paper/2505.24181/) (2025)
- [Predictability Enables Parallelization of Nonlinear State Space Models](https://mlsanity.com/paper/2508.16817/) (2025)
- [Learning State-Tracking from Code Using Linear RNNs](https://mlsanity.com/paper/2602.14814/) (2026)
- [Fixed-Point RNNs: Interpolating from Diagonal to Dense](https://mlsanity.com/paper/2503.10799/) (2025)
- [Debugging code world models](https://mlsanity.com/paper/2602.07672/) (2026)
- [Agentic Discovery of Neural Architectures: AIRA-Compose and AIRA-Design](https://mlsanity.com/paper/2605.15871/) (2026)
- [A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems](https://mlsanity.com/paper/2509.21716/) (2025)
- [Consistency Deep Equilibrium Models](https://mlsanity.com/paper/2602.03024/) (2026)
- [Exploration of Fast-Slow Latent Recurrence for Train-Short, Test-Long Generalization](https://mlsanity.com/paper/2604.01577/) (2026)
- [Energy-guided Recursive Model](https://mlsanity.com/paper/2607.10128/) (2026)
- [Can Video World Models Track Unobserved World States?](https://mlsanity.com/paper/2608.30692/) (2026)
- [Dissecting Linear Recurrent Models: How Different Gating Strategies Drive Selectivity and Generalization](https://mlsanity.com/paper/2601.12598/) (2026)
- [CHASE: Cache-Hole-Adapted Skip Exit for Looped State-Space Language Models](https://mlsanity.com/paper/2607.10110/) (2026)
- [Proteus: Incremental Memory Activation for Long-Context Sequence Modeling](https://mlsanity.com/paper/2608.16844/) (2026)
- [Reshape and Recur: Improving SSMs with Input Reshaping and Depth Recurrence](https://mlsanity.com/paper/2605.16048/) (2026)
- [ADPTNet: Adaptive with Prescriptive Timescales Non-Linear SSM for Sequence Modelling](https://mlsanity.com/paper/2609.34034/) (2026)

## Abstract (arXiv)

State-space models (SSMs) and transformers dominate the language modeling landscape. However, they are constrained to a lower computational complexity than classical recurrent neural networks (RNNs), limiting their expressivity. In contrast, RNNs lack parallelization during training, raising fundamental questions about the trade off between parallelization and expressivity. We propose implicit SSMs, which iterate a transformation until convergence to a fixed point. Theoretically, we show that implicit SSMs implement the non-linear state-transitions of RNNs. Empirically, we find that only approximate fixed-point convergence suffices, enabling the design of a scalable training curriculum that largely retains parallelization, with full convergence required only for a small subset of tokens. Our approach demonstrates superior state-tracking capabilities on regular languages, surpassing transformers and SSMs. We further scale implicit SSMs to natural language reasoning tasks and pretraining of large-scale language models up to 1.3B parameters on 207B tokens representing, to our knowledge, the largest implicit model trained to date. Notably, our implicit models outperform their explicit counterparts on standard benchmarks. Our code is publicly available at http://github.com/microsoft/implicit_languagemodels .