LLM & VLM courseBlog
136Track 5: LLM inference and serving · session 59 of 65

Scheduling: FCFS, preemption, fairness and SLOs

A serving engine has more requests than batch slots, so after every token it must decide who runs, who waits and who is paused. This session shows why first-come-first-served makes short requests wait behind long ones, how preemption works when every paused request owns a KV cache, how FastServe’s multi-level feedback queue and the Virtual Token Counter (VTC) fix speed and fairness, and how latency targets (SLOs) and output-length prediction shape admission.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: IntermediateBefore this: Session 81 (inference metrics), Session 84 (batching basics), Session 135 (continuous batching and chunked prefill), Session 80 (the KV cache)

What you will learn

  • Why FCFS causes head-of-line blocking, and why SJF and SRPT minimize the mean completion time (with the exchange argument)
  • What preemption does to the KV cache: keep, swap or recompute, with the cost of each for Llama 3 8B
  • How FastServe’s skip-join multi-level feedback queue approximates SJF without knowing output lengths, and why long prompts must skip the top queue
  • How the Virtual Token Counter shares the GPU fairly by weighted tokens, why it lifts returning clients, and what its 2× bound says
  • How a TPOT target and KV memory together cap the batch size, and how to compute that cap
  • How output-length prediction and learning to rank make SJF-like scheduling practical, and why the P99 must be watched

Why this matters

A serving engine always has more requests than it can run at once. Every few milliseconds it must decide: which waiting requests join the batch, which running requests keep going, and which ones are paused. This decision is scheduling. The GPU does the same total work under every policy, but the users see very different waiting times.

In session 135 we learned how requests share one batch: continuous batching adds and removes requests at every decode step, and chunked prefill splits long prompts so they do not stall the decodes. This session is about who gets the batch slots and the KV-cache memory when there is not enough for everyone. Four problems appear in every real service:

  • Head-of-line blocking. With first-come-first-served (FCFS), a request that needs 2,000 output tokens can make ten requests that need 20 tokens wait behind it.
  • Preemption. To let short requests pass, we must be able to pause a long one in the middle. Its KV cache must then be kept, moved to CPU memory, or thrown away and rebuilt later. Each choice has a cost.
  • Fairness between users. One customer who sends 1,000 requests per minute should not make another customer who sends 10 wait for minutes.
  • Service-level objectives (SLOs). The service promises numbers, such as “first token within 1 second, then at least 20 tokens per second”. The scheduler must keep these promises for as many requests as possible.

These are real system choices. vLLM schedules FCFS by default, puts all running decodes into the batch before new prefills, and, when the KV cache is full, preempts requests and later recomputes them [Certain] (vLLM docs). It also offers a priority policy [Likely]. FastServe (Wu et al.) replaced FCFS with a preemptive multi-level feedback queue and reports up to 31.4× higher throughput than vLLM under the same average-latency target, on OPT models [Certain]. The Virtual Token Counter (VTC, Sheng et al.) gives each client a fair share of tokens with a proven bound [Certain]. The survey of Zhou et al. (section 6.2) lists scheduling as one of the main parts of a serving system.

What the scheduler controls, and how we score it

Think of the engine as a loop. One iteration is one forward pass of the model over the current batch. In each iteration, every running request in decode makes one new token, and requests in prefill process (part of) their prompt. Between two iterations the scheduler may change the batch. This is iteration-level scheduling (Orca), and it is what makes all the policies in this session possible: a request can be paused after any token.

The metrics come from session 81. For a request that arrives at time \(a\), gets its first token at \(t_1\) and its last (the \(n\)-th) at \(t_n\):

\[ \text{TTFT} = t_1 - a, \qquad \text{TPOT} = \frac{t_n - t_1}{n - 1}, \qquad \text{JCT} = t_n - a \tag{136.1} \]
Read the symbols
TTFT
time to first token: queueing time plus prefill time
TPOT
time per output token after the first one (the average inter-token latency)
JCT
job completion time: the full time from arrival to the last token (also called end-to-end latency)

Scheduling papers often also use the slowdown (or normalized latency) of a request: its JCT divided by its own length. A request of 5 tokens that waits 100 steps has slowdown 20; a request of 1,000 tokens that takes 1,100 steps has slowdown 1.1. Average slowdown punishes policies that make short requests wait, which is what users feel.

\[ \text{slowdown}_i = \frac{\text{JCT}_i}{n_i}, \qquad \text{goodput} = \frac{\big|\{ i : \text{TTFT}_i \le \tau_{\text{ttft}},\ \text{TPOT}_i \le \tau_{\text{tpot}} \}\big|}{T} \tag{136.2} \]

Goodput (from session 81) counts only the requests that met both SLO targets \(\tau_{\text{ttft}}\) and \(\tau_{\text{tpot}}\) in a time window \(T\). A scheduler is good when it raises goodput, not only raw tokens per second.

FCFS and head-of-line blocking

First-come-first-served runs requests in the order they arrive. It is simple, it never starves anybody, and it needs no information about the requests. But LLM requests have very different lengths: one asks “yes or no?”, another asks for a 3,000-word essay. When a long request is in front, every short request behind it waits for the long one. This is head-of-line (HOL) blocking.

Take one server that runs one request at a time. One long request of length \(L\) arrives first, then \(k\) short ones of length \(s\), all at time 0. Under FCFS the \(j\)-th short request finishes at \(L + js\). If we run the short ones first (shortest job first, SJF), the long one finishes last at \(L + ks\):

\[ \overline{\text{JCT}}_{\text{FCFS}} = \frac{L + \sum_{j=1}^{k}(L + j s)}{k+1}, \qquad \overline{\text{JCT}}_{\text{SJF}} = \frac{\sum_{j=1}^{k} j s + (L + k s)}{k+1} \tag{136.3} \]
Worked example: one long request in front

