M5.2 - Continuous Batching and Scheduler Pressure

M5.2 - Continuous Batching and Scheduler Pressure

0x00 Overview And Background

0x00A From A Rectangular Batch To A Repeated Decision

Batching is often introduced as a tensor-shape operation. A collection of examples with compatible dimensions becomes one leading batch axis:

X: [B, S, d]

That view is sufficient when the examples enter together, execute the same graph, and leave together. Training batches and many offline inference jobs have this contract. Padding may waste work, but the membership of the batch is not itself a decision repeated inside the forward pass.

Autoregressive serving breaks that lifecycle. A request first contributes a prompt frontier, then remains live across an unknown number of generation steps. Other requests can arrive, finish, cancel, miss a cache dependency, or change readiness while it is still decoding:

request A: prompt ----------------> decode -> decode -> finish
request B:          prompt -------> decode -> cancel
request C:                     wait -----> prompt -> decode -> ...
request D:                                  priority arrival -> wait

The important mismatch is therefore not only unequal tensor lengths. It is unequal request lifetimes. If batch membership is frozen until the slowest request completes, a finished sequence leaves an unusable slot while new work waits behind a barrier that no model equation requires.

Transformer Series A26 - K/V Cache Optimization: P/D Separation Or Merging introduces this failure from both sides. At the service level, early-finished and late-arriving requests make a fixed batch waste capacity and queue work. At the operator level, mixed prompt and decode rows do not form one simple [B,S,d] rectangle because their sequence extents, positions, masks, and K/V histories differ.

ORCA made the systems transition explicit. Instead of submitting a set of generative requests and waiting for every request to finish, its scheduler submits one model iteration, receives the result, updates the request pool, and chooses again. Selective batching then recovers shared token-wise work while preserving request-local attention state. The historical move can be summarized as:

“Continuous batching” is now the common operational term for dynamic batch membership during generation. It should not be read as the name of one canonical algorithm. ORCA, SARATHI, Sarathi-Serve, and production runtimes can all reschedule work at fine granularity while choosing different reservation, chunking, priority, preemption, and overload rules.

This article reconstructs the common decision boundary before comparing those policies.

0x00B The Missing Object: One IterationPlan

M5.1 turned K/V cache from two anonymous tensors into a logical, versioned per-request serving object. It separated:

emitted output progress
computed-token progress
committed cache progress
logical K/V payload
reserved and resident state
request lifecycle and readiness

That separation matters immediately. Prefill can emit the first output token; the later one-row decode call processes that token as input and produces the next output. A scheduler that treats “output length,” “computed length,” and “committed K/V length” as one counter can schedule the wrong row even when its nominal batch size is legal.

M5.1 also provides the payload coefficient that turns a token frontier into a logical K/V trajectory:

M_KV = B * T * L * 2 * H_kv * d_h * bytes

That formula describes state. It does not answer the policy question:

Which legal prefill intervals and decode rows should execute in the next engine iteration under token, sequence, memory, fairness, and SLO constraints?

M5.2 owns the answer as one conceptual object:

IterationPlan
    input:
        factual request frontiers and readiness
        waiting/running/suspended queue state
        token and sequence budgets
        reservation, fairness, and SLO policy
        allocator and foreign-readiness results

    decision:
        selected request generations
        one legal token interval per selected request
        admission, queue, reservation, or preemption intent
        deterministic policy identity and tie-break

    result boundary:
        the engine may execute and return facts
        M5.1 state advances only from the completed result

The plan is versioned policy output, not another name for a batch tensor. It records what should run before token rows are packed, before request-local attention segments are assembled, and before execution publishes progress. Section 0x01A establishes the exact immutable schemas, interval predicates, and negative fixtures. This opening freezes the owner and the direction of the interface before those details are derived.

The resulting article path is:

fixed request batch
    -> iteration-level decision
        -> validated IterationPlan
            -> selective token packing and request-local attention
                -> admission, chunking, fairness, and preemption policies
                    -> completed result returned to M5.1 state

This framing prevents “continuous batching” from collapsing scheduler policy, cache allocation, K/V transfer, and model execution into one mechanism.

0x00C Owner Contract: Consumes, Owns, And Defers

The ownership rule is not “the scheduler may mention only queues.” Scheduling necessarily consumes facts from memory, runtime, and model subsystems. The rule is that M5.2 chooses work and policy transitions without silently implementing the subsystem that supplied each constraint.

This article can therefore decide to preempt a request without claiming to copy its K/V to host memory. It can prioritize a prefix hit without implementing the prefix index. It can wait for a remote cache without choosing the remote worker or transfer protocol. It can carry an adapter or speculative constraint without pretending ordinary decode semantics fully describe that specialized work.

0x00D Source Continuity And Corrections

A24 and A26 contain the right systems intuition, but the reconstruction needs four precision corrections before their mechanisms are extended.

Two further distinctions remain active throughout the article:

planning is not execution:
    an IterationPlan proposes legal work
    only a completed engine result advances service state

reservation is not allocation:
    a scheduler may estimate future K/V pressure
    only the allocator can publish physical feasibility and ownership

The current article uses A26 for the historical ORCA/SARATHI path and A24 - K/V Cache Optimization for metrics and later policy variants. Primary papers and pinned runtime source qualify those source-local explanations. Benchmark numbers remain source-reported unless reproduced under a declared local measurement manifest.

0x01 Claim Status And Scope

The article’s synthesis claim is:

Continuous batching is not just "larger batching."
It is a repeated, versioned decision over legal request-token intervals,
constrained by queue state, KV pressure, fairness, and latency risk.

0x01A Immutable Workload, State, Plan, And Result

The phrase “choose the next batch” sounds simple enough to implement with one mutable dictionary attached to every request. That representation erases the question of who knew what, and when. A scheduler can then read a field produced after execution while claiming it was available before execution, mutate a request that has already advanced to another generation, or debit fairness for work that was planned but never completed.

The fix is not more queue-state labels. It is four records with separate writers and validity windows.

Four Records, Four Update Authorities

The repository fixture makes the visibility boundary explicit:

WorkloadManifest on disk:
    online request declarations
    fixture_only_hidden_truth:
        realized_output_tokens

online policy projection:
    fixture_only_hidden_truth removed
    realized_output_tokens is fixture-only hidden truth

The hidden field is useful later when a replay evaluates reservation error or completion time. It is illegal online input. A policy may see max_output_tokens, a source-labelled prediction, or a quantile produced from historical data. It may not see how many tokens this fixture will eventually emit unless the experiment is explicitly labelled as an oracle policy.

The four schemas are compact enough to reconstruct:

WorkloadManifest
    workload_id, clock contract
    request declarations and request_generation
    policy_id, policy_version, deterministic tie-break
    token and sequence capacity

SchedulerState
    decision_id, state_version, monotonic_now
    waiting, running, suspended, finished
    request service views from M5.1
    factual readiness and completed-service counters

IterationPlan
    decision_id, input_state_version
    policy_id, policy_version
    selected request_generation + snapshot_version
    [computed_start, computed_end)
    derived work annotation, positions, dependencies
    budget ledger and queue intent

IterationResult
    decision_id, input_state_version
    completed intervals and output events
    progress before/after, failures, terminal events
    actual completed-service debits

These are semantic records, not a requirement to parse JSON in a serving hot path. Packed structs, arena indices, and device-side metadata are valid implementations if they reconstruct the same identity, version, and interval contract.

Deriving The Only Legal Ordinary Token Interval

Let request r expose these factual frontiers at scheduler cut n:

p_r = prompt token count
e_r = emitted output-token count
c_r = computed token count
k_r = all-layer committed cache length

This article’s ordinary, non-speculative fixture requires k_r = c_r at the published decision boundary. M5.1 explains why e_r and c_r are not equal. The prompt belongs to the authoritative logical stream before it is computed, and the latest emitted output token ordinarily becomes a K/V row only in the next model call.

For an unfinished prompt:

$$c_r < p_r, \qquad e_r=0.$$

The next legal prefill interval must begin at the current frontier and remain inside the prompt:

$$c^{start}_{r,n}=c_r, \qquad c_r < c^{end}_{r,n}\le p_r.$$

For ordinary decode, at least one output token has already been emitted, and the computed frontier is one position behind the logical stream:

$$e_r\ge1, \qquad c_r=p_r+e_r-1.$$

The only legal ordinary decode interval is therefore:

$$[c^{start}_{r,n},c^{end}_{r,n})=[c_r,c_r+1).$$

Renderer-safe contract:

prefill:
    start = computed
    computed < end <= prompt_tokens

ordinary decode:
    emitted >= 1
    computed = prompt_tokens + emitted - 1
    [start, end) = [computed, computed + 1)

PREFILL_CHUNK and DECODE_ROW are derived annotations. They are not independent fields a policy may forge. Request-local positions must equal range(start, end). A cached prompt simply starts with a later valid computed frontier. Specialized speculative and tree-shaped work has a different temporary-state contract owned by M7; it cannot be smuggled through this ordinary one-row decode rule.

One Valid Mixed Iteration

The Loop 2 fixture freezes a scheduler cut at iteration 5:

The declared policy orders ready decode rows before ready prefill, then uses:

(phase_rank, priority_rank, arrival_order, request_id, request_generation)

Its reproducible ready order is req-B:2, req-C:1, req-A:0. The resulting plan consumes both budgets exactly:

$$K_{used}=1+1+2=4\le K_{token}=4,$$ $$N_{used}=3\le K_{seq}=3.$$

selected_work:
    req-B:2 snapshot 9  [3,4)  DECODE_ROW
    req-C:1 snapshot 6  [3,4)  DECODE_ROW
    req-A:0 snapshot 3  [0,2)  PREFILL_CHUNK

not selected:
    req-D:0  foreign readiness is false
    req-E:4  terminal generation

This is not a claim that decode-first is universally optimal. It is a contract fixture: given the declared policy and input state, another implementation must reproduce the same key order or explain a different policy identity.

Planned, Completed, Emitted, Computed, And Committed

An IterationPlan does not advance any request counter. It only authorizes an attempt. Execution may reject an allocation, lose readiness, be cancelled, or complete fewer rows than planned. The result must therefore carry both the planned and completed intervals.

For a fully completed ordinary interval:

computed_after = completed_end
committed_after = computed_after after all-layer publication

emitted_after = emitted_before + 1
    if a decode row completes
    or if prefill reaches the prompt frontier

logical_after = prompt_tokens + emitted_after

In indicator notation:

$$e^{after}_r=e^{before}_r +\mathbf{1}[\text{decode row completed}] +\mathbf{1}[\text{prefill first reaches }p_r].$$

The fixture result exposes the clocks rather than hiding them:

req-A has not reached the end of its four-token prompt, so it emits nothing. req-B emits its second token and reaches EOS in the synthetic result. Its logical stream has length 5 while its committed cache has length 4: the final emitted token has not been processed as a later input row. This is the same off-by-one invariant M5.1 uses to prevent a correction token or final output from borrowing the wrong K/V row.

Fairness accounting follows the same publication rule. If an interval was planned but did not complete, it consumed no completed token service in this contract. The fixture debits client-alpha by three completed rows and client-beta by one; it never derives service from the plan alone.

Version Binding And Deterministic Replay

A request ID is not enough to authorize work. Every selected row binds:

decision_id
input_state_version
policy_id + policy_version
request_id + request_generation
M5.1 snapshot_version
computed interval and readiness dependencies

A retry from state_version=6 cannot publish into version 7 merely because request_id still matches. A delayed completion for generation 1 cannot advance generation 2. A cancellation or append that changes the M5.1 snapshot invalidates the old plan before packing or publication.

Deterministic tie-break evidence serves a different purpose. Policy versions can intentionally choose different work, but one policy applied to the same immutable state must not depend on hash-map iteration order. Recording the ordered key makes a scheduler decision replayable without claiming that the key is a universal scheduling objective.

Mechanical Validation And Negative Fixtures

The executable boundary rejects invalid work before model execution:

def validate_plan(workload, state, plan):
    assert plan.input_state_version == state.state_version
    assert plan.policy_identity == workload.policy_identity

    for work in plan.selected_work:
        view = resolve_exact_generation_and_snapshot(work, state)
        assert view.ready and not view.terminal
        assert work.start == view.computed_frontier
        assert annotation_is_derived(work, view)
        assert positions(work) == range(work.start, work.end)

    assert sum(work.width for work in plan) <= state.token_budget
    assert unique_request_count(plan) <= state.sequence_budget
    assert tie_break_evidence_replays(plan, state)

The standard-library oracle in docs/numinens-evidence/m5-2-continuous-batching/ validates the four JSON records and then mutates one invariant at a time. Negative fixtures cover:

interval before frontier or beyond prompt
multi-row ordinary decode
duplicate or stale request generation
stale M5.1 snapshot or scheduler-state version
unready, terminal, or duplicated queue member
token/sequence budget and ledger drift
forged phase, position trace, policy version, or tie-break
realized-output or physical-block information leak
unplanned completion, wrong output clock, and planned-service debit

These tests prove internal contract consistency under a synthetic fixture. They do not implement ORCA, choose a production policy, measure GPU utilization, or validate physical allocation. Those mechanisms remain later loops and neighboring article owners.

0x02 Why Static Batching Breaks

Static batching works when a batch starts together and finishes together. Training often has that shape:

X: [B, S, d]

The batch is a rectangle. The examples have the same forward-pass contract. The optimizer step waits for every item.

Autoregressive serving does not have that shape. One request may produce four output tokens. Another may produce eighty. A third may arrive while the first two are still decoding. If the serving engine freezes the active request set until the slowest request completes, two bad things happen:

• a completed request cannot return promptly because the batch barrier is still open;
• a newly arrived request cannot enter even if one slot has effectively become free.

Source: ORCA: A Distributed Serving System for Transformer-Based Generative Models, Figure 3. The dashes are computation imposed by a fixed batch after one request has already finished.

The difference is not cosmetic. It changes the scheduling unit.

A First-Token-Correct A/B/C Fixture

A concrete trace makes the failure auditable, but only if every policy uses the same token clock. The fixture below inherits M5.1’s contract:

prefill completion:
    emits output token 1

later ordinary decode completion:
    consumes the latest emitted token as an input row
    emits exactly one later output token

Let one worker expose two logical request slots. Each selected request uses one slot for one unit-duration synthetic iteration. Every prompt is abstracted to one prefill operation, so a request with realized total output length G uses one prefill slot-iteration plus G - 1 decode slot-iterations:

The realized lengths are fixture-only execution truth. Neither online policy may read them before an EOS or stop result arrives. They are shown here because the completed replay is being derived retrospectively.

Under fixed request-batch membership:

Iteration-level refill changes only the membership rule:

Deriving Fixed-Batch Slot Occupancy

The fixture deliberately makes one logical slot the unit of accounting. For a fixed cohort occupying a worker with B request slots, let request r require G_r slot-iterations. Because membership remains frozen until the longest request completes, the cohort remains open for:

$$I_{batch}=\max_r G_r$$

iterations. The available and useful slot work are therefore:

$$W_{available}=B\max_r G_r, \qquad W_{useful}=\sum_r G_r.$$

The difference is fixed-barrier idle work:

$$W_{idle}=B\max_r G_r-\sum_r G_r.$$

Dividing useful by available slot work gives the retrospective logical slot occupancy:

$$U_{slot}=\frac{\sum_r G_r}{B\max_r G_r}.$$

For the first fixed cohort, A and B:

useful = 2 + 8 = 10 slot-iterations
available = 2 * max(2, 8) = 16 slot-iterations
fixed-barrier idle = 16 - 10 = 6 slot-iterations
U_slot(A,B) = 10 / 16 = 0.625

The second cohort contains only C but still runs on a two-slot worker:

useful = 3
available = 2 * 3 = 6
empty-slot idle = 3

Across the whole fixed-policy replay, the worker runs for 11 iterations:

useful = 2 + 8 + 3 = 13
available = 2 * 11 = 22
idle = 22 - 13 = 9
logical slot occupancy = 13 / 22 = 0.591

Iteration refill performs the same 13 useful request operations but ends when B finishes at cut 8:

useful = 13
available = 2 * 8 = 16
idle = 16 - 13 = 3
logical slot occupancy = 13 / 16 = 0.8125

The latency clocks reconcile with the same cut convention:

These quantities are not synonyms:

Prefill and decode iterations can have radically different shapes, durations, arithmetic intensities, and memory traffic. Real iteration duration also changes with batch composition and cache length. Calling U_slot GPU utilization would therefore turn a scheduling abstraction into a false hardware measurement. The article and executable report label it not measured GPU utilization.

Request-To-Iteration Transition

At cut 2, both policies receive the same immutable facts:

SchedulerState v2:
    A: FINISHED after output token 2
    B: WAITING_DECODE after output token 2
    C: WAITING_PREFILL, arrival_cut = 2
    request_slots = 2

The policy output is where they diverge:

fixed_request_batch plan:
    preserve current cohort membership until B finishes
    slot 0 = IDLE_FIXED_BATCH_BARRIER
    slot 1 = B decode row -> possible output token 3

iteration_refill plan:
    release A from scheduler membership
    admit C into the newly eligible slot
    slot 0 = C prefill -> possible output token 1
    slot 1 = B decode row -> possible output token 3

Execution then returns facts rather than mutating the plan:

IterationResult for [cut 2, cut 3):
    C prefill completed -> first_token_cut = 3
    B decode completed -> emitted_output_tokens = 3

successor SchedulerState v3:
    publish only completed progress
    retain B and C as live if neither returned a terminal result

This is the request-to-iteration transition in its minimal form:

