# Incremental KV prefix cache

Reuse a conversation's KV up to its longest common prefix, prefill only the new suffix into the **same** buffer,
and hand that extended buffer to the next turn. This is what makes long agentic sessions flat-cost instead of
quadratic.

## Why it is not just "skip the prefix"

The KV for one shared `fused.State` is written by prompt **chunks**, and the original chunker sized chunks from the
**total prompt length**:

```
n = ceil(L0 / rows);  step = ceil(L0 / n)
```

So two requests whose prompts differ in length compute the *same* prefix rows with *different* chunk boundaries,
hence a different row count per chunk - and the kernels' tiling is a function of that row count. A resumed request
therefore inherited KV that a cold run of the current prompt would never have produced. The symptom was
intermittent, which is why it took a per-row provenance dump to localise: a passing case had `len(W) == len(P)` and
zero differing rows; a failing case had layer 0 identical and layers 39/77 diverging from position ~8.

## The two invariants

1. **Chunking is a function of position only.** A fixed grid of `prompt_rows` tokens plus a final remainder. Every
   boundary is a multiple of `prompt_rows`, independent of `L0`, so a prefix is always produced by the same tiling.
   This is the same reason vLLM uses a constant block size.
2. **Reuse is bounded by the canonical prefill frontier.** Generated tokens are **decode**-written, and decode bits
   are not prefill bits. Reuse is limited to
   `min(longest_common_prefix, canonical_end, len(prompt) - 1)`, where `canonical_end` is the previous request's
   **prompt** length. Without this, a reply that crosses a grid boundary (prompt 1020 + 10 generated -> rounds to
   1024) would reuse rows that decode wrote.

## Patch series

Applied in order by `apply.sh`. Each script refuses unless its anchor appears exactly once, and is dry-run by
default.

| # | Patch | What it does |
|---|---|---|
| 1 | `patch_01_prefill_offset.py` | `prefill(prompt, offset=0)` / `_prefill` / `generate(..., offset=0)`; chunks run over the absolute range |
| 2 | `patch_02_drafter_resume.py` | `Drafter.resume(position)`; move the drafter ring to the offset; report `stats["cached"]` |
| 3 | `patch_03_engine_wiring.py` | host record + offset decision in `engine._run`; `record(prompt + out[:-1])` |
| 4 | `patch_04_chunk_alignment.py` | run whole cold chunks; quantize the offset to a cold boundary |
| 5 | `patch_05_fixed_chunks.py` | the position-fixed grid (`TF_GLM53_FIXED_CHUNKS`) |
| 6 | `patch_06_finalize.py` | cache on by default; fixed chunks bound to it; conservative record length |
| 7 | `patch_07_canonical_end.py` | bound reuse at the canonical prefill frontier; hard-guard the binding |

`prefix_cache.py` is the module the patches install.

## Environment

| Variable | Default | Meaning |
|---|---|---|
| `TF_GLM53_PREFIX_CACHE` | `1` | enable the cache |
| `TF_GLM53_FIXED_CHUNKS` | follows the cache | position-fixed grid; forced on when the cache is on |

`TF_GLM53_PREFIX_CACHE=0` restores the byte-identical pre-cache path.

## Acceptance tests

Run these against a live lane. They are the tests that actually caught the bugs, including two of my own.

| Script | What it proves |
|---|---|
| `test_stress.py` | 8 alternating reused/cold pairs: the reused run must match the cold run |
| `test_semantic.py` | the reused reply answers the **current** prompt, not the previous turn's |
| `test_growth.py` | per-turn wall stays flat as the prompt grows (the O(n^2) is gone) |
| `test_agentic.py` | 4 tool-use tasks with per-turn assertions: schema-valid calls, read-before-write, no identical repeats, no swallowed errors, no false "tests pass" claims |

Baseline to beat: before this work, per-turn wall at 2.7k -> 15.9k context was 15.5 -> 85.3 s. After: 13.0 -> 19.4 s.

## Results

| Check | Result |
|---|---|
| Boundary matrix (LCP at a grid boundary +-0/1/2, exact repeat, shorter prompt) | 0/5 failures, 0 stale |
| Semantic stale-reuse (6 pairs) | 0/6 stale |
| Per-row KV provenance, cold vs resumed | 0/10 failures |
| Strict-acceptance stress (8 pairs) | 0/8 mismatches |
| Cold path with the cache off | `sha=e38c30fdc5e4`, bit-equal, unchanged |
| Decode speed | 55.7 / 69.2 / 73.6 tok/s vs 55.86 / 69.30 / 73.73 before - unchanged within noise |
| GSM8K | 96.7% vs 96.66% before |

## Known limits

- **One conversation is cached at a time.** The KV is a single shared full-capacity buffer (~15-20 GB at 1M), so a
  cache of N whole states is impossible on this hardware. Switching conversations forfeits the reuse.
- **One-chunk quantization loss.** Reuse rounds down to the grid, so up to `prompt_rows` tokens are re-prefilled per
  turn. A smaller grid would waste less but adds chunk overhead; measure before changing it.
- **`top2` acceptance means output can differ from cold at near-ties** even with identical KV. That is expected, not
  a defect - but it also means output hashes are a weak correctness test. Compare KV rows and logits when it
  matters.
- **Zero failures in ten trials is not proof of reliability.** It bounds the failure rate at roughly 26% at 95%
  confidence. The provenance and boundary tests are stronger evidence than pass counts.