SARP: An On-SSD Index for KVCache with Fast Prefix Matching and Recovery: what it means for business leaders

An SSD-resident index for LLM cache metadata that recovers from a restart up to 77 times faster than in-memory indexes while matching prefixes nearly as well, so a crash no longer forces minutes of GPU recomputation.

1. What the method is

SARP, short for Sparse Adaptive Routing and Packing, is a persistent index for the key-value cache that large language model serving systems keep across GPU nodes and storage tiers. The index answers one question for every incoming request: which already computed cache blocks match the request's token prefix, and where they live. SARP stores the block identifiers and block metadata on SSD, packed into segments of up to 64 consecutive blocks, and keeps only a sparse routing directory in memory that points from selected prefix positions to candidate segments. After a crash or restart it reloads just that directory from a snapshot, so recovery rebuilds a fraction of the state an in-memory index needs, while a single SSD read fetches metadata for many blocks at once. The authors, at Arizona State University, built it in C++ on top of RocksDB, WiredTiger and BloomStore and report results on four chat and agent workloads.

2. Why the method was developed

Every request that shares a prefix with earlier traffic, which is most of them in chat and agent sessions, can skip recomputing that prefix on the GPU if the serving system can find the cached blocks. The index that makes this possible normally lives in DRAM, so a crash or routine restart loses it, and otherwise intact cache blocks on SSD or in object storage become invisible until the index is rebuilt. The authors measure that rebuild at one billion entries: 621 seconds for Redis and roughly 33 and 52 minutes for Mooncake and NVIDIA Dynamo. During that window affected requests pay full prefill cost. Moving the index onto SSD with RocksDB cuts recovery to about 100 milliseconds but slows prefix matching by 39 to 402 times, because each block or tree node becomes a separate storage read. Neither placement gives both fast recovery and fast matching, and that gap is what SARP closes.

3. Who should care

This matters to us only where we run our own LLM serving at scale rather than call a vendor API. Our inference platform engineers are the direct audience: if we deploy vLLM, SGLang, Dynamo, Mooncake or llm-d with cache offloading to CPU memory, SSD or object storage, the global index is a single point whose loss turns a restart into minutes of degraded latency and extra GPU spend. Site reliability and on-call staff should care because index recovery sets how long time to first token stays elevated after any restart, planned or not. Finance and capacity planning should note that lost cache visibility means paying for prefill again on hardware we already paid to fill. Product owners of chat and agent features, where sessions grow turn by turn and published coding-agent traces show 95.7 percent of input tokens hitting the cache, feel the latency most. Teams buying managed inference can skip this page.

4. How the method works

Token sequences are cut into 16-token blocks, each identified by a chained hash of the whole prefix ending there. SARP packs up to 64 block identifiers and their metadata into one segment on SSD, so one read covers up to 1,024 tokens. In memory, a routing directory maps the prefix hash at four evenly spaced routing points per segment to a posting list of segments sharing that prefix. Where a posting list exceeds a threshold, refinement adds one routing point at the interval midpoint, or at the last block of the final interval. Each candidate carries a 64-bit filter of eight 8-bit fingerprints over two-block regions, bounding how far it can match. SARP binary-searches the sorted list, retrieves the strongest candidates within a per-window cap, and verifies block identifiers with AVX2 before reusing anything. Pruning drops routing points whose predecessor holds three or fewer candidates, and recovery reloads only the directory snapshot.

5. How it was evaluated

The authors drive the index alone, with no model inference or cache transfer, replaying four datasets tokenized with the Llama-2 tokenizer: CodeAct and LMCache-Agent for agent sessions, EABF with long ShareGPT conversations, and UltraChat with 487,000 short synthetic chats. Each turn first matches its accumulated history, then inserts the extended sequence, with sessions advanced round-robin and every experiment repeated three times. The testbed is one server with two 28-core Xeon Gold 6330 CPUs, 751 GiB of DRAM and a 2 TB Samsung 980 PRO NVMe drive, using 42 request threads and 14 RocksDB threads. Baselines are vLLM's in-memory DRAM-BlockHash, SSD-BlockHash with the same entries in RocksDB, Segment-Hash keyed directly from the query, and Segment-Radix with its memory capped so its recovery lands within 0.96 to 1.96 times SARP's. All SSD designs get a RocksDB memory budget of 10 percent of the uncompressed SSD-BlockHash store, from 5 to 362 MiB. One SARP configuration is used across all datasets.

6. How it performed

Across the four workloads SARP recovers 8.0 to 77.5 times faster than the in-memory baselines and delivers 1.15 to 66.6 times the request throughput of the on-SSD baselines: 3.70 to 66.6 times SSD-BlockHash, 2.04 to 5.67 times capped Segment-Radix and 1.15 to 6.78 times Segment-Hash, with the lowest mean prefix-match latency on every dataset. The price in cache reuse is negligible, 0.0030 to 0.029 percent fewer tokens reused than exact matching. The limits matter: the evaluation is an index-only simulation on one server, so it does not show end-to-end time to first token or GPU savings, and the text we have is truncated before the recovery, space-amplification and scalability details. SARP is a research prototype, not yet part of vLLM, Dynamo or Mooncake, and the gains are smallest against Segment-Hash on some workloads. Our call: watch, and ask our serving vendor or platform team how long our cache index takes to recover today. (Source: arXiv 2610.26849, 2026)