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

Teams serving agents on hybrid models should read this, because HiState (the paper's prefix cache system) eases a cache failure that only hybrid models have, without extra GPU memory. The recurrent layers of a hybrid model compress the whole prefix into a fixed-size snapshot (the paper calls it a checkpoint), and it cannot be cut back to an earlier position. So even when the KV is still cached, if the snapshot at the match point was never saved or has already been evicted, a long stretch must be recomputed from an earlier snapshot, or from scratch. HiState exploits an asymmetry: a cache hit reads every matching KV entry but only one snapshot, and the snapshot's size does not depend on context length. So it keeps many historical snapshots on SSD and saves fast memory for KV. It also sets how dense each segment's snapshots are from storage pressure, and puts snapshots and KV into one eviction queue ranked by recomputation cost. On two public coding-agent traces, it reaches p99 TTFT speedups of up to 5.73 times over Marconi on vLLM and up to 5.44 times over SGLang's HiCache. Extra snapshots cost no fast memory, and each hit reads only one from slow storage.

What problem is it actually solving?

First, why caching is different for hybrid models. A full-attention layer stores KV for every token, so prefix caching can cut and reuse at any position: if a new request shares its first 5,000 tokens with an old one, the system reuses the KV of those 5,000 tokens. Recurrent layers (linear attention, state space models) store nothing per token. They keep one fixed-size state and update it in place with every token they read. By token 7,000 that state already mixes in tokens 5,001 to 7,000 and cannot go back to what it was at token 5,000. So to resume a hybrid model at some position, the system needs all the KV before that position and one snapshot saved at or before it. If the snapshot is earlier than the match point, the system restores the recurrent state from that snapshot, reuses the KV before it, and reruns prefill on the tokens between the snapshot and the match point; if there is no snapshot at all, the whole prefix must be prefilled again.

In ordinary chat this is not a big problem: each turn appends to the previous one, so saving a snapshot at the end of each turn mostly suffices. Existing schemes such as Marconi save snapshots mainly at turn ends and at observed branching points. Agents are different. Here is a coding-agent session (illustrative):

At turns 6 and 8 the KV is still cached, yet a long stretch must be recomputed for lack of a snapshot. The paper calls such a hit in the middle of a turn an internal hit. There is a second kind of failure. A snapshot saved at the end of turn 1 goes unread while the session moves on for many turns and gets evicted under LRU. A direct remedy is to refresh the access times of all earlier snapshots on the same prefix whenever one is hit (the paper calls this refresh-all). But then every active session's historical snapshots are protected, and a session waiting for a tool result can lose its latest snapshot because it looks long unused, so its next append misses the cache outright.

The obvious fix, saving a snapshot every fixed number of tokens, is expensive. The paper's numbers: for Qwen3.5-9B with a 32K context and a snapshot every 1,024 tokens, the FP32 recurrent states alone take about 1.6 GB, more than the BF16 KV of the same context (about 1.1 GB, Section 1). Snapshots fill memory, push out other sessions' KV, and the recomputation saved in one place is paid back elsewhere.

The overall design

HiState is a prefix cache manager built on vLLM that answers three questions:

The division of labor: tiering lets the system keep many snapshots, interval control sets how dense they are, and eviction decides which snapshots and which old sessions give way. Each part is explained below.

Why historical snapshots belong on SSD while KV gets priority in fast memory

The starting point is a simple count. Take a context of L tokens with a snapshot every I tokens. The cache holds the KV of all L tokens and about L/I snapshots. A hit at the end reads all of the KV but only one snapshot. The paper calls "bytes one hit reads" divided by "bytes stored for this context" the access ratio: 100% for KV and I/L for snapshots. At 32K tokens, an interval of 1,024 gives a snapshot ratio of 3.1%, and an interval of 4,096 gives 12.5% (Section 3.1). In other words, of the snapshots kept in fast memory, one hit uses only a small fraction; the rest just take up space.

Now the cost of reading back from slower storage. The paper estimates it for Qwen3.5-9B on one H100, with 64 GB/s over PCIe 5.0 and 5 GB/s from SSD (Figure 5b):

With snapshots on SSD, each hit costs only about 10 ms more, and that number does not depend on context length or on how many snapshots are kept. With KV on SSD, the extra time grows with context length and approaches one second at 128K. So fast memory should go to KV first; extra snapshots on SSD barely slow any single hit. HiState's placement follows this: the GPU holds only running KV and states, CPU memory holds reusable KV prefixes first, and historical snapshots go to SSD; colder KV moves to SSD only when CPU memory is full too.

How dense should snapshots be?

Denser snapshots mean fewer tokens to recompute on an internal hit but more storage. HiState picks an interval for each newly added context segment by minimizing the sum of the two costs. How the recurrent state at those positions is captured during prefill (for example, whether prefill chunks are split at the interval) is not described in the paper, so a reimplementation has to fill in that step.

Recomputation cost is measured as how far a hit lands from the nearest earlier snapshot, assuming the hit is equally likely at every position in the segment. Storage cost is the number of snapshots times the size of one snapshot, times a pressure factor. The snapshot size is expressed as the number of tokens of KV it equals, so the two costs share one unit and can be added. The pressure factor equals how long KV stays in the cache on average divided by how long snapshots stay on SSD on average. Both durations are estimated online with exponential moving averages. If snapshots get pushed out before KV, SSD is tight, the factor grows and the interval widens. HiState actually picks, from the set of supported intervals, the one with the lowest total cost; under the uniform assumption, the continuous approximation shows the trend:
$$I^{\ast }=\sqrt{2L{N}_s\frac{T_{\mathrm{KV}}}{T_{\mathrm{state}}}}$$
$L$ is the length of the new segment, $N_s$ is how many tokens of storage one snapshot equals, and $T_{\mathrm{KV}}$ and $T_{\mathrm{state}}$ are the average residence times of KV and snapshots. The intuition: longer segments and tighter SSD mean sparser snapshots. A mental-math example (illustrative): an 8,000-token segment, one snapshot equal to 100 tokens, equal residence times; under the square root is 2×8000×100, so the continuous solution is about 1,265 tokens. If SSD gets tight and the factor becomes 4, it doubles to about 2,530. HiState then picks the supported interval closest to the optimum. Whatever the choice, the segment's final snapshot is always saved, so the next append can continue directly.

What goes first when space runs out?

Eviction has to serve two goals at once. Within a session, historical snapshots that may be revisited should stay. Across sessions, a long-inactive session should not keep holding space.

HiState first defines what can be evicted. An intermediate snapshot can go on its own: the KV stays, and a hit falls back to the nearest earlier snapshot still kept and recomputes from there. If neighboring snapshots were also evicted, that stretch can be long, which is why recomputation enters the score. Each session's last KV segment, from its last intermediate snapshot to the end, is bundled with the final snapshot as one unit, because resuming from the end needs both. In the paper's words, reclaiming a cold session removes its unshared KV entries and remaining states; how the remaining prefix is split into units after its final bundle goes, the paper does not spell out. All sessions' intermediate snapshots and these final bundles are ranked together by the score
$$H_x=t_x+\tau \frac{C_x}{M_x}$$
$t_x$ is the last access time, $C_x$ is the expected extra recomputation in tokens if it is removed, $M_x$ is the space removing it actually frees in the tier that is short of space (CPU memory or SSD, say). Items stored on other tiers free nothing there. $\tau$ sets how much "how recent" weighs against "how much we lose"; the lowest score goes first. $C_x$ is an expectation weighted by hit-position probability. Sessions are equally likely, the end's access probability is an exponential moving average, and the rest is spread uniformly over internal positions. When a snapshot is hit, all earlier snapshots on the same prefix get their access times refreshed too, so an active session's historical snapshots are not pushed out just because nobody read them directly. This step is the same as plain LRU plus refresh-all. The difference is the cost term $C_x/M_x$: it gives low scores to intermediate snapshots that sit close together and need little recomputation once removed, so they are more likely to go. What goes first is still decided jointly by access time, recomputation cost and space freed, so a long-inactive session's final bundle can also score lowest and be reclaimed whole.

Figure 7 of the paper gives a concrete case. Session B has historical snapshots S1 and S2 and final snapshot S3; a long prefix comes before S1, and only a short gap separates S1 and S2. Session C has only its final snapshot S6. One snapshot must go.

LRU evicts S1 because it has gone longest without access, so B must recompute that long prefix if it returns to S1. LRU plus refresh-all keeps B's historical snapshots but pushes out S6, which C is waiting to use. HiState evicts S2, because rebuilding it from S1 takes only a short stretch. Both S1 and S6 survive.

Results: how much does tail latency drop?

First, a concept used below. A request is reuse-sensitive if it meets either of two conditions. Under vLLM's disk-offload version (the baseline for the mean TTFT rows below), its hit rate is at least 5 points below the unlimited cache (an ideal reference that never evicts and keeps a snapshot at every position). Or its hit rate differs by at least 5 points between HiState and vLLM's disk-offload version. These are the requests where the caching policy actually matters.

Experiments run Qwen3.5-9B on one H100 with a GPU cache pool of about 45 GiB, plus 96 GiB of CPU memory and 150 GiB of disk. The workloads come from two public traces of real coding agents: Weka (Claude Code sessions, 125 sessions and 3,784 requests) and the Codex subset of TraceLab (68 sessions and 4,791 requests), with at most 24 sessions running at once and each replayed for about three hours. The baselines are vLLM with Marconi's save-at-turn-end policy (GPU only), the authors' CPU-offload and CPU-plus-disk-offload versions of vLLM (both with LRU), and SGLang's HiCache. Hit rate counts only tokens that were truly not recomputed: a KV match whose snapshot must be recomputed does not count.

These numbers show two things, plus one caveat. First, offloading alone cuts tail latency a lot, but HiState is faster still than the vLLM version that also offloads to disk, so capacity is only part of it; keeping the right snapshots matters too. Second, HiCache also uses disk, yet its p95 and p99 are worse than even the vLLM version that offloads only to CPU. The paper's explanation is that it splits GPU cache half and half between KV and states by default, the state half cannot relieve KV pressure, and KV gets evicted before it is reused. The caveat: the mean TTFT is computed on the reuse-sensitive subset, not on all requests. Across all requests, p50 is broadly the same as the disk-offload version, slightly worse on Weka.

The ablation uses the 46 reuse-sensitive TraceLab requests (Figure 10). Swapping eviction back to file-level LRU raises mean TTFT by 37%, the largest loss. Swapping interval control for two other ways of saving snapshots raises mean TTFT by about 9% to 10%. One is vLLM's align policy, which saves snapshots only where a scheduler step ends exactly on a cache block boundary. The other saves one every 32 cache blocks (a GPU cache pool block holds 576 tokens in the experiments); both keep final snapshots. So eviction contributes the most, interval control decides where computation can resume, and both are needed.

A synthetic test measures how much intermediate snapshots are worth as context rewrites become more frequent: each session runs 16 turns with 8K new input tokens per turn, and the share of rewriting requests comes in four levels up to 10%. Compared with vLLM's disk-offload version, HiState cuts the mean TTFT of rewriting requests by 18% to 21%, because it keeps snapshots near the rewrite point. The previous turn's final snapshot lies after the rewrite point and contains the discarded content, so it cannot be used, and the baseline must fall back to an earlier valid snapshot before the rewrite point.

Limitations I see

First, the setup is narrow. Only one model, Qwen3.5-9B, on one H100 is tested, with no multi-GPU parallelism and no combination with deployments such as prefill-decode disaggregation. On other hybrid models with a different share of recurrent layers, the size ratio between snapshots and KV changes, and the SSD benefit must be recomputed.

Second, the gains sit in the tail. p50 is about the same as the disk-offload version and slightly worse on Weka; the paper itself says the extra p99 gain over the disk-offload version is smaller on Weka than on TraceLab. Rewriting requests get 18% to 21% lower mean TTFT, not an order of magnitude.

Third, access probabilities rest on simple assumptions. Recomputation cost assumes hits are uniform within a segment, and sessions are assumed equally likely to be accessed. Real agent truncation often happens at fixed places (such as the middle of a tool output), and saving snapshots by that pattern might be cheaper than the uniform assumption, a direction the paper does not test. Sessions that return after a long idle period still miss under HiState, which on reuse-sensitive requests recovers only about 85% to 87% of the reusable tokens of the unlimited cache.

How a search or recommendation team could try it

Agents in search and recommendation (multi-turn retrieval assistants, conversational recommendation) also go back and rewrite context. Teams serving them on hybrid models can try it this way:

1. Measure the problem first: count, in your own request logs, how many requests match KV at a point that is not the end of any turn, and what their TTFT is. If the share is low, leave things alone.
2. Do the cheapest step first: write historical snapshots to SSD, keep KV in CPU memory first, keep final snapshots in fast memory as before, and watch p95 and p99 TTFT.
3. Then change eviction: in the ablation eviction contributes most, so first replace LRU with a score of access time plus recomputation cost divided by space, and decide afterwards whether to add the adaptive interval.
4. Keep watching p50, to make sure the tail gains are not bought with slower common requests.

Verdict

The key lesson: prefix caching for hybrid models should put KV and snapshots on different storage tiers, because one hit reads all the KV but only one snapshot; for eviction, both then go into one queue ranked by recomputation cost.