FIER : Fine-Grained and Efficient KV Cache Retrieval for Long-context LLM Inference (2025)

Abstract: The Key-Value (KV) cache reading latency increases significantly with context lengths, hindering the efficiency of long-context LLM inference. To address this, previous works propose retaining a small fraction of KV cache based on token importance. For example, KV eviction uses static heuristics to retain tokens, while KV retrieval dynamically selects query-relevant tokens for more adaptive cache management. However, we observe that important tokens are often sparsely distributed across the long context. This sparsity makes existing page-level KV retrieval inaccurate, as each page may include irrelevant tokens and miss critical ones. In this work, we propose Fier, a **Fi**ne-Grained and **E**fficient KV cache **R**etrieval method. Fier uses 1-bit quantized keys to estimate the importance of each token, resulting in efficient and precise retrieval. Experiments show that Fier matches full KV performance using only 11% of the cache budget across various long-context tasks, reducing decoding latency by 1.2 \times to 1.5 \times .

## introduction kv caching is a memory-for-computation acceleration technique for llm inference, enabling faster decoding by reusing intermediate hidden states @xcite . however, during inference, each decoded token must attend to the full kv cache, causing cache reading latency to grow significantly with context length. for example, in llama 7b @xcite , a 32ktoken kv cache requires 16gb of memory and over 11ms to read-accounting for more than half of the total inference time @xcite . to address this issue, previous works have proposed to selectively retain only a subset of kv cache entries based on token importance. among them, one line of work-known as kv eviction (fig. 1(b ))-focuses on retaining fixedposition tokens that typically receive higher attention weights, such as the initial tokens (due to the attention sink phenomenon) and the most recent tokens @xcite @xcite . however, these approaches overlook the dynamic nature of kv criticality, i.e., tokens that are evicted earlier may become important in the future. their inability to recall evicted tokens often results in degraded performance in multi-round qa or long conversation applications. motivated by this, another line of work-kv retrieval (fig. 1(c ))-has been proposed to dynamically recall tokens that are most relevant to the current query during generation @xcite . despite achieving better performance, kv retrieval requires frequent estimation of the token importance for every new query, introducing additional computational overhead. to mitigate this, existing methods perform page-level retrieval, where all tokens that belong to a certain page of the kv cache are retrieved (or not re-trieved) simultaneously to avoid computing full attention scores, leading to a coarser granularity of retrieval. however, we observe that in long-context tasks, information relevant to the current query may be scattered throughout the entire input, i.e., important tokens are often sparsely distributed across the kv cache (shown in fig. 2 ). consequently, page-level retrieval inevitably leads to imprecise selection: retrieved pages may include irrelevant tokens, while evicted pages may exclude critical ones, thereby affecting the model performance. in this paper, we aim to address the retrieval inaccuracy while preserving selection efficiency. specifically, we find that quantizing the key cache to as low as 1-bit has minimal impact on the accuracy of top-k selection in token importance estimation (shown in fig. 3 ). despite quantization truncates large values, important tokens are still preserved in the top-k after computing quantized attention. based on this insight, we propose fine-grained and efficient kv cache retrieval (fier), a 1-bit quantization-based kv retrieval method. as shown in fig. 1(d ), fier enables more accurate recovery of important tokens and reduces the selection cost. this leads to improved model performance under the same cache budget. we evaluate fier across pg19 (rae et al., 2019), longbench @xcite , and the passkey retrieval benchmarks @xcite . the results demonstrate the effectiveness of fier in both generative and retrieval-focused settings. experiments show that fier achieves performance comparable to using the full kv cache while requiring only 11% of the cache budget, and consistently outperforms existing kv eviction and retrieval baselines. additionally, fier achieves 1.2× to 1.5× decoding speedup across different context lengths on a single rtx 4090 gpu. in summary, we make the following contributions in this work: long-context llms. large language models (llms) have transformed the landscape of natural language processing, largely due to their strong ability to deal with long context. their context length capacity has increased dramatically-from 4k to 128k @xcite , 1m @xcite , and even 10m @xcite tokens. this expansion unlocks a range of advanced capabilities, including o1 long-range reasoning @xcite , incontext learning @xcite , and multimodal intelligence @xcite . fier aims to improve the inference efficiency of long-context llms by exploiting the sparsity of the kv cache. ## conclusion we present fier, a fine-grained and efficient kv cache retrieval algorithm that selects important tokens using 1-bit quantization. by involving all tokens in the computation, fier enables token-level criticality estimation, leading to improved recall rate and model performance. extensive experiments across various tasks and model architectures show that fier consistently outperforms existing methods. notably, fier matches full cache performance using only 11% of the kv budget and achieves a 1.2×-1.5× decoding speedup.