# How a language model is served

Lecture 18 · Serving models · Distributed Systems I
Paper: vLLM / PagedAttention (SOSP 2023)
The page also has slides and an interactive simulator: https://alfonsocampodonico.com/classes/distributed-systems/como-se-sirve-un-modelo?lang=en
Code: https://github.com/AlfonsoCampodonico/ta050-sistemas-distribuidos/tree/main/repos/servir-tokens (`gh repo clone AlfonsoCampodonico/ta050-sistemas-distribuidos`)

> Continuous batching and PagedAttention: what happens inside an inference engine like vLLM.

In Lectures 16 and 17 we trained a model on thousands of GPUs. This lecture is the other half: how it gets served. A chat request crosses familiar infrastructure —HTTPS, load balancers, a gateway— and ends up in a loop that runs the model once per token. Almost all the time and almost all the cost are in that loop, and what decides how many people a GPU can serve at once is how a single structure is managed: the KV cache.

**Paper:** W. Kwon et al., [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://arxiv.org/abs/2309.06180), SOSP 2023. This is the vLLM paper.

**Further reading:** G.-I. Yu et al., [Orca: A Distributed Serving System for Transformer-Based Generative Models](https://www.usenix.org/conference/osdi22/presentation/yu), OSDI 2022. For the full journey of a request: A. Campodónico, [What happens after you hit send](/posts/what-happens-after-you-hit-send).

**Hands-on material:** the **Inference engine** simulator, to show in class, and the `servir-tokens` repository (Go, no dependencies), with the same engine behind a real HTTP server.

The paper's central idea is an old one for us: it is the paged virtual memory from Operating Systems, applied to GPU memory. We'll see why it was needed and what it changes.

## 1. The journey of a request

The first half of the journey is infrastructure we already know, and it's fast: tens of milliseconds. The chat client builds a JSON with the conversation and sends it over HTTPS with a `POST`, asking for the response as a stream (`Accept: text/event-stream`). The connection **stays open**, because the response won't arrive all at once.

1. **Edge.** DNS or anycast sends the request to a nearby point of presence. TLS terminates there, invalid traffic is filtered out and per-IP limits are applied, and a load balancer picks a healthy backend and pins the long-lived connection to it.
2. **Gateway.** It authenticates the key and checks quotas and limits. Limits are counted in **tokens**, not requests: the token is the unit of cost.
3. **Router.** It picks a pool of model replicas and a region. Some prefer a replica that recently saw the same prefix, to reuse its cache.

A replica of a 70-billion-parameter model takes about 140 GB of weights in 16 bits, more than an 80 GB H100 GPU. It is split across the 8 GPUs of a node with tensor parallelism, which we saw in Lecture 16: within the node, over NVLink. Bringing up a replica takes minutes, because those weights have to be loaded and the server warmed up. That's why capacity is planned ahead and sits there waiting.

From here on, everything happens inside the **inference server** (vLLM, SGLang, TensorRT-LLM). That's the part this lecture studies.

> The full journey, with a simulator for every hop, is in the further-reading post. For us one conclusion is enough: the network is fast and boring, and the time goes into the GPU.

## 2. Prefill and decode

Generating text is a loop: run the model once, get **one** token, append it to the sequence and run again. Each round depends on the previous one, because the next token is computed from all the previous ones. There's no way to parallelize a response across time.

The text is first split into tokens, each one a number from a fixed vocabulary, and each number is turned into a vector. That's the model's input. Then there are two very different phases.

**Prefill.** The first pass processes the whole prompt at once: all its tokens go through all the layers in parallel. These are large matrix multiplications, and the GPU is busy doing math: this phase is **compute**-bound. It ends with the first token of the response.

**Decode.** Each following pass processes a single new token per sequence. To do that, the GPU has to read **all the weights** from its memory, plus the saved state of the previous tokens, only to do very little math with them. These are matrix-vector products: the phase is bound by **memory bandwidth**, and the GPU spends most of its time waiting for data.

|  | Prefill | Decode |
| --- | --- | --- |
| How many times | Once per request | Once per output token |
| Tokens per pass | The whole prompt | One per sequence |
| Bottleneck | Compute | Memory bandwidth |
| Shows up as | Time to first token (TTFT) | Time per output token (TPOT) |
| What batching gains | Little: it's already parallel | Almost everything: one read of the weights serves the whole batch |

The last row is the key to the whole lecture. If a decode pass costs the same with one sequence as with thirty, because the expensive part is reading the weights once, then you want to fit as many sequences as possible into each pass. The throughput of an inference server is, almost literally, **how many sequences fit in the batch**.

> The vLLM paper says it in §2.2: autoregressive generation processes one token per step with matrix-vector operations, underuses the GPU's compute and ends up memory-bound. That phase accounts for most of a request's latency. And in §2.3: batching amortizes loading the weights across all the requests in the batch.

## 3. The KV cache

In each layer, attention compares the current token with all the previous ones. For that it needs two vectors from each previous token: its **key** and its **value**. Recomputing them at every step would mean redoing the whole prompt for every generated token. Instead, they're computed once —during prefill for the prompt, and in the step where each generated token appears— and stored. That's the **KV cache**: the state of each in-flight sequence.

It grows a little with every token and it takes a lot of space. The size per token is:

```latex
2 \times \text{layers} \times \text{KV heads} \times \text{dimension per head} \times \text{bytes per number}
```

| Model | Calculation | Per token | One sequence |
| --- | --- | --- | --- |
| OPT-13B (the paper's) | 2 × 40 layers × 5120 × 2 bytes | ≈ 800 KB | ≈ 1.6 GB at 2048 tokens |
| Llama 3 70B | 2 × 80 layers × 8 heads × 128 × 2 bytes | 320 KiB | ≈ 2.6 GB at 8000 tokens |

Llama 3 takes less per token than a much smaller model because it uses *grouped-query attention*: several query heads share the same keys and values.

With that you can see how a GPU's memory is split up. In the paper's example (§1, figure 1), a 13B model on a 40 GB A100 uses about 65% for the weights and almost 30% for the KV cache. The weights are fixed: what can be managed is that 30%. **The KV cache is what limits the batch size**, and therefore the throughput.

> The whole lecture can be summed up in one sentence from the paper (§3): the throughput of an inference server is memory-bound. What follows is how to use that memory well.

## 4. Iteration-level batching: Orca

If the batch is what matters, the first question is how it's built. Systems before Orca, such as NVIDIA's FasterTransformer, did **request-level batching**: gather several requests, run the model on that batch until all of them finish, and only then build the next one.

With text generation that works badly, because responses have very different lengths. A 10-token response that lands in a batch with a 1,000-token one is done after 10 iterations, but it can't go back to the client until the long one finishes. Meanwhile it holds a slot in the batch, and new requests that arrived wait outside, even if there's plenty of room for them.

Orca's proposal (OSDI 2022) is **iteration-level scheduling**: the scheduler asks the engine to run **a single iteration** of the model on the current batch, and decides again between iterations. Sequences that finished leave and go back to the client; waiting ones get in. Today this is called **continuous batching**.

There's a technical detail needed to make this work: a single iteration mixes sequences in prefill, with many tokens, and others in decode, with one. Orca solves it with **selective batching**: it batches the operations that don't depend on the sequence, like the linear layers, and processes attention for each sequence separately.

> The result Orca reports, on 175B GPT-3: 36.9 times the throughput of FasterTransformer at the same latency. It's the same idea we saw last lecture with the pipeline: don't let the slowest request hold everyone back.

The simulator shows it directly: with static batching, the first token arrives together with the full response, and throughput is stuck at what a batch waiting on its longest response can deliver. In the repository, `go run ./cmd/sim batching` quantifies it.

## 5. The memory problem

Orca solves when each sequence enters the batch, but not how many fit. That's decided by KV cache memory, and that's the problem vLLM attacks.

Previous systems stored each request's KV cache in a **contiguous chunk** of memory, because attention kernels expected the data to sit side by side. But when a request arrives nobody knows how much it will generate. The only safe option is to reserve the maximum up front, say 2048 tokens. That causes three kinds of waste, which the paper describes in §3.1:

1. **Reservation.** Space set aside for tokens that haven't been generated yet. It will be used, but meanwhile nobody else can use it.
2. **Internal fragmentation.** Reserved space that will never be used, because the response ended before the maximum. You only find out at the end.
3. **External fragmentation.** Free gaps between chunks, which add up to a lot but are each too small for a new request.

The paper measured how much of the KV cache memory held actual tokens in existing systems: **between 20.4% and 38.2%**. Between 60% and 80% of the memory that matters most was wasted.

The simulator shows it with colors: with contiguous memory, each request paints its 512-slot chunk with a strong color for the tokens it already has and a pale one for the rest. Almost the whole map ends up pale. In the repository, `go run ./cmd/sim memoria` gives a utilization of around 28% for reserving the maximum: within the range the paper measured.

> Notice the resemblance to Operating Systems: contiguous first-fit allocation, gaps that are useless, memory that's plentiful in total but not in any one place. It's the classic memory allocation problem from before paging.

## 6. PagedAttention: the KV cache as virtual memory

vLLM's solution is the same one operating systems found for process memory: **paging**. KV cache memory is split into fixed-size **blocks**, 16 tokens by default (§7.2). Each sequence sees its tokens as if they were contiguous, in logical blocks 0, 1, 2…, and a **block table** maps each logical block to a physical block that can be anywhere on the GPU. Each table entry also records how many positions in the block are filled (§4.2).

The paper makes the analogy explicit (§1):

| Operating system | vLLM |
| --- | --- |
| Page | KV cache block |
| Byte | Token |
| Process | Sequence |
| Page table | Block table |

> *Diagram: block tables · two sequences, 4-token blocks. It is in the slides.*

Sequence A has its tokens in physical blocks 7 and 1, and B in 3 and 6: neither is contiguous, and it doesn't need to be. The only unused spots are the end of each one's last block.

That gives the three properties that matter:

- **Space is allocated as needed.** When a sequence is admitted it gets just enough blocks for the prompt. When its last block fills up, it gets another one. Reservation goes away.
- **Waste is less than one block per sequence.** The only unused space is the end of the last block: at most 15 tokens per sequence, whatever its length.
- **There's no external fragmentation.** All blocks are the same, so any free block works for any sequence.

The price is paid in the attention kernel. Now a sequence's keys and values are scattered across memory, so the kernel has to read them block by block following the table. That's what the name means: **PagedAttention** is an attention algorithm that works on paged memory.

> Why not one-token blocks, so nothing is wasted? Because very small blocks don't take advantage of the GPU's parallelism when reading, and the table grows. The paper studies block size in §7.2 and picks 16 by default: big enough to read memory efficiently, small enough to waste little. It's the same trade-off as page size in an operating system.

## 7. Sharing and eviction

Once there's a table in the middle, the other virtual memory tools show up.

**Sharing with copy-on-write (§4.4).** When several responses are requested for the same prompt (parallel sampling) or beam search is used, all the sequences start with the same prompt. vLLM doesn't copy it: all their tables point to the same physical blocks, and each block carries a **reference count**. Only when a sequence wants to write to a shared block does it get a new one: the data is copied and the original's count goes down. It's Unix's `fork()`. The paper measures memory savings of 6.1% to 9.8% with parallel sampling on Alpaca and 37.6% to 55.2% with beam search; on ShareGPT, 16.2% to 30.5% and 44.3% to 66.3% (§6.3).

**FCFS scheduling (§4.5).** Requests are served in arrival order. Since the maximum is no longer reserved, in-flight sequences may grow until memory runs out. Then vLLM **evicts** the sequences that arrived last. Eviction is all or nothing: a sequence leaves with all its blocks, because it needs all of them for every step. Groups of sequences that share blocks are evicted together.

There are two ways to bring an evicted sequence back:

- **Swapping.** Copy its blocks to CPU memory and bring them back later. It's an operating system's swap.
- **Recomputation.** Throw its blocks away and, when it's readmitted, recompute them with a prefill of the prompt plus what was already generated. This works because prefill is fast: it processes all those tokens in parallel.

> The paper compares the two in §7.3: recomputation never adds more than 20% over swapping's latency, and with small blocks swapping performs poorly because it makes many small transfers. In the 16 to 64 tokens-per-block range the two perform similarly. The repository implements recomputation; adding swapping is exercise 1.

You can see it in the simulator: with paged memory and a fair amount of load, the eviction counter goes up and some sequences start over with a prefill.

## 8. Results and distributed execution

**Distributed execution (§4.6).** A large model doesn't fit on one GPU, so vLLM splits it with Megatron-LM-style tensor parallelism, as we saw in Lecture 16: each GPU holds a share of the attention heads, and they synchronize with all-reduce. There is **a single** KV cache manager, inside the centralized scheduler. All GPUs share the same mapping from logical to physical blocks; each one stores in those blocks only the keys and values of its own heads. On every iteration, the scheduler sends the same table to all of them.

**Evaluation (§6).** The models are OPT at 13B, 66B and 175B and LLaMA at 13B, on Google Cloud A100s: one 40 GB GPU for 13B, four for 66B and eight 80 GB ones for 175B. The workloads come from two datasets: ShareGPT, real conversations users shared from ChatGPT, and Alpaca, instructions generated by a model. ShareGPT has prompts about 8.4 times longer and responses about 5.8 times longer than Alpaca.

The comparison is against FasterTransformer and against three versions of Orca that differ in how much memory they reserve per request:

| System | What it reserves | Requests per second vLLM sustains, on ShareGPT |
| --- | --- | --- |
| Orca (Max) | Always 2048 tokens | 2.7× to 8× more |
| Orca (Pow2) | Up to twice what's needed | — |
| Orca (Oracle) | Exactly what's needed, known in advance | 1.7× to 2.7× more |
| FasterTransformer | Request-level batching | Up to 22× more |

Orca (Oracle) is impossible in practice: nobody knows in advance how much a request will generate. That vLLM still beats it shows the problem wasn't only over-reserving: Oracle still sets aside space up front for tokens that don't exist yet and suffers external fragmentation, and vLLM has neither (§6.2: it batches 2.2× more requests at once). The paper's summary: **2 to 4 times the throughput** of state-of-the-art systems at the same latency.

## 9. The stream back

Each token leaves the engine at the end of an iteration, and is sent to the client right then over the connection that stayed open from the start. The most common format is **server-sent events (SSE)**: an HTTP response with `Content-Type: text/event-stream` that never finishes arriving, where each event is a `data:` line followed by an empty line:

```text
data: {"delta":"La "}

data: {"delta":"luz "}

data: [DONE]
```

The exact format varies by provider. On the way back, the gateway counts output tokens for billing and quotas, and the browser appends each fragment as it arrives.

Two distributed systems problems show up here:

- **Proxies that buffer the response.** A proxy with buffering reads the whole response before forwarding it. The server sends each token on time, but the client gets everything at once at the end. In nginx you turn it off with `proxy_buffering off` or with the `X-Accel-Buffering: no` header sent by the server. In the demo, with `cmd/servidor -speed 2` and `cmd/proxy -buffer` in front, the 60 tokens the server sent every 40 ms all arrive together at 2.5 s.
- **Clients that leave.** If the user closes the tab, the server has to notice and cancel the request. Otherwise it keeps generating tokens nobody will read, holding a slot in the batch and KV cache blocks another request could use. In Go, that means watching `r.Context().Done()` in the handler and telling the engine.

The numbers for a typical request, with illustrative values: the network, tens of milliseconds; queueing and prefill, tens to hundreds; each decode token, on the order of 10 to 50 ms. A 300-token response at 30 ms per token takes 9 seconds, and nearly all of it is decode. That's why streaming matters: the user starts reading after the first token, not the last.

## 10. Demo, questions and references

The **Inference engine** simulator runs in the browser: it shows the GPU memory map filling up token by token, with static or continuous batching and contiguous or paged memory, and compares the four combinations on the same workload. The `servir-tokens` repository has the same engine in Go:

```text
go run ./cmd/sim batching      # static vs continuous (Orca)
go run ./cmd/sim memoria       # contiguous reservation vs blocks (vLLM)
go run ./cmd/sim cow           # parallel sampling with copy-on-write
go run ./cmd/servidor -speed 2 # the engine behind HTTP + SSE
go run ./cmd/proxy -buffer     # a proxy that breaks streaming
```

**Review questions**

1. Why is decode bound by memory bandwidth and not by compute? What changes in the cost of an iteration when going from 1 to 32 sequences in the batch?
2. Compute the per-token KV cache size of a model with 32 layers and 8 KV heads of 128 dimensions, in 16 bits. How many 4,000-token sequences fit in 40 GB set aside for the KV cache?
3. With static batching, why does the first token arrive with the full response? What does Orca change to avoid it?
4. Name the three kinds of waste in contiguous reservation and explain which ones paging eliminates and which one it reduces to less than a block.
5. What analogy does the paper draw between vLLM and an operating system? What plays the role of the page table?
6. Four samples of a 500-token prompt: how many 16-token blocks are copied with copy-on-write when each one writes its first token? Why not all of them?
7. Why is eviction all or nothing? When is it better to recompute instead of swapping?
8. A user closes the tab halfway through a long response. What resources stay occupied if the server doesn't notice, and how does it find out?

**References**

- W. Kwon et al. [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://arxiv.org/abs/2309.06180). SOSP 2023.
- G.-I. Yu et al. [Orca: A Distributed Serving System for Transformer-Based Generative Models](https://www.usenix.org/conference/osdi22/presentation/yu). OSDI 2022.
- A. Campodónico. [What happens after you hit send](/posts/what-happens-after-you-hit-send). 2026.
- D. Narayanan et al. [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://arxiv.org/abs/2104.04473). SC 2021 (Lecture 16).

## Run the examples

With Go installed and no dependencies, from the repository root:

```sh
cd repos/servir-tokens
go test ./...
go run ./cmd/sim batching
go run ./cmd/sim memoria
go run ./cmd/sim cow
go run ./cmd/servidor -speed 2
```