Let \(L = 100\) steps, \(k = 9\) short requests of \(s = 1\) step. FCFS: \((100 + 9 \cdot 100 + 45)/10 = 104.5\) steps on average. SJF: \((45 + 109)/10 = 15.4\) steps. SJF is 6.8 times better on average. The long request pays for it: its JCT grows from 100 to 109 steps, which is only 9% more.

This is a general result. On one server with all jobs present at time 0, sort the jobs by length \(p_{(1)} \le p_{(2)} \le \dots \le p_{(n)}\). The total completion time is

\[ \sum_{i=1}^{n} C_i = \sum_{j=1}^{n} (n - j + 1)\, p_{(j)} \tag{136.4} \]

because the \(j\)-th job delays itself and every job after it. To make the sum small, the largest weight \(n\) must multiply the smallest \(p\). So SJF minimizes the mean completion time (the “exchange argument”: swapping any long job ahead of a short one makes the sum larger) [Certain]. When jobs arrive over time, the preemptive version, shortest remaining processing time (SRPT), is optimal for the mean [Certain]. There are two catches for LLMs. First, we do not know the output length in advance. Second, preemption is not free because of the KV cache. The rest of the session deals with both.

Figure 1 runs nine requests through a small engine with 1 to 3 batch slots. Each step, every running request makes one token. Request J1 is long and arrives first.

long request J1 runningshort request runningarrived and waiting
Figure 1. Nine requests, five policies. Each row is one request; each column is one engine step. The number on the right is the request’s JCT in steps. MLFQ uses quanta of 1, 2, 4, 8 … tokens and knows nothing about lengths.
How to read Figure 1

Start with FCFS and 1 slot: J1 runs for 20 steps and all eight short requests wait behind it (mean JCT of the short ones: 32.25 steps). Switch to SJF: the short ones finish early (8.88 steps on average) and J1 finishes last. SJF with predicted lengths uses a noisy guess \(\hat n = n\, e^{\sigma z}\); raise σ and watch it make mistakes, but still beat FCFS. MLFQ does not know any length, yet it is far better than FCFS (21.67 against 30.89). Now set 2 slots: SRPT, which may pause J1 at any step, gives the lowest mean, while J1 itself gets slower. Now go back to 1 slot and shorten J1 to 4 tokens: FCFS comes close to SJF (14.89 against 10.89), because HOL blocking needs a long job, and MLFQ becomes worse than FCFS (18.22). When no job is long, MLFQ’s switching between jobs only delays everybody.

Preemption: pausing a request at a token boundary

SRPT and MLFQ are preemptive: they may stop a running request to run another one. For a classic web server, pausing a job is cheap. For an LLM, a paused request owns its KV cache: the keys and values of every token so far, which it needs to continue (session 80). There are three options [Certain]:

  1. Keep it on the GPU. The request just skips a few iterations. No extra work, but its memory stays taken, so fewer new requests fit.
  2. Swap it out to CPU memory over PCIe, and swap it back in before it runs again.
  3. Drop it and recompute. Free the memory now. When the request resumes, run a prefill over its prompt plus all tokens it already generated, which rebuilds the cache.

The size of the cache decides the price. For a model with \(n_\ell\) layers, \(n_{kv}\) key-value heads of dimension \(d_h\), and \(b\) bytes per number:

\[ \kappa = 2\, n_\ell\, n_{kv}\, d_h\, b \ \ \text{bytes per token}, \qquad T_{\text{swap}} \approx \frac{\kappa\, \ell}{B_{\text{link}}}, \qquad T_{\text{recompute}} \approx \frac{2 N \ell}{F_{\text{eff}}} \tag{136.5} \]
Read the symbols
\(\kappa\)
KV-cache bytes per token; the 2 counts keys and values
\(\ell\)
number of tokens in the request so far (prompt plus generated)
\(B_{\text{link}}\)
bandwidth of the GPU–CPU link actually achieved
\(N\)
number of model parameters; a prefill costs about \(2N\) FLOPs per token (attention adds a little more)
\(F_{\text{eff}}\)
FLOPs per second the GPU actually achieves during prefill
Worked example: swap or recompute for Llama 3 8B

Llama 3 8B has 32 layers, 8 KV heads and head dimension 128 [Certain] (its config.json). In BF16: \(\kappa = 2 \cdot 32 \cdot 8 \cdot 128 \cdot 2 = 131{,}072\) bytes, that is 128 KiB per token. A request with \(\ell = 2{,}000\) tokens owns 262 MB of cache.

Swap: assume a PCIe 5.0 x16 link that achieves 50 GB/s (peak is about 64 GB/s per direction) [Likely]: \(262\ \text{MB} / 50\ \text{GB/s} = 5.2\ \text{ms}\) one way. Recompute: \(2 \cdot 8.03 \times 10^{9} \cdot 2{,}000 = 32.1\) TFLOP. On an H100 (989 dense BF16 TFLOPS peak) at 50% utilization, that is 65 ms.

So per request, swapping is about 12 times faster in raw time here. Why does vLLM V1 recompute by default? Recompute frees memory at once and needs no CPU buffers. The rebuild is a prefill, which is compute-bound, so it can share an iteration with memory-bound decodes and use compute that would be idle (session 135). Swapping instead needs the copy to overlap with compute, or the GPU waits. vLLM’s docs say recompute has lower overhead in the V1 design [Certain]. With GQA the cache is small, so both options are cheap for short requests.

Who gets preempted? vLLM preempts the most recently admitted request first, so the oldest requests keep making progress (a FCFS-friendly rule) [Likely]. A preemptive policy like SRPT or MLFQ preempts by priority instead. Either way, preemption should be rare: every preemption wastes some work or bandwidth, and it adds a gap in the paused user’s token stream.

