HiState: Hierarchical Prefix Cache Management for Hybrid LLM Serving in Agentic Workloads

Zaifeng Pan, Lucas Wang, Xinwei Qiang, Yanbo Zhou, Chang Chen, Zhengding Hu, Yue Guan, Yufei DingarXiv 2026 · arXiv

TL;DR

HiState is a new prefix cache management system designed specifically for hybrid LLMs (which combine attention and recurrent layers) serving agentic workloads. By exploiting the fact that recurrent state checkpoints are small and only one is needed per request, HiState uses a hierarchical approach—storing checkpoints on SSDs while keeping KV caches in fast memory—to achieve up to a 5.73× speedup in tail latency (p99 TTFT).

What Problem Does This Paper Address?

Modern "hybrid" LLMs (like Jamba or Kimi) are gaining popularity because they combine the high quality of standard attention layers with the efficiency of recurrent layers (like Mamba or Linear Attention). However, serving these models efficiently is tricky, especially for AI agents.

Standard prefix caching works well for attention layers: if two requests share the first 100 tokens, the system reuses the calculated Key-Value (KV) cache for those tokens. But recurrent layers are different. A recurrent state summarizes the entire preceding context into a single fixed-size vector. If an agent edits the middle of a prompt or rewinds to an earlier step, the system needs a specific "checkpoint" of that recurrent state at the exact point of the change.

Figure 1. Model architectures and prefix cache reuse. (a) A full-attention model. (b) A hybrid model with linear-attention layers. (c) KV entries support reuse through t5, but the checkpoint S7 at t7 cannot be converted back into S5. Without S5 or an earlier checkpoint, the system must recompute t0–t5.

Existing systems usually only save checkpoints at turn boundaries. Agent workloads, however, frequently involve context mutation:

  • Truncation: Shortening long tool outputs to save space.
  • Rewinding/Editing: Going back to a previous step to try a different approach.

These operations create "internal prefix hits" where the KV cache might be available, but the necessary recurrent checkpoint is missing, forcing the system to recompute the entire prefix from scratch.

Methods

HiState introduces three core innovations to manage these checkpoints without exhausting system memory:

  1. Asymmetric Cache Tiering: The authors observed a crucial asymmetry: to resume a prefix, you need all the KV entries for preceding tokens, but only one recurrent checkpoint. While KV caches grow with context length, a single checkpoint is small and fixed-size. HiState prioritizes fast GPU/CPU memory for KV caches and offloads historical checkpoints to the much larger (but slower) SSD. Because only one checkpoint is loaded per hit, the SSD transfer time is negligible compared to recomputation.
  2. Adaptive Interval Control: Instead of saving checkpoints at fixed intervals, HiState uses a controller that balances the cost of recomputation against storage pressure. It dynamically adjusts how often to save checkpoints based on context length and current memory/SSD usage.
  3. Unified Eviction Policy: Standard Least-Recently Used (LRU) policies often evict useful historical checkpoints during long agent sessions. HiState uses a cost-aware ranking that considers recency, the amount of recomputation a checkpoint saves, and its storage footprint. This allows the system to "sparsify" (delete) intermediate checkpoints that are cheap to recompute while protecting critical terminal states.
Figure 2. Context changes that create internal prefix hits. (a) Trun- cating a message’s middle preserves a prefix ending near the omis- sion marker. (b) Rewinding and revising an earlier input preserves a prefix ending where the edit begins.

Datasets

The researchers evaluated HiState using:

  • Weka: A dataset of real-world traces from coding agents (Claude Code).
  • TraceLab: A public dataset characterizing coding agent workloads (specifically the Codex subset).
  • Synthetic Microbenchmarks: Designed to stress-test the system by varying how frequently context is mutated.