immutable state at cut i
    -> policy chooses membership and legal work
        -> engine executes one iteration
            -> result publishes completion and stop facts
                -> immutable state at cut i+1

The standard-library oracle in docs/numinens-evidence/m5-2-continuous-batching/batching_transition.py replays both policies from batching_transition_workload.json, writes batching_transition_report.json, and rejects invalid first-token clocks, duplicate generations, impossible output lengths, unknown policies, and any fixture that labels the result measured GPU utilization. Realized output length is removed from the online workload projection before either policy runs.

The source A26 calls out the two workload failures explicitly: early-finished requests and delayed-join requests. ORCA’s paper states the same reason externally: generation spans multiple iterations, while fixed request batches cannot replace completed members or admit new work before the batch boundary.

So the first scheduler correction is:

Do not schedule "the request" as one indivisible execution object.
Schedule the next iteration of each live request.

0x03 The Iteration Is The Scheduling Unit

For decoder-only generation, a request moves through two broad model phases:

prefill:
    process S prompt rows
    write prompt K/V
    emit first token

decode:
    process 1 new query row
    read historical K/V
    append one K/V row
    emit next token

Each decode token is one model iteration for that request. The scheduler can therefore stand between iterations:

run one iteration
observe outputs and stops
release finished requests
admit new requests if possible
choose the next batch of work
run the next iteration

ORCA’s contribution was not only “batch more.” It moved control back to the scheduler between model iterations. The scheduler invokes the execution engine for one iteration, receives one token per active sequence, updates request state, then chooses again.

ORCA Algorithm 1: Historical State And Reservation Contract

The control loop is easier to understand if the variables in ORCA’s original Algorithm 1 are reconstructed before translating them into a modern runtime. The paper’s scheduler carries four global quantities:

Each request also carries a phase state and max_tokens, the paper’s per-request upper bound on the total token count after processing. The historical transition is:

INITIATION:
    request has never been scheduled
    Select() may reserve req.max_tokens slots

RUNNING:
    one scheduled batch containing this request is in the engine pipeline
    Select() filters the request out, preventing duplicate concurrent work

INCREMENT:
    the previous iteration returned
    the request is eligible for a later one-row generation iteration

ORCA’s Select(pool, n_rsrv) is iteration-level FCFS rather than a general SLO policy:

def select_orca_historical(pool, n_rsrv, max_bs, n_slots):
    batch = []
    eligible = sort_by_arrival_time(
        req for req in pool if req.state != RUNNING
    )

    for req in eligible:
        if len(batch) == max_bs:
            break

        if req.state == INITIATION:
            new_n_rsrv = n_rsrv + req.max_tokens
            if new_n_rsrv > n_slots:
                break
            n_rsrv = new_n_rsrv

        batch.append(req)

    return batch, n_rsrv

The use of break is part of the paper’s arrival-order contract: it does not silently skip an older initiation request to admit younger work that happens to fit. Once selected, the outer loop schedules exactly one model iteration, marks every member RUNNING, and increments n_scheduled. When n_scheduled == n_workers, the scheduler waits for a scheduled batch to return. Returned members become INCREMENT; finished requests release their req.max_tokens reservation.

This reservation rule solved a concrete problem in the paper: without admission-time headroom, all live requests could need another K/V row while no slot remained, leaving the scheduler unable to advance any of them. It is not a timeless prescription. Reserving every request’s maximum total length can waste capacity; optimistic admission can improve concurrency but requires a defined underestimation and preemption path. Loop 5 compares those policies.

It is also important not to import the paper’s abstract slot counter into the wrong owner:

historical ORCA n_rsrv:
    scheduler-side conservative reservation counter

Transformer System IterationPlan reservation_decisions:
    versioned policy intent

M5.3 allocator result:
    physical feasibility, ownership, pages, and block tables

The original algorithm does not depict concurrent request arrival/removal, modern token budgets, chunked prompt intervals, prefix reuse, cancellation, priority classes, or versioned stale-result rejection. The immutable records in 0x01A extend the control contract without rewriting ORCA as if the 2022 paper already implemented those later mechanisms.

That gives the serving engine a place to make decisions:

• remove finished requests;
• admit new prompts;
• decide whether prefill or decode gets priority;
• maintain fairness;
• release or retain KV blocks;
• avoid violating TTFT or TPOT targets;
• keep enough work in the batch to use the GPU.

The request state visible to that loop is more specific than “running” or “not running.” The labels below are human-readable projections of the versioned SchedulerState contract from 0x01A; they are not a second mutable state machine:

The control loop looks like this:

A compact scheduler sketch must preserve the plan/result boundary:

while server_running:
    state = publish_scheduler_state(
        m5_1_service_views,
        queue_snapshot,
        allocator_and_foreign_readiness,
        completed_service_counters,
    )

    plan = policy.choose(workload.online_projection(), state)
    validate_plan(workload, state, plan)

    packed_iteration = pack_selected_intervals(plan)
    result = run_model_iteration(packed_iteration)
    validate_result_against_plan(result, plan, state)

    publish_only_completed_progress(result)
    debit_fairness_from_completed_service(result)

This pseudocode is intentionally not a production scheduler. Real systems add fairness, preemption, priority classes, prefix reuse, tensor/pipeline parallel placement, memory paging, and failure recovery. A latency-protecting policy may prioritize decode cadence before admitting prompt work; a TTFT-heavy policy may do the opposite. The point is the invariant:

the scheduler forms the next token batch from live request state

That is different from:

the scheduler forms a request batch and waits until it is done

0x04 Selective Batching: Not Every Operation Has The Same Shape

Iteration-level scheduling creates a second problem. The selected requests can have different query lengths, positions, phases, and history lengths. The engine cannot recover that information from one anonymous token matrix.

From IterationPlan To PackedIteration

Let request i contribute the legal interval selected in 0x01A:

[computed_start_i, computed_end_i)

Its number of query rows is:

$$q_i = \text{computed\_end}_i - \text{computed\_start}_i.$$

For N selected request generations, the packed query-row count is:

$$Q_{tot}=\sum_{i=0}^{N-1}q_i.$$

Define prefix offsets:

$$o_0=0, \qquad o_{i+1}=o_i+q_i.$$

Then request i owns exactly the packed half-open slice [o_i, o_{i+1}). Packing is not only concat(hidden). The executor needs a row-level route and a segment-level attention descriptor:

PackedIteration
    hidden:                  [Q_tot, d]
    request_offsets:         [N + 1]
    request_key_by_row:      [Q_tot]
    request_local_position:  [Q_tot]
    phase_by_row:            [Q_tot]
    logical_cache_handle:    [N]
    decision_id / state version / snapshot versions

The distinction from the scheduler record is strict:

IterationPlan:
    which legal request intervals should run?

PackedIteration:
    where did every selected row land, and which request-local
    attention state must it use?

The executor may derive the second from a validated first. It may not change the selected intervals while packing them.

A Five-Row Mixed-Phase Fixture

The Loop 4 fixture selects three request generations:

This produces five, not four, token rows:

q = [1, 3, 1]
Q_tot = 1 + 3 + 1 = 5
request_offsets = [0, 1, 4, 5]

packed row:       0    1    2    3    4
request:         A:0  B:0  B:0  B:0  C:0
token label:      A5   B0   B1   B2   C2
local position:    5    0    1    2    2

The packed hidden tensor has shape [5,d]. In the MHA-style notation used by ORCA Figure 5, one fused QKV projection produces [5,3d], then splits into three [5,d] tensors. In a GQA or MLA implementation the projection and cache dimensions differ; M5.7 and M5.8 own those architecture-specific shapes. The packing argument only requires that every packed row follows the declared projection ABI.

Why Token-Wise Operations Can Share The Packed Axis

Suppose a function f applies the same weights and row-local state to every row, without reducing or mixing the packed axis. Then:

$$f\left(\operatorname{concat}(X_0,\ldots,X_{N-1})\right) = \operatorname{concat}\left(f(X_0),\ldots,f(X_{N-1})\right).$$

For a linear projection this follows directly. If row r is copied from request matrix X_i, then:

$$(X_{pack}W)_r = X_{pack,r}W = X_{i,local(r)}W.$$

No term depends on another packed row. The same reasoning covers row-local LayerNorm/RMSNorm, elementwise activation, residual addition, and MLP linear maps when their runtime metadata and weights are compatible. It does not cover an operation that reduces across packed rows, uses request-specific weights without a routing map, or mistakes the packed axis for one sequence.

ORCA exploited this equality to reuse model-weight reads across irregular requests. Figure 5 in the primary paper shows seven input rows entering a shared QKV linear, splitting for request-local attention, merging back to [7,H], and sharing the output linear:

Source: ORCA, Figure 5. The paper’s concrete path is [7,H] -> [7,3H] -> request-local attention -> [7,H]; the five-row fixture below is an independent executable reconstruction rather than a claim that modern kernels retain the same implementation.

Request-Local Attention Relation

Attention is different because each query row needs a request-local key set. Let packed query row r belong to request generation i at local position p_r. Let key row s belong to request generation j at local position u_s. The ordinary causal visibility predicate is:

$$\operatorname{visible}(r,s) = (i=j)\ \land\ (u_s\le p_r)\ \land\ \operatorname{available}_i(u_s).$$

Equivalently, the logical mask is:

$$M_{r,s}= \begin{cases} 0, & \text{if }\operatorname{visible}(r,s),\\ -\infty, & \text{otherwise.} \end{cases}$$

available_i binds prior rows through request i’s logical K/V handle and current rows through its packed segment. It does not expose a physical page or address; that mapping belongs to M5.3.

For the fixture, the permitted keys are:

For segment i, attention is therefore:

$$O_i= \operatorname{softmax} \left( \frac{Q_iK_i^\top}{\sqrt{d_h}}+M_i \right)V_i.$$

The outputs are written back into the same packed slice O_pack[o_i:o_{i+1}]. That stable order is what lets the output projection, residual path, and MLP return to packed token-wise execution.

Tensor And Code Trace

The complete layer-level path is:

def run_selective_layer(plan, service_views, layer, allocator_view):
    validate_plan(plan, service_views, allocator_view)

    packed = pack_selected_intervals(plan, service_views)
    # hidden [Q_tot, d], offsets [N+1], positions [Q_tot]

    q_pack, k_pack, v_pack = layer.qkv(packed.hidden)
    # shared row-wise projection over [Q_tot, d]

    attention_pack = empty_like(packed.hidden)
    for i, route in enumerate(packed.request_routes):
        begin, end = packed.offsets[i : i + 2]
        prior_kv = logical_kv_view(route.logical_cache_handle, layer)

        segment_kv = append_current_rows_for_attention(
            prior_kv,
            k_pack[begin:end],
            v_pack[begin:end],
            positions=packed.positions[begin:end],
        )
        mask = causal_request_local_mask(
            query_positions=packed.positions[begin:end],
            key_positions=segment_kv.positions,
        )

        attention_pack[begin:end] = attention(
            q_pack[begin:end], segment_kv.keys, segment_kv.values, mask
        )

    projected = layer.output_projection(attention_pack)
    return scatter_by_route(projected, packed.row_routes)

The loop expresses the semantic contract, not a required launch structure. The 2022 ORCA design split and ran attention per request. A modern segmented, ragged, or paged attention kernel can consume all descriptors in one launch. Both implementations are valid if they enforce the same request identity, position, visibility, and logical-cache relation.

Alternative execution choices expose different costs:

Executable Packed-Versus-Reference Check

The article-local standard-library oracle executes a small two-head attention layer through two independent paths:

packed path:
    pack five rows
    -> project Q/K/V together
    -> execute three request-local segments
    -> merge in packed order
    -> output projection
    -> scatter by explicit route metadata

reference path:
    project and attend A, B, and C separately
    -> concatenate only after each request result is complete

The checked-in report reconciles:

In report form, cross-request visibility = 0 for all five queries.

For packed row 0, the trace is concrete:

source:
    A:0, interval [5,6), token A5, packed row 0
    logical cache handle = logical-kv:A:0:v6

projected:
    Q = [1.0, 0.5, -0.5, 0.25]
    K = [0.5, 0.5, -0.75, 0.5]
    V = [0.875, 0.3125, -0.25, 0.25]

attention:
    visible A positions = [0,1,2,3,4,5]
    visible B/C positions = []

output projection:
    [0.489202312272, 0.298728487621,
     0.187306095736, 0.430293906618]

scatter:
    route_metadata[packed_row=0] -> A:0, request_local_row=0

Run it with:

python3 docs/numinens-evidence/m5-2-continuous-batching/selective_batching_oracle.py \
  --write-report
python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop4_selective_batching.py'

The negative suite rejects corrupted offsets, positions, phase/interval contracts, duplicate logical handles, future-token visibility, and cross-request attention. The result is a synthetic contract check, not a kernel benchmark or claim about floating-point identity across production dtypes.

Finally, a layer output row is not service progress. Only after all layers, logits, sampling, stop handling, and result validation may an IterationResult publish completed progress back to M5.1. Packing is execution metadata; it does not bypass the plan/result boundary.

0x05 Budgets Are Different Questions

“How large is the batch?” has no single serving answer. A scheduler needs at least three ledgers, and each ledger constrains a different time horizon:

sequence budget:
    how many request generations may participate in this iteration?

token budget:
    how many input rows may execute in this iteration?

reservation budget:
    how much logical future state may admitted trajectories demand?

The first two bound the next engine call. The third bounds work that might not exist until many calls later. Conflating them creates two opposite errors: a three-request prefill can fit the sequence budget while overflowing the token budget, and a one-row decode can fit both iteration budgets while admitting a future trajectory that the cache cannot sustain.

Two Iteration Budgets, Not One Batch Size

Let I be the set of request generations selected for one IterationPlan, and let q_r be the width of request r’s legal interval:

q_r = computed_end_r - computed_start_r

For ordinary work, q_r = 1 for decode and may be greater than one for a prefill interval. The two iteration counters are therefore:

$$N_{\mathrm{seq}}(I)=\sum_{r\in I}1=|I|$$ $$N_{\mathrm{tok}}(I)=\sum_{r\in I}q_r$$

Renderer-safe form:

N_seq(I) = number of selected request generations
N_tok(I) = sum over selected r of interval width q_r

legal iteration iff:
    N_seq(I) <= B_seq
    and
    N_tok(I) <= B_tok

The conjunction matters. With B_tok = 6 and B_seq = 3:

No scalar “batch size” preserves those results. The token budget controls scheduled rows and the shape of shared row-wise operations. The sequence budget controls per-request metadata, request-local attention segments, adapter or cache handles, and the number of live service objects allowed into the call.

The distinction is visible in pinned runtime source rather than invented for this article. vLLM v0.23.0 names max_num_batched_tokens and max_num_seqs separately; its scheduler initializes a token budget and also prevents the running set from exceeding the sequence limit. That is one implementation, not a universal policy, but it verifies the two-counter boundary.

Loop 2 already validates these counters in every immutable IterationPlan. Loop 5 adds the counterexamples above because “both are checked” is weaker than understanding why neither counter can replace the other.

Consume The M5.1 Byte ABI

The reservation ledger needs bytes, but M5.2 must not rediscover model architecture. M5.1 publishes a versioned service ABI with a logical byte coefficient:

delta_KV_row = logical K/V bytes added by one all-layer committed row

For the running GQA/fp16 profile, M5.1 has already derived:

profile_id   = m5-1-gqa-fp16-logical-row-v1
delta_KV_row = 131,072 bytes = 128 KiB

M5.2 consumes that value. It does not reopen L, H_kv, d_h, dtype, MLA, or K/V quantization. A different M5.7, M5.8, or M8.6 cache ABI can publish a different coefficient without changing the admission algebra here.

For a factual M5.1 service view with T_r committed rows, current logical payload is:

$$M_{r,\mathrm{committed}}=T_r\,\Delta M_{\mathrm{KV,row}}$$

For active request set A(t):

$$M_{\mathrm{active}}(t)=\sum_{r\in A(t)}T_r(t)\,\Delta M_{\mathrm{KV,row}}$$

Renderer-safe form:

M_committed_r = T_r * delta_KV_row
M_active(t)   = sum_r T_r(t) * delta_KV_row

This is logical payload accounting. Physical pages, tail fragmentation, sharing, copy-on-write, and allocator ownership remain M5.3 results.

Deriving Future Rows From The First-Token Contract

Output-token count is not cache-row count. M5.1 proved the ordinary open-stream frontier:

after E >= 1 outputs have been emitted:
    committed cache rows = prompt rows + E - 1
    latest emitted output has not yet been processed as an input row

Suppose a running request has emitted E_r outputs and an admission policy forecasts G_hat_r total outputs. Every additional output decision requires processing the previous emitted frontier once, so its estimated future append rows are:

$$\widehat A_r=\max(\widehat G_r-E_r,0)$$

Renderer-safe form:

estimated_future_append_rows_r = max(forecast_total_outputs_r - emitted_outputs_r, 0)

For a brand-new request whose prompt has not run, the trajectory has two pieces. Let U_r be the exact uncached prompt rows supplied by M5.3’s prefix result:

$$\widehat A_r^{\mathrm{new}} =U_r+\max(\widehat G_r-1,0)$$

The -1 is not a memory optimization. Prefill commits prompt K/V and emits output 1; only a later decode call processes output 1 into another K/V row. If the request stops after that first output, no generated-token row needs to be appended. A coarse prompt + max_new_tokens expression is conservative, but it hides this lifecycle boundary and can produce off-by-one cache claims.

The scheduler’s byte estimate is then just a unit conversion:

$$\widehat M_{r,\mathrm{future}}=\widehat A_r\,\Delta M_{\mathrm{KV,row}}$$

