Deadline-Driven Approximate Repair of Distributed KV Caches

When a large language model serves long documents, it stores a running memory of every token it has read, called the key-value (KV) cache. At long context lengths this cache outgrows one GPU and is spread across machines. When one machine fails or is preempted, its shard of the cache must be rebuilt. Today there are two choices. The first is to recompute the shard from the prompt. The second is to store it redundantly and copy it back bit-for-bit, using replication or an erasure code, which is a way of storing extra parity data so that missing pieces can be rebuilt from surviving ones. Both choices treat the cache like a database record that must come back exactly. A KV cache is not like that. It is a numerical object that can already be compressed 20x while losing less than 1% accuracy (KV Cache Transform Coding). Its sensitivity is also very uneven: keys and a few outlier channels matter far more than everything else (QAQ).

We propose to repair lost cache shards to a task-level fidelity target rather than to exact bits. The node rebuilding a shard asks many helper machines for small pieces of coded data. It starts from a coarse but exact protected core and sharpens the remaining detail with each extra response. It stops at a deadline instead of waiting for the slowest helper. This changes the central tradeoff in coded repair. Exact codes save bandwidth by contacting more helpers, but on a jittery network that means waiting for the slowest of more machines. With approximate refinement, more helpers can only improve the result, and the deadline caps the latency.

Core Claim

Classical regenerating codes (Network Coding for Distributed Storage Systems) show that contacting $d > k$ helpers reduces repair traffic. For $k=7, n=14$ they report a 73% reduction for the minimum-storage point. But exact repair completes only when the needed responses have all arrived, so latency is governed by an order statistic over $d$ random delays. Section 4 of our research file flags this as a tension, but nothing in it resolves it.

We claim that for model state, the right objective is a different one: minimize repair latency subject to downstream task accuracy staying within a tolerance $\epsilon$ of the undamaged cache. Under that objective, a precision-aware code has two parts:

  • a small exactly-coded core holding the precision-critical components;
  • a well-conditioned real-valued code holding the rest, decodable from any subset of responders.

This code should dominate both exact erasure coding and recompute on tail repair latency at matched storage overhead and matched accuracy.

Numerical precision is the mechanism that decides what goes in each part. The analysis in Every Bit Counts shows exact-match behaviour in softmax attention has a sharp bit-width cliff: INT4 accuracy fell to about 59.7% versus about 92.7% at INT8 on their synthetic equality task. That tells us some components cannot be approximated at all and belong in the exact core. Precision also constrains the refinement code itself. Its stored values are low-bit numbers, and the decoder amplifies their rounding error by the conditioning of whichever subset of helpers answered.

Research Program

The representation. We reuse the method of KVTC, which projects keys and values onto a learned PCA basis and allocates bits by dynamic programming. Its coefficient ordering gives us a natural split into two tiers:

  • Tier 0 holds key coefficients above an energy threshold, the outlier channels that QAQ found must stay at 16 bits, and the attention-sink and recent-window tokens. It is protected by an ordinary byte-level erasure code, so it is recovered exactly. Precision is irrelevant for this tier, because the code operates on bit patterns rather than numbers.
  • Tier 1 holds everything else as a real coefficient vector $x \in \mathbb{R}^m$. Each of the $n$ storage nodes holds $y_i = Q_b(A_i x)$, where $A_i$ is that node's block of an encoding matrix $A$ and $Q_b$ rounds to $b$ bits.

Decoding Tier 1. Suppose the set $S$ of helpers answers by the deadline. The rebuilder forms the least-squares estimate $\hat{x}_S = A_S^{+} y_S$, where $A_S^{+}$ is the pseudo-inverse of the rows held by $S$. Its error obeys

$$\|\hat{x}_S - x\| \le \|A_S^{+}\| \, \sqrt{|S|\,m/k}\;\delta_b + \|x - \Pi_S x\|,$$

where:

  • $\delta_b$ is the per-entry rounding error at $b$ bits;
  • $m/k$ is the number of stored values per helper;
  • $\Pi_S$ projects onto the span of the rows of $A_S$.

The second term is truncation error and disappears once $S$ spans the space. The first term is quantization error inflated by conditioning. This is why a random or Vandermonde-style $A$ is a poor choice: some subsets are badly conditioned, the same failure that BACC identified for polynomial coded computing over the reals. BACC fixed it with rational interpolation at Chebyshev nodes. We borrow that lesson and design $A$ to keep the worst-case $\|A_S^{+}\|$ small across all subsets of each size. Candidate designs are near-tight frames and nested Chebyshev-style constructions. We also order rows so that early responders carry the high-energy PCA directions.

The repair policy. The rebuilder issues requests to $d$ helpers. It decodes Tier 0 as soon as its exact code is satisfied, then folds in Tier-1 responses as they arrive. It stops at a deadline $T$, or earlier if an online fidelity proxy crosses threshold. The proxy is the attention-logit distortion predicted from the bound above. The parameters $(d, T, b)$ are chosen per workload from a measured latency distribution, following the hardware-in-the-loop profiling idea of Air Learning.

The simulation-to-hardware study. This is the evaluation lens, not a side topic. Coding results in this area are mostly analytical or simulated. Themis was validated only in ASTRA-SIM, and Rack-Aware Regenerating Codes assume deterministic transfers. GuaranTEE and Walker et al. document what simulators miss: memory bus contention, cache interference, and non-linear thermal behaviour. Our repair runs concurrently with serving traffic, so it competes for GPU memory bandwidth and NIC queues. We will run every scheme twice, in a discrete-event simulator with fitted latency distributions and on a physical GPU cluster under live serving load. We will report where the two disagree.

