# M4.5 — KV preemption on the regular decode path

> Follow-up to [`2026-05-07-m4-guidellm-canonical-stuck.md`](../experience/errors/2026-05-07-m4-guidellm-canonical-stuck.md).
> Closes the bench-gate hole that's blocking M3+M4 publishable numbers.
> **Net delta is tiny because the preemption infrastructure already exists**
> — M4.5 is a one-callsite hookup, not a from-scratch implementation.
>
> **Actual landed scope (2026-05-07, `763d6bb`)**: even narrower than this
> plan estimated. Codex's 9-line fix in `admission.rs` (skip waiting
> requests with closed `delta_tx`) + `scheduler_loop.rs` (drop slots whose
> client disconnected) addresses the SPECIFIC observed M4 stall — clients
> killed mid-bench, server didn't release their slots, deadlocked at
> `active=12 waiting=560`. The generic `retract_decode_to_fit` hookup
> proposed below in §1 was not necessary for the observed shape; defer it
> to a future plan if/when sustained-connected-clients hit the same
> deadlock. The bench gate is unblocked by the narrow fix alone.

## P0 finding (2026-05-07) — preemption is already built, just not wired

`grep -rn "retract\|victim" infer/src/scheduler/cuda/` exposes the
existing infrastructure:

| Symbol | File:line | Purpose |
|---|---|---|
| `retract_victim_score(generated_tokens, prompt_tokens)` | `decode.rs:12` | Score function — least-progressed wins, tie-break to longest prompt |
| `retract_victim_pos(decode_indices)` | `decode.rs:78` | Pick position in decode batch with the worst score |
| `Scheduler::retract_decode_to_fit(decode_indices, token_ids, extra_pages)` | `decode.rs:91` | Loop: while pool can't fit decode + extra_pages, pick victim, `requeue_preempted_decode`, remove from batch |
| `requeue_preempted_decode(slot_idx)` | `decode.rs:141` | Move victim's request back to waiting queue with checkpointed state |

**Existing call sites** of `retract_decode_to_fit`:

- `scheduler/cuda/spec_path.rs:95` — spec-verify path: reserves
  `extra_verifier_pages`, retracts decode if pool pressure forces it.
- `scheduler/cuda/spec_path.rs:343` — same, mixed-batch variant.

**What's missing**: the *regular* decode path (non-spec) does NOT call
`retract_decode_to_fit`. It only calls `alloc_pool_tokens_with_retry`,
which evicts un-referenced prefix-cache blocks but cannot preempt
active running requests.

That's why kv_util ≈ 99.8% with 12 active slots deadlocks: prefix-cache
is empty (active slots own everything), allocation fails, no preemption
fires, scheduler emits idle plans forever.

## 1. The fix

One callsite addition in the regular decode plan path. In
`scheduler/cuda/decode.rs` (or wherever `decode_indices` is finalised
before issuing the decode batch), call `retract_decode_to_fit` with
`extra_pages = 0` (no spec-verify reservation needed) when
`pool_free_pages() < decode_pages_needed(decode_indices)`.

Sketch (location TBD by codex; the exact insertion point depends on
`scheduler_loop.rs::step` plumbing):

```rust
// Before submitting the decode batch to the model:
self.retract_decode_to_fit(&mut decode_indices, &mut token_ids, /* extra_pages */ 0);
```

The retract loop already terminates when `decode_indices.len() <= 1`,
so it never empties the batch — at least one slot always advances. The
preempted slots' requests go back to the waiting queue and are picked
up on a future scheduler tick once their KV pages have been reused by
the survivors generating tokens (or by waiting requests that fit
better).

## 2. Tasks

