Why a Second Kind of Engine: Batching, Paged Attention and Throughput

By the end of this lesson you will be able to say what a serving engine does that a single-user engine does not, explain continuous batching and paged attention to somebody else, predict roughly how many concurrent conversations your machine’s memory can hold, and decide which of your own workloads needs an engine of this kind at all.

Two different questions

Part 6 taught you to ask “how fast does this model answer me”. That question has one answer, and Part 5 gave you the arithmetic behind it: decode reads every active weight once per token, so the pace of an answer is set by memory bandwidth.

A serving engine answers a different question: “how much work does this machine get through”. Those two are not the same, and improving one often costs the other.

Think about a machine that generates one token every 25 milliseconds for a single user. If a second user arrives and the engine simply takes turns, each of them now waits 50 milliseconds per token and the machine does exactly the same total work. That is the wrong way to do it, and it is what happens if you run two copies of a single-user server on one accelerator.

The right way exploits an asymmetry you have already met. Reading the weights for one token and reading them for twenty tokens costs almost the same, because the expensive part is fetching the weights from memory, not the arithmetic done with them. If the engine can arrange for twenty sequences to take their step together, one pass over the weights serves all twenty. The per-user pace barely changes and the machine’s total output goes up by something close to twenty.

That is batching, and it is the whole reason this part exists.

!Important

Latency and throughput are different measurements and both need reporting. Latency is what one person experiences: time to first token, then time per output token. Throughput is what the machine produces: output tokens per second across everybody, and completed requests per second. A change that improves one usually moves the other, so a claim about “speed” that does not say which one it means has not said anything. The lab in this part measures both, at four concurrency levels.

Continuous batching

The naive version of batching is static: collect requests until you have a batch, run them together until they all finish, then start the next batch. It is easy to implement and it wastes an enormous amount of the accelerator, because requests do not finish together. A batch of eight where one answer runs to 900 tokens and seven stop at 60 spends most of its life computing one sequence in a slot built for eight.

Continuous batching, sometimes called in-flight batching, works at the granularity of a single decode step instead. Every step, the scheduler looks at what is running and what is waiting, forms the batch for this step, and runs it. A sequence that finished leaves immediately and its slot is refilled from the queue on the very next step.

One iteration of a continuously batched engine

1. 1Requests arrive independentlyThey join a waiting queue. Nothing waits for a batch to fill up.
2. 2The scheduler forms this step's batchSequences already decoding, plus as many waiting prompts as the token budget and free KV blocks allow.
3. 3One forward pass over the weightsEvery sequence in the batch advances. The weights are read once for the whole batch, which is why the second concurrent request is nearly free.
4. 4Finished sequences leaveA sequence that emitted its stop token returns to its client and releases its KV blocks in the same step.
5. 5Waiting requests take the free slotsThe next step is formed from scratch, so a request that arrived a millisecond ago can be in it.

The loop runs at decode-step granularity, typically tens of times a second. Nothing in it waits for a batch boundary, which is what 'continuous' means.

Prefill complicates this. Reading a 4,000-token prompt is a single compute-heavy operation that, if run whole, stalls every decoding sequence in the batch for as long as it takes. That shows up to users as an answer that pauses whenever somebody else asks a long question.

The fix is chunked prefill: split a long prompt into pieces and mix each piece into a normal decode step, so prefill progresses without ever monopolising a step. vLLM’s optimisation guide states that “in V1, chunked prefill is enabled by default whenever possible”, and describes the trade directly: smaller token budgets per step “achieve better ITL because there are fewer prefills slowing down decodes”, while higher values “achieve better time to first token”.

Four requests through a continuously batched engine

Request 1

prefilldecode

Request 2

prefilldecode

Request 3

prefilldecode

Request 4

prefilldecode

step 1step 5step 9step 12

Each column is one scheduler step. Request 2 arrives while request 1 is already decoding and joins the very next step; request 1 finishes early and request 4 takes its place without waiting for anything. The prefill blocks are chunked, so no single step is spent entirely on reading one prompt.

llama.cpp has a version of this. Its server README documents -np, --parallel N as the number of server slots and -cb, --cont-batching as enabled by default. Part 6 used it. The difference is not that llama.cpp cannot batch; it is how the memory behind those slots is managed, which is the next section.

