Tail-Replay: Escaping the Curse of Linear Attention in Prefix Caching for Hybrid LLMs

• URL: http://arxiv.org/abs/2608.30310v1
• Date: Mon, 31 Aug 2026 06:27:07 GMT
• Title: Tail-Replay: Escaping the Curse of Linear Attention in Prefix Caching for Hybrid LLMs
• Abstract summary: We present Tail-Replay, a prefix caching mechanism that enables unconstrained token-level prefix reuse.<n>We evaluate Tail-Replay on three Gated DeltaNet-based hybrid models using the LongBench and RULER benchmarks.
• Score: 5.5444120195759785
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hybrid large language models interleave full-attention layers with linear-attention layers to reduce the cost of long-context inference. This structure complicates prefix caching: full-attention key-value caches are token-addressable, whereas linear-attention layers maintain recurrent states that cannot be rolled back to arbitrary prefix boundaries. Existing hybrid prefix caching methods address this mismatch by storing recurrent-state checkpoints. As a result, token-level matches are directly usable only at positions aligned with stored checkpoints, constraining prefix reuse to a discrete set of boundaries. We present Tail-Replay, a prefix caching mechanism that enables unconstrained token-level prefix reuse in hybrid large language models. The key insight is that linear-attention mechanisms such as Gated DeltaNet can be viewed as a structured, lossy compression of the input prefix: gated recurrent updates progressively attenuate the contributions of earlier inputs. Consequently, the recurrent state of a matched prefix can be well approximated by replaying only a short, recent suffix of that prefix. Tail-Replay exploits this property by caching the exact full-attention key-value cache while omitting recurrent-state checkpoints. On a cache hit, it reconstructs the linear-attention states by replaying a short, recent suffix of the matched prefix. As a result, the reuse boundary is determined by the shared tokens rather than by recurrent-state checkpoints. We evaluate Tail-Replay on three Gated DeltaNet-based hybrid models using the LongBench and RULER benchmarks. With only a 5--10\% replay budget, it retains 92.8--99.9\% of full-prefill quality on LongBench and RULER. For serving efficiency, we evaluate time-to-first-token speedups across multiple matched-prefix lengths---8K, 16K, and 32K. The speedup grows with prefix length, reaching $9.1$--$14.3\times$ over full prefill at 32K.

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)
• Position Rebinding Cache Reuse: Replay-Free Visual Revisiting for Interleaved Multimodal Reasoning [51.563653495547335]
  multimodal reasoning improves visual grounding by revisiting visual evidence during multi-step generation.<n>We propose Position Rebinding Cache Reuse (PRCR), a cache-level framework for replay-free visual revisiting.<n>PRCR achieves replay-level or better performance, improving average accuracy by 5 percent and reducing visual-revisiting by up to tens of thousands of times.
  arXiv  Detail & Related papers  (2026-06-25T05:47:52Z)
• CacheWeaver: Cache-Aware Evidence Ordering for Efficient Grounded RAG Inference [4.3361375690943795]
  Prefix caching in serving engines such as vLLM reduces this cost only when requests share the same token prefix.<n>We present CacheWeaver, a lightweight prompt-layer method for cache-aware evidence ordering.
  arXiv  Detail & Related papers  (2026-06-18T00:38:46Z)
• miniReranker: Efficient Multimodal Reranking through Visual Cache Reuse and Interaction Sparsity [21.54829080388454]
  Multimodal large language models (MLLMs) have recently shown strong potential as point-wise rerankers.<n>However, point-wise reranking suffers from substantial repeated computation across query--document pairs.<n>We propose a $textitvision-first$ formulation that improves both cache reuse efficiency and reranking performance.
  arXiv  Detail & Related papers  (2026-06-09T12:11:02Z)
• 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)
• Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference [2.752817022620644]
  Auto-regressive token generation in large language models requires "attending to" key and value tensors (KV cache) of all previous tokens.<n>Prior work aims to improve the efficiency of this decode process by multiple requests together.<n>We introduce Chunked Hash Tree (CHT), a lightweight data structure that enables fast prefix detection and efficient request selection.
  arXiv  Detail & Related papers  (2026-05-07T11:34:10Z)
• 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)
• Sparse Prefix Caching for Hybrid and Recurrent LLM Serving [0.7284556903703034]
  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.
  arXiv  Detail & Related papers  (2026-04-17T09:24:58Z)
• Rectified Sparse Attention [61.7702154360081]
  Efficient long-sequence generation is a critical challenge for Large Language Models.<n>We propose Rectified Sparse Attention (ReSA), a simple yet effective method that combines block-sparse attention with periodic dense rectification.<n> Experiments across math reasoning, language modeling, and retrieval tasks demonstrate that ReSA achieves near-lossless generation quality.
  arXiv  Detail & Related papers  (2025-06-04T16:01:48Z)
• 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)

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.