Algorithm 1: one iteration of a preemptive scheduler (iteration level)
  1. input: running set \(R\), waiting queue \(W\), KV blocks free \(F\), token budget per iteration \(K\), a priority function \(\pi\) (smaller runs first)
  2. sort \(R \cup W\) by \(\pi\) // FCFS: \(\pi\) = arrival time; SRPT: remaining tokens; MLFQ: queue level
  3. for each running request \(r\) that needs a new KV block do
  4.   while \(F = 0\) do preempt the request in \(R\) with the worst \(\pi\): swap its blocks out, or free them and mark it “recompute”; move it to \(W\)
  5.   give \(r\) one block, \(F \leftarrow F - 1\)
  6. for each request \(w \in W\) in order of \(\pi\) do
  7.   if \(\pi(w)\) is better than the worst \(\pi\) in \(R\) and preemption is allowed then preempt that worst request
  8.   if \(w\) fits in \(F\) and in the token budget \(K\) then move \(w\) to \(R\) (its prefill, or recompute, may be chunked) else break
  9. run one forward pass over \(R\); append one token to every decoding request; remove finished requests and free their blocks

FastServe: a preemptive multi-level feedback queue

SRPT needs the remaining length, which we do not know. Operating systems had the same problem for decades and solved it with a multi-level feedback queue (MLFQ). The idea: we cannot see how long a job is, but we can see how long it has already run. A job that has run a long time is probably a long job. So:

  • There are queues \(Q_1, Q_2, \dots, Q_m\). \(Q_1\) has the highest priority. The scheduler always runs jobs from the highest non-empty queue, FIFO inside a queue.
  • Each queue has a quantum: the amount of service a job may use in that queue. Quanta grow down the queues.
  • A new job starts at the top. When it uses up its quantum, it is demoted one queue down.

Short jobs finish while still in the top queues. Long jobs sink and run when nothing short is waiting. MLFQ approximates SJF without knowing any lengths. FastServe (Wu et al.) applies this to LLM serving, with preemption at the granularity of one output token [Certain]. Its quanta double from queue to queue, starting from the time of the shortest iteration [Certain]:

\[ q_i = 2^{\,i-1}\, q_1, \qquad i = 1, \dots, m \tag{136.6} \]

Skip-join: the prefill problem

Plain MLFQ has an LLM-specific flaw. The first iteration of a request is its prefill, and its time grows with the prompt length. A request with a 4,000-token prompt has a first iteration many times longer than a decode step. If it enters \(Q_1\), it blows through the tiny quantum in its very first iteration, and while it runs, it blocks all the short jobs in \(Q_1\). Then it is demoted step by step, wasting priority on the way. FastServe’s fix is skip-join: profile the prefill time \(t_{\text{init}}\) from the prompt length (which is known at arrival), and let the request join directly the highest queue whose quantum can hold its first iteration [Certain]:

\[ i^\star = \min\{\, i : q_i \ge t_{\text{init}} \,\} = 1 + \left\lceil \log_2 \frac{t_{\text{init}}}{q_1} \right\rceil \tag{136.7} \]
Read the symbols
\(q_i\)
quantum of queue \(i\): how much execution time a job may use there before it is demoted
\(t_{\text{init}}\)
predicted time of the request’s first iteration (its prefill), from its prompt length
\(i^\star\)
the queue where the new request starts (for \(t_{\text{init}} \le q_1\) it is queue 1)

Example: with \(q_1 = 1\) unit, a request with \(t_{\text{init}} = 3\) skips to \(Q_3\) (quantum 4); one with \(t_{\text{init}} = 8\) goes to \(Q_4\) (quantum 8). Long prompts start at lower priority. Short prompts start at the top.

Two more pieces complete FastServe. Starvation prevention: any job that has waited longer than a threshold \(\alpha\) is promoted back to \(Q_1\); the paper sets \(\alpha\) from the SLO, with a default of 300 ms [Certain]. Proactive KV-cache swapping: MLFQ keeps many paused jobs, and their caches fill the GPU. FastServe swaps caches to host memory while other jobs run, so the copy is not on the critical path. It estimates for each job when it will run next, swaps out the job that will wait longest, and swaps in the one that will run soonest [Certain]. Their OPT-175B example: one decode iteration takes about 60 ms, while moving a 2.3 GB KV cache takes about 36 ms, so the copy can hide behind the compute [Certain].

Algorithm 2: skip-join MLFQ (FastServe, simplified to one job per iteration)
  1. input: quanta \(q_1 \lt q_2 \lt \dots \lt q_m\) with \(q_i = 2^{i-1} q_1\), starvation threshold \(\alpha\)
  2. on arrival of request \(r\): estimate \(t_{\text{init}}(r)\) from its prompt length; put \(r\) at the tail of \(Q_{i^\star}\) (formula 136.7); \(\text{used}(r) \leftarrow 0\)
  3. loop every iteration:
  4.   for each waiting \(r\) with wait time \(\ge \alpha\): move \(r\) to the tail of \(Q_1\), \(\text{used}(r) \leftarrow 0\) // no starvation
  5.   pick the head \(r\) of the highest non-empty queue \(Q_i\); swap its KV cache in if needed
  6.   run one iteration of \(r\) (prefill if it has no token yet, else one decode step); \(\text{used}(r) \mathrel{+}= \) its time
  7.   if \(r\) finished then free its cache
  8.   else if \(\text{used}(r) \ge q_i\) then demote \(r\) to the tail of \(Q_{\min(i+1, m)}\), \(\text{used}(r) \leftarrow 0\)
  9.   in the background: swap out caches of jobs that will run last, swap in those that will run next

The real FastServe runs a batch of the top jobs together, not one, and demotes by more than one level when the next iteration is long [Certain]. Figure 2 keeps one job per iteration so you can follow every step.

