Continuous batching under load

Four quantities per concurrency level, defined exactly as vLLM's own serving benchmark defines them so your numbers are comparable with vllm bench serve:

TPOT is one line, and the definition matters because the alternatives differ by a token:

            tpot = 0.0
            if output_len > 1:
                latency_minus_ttft = outputs[i].latency - outputs[i].ttft
                tpot = latency_minus_ttft / (output_len - 1)
                tpots.append(tpot)
            # Note: if output_len <= 1, we regard tpot as 0 for goodput
            all_tpots.append(tpot)

TTFT and ITL are taken client-side, one timestamp per SSE data frame, which is what a user actually experiences:

                            timestamp = time.perf_counter()
                            data = json.loads(chunk)

                            if choices := data.get("choices"):
                                content = choices[0]["delta"].get("content")
                                # First token
                                if ttft == 0.0:
                                    ttft = timestamp - st
                                    output.ttft = ttft

                                # Decoding phase
                                else:
                                    output.itl.append(timestamp - most_recent_timestamp)

Closed loop, deliberately

run.py holds exactly N requests in flight: each of N workers starts a new request the instant its previous one finishes. That answers "with N users each waiting on an answer, what do they see?" — and it is the right question for a batching experiment, because concurrency is the independent variable and is held exactly.

It is the wrong question for capacity planning. "What happens at 40 requests per second?" needs open-loop arrivals, where a slow server does not slow the arrival process down; that distinction, and why closed-loop benchmarks systematically flatter a saturated server, belongs to §10.3 and lab 11. Both engines' harnesses take the same pair of knobs, and the help text spells out the interaction:

    parser.add_argument(
        "--max-concurrency",
        type=int,
        default=None,
        help="Maximum number of concurrent requests. This can be used "
        "to help simulate an environment where a higher level component "
        "is enforcing a maximum number of concurrent requests. While the "
        "--request-rate argument controls the rate at which requests are "
        "initiated, this argument will control how many are actually allowed "
        "to execute at a time. This means that when used in combination, the "
        "actual request rate may be lower than specified with --request-rate, "
        "if the server is not processing requests fast enough to keep up.",

    parser.add_argument(
        "--max-concurrency",
        type=int,
        default=None,
        help="Maximum number of concurrent requests. This can be used "
        "to help simulate an environment where a higher level component "
        "is enforcing a maximum number of concurrent requests. While the "
        "--request-rate argument controls the rate at which requests are "
        "initiated, this argument will control how many are actually allowed "
        "to execute at a time. This means that when used in combination, the "
        "actual request rate may be lower than specified with --request-rate, "
        "if the server is not processing requests fast enough to keep up.",

Word-for-word identical, which is worth noticing: SGLang's serving benchmark descends from vLLM's, so when you compare engines with these two harnesses you are at least comparing the same definitions.

$ vllm serve meta-llama/Meta-Llama-3-8B-Instruct --max-num-seqs 256 --port 8000
$ python3 run.py --port 8000 --concurrency 1 2 4 8 16 32 64 128 --requests-per-level 512

$ python3 -m sglang.launch_server --model-path meta-llama/Meta-Llama-3-8B-Instruct \
    --max-running-requests 256 --port 30000
$ python3 run.py --port 30000 --concurrency 1 2 4 8 16 32 64 128 --requests-per-level 512 --json sglang.json

$ python3 run.py --help          # every knob, including --api, --input-len, --knee-threshold

Requests are pinned to a fixed output length with ignore_eos, which both engines accept on their OpenAI-compatible routes as an extension field. Without it, output lengths vary, batch composition varies with them, and you are measuring a different experiment at every level.

Prompts are distinct pseudo-random integer strings rather than one repeated prompt. A repeated prompt is served almost entirely out of the prefix cache after the first request, which quietly converts a batching experiment into a caching experiment — that one is lab 04, and it has its own README.

Predict first

1. Output tok/s at concurrency 1. Use β from lab 01 and the Llama-3-8B weight stream: β / 15.01 GB tokens per second is the ceiling, and it is derived in §0.4 as about 223 tok/s on H100 spec-sheet bandwidth.
2. The concurrency at which throughput stops doubling. Predict it from the ridge point rather than guessing: a decode step's weight GEMMs sit at I = B in bf16, so the batch stops being weight-bound somewhere below I*.
3. What TTFT p99 will do across the sweep, and whether TPOT p99 will move more or less than TTFT p99 does.

The shape the book's derivations predict is this: throughput climbs steeply, bends, and flattens; TTFT climbs the whole way and then accelerates; TPOT climbs slowly and then jumps. The climb is batching amortising the weight stream (§0.4); the flattening is the point at which it has nothing left to amortise, or the pool has nothing left to give (§1.3). The bend is the knee. run.py reports it as the first level whose marginal throughput gain falls below --knee-threshold of what perfectly linear scaling would have given. Whether your curve has that shape is the first thing to check, and a curve that does not is a finding worth chasing.

Use at least 512 requests for the advertised maximum concurrency of 128, report actual active concurrency, and separate ramp-up/drain from a sustained measurement interval. Repeat runs and retain failures; 512 is a starting workload size, not a guarantee of precise p99 estimates.

Finding the knee is easy. Naming its cause is the exercise, and start with these candidates, then inspect compute, launch and host-side limits:

The two vLLM signatures live in one log line, assembled here:

        # Format and print output.
        log_parts = [
            "Avg prompt throughput: %.1f tokens/s",
            "Avg generation throughput: %.1f tokens/s",
            "Running: %d reqs",
            "Waiting: %d reqs",
        ]
# ...
        if self.num_preemptions > 0:
            log_parts.append("Preemptions: %d")
            log_args.append(self.num_preemptions)

        log_parts.extend(
            [
                "GPU KV cache usage: %.1f%%",
                "Prefix cache hit rate: %.1f%%",
            ]

The Preemptions line is conditional — it only appears once the counter is non-zero, so its absence is information too. SGLang assembles the equivalent pair into one message, the running count and pool usage at the front and the queue depth appended at the end:

        iter_msg = f" [{batch_iter}]" if LOG_FORWARD_ITERS else ""
        msg = f"Decode batch{iter_msg}, #running-req: {num_running_reqs}, {token_usage_msg}"
# ...
        msg += (
            f"{self._graph_backend_label}: {can_run_cuda_graph}, "
            f"gen throughput (token/s): {self.last_gen_throughput:.2f}, "
            f"#queue-req: {len(self.scheduler.waiting_queue)}"
        )

and its retraction warning is unmistakable when the pool runs dry:

            msg_prefix = (
                "KV cache pool is full. Retract requests. "
                if kv_full_retract_flag
                else "Testing retraction. "
            )
            msg_details = f"#retracted_reqs: {len(retracted_reqs)}, #new_tokens_gained: {new_token_gained}"
            if mamba_num_gained is not None:
                msg_details += f", #mamba_num_gained: {mamba_num_gained}"
            if kv_full_retract_flag:
                msg_details += (
                    f", #new_token_ratio: {old_ratio:.4f} -> {new_token_ratio:.4f}"
                )
            logger.warning(msg_prefix + msg_details)

A retraction is not a crash and not a leak. It is the scheduler telling you it admitted more than it can carry, and that you are now paying to recompute prefills you already paid for. If your knee coincides with retraction warnings, the fix is capacity — fewer resident tokens per request, or a smaller admission cap — not a bigger batch.

The server benchmark above measures a real deployment. This companion lab needs only Python 3.10 or newer and the standard library. It answers a different question: can a scheduler account for every input token, reserved page, cancellation and cleanup event on a fixed workload? Download scheduler_sim.py, then run these commands from its directory. No model download, API key, engine install or GPU is used.

python scheduler_sim.py --output continuous.json
python scheduler_sim.py --policy serial --output serial.json
python -m json.tool continuous.json

Every dispatch lasts one synthetic tick regardless of its token count. Report synthetic TTFT, queue delay and dispatch count, not milliseconds or tokens per second. The serial policy admits one request at a time; the continuous policy admits up to max_active and mixes decode rows with chunked prefills. Neither implements padded static batch formation. The model exposes reservation and lifecycle differences without pretending to measure attention bandwidth.

Input and output contracts

Supply --trace workload.jsonl to replay your own workload. Each nonblank line is one JSON object in either of the following forms; the built-in workload is reproduced here in full. Timestamps are nonnegative integer boundaries, prompt and requested output lengths are positive integers, and all request IDs must be unique for the entire trace. A cancellation must reference a request arriving at or before its timestamp. Unknown fields and booleans masquerading as integers are rejected.

{"time": 0, "event": "arrival", "id": "long", "prompt_tokens": 8, "output_tokens": 4}
{"time": 0, "event": "arrival", "id": "short", "prompt_tokens": 2, "output_tokens": 2}
{"time": 1, "event": "arrival", "id": "cancel-me", "prompt_tokens": 6, "output_tokens": 4}
{"time": 2, "event": "cancel", "id": "cancel-me"}
{"time": 2, "event": "arrival", "id": "late", "prompt_tokens": 3, "output_tokens": 2}

The output is one JSON document with schema_version, time_unit, the full config, a per-request table, an ordered events trace and summary counts. Each request records arrival, admission, terminal time, output timestamps, queue ticks, TTFT ticks and individual ITL ticks. TTFT is null when no output was produced; it is never manufactured as zero for cancelled or rejected requests. A one-token response has an empty ITL list because there is no inter-token interval.

Each snapshot includes logical block tables, allocated and free counts, active reservation credits, draining pages and remaining admission headroom. Snapshots occur after boundary events and admission but before dispatch. Dispatch events list the request, phase and input-token count for every participating row. The subsequent token and terminal events occur at the completion boundary. Arrival, cancellation and release events make missing work distinguishable from missing instrumentation.

Expected built-in result

The default continuous run performs seven dispatches and processes 19 input tokens: 11 for long, three for short, four for late, and one prefill token wasted on cancel-me. Three requests finish, one cancels, none rejects. All eight pages are reusable by tick eight, one tick after the last response completes. That final drain time is not the last request's response latency.

from scheduler_sim import demo_trace, simulate

report = simulate(demo_trace())
assert report["time_unit"] == "synthetic_tick"
assert report["requests"]["long"]["token_times"] == [4, 5, 6, 7]
assert report["requests"]["cancel-me"]["ttft_ticks"] is None
assert report["summary"] == {
    "drained_at_tick": 8, "dispatches": 7,
    "processed_input_tokens": 19, "free_blocks": 8,
    "finished": 3, "cancelled": 1, "rejected": 0,
}
assert report == simulate(demo_trace())
print("deterministic trace and complete cleanup: OK")

Experiments with an answer you can check

1. Reservation versus allocation. Set capacity to two four-token pages and submit a one-token prompt requesting eight outputs, followed by a one-token prompt requesting one output. The first request reserves both pages before allocating either, so the second queues despite a nonempty physical free list. Inspect reserved_blocks and admission_headroom, not only free_blocks.
2. Cancellation versus reuse. Use a one-page pool, two one-token prompts with one-token outputs, and --release-delay 3. The first response finishes at tick one, but the second cannot be admitted until tick four. Reducing the delay to zero allows admission at tick one. Delayed release is a storage-lifetime constraint, not extra request computation.
3. Boundary races. Cancel a one-token request at tick one after it was dispatched at tick zero. Completion wins because dispatch results commit before boundary arrivals and cancellations. Cancel the same request at tick zero and it never runs. The trace must show cancel_ignored in the first case and cancelled in the second.
4. Decode priority. Reduce --token-budget to one while multiple requests are active. A decode row can consume the entire budget, delaying prefill. Rotation shares decode opportunities across the current rows; it does not erase the phase-priority tradeoff. Compare each request's token timestamps instead of averaging away the delayed request.
5. Failure conservation. Submit a prompt that cannot fit even alone. It must become rejected, not remain queued forever or acquire negative headroom. Add a duplicate arrival ID and confirm the input is rejected before simulation, preventing ambiguous cancellation routing across ID reuse.

Verification and limits

From a repository checkout run python site/test_inference_scheduler.py. Tests execute both printed Python examples, the CLI JSONL roundtrip, deterministic boundary cases, 60 seeded scheduler workloads and 5,000 randomized allocator operation choices against a separate logical-token oracle. See the ownership lesson for shared partial prefixes, synchronous copy-on-write, transfer pins and failure-atomic allocation.

No real request traces or performance measurements are bundled. Replay accepts arrivals, intended lengths and cancellations, not worker kernel traces. The scheduler has no preemption, cache-hit-aware admission, distributed routing, deadline objective or prefill/decode-specific cost curve; the allocator's shared-prefix operations are tested separately from scheduling. Keep the JSON configuration with any result, and retain these exclusions when discussing what an experiment demonstrates. Extend one policy at a time and rerun the conservation tests before adding a performance interpretation.

The previous arrival simulator deliberately reserves worst-case capacity and has no victim-selection policy. This separate lifecycle exercise adds explicit preemption and full recomputation without changing that scheduler's results. Download scheduler_faults.py beside scheduler_sim.py. Both use only the Python standard library. Run python scheduler_faults.py --output faults.json for a deterministic JSON event trace; run python site/test_inference_faults.py from the repository for the executable contracts.

Three histories that must not be confused

A request retains its original prompt, the tokens already sent to the client, and the input rows whose KV has been materialized. For a prompt [10, 11, 12] and sampled outputs [20, 21], the committed KV rows are [10, 11, 12, 20]. Token 21 has been sampled but has not yet been fed back. Rebuilding all five tokens now and feeding 21 again on the next decode step would duplicate an input row. Re-emitting 20 and 21 would instead duplicate the client-visible output stream. These are different bugs.

RecomputeRequest keeps prompt and emitted-token history on the host. preempt() releases its page-table ownership and marks it preempted; it does not erase that history. resume() rebuilds the prompt plus all but the most recent sampled output, then makes the request active. The next sample() first commits the pending sampled token and records one new output. The supplied token is a hypothetical model result: this module does not implement a model, sampling algorithm, RNG restoration or logits evaluation.

from scheduler_faults import PagedKV, RecomputeRequest

pool = PagedKV(capacity=4, block_size=2)
request = RecomputeRequest(pool, "r", [10, 11, 12])
assert request.resume()
request.sample(20)
request.sample(21)
request.preempt()
assert len(pool.free) == 4
assert request.resume()
assert request.recomputed_rows == 4
assert pool.read("r") == [10, 11, 12, 20]
request.sample(22)
assert request.outputs == [20, 21, 22]
request.cancel()
assert len(pool.free) == 4

Admission failure is not partial progress

Reconstruction needs enough pages for the entire committed prefix in this model. If allocation fails halfway through, resume() releases every partially reconstructed page, leaves the request queued or preempted, returns False, and does not increment the successful-replay counter. A failed decode allocation similarly emits no new token. The test suite deliberately leaves one competing page resident so a two-page replay starts allocating but cannot finish, then verifies that no page leaks and a later retry succeeds.

This atomic operation is a teaching simplification, not chunked-prefill scheduling. It counts successfully reconstructed input rows, not wasted partial reconstruction attempts or FLOPs. A real scheduler may checkpoint reconstruction progress across several token-budget-limited dispatches. Its accounting must distinguish useful rows, failed work, retained partial KV and client-visible progress. Attention over a warm suffix also has different work from a cold prompt of the same suffix length; token counts alone do not establish a swap-versus-recompute speedup.

What the model proves, and what it does not

The invariant is exact: while active, the page-table read equals prompt plus emitted outputs excluding the newest output. Every emission event has one increasing output index, and replay produces no emission events. Cancellation is idempotent; a cancelled request cannot resume. Forty fixed random seeds exercise 2,000 preempt/sample operation choices against an independently retained output-history oracle.

The model does not prove output equality after an actual engine replay. Real equivalence additionally depends on positions, attention masks, model and adapter identity, numeric execution, sampling/RNG state and the exact accepted history under speculative decoding. Nor does it prove scheduling fairness: a victim-selection policy can keep preempting the same request forever. To evaluate such a policy, add a bounded-arrival workload, a starvation metric and an explicit progress assumption rather than inferring fairness from memory conservation. See the scheduler's recomputation contract.

A request is cancelled in the control plane while a transport still holds its source and destination addresses. Returning those pages to the free list immediately is unsafe: a delayed write could corrupt another request. TransferManager models this lifetime mismatch using the existing allocator's transfer pins. Source and destination use one pool so every page is observable; real P and D workers have separate address spaces, allocators and failure detectors.

State machine and publication boundary

begin(source, room) snapshots the source rows, pins their storage, reserves private destination pages and pins those pages too. If reservation fails, all newly allocated pages and the source pin are rolled back. The destination is unpublished: read() raises until complete() copies the snapshot and changes the transfer to ready. This is an atomic control-plane model of a completion acknowledgement, not a simulation of bytes arriving over a network.

A cancellation arriving after successful publication loses this particular state-machine race: abort() returns False, and the caller releases the already published output through release_output(). An abort that arrives first prevents subsequent publication. A duplicate completion, duplicate drain acknowledgement or unknown transfer key returns False without touching memory. This explicit event ordering makes the example reproducible; it is not a claim that every engine resolves races identically.

Worked cancellation ledger

Take four pages of two rows each. A three-row producer occupies two pages; destination reservation occupies the other two. The producer cancels and drops its owner. The transfer aborts and drops the destination owner. There are now zero request-owned pages but also zero free pages: four pages remain pinned by transport. Even an attempted reconstruction must fail until the transport is known to have stopped accessing them.

from scheduler_faults import PagedKV, RecomputeRequest, TransferManager

pool = PagedKV(4, 2)
request = RecomputeRequest(pool, "r", [1, 2, 3])
assert request.resume()
manager = TransferManager(pool)
old = manager.begin("r", "room-a")
request.preempt()
assert manager.abort(old, "consumer_failure")
assert len(pool.free) == 0
assert not request.resume()
assert not manager.complete(old)
assert manager.acknowledge_drained(old)
assert len(pool.free) == 4
assert request.resume()
new = manager.begin("r", "room-a")
assert new != old
assert not manager.complete(old)
assert manager.complete(new)
assert manager.read(new) == [1, 2, 3]
manager.release_output(new)
request.cancel()
assert len(pool.free) == 4

Room reuse and stale callbacks

A room name is a routing label, not a lifetime identity. The manager rejects a second live transfer for the same room and allows reuse only after drain or output release. Each attempt receives a monotonically increasing key. A late callback carries that old key, never only the room string, so it cannot publish into or release the newer attempt's pages. The transfer counter advances even when destination reservation fails; skipped generations are harmless.

The model retains terminal records as tombstones, and one manager owns its private owner/pin namespace for a pool. Production systems cannot grow tombstones forever. They need an explicit callback-expiry and garbage-collection policy, an incarnation identifier that survives worker restarts, and fencing at the transport or allocation layer. Merely ignoring a stale Python callback cannot stop an old RDMA write into an address that has already been reused. That is why this model permits reuse only after an externally justified drain acknowledgement.

Fault matrix and liveness assumptions

The executable suite applies the same retention contract to cancellation, timeout, producer failure and consumer failure. It also tests duplicate room names, stale and duplicate callbacks, publication before read, partial-allocation rollback, source mutation during transfer, and recomputation blocked by pinned pages. Thirty seeded randomized runs make 3,000 lifecycle operation choices and compare each published snapshot with a separate token-history oracle. Pins freeze the source view: appending to a shared or pinned partial tail invokes copy-on-write rather than changing the bytes a transfer is expected to read.

Safety is unconditional within the API contract; eventual cleanup is conditional. If no trustworthy drain acknowledgement ever arrives, the model intentionally retains storage. A timeout alone is not proof that a remote writer stopped. A production recovery path might revoke registrations, reset a transport context, destroy a worker incarnation or quarantine pages until hardware completion, depending on the backend. The exercise supplies none of those mechanisms, no actual process crash, and no GPU/network measurement. See P/D failure contracts before applying the toy result to an engine.

Exercises with observable answers

1. Remove a drain acknowledgement. Stop immediately after abort(). Expected: the request is no longer active, but four pages remain allocated. A test expecting all pages free here would encode a use-after-free bug.
2. Reverse completion and abort. Run completion first, then abort. Expected: the destination is readable, abort returns false, and output release frees destination ownership. Reverse the order and the read remains forbidden until that aborted attempt is drained; it never becomes ready.
3. Append during transfer. Transfer [1, 2, 3] with two-row pages, then append 4 at the source. Expected: completion still publishes [1, 2, 3]; the source's partial tail has been copied. Repeat with no spare page and verify that append fails without changing either snapshot.
4. Reuse a room. Drain attempt A, start B in the same room, then deliver A's completion again. Expected: B remains in flight and its allocations are unchanged. A room-only lookup would fail this experiment.
5. Interpret the built-in JSON. Expected: outputs [20, 21, 22], received rows [10, 11, 12, 20, 21], four successfully recomputed rows, four pages retained before the first drain acknowledgement, and all eight pages free at the end. These are exact accounting values, not latency estimates.