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.
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:
- 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.
- 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.
- 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.
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.
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