# On the Recall Scaling Laws in Mamba: A Theoretical and Mechanistic Study via Hashing

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Core SSM architectures for language, one of 10 directions in State-space sequence models (S4, Mamba).
- Builds on 25 of its 50 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Placed in

- State-space sequence models (S4, Mamba) / [Core SSM architectures for language](https://mlsanity.com/ssm/core-ssm-architectures-for-language/)

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

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model](https://mlsanity.com/paper/2401.09417/) (2024)
- [VMamba: Visual State Space Model](https://mlsanity.com/paper/2401.10166/) (2024)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models](https://mlsanity.com/paper/2402.19427/) (2024)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [Simple linear attention language models balance the recall-throughput tradeoff](https://mlsanity.com/paper/2402.18668/) (2024)
- [Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2402.00789/) (2024)
- [Test-time regression: a unifying framework for designing sequence models with associative memory](https://mlsanity.com/paper/2501.12352/) (2025)
- [MambaByte: Token-free Selective State Space Model](https://mlsanity.com/paper/2401.13660/) (2024)
- [DeciMamba: Exploring the Length Extrapolation Potential of Mamba](https://mlsanity.com/paper/2406.14528/) (2024)
- [LongMamba: Enhancing Mamba's Long Context Capabilities via Training-Free Receptive Field Enlargement](https://mlsanity.com/paper/2504.16053/) (2025)
- [BlackMamba: Mixture of Experts for State-Space Models](https://mlsanity.com/paper/2402.01771/) (2024)
- [Overclocking LLM Reasoning: Monitoring and Controlling Thinking Path Lengths in LLMs](https://mlsanity.com/paper/2506.07240/) (2025)
- [Mimetic Initialization Helps State Space Models Learn to Recall](https://mlsanity.com/paper/2410.11135/) (2024)
- [Understanding the Skill Gap in Recurrent Language Models: The Role of the Gather-and-Aggregate Mechanism](https://mlsanity.com/paper/2504.18574/) (2025)
- [Mechanistic evaluation of Transformers and state space models](https://mlsanity.com/paper/2505.15105/) (2025)
- [Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacity](https://mlsanity.com/paper/2506.11891/) (2025)
- [Overflow Prevention Enhances Long-Context Recurrent LLMs](https://mlsanity.com/paper/2505.07793/) (2025)
- [Quantifying Memory Utilization with Effective State-Size](https://mlsanity.com/paper/2504.19561/) (2025)
- [On the Expressivity of Selective State-Space Layers: A Multivariate Polynomial Approach](https://mlsanity.com/paper/2502.02209/) (2025)

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

- [On the Importance of Gating: Memorization vs. In-Context Learning in State Space Models](https://mlsanity.com/paper/2609.16540/) (2026)

## Abstract (arXiv)

Associative Recall (AR) is the cognitive ability to learn and retrieve links between items in memory. In NLP, AR is used as a benchmark for evaluating the in-context memory capacity of architectures such as Mamba, and has been found to strongly correlate with language modeling performance. This paper explores AR from the perspective of mechanistic interpretability, aiming to reverse-engineer the exact internal algorithm used by Mamba to perform recall. Our key insight is that Mamba performs recall by implicitly learning linear hash functions, and we identify the low-level circuit that enables this behavior. Building on these findings and inspired by theoretical tools in similarity-preserving hashing, such as the Johnson-Lindenstrauss lemma, we develop a theoretical framework for analyzing AR, which we term Recall Scaling Laws. Given the vocabulary size and the number of facts in context, this framework allows us to (1) predict the embedding and state dimensions required for Mamba to achieve perfect recall, (2) predict recall success probability given the model dimensions, and (3) analyze multi-layer models and multi-head SSM patterns. Empirical results show that our theoretical findings are accurate and predictive, offering insights into how AR capacity scales with vocabulary, state, embedding size, and architecture.