estimated_future_bytes_r =
    estimated_future_append_rows_r * delta_KV_row

This derivation separates four quantities that the earlier compact article collapsed:

Continuous batching is therefore bounded by cache state as well as current compute, but a scheduler can estimate only the unknown part.

0x06 Admission Under Output Uncertainty

Admission does not accept a token. It accepts a policy estimate of a future trajectory. The distinction is unavoidable because stopping on EOS, a stop string, cancellation, or a declared cap occurs in the future.

Output Length Is Hidden Future State

Let G_r* be the total output length eventually realized for request r. Before execution reaches that stop event, an online scheduler does not know G_r*. It may legally know:

declared maximum output length
current emitted output count
versioned output-length prediction
prediction quantiles or calibrated risk class
priority, deadline, and cancellation state
current reservation and allocator-visible capacity facts

It may not know the test fixture’s future realization. Any experiment that reserves exactly G_r* before admission has leaked its answer into the policy. That leak makes utilization, rejection, preemption, and latency results impossibly clean.

For a forecast G_hat_r, define the estimated and realized future append rows:

A_hat_r = max(G_hat_r - E_r, 0)
A_star_r = max(G_star_r - E_r, 0)

The signed reservation error is:

$$\varepsilon_r=\widehat A_r-A_r^*$$

epsilon_r > 0: over-reservation; capacity was withheld but unused
epsilon_r = 0: exact only in hindsight
epsilon_r < 0: under-reservation; extension or recovery may be required

The formula does not identify a winning policy. It names the cost paid on either side of uncertainty.

Maximum, Point, Quantile, And Watermark Policies

The main policy families choose different answers for G_hat_r:

ORCA’s paper-specific Algorithm 1 uses the maximum-bound family. When an initiation request first enters the batch, it adds req.max_tokens to n_rsrv; selection stops if that would exceed n_slots, and reservation is released at finish. The paper explicitly uses this to guarantee enough preallocated K/V slots under its model. It is important history, but not proof that every paged runtime should reserve every maximum or that n_rsrv is a physical allocation record.

Point and quantile policies are synthesis alternatives. A quantile is not automatically conservative: “p90 per request” does not imply a 90% guarantee that an entire concurrent cohort fits, especially when errors are correlated. Calibration must match workload, model, sampling settings, stop policy, and time period.

A watermark changes the admission ceiling rather than the request forecast. Let C_hard be the scheduler-visible hard reservation ceiling and W be rows held outside ordinary admission:

$$C_{\mathrm{soft}}=C_{\mathrm{hard}}-W$$

For FIFO request j, one teaching admission predicate is:

$$R_{j-1}+\widehat A_j\le C_{\mathrm{soft}}$$

soft_ceiling = hard_reservation_ceiling - watermark

admit intent iff:
    existing_reservations + estimated_future_append_rows
    <= soft_ceiling

The watermark is shared recovery space, not request-owned reservation. It can reduce repeated emergency preemption, but it may sit unused and it cannot promise that M5.3 has a compatible physical block arrangement.

One Hidden-Truth Policy Replay

The Loop 5 fixture starts with eight committed-or-reserved logical rows and a hard ceiling of 28 rows. The M5.1 ABI says one row is 128 KiB. Three FIFO resume-ready requests have each emitted one output already:

The online planner receives every column except “hidden realized total.” The offline evaluator reveals that column only after each plan is frozen:

At 128 KiB per row:

hard ceiling:       28 rows = 3.5 MiB
watermark:           4 rows = 0.5 MiB
soft ceiling:       24 rows = 3.0 MiB

maximum unused:      5 rows = 640 KiB
point underestimate:11 rows = 1.375 MiB
p90 underestimate:   3 rows = 384 KiB
hard breach:         1 row  = 128 KiB

These are synthetic logical payload numbers. They do not measure prediction quality, runtime latency, physical fragmentation, or a production allocator. Their job is to make rejection, over-reservation, under-reservation, and recovery visible under one immutable stream.

Reservation Estimate Is Not Allocation Result

An admission planner can produce three records in sequence; it must not merge them:

ReservationEstimate        owned by M5.2
    policy_id
    prediction_version
    estimated append rows and bytes
    hard and soft reservation ceilings

AllocationRequest          issued by M5.2 to M5.3
    request generation
    allocation epoch
    requested append rows and bytes

PhysicalAllocationResult   owned by M5.3
    success / failure / retry fact
    physical ownership and mapping metadata

The first record can pass while the third fails. Logical bytes may fit a ceiling while physical blocks are fragmented, shared, pinned, in transfer, or changed since the allocator epoch. Conversely, a demand-paged allocator may grant only the next chunk rather than materializing the entire forecast.

The planner therefore emits intent and waits for a result:

def plan_admission(request, service_view, policy, budget_view):
    forecast_total = policy.output_forecast(request)
    estimated_rows = max(
        forecast_total - service_view.emitted_output_tokens,
        0,
    )

    soft_ceiling = (
        budget_view.hard_reservation_ceiling_rows
        - policy.watermark_rows
    )

    if budget_view.reserved_rows + estimated_rows > soft_ceiling:
        return DeferCapacity(policy_id=policy.id)

    return AdmissionIntent(
        reservation_estimate_rows=estimated_rows,
        allocation_request=AllocationRequest(
            owner="M5.3",
            allocation_epoch=budget_view.allocation_epoch,
            requested_append_rows=estimated_rows,
        ),
        physical_allocation_result=None,
    )

The None is part of the correctness contract. Filling it with guessed block IDs would move allocator authority into the scheduler.

Recovery Is A Versioned Intent

Underestimation does not allocate memory. As realized progress approaches the reserved frontier, the scheduler must request an extension and branch on the returned allocator fact:

OPEN_UNDER_RESERVATION
    -> request logical reservation extension
        -> request M5.3 physical allocation
            -> GRANTED: publish new reservation/allocation epoch
            -> TEMPORARILY_UNAVAILABLE: wait under declared SLO policy
            -> FAILED: choose preemption, rejection, or abort intent

For the optimistic and p90 fixture plans, realized demand reaches 29 rows against a hard ceiling of 28. The synthetic scheduler names C:0, the lowest priority admitted request, as a preemption candidate. That is not a claim that C’s pages have been released. A complete path still requires:

PreemptionIntent       M5.2 policy output
PreservationIntent     recompute, M5.5 offload, or another legal path
PhysicalReleaseResult  M5.3 fact
SuccessorState         versioned queue and M5.1 lifecycle update

The one-row watermark underestimate is different. Its realized total of 22 rows remains below both the 24-row soft ceiling and 28-row hard ceiling, so M5.2 can issue an extension request without selecting a victim. M5.3 may still deny the physical request; headroom is policy capacity, not allocated memory.

Recovery alternatives optimize different objectives:

No policy is free. Maximum reservation pays in rejected concurrency; optimistic reservation pays in recovery tails; quantiles pay in calibration and residual tail risk; watermarks pay in deliberately idle headroom.

Executable Hidden-Truth Boundary

The article-local evidence surface now includes:

docs/numinens-evidence/m5-2-continuous-batching/
    admission_uncertainty_fixture.json
    admission_uncertainty.py
    admission_uncertainty_report.json
    invalid_admission_uncertainty_fixtures.json
    test_loop5_admission_uncertainty.py

The oracle strips fixture_only_hidden_truth and the oracle policy before calling any online policy. A metamorphic test changes all realized lengths and proves every online plan remains byte-for-byte unchanged. Only then does the offline evaluator score over-reservation, under-reservation, rejection, hard breach, extension, and preemption intent.

Negative fixtures reject hidden-truth leakage, physical block fields, architecture re-derivation, illegal watermarks, bad prediction ordering, forecast values above the declared maximum, an unlabelled oracle, and corrupted token/sequence expectations.

Run the Loop 5 contract with:

python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop5_admission_uncertainty.py'

This evidence compares policy contracts, not policy quality. A production quantile policy still needs a versioned prediction model, calibration and drift evidence, workload-specific evaluation, and runtime allocation results.

0x07 SLO Clocks, Slack, Goodput, And Overload

M5.1 already owns the endpoint clocks and metric denominators. Repeating that derivation here would blur the owner boundary. M5.2 asks the next question:

Given factual arrival and output clocks, declared latency objectives, and a versioned cost model, which legal work should the scheduler select now, and what must it report when offered work exceeds service capacity?

The answer needs four objects that are often collapsed into the word latency: a factual deadline, remaining clock headroom, predicted slack, and the eventual measured outcome.

Consume M5.1 Clocks; Never Restart Them At Admission

Let request r arrive at a_r and emit outputs at factual times y_{r,0}, y_{r,1}, .... M5.1 exports those events and the declared SLOs. M5.2 derives scheduling deadlines without changing their origins:

$$d^{first}_r=a_r+\tau^{TTFT}_r,$$ $$d^{next}_{r,j}=y_{r,j-1}+\tau^{TBT}_r, \qquad j\ge 1.$$

Renderer-safe clock contract:

first-token deadline = original arrival + TTFT limit
next-token deadline  = previous output emission + TBT limit

never use:
    admission time + TTFT limit
    prefill-start time + TTFT limit
    latest scheduler retry + TTFT limit

Resetting the first clock when a request is admitted erases queueing delay. Resetting a next-token clock when work is selected erases a streaming stall. Both can make an overloaded scheduler look compliant by moving the deadline it was supposed to satisfy.

M5.1 also establishes that one emitted output can remain ahead of the committed K/V frontier. A token’s emission time closes a TTFT or TBT clock; cache publication remains a separate correctness event. Loop 7 consumes both facts but does not redefine either.

For a one-output request there is no inter-output interval. Its TPOT remains undefined, while successful completion and TTFT still participate in the request-level SLO predicate. Writing TPOT=0 would manufacture evidence for a decode interval that never existed.

Deadline, Headroom, And Predicted Slack Are Different

At scheduler time n, raw clock headroom is factual:

$$h_r(n)=d_r-n.$$

It says how much wall-clock time remains. It says nothing about how long the candidate work will take. Let a named model m predict endpoint completion:

$$\widehat f_r(n;m)=n+\widehat c_r(n;m).$$

Predicted slack is then:

$$s_r(n;m)=d_r-\widehat f_r(n;m) =h_r(n)-\widehat c_r(n;m).$$

For a waiting request, d_r is its first-token deadline and the cost model must cover the remaining path to first emission. For a live stream, d_r is the next-token deadline and the model must cover the next legal decode result. The same request can therefore move from a TTFT clock to a TBT clock without changing identity.

The Loop 7 fixture uses this deliberately weak model:

model_id = exclusive_endpoint_lower_bound_v1

waiting first token:
    predicted_finish = now + remaining_prefill_units * tick

active next token:
    predicted_finish = now + tick

slack = deadline - predicted_finish

It is a synthetic unmeasured lower bound, not a calibrated latency predictor. Negative slack means the endpoint is infeasible even under that optimistic exclusive-service model, assuming the model contract is valid. Positive slack is not a guarantee: queue contention, batch-shape changes, allocation failure, transfer readiness, preemption, and model error can spend it before completion.

One teaching selector is:

def select_least_slack(now_ms, service_views, cost_model, row_budget):
    candidates = []
    for view in service_views:
        if not view.has_legal_work:
            continue

        deadline = (
            view.arrival_ms + view.ttft_slo_ms
            if view.outputs_emitted == 0
            else view.last_output_ms + view.tbt_slo_ms
        )
        predicted_finish = cost_model.endpoint_finish(now_ms, view)
        candidates.append((deadline - predicted_finish, view))

    return stable_take(candidates, row_budget)

This pseudocode omits admission, batching interactions, and feasibility reconciliation. It also proves no fairness property. Section 0x09A owns client service, aging, MLFQ, and VTC; a least-slack order can starve a class whose deadlines are consistently loose.

One Burst, Two Overload Contracts

The executable burst has a transparent service model:

iteration duration:       10 ms
row capacity per tick:    2
offered at t=0:           6 requests
work per request:         1 first-token unit + 1 next-token unit
TTFT limit:               30 ms
TBT limit:                20 ms
selection:                least predicted slack
tie-break:                next token, arrival, request id

The runtime learns completion from each output event; the online request projection does not contain fixture_only_realized_output_tokens.

Two declared overload contracts produce different outcomes:

Accept-all emits every response but selects two endpoints with negative predicted slack; two requests miss TTFT. Bounded admission protects the four accepted requests in this fixture, but rejection is a user-visible outcome, not free SLO success. Both policies therefore deliver the same fixed-window request goodput while exposing different throughput and failure surfaces.

The four-live cap is not a recommended controller. It exists to make the accounting consequence mechanical. Production overload actions can include:

Offered, Admitted, Completed, And SLO-Valid

Choose one immutable offered cohort and observation window W. Let:

N_off    = requests whose original arrival falls in the cohort
N_adm    = offered requests admitted by this policy
N_comp   = offered requests completed successfully inside W
N_valid  = completed requests satisfying every declared request SLO
N_miss   = completed requests failing at least one declared SLO
N_rej    = rejected offered requests
N_open   = admitted requests unfinished at window end

The outcome partition must close:

$$N_{off}=N_{valid}+N_{miss}+N_{rej}+N_{open}.$$

This produces distinct rate ledgers:

$$\lambda_{off}=\frac{N_{off}}{W}, \qquad T_{req}=\frac{N_{comp}}{W}, \qquad G_{req}=\frac{N_{valid}}{W}.$$

If E_i is the number of tokens actually emitted in the window and q_i is one only for a successfully completed SLO-valid request:

$$T_{tok}=\frac{\sum_i E_i}{W}, \qquad G_{tok}=\frac{\sum_i q_i E_i}{W}.$$

T_tok includes useful partial streaming work from a request that may remain unfinished. G_tok intentionally does not: its predicate requires successful request completion under the declared contract. Another evaluation may choose a per-token deadline predicate, but it must use another name and denominator.

The corresponding fractions answer different questions:

offered-load attainment     = N_valid / N_off
admitted attainment         = N_valid / N_adm
completion-conditioned rate = N_valid / N_comp

The last quantity is useful for diagnosing completed work, but completion-conditioned attainment is diagnostic, not offered-load attainment. A policy that rejects half the arrivals can report 100% among completions while serving only half the offered cohort successfully.

DistServe uses goodput as a capacity objective rather than only one-window arithmetic. For offered request rate lambda and required attainment alpha, the paper-level contract can be written schematically as:

$$G^*=\max\{\lambda:\Pr_{\lambda}[\text{TTFT and TPOT SLO valid}]\ge\alpha\}.$$

The fixed-window G_req above is an observed rate at one offered workload. It does not estimate G* without a rate sweep, repeated trials, warmup policy, workload distribution, and measured runtime.

Average, Percentile, Deadline, And Goodput Objectives Are Not Substitutes

Optimizing one column does not optimize the others. A small number of long valid outputs can raise token goodput while request goodput stays modest. A low mean can coexist with severe tail stalls. Earliest deadline can improve SLO attainment while violating a client-fair service contract.

Tail Metrics Need A Sample Contract

Loop 7 uses the nearest-rank empirical estimator:

$$\widehat Q_p=x_{(\lceil pn\rceil)},$$

where x_(k) is the kth ordered observed sample. The estimator alone is not enough. With twelve observations, a reported p99 is merely the maximum under many conventions and carries no meaningful repeated tail coverage.

The evidence therefore applies this explicit article reporting rule:

p50: report at n >= 2
p95: report at n >= 20
p99: report at n >= 100
otherwise: insufficient_sample

These thresholds follow the reciprocal tail-mass intuition of at least one sample per tail interval. They are a transparency gate, not a universal statistical theorem and not a confidence interval. Correlated arrivals, warmup, non-stationarity, and repeated requests from one client can reduce the effective sample size further.

The oracle’s tail probe contains 98 values of 10 ms and two values of 500 ms:

mean = 19.8 ms      -> passes a 20 ms mean gate
p95  = 10 ms        -> passes
p99  = 500 ms       -> fails

A mean-only result cannot support the p99 claim. Percentiles computed only over completions also cannot make rejected or unfinished requests disappear; those outcomes stay in the offered-cohort ledger beside the latency sample.

Capacity Is A Feasibility Boundary, Not A Scheduling Preference

Let A_k be newly released service rows, C_k completed row capacity, and Q_k unfinished ready work at iteration k:

$$Q_{k+1}=\max(0,Q_k+A_k-C_k).$$

If long-run offered work exceeds service, expected backlog grows. No tie-break can satisfy every finite deadline indefinitely. For a finite observation window, if required work D_W exceeds available slots C_W, at least D_W-C_W rows must be rejected, delayed beyond the window, or removed through another explicit action:

$$D_W>C_W \quad\Longrightarrow\quad \text{all offered work cannot complete inside }W.$$

The saturation fixture offers 240 two-row requests over W=1.3 s:

offline realized demand:  240 * 2 = 480 rows
window capacity:          130 ticks * 2 = 260 rows
unavoidable excess:       220 rows

The demand ledger uses realized output length only offline to prove the finite-window shortfall. The online policy projection does not receive it.

The bounded policy reports 100% completion-conditioned attainment but only 50.833% offered-load attainment. That is not a contradiction: 118 rejected requests are visible failures in the second denominator. The example proves accounting and overload behavior under one synthetic service model. It does not prove that a four-request cap is optimal, fair, or suitable for a GPU.

Source Contracts: DistServe, Sarathi-Serve, And SCORPIO

The sources make three different claims; they should not be blended into one universal scheduler:

