DEP: Versioned vLLM scheduler fidelity and soak testing in mocker [DYN-3299]

[PeaBrane]

Summary

Establish a versioned fidelity contract between Dynamo mocker's vLLM model and the upstream vLLM scheduler, then continuously validate that contract with deterministic CPU-only regressions and longer seeded soak tests.

The first concrete correction is to eliminate “partial allocation plus ordinary waiting.” One ordinary MoveBlock::Use is a synchronous plan/reserve/commit transaction: it either commits the complete requested allocation or leaves request ownership, cache visibility, sequence accounting, and emitted effects unchanged. Typed outcomes distinguish capacity exhaustion from an asynchronous offload dependency so the scheduler preempts only for the former. Intentional persistent ownership, such as a disaggregated handoff reservation, remains an explicit lifecycle outside ordinary Use.

Related scopes are tracked separately:

• #11015 owns replay-level liveness classification and diagnostics.
• #10736 owns explicit disaggregated handoff source/destination ownership.
• #11018 owns causal settlement of asynchronous KVBM pipelines.

Motivation

A high-soak Dynamo mocker replay using a Mooncake-backed, disaggregated vLLM/KV-router configuration independently exposed a scheduler dead-end:

1. A waiting request acquired some G1 blocks during admission.
2. A later allocation in the same attempt required asynchronous G1 offload.
3. The partial allocation was committed and the result was treated as ordinary capacity exhaustion.
4. Running requests were preempted and prepended ahead of the partially owning request.
5. The new queue head could not reacquire enough capacity because a non-head waiting request retained active blocks.
6. Eventually workers were idle and requests remained unfinished, but no transfer, event, deadline, or runnable request could make progress.

Only after isolating that ownership path did we compare it with current upstream vLLM and find that vLLM had recently fixed a closely related liveness class in vllm-project/vllm#44560. That upstream failure also involved non-running async KV owners consuming capacity needed by another request to finish. The implementation paths are not identical, but the invariant is the same: a request that cannot make forward progress must not silently consume capacity required by the request ahead of it.

This was almost entirely an independent discovery during a high-soak mocker test. Coincidentally finding the same class of problem that upstream vLLM had just addressed is evidence that a faithful, aggressively asserted mock scheduler can be an early-warning tool—not only a performance estimator. Today that value is limited by semantic drift: upstream vLLM preflights ordinary allocations and uses explicit state plus reservation accounting for intentional async KV ownership, while mocker can currently commit a partial ordinary allocation before returning blocked.

Proposal

1. Define a versioned fidelity contract

For every supported vLLM release or pinned commit, document the observable scheduler semantics that mocker models:

• waiting, running, preempted, and async-KV-blocked request states;
• ordinary KV allocation prepare, commit, and abort rules;
• preemption victim selection and ownership release;
• prefix-cache reference behavior;
• chunked-prefill and full-ISL admission;
• asynchronous KV load/offload ownership, reservations, completion, and failure;
• queue ordering and head-of-line behavior.

Document intentional deviations explicitly. Updating the modeled vLLM version must update this contract and its conformance tests.

2. Make ordinary allocation transactional

Implement one MoveBlock::Use as a synchronous plan/reserve/commit transaction. prepare_use pins existing hits and reserves every fresh slot without installing cache entries, registering blocks, publishing Stored, or advancing sequence allocation/computed state. commit_use consumes a complete prepared transaction and infallibly makes all effects visible in order.

Return a typed outcome equivalent to:

• Ready(UseTransaction);
• CapacityExhausted;
• BlockedOnOffload { deadline };
• RetryNow for a synchronous state-changing completion such as presence filtering.

Dropping an uncommitted plan must leave all of the following unchanged:

• active request references and physical ownership;
• inactive/reusable cache entries and prefix-cache credit;
• block registration and Stored/Removed effects;
• num_allocated_tokens, computed-token state, and related sequence metadata;
• ownership that existed before the attempt.

