# TokenSelect: Efficient Long-Context Inference and Length Extrapolation for LLMs via Dynamic Token-Level KV Cache Selection

arXiv: https://arxiv.org/abs/2411.02886 · HTML: https://mlsanity.com/paper/2411.02886/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 46 of its 74 references that are in the map.
- First posted on arXiv 5 Nov 2024.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 30 of 46)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [ChatGLM: A Family of Large Language Models from GLM-130B to GLM-4 All Tools](https://mlsanity.com/paper/2406.12793/) (2024)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [Extending Context Window of Large Language Models via Positional Interpolation](https://mlsanity.com/paper/2306.15595/) (2023)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [∞Bench: Extending Long Context Evaluation Beyond 100K Tokens](https://mlsanity.com/paper/2402.13718/) (2024)
- [DeepSpeed Ulysses: System Optimizations for Enabling Training of Extreme Long Sequence Transformer Models](https://mlsanity.com/paper/2309.14509/) (2023)
- [InfiniGen: Efficient Generative Inference of Large Language Models with Dynamic KV Cache Management](https://mlsanity.com/paper/2406.19707/) (2024)
- [Leave No Context Behind: Efficient Infinite Context Transformers with Infini-attention](https://mlsanity.com/paper/2404.07143/) (2024)
- [InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory](https://mlsanity.com/paper/2402.04617/) (2024)
- [GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM](https://mlsanity.com/paper/2403.05527/) (2024)

## Built on by (most cited first, 30 of 39)

- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [On Memory Construction and Retrieval for Personalized Conversational Agents](https://mlsanity.com/paper/2502.05589/) (2025)
- [Token Reduction Should Go Beyond Efficiency in Generative Models -- From Vision, Language to Multimodality](https://mlsanity.com/paper/2505.18227/) (2025)
- [Rethinking Memory in LLM based Agents: Representations, Operations, and Emerging Topics](https://mlsanity.com/paper/2505.00675/) (2025)
- [LEMMA: Learning from Errors for MatheMatical Advancement in LLMs](https://mlsanity.com/paper/2503.17439/) (2025)
- [RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference](https://mlsanity.com/paper/2505.02922/) (2025)
- [TokenButler: Token Importance is Predictable](https://mlsanity.com/paper/2503.07518/) (2025)
- [Beyond Exponential Decay: Rethinking Error Accumulation in Large Language Models](https://mlsanity.com/paper/2505.24187/) (2025)
- [AssoMem: Scalable Memory QA with Multi-Signal Associative Retrieval](https://mlsanity.com/paper/2510.10397/) (2025)
- [Accelerating Large-Scale Reasoning Model Inference with Sparse Self-Speculative Decoding](https://mlsanity.com/paper/2512.01278/) (2025)
- [UniGist: Towards General and Hardware-aligned Sequence-level Long Context Compression](https://mlsanity.com/paper/2509.15763/) (2025)
- [ProxyAttn: Guided Sparse Attention via Representative Heads](https://mlsanity.com/paper/2509.24745/) (2025)
- [ContextPilot: Fast Long-Context Inference via Context Reuse](https://mlsanity.com/paper/2511.03475/) (2025)
- [Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving](https://mlsanity.com/paper/2503.00392/) (2025)
- [Vegas: Self-Speculative Decoding with Verification-Guided Sparse Attention](https://mlsanity.com/paper/2602.07223/) (2026)
- [SparseServe: Unlocking Parallelism for Dynamic Sparse Attention in Long-Context LLM Serving](https://mlsanity.com/paper/2509.24626/) (2025)
- [The Model Knows, the Decoder Finds: Future Value Guided Particle Power Sampling](https://mlsanity.com/paper/2605.02427/) (2026)
- [KVSwap: Disk-aware KV Cache Offloading for Long-Context On-device Inference](https://mlsanity.com/paper/2511.11907/) (2025)
- [Knowing When to Stop: Efficient Context Processing via Latent Sufficiency Signals](https://mlsanity.com/paper/2502.01025/) (2025)
- [Retrospective Sparse Attention for Efficient Long-Context Generation](https://mlsanity.com/paper/2508.09001/) (2025)
- [Unifying Sparse Attention with Hierarchical Memory for Scalable Long-Context LLM Serving](https://mlsanity.com/paper/2604.26837/) (2026)
- [Towards Efficient Large Language Model Serving: A Survey on System-Aware KV Cache Optimization](https://mlsanity.com/paper/2607.08057/) (2026)
- [Can Language Models Actually Retrieve In-Context? Drowning in Documents at Million Token Scale](https://mlsanity.com/paper/2607.01538/) (2026)
- [UT-ACA: Uncertainty-Triggered Adaptive Context Allocation for Long-Context Inference](https://mlsanity.com/paper/2603.18446/) (2026)
- [LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding](https://mlsanity.com/paper/2607.24555/) (2026)
- [CoSA: Accelerating Long-Context Inference via Proxy-Kernel Co-Designed Sparse Attention](https://mlsanity.com/paper/2607.25291/) (2026)
- [Recall Before You Rank: Similarity-Guided Top-K Reuse for Efficient Long-Context Attention](https://mlsanity.com/paper/2607.27692/) (2026)
- [PatternKV: Flattening KV Representation Expands Quantization Headroom](https://mlsanity.com/paper/2510.05176/) (2025)
- [CTkvr: KV Cache Retrieval for Long-Context LLMs via Centroid then Token Indexing](https://mlsanity.com/paper/2512.15550/) (2025)
- [Attention-Mass Condensation for Sparse Decoding](https://mlsanity.com/paper/2602.06317/) (2026)

## Abstract (arXiv)

Rapid advances in Large Language Models (LLMs) have spurred demand for processing extended context sequences in contemporary applications. However, this progress faces two challenges: performance degradation due to sequence lengths out-of-distribution, and excessively long inference times caused by the quadratic computational complexity of attention. These issues limit LLMs in long-context scenarios. In this paper, we propose Dynamic Token-Level KV Cache Selection (TokenSelect), a training-free method for efficient and accurate long-context inference. TokenSelect builds upon the observation of non-contiguous attention sparsity, using QK dot products to measure per-head KV Cache criticality at token-level. By per-head soft voting mechanism, TokenSelect selectively involves a few critical KV cache tokens in attention calculation without sacrificing accuracy. To further accelerate TokenSelect, we design the Selection Cache based on observations of consecutive Query similarity and implemented the efficient Paged Dot Product Kernel, significantly reducing the selection overhead. A comprehensive evaluation of TokenSelect demonstrates up to 23.84× speedup in attention computation and up to 2.28× acceleration in end-to-end latency, while providing superior performance compared to state-of-the-art long-context inference methods.