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

• URL: http://arxiv.org/abs/2609.07681v1
• Date: Mon, 07 Sep 2026 16:05:24 GMT
• Title: On the Recall Scaling Laws in Mamba: A Theoretical and Mechanistic Study via Hashing
• Abstract summary: Associative Recall (AR) is the cognitive ability to learn and retrieve links between items in memory.<n>In NLP, AR is used as a benchmark for evaluating the in-context memory capacity of architectures such as Mamba.<n>This paper explores AR from the perspective of mechanistic interpretability, aiming to reverse-engineer the exact internal algorithm used by Mamba to perform recall.
• Score: 71.41613782662272
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Understanding LoRA as Knowledge Memory: An Empirical Analysis [20.53732426953178]
  This work investigates a parametric approach using Low-Rank Adaptation (LoRA) as a modular knowledge memory.<n>We bridge this gap through the first systematic empirical study mapping the design space of LoRA-based memory.<n>Our findings position LoRA as the complementary axis of memory alongside RAG and ICL, offering distinct advantages.
  arXiv  Detail & Related papers  (2026-03-01T13:28:57Z)
• Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learning [53.983686308399676]
  Mamba is a proposed linear-time sequence model with strong empirical performance.<n>We study in-context learning of a single-index model $y approx g_*(langle boldsymbolbeta, boldsymbolx rangle)$.<n>We prove that Mamba, pretrained by gradient-based methods, can achieve efficient ICL via test-time feature learning.
  arXiv  Detail & Related papers  (2025-10-14T00:21:20Z)
• Learning Compact Representations of LLM Abilities via Item Response Theory [35.74367665390977]
  We explore how to learn compact representations of large language models (LLMs)<n>We frame this problem as estimating the probability that a given model will correctly answer a specific query.<n>To learn these parameters jointly, we introduce a Mixture-of-Experts (MoE) network that couples model- and query-level embeddings.
  arXiv  Detail & Related papers  (2025-10-01T12:55:34Z)
• Mechanistic evaluation of Transformers and state space models [45.59983103386498]
  State space models (SSMs) for language modelling promise an efficient and performant alternative to quadratic-attention Transformers.<n>We find that only Transformers and Based SSM models fully succeed at Associative Recall (AR)<n>We find that all architectures learn the same mechanism as they did for AR, and the same three models succeed at the task.
  arXiv  Detail & Related papers  (2025-05-21T04:56:09Z)
• Quantifying Memory Utilization with Effective State-Size [73.52115209375343]
  We develop a measure of textitmemory utilization'<n>This metric is tailored to the fundamental class of systems with textitinput-invariant and textitinput-varying linear operators
  arXiv  Detail & Related papers  (2025-04-28T08:12:30Z)
• Exploring Training and Inference Scaling Laws in Generative Retrieval [50.82554729023865]
  Generative retrieval reformulates retrieval as an autoregressive generation task, where large language models generate target documents directly from a query.<n>We systematically investigate training and inference scaling laws in generative retrieval, exploring how model size, training data scale, and inference-time compute jointly influence performance.
  arXiv  Detail & Related papers  (2025-03-24T17:59:03Z)
• From Markov to Laplace: How Mamba In-Context Learns Markov Chains [36.22373318908893]
  We study in-context learning on Markov chains and uncover a surprising phenomenon.<n>Unlike transformers, even a single-layer Mamba efficiently learns the in-context Laplacian smoothing estimator.<n>These theoretical insights align strongly with empirical results and represent the first formal connection between Mamba and optimal statistical estimators.
  arXiv  Detail & Related papers  (2025-02-14T14:13:55Z)
• MambaLRP: Explaining Selective State Space Sequence Models [18.133138020777295]
  Recent sequence modeling approaches using selective state space sequence models, referred to as Mamba models, have seen a surge of interest.<n>These models allow efficient processing of long sequences in linear time and are rapidly being adopted in a wide range of applications such as language modeling.<n>To foster their reliable use in real-world scenarios, it is crucial to augment their transparency.
  arXiv  Detail & Related papers  (2024-06-11T12:15:47Z)
• On the Relationship Between Variational Inference and Auto-Associative Memory [68.8204255655161]
  We study how different neural network approaches to variational inference can be applied in this framework. We evaluate the obtained algorithms on the CIFAR10 and CLEVR image datasets and compare them with other associative memory models.
  arXiv  Detail & Related papers  (2022-10-14T14:18:47Z)
• Learning from Context or Names? An Empirical Study on Neural Relation Extraction [112.06614505580501]
  We study the effect of two main information sources in text: textual context and entity mentions (names) We propose an entity-masked contrastive pre-training framework for relation extraction (RE) Our framework can improve the effectiveness and robustness of neural models in different RE scenarios.
  arXiv  Detail & Related papers  (2020-10-05T11:21:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.