Continuous batching — why an LLM server should not wait for a batch to finish

Over the last several lessons, we have built the pieces of a modern inference server.

We separated prefill from decode, saw how speculative decoding creates more parallel work, used quantization to reduce memory traffic, used PagedAttention to manage the KV cache efficiently, and used prefix caching to avoid repeating prefill work.

Today we will focus on the scheduler that ties many of those ideas together:

The intuition is simple:

Do not make a group of LLM requests march in lockstep until the slowest one finishes.

Instead, after every generation step, remove requests that are done and immediately insert new work.

That sounds like a small scheduling detail. In practice, it is one of the reasons a GPU can serve many interactive users efficiently.

Start with ordinary batching¶

In conventional neural-network inference, batching is straightforward.

Suppose four image-classification requests arrive:

image A
image B
image C
image D

We stack them into one tensor:

and run the model once.

Every input goes through essentially the same fixed amount of computation.

The batch starts together and ends together:

A: [==========]
B: [==========]
C: [==========]
D: [==========]

This is often called static batching.

For LLM generation, however, requests do not have fixed lengths.

LLM requests finish at different times¶

Suppose four prompts begin decoding together.

Their generated lengths happen to be:

With a rigid batch, generation looks like:

step:  1 2 3 4 5 6 7 8

A:     ● ● ●
B:     ● ● ● ● ● ● ● ●
C:     ● ●
D:     ● ● ● ● ● ●

After step 2, C is finished.

After step 3, A is finished.

After step 6, D is finished.

But if the batch cannot change until B finishes, those vacated slots do no useful work.

Conceptually:

step:  1 2 3 4 5 6 7 8

A:     ● ● ● - - - - -
B:     ● ● ● ● ● ● ● ●
C:     ● ● - - - - - -
D:     ● ● ● ● ● ● - -

The dashes are wasted opportunities.

Continuous batching fills the holes¶

Now suppose new requests E, F, and G are waiting.

The scheduler can replace completed sequences immediately.

For example:

step 1:
[A B C D]

step 2:
[A B C D]

C finishes

step 3:
[A B E D]

A finishes

step 4:
[F B E D]

...

The batch is no longer a fixed group of requests.

It is a changing set of active sequences.

That is why the technique is called:

or sometimes iteration-level scheduling.

The important scheduling boundary is not "after the whole batch."

It is roughly "after each model iteration."

The restaurant-table mental model¶

Imagine a restaurant with a table that seats eight people.

Static batching behaves strangely:

Seat eight diners together. Nobody new may sit down until all eight have finished dinner.

If one diner eats for two hours, empty seats remain unusable even after everyone else leaves.

Continuous batching says:

Whenever a diner leaves, seat the next waiting customer.

The table stays full.

The GPU is the table.

Active token positions are the diners.

The goal is to keep expensive hardware occupied with useful work rather than preserving the identity of an old batch.

Why batching matters so much during decode¶

Recall the matrix multiply from Day 46.

For one sequence, a projection during decode looks roughly like:

With \(B\) active sequences:

The same weight matrix can now be reused across \(B\) token vectors.

Increasing \(B\) raises arithmetic intensity.

So keeping the decode batch populated can improve hardware efficiency.

Continuous batching therefore converts request concurrency into weight reuse.

That is the core performance mechanism.

A concrete utilization example¶

Suppose a server starts with a batch of 8 requests.

Imagine their remaining generation lengths are:

With static batching, the batch lives for 8 decode iterations.

The number of useful token computations is:

But the batch has capacity for:

sequence-slots across those iterations.

So useful occupancy is only:

Nearly half the potential sequence-slots are empty.

Now suppose an unlimited queue of new requests exists and continuous batching immediately fills every vacated slot.

The server can keep the batch near:

for almost every iteration.

The same hardware now spends far more of its time doing useful token work.

This example is deliberately simplified, but it shows why variable output lengths make static batches inefficient.

But new requests need prefill¶

There is an immediate complication.

A newly arriving request is not ready to decode.