Figure 2. Skip-join MLFQ on five requests. Quanta are 1, 2, 4, 8 time units (one decode iteration = 1 unit). Prefill times \(t_{\text{init}}\): A = 4, B = 1, C = 2, D = 1, E = 8; output lengths: A = 8, B = 3, C = 5, D = 2, E = 3 tokens. A and B arrive at time 0, C at 1, D at 3, E at 6. Starvation threshold \(\alpha = 12\).
How to read Figure 2

Each step is one iteration. The four lanes are the queues; the small numbers on a chip are the time it has used in that queue and the quantum. The bar at the bottom shows which job ran when (wide blocks are prefills). With skip-join on, A (prefill 4) starts in \(Q_3\) and E (prefill 8) in \(Q_4\), so the short requests B and D finish at once: mean JCT 15.4 units, against 17.8 for FCFS run-to-completion. In iteration 13 (time 23) A is promoted back to \(Q_1\): it has waited 12 units since it last ran. Turn skip-join off: everybody starts in \(Q_1\), every long prefill runs at top priority and blocks the others, and the mean JCT becomes 24.0, worse than FCFS.

Fairness between users: the Virtual Token Counter

So far every request was alone. A real API serves many clients (customers, apps, tenants). If client A sends 10 times more requests than client B, FCFS gives A about 10 times more GPU and makes B’s few requests wait in A’s long queue. A common fix is a request-per-minute (RPM) limit per client. Sheng et al. show that RPM limits are not work-conserving: the GPU can sit partly idle while a limited client still has requests waiting, so throughput is lost [Certain]. They want a scheduler that never idles when work exists and still shares the GPU fairly.

First, what is “service”? Counting requests is wrong, because requests have very different sizes. VTC counts tokens, with a weight for input tokens and one for output tokens:

\[ W_i(t_1, t_2) = w_p\, n_p + w_q\, n_q \tag{136.8} \]
Read the symbols
\(W_i(t_1, t_2)\)
service received by client \(i\) in the time window \([t_1, t_2)\)
\(n_p, n_q\)
input (prompt) tokens processed and output tokens generated for client \(i\) in that window
\(w_p, w_q\)
weights; the paper uses \(w_p = 1\), \(w_q = 2\), following API prices where output tokens cost about twice as much [Certain]

Fair means: two clients that both always have requests waiting (“backlogged”) receive about the same \(W\). A client that asks for less than its share gets all it asks for, quickly. This is the classic idea of fair queuing from networks, adapted to continuous batching.

How VTC works

Each client \(i\) has a counter \(c_i\) of the service it got. Three rules [Certain]:

  1. Pick the least-served client. When there is room in the batch, take the client with the smallest counter among clients with waiting requests, and admit that client’s oldest request. Add \(w_p \times\) (its input length) to the client’s counter at admission.
  2. Charge as you go. After each decode step, add \(w_q\) to the counter of every client with a running request, once per token it produced.
  3. Lift the counter of a returning client. When a request arrives from a client with nothing in the queue, raise its counter so it cannot use credit saved while it was idle:
\[ c_u \leftarrow \max\Big( c_u,\ \min_{i \in \mathcal{Q}} c_i \Big) \tag{136.9} \]

Here \(\mathcal{Q}\) is the set of clients with waiting requests. (If the queue is empty, the paper lifts \(c_u\) to the counter of the last client that left the queue.) Without the lift, a client that was quiet for an hour would return with a tiny counter and take the whole GPU until it caught up, starving everybody. The idea is “no saving up”: fairness is about the present, not about the past. The paper calls VTC without the lift “least counter first” (LCF).

The main result bounds the difference in service between any two backlogged clients \(f\) and \(g\), over any time window [Certain]:

\[ \big| W_f(t_1, t_2) - W_g(t_1, t_2) \big| \le 2 \cdot \max\big( w_p L_{\text{input}},\ w_q M \big) \tag{136.10} \]
Read the symbols
\(L_{\text{input}}\)
the maximum input length of a request
\(M\)
the maximum number of tokens that fit in one running batch (KV-cache capacity)

The bound does not grow with the window length: over an hour or a day, the gap stays the same constant. The paper also shows that some work-conserving schedule must have a gap of at least \(w_q M\), so the factor 2 is close to the best possible [Certain]. The scheduler is about 100 lines on top of S-LoRA [Certain].

Algorithm 3: Virtual Token Counter (Sheng et al., simplified)
  1. state: counters \(c_i = 0\) for all clients; waiting queue \(\mathcal{W}\); running batch \(R\); weights \(w_p, w_q\)
  2. on arrival of request \(r\) from client \(u\): if \(u\) has no request in \(\mathcal{W}\) then lift \(c_u\) by formula (136.9); append \(r\) to \(\mathcal{W}\)
  3. each iteration:
  4.   while \(\mathcal{W}\) is not empty do
  5.     \(k \leftarrow \argmin_{i \text{ with requests in } \mathcal{W}} c_i\); \(r \leftarrow\) oldest request of \(k\)
  6.     if \(r\) does not fit in memory then break
  7.     move \(r\) to \(R\); \(c_k \leftarrow c_k + w_p \cdot \text{input\_len}(r)\)
  8.   run one decode step on \(R\); for each running request of client \(i\): \(c_i \leftarrow c_i + w_q\)

VTC also works with other cost functions, for example a cost based on FLOPs, where tokens with a long prefix cost more because of attention, or a profiled cost curve, and it extends to weighted shares (a paying tier gets twice the weight) [Certain]. Figure 3 compares FCFS, LCF and VTC.

client A (heavy, 1 request per step)client B (light, 1 request per 8 steps)client C (heavy, joins later)
Figure 3. Three clients share an engine with 4 batch slots. Every request has 16 input and 8 output tokens, so it costs \(16 w_p + 8 w_q = 32\) with \(w_p = 1\), \(w_q = 2\). The engine can finish half a request per step, so A alone already overloads it. Lines show the cumulative service \(W\) of each client.
How to read Figure 3

