Llm Inference Serving Tutorial En

§0 The Request-State-Machine Mental Model + TL;DR Cheat Sheet

LLM inference serving is not "run one forward pass" — it is a state machine spanning the gateway, the scheduler, the GPU-memory manager, and the sampler. The interview-worn "what's the difference between prefill and decode" covers just two cells of this machine — without standing the full path up first, you cannot say which step TTFT is stuck on, which resource a KV OOM is alarming about, or where to start when p99 degrades. This state machine is the through-line of this tutorial; quantization, the KV capacity formula, and the speculative-decoding derivations are already covered in the other tutorials, so here we only discuss where they plug into the serving pipeline and what they change.

1. Request path: ingress gate → tokenize/validate → prefix lookup → scheduler admission + KV reservation → queued/runnable → prefill → first token (taken directly from the logits of the last prefill forward, not "a separate decode run") → per-step decode (sampling + streaming) → finished → KV reclaim (§0.1, §1).
2. Two-stage admission: the ingress gate does only coarse-grained checks before tokenization; the precise KV/token-budget decision must wait until after tokenize and prefix lookup, and passing it only reserves (bookkeeping level) — physical allocation happens when some tick selects the request (§1.2).
3. Metrics: $TTFT=t_{\text{first emit}}-t_{\text{arrival}}$, $ITL_j=t_{\text{emit},j}-t_{\text{emit},j-1}$, $TPOT=\frac{t_{\text{last emit}}-t_{\text{first emit}}}{N_{\text{out}}-1}$ — declare the system boundary for each quantity first; throughput is a rate, SLO attainment is a ratio, goodput is "the rate that meets the SLO" — the three must not be conflated (§2).
4. Typical bottlenecks: "prefill compute-bound, decode bandwidth-bound" is an empirical conclusion for common operating regimes, not a theorem — larger batches, quantization, and ultra-long context all move the bottleneck (§2.3).
5. Sampling: top-p is the smallest sorted prefix whose cumulative probability first reaches or exceeds the threshold (the boundary token must be kept); the min-p support set changes with temperature; multiple filters do not always commute; constrained decoding is essentially setting illegal tokens' logits to $-\infty$ and then sampling as usual (§3).
6. KV: PagedAttention is block-table indirection, not "page faults auto-loading from disk"; prefix caching reuses exact token prefixes, not semantically similar prompts, and multi-tenant deployments must also guard against cache side channels (§4).
7. Scheduling: static batching's real limitation is that empty slots cannot be refilled by new requests before the whole batch ends; continuous batching saves empty slots via iteration-level refill but does not guarantee lower latency for every workload; chunked prefill improves decode ITL yet may lengthen the long prompt's own TTFT (§5).
8. Scaling and diagnosis: disaggregation is not an unconditional speedup (its gains must clear the break-even of KV transfer/coordination/failure recovery); optimizations do not stack linearly; the same seed does not guarantee token-level reproduction; when p99 degrades, split queueing time from service time first, then instrument stage by stage along the state machine (§6, §7, §1.6).

0.1　Happy path: a request that completes normally

Client request
  → ① ingress gate (coarse-grained fast rejection, no tokenization needed)
  → ② tokenize / validate (only now is the exact prompt length known)
  → ③ prefix lookup (exact token-prefix match; the hit portion reuses KV)
  → ④ scheduler admission + KV reservation (bookkeeping, not physical allocation)
  → ⑤ queued / runnable (waiting to be selected by some scheduler tick)
  → ⑥ prefill (one or more forwards over the missed span)
  → ⑦ first-token sampling → ⑧ per-step decode (sampling pipeline §3 + detokenization/streaming)
  → ⑨ FINISHED → ⑩ KV reclaim + billing/logging

Side paths: REJECTED can occur at either admission check ① or ④; PREEMPTED/SWAPPED/RESUMED, BACKPRESSURED, and TIMED_OUT/FAILED/CANCELLED are branches reachable from any running stage — the full state diagram is in §0.2. Three notes below the diagram:

• The first token comes directly from the logits/hidden state of the last prefill forward — no "independent" decode iteration needs to start first; the full-prefix-hit exception is in §1.1.
• KV reservation ≠ physical allocation: passing ④ only means the quota is reserved in the books; physical blocks are allocated when some tick selects the request (§1.2, §5.1).
• Stop strings can straddle token boundaries, so the server must buffer a small span of uncommitted text before it can emit safely (§3.4).

0.2　The full state machine: aggregated view

§1 The Request State Machine: From HTTP to Token Stream

1.1　Panorama: what a request actually goes through

Expanding §0's diagram, the details interviewees most often omit:

