Chapter 31 Serving Efficiency: Reuse, Kernels, Speculation, and Batching

31.1 Three users arrive before the first answer finishes

The travel assistant receives three requests close together. A single model can answer them sequentially, but the second and third users wait while the first finishes. Adding a faster mathematical operation might help, yet it would not by itself decide which user runs next. Reusing a prefix might help only the requests that share it. A proposal model might add work without accepting enough tokens to repay it.

We will keep one workload fixed and identify which layer each optimization changes. A model specifies weights and computation. An engine executes those operations and manages device state. A server receives requests, queues and schedules them, and returns results. The application assembles evidence and decides what a successful answer means. These roles can live in one process or several; the distinction is responsibility, not a required deployment diagram.

31.2 Establish a schedule before announcing a speedup

Example 31.1 — A fully supplied workload. Request A arrives at 0 ms with four input tokens and requests three output tokens. B arrives at 20 ms with four input tokens and requests two outputs. C arrives at 40 ms with two input tokens and requests one output. These counts are assigned, include the entire tokenized input, and are identical in both schedules. All six outputs complete; there are no errors, cancellations or network delays in this scenario.

Table 31.1 — Assigned emission timestamps, in milliseconds on one clock

Request	Arrival	Input / output count	Serial schedule emissions	Continuous schedule emissions
A	0	4 / 3	100, 140, 180	100, 150, 200
B	20	4 / 2	260, 300	150, 200
C	40	2 / 1	360	180

These are given schedules, not measurements of a named framework and not predicted timings from token counts. They illustrate a possible tradeoff. We do not attribute their difference to all four optimizations at once; identifying a causal speedup would require controlled measurements changing one factor under the same workload.

Use Chapter 30’s definitions. In the serial schedule B’s TTFT is $260-20=240$ ms; in the continuous schedule it is $150-20=130$ ms. For A, the serial post-first-token gaps are 40 and 40 ms; continuous gaps are 50 and 50 ms. B starts sooner while A’s later tokens arrive more slowly.

Table 31.2 — Derived per-request metrics

Request	Serial TTFT	Continuous TTFT	Serial TPOT	Continuous TPOT
A	100 ms	100 ms	40 ms	50 ms
B	240 ms	130 ms	40 ms	50 ms
C	320 ms	140 ms	Missing	Missing

C has only one output, so inventing a zero TPOT would bias an average. Also publish distributions or per-request results: a single average can conceal a long wait for C. With three requests, a tail percentile is little more than a choice among three observations; it cannot establish production tail reliability.

31.3 Reuse the same prefix, not merely similar words

Suppose A’s input IDs are [10,11,12,13], B’s are [10,11,12,14], and C’s are [20,21]. A and B share the first three IDs. Under the same weights, positional setup and other computation conditions, their causal K/V for that prefix are identical. Prefix caching retains that computed prefix across requests so B can reuse it once it exists, processing only its different suffix. The longest shared prefix is three positions; similar meaning or a match elsewhere in the prompt is insufficient.

This does not imply that B can reuse A’s cache at arrival time 20 ms. A must first have computed and made the relevant state available, and the server must retain it. An engine may share physical cache blocks and copy a block when a branch appends, rather than duplicate all numerical values. Eviction can remove the opportunity; admitting a long retained prefix consumes capacity that could otherwise hold active requests.

For our changed-policy example, a prefix containing the archived 600-yuan rule is not an exact prefix match for the new 750-yuan rule. A cache key must identify the token content and computation version, including relevant adapters and positional conventions, rather than only a document title. Reuse also belongs inside the application’s allowed access boundary. The fact that two users submit the same prefix does not grant one access to another user’s private content or metadata.

Prefix caching saves some prefill work. It is different from the within-request KV reuse in Chapter 30 and from returning an old final answer. It does not automatically save the work of generating a new suffix. The arrival and length table remains the same whether the prefix cache hits or misses; the measured schedule would reveal the effect.

31.4 Keep the attention function, move less intermediate data

Full attention can create a large matrix of position-pair scores. A naive implementation writes large intermediates to relatively slow device memory and later reads them back for softmax and value mixing. FlashAttention reorganizes that work into tiles small enough for faster on-chip storage, combines normalization statistics, and avoids materializing the full score matrix in slower memory. This is an engine/kernel change, not deletion of the model’s permitted attention pairs.

Example 31.2 — Combine tile statistics, not tile averages. For one query, assign unnormalized weights $[4,2,1,1]$ and scalar values $[1,3,0,2]$. The full weighted sum is $4\times1+2\times3+1\times0+1\times2=12$, with total weight 8, giving output 1.5. Split into two tiles. The first has numerator 10 and denominator 6; the second has numerator 2 and denominator 2. Combining them gives $(10+2)/(6+2)=1.5$.