SCORPIO is useful evidence that deadline ordering, prediction, admission, and batch selection are separable mechanisms. Its prediction-dependent guarantee language is not transferred to the uncalibrated lower-bound model in this article. DistServe’s capacity goodput is not replaced by one replay’s observed rate. Sarathi-Serve’s p99 TBT evaluation is not inferred from the twelve-sample burst.

Executable SLO And Overload Oracle

The reproducible Loop 7 files are:

docs/numinens-evidence/m5-2-continuous-batching/
    slo_overload_fixture.json
    slo_overload_oracle.py
    slo_overload_report.json
    invalid_slo_overload_fixtures.json
    test_loop7_slo_overload.py

Run them with:

python3 docs/numinens-evidence/m5-2-continuous-batching/slo_overload_oracle.py \
  --write-report
python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop7_slo_overload.py'

The oracle validates event order, first/next deadline origins, slack reconciliation, one-output TPOT, hidden-realization exclusion, closed outcome partitions, request/token rate units, offered and conditional denominators, tail sample gates, and finite-window overload arithmetic. Nineteen negative fixtures corrupt one contract at a time.

This evidence is a synthetic contract test. It is not a calibrated latency predictor, GPU capacity benchmark, production overload controller, or fairness proof. A production result must pin hardware, model, dtype, parallelism, runtime, cost-model version, workload and arrival process, observation window, warmup, repetitions, and confidence or uncertainty treatment.

0x08 Prefill And Decode Pull The Scheduler In Different Directions

Prefill and decode have different resource shapes:

SARATHI measures this asymmetry rather than treating it as a label. In its single-layer LLaMA-13B experiments on an A6000, prefill throughput saturates at comparatively small token batches, while decode needs much larger batches to approach saturation:

The paper then connects that behavior to arithmetic intensity. Prefill’s large matrix operations have substantial reuse even at small request counts; decode’s token-at-a-time operations remain low-intensity until impractically large batches:

Source for both panels: SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills, Figure 4. The measurements are for a single LLaMA-13B layer on an A6000 with the paper’s sequence and batch settings. They explain the scheduling pressure in that setup; they are not universal saturation points.

This is the quantitative reason a mixed iteration can be attractive: a prefill chunk can supply compute-dense work while decode rows consume otherwise underused capacity. The scheduler still has to protect token gaps and KV residency; the graph does not make arbitrary mixing free.

The scheduler tension is:

prefill priority:
    improves first-token latency
    can delay every active decode request

decode priority:
    protects streaming cadence
    can make new prompts wait

Static batching avoids the choice by being inflexible. That is not a solution. It just hides the cost in queueing and idle slots.

Continuous batching exposes the choice at every iteration:

next iteration =
    some decode tokens
    maybe some prefill work
    maybe no new prompt if memory or TPOT risk is too high

This is where SARATHI fits.

0x09 Chunked Prefill And Decode-Maximal Batching

A long prefill can saturate compute. A decode-only batch can underuse compute because each request contributes one new token row and then reads a growing cache. Chunked prefill asks a narrower question than generic continuous batching:

Can one prompt be split across several legal IterationPlan intervals so active decode rows share those model invocations without changing what any prompt token may attend to?

There are two separate obligations in that question. The semantic obligation is causal equivalence. The systems obligation is choosing a chunk and scheduling policy whose extra invocations and repeated cache reads are worth the latency or utilization benefit. Satisfying the first does not answer the second.

The original SARATHI paper names its two mechanisms precisely:

chunked-prefills:
    split one prefill into equal compute-sized chunks

decode-maximal batching:
    use one prefill chunk in a hybrid batch
    piggyback decodes in the remaining request slots

That paper mechanism is only one policy. Sarathi-Serve and vLLM use related chunking ideas but different ordering and budget rules. Before comparing them, the attention contract has to be derived.

One Causal Triangle, Partitioned Into Chunks

Let a prompt contain S positions and let chunk boundaries be:

$$0=s_0<s_1<\dots<s_M=S, \qquad c_m=s_{m+1}-s_m.$$

For a query at global position i inside chunk m, a legal chunked-prefill call exposes two K/V regions:

1. every committed row from earlier chunks, positions [0, s_m);
2. the causal prefix of the current chunk, positions [s_m, i].

Their union is exactly the full-prefill causal set:

$$\{0,\dots,s_m-1\}\cup\{s_m,\dots,i\} =\{0,\dots,i\}.$$

Nothing is missing, and no future key appears. The number of query-key pairs processed for chunk m is therefore:

$$P_m =c_m s_m+\frac{c_m(c_m+1)}{2}.$$

The first term is attention from the current queries to committed history. The second is the in-chunk causal triangle. Substituting s_{m+1}=s_m+c_m gives:

$$P_m =\frac{s_{m+1}(s_{m+1}+1)}{2} -\frac{s_m(s_m+1)}{2}.$$

Summing across chunks telescopes:

$$\sum_{m=0}^{M-1}P_m =\frac{S(S+1)}{2}.$$

Renderer-safe derivation:

chunk m pairs:
    P_m = c_m * s_m + c_m * (c_m + 1) / 2

same expression as a triangular-number difference:
    P_m = tri(s_{m+1}) - tri(s_m)

sum over chunks:
    sum_m P_m = tri(S) = S * (S + 1) / 2

The algebra proves that partitioning does not add logical causal pairs. It does not prove equal physical traffic, equal launch count, or bitwise equal floating-point reductions.

This reconstruction follows the semantic job of SARATHI Figure 6 while making the global positions, tensor extents, and commit boundary explicit. It is not a copy of the paper figure.

Tensor And Cache-Frontier Trace

Consider S=12 and chunks [0,4), [4,8), and [8,12). At the start of the second chunk, the legal computed and committed frontier is a=4. For one layer:

input hidden rows:
    X_m              [c=4, d]

new projections:
    Q_m              [4, H_q, d_h]
    K_new, V_new     [4, H_kv, d_h]

committed history supplied by M5.1/M5.3:
    K_hist, V_hist   [a=4, H_kv, d_h]

visible key/value extent for this chunk:
    K_visible, V_visible
                      [a+c=8, H_kv, d_h]

attention score extent before head grouping details:
    score             [H_q, 4, 8]

M5.7 owns how query heads map to H_kv under MHA, GQA, or MQA. The chunk contract needs only the declared K/V ABI and the global-position visibility relation:

q4 -> k0 k1 k2 k3 k4
q5 -> k0 k1 k2 k3 k4 k5
q6 -> k0 k1 k2 k3 k4 k5 k6
q7 -> k0 k1 k2 k3 k4 k5 k6 k7

One layer-level teaching path is:

def chunked_attention_layer(x_chunk, chunk_start, cache, positions):
    q, k_new, v_new = project_qkv(x_chunk)

    k_hist, v_hist = cache.read_committed_prefix(end=chunk_start)
    k_visible = concat(k_hist, k_new, axis="sequence")
    v_visible = concat(v_hist, v_new, axis="sequence")

    mask = global_causal_mask(
        query_positions=positions,          # [chunk_start, ..., chunk_end-1]
        key_positions=range(chunk_start + len(x_chunk)),
    )
    y = segmented_attention(q, k_visible, v_visible, mask)

    cache.stage_current_layer(k_new, v_new)
    return y

The scheduler may plan [4,8), but it does not publish the request frontier. The runtime stages each layer’s new K/V, completes the model path, samples only when the prompt frontier is reached, and returns an IterationResult. M5.1 advances the all-layer committed frontier only from that completed result. A failed chunk cannot leave the request advertising [0,8) while some layer still owns only [0,4).

The Loop 6 oracle constructs deterministic Q/K/V rows and compares full causal attention with chunk sizes 1,2,3,4,5,6,12. Every partition contains the same 78 causal pairs for S=12, has no missing or extra pair, and returns zero numerical error because the teaching implementation preserves the same per-query reduction order. The production claim is deliberately weaker:

semantic equivalence requires:
    identical token IDs and global positions
    identical causal visibility
    identical model weights and inference state
    deterministic/evaluation-mode behavior
    legal all-layer K/V publication

it does not require:
    bitwise equality across different kernels or reduction orders

This is an inference contract. Training-time chunking also has activation, gradient, random-state, and backpropagation obligations that this article does not claim to satisfy.

Logical Equivalence Is Not Equal Physical Work

The causal-pair proof can be true while the chunked execution is slower. Three different costs must not be collapsed.

1. Cross-invocation history exposure

When chunk m begins at s_m, its attention call has to make earlier K/V rows available again. Define the cross-invocation K/V reload proxy:

$$R_{hist}=\sum_{m=0}^{M-1}s_m.$$

For equal chunks S=MC, this becomes:

$$R_{hist} =C\sum_{m=0}^{M-1}m =\frac{CM(M-1)}{2}.$$

This counts each prior K/V row once for each later chunk invocation that needs it. It excludes the row’s initial production and does not count low-level cache-line, tile, or per-query transactions. If b_KV is M5.1’s declared all-layer logical bytes per committed row, a transparent exposure proxy is:

$$B_{hist,proxy}=R_{hist}\,b_{KV}.$$

Renderer-safe warning:

cross-invocation K/V reload proxy:
    R_hist = sum(chunk_start_frontier)
    B_hist_proxy = R_hist * logical_KV_bytes_per_row

not claimed:
    measured HBM bytes
    cache-line transactions
    exact kernel traffic

SARATHI and Sarathi-Serve both identify repeated reads of K/V from earlier chunks as chunking overhead. Their wording uses slightly different counting conventions for the first chunk. The proxy here counts only later-call re-exposure, so the first chunk’s rows contribute M-1, not their initial write or first use.

2. More model invocations and fixed overhead

Full prefill uses one top-level model invocation for the prompt. M chunks use M invocations, hence M-1 extra invocation boundaries. That does not imply exactly M-1 extra kernel launches: a model invocation contains many kernels, and a compiler may fuse, capture, or dispatch them differently. It does expose where host scheduling, launch, synchronization, and small-matrix overhead can enter.

Every prompt row still traverses the same linear and FFN layers logically, but smaller chunks can lower arithmetic intensity and leave less parallel work per call. Tile quantization adds a non-monotonic backend effect: a chunk one row past a favorable tile boundary can execute more padded work than a nearby chunk. SARATHI reports this effect for its measured model/hardware setup; it is not a universal tile size.

3. Hybrid-batch reuse can repay some overhead

The benefit comes from the mixed execution path, not chunking alone. Prefill and decode rows use the same linear weights. A compatible implementation can pack their row-wise projections and FFN operations together, reusing a weight stream that a separate decode-only invocation would have loaded again. Attention remains request-local and phase-shaped, exactly as the selective batching contract in 0x04 requires:

shared/fused where row-local:
    QKV projection
    output projection
    FFN linear operations

segmented by request and phase:
    attention history
    positions and masks
    K/V handles and publication

SARATHI calls this decode piggybacking. It does not make attention traffic or K/V residency disappear.

Chunk-Size Sensitivity Without A Universal Winner

The executable sweep fixes S=16 and consumes the Loop 5/M5.1 profile value b_KV=131072 bytes per all-layer logical row. The byte column is a cross-invocation exposure proxy, not a measurement:

The non-power-of-two case matters. Chunk count alone does not determine history exposure; the actual boundaries do. The table still cannot choose a production chunk. A real decision also needs:

measured iteration latency by mixed-batch shape
decode batch and context-length distribution
TTFT and TBT/TPOT objective
model, dtype, parallelism, kernel, and graph-capture regime
tile and padding behavior
KV allocation and preemption outcomes
arrival-time prefill-to-decode mix

SARATHI, Sarathi-Serve, And vLLM Are Different Policies

The shared mechanism is legal partial prefill. The batch-construction contract is not shared.

SARATHI: profiled chunk anchor and decode-maximal batching

The 2023 paper uses one prefill chunk as the compute-shaping anchor, then piggybacks decodes in the remaining request slots. Its simplified memory model derives a maximum resident request batch:

$$B_{paper} =\left\lfloor\frac{M_G-M_S}{L_{max}m_{KV}}\right\rfloor,$$

where M_G is GPU memory, M_S is model-state memory, L_max is the assumed maximum sequence length, and m_KV is K/V bytes per token for one request in the paper model. One resident prefill leaves at most B_paper-1 decode requests to piggyback. This is a historical paper capacity approximation, not a replacement for M5.3’s paged allocation result or Loop 5’s uncertain-output admission contract.

For chunk size C, the paper uses the teaching ratio:

$$P:D=\frac{C}{B_{paper}-1}.$$

Smaller C creates more hybrid opportunities and can cover more decodes, but it can reduce prefill efficiency and amplify repeated K/V reads. The paper’s selection process is therefore two-stage: profile a chunk region suitable for the model, hardware, and expected P:D mix, then account for favorable matrix tile dimensions when the prefill and decode rows are fused. Its reported chunk sizes and speedups remain source-reported measurements.

Sarathi-Serve: running decodes, partial prefill, then admission

Sarathi-Serve turns chunking into an online serving policy. Algorithm 3 first places all running decode rows, then an already-partial prefill, and only then admits new requests. Prefill work is bounded by the leftover token budget tau:

tau = profiled token budget under the target TBT SLO
n_t = rows already placed this iteration

running decodes first
ongoing partial prefill next:
    c = min(prefill_remaining, tau - n_t)
new requests last, while allocation and tau allow

The paper calls the result stall-free scheduling because it is designed to avoid pausing ongoing decodes behind a full long prefill. That is a source-reported paper objective under its profiled token budget, not a proof that every deployment has zero TBT increase. The paper explicitly chooses tau by trading TBT SLO pressure against small-chunk utilization, repeated K/V access, fixed overhead, tile behavior, and pipeline bubbles.

vLLM v0.23.0: frontier catch-up, running queue, waiting queue

The pinned vLLM V1 source is more general than the phrase “decode first.” At tag v0.23.0 (0fc695f...), Scheduler.schedule() says there is no scheduler level prefill/decode phase. A request has num_computed_tokens and a target num_tokens_with_spec; the scheduler assigns rows so the former catches the latter.

The source traverses self.running before a waiting queue, clamps per-request work by long_prefill_token_threshold when configured, and then clamps by the remaining max_num_scheduled_tokens budget:

num_new_tokens = (
    request.num_tokens_with_spec
    + request.num_output_placeholders
    - request.num_computed_tokens
)
num_new_tokens = min(num_new_tokens, long_prefill_token_threshold_if_enabled)
num_new_tokens = min(num_new_tokens, remaining_token_budget)

Only after running requests are considered does the pinned scheduler traverse waiting requests, where unfinished frontier work can likewise be chunked to fit the remaining budget. Allocation failure and preemption can change the result. This is a versioned source observation, not a promise about every vLLM release or configuration.

No row in this table is “the chunked-prefill algorithm.” Each binds a different state model, ordering rule, and optimization contract.

Worked Cadence And Pipeline-Imbalance Comparison

A small worked example separates continuous progress from unchanged latency. It preserves the synthetic schedule originally developed with M5.6, now taught here under the scheduling owner. Its decode-first assembly is a teaching policy, not a reconstruction of original SARATHI’s prefill-first batch construction.

Take a ten-token prompt, chunks of four, four, and two rows, three eligible decode requests, and an eight-token iteration budget:

Decode-only service is assumed to take 4 ms. All selected decodes progress in every mixed slot and all three slots fit the fixture’s 10 ms service gate, but they still wait longer between outputs. These service times are inputs, not values derived from row counts; queueing and a different hardware or load profile can invalidate the gate.

The existing causal-pair ledger above gives 10, 26, and 19 pairs for these chunks: 55 in total, equal to the full ten-token causal triangle. Twelve prior rows are exposed across later invocations. Neither count is measured HBM traffic.

For a vector of microbatch service times $t_1,\ldots,t_n$, define a synthetic imbalance-area proxy:

$$I=n\max_i t_i-\sum_i t_i.$$

Here $n$ is the number of microbatches, each $t_i$ is in milliseconds, and $I$ is an accumulated idle-area proxy in milliseconds across those microbatches. The vectors [18,4,4] and [8,8,6] yield 28 ms and 2 ms. They illustrate uneven versus more uniform service, not equal-work measurements. This expression is not a pipeline simulator, actual bubble duration, or an end-to-end speedup prediction.

The source-local A26 illustration identifies several causes of unequal work; its diagram is explanatory, not a measurement of this fixture:

The preserved fixture remains executable at its historical path:

python3 docs/numinens-evidence/m5-6-prefill-decode-disaggregation-kv-placement/sarathi_schedule_oracle.py \
  docs/numinens-evidence/m5-6-prefill-decode-disaggregation-kv-placement/sarathi_schedule_fixture.json

It checks chunk coverage, selected decode membership, declared service gates, causal pairs, prior-row exposure, cadence dilation, and the proxy. The old directory and asset names record provenance; they no longer assign this derivation to M5.6. Production fairness and the source-pinned policy distinctions remain the contracts developed in this article.

Starvation Counterexamples, Not A Fairness Proof

Priority determines which class can make progress under saturation. The Loop 6 fixture uses B_tok=6 for four iterations:

The first two are persistent-pressure proofs: if the same ready-set condition continues, the opposite class receives zero rows every iteration. The bounded variant rotates decode IDs and reserves one prefill row, but it is not offered as a production policy and proves no latency, fairness bound, or optimality. Section 0x09A derives client-level service definitions, aging, MLFQ/VTC alternatives, and formal starvation protection.

The source-policy table and these adversarial replays are intentionally separate. The replay is synthetic contract evidence, not a production scheduler replay of SARATHI, Sarathi-Serve, or vLLM.

Executable Chunk And Policy Oracle