Paged attention

Every sequence being served needs its own KV cache: the keys and values computed for every token it has seen so far, kept so they need not be recomputed. That cache grows by one entry per generated token and disappears when the request ends.

The obvious implementation reserves a contiguous block per sequence, sized for the longest answer it might produce. The PagedAttention paper describes exactly what goes wrong: “the key-value cache (KV cache) memory for each request is huge and grows and shrinks dynamically. When managed inefficiently, this memory can be significantly wasted by fragmentation and redundant duplication, limiting the batch size.”

Two kinds of waste, and both are worth picturing. Internal fragmentation: a slot reserved for 2,048 tokens holding a 60-token answer has wasted 97 per cent of itself for the life of the request. External fragmentation: the free memory is there in total but not in one piece large enough for the next slot, so a request queues while memory sits idle.

PagedAttention borrows the solution operating systems have used for decades. The cache is cut into small fixed-size blocks, a sequence holds a list of block numbers rather than one range, and the blocks a sequence uses need not be next to each other. A sequence grows by taking one more block off the free list; it shrinks by handing blocks back. The paper’s claim for the result is “near-zero waste in KV cache memory” and “flexible sharing of KV cache within and across requests”, and it reports 2–4 times the throughput of the systems it was compared against in 2023 at the same latency.

The consequence you will feel is that the batch size stops being something you configure defensively and becomes something the engine works out from the memory actually free. That is why vLLM’s front-page options are about memory fractions and token budgets rather than about slot counts.

▤Memory budget

Paged attention removes waste; it does not remove the requirement. Twenty concurrent conversations still need twenty conversations’ worth of keys and values. Paging means you get to use nearly all of the memory you reserved instead of about half of it. It does not mean the KV cache became small.

The memory that concurrency actually costs

Take Qwen3-8B, the reference 8B model from Part 4, on a 16 GB machine. It is Apache-2.0 licensed and ungated; the model reference records the licence. Its recorded KV cost is about 144 KiB per token at FP16, and its Q4_K_M weights are about 5 GB.

Serving twenty concurrent requests with 4,096 tokens of context each means holding 81,920 tokens of KV cache. The arithmetic gives roughly 12 GB, which does not fit alongside the weights.

Qwen3-8B at Q4_K_M, twenty concurrent requests at 4,096 tokens each, on a 16 GB machine — estimates from the course model reference

16 GB budget

Weights, Q4_K_M

5 GB

KV cache, 20 x 4,096 tokens at FP16

12.1 GB

Activations and compute buffers

1 GB

Requested

18.1 GB

Machine budget

16 GB

Over budget. 18.1 GB requested against a 16 GB machine - 2.1 GB over. Something here has to shrink: a smaller quantisation, a shorter context, or fewer of these reservations at once.

The bar is over budget on purpose. Weights are fixed; the KV cache scales with concurrency multiplied by context, and at twenty slots it is larger than the weights. Three levers bring it back inside: fewer concurrent slots, less context per slot, or a quantised KV cache. Quantising the cache to eight bits roughly halves the KV segment and the whole thing fits with room to spare.

Turn the arithmetic round and it becomes a planning tool. Ten gigabytes of KV budget divided by 144 KiB per token is roughly 72,000 tokens of cache, which is about seventeen conversations at 4,096 tokens, or thirty-five at 2,048, or four at 16,384. Concurrency and context trade against each other directly, and the exchange rate is a division you can do before you start the server.

A mixture-of-experts model changes the weights side of that sum but not the KV side. Qwen3-30B-A3B reads only its active parameters per token, so it decodes quickly for its size, but the memory it occupies is set by its total parameters, and its KV cache is charged per token exactly like a dense model’s.

Prefix caching

The second big idea is that requests overlap. A chat application sends the same system prompt every time. An agent sends a long tool schema on every step of its loop. A document assistant sends the same 8,000-token document with a different question after it. In each case a large part of the prompt has already been computed and thrown away.

Because paged attention already stores the cache in blocks addressed by number, keeping useful blocks around costs nothing structurally. vLLM’s design notes describe hashing “each kv-cache block by the tokens in the block and the tokens in the prefix before the block”, keeping a map from those hashes to blocks, and evicting on a least-recently-used basis when space is needed. A request whose first several blocks hash to blocks already in the pool skips prefilling them entirely.