FCFS: A’s flood fills the queue, B’s requests wait behind it (49.55 steps on average) and C gets almost nothing. LCF: B is served at once, but when C joins at step 80 its counter is 0, so C takes every slot and A is not admitted for 81 steps. That is the “saved credit” problem. VTC: C’s counter is lifted to A’s, so from then on A and C grow at the same slope (480 each in steps 120–199), and B, which asks for less than its share, gets all its 320 with zero waiting. Move the start step of C and check that the pattern stays.

SLOs and output-length prediction

A production service has explicit targets, such as \(\text{TTFT} \le 1\) s at P99 and \(\text{TPOT} \le 50\) ms. Scheduling affects both. TTFT is mostly queueing: how long a request waits for a slot and for its prefill. TPOT is mostly batch size: every running request shares each iteration, and a bigger batch makes each iteration slower. A simple model of one memory-bound decode iteration (session 82) is that it reads all weights once plus the KV cache of every request in the batch:

\[ \text{TPOT}(b) \approx \frac{P + b\, \ell\, \kappa}{\text{BW}}, \qquad b_{\max} = \min\left( \left\lfloor \frac{\tau_{\text{tpot}}\, \text{BW} - P}{\ell\, \kappa} \right\rfloor,\ \left\lfloor \frac{M_{\text{KV}}}{\ell\, \kappa} \right\rfloor \right) \tag{136.11} \]
Read the symbols
\(b\)
number of requests in the batch
\(P\)
bytes of model weights
\(\ell\)
context length of each request (assumed equal here); \(\kappa\) is KV bytes per token, formula (136.5)
BW
HBM bandwidth of the GPU
\(\tau_{\text{tpot}}\)
the TPOT target
\(M_{\text{KV}}\)
memory available for KV cache

This is a best case: it assumes full bandwidth and ignores compute, which is fair while the batch is small enough for decode to stay memory-bound. The first term of \(b_{\max}\) is the SLO limit; the second is the memory limit. An SLO-aware scheduler admits requests only up to \(b_{\max}\) and lets the rest wait (or sends them to another replica). Admitting more raises tokens per second but makes every running user slower.

Worked example: how many users fit under a 20 ms TPOT target?

Llama 3 8B in BF16 has \(P = 8.03 \times 10^9 \times 2 = 16.06\) GB. On an H100 SXM (80 GB, 3.35 TB/s), reading the weights alone takes \(16.06 / 3350 = 4.79\) ms. Each request with \(\ell = 2{,}048\) tokens adds \(2{,}048 \times 131{,}072\) bytes = 268 MB, which is 0.080 ms more per iteration.

SLO limit: \(\lfloor (20 - 4.79)/0.080 \rfloor = 189\) requests. Memory limit, if 90% of 80 GB is usable: \(\lfloor (72 - 16.06)\ \text{GB} / 268\ \text{MB} \rfloor = 208\). So \(b_{\max} = 189\), TPOT is 19.94 ms, and the GPU makes \(189 / 0.01994 \approx 9{,}479\) tokens per second at best. With a looser 50 ms target, memory becomes the limit (208 requests) and TPOT is only 21.5 ms.

TPOT(b), formula (136.11)TPOT targetKV-memory limit
Figure 4. SLO-aware admission for Llama 3 8B (BF16) on one H100 SXM, with the best-case memory-bound model (136.11). The dot marks the largest batch that meets both the TPOT target and the memory limit.
How to read Figure 4

The solid line rises with batch size because each request adds its KV cache to every iteration’s reads. Where it crosses the dashed target line, the SLO stops you; at the shaded wall, KV memory stops you. Long contexts (16K, 32K) make each request expensive, so few users fit and memory is often the limit first. Short contexts and a strict target make the SLO the limit. A target below 4.79 ms cannot be met at all: that is the time to read the weights once.

Deadline-aware ordering

Given targets, the scheduler can also choose the order. Earliest deadline first (EDF) runs the request whose TTFT deadline \(a_i + \tau_{\text{ttft}}\) comes soonest. Under heavy overload, EDF can fail badly, because it spends time on requests that will miss anyway. A common fix is to drop or delay requests that cannot make their deadline any more, and serve those that still can [Likely]. Andes (Liu et al.) goes one step further and schedules at the token level to maximize users’ quality of experience: a user who reads slowly does not need tokens faster than they read, so their request can be paused briefly while another user catches up [Certain].

Predicting the output length

SJF and SRPT beat FCFS, but they need lengths. The prompt length is known; the output length is not. Three ways to get it:

  • Ask the model. Zheng et al. let the LLM itself estimate its response length (“response length perception”) and group requests of similar predicted length into one batch, so they finish together; they report 86% higher throughput with a LLaMA-based model [Certain].
  • A small predictor. S³ (Jin et al.) trains a small classifier on the prompt to predict the output length bucket, sizes the KV allocation by it, and handles mispredictions; it reports 6.49× higher throughput than systems that assume the worst-case length [Certain].
  • Predict the order, not the number. Fu et al. argue that exact lengths are hard to predict but the ranking of requests by length is easier. They train a ranker with learning to rank and approximate SJF with it; they report 2.8× lower latency for chatbot serving and 6.5× higher throughput for synthetic data generation [Certain].

The third idea fits the math: SJF (formula 136.4) needs only the order of the jobs, not their exact sizes. A predictor that gets the order mostly right gives most of the gain, as the “SJF (predicted)” option in Figure 1 shows. Two cautions: a prediction can be badly wrong (a “short” request that writes an essay), so pair it with preemption or MLFQ-style demotion; and strict SJF starves long requests under load, so add aging (raise the priority of a request as it waits), as FastServe does with \(\alpha\).

