LLM Serving — KV Cache, Batching, Speculative Decoding

Why this session exists

Serving is a joint quality, latency, throughput and cost problem. A $0.20 query can be worthwhile for one product and unaffordable for another; no serving trick alone determines viability. You will distinguish prefill/decode, derive KV and bandwidth budgets, compare batching policies, understand exact speculative sampling, and design a controlled vLLM experiment. Efficient attention (115), Transformer structure (112) and evaluation (122) supply the prerequisites.

The pizza-kitchen analogy separates preparation from repeated work, but static batching was used before 2023 and is not identical to serving one user at a time. Continuous batching changes admission granularity, not the existence of batches.

Prefill, decode and the roofline model

Prefill processes prompt positions in parallel and creates initial keys/values. Autoregressive decode emits a token, extends the cache and uses preceding keys/values for attention. For a dense model with P parameters, a simplified layer-dominated pass uses about 2P FLOPs per token. If B token positions share one read of b-byte weights, arithmetic intensity is roughly 2PB/(Pb)=2B/b FLOP/byte. At b=2, batch-one decode is about 1, batch32 about 32, and a 2048-token prefill about 2048, ignoring attention, activations and cache traffic.

Compare intensity with hardware compute/bandwidth, then profile. Small-batch decode is often bandwidth-sensitive and large prefill often compute-heavy, but batching, long contexts, MoE, quantization, communication and kernels change the bottleneck. GPU utilization alone does not diagnose it; measure memory traffic/bandwidth, kernel timings, cache pressure, occupancy and queue time. Buying by either FLOPs or HBM bandwidth alone is insufficient. For assumed 2TB/s bandwidth and 7B two-byte weights, 2e12/14e9 ≈ 142.86 weight-read-limited steps/s is an optimistic bound, not a reproduced A100 result or a universal per-user limit.

Without caching, rerunning the entire growing prefix repeatedly recomputes projections and attention. Caching avoids those prior-position computations; it does not make attention to a length-t history O(1). Dense cached attention still reads O(t) keys/values per step, so total attention over T generated positions can remain quadratic. FlashAttention, KV caching and speculative decoding address different work.

KV memory, paging and prefix identity

For uniform layers, conventional cache bytes are

L is layers, B sequences, T cached positions, H_KV key/value heads, d_h head width, and b bytes per element. GQA/MQA use KV heads, not query heads. With L=32, H_KV=32, d_h=128 and b=2, one token is 524,288 bytes = 512KiB; 2048 positions are 1GiB per sequence; forty are 40GiB before weights/workspaces. At 32768 positions the same architecture uses 16GiB per sequence. Decimal GB and binary GiB are not interchangeable.

PagedAttention maps logical KV blocks to physical blocks, allowing noncontiguous allocation and sharing. It reduces external fragmentation and reservations; the last partially filled block still wastes space, and page tables/workspaces cost memory. Page size is implementation/configuration dependent, not always 16. The original fixed “60%→under4%, 3–4× users” figures are not universal guarantees.

Prefix reuse requires matching model/base/adapter, exact token prefix, positions, attention semantics and relevant cache configuration. A shared system prompt can save prefill work, not all decode work. Include tenant isolation policy and cache salts/authorization where appropriate. A matching text string under different tokenization or adapters is not sufficient. Transformers 4.57.1's cache guide explains reused past keys/values and inference-only caveats.

Static versus continuous scheduling

A static batch is a fixed cohort; finished members can leave idle capacity until the cohort drains. An iteration-level scheduler can admit waiting requests as others complete, subject to memory, token budgets and arrivals. For a burst with three slots and output lengths [5,20,10,15,10], static cohorts take 20+15=35 unit-time iterations; refilling a freed slot produces 20. This illustrative gain assumes constant step duration and no prefill overhead. It is not a GPU throughput prediction.

Continuous batching does not guarantee full batches, fairness or low queueing. Long prefills may delay active decodes; chunked prefill trades prompt completion against decode latency. Long outputs pin cache capacity even when work is interleaved. Admission quotas, per-request input/output limits, separate pools where justified, cancellation and backpressure protect other requests.

TTFT includes queueing, prefill and first-token delivery. Inter-token latency records delivered token spacing; average TPOT and end-to-end latency are different metrics. Throughput is total completed output tokens divided by the measured wall interval, not an average of each request's tokens/latency. Little's law relates stable long-run averages L=lambda*W under a consistent boundary; it does not turn p99 latency into capacity.

Speculative decoding: distribution and break-even

A draft proposes tokens from q, and the target provides p. Exact speculative sampling accepts a proposed token x with probability min(1,p(x)/q(x)); upon rejection, sample from the normalized positive residual (p-q)+. Accepted mass is min(p,q), rejected residual supplies the remainder, recovering p under the algorithm's assumptions. It is not “accept whenever the target's argmax matches” for stochastic generation. A target can verify several proposed positions in parallel; algorithms also use a bonus target token after a fully accepted block.

