Research map / Architectures and efficiency / Attention and transformers

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

NeurIPS 2026 · Architectures and efficiency › Attention and transformers · approach: State space and recurrent sequence models · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Reverse-engineers how a linear Mamba solves multi-query associative recall as implicit JL-based linear hashing, and derives recall scaling laws relating embedding size D, state size N, vocabulary V and facts N_f, validated empirically.

Problem

Understanding the internal algorithm Mamba uses for associative recall (AR/MQAR) and how recall capacity scales with vocabulary size, number of facts, state size, and embedding size.

Approach

Shows Mamba implements recall via JL-style linear hash functions (key/query compressed by a JL matrix into the state, values stored as outer products), and uses this to derive probabilistic scaling laws, extended to multi-layer and multi-head Mamba-2 models.

Key results

• Recall accuracy across D-N grids collapses onto a single curve of the form Phi(x - sqrt(2 log V)) with x = sqrt(ND/(aN_f+N)), with a≈1 for AR and a≈5/4 for MQAR.
• Multi-layer experiments show accuracy depends only on effective state size Lambda*N, matching the multi-layer scaling law.
• Among Mamba-2 head patterns, only MHA improves recall over the single-head baseline; MQA and MKA are weaker, consistent with the Mamba-2 perplexity ablations.

Surprising findings

• Padding tokens sampled randomly from the full vocabulary are used following the original MQAR implementation, which adds noise to the recall task.
• Among Mamba-2 head patterns, MVA matches the single-head baseline rather than improving on it.

Limitations

• Analysis relies on simplified linear or simplified Mamba models; the role of the gating branch is not characterized.
• Full nonlinear model scaling constant a_full was determined heuristically.
• Theory analyzes single-query and MQAR settings under idealized JL assumptions with large-V asymptotics.

Experimental setup

Datasets: MQAR synthetic data

Benchmarks: MQAR AR

Metrics: recall accuracy best-of-seeds accuracy

Builds on: Mamba Mamba-2 MQAR Johnson-Lindenstrauss lemma

Closest papers by meaning

• Scaling Laws for Associative Memories (ICLR 2024 · similarity 0.89)
• Factual recall in linear associative memories: sharp asymptotics and mechanistic insights (NeurIPS 2026 · similarity 0.89)
• Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacity (ICML 2025 · similarity 0.88)
• Simple linear attention language models balance the recall-throughput tradeoff (ICML 2024 · similarity 0.88)
• Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory (NeurIPS 2026 · similarity 0.87)
• Frozen Memory Is Not Enough: Rethinking External Memory as Extraction (NeurIPS 2026 · similarity 0.86)