Preemption starvation under sustained KV overload: recompute-mode limitations and potential mitigations

[sriumcp]

Context

While investigating the Phase 1 livelock bug (#349, fixed in #519), we discovered a second, deeper problem: under sustained KV overload, recompute-mode preemption causes complete starvation — no request ever completes because every request is preempted before finishing decode, loses all progress, and restarts from scratch.

This is not a bug — it is a faithful reproduction of real vLLM v1 behavior. Both systems exhibit identical starvation under the same conditions. This discussion explores the mechanism, validates BLIS fidelity, and considers potential mitigations.

The Reproducer

./blis run \
  --model meta-llama/llama-3.1-8b-instruct --hardware H100 --tp 1 \
  --total-kv-blocks 7463 --block-size-in-tokens 16 \
  --max-num-running-reqs 256 --max-num-scheduled-tokens 2048 \
  --num-requests 300 --rate 10.0 --seed 7 \
  --prompt-tokens 300 --prompt-tokens-stdev 200 --prompt-tokens-min 200 --prompt-tokens-max 400 \
  --output-tokens 3500 --output-tokens-stdev 3200 --output-tokens-min 3200 --output-tokens-max 3596 \
  --alpha-coeffs 232.46,1.75,3357.44 --beta-coeffs 5752.71,17.25,6.00

Result: 0 completed requests, 9,599 preemptions over 120s. Each request needs ~237 KV blocks at peak; 7,463 total blocks support ~31 concurrent. At rate=10/s, 300 requests arrive in 30s — a 6.5x overload on sustained throughput capacity (~1.55 completions/s).

BLIS vs vLLM v1: Side-by-Side Comparison

We traced the vLLM v1 scheduler (vllm/v1/core/sched/scheduler.py) to verify that BLIS matches. Every relevant mechanism is identical:

Mechanism	vLLM v1	BLIS	Match?
Preemption mode	Recompute only — num_computed_tokens = 0, all KV blocks freed	Recompute only — ProgressIndex = 0, all KV blocks freed	Yes
Eviction victim (FCFS)	self.running.pop() — youngest request (LIFO from tail)	RunningBatch.Requests[len-1] — youngest request (tail)	Yes
Re-entry position	self.waiting.prepend_request(request) — front of queue	WaitQ.PrependFront(request) — front of queue	Yes
Phase 2 after preemption	if not preempted_reqs: — waiting queue skipped entirely	!result.PreemptionHappened — waiting queue skipped entirely	Yes
Anti-starvation	None — num_preemptions tracked for metrics only, never used for scheduling priority	None	Yes
Swap mode (CPU offload)	Not supported in v1 (was in v0)	Not supported	Yes
Prefix cache salvage	Possible — freed blocks retain block_hash, get_computed_blocks() finds them on re-schedule	Possible — GetCachedBlocks() checks hash table on re-admission	Yes

Conclusion: BLIS preemption physics is faithful to vLLM v1. The starvation is not a BLIS-specific problem — it is an inherent limitation of recompute-mode preemption under sustained overload.

Why Starvation Occurs

1. Admission phase: Requests enter the running batch, consuming KV blocks for prefill (~13-25 blocks each).
2. Decode phase: Each decode step allocates 1 additional KV block per 16 output tokens. Over 3,200-3,596 output tokens, each request grows from ~25 blocks to ~237 blocks.
3. Pressure builds: As running requests grow, KV fills. New requests need blocks, so Phase 1 evicts the tail (youngest running request).
4. Progress lost: The evicted request has ProgressIndex = 0 — all decode progress (potentially thousands of tokens) is discarded.
5. Re-entry: The evicted request goes to the front of the wait queue and will be re-admitted in a future step... where the same cycle repeats.

The fundamental problem: each completion requires ~3,400 uninterrupted decode steps (~20s). But under 6.5x overload, no request can hold its KV blocks long enough to finish decode before being evicted.

Potential Mitigations

These are options to explore, not proposals. Each has tradeoffs:

1. Swap-mode preemption (CPU offload)

vLLM v0 supported PreemptionMode.SWAP — offload KV blocks to CPU memory, preserving progress. BLIS already has TieredKVCache with CPU offload infrastructure.

Pro: Preempted requests preserve progress.
Con: CPU-to-GPU transfer latency. Under severe overload, swap space also fills up. vLLM v1 deliberately dropped swap for simplicity.

2. Anti-starvation priority boost

Track num_preemptions per request. After N preemptions, boost scheduling priority to prevent re-eviction.

Pro: Simple. Guarantees forward progress.
Con: Boosted requests block new admissions indefinitely under severe overload.

3. Admission backpressure

When preemption rate exceeds a threshold, reject new requests or reduce admission rate.

Pro: Addresses root cause (more work than capacity). Matches real-world load shedding.
Con: Requires admission policy integration.

4. Progress-aware eviction

Instead of LIFO (youngest), evict the request with the least decode progress.

Pro: Requests close to completion are protected. Reduces wasted computation.
Con: Inverts fairness — newer requests are always evicted first.

5. Partial progress preservation (without swap)

On preemption, keep ProgressIndex and rely on prefix cache to reconstruct KV blocks on re-admission. Block hashes survive preemption in both vLLM and BLIS.

Pro: Zero CPU memory cost. Leverages existing prefix cache.
Con: Under severe pressure, freed blocks are immediately reallocated — prefix cache salvage is unlikely.

Related Issues

• bug: Phase 1 range loop visits evicted requests, causing cascading preemption livelock under KV pressure #349 — Phase 1 range loop livelock (fixed in fix(batch): replace range loop with index-based iteration to prevent Phase 1 livelock #519)
• design: generalize BatchContext/BatchResult for multi-engine support (R13) #518 — BatchContext/BatchResult R13 generalization for multi-engine support
• fix(sim): prevent KV livelock when request exceeds cache capacity (#373) #386 — KV livelock variant 1 (unservable request rejection)

Questions for Discussion

1. Is starvation under 6.5x overload a scenario users care about? If BLIS is used for capacity planning, "0 completions at this rate" is the correct answer — scale up.

2. Should BLIS match vLLM v1 exactly? Or should it explore mitigations as a research/what-if tool?

3. Would swap-mode preemption leverage the existing tiered KV cache? TieredKVCache already has CPU-tier infrastructure.

4. Is progress-aware eviction worth a hypothesis experiment? Test whether "evict least progress" beats "evict youngest" under sustained KV pressure.

[sriumcp]

Update: Over-Admission Is the Root Cause, Not Recompute-Mode Preemption

Further investigation reveals the starvation is not inherent to recompute-mode preemption — it is caused by over-admission. The scheduler admits requests based on their prefill block cost but does not account for their eventual decode block cost. This is identical in both vLLM v1 and BLIS.

The Mechanism

Phase	Blocks per request	Max concurrent (7,463 blocks)
Prefill (admission time)	~19 blocks (300 input tokens / 16)	392 requests
Full decode (completion time)	~232 blocks (3,700 total tokens / 16)	32 requests

With max_num_seqs=256 (vLLM default for large GPUs) or --max-num-running-reqs=256 (BLIS), the scheduler admits all 50 spike requests because they only need 50 x 19 = 950 blocks for prefill (well under 7,463). But as they decode, they collectively grow to 50 x 232 = 11,600 blocks — 56% over capacity. Preemption becomes inevitable, and with recompute mode, preempted requests lose all decode progress and restart from scratch.

Experimental Proof

We ran four configurations — varying spike vs sustained load and max-running-reqs:

Scenario	max_running_reqs	Completed	Preemptions	Throughput
300 req @ rate=10/s	256 (over-admitted)	0	9,599	0.0 req/s
50-request spike	256 (over-admitted)	0	9,217	0.0 req/s
50-request spike	32 (right-sized)	50	0	1.17 req/s
300 req @ rate=10/s	32 (right-sized)	161	0	1.34 req/s

Key finding: With max_num_running_reqs=32 (matching KV capacity at full decode), both the spike AND sustained overload scenarios produce zero preemptions. The batch size limit prevents over-admission. Requests wait in the queue instead of being admitted, growing, and getting preempted.

The 300-request sustained case completes 161/300 in 120s at 1.34 req/s — this is the correct capacity planning answer (the system is overloaded, ~139 requests do not finish within the horizon). The 50-request spike completes all 50 in ~43s.

vLLM Has the Same Problem

vLLM v1 has the same over-admission pattern:

1. Admission (scheduler.py line 1080): allocate_slots() checks if blocks are available NOW for the next chunk of tokens — not whether blocks will be available when the request finishes decode.

2. max_num_seqs (scheduler.py line 301): self.max_num_running_reqs = self.scheduler_config.max_num_seqs — this is the only batch size cap. Default is 128. Operators must tune it for their GPU memory, but there is no guidance tying it to expected output length.

3. No projected-capacity check: Neither vLLM nor BLIS estimates blocks_at_completion = ceil((input_tokens + expected_output_tokens) / block_size) and compares against total KV capacity before admission. Both admit greedily based on current availability.

In real vLLM deployments, this works because:

• Operators set max_num_seqs based on experience (typically 32-128 for 80GB GPUs)
• Output lengths are usually shorter (chat: ~200 tokens, not 3,400)
• The problem only manifests with long-output workloads AND high max_num_seqs

What BLIS Could Do That vLLM Does Not

These are potential BLIS enhancements that could upstream to vLLM:

1. Auto-compute max_num_running_reqs from workload characteristics

safe_limit = total_kv_blocks / ceil((mean_input + mean_output) / block_size)
effective_max = min(user_provided_max, safe_limit)

When the user provides --output-tokens (or a workload spec with output distributions), BLIS knows the expected output length. It could warn or auto-cap:

WARN: --max-num-running-reqs=256 exceeds KV-safe limit of 32 for this workload
      (7463 blocks / 232 blocks per request at full decode).
      Reducing to 32 to prevent preemption starvation.

vLLM cannot easily do this because it does not know the output length in advance (it depends on the model generation). BLIS has the advantage of knowing the workload spec upfront.

2. Projected-capacity admission check

Before admitting a request from the wait queue in Phase 2, estimate its total block cost at completion and check whether the running batch projected total exceeds capacity:

projected_total = sum(projected_blocks(r) for r in running) + projected_blocks(candidate)
if projected_total > total_kv_blocks:
    break  // don't admit

This is a speculative check (actual output length may vary), but for BLIS where output lengths are pre-specified, it would be exact. For vLLM, it could use max_tokens from the request as an upper bound.

3. Preemption-rate monitoring with admission backpressure

Track a rolling preemption rate. When it exceeds a threshold (e.g., >1 preemption per step for 10 consecutive steps), temporarily reduce max_num_running_reqs to the current running count minus 1. This creates self-regulating feedback:

• High preemption rate -> reduce batch size -> fewer admissions -> pressure drops -> preemption rate falls -> batch size gradually recovers

This is the most "production-ready" mitigation because it does not require knowing output lengths in advance and could apply directly to vLLM.

Updated Comparison Table

Mechanism	vLLM v1	BLIS (current)	BLIS (potential)
Admission check	Current blocks only	Current blocks only	Projected blocks at completion
Batch size limit	max_num_seqs (operator-tuned)	max_num_running_reqs (operator-tuned)	Auto-computed from workload spec
Preemption feedback	None	None	Adaptive batch size from preemption rate
Output length known?	No (model generates)	Yes (workload spec)	--

Revised Questions

The original discussion framed this as a recompute-vs-swap problem. The real framing is admission control:

1. Should BLIS auto-compute max_num_running_reqs? It has the information (output length from workload spec). vLLM does not. This would be a BLIS-specific advantage for capacity planning accuracy.

2. Should BLIS implement projected-capacity admission? This is the most principled fix — admit only what KV can sustain through completion. It could be prototyped in BLIS and proposed upstream to vLLM (using max_tokens as the projection bound).

3. Is adaptive batch-size feedback worth a hypothesis experiment? This is engine-agnostic and could land in both BLIS and vLLM. The hypothesis: "Under sustained KV pressure, reducing max_num_running_reqs proportional to preemption rate should eliminate starvation while maintaining >90% of throughput at the reduced batch size."