Prefix Integrity Analysis

A contract check, not a leaderboard

A compression paper usually reports one curve: compression ratio against model accuracy. That curve hides the failure that breaks a serving stack. An algorithm can leave accuracy untouched on the prompt it was measured on, and still rewrite the shared prefix into something a prefix-cache or offload store can no longer reuse. The damage is invisible on the accuracy plot because accuracy was never the property at risk — the property at risk is the cache contract.

Prefix caching means two requests with the same prefix reuse the same KV blocks. KV offloading means those blocks get written once and read back later, possibly on another machine. Both rest on a quiet assumption: the prefix maps to a stable, reloadable object that does not depend on which request happens to arrive next. An algorithm that quietly makes the stored prefix depend on the query, or change shape, or drop the system-prompt block, breaks that assumption while the accuracy number looks fine.

Two axes, judged separately

An algorithm can fail in two unrelated ways, and the harness keeps them apart so a single number never hides one behind the other.

A clean contract with bad drift, or clean drift with a broken contract, are both real failures — and they are different failures with different fixes. The verdict reports both: a PASS / WARN / FAIL status, a danger score, and one of five plain-language classifications.

Staged validation, cheapest filter first

The two axes are run as stages, not all at once, so a method that fails the cheap check never burns a GPU. Each stage is a gate: only what survives moves on. The whole point is that the early stages are almost free, because they run over a Cartridge — a deterministic, prefix-only KV artifact from our routing work that behaves exactly like a shared prefix cache — instead of a live serving stack.

The five verdicts

How it works

The harness uses a Cartridge as a deterministic stand-in for a prefix-cached or offloaded KV object. A cartridge is a fixed, precomputed KV cache with stable block boundaries, so it is a cheap, reproducible prefix you can run an algorithm against without rerunning prefill. It does not require LMCache or distributed serving — the cartridge is the offload emulator.

Every algorithm enters through one narrow slot — an adapter — so the harness never needs to know whether the thing is KRI, a quantizer, an eviction policy, or a clustering scheme. It only sees the manifest and the transformed tensors. The adapter also declares what the algorithm claims about itself: its policy (prefix cache, routing, or offload codec) and which fields it puts in its cache key. The verdict is the collision between what the algorithm claims and what it actually does.

To expose that collision, the harness replays the algorithm across many suffix or query requests that all share the same prefix hash, repeating each request to separate non-determinism from query-dependence. A selection that changes when you re-run the same query is broken. A selection that changes across different queries is query-aware — fine for routing, dangerous for a prefix cache keyed by prefix alone.

What gets measured

The first end-to-end run

A100 80GB · Qwen2.5-7B-Instruct · citation-check cartridge (4096 tokens, 256 blocks) · 16 queries · 2026-06-30

Six configurations went through the drift module and the contract verdict: two identity checks, two block selectors at a tight sixteen-block budget, and two KV codecs. The identity checks came back exactly zero — keeping every block, or applying the no-op codec, gave a KL of zero and full top-1 agreement on every query. That confirms the attention masking and the pinned query positions are exact, so any drift elsewhere belongs to the algorithm and not to the harness.

Selectors ran at a sixteen-of-256-block budget; the codecs here are per-tensor round-trips, a deliberately naive lower bound. The asymmetric extension — K16/V8 and friends, with fair per-channel key and per-token value scaling, and bytes accounted — is its own run in Quantization on the same axes below. Full data, reports, and the run log are archived in knlp-key-results/prefix-integrity-20260630/.

Ten methods off the leaderboard

The reference adapters prove the harness works. The real question is what it says about methods people actually deploy. We took ten off the KVPress leaderboard and their papers — StreamingLLM, Knorm, SnapKV, Expected Attention, TOVA, H2O, PyramidKV, plus Quest, Ada-KV, and KIVI — and ran each through the same slot. Each method is classified by its design: whether it keeps whole blocks or scattered tokens, whether the kept set depends on the query, whether heads disagree, and whether it changes the tensor layout. Those are facts about the method, not about any one prompt, so the contract axis settles them on a CPU.

One method — StreamingLLM, the only purely positional one — is a clean prefix-cache citizen. Everything adaptive picked a different block set for all sixteen queries, so under a prefix-only key it lands DANGEROUS_FOR_PREFIX_SHARING. That is not a knock on the methods; it says they are routers, not prefix-cache-safe compressors. Put the query hash in the cache key and the same six move to SAFE_ONLY_WITH_EXTENDED_CACHE_KEY. KIVI and Knorm are query-independent but change the layout — a dtype change, or per-head scattered tokens that leave half the blocks partial — so they need a custom connector, not plain block-hash reuse. Quest keeps the whole prefix and only routes reads, so it is honestly a router and labeled as one.

Measured drift — the two axes disagree

A100 80GB · Qwen2.5-7B-Instruct · KVPress presses · 5662-token context, keep ~25%