Leviathan et al. describe distribution-preserving accelerated decoding. Speed depends on draft cost, acceptance, block size, verification overhead and load. If m expected output tokens cost Tdraft+Tverify compared with m*Ttarget, speculation helps only when the former is smaller. There is no universal 70% threshold or 2–3× gain. A saturated target batch, mismatched draft or expensive draft can make it slower. Floating-point implementations and changed processors/settings need validation even when the ideal algorithm preserves the distribution.

Hands-on: cache equivalence and scheduling oracles

The CPU program compares cached and uncached causal attention for the same tiny tensors, then tests schedule, KV and speculative-mass arithmetic. Its scheduler helpers assume a positive integer slot count and positive integer output lengths; an empty request list takes zero ticks. They are fixed-fixture teaching functions, not admission validators: zero slots would make continuous fail to progress. It is not a vLLM server, GPU profile or throughput benchmark.

import math
import torch
 
torch.manual_seed(124)
torch.set_num_threads(1)
torch.set_default_dtype(torch.float64)
x = torch.randn(7, 4)
Wq, Wk, Wv = [torch.randn(4, 4) for _ in range(3)]
 
def full(prefix):
    q, k, v = prefix@Wq, prefix@Wk, prefix@Wv
    scores = q@k.T/math.sqrt(4)
    mask = torch.ones(len(prefix), len(prefix), dtype=torch.bool).triu(1)
    return scores.masked_fill(mask, -torch.inf).softmax(-1)@v
 
keys, values = [], []
for t in range(len(x)):
    q = x[t:t+1]@Wq
    keys.append(x[t:t+1]@Wk); values.append(x[t:t+1]@Wv)
    cached = (q@torch.cat(keys).T/2).softmax(-1)@torch.cat(values)
    assert torch.allclose(cached[0], full(x[:t+1])[-1], atol=1e-12)
# Wrong prefix values break identity despite matching tensor shapes.
wrong = (q@torch.cat(keys).T/2).softmax(-1)@(torch.cat(values)+1)
assert not torch.allclose(wrong[0], full(x)[-1])
 
def static(lengths, slots):
    return sum(max(lengths[i:i+slots]) for i in range(0, len(lengths), slots))
 
def continuous(lengths, slots):
    pending, active, ticks = list(lengths), [], 0
    while pending or active:
        while pending and len(active) < slots:
            active.append(pending.pop(0))
        active = [v-1 for v in active if v > 1]
        ticks += 1
    return ticks
 
lengths = [5,20,10,15,10]
assert static(lengths, 3) == 35 and continuous(lengths, 3) == 20
assert static([5]*6, 3) == continuous([5]*6, 3) == 10
per_token = 2*32*32*128*2
assert per_token == 524288 and per_token*2048 == 2**30
assert per_token*32768 == 16*2**30
p = torch.tensor([.2, .5, .3]); draft = torch.tensor([.6, .3, .1])
accepted_mass = torch.minimum(p, draft)
residual = (p-draft).clamp_min(0)
assert torch.allclose(accepted_mass+residual, p)
assert torch.isclose(accepted_mass.sum()+residual.sum(), torch.tensor(1.))
assert not torch.allclose(draft, p)  # blindly accept draft is wrong
assert math.isclose(2e12/(7e9*2), 142.85714285714286)
print("cache/scheduler/speculation contracts pass; no serving benchmark")

Restored vLLM experiment without executing a service

The original v0.5.4 launch/benchmark was unsafe as a copy-paste default: it installed packages, bound a public default address, downloaded weights, left a background process without cleanup and used statistics.quantiles on a concurrency-one sample, which fails on Python versions requiring at least two observations. This review runs none of that. A complete authorized experiment should:

1. Pin an evaluated vLLM release (the source contract here is 0.11.0), compatible driver/kernel/model/tokenizer revisions and an existing local model. Record hardware, dtype/quantization, context limits and available VRAM. A T4 is not a blanket compatibility promise.
2. In a separately authorized environment, use the documented serving interface bound to loopback for local tests, with bounded readiness timeout and cleanup in finally/trap. Fail if readiness never succeeds; do not continue after a loop that merely stopped waiting. No service command is executed in this lesson's audit.
3. Warm up, then run repeated requests at each concurrency with fixed input/output distributions. A burst sweep is a closed workload, not a production arrival process. Record offered load, successful tokens, errors, queueing, TTFT, inter-token intervals, end-to-end p50/p95/p99 and memory/preemption counters. A nonstreaming response can measure end-to-end time and usage, not TTFT/ITL.
4. Use perf_counter, not wall-clock timestamps, for elapsed time. Report total completion tokens divided by test wall time; do not multiply an already summed usage count by concurrency. Choose an explicit percentile estimator with enough samples; one sample has no trustworthy tail estimate. Include failed/time-limited requests in the report.
5. Compare prefix caching on/off with identical tokenized shared prefixes and cold/warm phases. Short shared prefixes or simultaneously cold requests may show little gain. Repeat with different prefixes as a negative control and verify cache identity/isolation.
6. Compare quality after quantization, kernels, speculative settings or tokenizer/model changes on task-specific and safety slices. Validate cancellation, dead clients, bounded buffers and resource release; aborting the client must not leak server KV state.