The reproducible files are in docs/numinens-evidence/m5-2-continuous-batching/:

chunked_prefill_fixture.json
chunked_prefill_oracle.py
chunked_prefill_report.json
invalid_chunked_prefill_fixtures.json
test_loop6_chunked_prefill.py

Run them with:

python3 docs/numinens-evidence/m5-2-continuous-batching/chunked_prefill_oracle.py --write-report
python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop6_chunked_prefill.py'

The negative fixtures reject a wrong causal-pair total, duplicate or zero chunk sizes, a drifted reload proxy, an unpinned policy contract, an unknown synthetic policy, an impossible dual reservation, and a falsified starvation expectation. The oracle does not contain a calibrated latency model. That omission is deliberate: Loop 7 will add SLO clocks and overload evidence, and Loop 10 will perform the fuller pinned-runtime trace.

0x09A Fairness Needs A Client, Interval, And Cost Function

The chunking counterexamples prove that a work class can receive zero rows under persistent pressure. They do not yet define fairness. “Serve the oldest,” “promote a starving job,” “share equally between clients,” and “reserve one slot for cold prompts” protect different objects.

A complete fairness statement needs five declarations:

identity:
    request, job, client, tenant, priority class, or cache-hit group?

eligibility interval:
    when is that identity continuously able to receive service?

service cost:
    requests, input tokens, output tokens, weighted tokens, rows, or time?

publication event:
    selected, admitted, executed, completed, or emitted?

guarantee:
    FIFO order, eventual progress, bounded waiting, proportional share,
    max-min service, or an SLO-conditioned objective?

Changing one line changes the policy contract. A client that submits one long prompt and a client that submits one-token decodes have each submitted one request, but they have not consumed comparable model work. Conversely, a request-aging rule can keep one old request alive while the same client’s many new requests consume most aggregate service.

Loop 8 therefore uses the following local accounting contract:

protected identity       = client_id
time                      = synthetic scheduler ticks in the oracle
service publication      = IterationResult.completed_intervals
failed/planned work       = zero authoritative completed service
starvation                = continuously eligible protected identity
                            completes zero service events in the interval

Input and output tokens need not have equal cost. For client i over [t_1,t_2], define:

$$W_i(t_1,t_2) =w_p n_{p,i}(t_1,t_2)+w_q n_{q,i}(t_1,t_2),$$

where n_p and n_q are completed input and output tokens and w_p,w_q are declared weights. The formula is additive because each completed event contributes one phase-specific token count:

$$\begin{aligned} W_i &=\sum_{e\in\mathcal C_i}c(e),\\ c(e) &=\begin{cases} w_p\,n_e,&e\text{ completes input rows},\\ w_q\,n_e,&e\text{ completes output rows}. \end{cases} \end{aligned}$$

This is an accounting model, not a claim that one input token always takes exactly w_p/w_q times one output token on every batch shape. Production weights need measurement and a declared hardware/runtime regime. Loop 8 uses w_p=1,w_q=2 only to make unlike service visible in deterministic fixtures.

Request Liveness And Client Fairness Are Orthogonal

Consider two clients:

client A: A0 A1 A2 A3 A4 A5 A6 A7
client B: B0 B1 B2 B3

Every event costs two weighted units and all arrive at tick zero. Request FIFO completes every request, so no request starves over the full horizon. Yet while both clients remain backlogged, it serves all eight A events first and reaches a client-service gap of 16. A least-service client policy alternates the first eight events and keeps the shared-backlog gap at 2.

Both policies eventually publish the same totals:

final completed service: A=16, B=8

The final gap is not itself a fairness violation after B stops being backlogged. The relevant question is what happened while both clients could continuously receive service. This distinction is central to VTC’s theorem and prevents a finite-demand client from permanently throttling an active one.

FastServe: Token-Level MLFQ Protects Jobs, Not Client Shares

FastServe attacks head-of-line blocking caused by request-level non-preemptive service. Its scheduler is a skip-join multi-level feedback queue (MLFQ) whose queue quantum approximates the amount of iteration work a job may consume at that priority.

Let queues Q_1,...,Q_m have increasing quanta:

$$q_1<q_2<\cdots<q_m.$$

The first iteration is profiled. A new job does not necessarily enter Q_1; it joins the highest-priority queue whose quantum can cover the profiled first iteration:

$$j_0=\min\{j:q_j\ge \widehat t_{init}\}.$$

This is the skip-join step. A large prompt can enter a lower queue directly instead of occupying the shortest-job queue and immediately being demoted. Scheduling and preemption happen at token/iteration boundaries, where the model has a coherent request frontier.

The paper’s Algorithm 1 first reconciles jobs that returned from the preceding iteration, then updates queue placement, and only then selects the next batch:

def fastserve_skip_join(queues, newly_arrived, returned, quanta, alpha):
    for job in newly_arrived:
        p = first_queue_with_quantum_at_least(
            profiler.next_iteration_time(job)
        )
        queues[p].push(job)                       # skip-join

    for job in returned:
        job.publish_new_generated_token()
        p = job.current_priority

        if job.finished:
            queues[p].remove(job)
            continue

        if job.depleted_quantum:
            eta = demotion_distance(
                p,
                profiler.next_iteration_time(job),
                quanta,
            )
            queues[p].remove(job)
            queues[min(p + eta, len(queues) - 1)].push(job)

        if job.wait_time >= alpha:
            queues[job.current_priority].remove(job)
            queues[0].push(job)                   # promote to Q1
            job.wait_time = 0

    next_batch = []
    for queue in queues:                          # Q1 to Qm
        for job in queue:
            if job.ready and len(next_batch) < max_batch_size:
                next_batch.append(job)
    return next_batch

The paper describes eta as a next-iteration-aware demotion distance and uses geometrically increasing queue quanta, with a lower queue quantum twice the higher one. It tunes alpha from the SLO and reports 300 ms as its default; that number is source-reported, not a universal starvation threshold. The pseudocode omits physical K/V movement. The scheduler may decide to preempt here; M5.5 owns whether and how cache state is swapped, staged, or recomputed.

Why does promotion matter? In the Loop 8 trace, one long prompt has first-step cost 4, so it skip-joins the queue with quantum 4. A cost-1 job arrives in the highest queue every epoch:

The promotion is a job-liveness rule. It proves no bound on weighted service between clients: one client can submit enough short jobs to dominate the high queue while every individual job still completes. FastServe’s paper objective, mechanism, and source-reported latency measurements must not be relabeled as client max-min fairness.

VTC: Fairness Is Weighted Service Between Clients

Virtual Token Counter (VTC) changes both the protected identity and the service unit. It keeps a counter c_i per client and selects the earliest request belonging to the active client with the smallest counter.

The word “virtual” matters. The counter is not a literal emitted-token count. It represents weighted service under the paper’s charging rules:

prefill charge:
    w_p * input_length(request)
    when the request is added to the running batch

decode charge:
    w_q * number_of_running_requests_for_client
    after one output-token generation step

Charging the prompt when it enters the running batch prevents a scheduler from selecting several expensive prompts from the same nominally least-served client before any of them finishes. Algorithm 2 is approximately:

def vtc_select(waiting, running, counter, last_counter):
    newly_active = clients_entering_active_set(waiting, running)
    for client in newly_active:
        if active_clients_except(client):
            floor = min(counter[c] for c in active_clients_except(client))
        else:
            floor = last_counter
        counter[client] = max(counter[client], floor)

    client = min(active_clients(), key=lambda c: (counter[c], c))
    request = earliest_waiting_request(client)

    if request_fits_running_batch(request):
        running.add(request)
        counter[client] += w_p * request.input_length

    outputs = run_one_decode_iteration(running)
    for client in clients_with_generated_outputs(outputs):
        counter[client] += w_q * generated_output_count(outputs, client)

The counter lift prevents idle credit. Suppose A has already reached counter 4 when B becomes active with a stored counter of 0. Without a lift, B could consume four service units merely to catch up for time when it had no waiting request. VTC sets:

$$c_B\leftarrow\max\left(c_B,\min_{i\in\mathcal A}c_i\right) =\max(0,4)=4,$$

where A is the set of already active clients. If the active set had become empty, Algorithm 2 uses the counter of the last client that left rather than resetting history to zero.

The Bound Is Conditional, Not A Scheduler Slogan

VTC’s paper result can be derived from a maximum one-step counter increment. Let:

L_input = maximum input tokens in one request
M       = maximum token count fitting the running batch
w_p     = input-token service weight
w_q     = output-token service weight

One prompt admission can increase one client counter by at most w_p L_input. One decode iteration can charge at most w_q M to one client. Therefore the largest discrete counter jump is:

$$U=\max(w_pL_{input},w_qM).$$

The scheduler always chooses a minimum-counter active client. Immediately before its charge, that client is no larger than every active peer. A single charge can overshoot the previous maximum by at most U, yielding the paper’s counter spread invariant while the queue is nonempty:

$$\max_i c_i-\min_i c_i\le U.$$

For two clients f,g that remain backlogged over the entire interval, service is the counter increment over that interval. Expand the difference:

$$\begin{aligned} W_f(t_1,t_2)-W_g(t_1,t_2) &=[c_f(t_2)-c_f(t_1)]-[c_g(t_2)-c_g(t_1)]\\ &=[c_f(t_2)-c_g(t_2)]-[c_f(t_1)-c_g(t_1)]. \end{aligned}$$

Each endpoint counter difference has magnitude at most U. The triangle inequality gives Theorem 4.4’s service-difference bound:

$$\left|W_f(t_1,t_2)-W_g(t_1,t_2)\right|\le 2U.$$

The Loop 8 fixture chooses w_p=1, w_q=2, L_input=8, and M=4:

U  = max(1*8, 2*4) = 8
2U = 16 weighted service units

That arithmetic does not reproduce the theorem. The theorem requires all of the following paper contracts:

1. both compared clients remain backlogged for the full measured interval;
2. Algorithm 2’s counter lift and charging events are preserved;
3. the scheduler is work-conserving under the paper’s memory criterion;
4. the main result’s no-preemption assumption holds;
5. L_input and M are valid finite bounds for the analyzed system.

Remove any assumption and 2U is no longer justified by this proof. A graph labelled “VTC-like” or a scheduler that merely chooses the smallest counter is not sufficient evidence.

Paper VTC And Completion-Reconciled Accounting Are Different Algorithms

The immutable M5.1/M5.2 state contract advances factual service only from a completed IterationResult. A failed plan must not look like delivered service. Paper VTC, however, charges a prompt when it enters the running batch. Those contracts cannot be silently merged.

Loop 8 therefore names a separate teaching adaptation:

completion_reconciled_vtc_teaching_v1

It keeps two counters:

C_select[i]
    provisional predicted service used to avoid selecting several expensive
    events from client i in one planning window

W_done[i]
    authoritative weighted service published only from completed intervals

The transaction is:

client = least_provisional_counter_client()
event = earliest_ready_event(client)
predicted = weighted_token_cost(event)

C_select[client] += predicted       # reservation for this decision
result = execute(event)

if result.completed:
    actual = weighted_completed_intervals(result)
    W_done[client] += actual
    C_select[client] += actual - predicted
else:
    C_select[client] -= predicted   # rollback
    W_done[client] += 0

The failure trace makes the distinction observable:

tick 0: select A input event, provisional cost 4
        execution fails
        C_select[A]: 0 -> 4 -> 0
        W_done[A]:   0 -> 0

tick 1: retry completes four input tokens
        C_select[A]: 0 -> 4
        W_done[A]:   0 -> 4

The VTC theorem does not transfer to this adaptation. The charging event, running-batch semantics, and proof state have changed. The local trace shows a useful accounting behavior under declared fixtures; it is neither an exact VTC implementation nor a new fairness theorem.

Five Policies, Five Different Contracts

The policies in this article are not interchangeable rankings of the same objective:

Static priority illustrates why a priority number is not a liveness rule. In the fixture, a low-priority request arrives at tick zero while one high-priority request arrives every tick. Static priority gives the protected request zero completed events. With teaching score

$$p_{eff}(r,t)=p_{base}(r)-\left\lfloor \frac{t-a_r}{q_{age}} \right\rfloor,$$

and q_age=2, the old request’s numeric priority improves until it wins at tick 8. This is an adversarial finite trace, not a universal bounded-wait proof: the result also depends on finite priorities, deterministic tie-breaks, continued eligibility, and the absence of a higher-priority floor it cannot cross.

Prefix-Aware Scheduling: Reuse Competes With Fairness

Once M5.3-style exact prefix reuse exists, prompt length is no longer the amount of prefill work. For request r on worker w:

$$U_{r,w}=S_r-H_{r,w},$$

where:

S_r      prompt tokens
H_r,w    exact cached-prefix tokens already resident on worker w
U_r,w    uncached prompt tokens that still require prefill

Routing by shortest queue while ignoring H_r,w can send a request away from a large cache hit. Routing by largest cache hit while ignoring age and queue cost can starve requests with unique prompts.

The competing policies are:

Preble makes this tradeoff explicit in a distributed prompt scheduler. Its local policy groups requests by cached-token percentage and samples proportionally across priority groups rather than serving only the largest hit. The exact paper algorithm should be consulted for reproduction; the general invariant is:

reuse value must not silently replace fairness

A teaching score can make the units visible:

estimated_finish(r, w) =
    queue_time(w)
  + prefill_profile(U_r,w)
  + transfer_or_load_cost(r, w)

priority(r, w) =
    -estimated_finish(r, w)
    + aging_weight * wait_time(r)

This is not Preble’s formula. It is a scheduler contract showing that prefix hit, queue delay, transfer, and age belong in one decision. M5.3 owns how the hit is found and validated; M5.2 owns when the request runs.

Preble’s local waiting policy is narrower than a general client-fair scheduler. It partitions waiting requests by cached-prompt-token percentage and allocates selections proportionally across priority groups, favoring higher-hit groups without permanently suppressing lower-hit ones. Distributed placement remains M5.6’s owner.

The Loop 8 oracle uses a deliberately simpler 2 high : 1 low cycle to expose the liveness mechanism:

reuse greedy under one new hot request each tick:
    hot completed = 9
    cold completed = 0   -> cold group starves

teaching 2:1 quota:
    hot completed = 8
    cold completed = 1   -> both groups progress

This is not an exact reproduction of Preble. It proves only that an explicit group quota changes the cold-group exit condition in the stated trace. Two clients inside the same high-hit group can still receive unequal service, so the result has no VTC client-service bound.

Starvation Is A Failed Exit Condition

An average service share can look acceptable while one protected identity never exits the queue. Loop 8 therefore treats starvation as a mechanical publish-gate failure:

$$Starved(g,[t_1,t_2]) =EligibleThroughout(g,[t_1,t_2]) \land CompletedEvents_g(t_1,t_2)=0.$$

The observation interval and continued-eligibility premise are required. A client that becomes blocked on an unavailable adapter, remote K/V, cancelled request, or invalid cache generation is not ready scheduler work; Loop 9 will make those readiness/preemption distinctions explicit. A client with no offered work is also not “starved.”

The four Loop 8 pressure probes answer different questions:

No policy passes merely because aggregate throughput is unchanged. The protected class must cross its declared progress boundary.

Fairness And SLO Must Be Reported Together

Fairness does not replace the Loop 7 clocks. In the client-flood fixture, FIFO and the least-service teaching policy complete all 12 events and publish the same final service totals. Their six on-time completions are distributed differently:

Aggregate goodput alone would hide B’s complete SLO failure under FIFO. The fairness gap alone would hide that both policies still miss half the events. Publication therefore needs at least:

service by protected identity
maximum gap over the continuously-backlogged interval
starvation count and observation horizon
SLO-valid, completed-miss, rejected, and unfinished outcomes by identity
aggregate offered-load goodput from Loop 7

The service weights and SLO clocks solve different accounting problems. w_p,w_q compare consumed service; TTFT/TBT deadlines judge whether user-visible events arrived on time. Tuning one objective can worsen the other.

Executable Fairness And Starvation Oracle

The reproducible Loop 8 bundle is:

fairness_starvation_fixture.json
fairness_starvation_oracle.py
fairness_starvation_report.json
invalid_fairness_starvation_fixtures.json
test_loop8_fairness_starvation.py

Run it with:

python3 docs/numinens-evidence/m5-2-continuous-batching/fairness_starvation_oracle.py --write-report
python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop8_fairness_starvation.py'

The fixture is deterministic synthetic contract evidence. It does not measure latency, reproduce FastServe performance, implement VTC’s full running-batch algorithm, reproduce VTC’s theorem, or reproduce Preble. Negative fixtures reject:

request-level identity presented as client fairness
planned or failed work published as completed service
FastServe presented with a VTC client bound
missing VTC charging, lift, bound, or theorem assumptions
the local completion adaptation presented as theorem-preserving
the teaching cache quota presented as exact Preble
missing protected classes or MLFQ promotion pressure
synthetic output presented as a production scheduler result

This closes Loop 8’s owner question: a policy is not “fair” until its identity, cost, interval, accounting event, liveness condition, and theorem scope are all inspectable.

0x09B Layer-Wise Allocation And Hierarchical Scheduling

Request-level cache residency is also not the only granularity. A conventional allocator treats one request as having all L layer caches resident. Layer-wise management treats residency as:

resident[r, layer, block]

LayerKV is an externally verified example: it introduces layer-wise block allocation, management, offload, and an SLO-aware scheduler. The attention semantics remain exact if each layer’s required rows arrive before that layer executes.

The memory ledger becomes:

$$M_{GPU}=\sum_r\sum_{l=1}^{L}M_{resident}(r,l),$$