It first needs to process its prompt.

Suppose the current decode batch contains:

A → one decode token
B → one decode token
C → one decode token
D → one decode token

and a new request E arrives with a 20,000-token prompt.

The scheduler now has two types of work:

decode:
A B C D

prefill:
E × 20,000 prompt tokens

From Day 46, we know these are very different workloads.

Decode wants predictable low latency.

Prefill can be a large compute-heavy operation.

If E's entire prefill monopolizes the GPU, A–D may stop receiving tokens temporarily.

So continuous batching is not merely "put all available work together."

It is a scheduling policy.

The scheduler has competing goals¶

An inference server often wants several things simultaneously:

These goals can conflict.

For example, waiting briefly for more requests may create a larger, more efficient batch.

But waiting increases latency.

Prioritizing decode protects existing interactive users.

But doing so too aggressively may make new prompts wait a long time for prefill.

Scheduling is therefore an optimization problem over user experience and hardware efficiency.

Chunked prefill revisited¶

Suppose E has a 20,000-token prompt.

Instead of processing all 20,000 tokens at once:

[prefill E: 20,000 tokens]

the server can divide it into chunks:

[prefill E: tokens 1–2048]
[decode A B C D]
[prefill E: tokens 2049–4096]
[decode A B C D]
...

The exact execution can be more interleaved than this simplified diagram.

The key idea is that a huge prefill request does not have to become one indivisible scheduling unit.

Chunking lets the server trade a little prefill efficiency for smoother decode latency.

This is a recurring systems pattern:

but also create more bookkeeping and potentially less efficient kernels.

Token budget instead of request budget¶

A useful way to think about modern LLM scheduling is that the scarce unit is often not the number of requests.

It is the number of tokens processed in the next iteration.

Suppose the scheduler allows a token budget:

It might schedule:

100 decode sequences      → 100 tokens
one prefill chunk         → 3996 tokens
--------------------------------------
total                     → 4096 tokens

Or:

500 decode sequences      → 500 tokens
several prompt chunks     → 3596 tokens
--------------------------------------
total                     → 4096 tokens

The scheduler packs work into the iteration subject to memory and compute constraints.

This is more flexible than saying:

Every batch contains exactly 32 requests.

Different requests contribute very different amounts of work.

PagedAttention makes continuous batching practical¶

Now connect this to Day 49.

If every request required one fixed contiguous KV-cache allocation, dynamically adding and removing sequences from a batch would be awkward.

With paged KV memory, each active sequence simply owns a collection of blocks.

When a request finishes:

Request C completes
      ↓
release C's private KV blocks
      ↓
blocks return to free pool

When a new request enters:

Request E begins
      ↓
allocate blocks as needed

The compute batch can change without requiring every sequence's KV cache to be packed into one contiguous giant tensor.

This is an important architectural connection:

PagedAttention and continuous batching solve different problems, but they reinforce each other.

Sequence length still affects the cost of a decode token¶

A subtle point: not all decode tokens cost exactly the same amount.

Suppose:

and:

Both A and B generate one new token in the next iteration.

But B's attention operation may need to inspect a much larger KV history.

So the batch dimension may contain one new query per request, while the attention work differs across sequences.

Conceptually:

A new token → attend over 500 cached positions

B new token → attend over 50,000 cached positions

This makes scheduling long-context workloads more complicated than simply counting active sequences.

A sophisticated scheduler may care about both:

number of new tokens
context lengths of those tokens
available KV memory

Memory can become the admission-control limit¶

Suppose the GPU has enough compute capacity to decode 500 requests concurrently.

But their KV caches consume all available HBM after 300 requests.

Then:

rather than:

limits concurrency.

The scheduler cannot admit another sequence until memory becomes available.

This is why the optimizations from recent lessons compose so strongly.

Quantized KV cache:

PagedAttention:

Prefix caching:

Together they can allow more active sequences.

More active sequences give continuous batching a larger pool of work.

That can improve GPU utilization.

The effects multiply.