Do not implement failed-attempt cleanup with compensating Deref or sequence reset. Once a fresh block is registered or published, compensation can leave an inactive reusable block and phantom cache credit for data that no forward pass computed. Visibility begins only at successful commit.

CapacityExhausted may trigger normal preemption followed by a clean retry. BlockedOnOffload must not preempt unrelated running work; the request remains at its prior ownership and is retried from its concrete dependency. RetryNow must be bounded by evidence of a state-changing synchronous completion and cannot become a same-state spin. Ordinary decode and speculative decode consume the same typed contract.

The offload engine may continue holding its explicitly tracked G1 source slots until transfer completion. Those holds belong to the transfer lifecycle, not silently to the blocked request.

3. Preserve explicit asynchronous ownership

Some paths intentionally reserve destination blocks while remote KV is loading. Those paths are lifecycle objects defined by #10736 and must not be rolled back as failed ordinary allocation. They provide:

• an explicit blocked request state;
• an explicit owner for every held block;
• remaining-footprint reservation accounting that prevents a later async load from consuming capacity an earlier in-flight request needs;
• a concrete completion/error notification;
• cleanup on cancellation, failure, and preemption.

This follows the model implemented by upstream vLLM in vllm-project/vllm#44560 rather than the closed lateral-preemption alternative in #40968. KVBM's separate external-clock settlement gap is tracked in #11018.

4. Add liveness and ownership invariants

At scheduler boundaries, assert that:

• every active physical block and logical reference reconciles to a request, cache entry, destination reservation, or in-flight transfer source hold;
• ordinary waiting requests do not retain allocations created by a failed admission attempt;
• every scheduler-blocked request has an explicit dependency or lifecycle owner;
• capacity release and reservation accounting use checked arithmetic.

Failure reports should identify request ID, block ID, owner class, request state, and the last ownership transition without requiring broad debug-log flooding. Replay-wide wakeup classification belongs to #11015.

5. Build a scheduler conformance and soak suite

Create two layers:

Deterministic conformance tests

• Port the observable scenarios from relevant upstream vLLM scheduler regressions.
• Cover low-capacity pools, shared prefixes, chunked prefill, preemption, async KV loads, KVBM G1→G2 offload, disaggregated prefill/decode, cancellation, and transfer failures.
• A blocked fresh Use is invisible until commit: no active-ref delta, reusable cache hit, prefix credit, registration, Stored event, or sequence-state change.
• Presence-filtered eviction produces one bounded immediate retry without a synthetic deadline or unrelated preemption.
• Ordinary decode waits without premature token emission or unrelated preemption, then resumes after its dependency.
• Speculative decode reserves its full burst footprint through the same typed contract.
• Dynamo adapters preserve exact Stored/Removed timing for committed neutral cache effects.

Seeded CPU-only soaks

• Run thousands of scheduler transitions across a matrix of small block pools, prompt/output lengths, arrival orders, batch sizes, prefix overlap, concurrency limits, transfer timings, and failure injection.
• Continuously check ownership, capacity, transfer-bijection, and liveness invariants.
• Persist the seed and a compact structured trace on failure.
• Minimize failing traces into deterministic regression cases where practical.
• Run a bounded seed set in pull requests and a larger scheduled/nightly matrix.

Where feasible, drive the equivalent upstream vLLM CPU scheduler fixture with the same abstract workload and compare observable decisions and ownership—not wall-clock or GPU kernel timing.

6. Track upstream scheduler changes

Monitor upstream vLLM scheduler, KV cache manager, request-state, and connector changes. A modeled-version update should include:

• an upstream diff review;
• fidelity-contract updates;
• imported or adapted upstream regressions;
• a deterministic conformance run;
• the extended soak matrix.

Alternate Solutions

Fix only this deadlock

Transactional allocation is required for the immediate bug, but a one-off patch does not prevent future semantic drift or demonstrate that the mocker remains a trustworthy early-warning tool.