The code: a small scheduling simulator

This simulator mirrors Figure 1 on a random workload: 200 requests, Poisson-like arrivals, log-normal output lengths (many short, a few very long, as in chat traffic), 8 batch slots. It compares FCFS, SJF with a noisy length predictor, MLFQ with doubling quanta, and SRPT with true lengths. The last lines show the VTC rules. It is deterministic: run it twice and you get the same numbers.

import torch
torch.manual_seed(0)

# A toy iteration-level engine: B batch slots, one token per running request per step.
N, B = 200, 8
arrival = torch.cumsum(torch.distributions.Exponential(0.22).sample((N,)), 0).floor().long()
length  = torch.distributions.LogNormal(3.0, 1.0).sample((N,)).ceil().long().clamp(1, 1000)
pred    = length.float() * torch.exp(0.5 * torch.randn(N))     # a noisy length predictor

def simulate(policy):
    rem, lvl, used, enq = length.clone(), [0] * N, [0] * N, arrival.tolist()
    done, running, t = [None] * N, [], 0
    while any(d is None for d in done):
        ready = [i for i in range(N) if arrival[i] <= t and done[i] is None]
        if policy in ("fcfs", "sjf_pred"):                  # non-preemptive: keep running jobs
            running = [i for i in running if done[i] is None]
            key = (lambda i: arrival[i].item()) if policy == "fcfs" else (lambda i: pred[i].item())
            waiting = sorted((i for i in ready if i not in running), key=key)
            running += waiting[: B - len(running)]
            batch = running
        elif policy == "srpt":                              # preemptive, oracle remaining length
            batch = sorted(ready, key=lambda i: rem[i].item())[:B]
        else:                                               # "mlfq": no length knowledge
            batch = sorted(ready, key=lambda i: (lvl[i], enq[i]))[:B]
        for i in batch:
            rem[i] -= 1
            if rem[i] == 0:
                done[i] = t + 1
            elif policy == "mlfq":
                used[i] += 1
                if used[i] >= 2 ** lvl[i]:                  # quantum doubles per level, formula (136.6)
                    lvl[i], used[i], enq[i] = lvl[i] + 1, 0, t + 1
        t += 1
    jct = torch.tensor(done) - arrival
    return jct.float().mean().item(), jct.float().quantile(0.99).item()

for p in ["fcfs", "sjf_pred", "mlfq", "srpt"]:
    mean, p99 = simulate(p)
    print(f"{p:9s} mean JCT {mean:7.1f}   p99 JCT {p99:7.1f}  (steps)")

# Virtual Token Counter: pick the backlogged client with the smallest counter, formulas (136.8)-(136.9)
def vtc_pick(counters, queued_clients):
    return min(queued_clients, key=lambda u: (counters[u], u))

def vtc_on_arrival(counters, u, queued_clients):
    if u not in queued_clients and queued_clients:          # counter lift: no saved-up credit
        counters[u] = max(counters[u], min(counters[v] for v in queued_clients))

c = {"A": 900.0, "B": 0.0, "C": 1500.0}
vtc_on_arrival(c, "B", ["A", "C"])
print(c, vtc_pick(c, ["A", "B", "C"]))

Output with PyTorch 2.8 on CPU (about 5 seconds):

fcfs      mean JCT   108.4   p99 JCT   295.7  (steps)
sjf_pred  mean JCT    71.5   p99 JCT   546.8  (steps)
mlfq      mean JCT    78.4   p99 JCT   812.2  (steps)
srpt      mean JCT    53.8   p99 JCT   571.8  (steps)
{'A': 900.0, 'B': 900.0, 'C': 1500.0} A

Read it carefully. SRPT halves the mean against FCFS, and a predictor with large noise (\(\sigma = 0.5\), so a guess is often off by 1.6× or more) still gets most of that gain. But all three non-FCFS policies make the P99 worse, and MLFQ without starvation prevention is the worst at the tail: long requests sink to the bottom queue and wait behind every newcomer. This is exactly why FastServe adds the promotion threshold \(\alpha\). In the last line B returned with counter 0, was lifted to 900 (the smallest counter in the queue), and wins the tie-break only by name: A and B now share fairly, and C waits until they catch up.

Where this is used

SettingTypical policyWhy
vLLM (default)FCFS; decodes first, then prefills in the token budget; preempt by recompute when KV memory runs out [Certain]Simple, no starvation, predictable; chunked prefill limits the worst HOL effect of long prompts
Interactive chat with a TTFT and TPOT SLOSLO-aware admission (cap the batch, formula 136.11), priority to interactive traffic, agingGoodput, not raw throughput, is what users and contracts measure
Multi-tenant API (many customers on one model)Fair queuing by weighted tokens (VTC), plus per-tier weightsA heavy tenant must not slow down a light one, and the GPU must not idle
Offline batch jobs (evaluation, synthetic data, labeling)Throughput-first; group by predicted length; run at low priority behind interactive workNo user is waiting; length grouping reduces wasted slots (Zheng et al., Fu et al.)
Video-RAG and video question answeringSeparate long-prompt requests (thousands of visual tokens) by skip-join-like priority or a separate prefill poolA video request’s prefill is long; without care it blocks short chat turns (session 137)
Live key-moment detection and alerts on a video streamStrict priority plus deadlines (EDF) for alert requests; captions and summaries as background workAn alert that arrives late is worthless; a summary can wait
Video retrieval, classification and fingerprinting with an LLM or VLM re-rankerShort, fixed-length outputs, so FCFS with batching is fine; fairness across indexing jobsLengths are known and equal, so HOL blocking is small

