Continuous batching — why an LLM server behaves like an operating system

Yesterday we saw why autoregressive decoding is often memory-bandwidth bound.

For one sequence, each decode step may load a huge fraction of the model weights just to generate one new token. That gives us a natural optimization:

If the weights are already being loaded, use them for as many sequences as possible.

This is the basic reason batching matters so much for LLM inference.

But ordinary fixed batching works badly for language models, because requests have wildly different prompt lengths and output lengths.

Modern inference servers therefore use continuous batching: instead of treating a batch as a fixed group of requests that must start and finish together, they continually add and remove sequences as generation proceeds.

The deeper idea is:

\[ \boxed{\text{an LLM inference server is partly a scheduler}} \]

It must decide, every few milliseconds, which tokens deserve scarce GPU compute and memory bandwidth.

Start with ordinary batching¶

Suppose four users submit requests:

A → generate 100 tokens
B → generate  10 tokens
C → generate  60 tokens
D → generate   8 tokens

A traditional batch might run:

batch = [A, B, C, D]

and process all four together.

At first this is great.

Instead of multiplying the model weights by one token vector:

\[ [1,d]\times[d,d], \]

we multiply them by four token vectors:

\[ [4,d]\times[d,d]. \]

The same weights support more useful work.

But then request D finishes after 8 tokens.

Request B finishes after 10.

Now what?

If the batch is fixed, we can end up with something conceptually like:

step  1: A B C D
step  2: A B C D
...
step  8: A B C D
step  9: A B C -
step 10: A B C -
step 11: A - C -
...
step 60: A - C -
step 61: A - - -
...
step100: A - - -

The GPU began with four useful sequences.

Near the end, it is effectively serving only A.

That wastes the opportunity to reuse model weights across more tokens.

The obvious improvement¶

Imagine new requests arrive while A is still running:

E arrives
F arrives
G arrives

Instead of waiting for A to finish, why not insert them into the empty batch slots?

Then execution might look like:

step  1: A B C D
...
step  8: A B C D
step  9: A B C E
step 10: A B C E
step 11: A F C E
...

As requests finish, new requests enter.

The batch is no longer a fixed object.

It is continuously changing.

Hence:

\[ \boxed{\text{continuous batching}} \]

The restaurant analogy¶

Yesterday we compared GPU inference to a restaurant kitchen.

Let's extend that analogy.

Imagine a chef can cook four dishes in parallel because the expensive ingredients are shared.

A naive restaurant says:

We will seat exactly four customers, finish every dish for all four customers, and only then admit another group.

That works poorly if one customer orders:

a sandwich

while another orders:

a twelve-course tasting menu.

The sandwich customer leaves quickly, but their kitchen slot remains empty until the tasting menu finishes.

A better restaurant immediately puts another order into the freed slot.

That is continuous batching.

The kitchen stays full.

Why LLM requests are unusually variable¶

Language-model requests vary along at least two major dimensions.

Prompt length¶

One request may contain:

\[ T_{prompt}=20 \]

tokens.

Another may contain:

\[ T_{prompt}=20{,}000. \]

Output length¶

One request might generate:

"Paris."

while another generates a 3,000-token report.

So even if requests arrive simultaneously, they almost never finish simultaneously.

This makes static batching particularly inefficient.

Prefill and decode also behave differently¶

Recall our two inference phases.

Prefill¶

The model processes the prompt:

\[ x_1,x_2,\ldots,x_T \]

in parallel.

Large matrix multiplications make prefill relatively compute-intensive.

Decode¶

The model generates:

\[ x_{T+1},x_{T+2},\ldots \]

one autoregressive step at a time.

Decode is often more memory-bandwidth sensitive.

So the scheduler is not merely choosing between requests.

It is choosing between different kinds of work:

prefill work
decode work

that stress the GPU differently.

A simple scheduler¶

Imagine the server has a token budget of:

\[ B=8 \]

token positions for the next GPU iteration.

It currently has six sequences decoding:

A B C D E F

Each needs one next-token decode step.

That consumes:

\[ 6 \]

token slots.

Two slots remain.

Perhaps a new request G has a 100-token prompt.

The scheduler could use the remaining capacity to begin prefilling part of G's prompt.

Conceptually:

GPU iteration:

decode:   A B C D E F
prefill:  G G

On the next iteration, the mix may be different.

This is why modern inference servers often operate in terms of tokens, not merely requests.

But prompts are not naturally one-token jobs¶

Suppose G has a prompt of:

\[ 1000 \]

tokens.

Running the entire prefill at once could monopolize the GPU.

Existing users waiting for decode tokens might suddenly experience a long pause.

Instead, the server can split the prompt into chunks.

For example:

G prompt = 1000 tokens

chunk 1 = 256
chunk 2 = 256
chunk 3 = 256
chunk 4 = 232

Then prefill work can be interleaved with decode work.

This technique is often called chunked prefill.

