Learn from the Past: Fast Sparse Indexing for Large Language Model Decoding
Not on the map. Why?
Abstract (arXiv)
As large language models (LLMs) continue to support increasingly longer contexts, the memory demand for key-value (KV) caches during decoding grows rapidly, becoming a critical bottleneck in both GPU memory capacity and PCIe bandwidth. Sparse attention mechanisms alleviate this issue by computing attention weights only for selected key-value pairs. However, their indexing computation typically requires traversing all key vectors, resulting in significant computational and data transfer overhead. To reduce the cost of index retrieval, existing methods often treat each decoding step as an independent process, failing to exploit the temporal correlations embedded in historical decoding information. To this end, we propose LFPS(Learn From the Past for Sparse Indexing), an acceleration method that dynamically constructs sparse indexing candidates based on historical attention patterns. LFPS captures two prevalent trends in decoder attention -vertical patterns (attending to fixed positions) and slash patterns (attending to relative positions) -and incorporates a positional expansion strategy to effectively predict the Top-k indices for the current step. We validate LFPS on challenging long-context benchmarks such as LongBench-RULER, using Llama-3.1-8B-Instruct as the base model. Experimental results show that LFPS achieves up to 22.8× speedup over full attention and 9.6× speedup over exact Top-k retrieval on an RTX 4090 GPU and a single CPU core of a Xeon Gold 6430, respectively, while preserving generation accuracy. These results demonstrate that LFPS offers a practical and efficient solution for decoding optimization in long-context LLM inference.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 28 of its 33 references that are in the map. First posted on arXiv 30 May 2025.
Builds on
28 of 33 references.
References · 28
- 2023GPT-4 Technical Reportcited by 18,396
- 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
- 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
- 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
- 2023Code Llama: Open Foundation Models for Codecited by 2,139
- 2023LongBench: A Bilingual, Multitask Benchmark for Long Context Understandingcited by 1,417
- 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,346
- 2024SnapKV: LLM Knows What You are Looking for Before Generationcited by 880
- 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 832
- 2023FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPUcited by 575
- 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 501
- 2021A Dataset of Information-Seeking Questions and Answers Anchored in Research Paperscited by 486
16 more
- 2024MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attentioncited by 383
- 2024DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Headscited by 288
- 2024InfiniGen: Efficient Generative Inference of Large Language Models with Dynamic KV Cache Managementcited by 245
- 2025MoBA: Mixture of Block Attention for Long-Context LLMscited by 198
- 2025Qwen2.5-1M Technical Reportcited by 164
- 2024ShadowKV: KV Cache in Shadows for High-Throughput Long-Context LLM Inferencecited by 134
- 2023SparQ Attention: Bandwidth-Efficient LLM Inferencecited by 119
- 2024RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrievalcited by 116
- 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 111
- 2024Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Taskscited by 96
- 2024PQCache: Product Quantization-based KVCache for Long Context LLM Inferencecited by 95
- 2024ClusterKV: Manipulating LLM KV Cache in Semantic Space for Recallable Compressioncited by 65
- 2024Human-inspired Episodic Memory for Infinite Context LLMscited by 62
- 2024FastDecode: High-Throughput GPU-Efficient LLM Serving using Heterogeneous Pipelinescited by 49
- 2024NEO: Saving GPU Memory Crisis with CPU Offloading for Online LLM Inferencecited by 37
- 2024Compute Or Load KV Cache? Why Not Both?cited by 25
Built on by
Citing papers per year: 2026: 1.
1 paper.