Common mistakes

  • Optimizing only the mean. SJF and SRPT lower the mean JCT but can starve long requests. Report P50 and P99, and add aging or a starvation threshold.
  • Ignoring the cost of preemption. A preemption either wastes recompute FLOPs or uses PCIe bandwidth. A policy that preempts every few steps can lose more than it gains. Keep a minimum run time or quantum.
  • Putting long prompts at the top priority. In a token-quantum MLFQ, a long prefill uses its whole first iteration at top priority and blocks short jobs. Use the prompt length (skip-join) or chunked prefill.
  • Counting requests instead of tokens for fairness. A client with few huge requests can then take most of the GPU. Charge by weighted input and output tokens (formula 136.8).
  • Letting idle clients bank credit. Least-counter-first without the lift (136.9) lets a returning client starve everybody.
  • Trusting length predictions blindly. Pair predictions with a fallback: preempt or demote a request that runs much longer than predicted.
  • Admitting until memory is full. The memory limit is not the SLO limit. A full batch can violate the TPOT target for every user at once (Figure 4).
  • Benchmarking at one arrival rate. Policies look the same at low load, where the queue is empty. Their differences appear near and above full load. Sweep the request rate.

Interview questions

What is head-of-line blocking in LLM serving, and why is it worse than in a typical web server?basic
With FCFS, a request at the head of the queue that takes a long time makes every request behind it wait, even if they need only a few tokens. It is worse for LLMs because request lengths vary by orders of magnitude (a few tokens to thousands), and the length is unknown at arrival. With one long request of 100 steps in front of nine requests of 1 step, the mean JCT is 104.5 steps under FCFS and 15.4 under SJF.
Why does SJF minimize the mean completion time?core
On one server with all jobs present, the total completion time is \(\sum_j (n-j+1)\,p_{(j)}\): the \(j\)-th job delays itself and all later jobs. The largest multiplier should go to the smallest job. If a longer job ran right before a shorter one, swapping them lowers the sum (exchange argument). With arrivals over time, the preemptive SRPT is optimal for the mean.
You do not know output lengths. How can you still get most of the benefit of SJF?core
Two ways. (1) Use attained service as a signal: a multi-level feedback queue starts every job at high priority and demotes it after it uses its quantum, so short jobs finish early and long ones sink (FastServe). (2) Predict: a small model or the LLM itself predicts the output length or a length bucket, or a learned ranker predicts the order of requests by length (learning to rank). SJF needs only the order, so a ranker is enough. Always add a fallback for mispredictions and aging against starvation.
What is skip-join in FastServe, and what problem does it solve?advanced
In MLFQ every job usually starts in the top queue with the smallest quantum. For an LLM the first iteration is the prefill, whose time grows with the prompt. A long prompt would use far more than the top quantum in one iteration while blocking short jobs, then be demoted step by step. Skip-join estimates the prefill time from the prompt length and puts the job directly in the highest queue whose quantum is at least that time: \(i^\star = \min\{i : q_i \ge t_{\text{init}}\}\), with quanta doubling per queue.
A request is preempted. What happens to its KV cache? Compare the options.core
Keep it on the GPU (no extra work, but memory stays taken), swap it to CPU memory (costs \(\kappa \ell / B_{\text{link}}\) each way and CPU buffers; it must overlap with compute to be hidden), or drop it and recompute (a prefill over prompt plus generated tokens, about \(2N\ell\) FLOPs, but memory is freed at once and the work is compute-bound, so it can share iterations with memory-bound decodes). For Llama 3 8B and 2,000 tokens: 262 MB, about 5 ms to swap at 50 GB/s versus about 65 ms to recompute at half of H100 peak. vLLM V1 defaults to recompute because it has lower overhead in its design.
Why are request-per-minute limits a poor way to get fairness?basic
They are not work-conserving: a client at its limit is blocked even when the GPU has spare capacity, so throughput is wasted. They also count requests, not work, so one client with few long requests can still use most of the GPU. Inside the limit, requests are still served FCFS, so a burst still blocks others.
Explain the Virtual Token Counter and why it needs a counter lift.core
Each client has a counter of weighted service, \(w_p\) per input token and \(w_q\) per output token (1 and 2 in the paper). When the batch has room, the scheduler admits the oldest request of the backlogged client with the smallest counter, and counters grow as tokens are processed. Without a lift, a client that was idle has a small counter and on return monopolizes the GPU until it catches up, starving others. The lift sets a returning client’s counter to at least the minimum counter of the waiting clients, so no credit is saved while idle.
What fairness guarantee does VTC give, and what do the terms mean?advanced
For any two clients that are backlogged during a window, the difference in received service is at most \(2\max(w_p L_{\text{input}}, w_q M)\), where \(L_{\text{input}}\) is the largest input length and \(M\) the largest number of tokens in a running batch. The bound is independent of the window length, so the shares converge. The authors also show a lower bound of \(w_q M\) for some work-conserving schedule, so VTC is within a factor of 2 of the best possible bound.
Your service has a 50 ms TPOT SLO and you see violations at high load. What do you do?core
TPOT rises with batch size because every iteration reads every running request’s KV cache. Cap the batch with SLO-aware admission (\(b_{\max}\) from \(\text{TPOT}(b) \le \tau\)) so excess requests wait or go to another replica. Use chunked prefill so prefills do not create long iterations, separate long-context requests, or disaggregate prefill and decode. Measure per-request TPOT at P99, not only the mean, and add capacity if goodput is still too low.
Why can earliest-deadline-first scheduling fail under overload, and how do you fix it?advanced
EDF always serves the most urgent request. Under overload, many requests are already late or will be; EDF keeps spending time on them, so others become late too (a domino effect) and goodput collapses. Fixes: admission control, dropping or deprioritizing requests that cannot meet their deadline any more, and scheduling for goodput (serve requests that can still make it). Token-level schemes such as Andes also use the fact that a reader does not need tokens faster than they read.
Design the scheduler for an API with free and paid tiers, chat and batch traffic.advanced
Classes first: interactive chat with SLOs above batch jobs; batch only fills spare capacity and is preempted first (by recompute, since it is not latency-sensitive). Inside the interactive class, weighted fair queuing by tokens (VTC with higher weight for paid tenants) so no tenant starves others. Within a tenant, a length-aware order (MLFQ or a learned ranker) with aging. Admission capped by the TPOT SLO and KV memory. Monitor goodput and P99 TTFT per tier; route overflow to other replicas.