| Task | File | LOC est. | Owner |
|---|---|---|---|
| P1. Add the `retract_decode_to_fit(..., 0)` call to the regular decode path. | `infer/src/scheduler/cuda/{decode.rs, scheduler_loop.rs}` | ~10 | Codex |
| P2. Repro test: drive scheduler to KV saturation with N concurrent long-output requests, assert `active=0 waiting=0` after client disconnect (the very deadlock shape from the M4 bench stall). | `infer/tests/scheduler_kv_pressure_drains.rs` (new) | ~120 | Claude |
| P3. Bench gate: re-run the M4 canonical guidellm sweep with `--max-seq-len 5120`. Expect drain to `active=0 waiting=0` after termination AND non-zero `benchmarks.json`. | `scripts/bench_guidellm.sh` invocation, no code change | 0 | Codex (remote) |
| P4. wins entry recording the line delta and the bench numbers (the first M3+M4 publishable bench data). | `docs/experience/wins/<date>-m4.5-kv-preemption.md` | one file | Claude |

**Total: ~130 LOC, 1.5 days.** Smaller than every other M-x in this
session because the heavy lifting (the preemption logic itself) was
already done in `decode.rs`.

## 3. Acceptance

- `cargo test --release -p infer --features cuda --test scheduler_kv_pressure_drains` passes (P2).
- `cargo test --release -p infer --features cuda --test e2e` still passes (no regression).
- `INFER_DETERMINISTIC=1 cargo test --release -p infer --features cuda --test greedy_consistency` still passes.
- `cargo test --release -p infer --features cuda --test spec_decode_correctness` still passes — `retract_decode_to_fit` already used by spec-verify, must keep working there.
- `scripts/bench_guidellm.sh cuda-m4.5-preemption --target http://localhost:8000 --model Qwen/Qwen3-4B --processor infer/models/Qwen3-4B` produces a non-zero `benchmarks.json`, AND `/v1/stats` reports `active=0 waiting=0` after clients exit.
- Service stats show non-zero `decode_rows` plan labels under sustained load (vs the all-`idle=242807` from the stuck run).

## 4. Risks + retreat

- **R1 — Preemption thrash**: under saturated load, every tick
  preempts a different victim, no request finishes. Mitigation:
  `retract_victim_score` already weights generated_tokens vs
  prompt_tokens to bias against finished-soon requests; the existing
  spec-verify call site has not reported thrash, so the regular path
  shouldn't either. If it does, add a "preempted recently" flag with
  a cooldown.
- **R2 — Preempted request loses generated tokens**: by design,
  `requeue_preempted_decode` requeues with `generated_tokens` retained
  in `request.generated_tokens` (not lost). The cost on resume is the
  prefill of the original prompt + already-generated tokens;
  prefix-cache hits should reduce that to mostly the regenerated tail.
  Worst case: wasted work proportional to current generation depth.
- **R3 — Deadlock survives**: P1's retract loop terminates when
  `decode_indices.len() <= 1`. If even ONE slot needs more pages than
  the pool can hold (single-request OOM), the deadlock recurs.
  Mitigation: that's a real OOM, surface it as an error to the client
  rather than silently retain the slot. P1 includes that error path.

## 5. Out of scope

- T1/T2 KV swap-out (SGLang `--preempt-mode=swap-out`). Future work
  once Tier-KV M_d Q1 lands and the M2 metal kv-tier adapter has a
  symmetric CUDA equivalent that supports KV demotion.
- Multi-tier preemption priority. Current single-tier (preempt
  least-progressed) suffices for the bench gate; multi-tier is a perf
  optimization, not a correctness fix.
- Spec-decode interactions with preemption. Spec-verify already calls
  `retract_decode_to_fit` itself; nothing changes for it.

## 6. References

- Errors entry that motivated this:
  [`2026-05-07-m4-guidellm-canonical-stuck.md`](../experience/errors/2026-05-07-m4-guidellm-canonical-stuck.md)
- Prior art (the existing victim infra): `infer/src/scheduler/cuda/decode.rs:12-150`
- The 2026-04-13 errors entry's historical note about
  "least-progressed victim, tie-break longest prompt" policy —
  the score function in `retract_victim_score` matches.
- vLLM preemption: `vllm/core/scheduler.py::_preempt`
- SGLang preemption mode: `--preempt-mode swap-out|recompute`