Conceptually:

iteration 1:
decode existing users
+ prefill G[0:256]

iteration 2:
decode existing users
+ prefill G[256:512]

iteration 3:
decode existing users
+ prefill G[512:768]

The server is time-sharing the GPU.

Now latency enters the picture¶

There are two especially important latency measurements for interactive LLMs.

Time to first token¶

Usually abbreviated:

\[ TTFT. \]

This measures:

\[ \text{request arrival} \rightarrow \text{first generated token}. \]

Long queueing or slow prefill hurts TTFT.

Inter-token latency¶

Sometimes expressed as time per output token:

\[ TPOT. \]

This measures roughly:

\[ \text{token }t \rightarrow \text{token }t+1. \]

If a user is watching text stream onto the screen, TPOT determines how smooth generation feels.

These objectives can conflict.

A scheduling conflict¶

Suppose 50 users are already decoding.

Then a new user arrives with a huge prompt.

If the scheduler says:

STOP ALL DECODE
PREFILL THE NEW 50,000-TOKEN PROMPT

the new user may get a better TTFT.

But the existing 50 users see their streams freeze.

Alternatively, if the scheduler says:

ALWAYS PRIORITIZE EXISTING DECODE

existing streams remain smooth.

But the new request may wait a long time before its prompt is processed.

So the scheduler must trade off:

\[ \boxed{ \text{throughput} \quad \text{TTFT} \quad \text{TPOT} } \]

You generally cannot optimize all three independently.

Throughput versus latency¶

Suppose a GPU can decode most efficiently with a batch of:

\[ 128 \]

sequences.

If only 20 requests are active, the server could wait until more requests arrive.

That might create a larger batch and improve throughput.

But users would sit in a queue.

So:

wait longer
→ bigger batches
→ better GPU utilization
→ worse user latency

while:

run immediately
→ smaller batches
→ lower queueing latency
→ worse GPU utilization

This is a classic scheduling problem.

The same tension appears in operating systems, databases, networks, and airline boarding.

Why continuous batching improves economics¶

Return to yesterday's arithmetic-intensity idea.

Suppose a weight matrix is:

\[ W\in\mathbb R^{4096\times4096}. \]

For one decode sequence:

\[ [1,4096]W. \]

For 128 simultaneous sequences:

\[ [128,4096]W. \]

The weight matrix itself has not grown.

But useful arithmetic per weight load has increased dramatically.

So continuous batching tries to maintain a healthy batch even though individual requests constantly terminate.

In simplified form:

\[ \boxed{ \text{more active sequences} \Rightarrow \text{more weight reuse} \Rightarrow \text{higher hardware utilization} } \]

up to the point where some other resource becomes limiting.

But batch size cannot grow forever¶

Why not simply batch 10,000 requests?

Because other costs grow.

One major cost is the KV cache.

Each active sequence owns cached keys and values for its context.

Very roughly:

\[ M_{KV} \propto B \times T \times L \times H_{KV} \times d_h. \]

Where:

\(B\) = active sequences,
\(T\) = context length,
\(L\) = number of layers,
\(H_{KV}\) = KV heads,
\(d_h\) = head dimension.

So increasing batch size increases memory consumption.

Eventually the GPU may run out of room for KV state.

A toy KV-cache example¶

Suppose one sequence consumes:

\[ 500\text{ MB} \]

of KV cache at its current context length.

Then:

\[ 100 \]

such sequences would require:

\[ 50\text{ GB}. \]

If the accelerator has 80 GB of HBM and the model weights already occupy 50 GB, those 100 sequences simply do not fit.

The scheduler therefore has another constraint:

\[ \boxed{\text{KV-cache capacity}} \]

It is scheduling both compute and memory.

Why PagedAttention was such an important idea¶

There is another problem.

Sequences grow and shrink dynamically.

If each request needs one large contiguous block of GPU memory for its KV cache, memory management becomes painful.

Imagine memory looking like:

[A A A A][B B][C C C][D D D D]

Then B finishes:

[A A A A][    ][C C C][D D D D]

Now a new request E needs a larger block than the hole left by B.

There may be enough total free memory, but not enough contiguous free memory.

This is fragmentation.

PagedAttention borrows an idea from operating systems: virtual memory.

Instead of requiring each sequence's KV cache to occupy one contiguous physical region, divide memory into fixed-size blocks or pages.

Then a sequence can logically look contiguous while physically occupying scattered blocks:

logical KV for E:

page 0 → physical block 17
page 1 → physical block 42
page 2 → physical block  9
page 3 → physical block 31

This is remarkably similar to a process's virtual address space.

The operating-system analogy becomes literal¶

At this point, an inference server starts to resemble an OS.

An operating system manages:

processes
CPU time
memory pages
priority
fairness

An LLM inference server manages:

requests
GPU iterations
KV-cache pages
priority
fairness

The mapping is surprisingly good:

