Sparse Prefix Caching for Hybrid and Recurrent LLM Serving

• URL: http://arxiv.org/abs/2605.05219v1
• Date: Fri, 17 Apr 2026 09:24:58 GMT
• Title: Sparse Prefix Caching for Hybrid and Recurrent LLM Serving
• Abstract summary: We formalize sparse prefix caching as checkpoint placement under a distribution over overlap depths.<n>For use cases where requests share a non-trivial prefix, we show that our method consistently improves the frontier traced by standard asymmetry on real-world data.<n>It preserves exact outputs, does not change the recurrent computation itself or require new recurrent update kernels.
• Score: 0.7284556903703034
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Prefix caching is a key latency optimization for autoregressive LLM serving, yet existing systems assume dense per-token key/value reuse. State-space models change the structure of the problem: a recurrent layer can resume from a single stored state rather than requiring the entire token history. This asymmetry opens a new design point between no reuse and dense caching: store exact recurrent states at a sparse set of checkpoint positions and, on a cache hit, resume from the deepest stored checkpoint and recompute the remaining suffix exactly. We formalize sparse prefix caching as checkpoint placement under a distribution over overlap depths, yielding an exact O(NM) dynamic program. For use cases where requests share a non-trivial prefix (e.g. asking different questions about a single long document), we show that our method consistently improves the Pareto frontier traced by standard heuristics on real-world data. Across QuALITY and System Prompts, distribution-aware placement dominates every fixed-budget baseline on the measured layer-group Pareto frontier and matches or outperforms the strongest heuristic (block caching) while typically using substantially fewer checkpoints, with the largest gains at low checkpoint budgets where the overlap distribution is most non-uniform. The method is most relevant when many requests share a substantial but not identical prefix within a retained cache entry. It preserves exact outputs, does not change the recurrent computation itself or require new recurrent update kernels, applies to recurrent/SSM layers whose hidden state can be extracted and restored exactly, and for hybrid models can be combined with existing KV-cache compression techniques.

Related papers

• Back from the Future: Key-Value Cache Management by Counter-Causal Surprise [67.1056509495879]
  Key-value (KV) cache management through compression and eviction strategies has emerged as an important research direction in recent years.<n>We propose a simple yet effective KV eviction scheme motivated by the insight that past tokens which can be well-predicted from more recent tokens are redundant.<n>We evaluate our strategy on various open-source LLMs and benchmark datasets showing competitive or improved performance over other state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-07-30T02:42:51Z)
• Remembering Distinct Items, Not Tokens: A Learnable Dirichlet-Process Cache Between State-Space Models and Attention [0.48342038441006796]
  We study a sparse cache that allocates a slot only when an input is novel, so its size tracks the number of distinct items rather than the number of tokens.<n>We develop it in two forms, a static cache with a fixed concentration and a surprise-adaptive variant whose concentration follows the recent novelty rate.
  arXiv  Detail & Related papers  (2026-07-10T18:28:21Z)
• Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction [65.710271475739]
  We introduce a global retention-based KV eviction method that learns each token's future utility under a unified memory budget.<n>We show that our method substantially reduces KV memory while matching or surpassing full-cache inference.<n>These results suggest that learned, globally calibrated KV eviction is not only a compression technique, but also a mechanism for improving long-context reasoning.
  arXiv  Detail & Related papers  (2026-05-10T16:47:50Z)
• Towards Distributed Inference of LLMs on a P2P Network [1.1458853556386797]
  Prefix caching can reduce LLM inference latency by reusing KV caches across requests with shared prompts.<n>We propose a decentralized, prefix-cache-aware routing scheme for peer-to-peer LLM serving.
  arXiv  Detail & Related papers  (2026-05-07T15:40:51Z)
• A Parametric Memory Head for Continual Generative Retrieval [52.66674234249913]
  Generative information retrieval (GenIR) consolidates retrieval into a single neural model that decodes document identifiers (docids) directly from queries.<n>We show that sequential adaptation improves retrieval on newly added documents but substantially degrades performance on earlier slices.<n>We propose post-adaptation memory tuning (PAMT), a memory-only stabilization stage that augments an adapted model with a modular parametric memory head.
  arXiv  Detail & Related papers  (2026-04-25T17:38:51Z)
• Stochastic KV Routing: Enabling Adaptive Depth-Wise Cache Sharing [29.913403615975174]
  Serving transformer language models with high throughput requires caching Key-Values ( KVs) to avoid redundant computation.<n>The memory footprint of KV caching is significant and heavily impacts serving costs.<n>We propose a simple training approach: random cross-layer attention. During training, layers randomly choose to attend either to their own KV states or those of a preceding layer.
  arXiv  Detail & Related papers  (2026-04-03T14:56:17Z)
• TokenLake: A Unified Segment-level Prefix Cache Pool for Fine-grained Elastic Long-Context LLM Serving [12.80179556886128]
  We propose a unified segment-level prefix cache pool, TokenLake.<n>It uses a cache interface to expose requests' query tensors, prefixes, and cache-aware operations.<n> TokenLake can improve throughput by up to 2.6$times$ and 2.0$times$ and boost hit rate by 2.0$times$ and 2.1$times$.
  arXiv  Detail & Related papers  (2025-08-24T05:45:16Z)
• EPIC: Efficient Position-Independent Caching for Serving Large Language Models [19.510078997414606]
  Caching improves serving performance by reusing Key-Value vectors across requests.<n>Existing context caching requires exact prefixes across requests.<n>We introduce Position-Independent Caching (PIC), which enables modular reuse of KV vectors regardless of prefixes.<n>We also introduce EPIC, a serving system incorporating our new LegoLink algorithm, which mitigates the inappropriate "attention sink" effect at every document beginning.
  arXiv  Detail & Related papers  (2024-10-20T08:42:29Z)
• Efficient Inference of Vision Instruction-Following Models with Elastic Cache [76.44955111634545]
  We introduce Elastic Cache, a novel strategy for efficient deployment of instruction-following large vision-language models. We propose an importance-driven cache merging strategy to prune redundancy caches. For instruction encoding, we utilize the frequency to evaluate the importance of caches. Results on a range of LVLMs demonstrate that Elastic Cache not only boosts efficiency but also notably outperforms existing pruning methods in language generation.
  arXiv  Detail & Related papers  (2024-07-25T15:29:05Z)
• Training-Free Exponential Context Extension via Cascading KV Cache [49.608367376911694]
  We introduce a novel mechanism that leverages cascading sub-cache buffers to selectively retain the most relevant tokens.<n>Our method reduces prefill stage latency by a factor of 6.8 when compared to flash attention on 1M tokens.
  arXiv  Detail & Related papers  (2024-06-24T03:59:17Z)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference [78.65321721142624]
  We focus on a memory bottleneck imposed by the key-value ( KV) cache. Existing KV cache methods approach this problem by pruning or evicting large swaths of relatively less important KV pairs. We propose LESS, a simple integration of a constant sized cache with eviction-based cache methods.
  arXiv  Detail & Related papers  (2024-02-14T18:54:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.