Baselines

Naive reference: recompute. On failure, the lost shard is recomputed by re-running prefill over the affected tokens on the replacement node. This is the "do nothing" reference because it needs no redundancy. Its cost grows with context length, which favours redundancy at long contexts. KVTC reports up to 8x lower time-to-first-token at 8K context from loading compressed caches instead of recomputing them, but no reported result found on Lacuna for recompute-based repair of a distributed cache shard. It runs on the same GPUs and the same model. Beating it means lower p99 repair latency at every context length above a crossover point we will report, with accuracy within $\epsilon$.

Strongest exact method: byte-level erasure coding. This applies a minimum-storage regenerating code and a locally repairable code to the KVTC-compressed shard bytes, which makes it exact and precision-agnostic. The locally repairable code follows Gopalan et al., where a single failure is repaired inside a small local group. The rack-aware variant follows Hou et al., whose MSRR codes report 33.3% lower cross-rack repair bandwidth than standard MSR for $n=12, k=8, r=4$. This is the strongest competitor because it matches our storage overhead and loses no accuracy. Every scheme will use identical storage overhead, identical compressed shards, and the same helper placement, and each gets the same grid search over $(n, k, d, r)$. Beating it means lower p99 repair latency, or fewer repair bytes, at matched overhead with accuracy within $\epsilon$.

Single compressed backup. Each shard keeps one extra copy compressed by KVTC at a high ratio, at 64x where KVTC still held RULER accuracy, and the rebuilder fetches it from one location. This is the one-description special case of our design. It is a serious competitor and is treated in the next section.

Replication at 2x and 3x is included for completeness. MemEC reports that erasure coding cuts redundancy by up to 60% relative to replication (MemEC).

Ablations. Three ablations isolate the key ingredients:

  • No Tier 0: everything goes into the real-valued code. This tests whether the precision cliff actually bites.
  • Random encoding matrix: replaces our conditioned design. This tests whether conditioning matters at low bit-widths.
  • Exact repair with a deadline: waits for any $k$ responses instead of using approximate refinement. This tests whether approximation itself is the source of the gain.

Why not just…?

Why not just recompute the prefill? It needs no extra storage and is exact. At short contexts it will probably win, and we expect to report that honestly. Prefill cost grows with context, while our repair cost grows only with shard size, so a crossover must exist. The open question is where it falls under live load on hardware. Our context-length sweep on LongBench and RULER locates it directly.

Why not just keep one heavily compressed backup copy? This is the real threat. It costs a few percent of storage and its repair traffic is tiny. Its weakness is that it has a single source, so its latency tail is that one helper's tail, and its fidelity is fixed by the compression ratio. Our design spreads comparable bytes over $d$ sources and accepts any subset. If the latency distribution measured on the cluster is light-tailed, the backup may match us. That outcome would mean the coding machinery is unnecessary, and we would say so. The experiment that settles it fixes the storage overhead and compares p99 repair latency and accuracy under both measured and injected heavy-tailed jitter.

Why not just use an exact locally repairable code, which already avoids wide fan-out? A locally repairable code contacts only $r$ helpers, which limits the slowest-of-many problem. It still has to wait for all $r$, however, and it moves $r$ full compressed fragments. Its exactness also spends bandwidth on low-sensitivity value coefficients that QAQ shows tolerate 2 bits. Our scheme is exact only where the precision cliff demands it. Whether that selective exactness buys meaningful latency is exactly what the head-to-head at matched overhead measures.

Proposed Experiments

Models and workloads. We use open long-context models served with tensor- and sequence-parallel KV sharding across 8 to 32 GPUs. Evaluation uses RULER, LongBench, Qasper and GSM8K, taken from the KVTC suite.

Failure model. Failures are injected mid-generation at random positions. Accuracy is measured on the remaining generation using the repaired cache. RULER's multi-hop tracing and aggregation tasks are the stress test, since RULER found that compression which preserves needle retrieval can still break these tasks.

Precision diagnostic. Alongside the language benchmarks we run the synthetic equality task of Every Bit Counts. It checks whether the Tier 0 boundary we choose sits above the reported cliff.

Metrics. We measure:

  • repair bytes moved;
  • p50 and p99 repair latency;
  • the slowdown of concurrent serving requests;
  • storage overhead;
  • task accuracy relative to the undamaged cache.

Decisive check 1: the latency–fidelity frontier. At matched storage overhead and accuracy within 1%, does our scheme reduce p99 repair latency against both the exact-coding baseline and the compressed backup, under jitter measured on the cluster? If not, the idea fails.

Decisive check 2: conditioning at low bit-width. At 4-bit Tier-1 storage, does the conditioned encoding matrix keep accuracy stable across responder subsets, where the random matrix degrades? This test bears directly on the precision part of the claim.

Decisive check 3: simulation versus silicon. Does the ranking of schemes produced by the discrete-event simulator match the ranking on hardware under serving load? We expect it to diverge. Exact codes with large fan-out should look better in simulation than on silicon, where repair traffic contends with decode-time memory bandwidth. We will quantify the gap with the same before-and-after gap metrics that Air Learning used for flight time and trajectory length.