Operating system	LLM server
process	generation request
CPU timeslice	GPU iteration
RAM	HBM
virtual-memory pages	KV-cache blocks
scheduler	batch scheduler
process arrival	request arrival
process termination	EOS / request completion

This is not just an analogy for teaching.

Many real inference-system design problems genuinely resemble classical systems problems.

Requests can also be preempted¶

Suppose GPU memory is full.

A high-priority request arrives.

One option is to temporarily remove another request's KV state from active GPU memory or recompute some state later.

Conceptually:

active:
A B C D

urgent request E arrives

pause D
run E
resume D later

That is preemption.

Again, the vocabulary sounds like operating systems because the underlying resource-allocation problem is similar.

Fairness matters too¶

Imagine two users.

User A requests:

\[ 10 \]

tokens.

User B requests:

\[ 10{,}000 \]

tokens.

A throughput-maximizing scheduler might make choices that cause short requests to wait behind large ones.

That can produce terrible tail latency.

A production service may therefore care about:

priority classes
maximum waiting time
per-user quotas
short-request preference
service-level objectives

The scheduler is implementing product policy as well as hardware optimization.

Why token-level scheduling is powerful¶

The crucial shift is:

Do not think of a request as one indivisible job.

A request consists of many units of work:

prompt token chunks
decode token 1
decode token 2
decode token 3
...

The scheduler can interleave these units across users.

That creates much more flexibility.

Instead of:

request A
request B
request C

the GPU sees something closer to:

A-decode
B-decode
C-prefill-chunk
D-decode
E-prefill-chunk
...

assembled into efficient batches.

Continuous batching also changes capacity planning¶

Suppose a model benchmark says:

\[ 100\text{ tokens/s} \]

for one sequence.

That does not imply the server can only produce 100 tokens/s total.

With batching, aggregate throughput might be far higher.

Perhaps:

batch 1    → 100 tokens/s total
batch 8    → 600 tokens/s total
batch 32   → 1,500 tokens/s total
batch 128  → 2,500 tokens/s total

while each individual user's stream may become somewhat slower.

This distinction is crucial:

\[ \boxed{ \text{per-user latency} \neq \text{aggregate throughput} } \]

Inference providers care intensely about the second quantity because it strongly affects cost per token.

Users usually care more about the first.

The scheduler lives between those objectives.

Connect this to model architecture¶

Notice how architectural choices now affect scheduling.

GQA¶

Smaller KV cache means:

\[ \text{more concurrent sequences fit in HBM}. \]

That enables larger effective batches.

Quantization¶

Smaller weights leave more HBM available for:

\[ \text{KV cache}. \]

Again, potentially more concurrent requests.

Sliding-window attention¶

Bounding the amount of history retained by some layers can reduce KV growth.

MoE¶

Only some experts execute per token, but routing and expert placement create new scheduling and communication challenges.

So model architecture and serving architecture cannot really be optimized independently.

A model that is mathematically elegant but awkward to batch or cache may be expensive to serve.

The deeper mental model: a GPU as a very expensive shared machine¶

Imagine hundreds of users each holding a ticket saying:

I need one more token.

Some also say:

Before that, I need 4,000 prompt tokens processed.

The GPU is an extraordinarily expensive machine capable of doing huge amounts of work, but it performs best when similar work is grouped together.

A scheduler stands in front of it.

Every iteration, the scheduler asks:

Who is ready?
Who has waited longest?
Who needs decode?
Who needs prefill?
How much KV memory is free?
How many token positions fit?
Can I form a larger batch?
Will that hurt interactive latency?

Then it constructs the next unit of GPU work.

When some sequences finish, their KV pages are reclaimed.

When new requests arrive, they enter the queue.

When prompts are large, they may be chunked.

When memory is scarce, requests may wait or be preempted.

So the serving loop looks something like:

                 ┌──────────────┐
new requests ───→│ waiting queue│
                 └──────┬───────┘
                        │
                        ▼
                 ┌──────────────┐
                 │  scheduler   │
                 └──────┬───────┘
                        │
            choose token work
                        │
                        ▼
                 ┌──────────────┐
                 │     GPU      │
                 │ prefill/decode│
                 └──────┬───────┘
                        │
                generated tokens
                        │
          ┌─────────────┴─────────────┐
          │                           │
       finished                    active
          │                           │
          ▼                           └──→ scheduler again
      free KV pages

Yesterday's lesson gave us:

\[ \text{batching} \Rightarrow \text{better weight reuse}. \]

Today's lesson adds the missing systems insight:

\[ \boxed{ \text{continuous batching} = \text{dynamically scheduling token work so the GPU stays efficiently occupied} } \]

And this is why high-performance LLM serving is not merely a problem of implementing Transformer equations quickly.

It is also a queueing problem, a memory-management problem, and a scheduling problem.

In other words, once the model is trained, operating the model efficiently starts to look surprisingly much like building an operating system.