SGLang generalises the same idea into what its paper calls RadixAttention: the cached prefixes are held in a radix tree so that many requests sharing progressively longer prefixes all reuse the longest match available, rather than only matching a single linear history. The SGLang paper reports up to 6.4 times the throughput of the systems it compared against on workloads built from agent control, few-shot prompting, JSON decoding, retrieval pipelines and multi-turn chat, which are precisely the workloads with heavy prefix sharing.

The effect on a user is that time to first token collapses on the second and later request with the same prefix, while decode speed is unchanged. That is a measurement you will make yourself in this part’s lab, and it is the reason Part 10’s prompting lesson cares about where the variable part of a prompt goes.

✕Common mistake

Putting the variable part of a prompt first destroys prefix reuse. Caching matches from the beginning of the token sequence. A prompt that starts with today’s date, a request id or the user’s name shares no prefix with the previous one, even if the next 6,000 tokens are identical. Put the stable material first and the variable material last.

Goodput, and why throughput alone is a trap

Maximising throughput alone produces a server that is unusable. Let enough requests in and every one of them crawls; the tokens-per-second total looks magnificent and nobody can hold a conversation.

The honest measurement is goodput: the rate of requests that completed and met a stated service-level objective. The objective is usually a pair of numbers, for example “time to first token under one second and time per output token under fifty milliseconds”, and a request that finishes outside them counts as zero however many tokens it produced.

This is not a course invention. vLLM’s own load-generation tool takes a --goodput option described as specifying service level objectives, alongside --percentile-metrics and --metric-percentiles for reporting the distribution rather than the mean. Reporting a mean latency for a serving system is close to useless: the mean hides the tail, and the tail is what people complain about.

So the four numbers to carry for the rest of this course are: output token throughput, request throughput, time to first token at a high percentile, and time per output token at a high percentile. The lab records exactly those.

When llama.cpp is still the right tool

This is a real question and the answer is often “llama.cpp”.

One user, one machine. With concurrency of one there is no batching to exploit, no fragmentation to eliminate and no prefix to share between requests. The engines converge, and llama.cpp starts in seconds against a minute or more, uses a fraction of the memory when idle, and runs from a single binary.

Your track is M. vLLM’s mainline GPU path does not cover Apple silicon. The next lesson gives the exact status and the alternatives.

The model you want exists only as GGUF. Community quantisations of new models appear as GGUF first and often only. vLLM’s quantisation matrix does list GGUF, but the ecosystem’s centre of gravity for GGUF is llama.cpp.

Memory is tight. A serving engine pre-allocates a large fraction of the accelerator so it has KV blocks to hand out. On a machine where the model barely fits, that reservation is the difference between running and not running.

You need it now. llama-server from llama.cpp v0.4.0 · verified 2026-09-08 is a file and a flag. vLLM at vLLM 0.28.0 · verified 2026-09-08 is a Python environment, a matching CUDA or ROCm stack, and a model in a format it accepts.

Use the serving engine when requests arrive concurrently, when the same prefix is sent repeatedly, or when total completed work per hour is the thing you are optimising. Use llama.cpp when it is you and one model.

Throughput can rise while every user waits longer

Distinguish an arrival process from a concurrency setting. A closed-loop load generator keeps a fixed number of requests in flight and sends the next request when one completes. An open-loop generator submits at a chosen arrival rate even when the service slows. They stress queueing differently, so record which one your harness implements.

At each load level, report completed requests, failures, time to first token, end-to-end latency and aggregate token throughput. Include output lengths: a model emitting shorter answers can complete more requests without generating tokens faster. Tail latency matters when a few long prefills delay many interactive users.

Paged cache management reduces some allocation waste and supports flexible scheduling; it does not create unlimited capacity. Tokens still occupy blocks and active sequences still compete for memory and computation. Increase load gradually and choose the largest admitted workload that meets your latency target, not the load with the largest throughput number. The rejected or queued requests are part of the service result.

Recap