Exercises

  1. One server, all at time 0: one request of 50 steps and four requests of 2 steps each. Compute the mean JCT under FCFS (long first) and under SJF.
  2. FastServe-style quanta with \(q_1 = 1\) decode iteration, doubling. A request’s prefill is estimated at 3.5 iterations. Which queue does it join with skip-join?
  3. Llama 3 8B, BF16, a paused request with 4,096 tokens. How large is its KV cache, and how long does one swap-out take at 50 GB/s?
  4. With \(w_p = 1\) and \(w_q = 2\), what is the VTC cost of one request with 300 input and 100 output tokens? Client A sends 10 of them; client B sent none so far but now arrives while A is the only waiting client with counter 5,000. What is B’s counter after the lift?
  5. Use formula (136.11) with the numbers of the worked example, but \(\ell = 4{,}096\) and a TPOT target of 30 ms. What is \(b_{\max}\), which limit binds, and what is the TPOT then? Check it in Figure 4.
  6. In Figure 2, turn skip-join off. Explain in two sentences why the mean JCT gets worse than FCFS.
Answerscheck
1. FCFS: completions 50, 52, 54, 56, 58, mean 54. SJF: 2, 4, 6, 8, 58, mean 15.6. 2. \(q_3 = 4 \ge 3.5\) and \(q_2 = 2 \lt 3.5\), so \(Q_3\) (formula 136.7: \(1 + \lceil \log_2 3.5 \rceil = 3\)). 3. \(4{,}096 \times 131{,}072 = 537\) MB; \(537\ \text{MB} / 50\ \text{GB/s} = 10.7\) ms. 4. \(300 + 2 \cdot 100 = 500\); A’s ten requests cost 5,000. B is lifted to \(\max(0, 5{,}000) = 5{,}000\), so it cannot jump ahead with saved credit. 5. Weights 4.79 ms, each request 0.160 ms: SLO limit \(\lfloor (30 - 4.79)/0.160 \rfloor = 157\); memory limit \(\lfloor 55.94\ \text{GB} / 0.537\ \text{GB} \rfloor = 104\). Memory binds, \(b_{\max} = 104\), and TPOT \(= (16.06 + 104 \times 0.537)/3.35 = 21.5\) ms, well under the target. 6. Every request starts in \(Q_1\), so the long prefills of A (4 units) and E (8 units) run at top priority, and the short requests that arrive meanwhile wait behind them, which is HOL blocking again. Then all jobs are demoted together and the decodes interleave, so even the short jobs B and D finish late (26 and 18 units instead of 3 and 4).

Key takeaways

  • Iteration-level scheduling lets the engine change the batch after every token; the policy decides TTFT, TPOT and JCT (136.1) and goodput (136.2), even though total work is the same.
  • FCFS suffers head-of-line blocking (136.3). SJF minimizes the mean completion time (136.4); SRPT is its preemptive, optimal version, but both need lengths and can starve long jobs.
  • Preemption costs memory, PCIe bandwidth or recompute (136.5). For Llama 3 8B a 2,000-token cache is 262 MB: about 5 ms to swap, about 65 ms to recompute; vLLM V1 recomputes by default.
  • FastServe uses an MLFQ with doubling quanta (136.6), skip-join by prefill time (136.7), starvation promotion and proactive KV swapping.
  • VTC shares the GPU by weighted tokens (136.8), lifts returning clients (136.9), and bounds the service gap by \(2\max(w_p L_{\text{input}}, w_q M)\) (136.10).
  • SLO-aware admission caps the batch where TPOT meets the target or memory runs out (136.11). Output-length prediction or ranking makes SJF-like ordering possible; always add a fallback and aging.

Key formulas

\[ \sum_i C_i = \sum_j (n-j+1)\, p_{(j)}, \qquad i^\star = \min\{ i : 2^{i-1} q_1 \ge t_{\text{init}} \}, \qquad \kappa = 2 n_\ell n_{kv} d_h b \]
\[ c_u \leftarrow \max\big(c_u, \min_{i \in \mathcal{Q}} c_i\big), \qquad |W_f - W_g| \le 2\max(w_p L_{\text{input}}, w_q M), \qquad \text{TPOT}(b) \approx \frac{P + b \ell \kappa}{\text{BW}} \]

References for this session

  1. Wu et al. (2023). Fast Distributed Inference Serving for Large Language Models (FastServe)
  2. Sheng et al. (2024). Fairness in Serving Large Language Models (VTC)
  3. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  4. Wu et al. (2023). Fast Distributed Inference Serving for Large Language Models (FastServe)
  5. Sheng et al. (2024). Fairness in Serving Large Language Models (VTC)
  6. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  7. Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
  8. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  9. Agrawal et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
  10. Fu, Zhu, Su, Qiao, Stoica, Zhang (2024). Efficient LLM Scheduling by Learning to Rank
  11. Zheng, Ren, Xue, Luo, Jiang, You (2023). Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
  12. Jin, Wu, Brooks, Wei (2023). S3: Increasing GPU Utilization during Generative Inference for Higher Throughput
  13. Liu, Chung, Wu, Lai, Lee, Chowdhury (2024). Andes: Defining and Enhancing Quality-of-Experience in LLM-Based Text Streaming Services