instead of requiring every admitted request’s entire cache stack to be resident at once. The saved capacity is exchanged for a layer pipeline:

while layer l computes:
    prefetch K/V needed by layer l+1
    optionally evict K/V from layer l-1

Conceptual schedule:

for layer in model.layers:
    await cache_tier.ensure_resident(requests, layer)
    prefetch_async(requests, layer + 1)

    hidden = layer.forward(
        hidden,
        kv=cache_tier.view(requests, layer),
    )

    evict_if_needed_async(requests, layer - 1)

This adds a second scheduling horizon:

iteration scheduler:
    which requests and token rows run next?

layer/cache scheduler:
    which layer's state must be resident next?

Failure changes from a simple OOM to a pipeline stall or stale-layer read. The runtime must measure per-layer prefetch lateness, transfer overlap, cache-tier hits, and the number of model iterations delayed by cache readiness.

LayerKV couples these horizons in one system, but the Transformer System ownership stays factored. M5.2 decides whether a request/layer is eligible and records its readiness deadline. M5.5 owns the reserve-copy-validate-publish transaction that makes an offloaded layer visible. A scheduler may consume READY, INFLIGHT, MISS, and predicted stall facts without reimplementing the tier directory.

0x0A Continuous Batching Is Not PagedAttention

Continuous batching and PagedAttention often appear together in serving stacks, but they solve different pieces.

If a serving article says “PagedAttention enables continuous batching,” that is directionally true in many implementations, but it is not a substitute for the scheduler story. PagedAttention makes dynamic KV memory manageable enough for large active batches. The scheduler still decides which requests, chunks, and decode tokens run next.

The contracts are:

scheduler:
    who runs next?

allocator:
    where does their K/V state live?

prefix cache:
    can any exact previous state be reused?

retention policy:
    is the model allowed to stop attending to some previous K/V?

architecture:
    how many K/V scalars does the model require per token?

M5 needs all of those. M5.2 owns only the first boundary.

0x0B A Small Worked Timeline

Suppose the server has:

decode-active:
    A, B, C

waiting-prefill:
    D with S=4096
    E with S=512

token_budget_per_iteration:
    768 token rows

Each active decode request contributes one token row:

A_d = 1
B_d = 1
C_d = 1
decode rows = 3

If the scheduler runs full prefill for D:

iteration token rows ~= 4096 + 3

That iteration is long, and every active decode stream waits behind it.

With chunking:

prefill_chunk_size = 640
remaining decode budget = 768 - 640 = 128

D chunk 0 = 640 prompt rows
D chunk 1 = 640 prompt rows
D chunk 2 = 640 prompt rows
D chunk 3 = 640 prompt rows
D chunk 4 = 640 prompt rows
D chunk 5 = 640 prompt rows
D chunk 6 = 256 prompt rows

The remaining token budget in each iteration can be filled with decode tokens, subject to KV capacity and TPOT risk. The decode streams can continue between D’s chunks:

This is not a proof that 640 is the right chunk size or that 768 is the right per-iteration token budget. The actual values depend on the model, GPU, parallelism, kernel path, SLOs, and workload. It is a ledger that forces the scheduler decision into the open.

Executable Baseline: A Contract Oracle, Not A Capacity Model

M5.2 now uses the article-local Loop 3 oracle rather than the older shared scheduler toy:

docs/numinens-evidence/m5-2-continuous-batching/
    batching_transition_workload.json
    batching_transition.py
    batching_transition_report.json
    invalid_batching_transition_fixtures.json
    test_loop3_batching_transition.py

That supersession is substantive. The older toy assigned token 1 to the first decode completion and reserved exact realized output trajectories at admission. The Loop 3 oracle instead enforces:

prefill completion emits output token 1
realized output length remains fixture-only execution truth
both policies receive one identical online workload projection
policy reacts to terminal results rather than future output length

Run the reproducible comparison with:

python3 docs/numinens-evidence/m5-2-continuous-batching/batching_transition.py \
  --output docs/numinens-evidence/m5-2-continuous-batching/batching_transition_report.json

The checked-in report reconciles the 0x02 derivation exactly:

This baseline deliberately has no service-time model. Later policy loops can add token budgets, variable prefill chunks, K/V admission, fairness, and calibrated runtime events without rewriting the first-token or policy-visibility contract. One fixture remains a state-machine oracle, not a saturation curve, latency benchmark, or measured utilization result.

0x0C Preemption, Resume, And Foreign Readiness

Admission cannot know a request’s realized output length. A scheduler can make a defensible admission decision and later find that the next decode row needs capacity which is not available. The phrase “preempt the request” still leaves three different questions unanswered:

policy:
    which request should stop, and which recovery path is acceptable?

physical transition:
    have its device-owned K/V blocks actually been released or preserved?

resume proof:
    which exact rows are ready, which rows must be rebuilt, and is the
    resulting request generation legal to schedule now?

M5.2 owns the first question and the scheduler-visible resume contract. M5.3 owns physical release, allocation, and exact prefix identity. M5.5 owns preservation, promotion, retrieval, and layer readiness. M5.6 owns worker placement. A policy intent can request those actions; it cannot publish their success.

Intent Is Not Release

The old synchronous mental model is unsafe:

choose victim -> release or transfer -> immediately count free blocks

Release can fail or finish late. Preservation can fail after release succeeds. A cancellation can publish a successor request generation while either operation is in flight. The scheduler therefore needs explicit, versioned records:

PreemptionIntent                     # M5.2 policy output
    intent_id
    request_id, generation, snapshot_sha256
    suspension_epoch
    mode: PRESERVE_EXACT | RECOMPUTE | ABORT
    fallback: RECOMPUTE | REMAIN_SUSPENDED | ABORT
    semantic_target_tokens
    reason, policy_id, decision_version

ReleaseResult                        # M5.3 fact
    same four-part binding
    status: READY | INFLIGHT | FAILED
    reclaimed_bytes                  # meaningful only when READY

PreservationResult                   # M5.5 fact
    same four-part binding
    status: READY | INFLIGHT | FAILED
    exact_ready_prefix_tokens

ResumeTicket                         # M5.2 derived policy record
    same four-part binding
    semantic_target_tokens
    rebuild_interval
    matched readiness receipts

Physical block identifiers, copy streams, host addresses, tier placement, and worker topology are deliberately absent from PreemptionIntent and ResumeTicket. They remain foreign implementation state.

The queue transition is consequently multi-stage:

RUNNING
    -> PREEMPT_PENDING
        -> SUSPENDED_PRESERVED
        -> SUSPENDED_RECOMPUTE
        -> CANCELLED

SUSPENDED_*
    -> RESUME_PENDING
        -> RUNNING
        -> CANCELLED

PREEMPT_PENDING is not free capacity. Only a matching successful ReleaseResult lets M5.2 consume a revised M5.3 free-capacity fact. Likewise, RESUME_PENDING is not runnable work. It waits for a complete readiness conjunction.

The Suspension Epoch Closes The ABA Hole

M5.1’s generation and snapshot digest protect logical request state. They do not distinguish this sequence:

request (generation=2, digest=S) preempted at epoch 10
request resumes without changing its semantic frontier
request (generation=2, digest=S) preempted again at epoch 11
delayed preservation result for epoch 10 arrives

If readiness were keyed only by generation and digest, the delayed epoch-10 receipt could satisfy epoch 11. This is an ABA-style identity error: the logical value looks the same, but it belongs to a different suspension transaction. Loop 9 therefore requires:

foreign_binding = (
    request_id,
    generation,
    snapshot_sha256,
    suspension_epoch,
)

The suspension epoch is monotone per request attempt. It does not replace the M5.1 generation or digest; all four fields must match.

Exact Preservation, Recompute, And Hybrid Rebuild

“Preemption” names a scheduler event, not one recovery mechanism.

For request r, two planning costs are:

C_recompute(r)
    ~= model_cost([T_ready, T_target))
       + allocation_and_queue_overhead

C_preserve(r)
    ~= KV_bytes_to_preserve / effective_write_bandwidth
       + KV_bytes_to_restore / effective_read_bandwidth
       + synchronization_and_staging_overhead

The commonly written 2 * KV_bytes / bandwidth is only the symmetric-link special case. It is not a latency prediction: directions may have different bandwidths, transfers can overlap, recomputation may batch, and the request may never resume.

Deriving The Legal Resume Frontier

Let T_target be the semantic frontier frozen by the preemption intent. For an ordinary decoding request under M5.1’s first-token convention:

T_target
    = committed_kv_tokens
    = computed_tokens
    = prompt_tokens + emitted_outputs - 1

Let T_ready be the longest exact, identity-matched, ready prefix supplied by preservation, exact prefix reuse, or promotion:

0 <= T_ready <= T_target

Every row below T_ready is already exact. Every row at or above T_target would cross the frozen semantic state. Therefore the only legal rebuild suffix is the set difference:

R_rebuild = [T_ready, T_target)
recompute_overhead_tokens = T_target - T_ready

The three cases follow directly:

Rebuild execution restores K/V; it does not emit output, advance the semantic emitted/computed/committed frontiers, or debit client fairness a second time. Loop 8’s authoritative service counter remains unique completed semantic work. Runtime cost is still visible through a separate recompute_overhead_tokens or resource-usage ledger.

Foreign Readiness Is A Conjunction

A resume ticket is valid only when every required fact is current:

resume_ready(r) =
    current_request_generation(r)
    and matching_suspension_epoch(r)
    and release_confirmed(r)             # M5.3
    and allocation_ready(r)              # M5.3
    and exact_cache_ready_or_rebuilt(r)   # M5.3 + execution
    and promotion_ready_if_required(r)    # M5.5
    and all_required_layers_ready(r)      # M5.5
    and placement_ready(r)                # M5.6

This conjunction explains why prefix_hit=True is insufficient. A prefix can be exact but not resident. It can be promoted to a worker whose placement generation is stale. Most layers can be ready while one required layer remains in flight. The scheduler consumes those facts; it does not perform their transactions.

Conceptual derivation:

def derive_resume_ticket(snapshot, intent, receipts):
    key = (
        intent.request_id,
        intent.generation,
        intent.snapshot_sha256,
        intent.suspension_epoch,
    )
    current = [receipt for receipt in receipts if receipt.binding == key]

    require(snapshot.lifecycle != "CANCELLED")
    require(snapshot.identity == intent.logical_identity)
    require(ready(current, owner="M5.3", kind="release"))
    require(ready(current, owner="M5.3", kind="allocation"))
    require(ready_if_requested(current, owner="M5.5", kind="promotion"))
    require(all_required_layers_ready(current))
    require(ready(current, owner="M5.6", kind="placement"))

    T_ready = exact_ready_prefix(current, intent.fallback)
    require(0 <= T_ready <= intent.semantic_target_tokens)

    return ResumeTicket(
        binding=key,
        rebuild_interval=(T_ready, intent.semantic_target_tokens),
        ordinary_next_frontier=intent.semantic_target_tokens,
    )

No call in this sketch copies K/V, allocates a block, promotes a tier, or places a worker. It validates facts and publishes policy output.

Cancellation Wins By Generation

M5.1 cancellation publishes a terminal successor generation. Suppose preemption intent (r,g,S,e) is in flight and cancellation publishes (r,g+1,S_cancelled). A later preservation or release result for (r,g,S,e) may still be useful for idempotent physical cleanup, but it is stale for scheduling:

old receipt cannot:
    make generation g+1 runnable
    create a resume ticket
    publish free capacity into a decision bound to generation g+1
    advance output, cache, or fairness frontiers

The stronger rule is “cancellation wins by successor generation,” not “the last callback wins.”

Failed Preservation Needs An Explicit Fallback Matrix

PreservationResult(status=FAILED) is not a cache-ready result. The policy must choose one of four explicit outcomes:

Falling back to recompute without immutable token history is invalid. Marking the failed receipt ready is invalid. Reusing a receipt from an earlier suspension epoch is invalid even if all token frontiers are unchanged.

Victim Selection Is A Fairness And SLO Policy

Possible victim scores include largest resident bytes, lowest recompute cost, lowest priority, youngest request, least recent service, longest remaining estimate, or lowest prefix-reuse value. Each optimizes a different objective. The victim record should therefore retain the score inputs and tie-break, not only the selected request ID.

Evicting the largest request may free the most state while discarding the most work. Choosing the cheapest request repeatedly may create a preemption loop. Priority selection can starve lower tiers. Loop 8’s client-service and liveness counters remain active across suspension; neither arrival time nor TTFT clock restarts at resume.

FastServe And Pinned vLLM Use Different Concrete Paths

FastServe combines token-level preemption with skip-join MLFQ and a distributed K/V cache manager. The paper’s architecture makes the separation between scheduler policy, K/V management, and execution visible:

By contrast, pinned vLLM v0.23.0 uses a concrete recomputation path in its V1 scheduler: when allocate_slots cannot satisfy a running request, the scheduler chooses a victim, calls _preempt_request, frees K/V and encoder cache state, resets num_computed_tokens to zero, marks the request PREEMPTED, increments its preemption counter, and prepends it to the waiting queue. On later admission, a preempted request is classified as resumed and recomputes its required frontier.

That source trace is a pinned runtime observation, not the universal definition of preemption. Connector-backed remote K/V readiness in the same source has separate waiting states and callbacks, reinforcing the broader rule that physical readiness and scheduler intent are different objects. Behavior outside tag v0.23.0 is not implied.

Executable Preemption And Resume Oracle

The Loop 9 evidence fixture exercises eight contracts:

exact preservation        -> empty rebuild [6,6), then ordinary [6,7)
full recomputation         -> rebuild [0,6), semantic service delta 0
partial exact prefix       -> rebuild [4,7), then ordinary [7,8)
failed preservation        -> explicit recompute fallback [0,5)
cancellation race          -> all old-generation receipts stale
repeated preemption        -> epoch-10 receipt cannot satisfy epoch 11
promotion in flight        -> no resume ticket
release in flight          -> no reclaimed capacity and no resume ticket

The checked-in report contains five resumable cases, three stale receipts, and zero semantic service published during rebuild. Twenty negative mutations reject wrong owners, missing binding fields, invalid frontiers, failed fallback, pending-capacity publication, stale generation/epoch acceptance, recompute-as-fairness-service, and production claim inflation.

Run it with:

python3 docs/numinens-evidence/m5-2-continuous-batching/preemption_resume_oracle.py
python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop9_preemption_resume.py'

This is synthetic contract evidence, not a production scheduler, allocator, offload implementation, placement implementation, latency benchmark, vLLM policy reproduction, or FastServe performance reproduction.

The runtime telemetry must preserve the same distinctions:

preemption intents by reason, mode, policy, client, and suspension epoch
matching release results and physically reclaimed bytes
preservation/promotion failures and fallback choice
recompute overhead tokens, separate from semantic service tokens
resume latency from original clocks, not a restarted TTFT
stale generation, digest, placement, layer, and suspension-epoch receipts
requests preempted repeatedly and SLO violations after resume

Without these counters, aggregate throughput can look healthy while one client repeatedly loses state or the allocator counts capacity that no successful release has published.

0x0D Pinned Runtime Source Trace And Multi-Policy Oracle

The preceding sections derived a scheduler contract from papers, M5.1 state, and synthetic counterexamples. A production source tree answers a different question: where do those concerns appear in one concrete implementation, and where does the implementation deliberately combine objects that this article separates for reasoning?

This section pins that answer to vLLM V1 tag v0.23.0, Git object 0fc695fc6d1d82e9a5ac6835ac8e4e1c83703665. It does not describe “vLLM in general,” and it does not claim that the local Python oracle executes vLLM. Every runtime statement below names a file, symbol, and marker in that frozen revision.

Two Source Files, One Immutable Revision

The evidence directory contains two unmodified Apache-2.0 snapshots:

runtime_source_pin.json freezes the tag object, complete file hashes, byte counts, upstream URLs, and 35 line markers. The offline verifier reads the snapshots as text; it neither imports vLLM nor depends on a moving web page. A tag name alone is insufficient evidence because a prose claim can silently drift to another symbol or line while still linking to a valid repository.

The source-marker contract is:

revision identity
    + complete source-file identity
        + symbol/line marker identity
            -> version-specific runtime observation

It is not:

one source observation
    -> universal scheduler mechanism
    -> exact behavior of another release or configuration

Source Trace: Running, Waiting, Remote, And Preempted

At Scheduler.schedule() line 340, the pinned source explicitly says that the scheduler has no separate scheduler-level “decoding phase” and “prefill phase.” Instead, each request exposes a computed frontier and a target token frontier. The running-path gap is conceptually:

Delta_run
    = num_tokens_with_spec
      + num_output_placeholders
      - num_computed_tokens

Delta_run
    <- min(Delta_run,
           configured long-prefill threshold when active,
           remaining scheduled-token budget,
           remaining model-length bound)

That expression is more general than “schedule one decode token.” A running request can be catching up prefill, ordinary decode, or specialized frontier work. The phase label is derived from request state; it is not the loop that selects the request.

The control path then has distinct passes:

The waiting-path gap differs slightly because local prefix hits, external prefix hits, resumed work, and async transfer can change its starting point:

T_wait_start
    = local exact computed tokens
      + external exact computed tokens

Delta_wait
    = request.num_tokens - T_wait_start

Delta_wait
    <- min(Delta_wait,
           configured long-prefill threshold when active,
           remaining scheduled-token budget)

When async remote loading is required, the pinned source can allocate for the transfer, set request.status = WAITING_FOR_REMOTE_KVS, and keep the request out of runnable service until the connector promotes its status. The source therefore supplies concrete evidence for Loop 9’s broader rule:

