5. The engine¶
Replace the per-turn service time with an engine. Each iteration allocates a token budget across the requests it is running and then admits waiting requests with the remaining budget. This model allows prefill and decode to share an iteration.
The program¶
// Chapter 5: the engine.
// The `fifo` stage of chapters 3 and 4 served one turn at a time. A real
// LLM engine runs *iterations*: every iteration hands a token budget to the
// requests it is already running — one token to each decoding request, a
// chunk to each prefilling one — and then admits waiting requests with
// whatever budget is left. Prefill and decode share the same iteration.
use "std/args";
let B = 2048; // token budget per iteration (max_num_batched_tokens)
let bs = 16; // tokens per block
let alpha = 2e-5; // compute per scheduled token (s)
let omega = 2e-4; // weights read per iteration (s)
let beta = 2e-9; // KV read per iteration per resident token (s)
let p = 0.8;
fn main() {
let max_seqs = args.number("max_seqs", 16); // how many requests may run at once
let blocks = args.number("blocks", 4000); // KV blocks
let Lambda = args.number("Lambda", 0.5);
let Z = args.number("Z", 3.0);
device gpu {
compute (t) = t * alpha;
hbm (k) = omega + beta * k;
kv cap blocks * bs;
}
pool kv on gpu { block bs; evict lru; preempt lifo; }
engine llm on gpu {
reqs cap max_seqs;
tokens cap B;
// what the engine does with one request: reuse what the cache holds of
// the prompt, prefill the rest, decode, and leave it all cached
request (prompt, output) {
// how much of the prompt the cache could supply, in whole blocks
set hitmax = floor((prompt - 1) / bs) * bs;
// read when the request is admitted: while it waits, its prefix is
// still evictable
at admission { reused = min(cachedin(kv), hitmax); }
// a request preempted runs again from here; count its hit once
set c = min(cached, floor((prompt - 1) / bs) * bs);
branch (computed == 0) { observe hit = c > 0; }
prefill (prompt - c) growing kv;
decode (output - 1) growing kv;
cache (prompt + output);
}
schedule {
advance running;
// a running slot, and the blocks of the reused prefix plus the chunk
// the budget left allows; only if the whole prompt fits, as vLLM's
// default scheduler_reserve_full_isl (config/scheduler.py:191)
admit waiting while (running.preempted == 0)
taking reqs (1), kv (min(prompt, reused + budget_left(llm))) reserve (prompt);
}
// an iteration costs whichever is larger: reading the weights and the
// running requests' KV, or computing the tokens it scheduled
execute (max(hbm(batch.kv_decode + batch.kv_prefill), compute(batch.tokens)));
}
pool reqs on llm { queue fifo; }
workload {
arrive poisson(Lambda);
init { set K = 0; }
turn {
set n = K == 0 ? ~uniform(1000, 3000) : ~exp(500);
set o = ~exp(200) + 1;
}
// the conversation: a request per turn, then a tool call and the next
// turn, or the end
session {
loop {
turn;
set K = prompt + o;
branch with (p) { tool (~exp(Z)); } else { drop kv; end; }
}
}
}
// a turn is one request to the engine
server {
set prompt = K + n;
llm (prompt, o);
}
}
Its deployment, drawn by serq draw:
The engine on its device¶
The stage engine of chapters 3 and 4 is now an engine, and engine is
the word that declares one, so the engine is named llm. Leaving its
request aside for now:
device gpu {
compute (t) = t * alpha;
hbm (k) = omega + beta * k;
kv cap blocks * bs;
}
pool kv on gpu { block bs; evict lru; preempt lifo; }
engine llm on gpu {
reqs cap max_seqs;
tokens cap B;
request (prompt, output) { … }
schedule {
advance running;
admit waiting while (running.preempted == 0)
taking reqs (1), kv (min(prompt, reused + budget_left(llm))) reserve (prompt);
}
execute (max(hbm(batch.kv_decode + batch.kv_prefill), compute(batch.tokens)));
}
pool reqs on llm { queue fifo; }
The device says what the hardware offers: the time to compute t
tokens, the time to read k tokens of KV, and the KV capacity. pool kv
on gpu is the device's memory, with its rules: blocks, eviction,
preemption. The engine says what runs on it. reqs cap is how many
requests may run at once (max_num_seqs), tokens cap the tokens one
iteration may schedule (max_num_batched_tokens). pool reqs on llm
holds the engine's reqs cap: its running slots, and the queue of
requests waiting for one, served fifo.
schedule is what each iteration does: give the running requests their
tokens, then admit waiting ones while nothing was preempted. taking says
what an admission takes of a request, below. execute is how long the
iteration takes, as an expression in what it scheduled:
| Value | Meaning |
|---|---|
batch.tokens |
tokens scheduled this iteration |
batch.decoding |
decoding requests scheduled |
batch.prefilled |
prefill tokens scheduled |
batch.kv_decode, batch.kv_prefill |
memory held by the scheduled decode / prefill requests |
batch.attention |
attention work of the prefill chunks, \(\sum n(K + n/2)\) |
The cost is the larger of the time to read weights and KV memory and the
time to compute the scheduled tokens. Fit these parameters to measurements
of the engine you want to model. each at most (c) limits each request's
prefill in an iteration, and advance running takes an order and an
only; see Engines on devices.
What the engine does with one request¶
prompt and output are the request's parameters: its prompt and output
lengths in tokens, which the server passes when it calls the engine
(below).
request (prompt, output) {
set hitmax = floor((prompt - 1) / bs) * bs;
at admission { reused = min(cachedin(kv), hitmax); }
set c = min(cached, floor((prompt - 1) / bs) * bs);
branch (computed == 0) { observe hit = c > 0; }
prefill (prompt - c) growing kv;
decode (output - 1) growing kv;
cache (prompt + output);
}
The request block reads top to bottom in the order things happen to one
request. Before it is admitted, it computes how much of its prompt the
cache could supply, in whole blocks (hitmax; the last token is always
recomputed). It waits in reqs's queue until an iteration's admit
waiting takes it. Then it prefills what the cache does not hold, decodes
its output, and when it ends, cache (prompt + output) leaves its
sequence cached for the session's next turn, as in chapter 4.
at admission { reused = …; } names a value read when the request is
admitted, not when it arrives. A prefix may be evicted while the request
waits, so reading the cache earlier in a set would use an outdated
value. taking reads reused.
prefill (e) and decode (e) are the engine's work on the request,
in tokens. The engine splits them over iterations: a prefill takes the
chunks the budget allows, a decode one token per iteration.
growing kv allocates additional blocks as the request advances instead
of reserving its full memory at admission. With preempt lifo, a failed
growth can preempt the most recently admitted running request. The
preempted request goes back to the queue and runs from its admission
again; see preemption semantics for the state preserved
across retries. That is why the program observes hit only on the first
attempt, where computed is 0.
The time to the first token needs no observe: the report's client
section gives it for every turn, from the turn; to the token the
prefill samples, once however many times the request is preempted, and
the time per output token after it
(what the client sees).
What an admission takes¶
admit waiting while (running.preempted == 0)
taking reqs (1), kv (min(prompt, reused + budget_left(llm))) reserve (prompt);
taking sits on admit waiting because that is when the scheduler sizes
the request: it reads the request's parameters and its at admission
names, at the moment the iteration admits it.
reqs (1) is one running slot.
kv (min(prompt, reused + budget_left(llm))) is the blocks of the
reused prefix plus the prefill chunk the iteration's budget still allows,
capped by prompt. budget_left(llm) is the token budget left after
serving the running requests.
reserve (prompt) admits the request only if the whole prompt fits
beside the memory the running requests hold, although only the first
chunk is allocated. This is vLLM's default (scheduler_reserve_full_isl).
Without it, a long prompt is admitted on its first chunk and its later
chunks preempt other requests; at the loads of the next chapter, that
raises the preemption count about tenfold.
Waiting requests are admitted only by admit waiting, in an iteration,
with the budget left, and never in an iteration that preempted: pool reqs
on llm hands the pool's queue to the engine's scheduler.
The workload and the server¶
The session inside workload describes the conversation: each turn;
waits for a response before the client decides whether to continue. The
server says what a turn is:
one request to the engine, with the session's context and new tokens as
its prompt and o as its output. llm (prompt, o) runs the engine's
request with its parameters prompt and output bound to these. The
deployment figure shows the server side.
Running it¶
run: horizon 20000 end 20000 warmup 2000 seed 1 events 9160272 arrivals 9905 ended 8905 turns 43948 mean live 6.012
observe count mean 95% CI cv2 p99
------- ----- ------ ------- ----- ------
hit 43948 0.7932 ±0.0030 0.261 1.0000
client count mean 95% CI cv2 p99
-------- ----- --------- ---------- ----- ---------
ttft 43948 0.01798 ±0.00045 1.329 0.07634
tpot 43949 0.0002383 ±0.0000060 4.047 0.0006076
response 43949 0.06272 ±0.00095 0.665 0.23843
stage number util done thru wait service iters
----- ------ ----- ----- ------ ------ ------- -------
llm 0.151 0.136 87897 4.8832 0.0000 0.0310 9111287
tool 5.859 0.999 35045 1.9469 0.0000 3.0093 0
step prefill only decode only mixed idle decodes decode batch decode step itl p50 itl p99
---- ------------ ----------- ----- ----- ------- ------------ ----------- -------- --------
llm 0.036 0.095 0.006 0.864 0.109 1.078 0.000223 0.000209 0.000243
pool used cached queue holders wait admits evict(n) evict(u) preempt spill rej stuck
---- ----- ------- ----- ------- ------ ------ -------- -------- ------- ----- --- -----
kv 723.3 28911.2 0.000 0.151 NaN 48984 198 1640352 0 0 0 0
reqs 0.2 0.0 0.002 0.151 0.0007 48984 0 0 0 0 0 0
done 87897 at llm against 43 948 turns — two runs per turn, prefill
and decode.
TTFT is now separately observable, and at 18 ms it is a different quantity from the 63 ms response. Iteration-level simulation gives both.
wait NaN on the kv pool
An admission that takes several pools joins the queue of the first
one taking names, reqs, so kv never has a queue of its own and has
no queue-wait samples. Read the wait on reqs.
Next: turn the load up. → The cliff