The contract axis above is design-derived. To fill the other axis with real numbers we installed KVPress and ran its actual presses on an A100: for each method, compress the KV of a long context, then measure how far the model's next-token distribution moves from the uncompressed baseline. This is the same drift the reference run measured with fp8/int8, now from the real methods.

The reason to measure both axes is still the point: a quality leaderboard ranks SnapKV at the top and would send it to production, while the contract axis shows it is a router, not a prefix-cache-safe compressor, so under a prefix-only key it would corrupt a shared prefix. Whether the safe-looking positional method must buy that safety with accuracy is what the next experiment settles. The right choice depends on which axis binds — and you only see both if you measure both.

Compression here is query-independent (the question is appended after compression), so this isolates each method's intrinsic quality loss; the query-dependence that drives the contract verdict is a design property, measured separately. Four-probe needle set, one budget; KL is the robust signal. PyramidKV and Ada-KV hit KVPress API mismatches on this build and are design-classified only. Data in prefix-integrity-20260630/kvpress_drift/.

The decisive test — reusing a compressed prefix across queries

A100 80GB · W7900 · Qwen2.5-7B-Instruct · 4096 and 16384-token shared prefixes · 6 prefixes each

The drift table above compressed each prefix without a query, so it could not show the thing that actually makes an adaptive method unsafe to share: its compressed cache depends on which question you asked. This test runs that directly. One long prefix holds several planted facts; we build a method's compressed cache and then reuse it across different questions under a prefix-only key — exactly what a prefix cache does when two requests share the same opening context. We score only the facts the uncompressed model can actually answer, so a compressed method is judged on real retrieval, not on the model's own confusion.

A query-aware method (keep the tokens the question attends to, SnapKV-shaped) is measured two ways. Honest selects using the current question — the method deployed correctly, with the question inside the cache key. Unsafe reuse builds the cache from the first question and reuses that same prefix-only artifact for every later question. A positional method (a sink plus a recent window, StreamingLLM-shaped) never looks at the question, so its one cache serves every query identically.

Deployed correctly, the query-aware method climbs toward the dense baseline as the budget grows — 0.28, then 0.76, then 0.93. But reusing that same cache across questions stays at roughly half of that at every budget: it kept the first question's fact, not the current one's. The overlap between the token sets different questions want to keep is only about a third to a half, which is both why the harness flags it dangerous and why the reuse collapses.

The positional method is the mirror image. Every question keeps the same tokens, so its cache is perfectly reusable — but at these budgets a sink plus a recent window never reaches the old middle where the facts sit, so it answers nothing. One method is high quality only when the cache key carries its question; the other keeps full reuse but cannot serve the question at an aggressive budget. That trade — quality bought with cache reuse — is exactly what the contract axis predicted from the design alone, now confirmed by running it.

Running the same replay at four times the context shows the trade is a property of the selection, not of length — and the cost of reuse grows with it. A cheaper q·k selector recomputes the same observation-window signal one layer at a time and reaches 16384 tokens, where the full attention tensor will not fit. At matched budgets the honestly deployed method climbs while the reused artifact falls further behind.

At 16K the honest method reaches the dense baseline by a quarter budget (1.00), but the prefix-only reuse tops out at 0.33 — a three-fold gap where 4096 tokens showed less than two. Longer shared context makes an adaptive method's cache both more valuable to reuse and more wrong to reuse, at once. The kept-set overlap stays near a half, so the harness flags the same danger at either length.

The 4096-token rows read full attention directly; the 16384-token rows use a q·k selector that recomputes the observation-window score from one layer's inputs at a time, so only a [heads, obs, T] slice is ever resident and the forward runs with memory-efficient attention. A parity check against the full-attention selector at 2048 tokens matches its kept sets (Jaccard 0.86) and its answer accuracy. The positional row is a floor, not a tuned StreamingLLM. Single model. Getting the 4096 result to hold took a validated masking path, distinct non-interfering facts, a normalized scorer, and a sink-aware selector. Data and plot in prefix-integrity-20260630/pia-reuse-replay/ and pia-reuse-replay-16k-*.

Same story in a tiered cache — a kill-test

A100 80GB · Qwen2.5-7B-Instruct · 128-token blocks · keep 7 of 28 blocks

The reuse replay above is about a prefix cache. The same question comes up for a tiered cache that keeps a few old blocks in fast memory and spills the rest: which blocks do you keep? One proposed answer was a query-independent magnitude score (sum the keys and values in a block, keep the biggest). If that worked you could route without knowing the question. This run tests it directly. Facts are planted one per old block; each question needs a different block; a method keeps the protected first block, a small recent window, and three old blocks of its choosing. Success is keeping the block that holds the answer and then answering. We score only the facts that sit in a genuine old block, since a fact in the recent window is kept by everyone and tests nothing.