Knowing that matching remote K/V exists is not the same as knowing that the request is ready for this iteration.

Preemption Is A Source-Specific State Transition

On running-path allocation failure, the pinned FCFS path removes the tail of the running queue. Its priority path chooses:

max(running, key=(priority, arrival_time))

Because lower numeric values mean earlier handling in SchedulerConfig, this max is the least-favored running request, with later arrival breaking a tie. If the victim had already been placed in the current output, its scheduled rows and budgets are removed before the source continues.

Scheduler._preempt_request() then performs a concrete recomputation policy:

self.kv_cache_manager.free(request)
self.encoder_cache_manager.free(request)
request.status = RequestStatus.PREEMPTED
request.num_computed_tokens = 0
request.num_preemptions += 1
self.waiting.prepend_request(request)

This is an exact source trace for vLLM v0.23.0. It is not the generic PreemptionIntent -> ReleaseResult -> PreservationResult -> ResumeTicket interface derived in Loop 9. The source performs some of those actions synchronously inside one runtime owner. The conceptual interface separates them so asynchronous preservation, delayed release, another allocator, or another runtime cannot inherit a false success assumption.

The distinction also explains an otherwise surprising policy result. With zero free logical rows, running queue [A,B], priority(A)=10, and priority(B)=1:

source-shaped FCFS failure:
    tail victim = B
    B releases four teaching rows
    A schedules one row

source-shaped PRIORITY failure:
    least-favored victim = A
    current request preempts itself
    no running row is scheduled

The local oracle reproduces this decision shape with logical row counts. It does not call KVCacheManager, model block granularity, connectors, LoRA limits, encoder budgets, speculative lookahead, or worker execution. It is a source-shaped teaching policy, not an exact vLLM replay.

Configuration Fields Interact; They Are Not One Batch Size

The pinned SchedulerConfig exposes multiple controls with different jobs:

The config validates cross-field constraints. For example, max_num_batched_tokens >= max_num_seqs; concurrent partial prefills require chunked prefill; and the long-prompt threshold cannot exceed model length. Consequently, a benchmark that reports only “batch size” has not frozen the scheduler contract.

Conceptual Records Do Not Mirror One Runtime Class

The Transformer System records are an accounting decomposition, not a proposed rename of vLLM classes:

The last row is especially important. The pinned source comments that it advances the computed count after scheduling so the next prefill chunk can be scheduled promptly, while rejected speculative rows can be corrected later. That is a concrete runtime optimization and internal-state contract. This article’s evidence model keeps planned, completed, and authoritative service publication separate so a failed execution cannot appear as completed fairness service. The two models can describe the same runtime without being field-for-field identical.

Six Policies, One Immutable Decision Surface

runtime_policy_fixture.json freezes four scheduler snapshots. Six policies consume those same visible fields:

Every policy declares exact_runtime_reproduction=false, evidence basis, and a deterministic tie-break. Every emitted row contains only request-local logical intervals, work class, budget use, queue transitions, and logical preemption records. Physical block IDs fail validation.

The four scenarios expose different questions:

Identical results in one row do not make two policies equivalent. A fixture is useful only where its state activates a policy difference; another state can make different rules select the same intervals.

Reconcile Loop 3; Do Not Reimplement It

Loop 3 already answers one narrow historical question: fixed cohort versus iteration refill on the A/B/C first-token-correct workload. Loop 10 does not create a second simulator and hope the metrics agree. It freezes and verifies the exact file hashes:

batching_transition_workload.json
    sha256 = 04cec4f7...6d0723

batching_transition_report.json
    sha256 = 0ec36280...5824d

It then reads the checked-in report and reasserts:

That is exact artifact reconciliation, not duplicated model behavior. The Loop 10 snapshots compare next-iteration decisions; they do not replace the Loop 3 multi-iteration occupancy replay.

Executable Runtime And Policy Oracle

The Loop 10 evidence surface is:

runtime_source_pin.json
pinned/vllm-v0.23.0/scheduler.py
pinned/vllm-v0.23.0/scheduler_config.py
runtime_policy_fixture.json
runtime_policy_oracle.py
runtime_policy_report.json
invalid_runtime_policy_fixtures.json
test_loop10_runtime_policy.py

Run it offline with:

python3 docs/numinens-evidence/m5-2-continuous-batching/runtime_policy_oracle.py
python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop10_runtime_policy.py'

The checked-in report contains 35 verified markers, six policies, four scenarios, source-shaped FCFS and priority preemption decisions, remote-K/V blocking, recompute-versus-semantic-service accounting, and exact Loop 3 hash reconciliation. Twenty negative mutations reject source/tag/hash/marker drift, runtime-equivalence overclaim, missing claim limits, nondeterministic policy, stale source binding, illegal budget/frontier/readiness state, physical block leakage, and legacy-report drift.

This oracle proves that declared inputs reproduce declared logical decisions. It proves no latency, throughput, GPU utilization, allocator fidelity, production optimality, or vLLM/Sarathi-Serve behavioral equivalence.

0x0E Full Paper Contracts, Sensitivity, And Failure Closure

The preceding sections reconstructed mechanisms one at a time. That is the right way to understand an algorithm, but it creates one final comparison hazard: the names now sit beside one another even though they do not solve the same optimization problem.

ORCA selects request iterations. SARATHI shapes offline prefill/decode work. Sarathi-Serve protects ongoing token generation under a profiled budget. FastServe prioritizes jobs with preemption. VTC protects weighted client service. Preble values exact prefix reuse and distributed load. LayerKV admits prefills against predicted decode slack and layer residency. Pinned vLLM is a source implementation, not a paper objective.

Loop 11 therefore asks a stricter question:

Before two methods, results, or policy traces are compared,
have their decision unit, protected identity, visible state,
unknown future, objective, metric, assumptions, foreign owners,
and evidence class all been preserved?

A Method Name Is Not A Policy Contract

For method m, define the comparison contract:

$$\mathcal K_m = (G_m,I_m,S_m,D_m,U_m,O_m,M_m,A_m,F_m),$$

where:

K_m=(G,I,S,D,U,O,M,A,F)

G_m = scheduling granularity
I_m = protected identity
S_m = online-visible state
D_m = decision output
U_m = unknown future state
O_m = primary objective
M_m = metric and denominator
A_m = assumptions or theorem premises
F_m = foreign owner dependencies

Two methods can share a mechanism coordinate and still have different contracts. Both SARATHI and Sarathi-Serve chunk prompts, but only the latter orders running decodes, partial prefill, and new admission under a profiled online token budget. Both FastServe and VTC address unfair outcomes, but the former protects jobs through MLFQ promotion while the latter protects clients through weighted service counters.

The table is not a taxonomy by slogan. Every row in paper_contract_registry.json also freezes online state, decision output, required assumptions, non-claims, and a specific source version. Removing any one of those fields changes which implementation or theorem is being discussed.

Comparison Coordinates Come Before Result Numbers

A source-reported result is another contract:

$$\mathcal R = (V,C_s,\Theta,H_{\parallel},W,B,M,L,Q,Y,E),$$

with source version V, source location C_s, model Theta, hardware and parallelism H_parallel, workload W, baseline B, metric/denominator M, latency or SLO condition L, load coordinate Q, reported value Y, and evidence class E. The registry also retains coordinate-completeness and local-reproduction flags. Source identity is mandatory provenance, but a comparison does not require both results to come from the same paper.

Renderer-safe result-contract fallback:

R=(V,C_s,Theta,H_parallel,W,B,M,L,Q,Y,E)

The article permits a measured comparison only when every coordinate in the declared comparison set C is equal:

$$Comparable(r_a,r_b) = \bigwedge_{c\in\mathcal C} c(r_a)=c(r_b).$$

Renderer-safe comparison rule:

comparable measured results require equality of:
    model
    hardware and parallelism
    workload and arrivals
    baseline
    metric, unit, denominator, and percentile
    latency/SLO target
    load coordinate
    evidence class

paper name or a shared word such as "throughput" is insufficient

The source registry intentionally preserves incompatible headline results:

Every value is source-reported and not reproduced here. The executable registry finds zero result pairs with identical comparison coordinates. Therefore it produces no speedup ordering. This is not a weakness in the audit; it is the technically valid result.

Deriving The One-Control Sensitivity Surface

The sensitivity suite does not simulate the eight systems. This is a synthetic fixture, not a serving benchmark. It varies one declared control in a shared analytical fixture and asks which local ledger must change.

Let prompt length be S, nominal chunk size C, ready decode rows D, token budget B_tok, and sequence budget B_seq. The number of chunk invocations is:

$$M=\left\lceil\frac{S}{C}\right\rceil.$$

For actual chunk starts s_m, logical causal work and cross-invocation history exposure are:

$$P_{causal}=\frac{S(S+1)}{2}, \qquad R_{hist}=\sum_{m=0}^{M-1}s_m.$$

One hybrid iteration can piggyback at most:

$$D_{piggy} = \min\left( D, [B_{tok}-\min(C,S)]_+, [B_{seq}-1]_+ \right).$$

The first subtraction reserves token rows for one prefill chunk. The second reserves one selected sequence for that chunk. This is a shape ledger, not a latency model.

For logical reservation ceiling H, already reserved rows R_live, and one forecast of r_hat rows per new request, the maximum number of additional reservation intents under this simplified equal-forecast case is:

$$A_{intent} = \left\lfloor\frac{H-R_{live}}{\hat r}\right\rfloor.$$

A_intent is not a physical admission count. M5.3 may still reject an allocation. For exact prefix hit H_hit, uncached prompt work is simply:

$$U=S-H_{hit},$$

but only after M5.3 proves the hit’s identity and availability.

The base fixture is:

S=16, C=4, D=4
B_tok=8, B_seq=8
logical K/V row bytes=131072
logical reservation: 8 used of 28, forecast 5 rows/request
priority: low=4, high=0, aging quantum=2
client offered events: A=8, B=4
exact prefix hit=0, foreign_ready=true

It derives 4 chunks, 136 causal pairs, 24 history-exposure rows, 3 MiB of logical K/V exposure proxy, 4 decode piggyback rows, 4 reservation intents, and first aging crossover at tick 8.

The output-distribution row is a metamorphic check: the hidden-output sweep cannot change online projection. Hidden realized lengths change the offline workload outcome, but cannot change the online plan projection. The two chunk rows are the design counterexample: smaller chunks improve same-iteration piggyback room in this shape while increasing invocation and history-exposure proxies. No scalar “best chunk” follows.

Alternative Methods Change Different Coordinates

The contract registry supports design choices, not a universal winner:

fixed cohort barriers dominate
    -> ORCA's iteration boundary is relevant

decode weight-read inefficiency or pipeline bubbles dominate
    -> SARATHI's decode-maximal shape is relevant

ongoing TBT is harmed by eager prefills
    -> Sarathi-Serve's profiled token budget is relevant

job head-of-line blocking dominates
    -> FastServe's skip-join/preemption contract is relevant

one tenant dominates weighted service
    -> VTC's client counter contract is relevant

shared prompt work and distributed load dominate
    -> Preble's exact-prefix and placement contract is relevant

TTFT queueing is limited by full-stack K/V residency
    -> LayerKV's layer-ready scheduling interface is relevant

These branches can compose only after ownership is reconciled. Combining VTC selection with FastServe preemption changes VTC’s theorem assumptions. Combining Sarathi-Serve admission with LayerKV offload makes predicted layer readiness part of the batch-feasibility path. Combining Preble placement with chunked prefill requires both exact prefix facts and a local token budget. Composition is a new contract, not the sum of paper names.

Fifteen Failure Classes Close At Different Boundaries

The cumulative failure registry hash-binds Loops 3-10 rather than reimplementing their oracles. Fourteen prior rejection cases are consumed by identity. Four new Loop 11 rules close comparison-specific errors.

One recurring mistake is asking the scheduler to repair a fact it does not own. A high-priority request cannot execute with remote K/V still in flight. A large exact prefix hit does not imply residency on the chosen worker. A LayerKV-style positive slack estimate cannot make an offloaded layer visible. The policy can choose only among work whose foreign preconditions are already valid.

Executable Paper, Sensitivity, And Failure Contract

Loop 11 adds:

paper_contract_registry.json
source_reported_result_registry.json
paper_sensitivity_failure_fixture.json
paper_sensitivity_failure_oracle.py
paper_sensitivity_failure_report.json
invalid_paper_sensitivity_failure_fixtures.json
test_loop11_paper_sensitivity_failure.py

generic_policy_ranking_allowed=false

Run it with:

python3 docs/numinens-evidence/m5-2-continuous-batching/paper_sensitivity_failure_oracle.py --write-report
python3 -m unittest discover \
  -s docs/numinens-evidence/m5-2-continuous-batching \
  -p 'test_loop11_paper_sensitivity_failure.py'

The report contains eight paper/runtime contracts, nine source-reported result records, ten one-control cases over nine axes, fifteen failure classes, thirteen immutable file bindings, fourteen prior rejection references, and zero cross-paper measured-result pairs with equal comparison coordinates. Twenty-eight negative mutations reject source drift, missing contract fields, local-measurement overclaim, universal ranking, theorem transfer, owner collapse, hidden-truth leakage, compound sensitivity, expectation drift, and unknown failure evidence.

That result is deliberately narrow. The oracle proves the comparison and accounting contract. It does not measure a runtime, implement the papers, calibrate a predictor, reproduce a benchmark, or establish that one policy is best.

0x0F Failure Modes

The recurring pattern is a missing owner. If latency fails, ask which decision point owned it:

admission
prefill/decode priority
chunk size
KV budget
prefix reuse
worker placement
backend/kernel dispatch

M5.2 only covers the first four. Later M5 articles cover the rest.

0x10 Boundary To The Rest Of M5

M5.2 ends with the scheduler loop. The next articles should not repeat it; they should plug into it.

That is the systems arc:

M5.1:
    define the state object

M5.2:
    schedule the next iteration under that state

M5.3-M5.8:
    change allocation, reuse, retention, residency/retrieval,
    placement, or architecture

0x11 What This Article Claims

Source-local claims:

• A26 explains static batching failure, ORCA-style iteration-level scheduling, selective batching, SARATHI chunked prefill, and the prefill/decode fusion-vs-separation split.
• A24 defines TTFT, TPOT/TBT, throughput, and goodput as the serving metric vocabulary.
• M5.1 defines KV cache lifecycle, active KV trajectories, and why request state makes serving a scheduler problem.

Externally verified claims:

• ORCA frames generation as a multi-iteration workload and proposes iteration-level scheduling plus selective batching.
• PagedAttention/vLLM identifies dynamic KV cache growth, fragmentation, and duplication as limits on high-throughput batching.
• SARATHI uses chunked-prefills and decode-maximal batching so decodes piggyback on compute-heavy prefill chunks.
• Sarathi-Serve Algorithm 3 places running decodes before partial prefill and new requests under an SLO-profiled token budget.
• SARATHI and Sarathi-Serve identify repeated access to earlier-chunk K/V, small-chunk efficiency, and fixed invocation overhead as chunk-size costs.
• DistServe separates TTFT and TPOT as phase-specific latency objectives and optimizes goodput under both.
• SCORPIO separates predictor-supported TTFT deadline ordering/rejection from TPOT admission and batching guards; its mechanisms and reported gains remain paper-specific.
• vLLM’s scheduler and tuning documentation expose production guardrails for this same problem: chunked prefill, full-input admission checks, KV watermarks, decode-prioritized batching, and preemption/recompute when KV cache is insufficient.
• Preble shows that distributed prefix-aware scheduling must balance reusable prompt work with fairness rather than always selecting the largest prefix hit.
• FastServe uses token-level preemption, skip-join MLFQ queue entry, feedback demotion, and starvation-triggered promotion to reduce head-of-line blocking and protect waiting jobs.
• VTC defines weighted input/output-token service per client, lifts newly active counters to prevent idle credit, and proves a conditional service-difference bound for continuously backlogged clients.
• VTC’s paper bound follows from a maximum one-step counter charge U=max(w_p L_input,w_q M) and two endpoint counter-spread terms.
• Preble’s local waiting policy groups requests by cached prompt percentage and allocates selections across groups; this mechanism is not a VTC client-service theorem.
• LayerKV demonstrates layer-wise KV allocation/offload coupled to SLO-aware scheduling, adding a layer-residency horizon beneath iteration scheduling.
• At pinned tag v0.23.0, vLLM V1 frees a preempted request’s K/V state, resets its computed-token frontier to zero, marks it preempted, increments a preemption counter, and returns it to the waiting queue for later recomputation.
• At the same pinned revision, Scheduler.schedule() traverses running work before waiting work, skips waiting requests still blocked on remote K/V, and does not run the waiting pass after a running-path preemption.
• vLLM v0.23.0 exposes token-row, scheduled-token, sequence-count, chunking, partial-prefill, policy, and full-input-reservation controls as distinct configuration fields rather than one batch-size knob.
• ORCA, SARATHI, Sarathi-Serve, FastServe, VTC, Preble, and LayerKV expose different scheduling units, objectives, metrics, assumptions, and foreign system dependencies in their primary sources.
• SARATHI’s P:D sensitivity, Sarathi-Serve’s profiled token budget, FastServe’s job-level MLFQ, VTC’s client-service theorem, Preble’s prefix-aware hierarchy, and LayerKV’s predicted layer-ready admission are paper-specific contracts rather than variants of one generic policy.
• The headline performance and theorem values in the Loop 11 result registry are source-reported under distinct model, hardware, workload, metric, SLO, baseline, and load coordinates.
• Anyscale’s metrics documentation defines TTFT, TPOT/ITL, throughput, and goodput as separate serving metrics and frames goodput as SLO-satisfying work.