• Admission has two stages: the ingress gate does coarse fast rejection first; the precise KV/token-budget decision waits until after tokenize and prefix lookup — full mechanism (including reservation vs. physical allocation and the three over-limit responses) in §1.2.
• Prefix lookup happens before prefill: the scheduler matches existing cache exactly by token IDs (typically hash of the prefix token sequence); the hit portion is skipped, and prefill runs only over the missed suffix span (§4.3).
• Prefill over the missed span is one or more forwards: without chunked prefill it usually completes in one pass; with chunked prefill it is split across multiple iterations (§5.4).
• The first token is not necessarily a separate decode round: the last prefill forward itself computes the logits at "the last prompt position", and sampling happens right there — provided that forward actually computed this position. If the prefix cache fully hits (every prompt token skipped the forward), the system holds only K/V, no final hidden state/logits; it must have cached those logits separately, or at minimum recompute the last prompt token, otherwise there is nothing to sample the first token from — an easily missed step in the "full hit looks fastest" scenario. Many assume "prefill finishes, then a separate decode iteration produces the first token", which breeds the wrong intuition about what TTFT is made of.
• Per-step decode: each step runs 1 forward over only the new token, but attention reads the entire KV history; the token sampled this step immediately becomes next step's input (§3 unfolds the sampling details).
• Detokenization/streaming: each produced token is incrementally detokenized and pushed to the client; the buffering mechanism for stop strings straddling token boundaries is in §3.4 and §8 [D03].
• Termination conditions are a whole set, not "EOS and done": full list in §3.4; the termination/failure/cleanup protocol in §1.7.

1.2　Two-stage admission and overload handling

