Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention

Zhihao Zhan, Jianan Zhao, Zhaocheng Zhu, Jian Tang

TL;DR

State-Space Models (SSMs) like Mamba offer an efficient, sub-quadratic alternative to Transformers but struggle with complex, context-dependent data retrieval. This paper introduces a novel synthetic benchmark called "joint recall" to expose this limitation and proposes HAX, a hybrid architecture that augments SSMs with context-dependent sparse attention and a learnable key-selection mechanism. HAX significantly boosts long-context performance and training stability while maintaining sub-quadratic computational efficiency.

What Problem Does This Paper Address?

While Transformers dominate natural language processing, their self-attention mechanism suffers from a quadratic computational bottleneck ($O(l^2)$) as sequence lengths grow. State-Space Models (SSMs) have emerged as a promising alternative due to their linear or sub-quadratic scaling. However, empirical evidence shows that SSMs lag behind Transformers in capturing long-range dependencies and copying information.

Previously, researchers relied on a synthetic task called associative recall (AR) to measure a model's retrieval capabilities. AR requires a model to remember simple, static key-value pairs (e.g., if "snow" maps to "white", recall "white" when prompted with "snow"). The authors argue that AR is too simplistic and fails to reflect real-world language, where meaning is highly sensitive to context.

To address this, they introduce joint recall, where a key's associated value changes depending on the surrounding context (e.g., the answer to "Which side of the road do people drive on?" changes based on whether the context is the U.S. or the U.K.). Mathematically, they prove that standard SSMs lack the expressiveness to solve this multi-query joint recall task efficiently.

Comparison of joint recall and associative recall.

Methods

To overcome the expressiveness bottleneck of SSMs, the authors propose integrating them with Context-Dependent Sparse Attention (CDSA). Unlike fixed, context-independent sparse attention (like sliding windows), CDSA dynamically routes information based on the content of the sequence.

The authors instantiate this via a novel architecture called HAX (Locality-sensitive Hashing Attention with sparse Key Selection), which combines two complementary attention mechanisms:

  1. Locality-Sensitive Hashing (LSH) Attention: A form of CDSA that uses randomized hashing to bucket semantically similar queries and keys together, enabling flexible, content-based routing.
  2. Key Selection (KS) Attention: LSH attention typically struggles to capture "vertical-stripe" attention patterns—instances where a few globally important tokens (like instructions or formatting markers) must be attended to by almost every query. KS attention solves this by using a lightweight multilayer perceptron (MLP) to score and select the top-$k$ most important keys to broadcast globally.

The final HAX sparse attention pattern is the element-wise maximum of the LSH and KS patterns ($\mathbf{S}_{\text{HAX}} = \max\{\mathbf{S}_{\text{LSH}}, \mathbf{S}_{\text{KS}}\}$), which runs in parallel with state-of-the-art SSM layers (Mamba and Mamba2).

Illustration of the HAX architecture integrated with Mamba.

Datasets

The authors evaluated their approach across both synthetic and real-world long-context benchmarks:

  • Multi-Query Joint Recall: A newly introduced synthetic dataset consisting of 1.4 million training examples designed to test context-dependent key-value retrieval.
  • The Pile & TxT-360: Large-scale text corpora used for the continual pre-training of 130M and 790M parameter Mamba models.
  • UltraChat: Used for instruction fine-tuning the pre-trained models.
  • Ruler Benchmark: A synthetic long-context NLP benchmark evaluating models on retrieval, aggregation, and multi-hop reasoning at 2K and 4K context lengths.
  • LongBench: A suite of real-world long-context tasks spanning question answering, summarization, and code completion.
  • LM Evaluation Harness: Used to verify that the models maintain strong performance on short-context tasks.

Key Insights and Ideas

  • The Illusion of Associative Recall: Standard associative recall tasks create a false sense of security regarding an architecture's retrieval capabilities. Joint recall exposes a fundamental representation bottleneck in sequential state updates.
  • The Power of Dynamic Routing: The authors establish a strict theoretical expressiveness gap: SSMs combined with context-independent sparse attention (CISA) cannot solve joint recall in sub-quadratic time, whereas SSMs combined with CDSA can.
  • Synergy of LSH and Key Selection: LSH attention can overload specific buckets when many queries try to look at the same key. By introducing the learnable KS mechanism, HAX offloads global token tracking to a dedicated channel, preserving representation diversity in the hashing buckets.

Key Results

  • Synthetic Performance: On the Joint Recall task, adding HAX to Mamba improved accuracy from 16.3% to 38.0%. When paired with Mamba2, accuracy jumped from 36.6% to 74.3%, outperforming all context-independent attention baselines.
  • Training Stability: During continual pre-training on real-world text, Mamba+HAX was the only architecture that demonstrated a consistent, stable decline in validation loss, while other baselines plateaued or exhibited training instability.
Validation loss during continual pre-training on Mamba 130M models.
  • Downstream Benchmarks: On the real-world LongBench and Ruler benchmarks, the Mamba-790M+HAX hybrid model consistently achieved the highest average scores and demonstrated superior context length extrapolation capabilities when tested at 4K context length (despite only being trained on 2K).

Limitations and Future Work

While the paper demonstrates clear empirical benefits, a few limitations and areas for future exploration remain:

  • Hyperparameter Tuning: The Key Selection mechanism introduces a pairwise ranking loss during training, which requires balancing via a scalar hyperparameter ($\alpha$) alongside the standard language modeling loss.
  • Parameter Overhead: Although HAX maintains sub-quadratic computational complexity, adding the parallel attention branches and the MLP scoring network introduces a minor parameter overhead (approximately 1% additional parameters).
  • Hardware Optimization: The authors note that while hardware-efficient implementations like Triton kernels exist for standard LSH, future work is needed to fully optimize the combined HAX attention mechanism for maximum hardware throughput.

Summary updated

Abstract

Efficient long-context modeling remains a critical challenge for natural language processing (NLP), as the time complexity of the predominant Transformer architecture scales quadratically with the sequence length. While state-space models (SSMs) offer alternative sub-quadratic solutions, they struggle to capture long-range dependencies effectively. In this work, we focus on analyzing and improving the long-context modeling capabilities of SSMs. We show that the widely used synthetic task, associative recall, which requires a model to recall a value associated with a single key without context, insufficiently represents the complexities of real-world long-context modeling. To address this limitation, we extend the associative recall to a novel synthetic task, \emph{joint recall}, which requires a model to recall the value associated with a key given in a specified context. Theoretically, we prove that SSMs do not have the expressiveness to solve multi-query joint recall in sub-quadratic time complexity. To resolve this issue, we propose a solution based on integrating SSMs with Context-Dependent Sparse Attention (CDSA), which has the expressiveness to solve multi-query joint recall with sub-quadratic computation. To bridge the gap between theoretical analysis and real-world applications, we propose locality-sensitive Hashing Attention with sparse Key Selection (HAX), which instantiates the theoretical solution and is further tailored to natural language domains. Extensive experiments on both synthetic and real-world long-context benchmarks show that HAX consistently outperforms SSM baselines and SSMs integrated with context-independent sparse attention (CISA).
BibTeX
@inproceedings{zhan2025overcoming,
  author = {Zhihao Zhan and Jianan Zhao and Zhaocheng Zhu and Jian Tang},
  title = {{Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=XsNi2STaj0},
}
Figure