Learn from the Past: Fast Sparse Indexing for Large Language Model Decoding

Feiyu Yao, Qian WangarXiv 2025 · DOI · arXiv

As Large Language Models (LLMs) scale to context windows of 128k tokens and beyond, they encounter a significant physical constraint. While the initial "prefill" stage is computationally intensive, the subsequent "decoding" stage—where the model generates text token by token—is primarily limited by memory access and data movement.

The primary bottleneck is the Key-Value (KV) cache. For a model like Llama-3-8B, a 128k-token context requires approximately 16GB of VRAM just for the cache, often exceeding the capacity of consumer-grade GPUs. While offloading this cache to CPU memory is a common strategy, it introduces a new bottleneck: the limited bandwidth of the PCIe bus and CPU throughput.

A new approach, LFPS (Learn From the Past for Sparse Indexing), addresses these costs by predicting which historical tokens are most relevant for generating the next token, significantly reducing the computational overhead of sparse attention.

The Indexing Bottleneck in Long Contexts

In the decoding phase, sparse attention mechanisms attempt to save time by only attending to a small subset (Top-k) of the KV cache. However, identifying these Top-k keys traditionally requires calculating the dot product between the current query and every single key in the cache.

As context grows, this "indexing" step becomes an $O(n)$ bottleneck. If the cache is offloaded to the CPU, the CPU must perform millions of dot products for every generated token. Existing methods often treat each decoding step as an independent retrieval task, failing to exploit the temporal correlations inherent in LLM attention patterns.

Figure 1: Time breakdown of sparse indexing compared to full attention across varying sequence lengths.

The LFPS Method: Predictive Retrieval

LFPS shifts the paradigm from independent retrieval to predictive retrieval by leveraging historical attention data. Its core components include:

  1. Historical Pattern Tracking: The authors identified two dominant patterns in attention maps:
  2. Vertical Patterns: Consistent attention to fixed positions, such as the sequence start or specific "anchor" tokens.
  3. Slash Patterns: Attention to tokens at a fixed relative distance, representing local context or sliding windows.
  4. Score Tables: LFPS maintains "Score Tables" for these patterns, updated with a decay factor. Instead of scanning the entire cache, it uses these tables to select a small set of initial candidates.
  5. Position Expansion: Since important tokens often cluster, LFPS expands the candidate set to include immediate neighbors of previously important tokens, increasing retrieval coverage.
  6. Sparsity Bypass: LFPS identifies "lazy" attention heads that focus almost exclusively on the "sink token" (the first token). For these heads, it skips complex indexing and uses a simple mean value of the cache.
Figure 4: Visualization of attention sparsity showing the vertical and slash patterns exploited by LFPS.

Experimental Results

The researchers evaluated LFPS using the Llama-3.1-8B-Instruct model on long-context benchmarks including LongBench and RULER.

  • Performance Gains: On hardware consisting of an NVIDIA RTX 4090 and a Xeon Gold CPU, LFPS achieved a 22.8× speedup over full attention and was 9.6× faster than exact Top-k retrieval.
  • Throughput: In multi-core scenarios (batch size 8), LFPS reached 45 tokens/second, a 50% improvement over the Quest baseline.
  • Accuracy: On LongBench, LFPS achieved an average score of 54.66, nearly matching the full-attention model's 55.57 and outperforming other sparse methods like StreamingLLM.
  • Efficiency: At 128k context length, LFPS maintains performance while only performing dot products for approximately 1.7% of the KV cache.

Conclusion

LFPS demonstrates that attention in LLMs is highly predictable. By treating indexing as a recommendation task based on history rather than a raw search, LFPS bypasses the PCIe bandwidth and CPU compute bottlenecks. This synergy between CPU and GPU allows for efficient long-context decoding on accessible hardware without sacrificing generation quality. Future work may involve dynamic budget adjustment per layer and optimization for diverse architectures like Mixture-of-Experts (MoE).

Summary updated

BibTeX
@misc{yao2025learn,
  author = {Feiyu Yao and Qian Wang},
  title = {{Learn from the Past: Fast Sparse Indexing for Large Language Model Decoding}},
  year = {2025},
  eprint = {2506.15704},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.15704},
}
Figure