Throughput and latency pull in opposite directions¶

Suppose we want maximum throughput.

We might prefer a very large batch:

The GPU can reuse weights across many token vectors.

But perhaps only 200 requests are currently active.

We could wait for another 824 requests.

That would be terrible for interactive latency.

So production systems often have a dynamic compromise:

enough batching to use the GPU efficiently
but not so much waiting that users notice

Continuous batching helps because it does not require all requests to arrive together.

The server accumulates concurrency naturally over time while still allowing each request to make progress.

What happens under overload?¶

Suppose requests arrive faster than the server can complete them.

Then the queue grows.

At this point, clever batching cannot eliminate the fundamental capacity limit.

If arrival rate is:

requests per second and sustainable service rate is:

then when:

the backlog tends to grow.

Continuous batching can increase \(\mu\) by improving utilization.

But it cannot make capacity infinite.

Eventually the system needs mechanisms such as:

queueing
rate limits
admission control
request prioritization
load shedding
more replicas

This is where LLM serving becomes queueing theory and distributed systems.

Why one user's long answer can affect everyone else¶

Imagine a server with limited batch capacity.

A request generating 10,000 output tokens occupies one active sequence slot for a long time.

A request generating 20 tokens releases its slot quickly.

So output length affects not only that user's cost.

It affects how long resources remain occupied and therefore how quickly other requests can enter the active set.

This is one reason serving providers care about:

They are not merely billing controls.

They are resource-scheduling controls.

Scheduling policies can encode priorities¶

Suppose an inference cluster serves:

interactive chat
background document summarization
batch evaluation jobs

These workloads have different latency requirements.

Interactive chat may need low ITL.

Background summarization may tolerate seconds of delay.

A scheduler can assign priorities:

high priority:
interactive decode

medium priority:
interactive prefill

low priority:
offline batch work

During idle periods, batch jobs consume spare capacity.

During heavy interactive load, they yield.

This is analogous to operating-system process scheduling.

Once again, a classic systems concept reappears inside LLM infrastructure.

The deeper connection to operating systems¶

Look at the concepts from the last few lessons:

PagedAttention
→ virtual memory

prefix caching
→ memoization / shared pages

continuous batching
→ process scheduling

admission control
→ resource management

request priorities
→ scheduling classes

An inference engine increasingly resembles a small operating system whose scarce resources are:

GPU compute
HBM capacity
HBM bandwidth
KV-cache blocks
network bandwidth

and whose "processes" are active token sequences.

This is not merely an analogy.

The engineering problems genuinely have similar structure.

Continuous batching changes how we should think about a request¶

From the user's perspective, a request looks like one operation:

prompt
  ↓
model
  ↓
response

Inside the server, however, it may be decomposed into hundreds or thousands of scheduling events:

prefill chunk
decode token
decode token
decode token
pause
decode token
...

Between any two of those events, other users' work may enter or leave the GPU batch.

So an LLM request is not necessarily one contiguous execution on the hardware.

It is a stream of small pieces that the scheduler interleaves with other streams.

The key mental model¶

Imagine a busy airport runway.

Static batching says:

Choose eight airplanes. The runway belongs to those eight until every one of them has completed its entire journey.

That would be absurd.

Continuous scheduling instead asks:

What useful operation can occupy the runway next?

An airplane takes off.

The runway immediately becomes available to another airplane.

The identity of yesterday's "batch" does not matter.

For an LLM server, each decode iteration is like another runway slot:

iteration 1:
A B C D

iteration 2:
A B E D

iteration 3:
F B E D

Requests flow through the batch rather than belonging permanently to it.

That gives us today's main principle:

And this connects the last several lessons.

Quantization makes each unit of work cheaper.

PagedAttention makes its memory dynamically allocatable.

Prefix caching removes units of repeated work.

Speculative decoding tries to get more tokens from a unit of expensive work.

Continuous batching decides which units of work should run together right now.

Once many users share a model, that scheduling decision becomes almost as important as the Transformer computation itself.