Averaging the two normalized tile outputs equally gives $(10/6+2/2)/2=4/3$, which is wrong: the tiles have unequal probability mass. Real online softmax also tracks a running maximum and rescales sums when that maximum changes, so exponentials remain stable. The example isolates why intermediate sufficient statistics can be combined without retaining a complete matrix; it is not the complete kernel algorithm.

FlashAttention computes the same attention function in exact arithmetic. Different floating-point reduction orders can still produce numerical differences. Full attention’s pairwise arithmetic has not become linear in sequence length merely because memory traffic falls. Hardware, supported layouts, sequence lengths and kernel selection determine the benefit. A short CPU request may spend most of its time elsewhere. No universal speed multiplier follows from the name.

31.5 Guess ahead, then verify with the target model

Standard decode has a dependency between output tokens. Speculative decoding asks a cheaper proposal process to draft several tokens, then lets the target model evaluate those proposed continuations together. If enough proposals are accepted, one target invocation can advance several positions. Rejections discard later dependent guesses. Proposal cost, verification cost, acceptance and batching conditions determine whether this saves time.

For greedy target decoding, one can accept a draft token when it matches the target’s own greedy choice at that prefix. For stochastic decoding, simply accepting the target’s top choice is not enough to preserve its sampling distribution. A correction is needed.

Example 31.3 — Why rejection needs a residual distribution. Candidate order is Paris, Lyon. The target distribution is $p=[0.6,0.4]$; the proposal distribution is $q=[0.8,0.2]$. Both already include whatever generation policy has been declared. Draw from q. Accept Paris with probability $0.6/0.8=0.75$ and Lyon with probability 1, since the target gives Lyon at least as much mass as the proposal.

Accepted Paris mass is $0.8\times0.75=0.6$. Accepted Lyon mass is 0.2. The remaining rejection mass is 0.2, all from Paris proposals. The target still needs that entire mass on Lyon. The positive difference between target and proposal is $\max(p-q,0)=[0,0.2]$; normalized, it is $[0,1]$. Resampling a rejected proposal from that residual completes the target distribution exactly: Paris 0.6, Lyon $0.2+0.2=0.4$.

For a proposed candidate x with positive q, acceptance is $\min(1,p(x)/q(x))$. On rejection, sample in proportion to the positive part of p−q. If p and q coincide, all proposals are accepted and a zero residual is never sampled. A wrong implementation that resamples rejection directly from p would give Paris $0.6+0.2\times0.6=0.72$, changing the target distribution.

This argument preserves the target distribution under the algorithm’s assumptions, not a bit-for-bit match to an unrelated sequence of random draws. Applying different temperature or filtering during verification breaks those assumptions. The book reproduces the two-candidate correction, not a GPU speculative server or the paper’s speed results.

31.6 Change the active batch between iterations

A batch can share expensive weight reads and arrange matrix work efficiently, but requests have different lengths. If a server waits for every member of a fixed batch to finish, short requests may occupy slots after completion and newcomers may wait outside. Continuous batching changes the active set between execution iterations: remove completed requests and admit waiting ones when capacity permits. Orca’s iteration-level scheduling is an early systems example of this idea.

In Table 31.1’s continuous schedule, A and B remain active after C finishes at 180 ms. They finish at 200 ms. The table is consistent with changing active work, but it does not specify every kernel launch or prove a particular scheduling algorithm. An admission rule still needs limits on active tokens, cache capacity and fairness. Mixing a very long prefill with decodes can delay existing users; splitting prefill into chunks is one possible scheduling choice with its own overhead and tradeoff.

Same arrivals and lengths

1. Outside the modelA: 0 ms, 4 inputs / 3 outputs
2. Outside the modelB: 20 ms, 4 inputs / 2 outputs
3. Outside the modelC: 40 ms, 2 inputs / 1 output

All times are assigned scenario values, not framework benchmarks.

Serial completion

1. Text piecesA: 100 → 140 → 180
2. Text piecesB: 260 → 300
3. Text piecesC: 360

6 / .360 ≈ 16.667 output tokens/s; A later gaps 40 ms.

Continuous completion

1. Text piecesA: 100 → 150 → 200
2. Text piecesB: 150 → 200
3. Text piecesC: 180

6 / .200 = 30 output tokens/s; A later gaps 50 ms. In a common .400 s window, both rates are 15.

Figure 31.1 — A shorter queue can coexist with slower token spacing. Original book diagram · CC BY-SA 4.0.