Whether a request gets accepted is not "admit if a GPU is free" — it is a joint decision in two stages (matching the guards of REJECTED/QUEUED/DEGRADED in §0.2's state table):

Stage one: ingress gate (before tokenization) — looks only at coarse signals: request-body size limit, rate limits, whether the tenant quota is exhausted. This layer blocks obviously over-limit traffic at minimal cost, without waiting for the tokenizer to finish.

Stage two: scheduler admission + KV reservation (after tokenize/validate and prefix lookup) — only now are the exact prompt length and miss length known; it jointly considers:

• Current KV headroom (allocated blocks vs. total blocks, §4)
• Max batched tokens / max concurrent sequences (this iteration's token-work budget, §5.1, §5.5)
• Predicted output length (unknown output length is the main source of admission risk — most systems can only estimate via heuristics/history, and prediction error is itself one root cause of overload)
• Tenant quotas (prevent a single tenant from exhausting global resources in multi-tenant environments)

Passing stage two only means the KV quota is reserved (remaining capacity decremented in the books), not that physical blocks are allocated — physical allocation happens when a scheduler tick actually selects this request (RUNNABLE, §5.1).

Three responses when over limit: immediate rejection (REJECTED — fail fast so the client can retry another replica), queueing (QUEUED — holds request metadata and a reservation but no physical GPU resources; needs a queueing deadline), and degradation (DEGRADED — e.g. lower this request's allowed max concurrency/best-of-n, squeezing it in with a smaller reservation instead of rejecting).

1.3　Fairness and starvation

The choice of scheduling policy directly decides who starves:

There is no free scheduling policy — utilization maximization and fairness/tail latency are usually two goals to trade off deliberately; do not report only "how much throughput improved".

1.4　Cancellation, client backpressure, disconnect

If the server does not notice promptly after a client disconnects or explicitly cancels, it keeps running decode for a request nobody is listening to — pure GPU waste that also crowds out other requests' scheduling/KV resources. Engineering-wise this requires: heartbeat/half-close detection at the connection layer; the scheduler marking "cancelled" as the highest-priority KV-reclaim target; and backpressure on streaming responses — when the client cannot keep up, generated-but-unsent tokens must not buffer without bound (session memory grows, which then drags down other requests' streaming buffers); a bounded queue + backpressure signal is needed (BACKPRESSURED, §0.2), and once it tops out, either wait for the client to catch up or actively degrade/preempt the request. The full termination/failure/cleanup protocol (deadlines, worker failure, retry/idempotency) is in §1.7.

1.5　Model loading and warm-up: cold start is not steady-state TTFT

Right after a replica starts, weight loading (disk/object store into GPU memory), CUDA kernel autotuning, CUDA Graph capture, and memory-pool initialization all make the first batch of requests far slower than steady state. This cold-start latency must not be mixed into "steady-state TTFT" benchmarks — evaluation reports must report the cold-start tail and the steady-state distribution separately, or scale-up jitter gets misdiagnosed as a chronic problem. The full evaluation protocol (load sweep, saturation point, p99 sample size, etc.) is in §2.4.

1.6　The real limits of reproducibility

1.7　Termination, failure, and the resource-cleanup protocol

A request can reach a terminal state via four different paths — normal completion (FINISHED), client cancellation (CANCELLED), timeout (TIMED_OUT), worker failure (FAILED) — but every path must converge to the same reclaim routine, or you get resource leaks or double frees. The full bounded-buffer and backpressure story for slow clients is in §1.4.

Worker failure and retry: when a worker process crashes, every request it was serving must be marked FAILED; whether upstream retries depends on whether the request is idempotent — if the client already received partial tokens (a partial stream), naive retry produces a duplicated prefix, so either the client deduplicates or the server explicitly declares "on failure, retry from scratch; any partial output already sent is void".

Cleanup = three classes of resource actions — capacity/scheduling/accounting: capacity — physical KV blocks decrement by reference count, and shared prefixes/beam branches only truly return blocks to the allocator when the last holder releases (requests terminated while still QUEUED/DEGRADED only roll back reservation bookkeeping — there are no physical blocks to free); scheduling — release the batch slot and the active-sequence quota; accounting — produce exactly one terminal billing/log record. Cancellation and timeout can race and fire almost simultaneously — repeated calls into the reclaim routine must be idempotent: never free the same block twice (double-free), and never both "assume the other will handle it" so nothing gets freed (leak).

If the interviewer asks "what exactly does the system do after a request is cancelled", the answer should cover the cleanup invariants shared by all four paths, not just "stop decoding".

§2 Serving Metrics, SLOs, and the Prefill/Decode Roofline

2.1　Precise metric definitions (declare the system boundary first)

$$TTFT = t_{\text{first emit}} - t_{\text{arrival}}, \qquad ITL_j = t_{\text{emit},j} - t_{\text{emit},j-1}$$

$$TPOT = \frac{t_{\text{last emit}} - t_{\text{first emit}}}{N_{\text{out}} - 1}\quad (N_{\text{out}} \ge 2)$$

If the endpoint of E2E latency is defined as "the emit time of the last token" and all timestamps share the same system boundary, then $t_{\text{last emit}} - t_{\text{arrival}} = TTFT + \sum_{j=2}^{N_{\text{out}}} ITL_j$ is an identity, not an approximation; if the reported scope also includes post-emit flush/connection close/trailing network transfer, the right side needs that tail term added explicitly — only then write $\approx$.

Every quantity must first declare its system boundary: does TTFT include queueing time, tokenization time, gateway/network transfer? "Mean" or "p95/p99"?

2.2　Throughput, SLO attainment, and goodput

High system throughput (tokens/s or requests/s) does not mean good user experience — if the batch is packed full to pump throughput and TTFT/TPOT degrade across the board, users perceive a slowdown. Three routinely conflated concepts to pull apart:

• Throughput: work processed per unit time, a rate — but first declare which dimension: request throughput (requests/s), output-token throughput (output tokens/s), or total-token throughput (total tokens/s including prompt tokens, often used to estimate GPU-time occupancy/cost). The three can rank systems completely differently under long-prompt/short-output or short-prompt/long-output workloads.
• SLO attainment: the requests (or tokens) meeting the TTFT/TPOT/deadline SLO as a fraction of the total, a dimensionless ratio — $A = N_{\text{SLO}} / N_{\text{total}}$.
• Goodput: the requests (or tokens) meeting the same SLO constraints as a rate per unit time — $G = N_{\text{SLO}} / \Delta t$, still in requests/s or tokens/s, not a ratio. Describing goodput as "the fraction of requests meeting the SLO" is common but inaccurate: attainment and goodput are quantities of different dimensions — attainment can be high while goodput is low because the whole system is slow, and attainment can be mediocre while goodput is still numerically sizable because raw throughput is enormous.

When reporting system capability, give the throughput–latency curve (swept across concurrency/arrival rates, see §2.4) rather than a single-point throughput number; declaring which of the three throughputs, and whether it is SLO attainment or goodput, is likewise part of the "system boundary" that must be stated upfront.

2.3　The prefill/decode empirical regime — not a theorem

Expanding one standard Transformer layer's FLOPs (full derivation in kv_cache_speculative_decoding_tutorial.md §3.1, not repeated here) gives roughly: prefill computes $L$ tokens in one pass, reusing the weights $L$ times, so arithmetic intensity is usually high and GPU compute easy to saturate; decode computes only 1 new token per step yet re-reads the whole layer's weights plus the history-growing KV, so at small batch its arithmetic intensity is low and it often lands in the HBM-bandwidth-bound regime. This "prefill compute-bound, decode bandwidth-bound" is an empirical conclusion for common operating regimes, with two qualifiers: as decode batch grows, arithmetic intensity rises (the same weights amortize over more tokens), some linear layers can turn compute-bound again, and quantization shifts the batch size at which that flip happens; and at ultra-long context, prefill attention can itself be limited by IO/HBM/workspace/kernel implementation — using FlashAttention does not automatically make the whole prefill compute-bound. Input and output lengths also act asymmetrically: input length directly sets prefill work and per-step decode KV reads, while output length does not change the initial prefill's arithmetic intensity but adds decode rounds, KV residency time, and late-stage context length.

🎯 Roofline is an upper-bound thought experiment, not a latency predictor — the ridge point $I^{*}=\text{peak FLOP/s}/\text{HBM byte/s}$ exists only to compare against a kernel's own arithmetic intensity and judge which side it theoretically leans toward; real latency also depends on kernel implementation, scheduling overhead, and memory-access patterns — see [D09] in §8.

FlashAttention-style work optimizes the attention kernel's IO efficiency (saving GPU-memory reads/writes); PagedAttention (§4) manages the address space and allocation policy of KV during serving — they solve problems at different layers; do not merge them into one technique.

Lower still, the pure kernel/assembly-level factors — operator fusion, CUDA Graphs (shape changes force re-capture), prefill's wide GEMM vs. decode's narrow GEMM/GEMV ($L_q=1$), paged attention's extra block-table-indirection cost — are only name-checked here, not expanded; they are all examples of "implementation details visibly moving measured numbers".

2.4　Trustworthy benchmarks and capacity planning (overview)

Reporting throughput, goodput, and TTFT/TPOT as one trustworthy set of numbers is easier to get wrong than it looks; below is an incomplete checklist covering the most common pitfalls — full load-test script design is out of scope for this tutorial.

• Open-loop vs. closed-loop: open-loop keeps sending at a fixed arrival rate (e.g. Poisson arrivals); closed-loop fixes concurrency (send the next only after one completes). They measure different things: closed-loop naturally lowers the effective arrival rate as the system slows, easily squeezing "falsely stable" latency numbers out of an already-overloaded system; open-loop is closer to real production traffic but requires the load-test client itself not to become the bottleneck.
• Coordinated omission: under closed-loop or naive retry logic, when a request gets stuck the load tool tends to "forget" to keep sending follow-ups on the original cadence, so the sample systematically misses the slowest cases — the measured p99 comes out far more optimistic than reality. The fix is computing latency against scheduled arrival times rather than actual send times.
• Realistic input/output length distributions: use real traces (or at least synthetic distributions matching the real ones) instead of fixed lengths, because the prefill/decode ratio, KV occupancy, and batch composition all depend strongly on the length distribution; fixed-length load tests deviate systematically from production behavior.
• Load sweep and the saturation point: numbers measured at a single concurrency/arrival rate are meaningless; sweep a curve from idle to saturation, find the knee where the throughput–latency curve turns steep (the saturation point), and state explicitly "which latency this throughput number corresponds to".
• Report cold start separately, and mind p99 sample size: the cold-start tail must be reported apart from the steady-state distribution (§1.5), or scale-up jitter gets misread as a chronic problem; tail quantiles like p99 are very noisy at small sample sizes, so use enough samples and state confidence intervals.

The full input list for replica sizing (goodput-based replica-count calculation) is in Q19.

§3 Logits to Tokens: Sampling, Constrained Decoding, and Streaming

3.1　The sampling pipeline and a quick-reference table

The execution order of logits processors is part of the API semantics, and frameworks do not agree on it. This tutorial fixes the teaching pipeline below (for exposition only — it mandates no framework's order; notation: raw logits $z_i$, occurrence count $c_i$ of a token):

$$\text{hard constraints/logit bias} \to \text{repetition/frequency/presence penalties} \to \text{temperature} \to \text{truncation filters} \to \text{renormalize} \to \text{sample}$$

Quick-reference table for the four most common operators ($p_i=\text{softmax}(z_i/T)$; every filter renormalizes within its kept set):

Stacked truncation filters do not always commute — each filter renormalizes within its kept set, so the next one no longer sees the original distribution: top_k(3) then top_p(0.8) gives a different support from the reverse order; numerical counterexample in Q11 and §8 [D02].

3.2　Penalties: a penalty is not "subtract the same constant"

$$\text{Frequency/presence penalty}:\quad z_i' = z_i - \alpha_f c_i - \alpha_p\mathbf{1}[c_i>0]$$

The frequency term grows linearly with occurrence count; the presence term only cares "has it appeared or not"; whether counts includes prompt tokens (versus only the generated part) is decided by each API's semantics — tutorials/frameworks should state it explicitly.

$$\text{Sign-aware repetition penalty}\ (r>1):\quad z_i' = \begin{cases} z_i/r & z_i>0 \\ r\,z_i & z_i<0\end{cases}\qquad\text{applies only to tokens that have appeared}$$

It is not subtracting one constant from every seen token — the scaling direction depends on sign (positive logits get pushed down, negative logits get pushed further down).

3.3　Constrained decoding and best-of-n

JSON-schema, regex, and FSM-driven constrained decoding is essentially setting the logits of currently illegal tokens to $-\infty$ at every step, then doing softmax + sampling as usual (the apply_hard_mask in §8 [D01] demonstrates this primitive). Bad-word/banned-sequence (forbidding certain token sequences from reappearing), forced tokens (leaving finite logits only on designated tokens), and no-repeat n-gram are all special cases of the same mask primitive — the actual mask timing depends on the state of the generated suffix so far, and permanently banning a single token is just a banned sequence of length 1. The genuinely messy parts — automaton state transitions (FSM/PDA), tokenizer-aware matching, dead-end handling — are in Q9.

Best-of-n / parallel sampling cannot be treated as an ordinary sampling parameter: the $n$ candidates share the KV of the same prompt (copy-on-write, §4.2), and only the generated suffixes grow roughly $n$-fold — the full KV-occupancy and scheduling-accounting version is in Q24.

3.4　Stop conditions and streaming boundaries

Stop conditions must at least distinguish: the EOS token, stop-token sequences, stop strings (string-level, possibly straddling multiple token boundaries), max_new_tokens, the total context limit, the constrained decoder's accept state (e.g. JSON syntactically closed), deadlines, and client cancellation.

When a stop string straddles token boundaries, the server must buffer a span of uncommitted text that "may still be a stop-string prefix" before pushing to the client, and emit safely only once no further stop-string match is possible (§8 [D03] gives a minimal implementation). This belongs to the same "unstable boundary" family as the tokenization tutorial's prefix instability, but at a different layer — one at the tokenizer's encode boundary, the other at streaming's string-match boundary; the former, plus the full token-healing mechanism, is in tokenization_tutorial.md §5.4.

§4 The KV Lifecycle: Allocation, Paging, Sharing, and Routing

4.1　Capacity accounting: plugging the sibling tutorial's known quantity into serving

Per-token KV bytes directly reuse the conclusion of kv_cache_speculative_decoding_tutorial.md §2.1:

$$m_{\text{token}} = 2\, N_{\text{layer}}\, N_{\text{kv\_head}}\, d_{\text{head}}\, b$$

(the factor 2 is K/V; $b$ is bytes per element; this is the ideal payload, excluding allocator alignment, block-table metadata, quantization scales, and other overheads — the MQA/GQA/MLA derivations are in that tutorial). This tutorial treats $m_{\text{token}}$ as an externally known parameter and cares only about three things once it enters the serving lifecycle: block allocation and internal fragmentation, cross-request sharing and copy-on-write (§4.2), and reclamation under preemption/eviction (§4.4) — [D07]–[D08] hook this known quantity into those three things without re-verifying the formula itself.

4.2　PagedAttention: a block table, not automatic swap-out to disk

The core mechanism (full design in kv_cache_speculative_decoding_tutorial.md §5; this section covers only the serving half): each sequence's logical KV blocks map through a block table to non-contiguous physical blocks in GPU memory, and the attention kernel reads KV via this table's indirection. Fixed-size blocks remove the requirement that "each request must reserve one contiguous max-length KV span", cutting external fragmentation and over-reservation; but the last partially filled block still carries internal fragmentation (the allocator demo in §8 [D07]).

Physical blocks can be shared across common prefixes or beam branches via reference counting; when a shared writable tail block needs to diverge, the usual trigger is copy-on-write (copy the block and rewrite the mapping, rather than mutating the shared content in place).

4.3　Prefix caching and multi-tenant correctness

Prefix caching reuses the KV of an exact token prefix; the core criterion is "token-ID sequences equal position by position + every configuration that produced the KV is compatible" — e.g. same model version/weights, same adapter (LoRA etc.), same position encoding and attention configuration, same KV dtype/memory layout, same parallel sharding.

In multi-tenant settings, the prefix cache is a genuine security-boundary problem: the cache's hash-key design, access permissions, and eviction policy must all prevent tenants from using side channels like "did the cache hit" or "response-latency differences" to infer each other's private prefix contents — or worse, directly reusing cached content they should not access.

4.4　Eviction and preemption

For standard full causal attention, evicting any old KV forfeits the guarantee of equivalence with "the exact computation path that keeps the full history KV" — the evicted position should have participated in every subsequent query's attention, so dropping it introduces an approximation never validated in training. Safe sliding-window eviction requires the model itself to train/infer with windowed attention, or an explicit acceptance of the semantic shift brought by approximate methods like attention sinks or compression — eviction is a priced engineering choice, not a lossless optimization.

Common preemption approaches differ both in cost and in whether they actually relieve GPU-memory pressure — this is a common taxonomy, not an exhaustive one:

• Discard KV and recompute (recompute): truly frees physical KV blocks, at the cost of extra recomputation compute;
• Migrate to host memory (swap): also truly frees GPU memory, at the cost of extra transfer (growing with KV size);
• Pause but keep KV (descheduling): merely removes this request from the current round of scheduling; it skips this iteration but keeps holding all its physical KV blocks. This one should not be lumped with the other two as the same class of "memory reclamation": what it frees is compute/scheduling share, and it cannot relieve KV memory pressure; if the goal is to free KV space for other requests, descheduling alone does not help — it must pair with recompute or swap.

Which one (or which combination) to pick depends on the concrete trade-off of recompute cost vs. transfer bandwidth vs. memory pressure — there is no universally optimal answer.

The triple impact of long-generation requests — stretching mixed-batch iterations, occupying KV capacity long-term, raising the probability of triggering preemption — unfolds fully in Q21.

4.5　Cache-aware routing

With multiple replicas, choosing which replica to route to cannot just chase "the highest prefix-cache hit rate":

🎯 Cache-aware routing's correct objective is minimizing expected completion time or SLO-violation probability, not maximizing hit rate — the highest-hit replica can still be slower than a no-hit but idle replica if its queue is already deep. The routing decision must jointly weigh current queue depth, expected KV occupancy, the prefill savings from prefix-cache hits, and failure-domain isolation — not greedily optimize a single metric.

§5 Scheduling: Scheduler Ticks, Batching, and Admission

5.1　A scheduler iteration in full: what one tick does

Each scheduler tick (one iteration) is the hub connecting admission, KV, prefill, decode, sampling, and streaming — four core steps:

1. Reclaim and refill: reclaim last round's terminal requests per §1.7's cleanup protocol (freeing batch slots and KV blocks), then refill the active set from QUEUED/DEGRADED per the scheduling policy (§1.3) — provided max_num_seqs, physical KV capacity, and the already-reserved shares line up; the selected requests convert from "reserved" to physically allocated (QUEUED → RUNNABLE).
2. Allocate the budget, form the mixed batch: max_batched_tokens is this iteration's token-work budget (not a whole-lifetime reservation for the request — that was computed at admission, §1.2), split between prefill chunks (§5.4) and 1 decode token per active request.
3. Execute and emit: run one mixed forward containing both prefill chunks and decode tokens (kernel-level differences at the end of §2.3), apply §3's sampling pipeline to the logits to produce the next token, and hand it to streaming/stop-string detection (§3.4); if the client cannot keep up, the request goes BACKPRESSURED (§0.2) instead of buffering without bound.
4. Update states: check termination conditions (EOS/stop/length/deadline/cancel) and mark terminal states for next round's reclaim; under excessive KV pressure or to make room for higher priority, run preemption per §4.4 (recompute/swap/descheduling — only the first two truly free GPU memory).

Speculative decoding adds "a variable number of accepted tokens after verification + KV rollback of rejected candidates" to step 3; its accounting impact on this tick is in §7.

5.2　Static batching's real limitation

5.3　Continuous (in-flight) batching

Continuous batching removes finished requests and admits new ones into the vacated slots at iteration boundaries; the main gains come from less decode padding, fewer empty slots, and less head-of-line blocking.

5.4　Chunked prefill

Splitting a long prompt's prefill into multiple fixed-size chunks lets the scheduler interleave decode work between chunks, capping the token work of a single iteration and preventing one long prefill from monopolizing a whole iteration (head-of-line blocking).

5.5　Admission control and the joint KV/token-budget constraint

At the scheduler-implementation level, admission jointly maintains four constraints — max_num_seqs, max_batched_tokens (the iteration-level budget, §5.1), remaining KV block capacity, and tenant quotas — hitting any one means reject or queue, and the decision only affects whether the "reservation" succeeds; physical allocation waits for the moment a tick selects the request. The full two-stage admission is in §1.2.

§6 From One Machine to a Cluster: Replicas, Parallelism, and Prefill/Decode Disaggregation

6.1　Replica routing

Routing decisions across multiple replicas must trade off current queue depth, expected KV occupancy, prefix-cache locality, and failure domains — the cache-aware full version is in §4.5.

6.2　TP/PP/EP: the forward-only inference view

Inference has no backward pass and no optimizer state, but that does not make parallel communication disappear — communication-volume analysis and the full derivations of backward/ZeRO/FSDP/training pipeline schedules are in distributed_training_tutorial.md; here are only the three inference-specific points:

• TP: every layer's forward still needs collective communication (e.g. the all-reduce after row-parallel); at small decode batches, per-token communication latency easily outweighs the compute savings.
• EP (MoE): expert parallelism at inference still needs token dispatch/combine communication and faces expert load imbalance; no backward does not remove all-to-all latency, hot experts, or small-message communication overhead; EP usage is driven mainly by the MoE's expert placement.
• PP: for single requests and low concurrency, PP cannot automatically lower latency, since end-to-end still traverses all stages; it takes enough concurrent sequences or micro-batches to fill the pipeline, otherwise most time is spent waiting on bubbles.

6.3　Prefill/Decode Disaggregation

The motivation for splitting prefill and decode onto different nodes/resource pools: the two phases have very different resource profiles (prefill compute-heavy, decode bandwidth-heavy), they can scale independently, and it reduces interference from long prefills with same-node decode ITL.

§7 Combining Optimizations and Bottleneck Migration

Each optimization alone has a clean win story, but combined, the gains neither multiply nor add directly — together they change batch size, memory headroom, kernel shapes, and the location of the bottleneck itself:

• Quantization: weight quantization mainly relieves weight bandwidth and capacity pressure; KV-cache quantization is an independent design point — the model using low-bit weights does not entitle the KV to the same bit width as a matter of course (numeric sensitivity and per-channel/per-token granularity choices differ completely). Numeric details (scale/zero-point, concrete GPTQ/AWQ/FP8 error analysis) are in quantization_tutorial.md; this section gives only the decision dimensions:

  Quantized object	Main effect	Coupling point with serving
  Weights	Bandwidth, memory capacity	Moves the flip point of decode arithmetic intensity (§2.3)
  KV cache	Memory capacity, allowed batch/context ceiling	Affects §4's capacity accounting and block allocation
  Activations	Kernel support, numeric stability	Determines which fused kernels are usable and prefill's real throughput

• Speculative decoding: acceptance rate and the $E[\tau]$ expected-speedup derivation are in kv_cache_speculative_decoding_tutorial.md §7; this tutorial stresses only the serving accounting: each target verification processes multiple candidate tokens and yields a variable number of accepted tokens, so the scheduler must account separately for "verified tokens", "output tokens", and "KV delta" — never treat it as fixed-stride decode. Quantizing the target or the draft can shift the draft/target distribution gap and the acceptance rate through numeric error — speculative decoding and quantization are not strictly orthogonal.
• Prefix caching × continuous batching × disaggregation: a prefix hit shortens the effective prefill length, which changes the prefill pool's actual workload in a disaggregated deployment and thus the ratio at which the two resource pools should be provisioned — the three are mutually coupled, and evaluating any one in isolation yields misleading conclusions.

🎯 Online symptom → localization path (diagnostic table)

§8 From-Scratch Implementations: Demo Index

The full runnable script is code/inference_serving.py (pure standard library, no third-party dependencies, [D01]–[D09] finish in seconds on CPU); each demo verifies one isolated mechanism:

Key assertion snippets are folded below; the full invariant list and the script's real output are in §A.

# top-p: smallest sorted prefix whose cumulative probability first reaches or exceeds the threshold; keep the boundary token
p_ex = [0.4, 0.3, 0.2, 0.1]
filt = top_p_filter(p_ex, 0.65)
support = {i for i, p in enumerate(filt) if p > 0}
assert support == {0, 1}                                   # cumulative 0.7 >= 0.65
assert sum([p_ex[0]]) < 0.65                                # "strictly below p0" would drop the boundary token

# min-p support changes with temperature (not a fixed logit-gap threshold)
sizes = [len(min_p_support_from_logits(logits_t, T, alpha=0.3))
         for T in (0.2, 0.5, 1.0, 2.0, 5.0)]
assert sizes == sorted(sizes) and sizes[0] < sizes[-1]      # larger T, larger support

# filter order is not commutative
support_a = support_of(top_p_filter(top_k_filter(probs, 3), 0.8))   # top_k -> top_p
support_b = support_of(top_k_filter(top_p_filter(probs, 0.8), 3))   # top_p -> top_k
assert support_a != support_b                               # {0,1} vs {0,1,2}

reqs = [Request("A", 0, 1), Request("B", 0, 4), Request("C", 0, 1)]
comp_static, _  = simulate_batching(reqs, capacity=2, policy="static")
comp_cont,   _  = simulate_batching(reqs, capacity=2, policy="continuous")
assert comp_static == {"A": 1, "B": 4, "C": 5}    # C cannot start until t=4
assert comp_cont   == {"A": 1, "C": 2, "B": 4}    # C slots in at t=1 right after A finishes

# Note: "utilization" here is scheduler-slot utilization (total serviced tokens /
# (capacity * makespan)) — a capacity metric of this unit-cost toy model, not GPU
# SM/HBM utilization; in real systems each iteration's actual duration varies with
# batch composition and the prefill/decode mix, unlike the equal-time ticks assumed here.
u_static, _ = utilization(comp_static, reqs, 2)   # slot utilization: 6 / (2*5) = 0.60
u_cont,   _ = utilization(comp_cont,   reqs, 2)   # slot utilization: 6 / (2*4) = 0.75

m_token = kv_bytes_per_token(n_layer=2, n_kv_head=2, d_head=4, bytes_per_elem=2)
assert m_token == 64                                        # 2*2*2*4*2 bytes/token

logical_slots, allocated_slots = block_alloc_slots([1, 5], block_size=4)
assert (logical_slots, allocated_slots) == (6, 12)          # internal fragmentation: 12 > 6

no_share = physical_blocks_no_sharing([6, 7], block_size=4)  # 4
with_share = no_share - 1                                    # sharing one full block -> 3

§9 25 High-Frequency Interview Questions

Three difficulty tiers; organize answers as "framework → key formulas/definitions → common mistakes", without repeating the main text's derivations.

L1 Must-know

L2 Advanced

L3 Top-lab

§A Appendix: Sanity Check

Running python3 code/inference_serving.py (pure Python standard library, no third-party dependencies, seconds on CPU) should pass all checks [D01]–[D09]; the key invariant list and the real terminal output are folded below.

[D01] sampling operators: greedy tie-break, T=0 rejected, T->0 limits (unique->one-hot, tied->split), top-k/top-p/min-p/typical support sets (exact boundaries, nested/shift-invariant, domain-checked), penalties, constrained masking, deterministic + empirical draw checks PASS
[D02] filter order is NOT commutative: top_k->top_p support=[0, 1], top_p->top_k support=[0, 1, 2]  PASS
[D03] stop-string streaming: 'STOP' split across 3 chunks still detected (emitted='abc'), no-match case fully recoverable via flush  PASS
[D04] static: A=1,B=4,C=5 (util=0.60); continuous: A=1,C=2,B=4 (util=0.75); equal-length counterexample: both makespan=3 (no strict dominance); delayed-arrival workload respects arrival<=tick<completion; illegal inputs (7 cases) rejected immediately  PASS
[D05] chunked prefill: decode max-gap 3->1 (ITL improves) but long-prompt TTFT 3->4 (worsens) -- not a free lunch  PASS
[D06] KV bytes/token (L=2,kv_head=2,d_head=4,fp16)=64B; [D07] block alloc lengths=[1,5],P=4: logical=6 slots/384B, allocated=12 slots/768B; [D08] prefix-sharing (real token-sequence match) blocks 4->3, sub-block overlap shares 0, 3-way sharing scales as (n-1)*B_shared, TP-divisibility guard enforced  PASS
[D09] roofline ridge point I* = 201.3 FLOPs/byte (upper-bound reference only)  PASS

all inference serving sanity checks passed

📚 References

• PagedAttention / vLLM — Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, arXiv 2309.06180 (2023), SOSP 2023.
• Orca (iteration-level / continuous batching) — Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models, arXiv 2204.05120 (2022), OSDI 2022.
• Sarathi-Serve (chunked prefill) — Agrawal et al., Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve, arXiv 2403.02310 (2024), OSDI 2024.
• DistServe (disaggregation, goodput) — Zhong et al., DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving, arXiv 2401.09670 (2024), OSDI 2024.
• Splitwise (phase splitting) — Patel et al., Splitwise: Efficient Generative LLM Inference Using Phase Splitting, arXiv 2311.18677 (2023), ISCA 2024.
• SGLang / RadixAttention (radix-tree prefix caching) — Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs, arXiv 2312.07104 (2023).
• Nucleus sampling (top-p) — Holtzman et al., The Curious Case of Neural Text Degeneration, arXiv 1904.09751 (2019), ICLR 2020.
• Top-k sampling — Fan, Lewis & Dauphin, Hierarchical Neural Story Generation, arXiv 1805.04833 (2018), ACL 2018.
• Min-p sampling — Nguyen et al., Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs, arXiv 2407.01082 (2024).
• Locally typical sampling — Meister et al., Locally Typical Sampling, arXiv 2202.00666 (2022), TACL 2023.
• Speculative decoding — Leviathan, Kalman & Matias, Fast Inference from Transformers via Speculative Decoding, arXiv 2211.17192 (2022), ICML 2023.
• Speculative sampling — Chen et al. (DeepMind), Accelerating Large Language Model Decoding with Speculative Sampling, arXiv 2302.01318 (2023).
• FlashAttention (attention-kernel IO optimization — not the same technique as PagedAttention) — Dao et al., FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, arXiv 2205.14135 (2022), NeurIPS 2022.
• Megatron-LM (TP) — Shoeybi et al., Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism, arXiv 1909.08053 (2019).
• Roofline model — Williams, Waterman & Patterson, Roofline: An Insightful Visual Performance Model for Multicore Architectures, Communications of the ACM (2009) (no arXiv id).
• Constrained decoding / grammar-constrained generation — Willard & Louf, Efficient Guided Generation for Large Language Models, arXiv 2307.09702 (2023). This paper backs the concrete implementation of guided/grammar-constrained generation, but it should not be cited to argue that "every constrained-decoding implementation is essentially nothing but mask-and-renormalize" — §3.3's "essentially a mask" is an abstraction at the sampling-primitive level, not a restatement of that paper's scope.