Serving engines answer “how much work does this machine get through”, not “how fast does it answer me”, and those two questions pull in different directions. Continuous batching schedules at decode-step granularity so that finished sequences leave and waiting ones join without a batch boundary, and chunked prefill stops a long prompt from stalling everyone else’s tokens. Paged attention manages the KV cache in fixed-size blocks like operating-system pages, which removes the internal and external fragmentation that limits batch size, and makes sharing between requests possible. Prefix caching turns that sharing into skipped prefill for repeated system prompts, tool schemas and documents, with SGLang’s radix tree as a more general form of the same idea. Concurrency costs KV cache linearly in slots times context, so the two trade against each other by simple division. Goodput, not throughput, is the number that describes a usable service, and it needs percentiles rather than means. And when there is one user and one model, llama.cpp is still the better tool.

Check your understanding

Question 1. Why does adding a second concurrent request cost far less than twice as much work?

• The second request reuses the first request's KV cache
• Both sequences advance in one forward pass over the weights, and reading the weights is the expensive part of a decode step
• The engine lowers the precision when more than one request is active
• The second request is queued until the first finishes

Show the answer and why

Answer: Both sequences advance in one forward pass over the weights, and reading the weights is the expensive part of a decode step

Decode is bandwidth-bound: the weights are read once per step regardless of how many sequences take that step together. This is the entire economic argument for batching, and it stops working only when the batch gets large enough that the arithmetic, rather than the weight traffic, becomes the limit.

Question 2. What problem does PagedAttention solve, according to the paper that introduced it?

• The model is too large to fit in memory
• KV cache memory is wasted by fragmentation and redundant duplication when each sequence gets one contiguous reservation, which limits the batch size
• Attention is too slow to compute
• Prompts have to be re-tokenised for every request

Show the answer and why

Answer: KV cache memory is wasted by fragmentation and redundant duplication when each sequence gets one contiguous reservation, which limits the batch size

The paper names fragmentation and duplication as the waste and the batch size as the casualty. Cutting the cache into fixed-size blocks that a sequence holds as a list, rather than as a range, removes both kinds of fragmentation and lets blocks be shared between requests.

Question 3. You are serving Qwen3-8B, which costs about 144 KiB of KV cache per token at FP16, and you have roughly 10 GB of memory left after the weights. Which of these are true? Select all that apply.

• That budget holds roughly 72,000 tokens of cache in total, across all concurrent requests
• Halving the context per request roughly doubles the number of concurrent requests that fit
• Quantising the KV cache to eight bits roughly halves the memory each token costs
• The KV cache is charged per request rather than per token, so context length does not matter

Show the answer and why

Answer: That budget holds roughly 72,000 tokens of cache in total, across all concurrent requests, Halving the context per request roughly doubles the number of concurrent requests that fit, Quantising the KV cache to eight bits roughly halves the memory each token costs

The cache is charged per token, and the total is concurrency multiplied by context. That makes the trade a division you can do in advance: slots and context are interchangeable, and quantising the cache changes the exchange rate rather than the shape of the trade.

Question 4. An agent sends the same 6,000-token tool schema on every step, but prepends a fresh request id to each prompt. Why does prefix caching not help?

• Tool schemas cannot be cached
• Cached blocks are matched from the start of the token sequence, so a different first block means nothing after it matches either
• The cache is cleared between requests
• Prefix caching only works for chat, not for agents

Show the answer and why

Answer: Cached blocks are matched from the start of the token sequence, so a different first block means nothing after it matches either

Each block hash includes the hash of everything before it, so changing the first token invalidates the whole chain. Moving the request id to the end of the prompt would let all 6,000 tokens of schema be reused. This is a real and common own goal.

Question 5. Why is goodput a better headline number than raw throughput for a serving system?

• It is easier to measure
• Raw throughput can be maximised by admitting so many requests that none of them meets a usable latency target; goodput only counts requests that finished within a stated objective
• Goodput includes prefill and throughput does not
• Throughput cannot be measured with percentiles

Show the answer and why

Answer: Raw throughput can be maximised by admitting so many requests that none of them meets a usable latency target; goodput only counts requests that finished within a stated objective

Overloading a server raises its total token rate while making every individual request unusable. Goodput refuses to count those, which is why vLLM's own load generator takes a service-level objective and reports percentiles rather than a mean.

Check my answersClear