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.
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\):
- 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.
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\):
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
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.
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]:
- 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.
- Swap it out to CPU memory over PCIe, and swap it back in before it runs again.
- 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:
- 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
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.
- input: running set \(R\), waiting queue \(W\), KV blocks free \(F\), token budget per iteration \(K\), a priority function \(\pi\) (smaller runs first)
- sort \(R \cup W\) by \(\pi\) // FCFS: \(\pi\) = arrival time; SRPT: remaining tokens; MLFQ: queue level
- for each running request \(r\) that needs a new KV block do
- 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\)
- give \(r\) one block, \(F \leftarrow F - 1\)
- for each request \(w \in W\) in order of \(\pi\) do
- if \(\pi(w)\) is better than the worst \(\pi\) in \(R\) and preemption is allowed then preempt that worst request
- 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
- 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]:
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]:
- 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].
- input: quanta \(q_1 \lt q_2 \lt \dots \lt q_m\) with \(q_i = 2^{i-1} q_1\), starvation threshold \(\alpha\)
- 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\)
- loop every iteration:
- for each waiting \(r\) with wait time \(\ge \alpha\): move \(r\) to the tail of \(Q_1\), \(\text{used}(r) \leftarrow 0\) // no starvation
- pick the head \(r\) of the highest non-empty queue \(Q_i\); swap its KV cache in if needed
- run one iteration of \(r\) (prefill if it has no token yet, else one decode step); \(\text{used}(r) \mathrel{+}= \) its time
- if \(r\) finished then free its cache
- 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\)
- 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.
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:
- 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]:
- 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.
- 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.
- 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:
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]:
- 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].
- state: counters \(c_i = 0\) for all clients; waiting queue \(\mathcal{W}\); running batch \(R\); weights \(w_p, w_q\)
- 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}\)
- each iteration:
- while \(\mathcal{W}\) is not empty do
- \(k \leftarrow \argmin_{i \text{ with requests in } \mathcal{W}} c_i\); \(r \leftarrow\) oldest request of \(k\)
- if \(r\) does not fit in memory then break
- move \(r\) to \(R\); \(c_k \leftarrow c_k + w_p \cdot \text{input\_len}(r)\)
- 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.
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:
- 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.
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.
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
| Setting | Typical policy | Why |
|---|---|---|
| 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 SLO | SLO-aware admission (cap the batch, formula 136.11), priority to interactive traffic, aging | Goodput, 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 weights | A 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 work | No user is waiting; length grouping reduces wasted slots (Zheng et al., Fu et al.) |
| Video-RAG and video question answering | Separate long-prompt requests (thousands of visual tokens) by skip-join-like priority or a separate prefill pool | A video request’s prefill is long; without care it blocks short chat turns (session 137) |
| Live key-moment detection and alerts on a video stream | Strict priority plus deadlines (EDF) for alert requests; captions and summaries as background work | An alert that arrives late is worthless; a summary can wait |
| Video retrieval, classification and fingerprinting with an LLM or VLM re-ranker | Short, fixed-length outputs, so FCFS with batching is fine; fairness across indexing jobs | Lengths 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
Why does SJF minimize the mean completion time?core
You do not know output lengths. How can you still get most of the benefit of SJF?core
What is skip-join in FastServe, and what problem does it solve?advanced
A request is preempted. What happens to its KV cache? Compare the options.core
Why are request-per-minute limits a poor way to get fairness?basic
Explain the Virtual Token Counter and why it needs a counter lift.core
What fairness guarantee does VTC give, and what do the terms mean?advanced
Your service has a 50 ms TPOT SLO and you see violations at high load. What do you do?core
Why can earliest-deadline-first scheduling fail under overload, and how do you fix it?advanced
Design the scheduler for an API with free and paid tiers, chat and batch traffic.advanced
Exercises
- 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.
- 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?
- 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?
- 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?
- 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.
- In Figure 2, turn skip-join off. Explain in two sentences why the mean JCT gets worse than FCFS.
Answerscheck
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
References for this session
- Wu et al. (2023). Fast Distributed Inference Serving for Large Language Models (FastServe)
- Sheng et al. (2024). Fairness in Serving Large Language Models (VTC)
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Wu et al. (2023). Fast Distributed Inference Serving for Large Language Models (FastServe)
- Sheng et al. (2024). Fairness in Serving Large Language Models (VTC)
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Agrawal et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
- Fu, Zhu, Su, Qiao, Stoica, Zhang (2024). Efficient LLM Scheduling by Learning to Rank
- Zheng, Ren, Xue, Luo, Jiang, You (2023). Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
- Jin, Wu, Brooks, Wei (2023). S3: Increasing GPU Utilization during Generative Inference for Higher Throughput
- Liu, Chung, Wu, Lai, Lee, Chowdhury (2024). Andes: Defining and Enhancing Quality-of-Experience in LLM-Based Text Streaming Services