The versioned vLLM engine arguments document memory/context/prefix-related options. Actual behavior requires an integration run, which belongs to a separately authorized owner. No >1000 tokens/s result is claimed.

Production choices and failure diagnosis

Optimize the observed bottleneck. Serving-stack changes can preserve mathematical outputs but still introduce implementation/numerical bugs, queueing or migration costs; they are not “free wins.” Quantization reduces weight bytes, yet kernel support, dequantization and quality determine speed/value. A smaller/distilled model reduces work but may lose needed capability and needs an evaluation/training lifecycle. There is no universal 1–3pp quality cost or fixed optimal ordering of all interventions.

The five retained pathologies are long-context OOM, head-of-line/queue delays, KV preemption/recompute thrash, streaming/cancellation leaks and cold starts; task-specific quantization regressions are an additional quality risk. Enforce capacity/input/output budgets, profile admissions, monitor cache pressure, implement backpressure/deadline cleanup, and drain replicas before shutdown. No universal 30-second timeout or 60–120-second load time is asserted.

The original startup bill, p99 improvement and quantization incident numbers were unsupported. As design cases: repeated shared prefixes motivate a cache experiment; long requests motivate admission/fairness controls; a code-quality regression despite stable aggregate benchmarks motivates rollback and task-specific evaluation. TGI is not generically a static-batching engine. Claimed multiplicative speedups also require arithmetic and interaction checks: 4×, a 40% compute saving, 2× and 1.5× do not automatically yield an independently measured 24× end-to-end gain.

The serving landscape without a universal winner

vLLM emphasizes scheduling and KV management; Hugging Face TGI also supports continuous batching and streaming. As checked on 2026-10-09, TGI's official repository marks it as maintenance mode, accepting minor fixes and recommending downstream engines for new work; feature support is not a promise of ongoing feature development. TensorRT-LLM targets optimized NVIDIA execution with engine/version/hardware constraints. Managed APIs shift hardware operations to a provider but add model availability, pricing, data-handling and rate-limit contracts. Specialized hardware such as Groq should be compared on the same model, precision, input/output lengths, concurrency and latency SLO, not a blanket tenfold tokens-per-second claim. Multi-adapter serving adds adapter routing and cache identity to every option. These are selection questions, not a vendor performance benchmark.

Recall and stretch: complete answers

1. Phase bottlenecks: arithmetic intensity often differs; use the roofline approximation and profiles, not universal compute/bandwidth labels.
2. Continuous batching: refills eligible slots between iterations; it can improve utilization but does not guarantee 90% utilization or eliminate queues.
3. KV cache: layer keys/values written in prefill and appended in decode, reused for future attention; size uses KV heads and grows with cached tokens.
4. Paging: logical-to-physical blocks reduce allocation waste and permit sharing, with tail waste and finite capacity still present.
5. When speculation hurts: draft/verification overhead exceeds accepted-token savings, especially low acceptance or already saturated compute; no universal threshold.
6. H100 versus A100: a higher bandwidth can help a bandwidth-limited workload, but SKU, cache traffic, compute, precision and kernel support determine measured performance.
7. Quantized code regression: aggregate benchmark stability is insufficient; rerun product slices, assess errors, and roll back or separate configurations where justified.
8. Prefix reuse: identical token prefixes under identical relevant execution identity can save repeated prefill. Isolation, warmth and prefix length bound gains.
9. Head-of-line effects: long prefills or cache-pinning generations can delay others; use scheduling/admission limits, chunked prefill, cancellation or workload isolation.
10. Bandwidth stretch: assumed 2TB/s divided by 14GB gives about 143 weight-read-limited steps/s, before other costs. Batching shares weight reads across sequences but adds compute/KV traffic and eventually reaches another limit.

Explain KV bytes in GiB, distinguish throughput from latency, and name the quality gate that would stop a memory-saving change. Serving connects efficient attention, evaluation, adapters and product design; no fictitious sessions 142/148 are required for the capacity lesson.

Optional resources and onward navigation

The original optional pre-read links are retained as navigation, not fact-check evidence or promises about video length, quality or API stability. Use the versioned primary sources in the teaching for consequential claims. Original pacing was a suggested 90-minute session, not a completion guarantee.

• How LLMs Are Served · KV Cache Explained
• vLLM · Easy, Fast, Cheap LLM Serving with PagedAttention
• Deploy an LLM with vLLM in 10 minutes
• vLLM Docs · PagedAttention design
• How Continuous Batching Enables 23× Throughput
• Optimising LLM Inference

Next in the original sequence: S125 · Multimodal LLMs — CLIP, VLMs, Audio, Video. Publication and release navigation are adjudicated by the parent.

Hub: The 6-Month Learning Plan. The original 130-session scaffold is retained as navigation, not evidence that every destination has been reviewed.

Review and execution boundary

Reviewed against complete original and pre-edit current teaching with claim-specific primary evidence and independently replayed coverage. The executable CPU program is a bounded teaching test, not a pretrained model, serving, RAG or training benchmark. External model/service recipes remain source-supported and unexecuted. No weights, datasets, GPU, paid API or new service were used. Source publication is not end-to-end application acceptance.