Figure 31.1 makes the tradeoff visible: the continuous schedule shortens the final completion time while widening A’s between-token spacing. The application may prefer that schedule for a queue, or reject it if a user’s streaming pace has a strict requirement. “More throughput” does not resolve that preference.

31.7 Choose a window before dividing tokens by seconds

Example 31.4 — Two valid throughput questions. Counting from the first arrival until the final completion, serial produces six output tokens in 0.360 seconds: $6/0.360\approx16.667$ output tokens/s. Continuous produces the same six in 0.200 seconds: $6/0.200=30$ output tokens/s. This uses each schedule’s own completion window and measures how fast that finite workload drains.

If instead both experiments use a fixed observation window from 0 through 400 ms, both produce $6/0.400=15$ output tokens/s. Nothing contradictory happened: the denominator changed, and the faster schedule has more idle time inside that window. Publish input/output counting, arrivals, warmup, failures, concurrency and window endpoints. Sustained service throughput requires a workload that actually supplies work throughout the measurement.

Assign a single resource price of USD 2 per hour, charged exactly over each drain window with no minimum billing. Serial’s assigned cost is $2\times0.360/3600=0.0002$ dollars; continuous is $2\times0.200/3600\approx0.000111111$ dollars. Per 1,000 output tokens these become approximately 0.033333 and 0.018519 dollars. These are estimates under a fictional resource tariff, not API prices or actual bills. A fixed reserved hour costs the same regardless of how quickly these six tokens finish; labor, idle capacity and unsuccessful requests may dominate.

The core practice reads the fixed workload and derives these metrics; the scalar implementation checks them. Framework configuration and GPU experiments are optional. No claimed speedup comes from merely enabling a field in a file. We now have many resource metrics but still lack the most important denominator: how many requests produce acceptable answers? That requires an evaluation contract before choosing a model.

31.8 Summary

Prefix caching reuses previously computed matching input state; FlashAttention changes memory movement within attention; speculation verifies proposals; continuous batching changes which requests share iterations. They act at different layers and can interact. Compare explicit workloads using TTFT, post-first-token TPOT, defined-window throughput and a stated cost model, alongside answer quality.

31.9 Exercises

1. Using Table 31.1, calculate A and B’s complete-request durations under both schedules. Which user finishes sooner, and which later?
2. Compute throughput for both schedules over a fixed 500 ms window. Explain why it differs from the drain-window calculation.
3. Change Example 31.3 to $p=[0.3,0.7]$ and $q=[0.6,0.4]$. Give acceptance probabilities and the rejection distribution, then verify the final masses.
4. Two prompts contain the same words in a different order. Can prefix caching assume a hit? What else must match even when token IDs are identical?
5. A framework reports less attention memory, but decode time barely improves. Give two plausible bottleneck explanations and a measurement that could distinguish them.
6. A server completes more tokens by delaying every first token beyond the application’s limit. Has it improved under a contract with a hard TTFT bound?

31.10 Reference answers

1. Serial A takes 180 ms, B $300-20=280$ ms. Continuous A takes 200 ms, B $200-20=180$ ms. B finishes its request 100 ms sooner in duration; A takes 20 ms longer. The same schedule change benefits users differently.
2. Both give $6/0.500=12$ output tokens/s. The common window includes idle time after completion; each drain window excludes that time. Neither number can be compared without its window definition.
3. Acceptance is $[0.5,1]$. Accepted masses are 0.3 and 0.4; rejection mass is 0.3. The positive residual is $[0,0.3]$, so every rejected draw becomes Lyon. Final masses are 0.3 and 0.7.
4. No: token positions and the shared beginning must match, not a bag of words. The model/adapter, positional settings and relevant computation conditions must also match, with reuse permitted by the access boundary.
5. Weight reads or non-attention operations may dominate, or queueing may dominate end-to-end latency. Compare kernel/device timings with request queue and emission timestamps under the same workload. A memory allocation decrease alone cannot identify the limiting stage.
6. No. A hard bound is a gate, not a preference that extra throughput can compensate for. Report the throughput gain and the violated bound; seek another schedule or revise the contract explicitly before a new comparison.

31.11 References

• Dao et al., FlashAttention, 2022. Section 3 and Algorithm 1 explain tiled attention with online normalization and reduced memory traffic.
• Leviathan et al., Fast Inference from Transformers via Speculative Decoding, 2023. Section 2.3 specifies acceptance and residual correction for target-distribution sampling.
• Yu et al., Orca, 2022. Section 3 explains iteration-level request scheduling; Section 6.2 explicitly limits general latency claims.
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, 2023. Section 4 explains block-based KV storage underlying allocation and sharing decisions.