The answer block is fully selectable — the oracle gets it every time — and the query-aware score matches it. The magnitude score gets none of it, below even random, because it must commit to the same three old blocks for twenty different questions. Key magnitude is actually anti-informative here; value magnitude carries a little salience because the planted facts are conspicuous sentences, but it is capped for the same reason. It is the reuse replay's lesson in a different cache: a routing decision that ignores the question cannot serve many questions from one shared context, and the win that survives is query-aware. Details and the decision rule are in prefix-integrity-20260630/kri-tierkv-killtest/.

Quantization on the same axes — asymmetric KV codecs

A100 80GB · Qwen2.5-7B-Instruct · 4096-token cartridge · 48 queries

Selection is one way to shrink a KV cache; quantization is the other. A quantization codec is query-independent — it round-trips every block the same way regardless of the question — so on the contract axis it is safe to share, needing only a codec-aware connector for its non-standard dtype. That is the same query-independence that made a selector useless, turned into a virtue: a codec never has to guess which block the question wants, because it keeps them all, in fewer bits. This table puts codecs and block selectors on PIA's axes together, with bytes made explicit, and folds in the asymmetric K16/V8 quantization from the decode work — keep the fragile keys at 16 bits, compress the tolerant values.

Scale granularity decides this measurement, so fix it first. A single per-tensor scale on post-RoPE keys manufactures key fragility: the keys carry per-channel outliers, and a global scale clips them. Scale keys per-channel and values per-token — the standard granularity — and keep the crude per-tensor codecs only as a labeled stress control. Count bytes including the scale metadata.

At the same byte budget and the same contract safety, quantizing every block beats dropping whole blocks by one to two orders of magnitude on drift — K16/V8 at 0.75 bytes moves the distribution 48× less than a positional selector spending the same bytes, because evicting a quarter of the prefix throws away middle blocks a question needed, while quantization keeps them all approximately. That is a Pareto point selection cannot reach: it is why the deployed asymmetric serving stack quantizes the shared prefix rather than selecting over it.

The key-vs-value asymmetry survives, but honestly. Once keys are scaled per-channel the naive “keys die at 8 bits” effect mostly disappears (KL 0.079 → 0.009, a 9× rescue); what remains is a real but modest edge — quantizing keys still drifts about twice as much as quantizing values and is the only 8-bit arm to drop top-1 below one. The catastrophe is reserved for fp8 with a coarse scale, which reproduces the decode key-fp8 collapse and is the loudest warning in the table. Data in prefix-integrity-20260630/asym-codec-table/.

What the run shows

Run it

Run the stages in order. Stage 1 needs no GPU; stage 2 does. Screen on stage 1 first, and only spend the GPU on what survives.

Block survival, determinism, cache-key safety, and storage geometry. Pure bookkeeping over the block manifest — no weights are loaded, so it runs anywhere. Most methods that are unsafe to share fail here.

python -m routing.prefix_integrity.cli validate \
  --cartridge /path/to/cartridge_dir \
  --algorithm query_aware \
  --queries queries.jsonl \
  --budgets 8,16,32 --pins A1R2K13 \
  --out /path/to/report_dir

Loads a model over the cartridge and measures how far the candidate moves the next-token distribution. The query positions are pinned to the original prefix offset, so drift reflects the algorithm rather than re-indexing. Fold its output back into the verdict with --semantic-json. This step and everything below it require a GPU.

python -m routing.prefix_integrity.semantic_drift \
  --model Qwen/Qwen2.5-7B-Instruct \
  --cartridge /path/to/cartridge_dir \
  --queries queries.jsonl \
  --algorithm query_aware --mode selector --budget-k 16 \
  --out semantic.json

The byte-aware codec table on this page is the same GPU drift path swept over codecs and byte-matched selectors. Building a cartridge prefills a model, so it needs a GPU too:

python experiments/pia_build_cartridge.py \
  --model Qwen/Qwen2.5-7B-Instruct \
  --target-tokens 4096 --out-dir cart
bash experiments/pia_codec_table.sh   # none/int8/fp8 + k16v8, k8v16, k16v4, ...

The decisive same-prefix, many-query reuse replay picks its query-aware scorer with --selector: attn reads full attention (up to ~4K), qk uses the cheap q·k path that scales to 16–32K. pia_qk_parity.py checks the two agree where both fit.

python experiments/pia_reuse_replay.py \
  --model Qwen/Qwen2.5-7B-Instruct \
  --context-len 16384 --selector qk \
  --keep-ratio 0.15 --output-dir reuse16k
python experiments/pia_qk_parity.py # qk vs full-attention selector

A new algorithm enters by implementing select_blocks for a selector, a transform step for a codec, or both — loaded from a package.module:factory spec. It declares its policy and cache-key fields, and the harness checks those claims against what it observes. Built-in adapters (full, recency, random, anchor+recency, A1R2K13, an offline KRI prior, and the query-aware selector) stand as known-good and known-dangerous references.

Where it sits