Rewrite interpretation:

• Continuous batching is best understood as repeated, versioned selection of legal request-token intervals, not merely dynamic tensor batching.
• IterationPlan is scheduler policy output; packing, execution, and completed state publication are separate stages.
• WorkloadManifest, SchedulerState, IterationPlan, and IterationResult have separate writers and validity windows.
• Legal ordinary work begins at the computed frontier; prefill remains inside the prompt and decode processes exactly one already-emitted token.
• Policy replay binds decision, state, policy, request-generation, and M5.1 snapshot versions.
• Fairness service is debited from completed work rather than planned rows.
• Fairness claims retain separate identity, eligibility interval, service cost, publication event, and guarantee fields.
• FastServe job-liveness promotion, age-adjusted priority, cache-hit group quotas, and VTC client service are distinct contracts rather than interchangeable fairness labels.
• completion_reconciled_vtc_teaching_v1 uses provisional selection service and completed publication service; it is intentionally not presented as VTC Algorithm 2.
• A policy fails the Loop 8 gate when a continuously eligible protected identity completes zero service events, even if aggregate throughput remains high.
• Fairness and SLO outcomes are published together because equal aggregate goodput can conceal client-specific deadline failure.
• Fixed-batch idle slot-iterations follow from frozen cohort lifetime, while iteration refill can reuse membership only at a completed iteration boundary.
• Queue delay, logical slot occupancy, and measured GPU utilization are distinct quantities.
• ORCA’s paper-specific n_rsrv reservation counter, modern scheduler reservation intent, and M5.3 physical allocation result are separate objects.
• PackedIteration is derived execution metadata with stable offsets, positions, request generations, phases, and logical cache handles; it is not a replacement for IterationPlan.
• Shared row-wise projection, request-local segmented attention, stable merge order, and route-based scatter form the selective-batching execution contract.
• Token rows, request generations, and future logical reservation are separate budget dimensions.
• M5.2 consumes the M5.1 logical bytes-per-committed-row ABI rather than re-deriving cache architecture.
• Ordinary future append rows follow the M5.1 first-token frontier: max(forecast total outputs - emitted outputs, 0) for an open resumed stream.
• Maximum, point, quantile, and watermark reservation policies expose different over-reservation, under-reservation, rejection, and recovery outcomes.
• Realized output length is available only to offline evaluation or an explicitly labelled fixture-only oracle comparator.
• Reservation estimate, allocation request, physical allocation result, preemption intent, and physical release result are distinct records.
• Planning is not execution, and reservation is not physical allocation.
• Preemption intent, physical release result, preservation result, and resume ticket are separate versioned records with different writers.
• The foreign receipt key includes request ID, M5.1 generation, snapshot digest, and a monotone suspension epoch so repeated preemption cannot accept an older transaction’s readiness.
• The legal exact rebuild interval is [T_ready,T_target), where T_ready is a matching exact prefix and T_target is the frozen committed semantic frontier.
• Recompute overhead restores K/V without publishing new output, advancing semantic frontiers, or duplicating Loop 8 fairness service.
• A resume ticket requires the conjunction of current identity, confirmed release/allocation, exact cache state, required promotion/layer readiness, and placement readiness.
• Cancellation publishes a successor generation; delayed receipts from the prior generation may finish cleanup but cannot schedule work.
• Physically reclaimed bytes become scheduler facts only through a matching successful M5.3 release result, never through preemption intent.
• Source pinning requires a revision object, full-file hash, byte count, and symbol marker; a tag link alone does not bind article prose to one code path.
• The pinned source’s mutable request state, allocator calls, connector metadata, and SchedulerOutput span several conceptual owners rather than mapping one-to-one onto SchedulerState, IterationPlan, and IterationResult.
• The Loop 10 vLLM-shaped policies reproduce declared queue-pass and victim-selection decisions only; they do not reproduce production allocation, transfer, execution, or performance.
• Recompute rows consume logical scheduling budget while publishing zero new semantic service, and a request in WAITING_FOR_REMOTE_KVS remains ineligible until foreign readiness changes.
• Loop 3 occupancy metrics are consumed by exact artifact hash and metric reconciliation rather than by a second implementation of the same simulator.
• A paper comparison contract binds scheduling granularity, protected identity, visible state, decision output, unknown future, objective, metric, assumptions, and foreign owner dependencies.
• A measured-result comparison requires equal model, hardware/parallelism, workload, baseline, metric/denominator, latency or SLO target, load coordinate, and evidence class.
• Loop 11 one-control sensitivity derives local changes in chunk exposure, piggyback room, reservation intent, priority crossover, offered client mix, uncached work, and eligibility without converting them into latency or optimality claims.
• Alternative policies should be selected by the failure pressure and owner contract they address; composing mechanisms creates a new contract whose assumptions must be re-audited.
• The cumulative failure closure consumes prior artifacts by hash and rejection-case identity instead of reimplementing Loops 3-10.
• Chunked prefill preserves one causal triangle because committed history plus the in-chunk causal prefix equals the full [0,i] visibility set.
• The logical pair total telescopes to S(S+1)/2 for every legal chunk partition.
• sum(chunk_start_frontier) is a cross-invocation K/V reload proxy, not measured HBM traffic.
• SARATHI’s profiled prefill anchor, Sarathi-Serve’s stall-free token budget, and pinned vLLM’s running-then-waiting frontier catch-up are separate policy contracts.
• The Loop 6 starvation traces are synthetic class-progress counterexamples and do not replace Loop 8 fairness definitions.
• TTFT deadlines begin at original arrival, next-token deadlines begin at the previous output emission, and admission or retry cannot reset either clock.
• Factual headroom and predicted slack are separate; the latter requires a named prediction model and calibration scope.
• Offered requests close into SLO-valid completion, completed SLO miss, rejection, or unfinished state at the observation boundary.
• Request throughput, request goodput, emitted-token throughput, SLO-valid token goodput, and attainment fractions retain different units and denominators.
• Completion-conditioned attainment is diagnostic and cannot replace offered-load attainment under rejection or unfinished backlog.
• Tail percentiles require an explicit estimator, sample count, population, and reporting gate; mean-only evidence cannot support a p99 claim.
• When finite-window realized demand exceeds declared service slots, ordering cannot avoid an explicit overload outcome.
• Chunked prefill is the local scheduling bridge between pure continuous batching and later P/D separation.
• PagedAttention and continuous batching should be taught as adjacent mechanisms, not as synonyms.

Uncertain or implementation-specific:

• The best chunk size is workload and hardware dependent.
• Production chunk overhead depends on kernel selection, graph capture, matrix tiling, cache behavior, parallelism, and mixed-batch shape; the Loop 6 byte ledger is not calibrated.
• vLLM scheduling behavior outside pinned tag v0.23.0 is not implied by the source trace in this article.
• Production slack quality depends on workload-specific prediction calibration, drift, batch interaction, and foreign readiness.
• The Loop 7 percentile sample thresholds are an article transparency rule, not a universal statistical guarantee.
• The four-live overload cap is a synthetic accounting policy, not a production recommendation or capacity result.
• Production input/output service weights require calibration for the model, runtime, batch shapes, hardware, and objective; Loop 8’s 1:2 weights are synthetic.
• The priority-aging and 2:1 reuse-group traces establish progress only for their declared fixtures; they are not universal bounded-wait or fairness proofs.
• The completion-reconciled VTC teaching adaptation has no transferred VTC theorem and no new bound is claimed.
• FastServe’s source-reported latency improvements and VTC’s source-reported fairness/performance results are not reproduced by the Loop 8 oracle.
• The Loop 9 cost equations omit overlap, topology, queue interaction, cache-block granularity, copy setup, and kernel effects; they are policy ledgers rather than latency predictions.
• The Loop 9 oracle is a synthetic record/state contract and does not reproduce vLLM, FastServe, an allocator, an offload engine, or a placement runtime.
• The Loop 10 logical allocation-row model omits cache block size, prefix-block sharing, connector reservations, encoder state, LoRA limits, speculative lookahead, hybrid cache groups, and worker effects.
• The Loop 10 six-policy matrix establishes decision divergence only on four synthetic snapshots; it does not rank policies or establish production latency, throughput, fairness, or optimality.
• The Loop 11 source-reported results are intentionally not cross-paper ranked; none of their complete comparison-coordinate vectors are equal.
• Loop 11’s sensitivity values are analytical consequences of one synthetic fixture, not calibrated responses of ORCA, SARATHI, Sarathi-Serve, FastServe, VTC, Preble, LayerKV, or vLLM.
• Results from a composed policy cannot inherit a component paper’s theorem, SLO statement, or performance result without a new proof or measurement contract.
• The right admission policy depends on whether the runtime supports paging, preemption, prefix reuse, priority tiers, and request cancellation.
• Benchmark numbers from papers should be treated as source-reported unless reproduced in this repository.

0x11A Formula, Unit, And Renderer-Safe Registry

The display equations above are the readable derivations. This registry is the publication fallback and audit surface: it gives every display equation one stable identifier, preserves the same operation in plain text, and declares the unit family and owner. It is not a second derivation and does not transfer an M4, M5.1, M5.3, M5.5, or M5.6 mechanism into M5.2.

Frontiers, legality, and iteration budgets

F01 prefill_legality: c_r < p_r and e_r = 0
F02 prefill_interval: c_start[r,n] = c_r < c_end[r,n] <= p_r
F03 decode_legality: e_r >= 1 and c_r = p_r + e_r - 1
F04 decode_interval: [c_start,c_end) = [c_r,c_r+1)
F05 token_budget_example: K_used = 1 + 1 + 2 = 4 <= K_token = 4
F06 sequence_budget_example: N_used = 3 <= K_seq = 3
F07 emitted_transition: e_after = e_before + I[decode row completed] + I[prefill first reaches p_r]

Static batching and selective-batching tensors

F08 frozen_batch_iterations: I_batch = max_r G_r
F09 slot_work: W_available = B*max_r(G_r); W_useful = sum_r G_r
F10 idle_slot_work: W_idle = B*max_r(G_r) - sum_r G_r
F11 slot_utilization: U_slot = sum_r(G_r) / (B*max_r(G_r))
F12 request_row_count: q_i = computed_end_i - computed_start_i
F13 packed_row_count: Q_tot = sum_i q_i
F14 packed_offsets: o_0 = 0; o_(i+1) = o_i + q_i
F15 rowwise_concat: f(concat(X_0,...,X_N-1)) = concat(f(X_0),...,f(X_N-1))
F16 packed_projection_row: (X_pack W)_r = X_pack,r W = X_i,local(r) W
F17 visibility_predicate: visible(r,s) = (i=j) and (u_s<=p_r) and available_i(u_s)
F18 attention_mask: M_r,s = 0 when visible(r,s), else -infinity
F19 segmented_attention: O_i = softmax(Q_i K_i^T / sqrt(d_h) + M_i) V_i

Admission, future growth, and memory policy

F20 sequence_count: N_seq(I) = |I|
F21 scheduled_token_count: N_tok(I) = sum_(r in I) q_r
F22 committed_kv_bytes: M_r,committed = T_r * delta_M_KV,row
F23 active_kv_bytes: M_active(t) = sum_(r in A(t)) T_r(t) * delta_M_KV,row
F24 resumed_future_rows: A_hat_r = max(G_hat_r - E_r, 0)
F25 new_request_future_rows: A_hat_new_r = U_r + max(G_hat_r - 1, 0)
F26 future_kv_bytes: M_hat_r,future = A_hat_r * delta_M_KV,row
F27 reservation_error: epsilon_r = A_hat_r - A_star_r
F28 soft_capacity: C_soft = C_hard - W
F29 admission_test: R_(j-1) + A_hat_j <= C_soft

SLO clocks, outcomes, rates, tails, and overload

F30 first_token_deadline: d_first_r = a_r + tau_TTFT_r
F31 next_token_deadline: d_next_r,j = y_r,j-1 + tau_TBT_r for j >= 1
F32 factual_headroom: h_r(n) = d_r - n
F33 predicted_finish: f_hat_r(n;m) = n + c_hat_r(n;m)
F34 predicted_slack: s_r(n;m) = d_r - f_hat_r(n;m) = h_r(n) - c_hat_r(n;m)
F35 outcome_partition: N_off = N_valid + N_miss + N_rej + N_open
F36 request_rates: lambda_off=N_off/W; T_req=N_comp/W; G_req=N_valid/W
F37 token_rates: T_tok=sum_i(E_i)/W; G_tok=sum_i(q_i E_i)/W
F38 goodput_capacity: G_star=max{lambda: Pr_lambda[TTFT and TPOT valid] >= alpha}
F39 nearest_rank_quantile: Q_hat_p = x_(ceil(p*n))
F40 queue_recurrence: Q_(k+1) = max(0, Q_k + A_k - C_k)
F41 overload_boundary: D_W > C_W implies not all offered work can complete in W

Chunked prefill and decode-maximal batching

F42 chunk_partition: 0=s_0<s_1<...<s_M=S; c_m=s_(m+1)-s_m
F43 chunk_visibility_union: [0,s_m) union [s_m,i] = [0,i]
F44 chunk_causal_pairs: P_m = c_m*s_m + c_m*(c_m+1)/2
F45 telescoping_chunk_pairs: P_m = s_(m+1)*(s_(m+1)+1)/2 - s_m*(s_m+1)/2
F46 total_causal_pairs: sum_m P_m = S*(S+1)/2
F47 history_row_exposure: R_hist = sum_m s_m
F48 equal_chunk_exposure: R_hist = C*M*(M-1)/2
F49 history_byte_proxy: B_hist,proxy = R_hist * b_KV
F50 sarathi_batch_bound: B_paper = floor((M_G-M_S)/(L_max*m_KV))
F51 prefill_decode_ratio: P:D = C/(B_paper-1)

Fairness, liveness, reuse, and resident-state inputs

F52 paper_client_service: W_i(t1,t2) = w_p*n_p,i(t1,t2) + w_q*n_q,i(t1,t2)
F53 completed_event_service: W_i=sum_(e in C_i)c(e); c(e)=w_p*n_e for input rows or w_q*n_e for output rows
F54 mlfq_threshold_order: q_1 < q_2 < ... < q_m
F55 skip_join_queue: j_0 = min{j: q_j >= t_hat_init}
F56 vtc_counter_lift: c_B = max(c_B, min_(i in active)c_i) = max(0,4) = 4
F57 maximum_counter_charge: U = max(w_p*L_input, w_q*M)
F58 endpoint_counter_spread: max_i c_i - min_i c_i <= U
F59 service_difference_identity: W_f-W_g = [c_f(t2)-c_g(t2)] - [c_f(t1)-c_g(t1)]
F60 conditional_vtc_bound: |W_f(t1,t2)-W_g(t1,t2)| <= 2U
F61 aging_priority: p_eff(r,t) = p_base(r) - floor((t-a_r)/q_age)
F62 uncached_work: U_r,w = S_r - H_r,w
F63 starvation_predicate: Starved(g,[t1,t2]) = EligibleThroughout(g,[t1,t2]) and CompletedEvents_g(t1,t2)=0
F64 gpu_resident_input: M_GPU = sum_r sum_(l=1..L) M_resident(r,l)

Paper contracts and one-control sensitivity

F65 method_contract: K_m = (G_m,I_m,S_m,D_m,U_m,O_m,M_m,A_m,F_m)
F66 result_coordinates: R = (V,C_s,Theta,H_parallel,W,B,M,L,Q,Y,E)
F67 comparability: Comparable(r_a,r_b) = AND_(c in C) c(r_a)=c(r_b)
F68 chunk_count: M = ceil(S/C)
F69 sensitivity_pair_ledger: P_causal=S*(S+1)/2; R_hist=sum_m s_m
F70 piggyback_decode_rows: D_piggy=min(D, max(B_tok-min(C,S),0), max(B_seq-1,0))
F71 admission_intents: A_intent=floor((H-R_live)/r_hat)
F72 uncached_prefix_rows: U = S - H_hit

The unit contract is grouped because equations in one family share a semantic surface:

The machine-readable registry in docs/numinens-evidence/m5-2-continuous-batching/formula_registry.json binds these identifiers to the ordered display blocks and exact normalized LaTeX hashes. A changed equation, missing fallback, undeclared family, or unit owner drift fails the final publication audit.

0x12 Publish Gate

References

• M5.1 - Autoregressive Serving State: KV Cache Lifecycle and Scheduler Pressure
• M5.3 - KV Layout and Exact Reuse
• M5.5 - KV Retrieval, Offload, and Hierarchical Memory
• M5.6 - Prefill/Decode Disaggregation and K/V Placement
• Exploring the Transformer Series (24) - KV Cache Optimization
• Exploring the Transformer Series (26) - KV Cache Optimization: PD Separation or Merging
• ORCA: A Distributed Serving System for Transformer-Based Generative Models
• Efficient Memory Management for Large Language Model Serving with PagedAttention
• SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
• Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
• DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
• SCORPIO: Serving the Right Requests at the Right Time for Heterogeneous SLOs in LLM Inference
• FastServe: Fast Distributed Inference Serving for Large Language Models
• Fairness in Serving Large Language Models
• VTC paper PDF
• Preble: Efficient Distributed Prompt Scheduling for LLM Serving
• LayerKV: Optimizing Large Language Model Serving with Layer-wise KV Cache Management
• vLLM v0.23.0 scheduler configuration source
• vLLM v0.23.0 scheduler source
• vLLM scheduler configuration
• vLLM optimization and tuning
• Anyscale LLM serving metrics