Key Insights and Ideas

  • The "One-Checkpoint" Rule: The most significant "aha moment" is that recurrent state reuse is not data-intensive at the point of retrieval. Even if you store thousands of checkpoints on an SSD, you only ever need to pull one to start generating text. This makes SSDs a perfect, low-cost home for historical states.
  • LRU is Fragile for Agents: In multi-agent environments, a session might pause while waiting for a tool output. A standard LRU policy might see this "idle" session and evict its state to make room for others. When the tool finally returns, the agent suffers a massive latency penalty. HiState’s unified eviction prevents this "append miss" by valuing the recomputation cost of terminal states.
Figure 3. Checkpoint eviction before reuse under LRU. (a) S1 is saved after turn 1 but evicted under memory pressure as the session advances. Forking at that boundary in turn 8 requires recompu- tation. (b) While C waits for tool results after turn 6, A and B append new turns. Their newer checkpoints can displace C’s latest checkpoint S6 under memory pressure, causing a miss when C ap- pends turn 7. Each row shows a session’s context, with Si denoting the checkpoint after turn i.

Key Results

HiState was implemented on top of the popular vLLM framework and compared against state-of-the-art baselines like SGLang-HiCache and vLLM-Marconi.

  • Speedup: HiState achieved up to 5.73× speedup in p99 Time-To-First-Token (TTFT) on real agent traces.
  • Cache Hit Rate: On reuse-sensitive requests, HiState recovered 85-87% of the tokens that would be available with "Unlimited Cache," significantly outperforming baselines that rely on simple offloading.
  • Mutation Handling: In microbenchmarks with high mutation rates (10%), HiState reduced mean TTFT by 21% compared to standard disk-offloading methods.

Limitations and Future Work

  • SSD Bandwidth: While the paper argues checkpoint loading is fast, extremely high-concurrency environments might eventually bottleneck on SSD I/O if many sessions resume simultaneously.
  • Model Specificity: The evaluation focused on Qwen3.5-9B. While the principles apply to any hybrid model (like Jamba), the specific storage-to-compute ratios might vary for much larger models.
  • Integration: The authors note that HiState complements other optimizations like prefetching and scheduling, but full integration with those techniques remains for future work.

Summary updated

Abstract

Hybrid large language models combine full-attention and recurrent linear layers to reduce inference costs. Prefix caching can further reduce redundant computation across requests, but a recurrent checkpoint cannot recover an earlier state corresponding to a shorter prefix. Existing hybrid prefix caching systems retain checkpoints at selected boundaries to support common reuse patterns in conventional conversations. However, agent workloads modify and revisit earlier contexts, exposing reusable prefixes whose checkpoints were never saved or have already been evicted. A straightforward approach is to retain more checkpoints to reduce recomputation, but their cumulative footprint can displace reusable prefixes from other sessions and cause additional cache misses. To address these problems, we present HiState, a prefix cache management system for hybrid models serving agent workloads. Our key observation is that prefix reuse accesses all matching key-value (KV) entries but only one recurrent checkpoint, regardless of how many checkpoints are retained. This asymmetry allows HiState to retain historical checkpoints on SSD while prioritizing fast memory for KV entries: each hit retrieves only one checkpoint whose size is independent of context length. Within this hierarchy, we propose adaptive interval control to balance checkpoint storage against recomputation, and unified eviction to coordinate checkpoint sparsification with reclamation of stale trajectories. We implement HiState on top of vLLM and evaluate it on two public coding-agent trace datasets and controlled microbenchmarks. On real agent traces, HiState achieves up to 5.73x and 5.44x speedups in p99 TTFT over vLLM-Marconi and SGLang-HiCache, respectively.
BibTeX
@misc{pan2026histate,
  author = {Zaifeng Pan and Lucas Wang and Xinwei Qiang and Yanbo Zhou and Chang Chen and Zhengding Hu and Yue Guan and Yufei Ding},
  title = {{HiState: Hierarchical Prefix Cache Management for Hybrid LLM Serving in Agentic Workloads}},
  year = {2026},
  eprint = {2610.41508},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41508},
}
Figure