Reorder the queue or laterally preempt a waiting owner

This can break a specific cycle while preserving ambiguous ownership. Upstream considered lateral preemption in vllm-project/vllm#40968 and instead merged reservation-based admission in vllm-project/vllm#44560.

Add a replay timing barrier, sleep, or synthetic virtual-time advance

Timing changes may hide the dead-end but do not repair ownership or capacity accounting. They also risk reintroducing same-timestamp livelock.

Rely only on real-engine GPU soak tests

Real-engine tests remain necessary, but they are more expensive, less deterministic, and provide less visibility into block ownership transitions. CPU mock soaks should catch scheduler/accounting failures earlier and produce smaller reproductions.

Requirements

• CPU-only deterministic conformance tests must run without external services.
• Passing runs must remain quiet; failures must emit compact structured evidence.
• Soaks must be reproducible from a recorded seed and modeled vLLM version.
• No unfinished request may coexist with an empty wakeup set unless it is terminal or explicitly rejected.
• Ordinary failed admissions must not change request-owned capacity.
• Intentional async owners must be explicit, reserved, and notification-backed.
• The suite must distinguish semantic correctness from performance-model calibration.
• The immediate regression must fail before the transactional allocation fix and pass afterward.
• SGLang fidelity is out of scope for this DEP because it uses a separate scheduler and KV manager model.

Reproducer and Evidence

The high-soak reproducer is documented in #11015 because it is also the replay-level liveness fixture. Its decisive scheduler state was an idle worker with unfinished requests, no transfer/event/deadline, and G1 active blocks owned by non-head ordinary waiting requests. Two observed reciprocal capacity shapes were:

• active=77, queue head needing 200 blocks, available=179;
• active=221, queue head needing 76 blocks, available=35.

Tracing showed a waiting request acquiring fresh blocks, blocking on a later offload-dependent block, retaining the partial acquisition, and then being moved behind preempted running requests. The focused deterministic test should construct that transaction boundary directly; the 1,000-request replay remains integration evidence, not the primary unit proof.

References

Upstream vLLM

• #44560 — Resolve multiple async KV load deadlock (merged)
• #40968 — Resolve PD scheduler stall via lateral preemption (closed alternative)
• #37307 — Add option to schedule requests based on full ISL
• Current KVCacheManager.allocate_slots preflight/commit path
• Current async-load reservation and blocked-state path
• CPU scheduler construction and mocked KV connector fixture
• Seeded 20,000-step priority scheduler blast test
• vLLM mock engine, which emulates the engine protocol for frontend stress testing rather than scheduler/KV ownership

Dynamo context

• #8184 — KVBM G2 offload for online/offline replay
• #10439 — Gate vLLM waiting admission on full ISL
• #10919 — Replay zero-duration/no-progress protection
• #11015 — explicit offline replay liveness ownership
• #10736 — disaggregated KV handoff lifecycle
• #11018 — KVBM causal settlement acknowledgments

[PeaBrane]

Partially addressed by #11019, with explicit mocker offload/swap-in ownership continuing in stacked PR #11031.

The immediate correctness slice is implemented or under review:

• transactional MoveBlock::Use prepare/reserve/commit;
• typed capacity, concrete offload-dependency, and bounded retry outcomes;
• invisible aborts with no phantom active refs, cache visibility, registration, or Stored effects;
• the same contract through ordinary decode, speculative decode, destination reservation, and swap-in admission;
• focused regressions and repeated KVBM-enabled validation.

The larger fidelity program remains open:

• a documented, versioned upstream-vLLM semantic contract;
• systematic upstream change tracking;
• broader deterministic conformance coverage;
• reproducible seeded PR/nightly soak infrastructure and minimized failure traces;
• comprehensive ownership diagnostics across every scheduler boundary.

Keeping this DEP open as partially implemented.