Batching and Scheduling

A model server rarely has one user. A coding agent, a chat window, and a batch job may all send requests at the same moment. The server has one model loaded in memory, so it needs a rule for sharing it. This lesson is about that rule: which requests run in each pass through the model, who waits, and what happens when the server is full.

The sharing matters because it decides two numbers that users feel. The first is throughput, the total number of tokens the server produces per second. The second is latency, how long one user waits for the first token and between later tokens. A good sharing rule raises the first number without ruining the second.

After this lesson, you can compute why a single request leaves a GPU almost idle, simulate static and continuous batching, explain why a long prompt slows other users and how chunked prefill limits that, compare scheduling policies, size a queue with Little's law, explain preemption, and read the scheduling loop of llama-server and vLLM.

Here are the ideas in order. Each one is defined again where it first appears.

Some vocabulary from earlier lessons is needed. Prefill is the phase where the model reads the whole prompt at once. Decode is the phase where it produces the answer one token at a time. The KV cache (key-value cache) is the memory where the model keeps the intermediate results for every token it has already seen, so it does not recompute them. All three are explained in Generation, Prefill, Decode, and the KV Cache. The roofline model says that a step is limited either by how fast the GPU can do arithmetic or by how fast it can read memory, whichever is slower (FLOPs, Bandwidth, and the Roofline Model). A slot in llama-server is one place where it can hold one conversation (llama-server: Endpoints, Slots, and Prompt Cache). The vLLM flags used here are explained in Serving with vLLM.

The simulations in this lesson count steps, tokens, and blocks. They never measure wall-clock time, so the output is the same on every run. Where a time is needed, a step costs "units" from a roofline model: streaming the model weights from memory costs a fixed amount per step, and arithmetic cost grows with the number of tokens in the step. vLLM facts come from the 0.30.0 source (vllm/v1/core/sched/), and llama-server facts come from tools/server/server-context.cpp at commit 0c1e57098.

Example 1: utilization of a single decoding request

The problem. A GPU can do a huge amount of arithmetic per second. When a server handles one request, it does not use that capacity. This example shows by how much.

The idea. To produce one token, the GPU must read every weight of the model from memory once. For an 8B model compressed to 4.5 bits per weight, that is about 4.5 GB of reading for a token that needs very little arithmetic. The GPU spends most of the step waiting for memory. If a second request is decoding at the same time, the same weights can serve both: the GPU reads them once and does the arithmetic for two tokens. This is the reason batching exists. The earlier roofline lesson showed this (FLOPs, Bandwidth, and the Roofline Model, Example 10), but it ignored the KV cache. Each sequence also reads its own KV cache in every step, and that cache is not shared between sequences, so batching cannot amortize it.

The program computes the step time on an RTX 4090 (NVIDIA's published 165.2 TFLOP/s for FP16 tensor operations and 1,008 GB/s of memory bandwidth). The model has 8 billion parameters at 4.5 bits per weight. Every sequence holds a 4,096-token context, which costs 128 KiB of KV cache per token in F16 (16-bit floating point). The program reports FLOP utilization: the share of the GPU's peak arithmetic rate that the step actually uses. A step takes the larger of two times: the time to read the bytes, and the time to do the arithmetic. Look at how the utilization column changes as the batch grows.

import java.util.Locale;

public class DecodeUtilization {
    public static void main(String[] args) {
        double params = 8.03e9, weightBytes = params * 4.5 / 8;     // 8B model, 4.5 bits per weight
        double peak = 165.2e12, bw = 1008e9;                          // RTX 4090: FP16 tensor FLOP/s, bytes/s
        double kvPerSeq = 4096 * 131072.0;                            // 4096-token context, 128 KiB per token
        double vram = 24e9;
        System.out.println("batch  bytes/step GB  step ms  tok/s total  tok/s per seq  FLOP utilization");
        for (int b : new int[] {1, 8, 16, 32}) {
            double bytes = weightBytes + b * kvPerSeq;               // weights once, every sequence's KV
            double flops = 2 * params * b;
            double step = Math.max(bytes / bw, flops / peak);
            System.out.printf(Locale.ROOT, "%5d  %13.2f  %7.2f  %11.0f  %13.1f  %15.2f%%%n",
                    b, bytes / 1e9, step * 1000, b / step, 1 / step, 100 * flops / step / peak);
        }
        System.out.printf(Locale.ROOT, "sequences of 4096 tokens that fit next to the weights: %.0f%n",
                Math.floor((vram - weightBytes) / kvPerSeq));
    }
}

batch  bytes/step GB  step ms  tok/s total  tok/s per seq  FLOP utilization
    1           5.05     5.01          199          199.5             1.94%
    8           8.81     8.74          915          114.4             8.90%
   16          13.11    13.00         1231           76.9            11.96%
   32          21.70    21.52         1487           46.5            14.45%
sequences of 4096 tokens that fit next to the weights: 36

Read the first row. With one sequence, a step moves 5.05 GB: 4.52 GB of weights plus 0.54 GB of KV cache. At 1,008 GB/s that takes 5.01 ms, so the request receives 199.5 tokens per second. In that time the tensor cores do 16 GFLOP, which is 1.94% of what they could do. The other 98% of the compute capacity is idle because the step waits for memory.

Now the row for 8 sequences. The weights are still read once, but 8 caches are read, so a step moves 8.81 GB. Total throughput rises to 915 tokens per second, which is 4.6 times the single-request rate. Each individual sequence gets slower, from 199.5 to 114.4 tokens per second, because each step now takes longer. This is the basic trade of batching: the server as a whole gets much more done, and each user waits a little longer per token.

At 32 sequences the caches dominate the traffic (17.18 of 21.70 GB). Total throughput reaches 1,487 tokens per second, and utilization is still only 14.45%. The step is still memory bound, but now the reason is the KV cache and not the weights.

The last line is the capacity limit. After 4.52 GB of weights, the 24 GB card holds 36 caches of 4,096 tokens (the program ignores activation buffers, the temporary memory the model uses during a pass). Two facts follow for a server. Batching is how a server turns idle compute into throughput, and the KV cache is what limits the batch, both in memory and in bandwidth. The rest of this lesson is about filling the batch well. The next lesson, Paged KV Cache and Prefix Caching, is about fitting more sequences into the same memory.

Example 2: static batching: padding and waiting for the longest request

The problem. Batching needs a rule for when a group of requests starts and ends. The simplest rule is to collect a group, run it, and collect the next one.

The idea. Static batching forms a group of requests, runs steps until every request in the group is finished, then forms the next group. The weakness is that requests in a group generate different numbers of tokens. A request that needs 3 tokens finishes early, but its place in the batch stays reserved until the longest request in the group is done. Think of a minibus that cannot leave the stop until the last passenger boards and cannot open its doors until the last passenger's stop. The analogy matches the waiting, but a bus does not waste fuel on empty seats the way a batch wastes GPU work on empty places.

The program runs 8 requests that generate 12, 3, 7, 20, 5, 9, 4, and 15 tokens, in groups of 4. It counts slot-steps. One slot-step is one place in the batch for one step, whether that place produces a useful token or not. The ratio of useful slot-steps to all slot-steps tells you how much of the batch did real work. The program also records the step at which each request's result returns.

import java.util.Arrays;

public class StaticBatching {
    public static void main(String[] args) {
        int[] outputLen = {12, 3, 7, 20, 5, 9, 4, 15};             // tokens each request generates
        int batch = 4, step = 0, used = 0, slotSteps = 0;
        int[] done = new int[outputLen.length];
        for (int start = 0; start < outputLen.length; start += batch) {
            int longest = 0;
            for (int i = start; i < start + batch; i++) longest = Math.max(longest, outputLen[i]);
            for (int i = start; i < start + batch; i++) {
                used += outputLen[i];
                done[i] = step + longest;                            // results return when the batch ends
            }
            System.out.printf("batch %s runs %d steps, %d of %d slot-steps used%n",
                    Arrays.toString(Arrays.copyOfRange(outputLen, start, start + batch)), longest,
                    Arrays.stream(outputLen, start, start + batch).sum(), longest * batch);
            step += longest;
            slotSteps += longest * batch;
        }
        System.out.println("total steps " + step + ", useful tokens " + used + " of " + slotSteps
                + " slot-steps (" + 100 * used / slotSteps + "%)");
        System.out.println("finish step per request: " + Arrays.toString(done)
                + ", mean " + Arrays.stream(done).average().getAsDouble());
    }
}

batch [12, 3, 7, 20] runs 20 steps, 42 of 80 slot-steps used
batch [5, 9, 4, 15] runs 15 steps, 33 of 60 slot-steps used
total steps 35, useful tokens 75 of 140 slot-steps (53%)
finish step per request: [20, 20, 20, 20, 35, 35, 35, 35], mean 27.5

The first group runs 20 steps because its longest request generates 20 tokens. The request with 3 tokens finishes after step 3, and its place stays empty for the remaining 17 steps. This empty work is called padding. The group uses only 42 of its 80 slot-steps (4 places times 20 steps). The second group runs 15 steps and uses 33 of its 60.

Over both groups, 75 useful tokens take 140 slot-steps, so 53% of the batch capacity does useful work. Latency suffers as much as throughput. In this program the group's results return together, so the request with 3 tokens returns at step 20, not step 3. Requests 4 to 7 cannot even start before step 20, although slots were free from step 3 on. The mean finish step is 27.5.

Static batching matches how offline jobs run over a fixed dataset, where all inputs exist at the start and only the total time matters. For a server where requests arrive at different times and generate different lengths, the waste grows with the spread of output lengths.

Example 3: continuous batching: steps and throughput compared

The problem. In Example 2, a finished request left an empty place that nobody could use. The next example shows how the server fills that place right away.

The idea. Continuous batching makes the scheduling decision at every step instead of once per group. A request that finishes leaves the batch at once, and a waiting request takes its place before the next step. The technique is also called iteration-level scheduling, and the Orca paper (Yu et al., 2022) describes it. A step is cheap to reorganize because the model processes each token position independently of the other requests in the batch, so a new request can join at any step. The program runs the same 8 requests with 4 slots and prints the steps at which a waiting request joins. In each printed line, r0 to r7 are the requests, and a dash is an empty slot.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class ContinuousBatching {
    public static void main(String[] args) {
        int[] outputLen = {12, 3, 7, 20, 5, 9, 4, 15};
        int capacity = 4;
        int[] remaining = outputLen.clone(), done = new int[outputLen.length];
        Deque<Integer> waiting = new ArrayDeque<>();
        for (int i = 0; i < outputLen.length; i++) waiting.add(i);
        int[] slot = new int[capacity];
        Arrays.fill(slot, -1);
        int step = 0;
        while (!waiting.isEmpty() || Arrays.stream(slot).anyMatch(s -> s >= 0)) {
            boolean joined = false;
            for (int s = 0; s < capacity; s++)                       // fill free slots before the step
                if (slot[s] < 0 && !waiting.isEmpty()) { slot[s] = waiting.poll(); joined = true; }
            step++;
            StringBuilder line = new StringBuilder(String.format("step %2d:", step));
            for (int s = 0; s < capacity; s++) line.append(slot[s] < 0 ? "  -" : " r" + slot[s]);
            if (joined) System.out.println(line + "   <- a waiting request joined");
            for (int s = 0; s < capacity; s++)                       // every running request gains one token
                if (slot[s] >= 0 && --remaining[slot[s]] == 0) { done[slot[s]] = step; slot[s] = -1; }
        }
        int tokens = Arrays.stream(outputLen).sum();
        System.out.println("total steps " + step + ", useful tokens " + tokens + " of " + step * capacity
                + " slot-steps (" + 100 * tokens / (step * capacity) + "%)");
        System.out.println("finish step per request: " + Arrays.toString(done)
                + ", mean " + Arrays.stream(done).average().getAsDouble());
    }
}

step  1: r0 r1 r2 r3   <- a waiting request joined
step  4: r0 r4 r2 r3   <- a waiting request joined
step  8: r0 r4 r5 r3   <- a waiting request joined
step  9: r0 r6 r5 r3   <- a waiting request joined
step 13: r7  - r5 r3   <- a waiting request joined
total steps 27, useful tokens 75 of 108 slot-steps (69%)
finish step per request: [12, 3, 7, 20, 8, 16, 12, 27], mean 13.125

Follow the first lines. Request r1 generates 3 tokens and finishes in step 3, so at step 4, r4 takes its slot. Request r2 (7 tokens) finishes in step 7, and r5 joins at step 8. Request r4 (5 tokens, started at step 4) finishes in step 8, and r6 joins at step 9. Request r0 (12 tokens) finishes in step 12, and the last request, r7, joins at step 13. From then on no request waits, and slots empty out as the last requests finish.

The totals compare directly with Example 2:

The useful tokens are the same 75 in both cases. Continuous batching finishes the workload in 23% fewer steps and halves the mean finish step, because no slot waits for an unrelated request. The remaining 31% of empty slot-steps come from the tail: after step 20, only r7 is left running. With a steady stream of arrivals, the tail disappears and slots stay full.

Both engines in this course batch continuously. llama-server enables it by default (-cb, --cont-batching, "default: enabled" in common/arg.cpp; -nocb turns it off). vLLM's scheduler has no other mode.

Example 4: prefill-decode interference: a long prompt stalls the decodes

The problem. A step can contain tokens from two kinds of work. Requests that are generating contribute one token each. A request that has just arrived contributes its whole prompt, which can be thousands of tokens. This example shows what happens to the generating requests when a big prompt joins their step.

The idea. A step's cost depends on its total token count. A step with only a few tokens is limited by memory: it takes the same time to read the weights whether it carries 4 tokens or 400. A step with thousands of tokens is limited by arithmetic and takes longer. So when a long prompt shares a step with decoding requests, the step becomes long, and every decoding request waits for it.

The program uses a simple cost model. A step costs 10 units to stream the weights, or 1 unit per 50 tokens of compute, whichever is larger. This means steps with up to 500 tokens cost 10 units (500 divided by 50 is 10). Four requests are decoding when a 4,000-token prompt arrives before step 4, and the whole prompt is processed in that step. Watch the "gap" column, which is the time between two consecutive tokens for the decoding users.

import java.util.Locale;

public class PrefillInterference {
    // time units per step: 10 to stream the weights, or 1 per 50 tokens of compute, whichever is larger
    static double stepCost(int tokens) { return Math.max(10, tokens / 50.0); }

    public static void main(String[] args) {
        int decoders = 4, longPrompt = 4000;
        double clock = 0, prev = 0, worstGap = 0;
        for (int step = 1; step <= 7; step++) {
            int tokens = decoders + (step == 4 ? longPrompt : 0);    // the long prompt arrives before step 4
            clock += stepCost(tokens);
            worstGap = Math.max(worstGap, clock - prev);
            System.out.printf(Locale.ROOT, "step %d: %4d tokens, cost %5.2f, decoders get a token at t=%6.2f (gap %5.2f)%s%n",
                    step, tokens, stepCost(tokens), clock, clock - prev, step == 4 ? "  <- whole prompt in one step" : "");
            prev = clock;
        }
        System.out.printf(Locale.ROOT, "long request: first token after %.2f units; worst gap for the decoders %.2f units%n",
                stepCost(decoders + longPrompt), worstGap);
    }
}

step 1:    4 tokens, cost 10.00, decoders get a token at t= 10.00 (gap 10.00)
step 2:    4 tokens, cost 10.00, decoders get a token at t= 20.00 (gap 10.00)
step 3:    4 tokens, cost 10.00, decoders get a token at t= 30.00 (gap 10.00)
step 4: 4004 tokens, cost 80.08, decoders get a token at t=110.08 (gap 80.08)  <- whole prompt in one step
step 5:    4 tokens, cost 10.00, decoders get a token at t=120.08 (gap 10.00)
step 6:    4 tokens, cost 10.00, decoders get a token at t=130.08 (gap 10.00)
step 7:    4 tokens, cost 10.00, decoders get a token at t=140.08 (gap 10.00)
long request: first token after 80.08 units; worst gap for the decoders 80.08 units

Steps 1 to 3 carry 4 decode tokens each and cost 10 units, so the four users receive a token every 10 units. Step 4 carries 4,004 tokens and costs 4004 / 50 = 80.08 units, because the step is now limited by arithmetic. The four decoding users receive nothing for 80.08 units, which is eight times their normal gap. Then the rhythm returns to 10.

The time between two tokens of one request is the inter-token latency (ITL). A user who is reading a streamed answer sees the pause as a freeze. Every new long prompt causes one such pause for everyone who is already generating. A server that receives a long prompt every few seconds produces a visible stutter for all its users.

The new request gets its first token after 80.08 units. This delay is its time to first token (TTFT), the wait between sending a request and seeing the first token. Processing the whole prompt in one step gives the fastest possible TTFT for that request, and the other users pay for it. The next example trades a little of the new request's TTFT for the others' ITL.

Example 5: chunked prefill with a per-step token budget

The problem. Example 4 showed that one huge step hurts everyone else. The step needs to be smaller.

The idea. Chunked prefill cuts the long prompt into pieces and processes one piece per step. A token budget sets the maximum number of tokens per step. Each step first gives one token slot to every decoding request, then fills the rest of the budget with a chunk of the waiting prompt. The decoding users still get a token in every step, and the long prompt makes steady progress. vLLM's budget is --max-num-batched-tokens. llama-server's budget is the logical batch size -b (default 2048).

The program processes the 4,000-token prompt of Example 4 with budgets from 4,004 (no chunking) down to 256. For each budget it reports how many steps the prompt needs, when the long request receives its first token, and the worst gap for the four decoders. Compare the last two columns as the budget shrinks.

import java.util.Locale;

public class ChunkedPrefill {
    static double stepCost(int tokens) { return Math.max(10, tokens / 50.0); }

    static void run(int budget) {
        int decoders = 4, promptLeft = 4000, steps = 0;
        double clock = 0, worstGap = 0, firstToken = 0;
        while (promptLeft > 0) {
            int chunk = Math.min(promptLeft, budget - decoders);      // decodes first, then a prompt chunk
            double cost = stepCost(decoders + chunk);
            clock += cost;
            worstGap = Math.max(worstGap, cost);
            promptLeft -= chunk;
            steps++;
            if (promptLeft == 0) firstToken = clock;
        }
        System.out.printf(Locale.ROOT, "budget %4d: prompt in %2d steps, long request first token at %6.2f, worst decoder gap %5.2f%n",
                budget, steps, firstToken, worstGap);
    }

    public static void main(String[] args) {
        for (int budget : new int[] {4004, 2048, 512, 256}) run(budget);
    }
}

budget 4004: prompt in  1 steps, long request first token at  80.08, worst decoder gap 80.08
budget 2048: prompt in  2 steps, long request first token at  80.16, worst decoder gap 40.96
budget  512: prompt in  8 steps, long request first token at  81.68, worst decoder gap 10.24
budget  256: prompt in 16 steps, long request first token at 160.00, worst decoder gap 10.00

With a budget of 4,004, the prompt fits in one step. This is the result of Example 4: first token at 80.08 and a worst gap of 80.08.

With a budget of 2,048, the prompt takes 2 steps of about 2,044 tokens. Each step costs 40.96 units, so the decoders' worst gap halves. The long request's first token arrives at 80.16, almost unchanged. The total compute is the same as before. It is spread over two steps instead of one.

With a budget of 512, the prompt takes 8 steps of 508 tokens. Each step carries 512 tokens in total and costs 10.24 units, slightly above the memory-bound floor of 10. The decoders barely notice the prompt. The long request's first token arrives at 81.68 units, only 2% later than without chunking.

With a budget of 256, the prompt takes 16 steps. Each step costs 10 units, because 256 tokens are below the 500-token crossover, so the step is memory bound. The long request waits 160 units, twice as long as before. The reason is that each step now pays the full weight-streaming cost for only 252 prompt tokens, so the prompt needs many more steps.

The budget therefore has a best range. It must be large enough that each step reaches the arithmetic-bound region (here about 500 tokens), and small enough that no step is much longer than a decode step. On real hardware the crossover depends on the model and the GPU, and the roofline lesson shows how to compute it. This is the reason behind the defaults that Serving with vLLM, Example 4, lists: 2,048 tokens on smaller GPUs, and 8,192 or 16,384 on H100 and B200 class GPUs, where a step needs more tokens before arithmetic dominates.

Example 6: scheduling policies: first-come-first-served, priority, shortest-first, starvation

The problem. Sometimes more requests are waiting than the server can start. Someone must go first. The rule that decides is the scheduling policy.

The idea. Three common rules are:

• First-come-first-served (FCFS): the request that arrived first goes first.
• Shortest-first: the request with the least work goes first.
• Priority: each request carries a priority number, and the lowest number goes first (the same convention vLLM uses).

Each rule optimizes something different. FCFS is the fairest in arrival order. Shortest-first minimizes the average waiting time. Priority serves a goal outside the queue, such as serving an interactive user before a batch job.

The program runs six jobs through a server that runs one job at a time, so the policy alone decides the order. Each job has an arrival time, a length, and a priority. The program prints the order and the mean wait (the time from arrival to start). A second part sends one long job followed by a short job every 2 units and runs shortest-first, to show a danger of that rule.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Locale;

public class SchedulingPolicies {
    record Job(String name, int arrival, int length, int priority) {}

    // one server, one job at a time; picks the next job among those that have arrived
    static void run(String policy, List<Job> jobs, Comparator<Job> order) {
        List<Job> pending = new ArrayList<>(jobs);
        int clock = 0;
        double totalWait = 0;
        StringBuilder sequence = new StringBuilder();
        while (!pending.isEmpty()) {
            final int now = clock;
            Job next = pending.stream().filter(j -> j.arrival() <= now).min(order)
                    .orElse(pending.stream().min(Comparator.comparingInt(Job::arrival)).get());
            clock = Math.max(clock, next.arrival());
            totalWait += clock - next.arrival();
            clock += next.length();
            pending.remove(next);
            sequence.append(next.name()).append(' ');
        }
        System.out.printf(Locale.ROOT, "%-15s order %s  mean wait %.2f%n", policy, sequence, totalWait / jobs.size());
    }

    public static void main(String[] args) {
        List<Job> jobs = List.of(new Job("A", 0, 40, 1), new Job("B", 1, 5, 0), new Job("C", 2, 10, 1),
                new Job("D", 3, 2, 1), new Job("E", 4, 20, 0), new Job("F", 5, 3, 1));
        run("fcfs", jobs, Comparator.comparingInt(Job::arrival));
        run("shortest-first", jobs, Comparator.comparingInt(Job::length).thenComparingInt(Job::arrival));
        run("priority", jobs, Comparator.comparingInt(Job::priority).thenComparingInt(Job::arrival));

        List<Job> stream = new ArrayList<>(List.of(new Job("LONG", 0, 30, 1)));
        for (int t = 0; t < 40; t++) stream.add(new Job("s" + t, t * 2, 2, 1));   // a short job every 2 units
        int clock = 0;
        List<Job> pending = new ArrayList<>(stream);
        while (pending.stream().anyMatch(j -> j.name().equals("LONG"))) {
            final int now = clock;
            Job next = pending.stream().filter(j -> j.arrival() <= now)
                    .min(Comparator.comparingInt(Job::length).thenComparingInt(Job::arrival)).get();
            if (next.name().equals("LONG")) System.out.println("shortest-first: LONG starts at " + clock + " after waiting " + clock);
            clock += next.length();
            pending.remove(next);
        }
    }
}

fcfs            order A B C D E F   mean wait 43.17
shortest-first  order A D F B C E   mean wait 37.00
priority        order A B E C D F   mean wait 47.83
shortest-first: LONG starts at 80 after waiting 80

Job A arrives alone at time 0 and starts in every policy, because the server is idle and nothing else has arrived. Jobs B to F all arrive while A runs, so at time 40 the policy chooses among them:

• FCFS runs them by arrival: B, C, D, E, F. Mean wait is 43.17 units.
• Shortest-first runs D (2), F (3), B (5), C (10), E (20). Mean wait drops to 37.00, because short jobs no longer wait behind long ones. When all jobs are waiting at once, shortest-first gives the smallest mean wait of any order.
• Priority runs B and E (priority 0) before C, D, and F (priority 1). Mean wait rises to 47.83, because E, a long job, now delays three others. Priority serves an outside goal, not mean latency.

The last line shows the risk of shortest-first. A 30-unit job arrives at time 0 together with a stream of 2-unit jobs. Every time the server becomes free, a shorter job is waiting, so the long job waits 80 units, until the stream ends. With an endless stream it would never run. This is starvation: a request that the policy never selects. The usual fix is aging: a request's effective priority improves the longer it waits, so eventually it wins.

For an LLM server there is another problem with shortest-first: the length of a request is not known in advance. The prompt length is known, but the output length is not. Engines therefore use FCFS by default. vLLM's --scheduling-policy accepts fcfs (the default) and priority (SchedulerConfig.policy). With priority, a request's priority field orders the waiting queue, and ties are broken by arrival time (PriorityRequestQueue in request_queue.py). The source contains no aging. SGLang, another inference engine, offers more policies, including lpm, which runs requests with the longest cached prefix first (The Engine Landscape and How Ollama Works, Example 7).

Example 7: admission control, queues, and Little's law

The problem. Two questions need an answer: what happens when requests arrive faster than the server can finish them, and how many requests a server must be able to hold at once for a given workload.

The idea. Little's law answers the second question. It says that for a stable system, the average number of requests in the system L equals the arrival rate λ (lambda, requests per unit time) times the average time each request spends in the system W: L = λW. A small case by hand: if 2 requests arrive per second and each stays 5 seconds, then on average 2 x 5 = 10 requests are in the system at any moment. The law holds for any arrival pattern and any scheduling policy, as long as the system is in a steady state, meaning the averages do not drift over time.

The answer to the first question is admission control: when the server is full, it rejects new requests or limits its queue, instead of letting the queue grow forever.

The program simulates a server with 8 slots where each request holds a slot for 20 ticks, so its capacity is 8 / 20 = 0.40 requests per tick. Requests arrive at random (with a fixed seed) with probability p per tick. The program measures L, λ (completed requests per tick), and W at three loads. It then repeats the highest load with a queue limit of 16, beyond which requests are rejected. Check whether L and λW agree in each line.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Locale;
import java.util.Random;

public class AdmissionAndLittle {
    // each tick a request arrives with probability p; 8 slots; a request holds a slot for 20 ticks
    static void run(double p, int queueLimit) {
        Random random = new Random(11);
        int slots = 8, service = 20, ticks = 20_000;
        Deque<Integer> queue = new ArrayDeque<>();              // arrival tick of each waiting request
        int[] left = new int[slots], arrivalOf = new int[slots];   // left == 0 means the slot is free
        long inSystemSum = 0, finished = 0, timeSum = 0, rejected = 0, arrived = 0;
        for (int t = 0; t < ticks; t++) {
            if (random.nextDouble() < p) {
                arrived++;
                if (queueLimit >= 0 && queue.size() >= queueLimit) rejected++;   // answered with HTTP 503
                else queue.add(t);
            }
            int busy = 0;
            for (int s = 0; s < slots; s++) {
                if (left[s] == 0 && !queue.isEmpty()) { arrivalOf[s] = queue.poll(); left[s] = service; }
                if (left[s] > 0) busy++;
            }
            inSystemSum += queue.size() + busy;                    // requests in the system during tick t
            for (int s = 0; s < slots; s++)
                if (left[s] > 0 && --left[s] == 0) { finished++; timeSum += t + 1 - arrivalOf[s]; }
        }
        double lambda = (double) finished / ticks, w = (double) timeSum / finished, l = (double) inSystemSum / ticks;
        System.out.printf(Locale.ROOT, "p=%.2f limit=%4s: L=%7.2f  lambda=%.4f  W=%8.2f  lambda*W=%7.2f  rejected %d of %d%n",
                p, queueLimit < 0 ? "none" : String.valueOf(queueLimit), l, lambda, w, lambda * w, rejected, arrived);
    }

    public static void main(String[] args) {
        System.out.println("capacity: 8 slots / 20 ticks = 0.40 requests per tick");
        run(0.20, -1);
        run(0.36, -1);
        run(0.44, -1);
        run(0.44, 16);
    }
}

capacity: 8 slots / 20 ticks = 0.40 requests per tick
p=0.20 limit=none: L=   3.96  lambda=0.1976  W=   20.06  lambda*W=   3.96  rejected 0 of 3955
p=0.36 limit=none: L=   8.93  lambda=0.3581  W=   24.93  lambda*W=   8.93  rejected 0 of 7172
p=0.44 limit=none: L= 447.50  lambda=0.3996  W= 1019.46  lambda*W= 407.38  rejected 0 of 8831
p=0.44 limit=  16: L=  20.30  lambda=0.3996  W=   50.71  lambda*W=  20.26  rejected 815 of 8831

At p = 0.20 (half of capacity), a request waits almost nothing: W = 20.06 ticks against 20 ticks of service. On average 3.96 requests are in the system, and λW = 0.1976 x 20.06 = 3.96, equal to L as Little's law states.

At p = 0.36 (90% of capacity), W rises to 24.93, because requests sometimes find all slots busy and queue. Again L = 8.93 = λW. Queueing time grows sharply as the load approaches capacity, even though the server is not overloaded on average.

At p = 0.44, arrivals exceed capacity. The server completes 0.3996 requests per tick, which is its maximum, and the rest accumulate. The average finished request spends 1,019 ticks in the system, and the queue grows for the whole run. L (447.50) and λW (407.38) no longer agree, because the system never reaches a steady state, and the requests still queued at the end are not counted in W. Without a limit, waiting time grows without bound.

With a queue limit of 16, the server rejects 815 of 8,831 requests and keeps W at 50.71 ticks. Little's law holds again (20.30 against 20.26), because the bounded queue makes the system stable. Rejecting early lets a client retry on another server or show an error, instead of waiting for an answer that would arrive long after it is useful. The server answers a rejected request with HTTP 503, the status code for "service unavailable".

Little's law also sizes a deployment. A target of 20 requests per second with a mean of 10 seconds per request needs room for 20 x 10 = 200 concurrent requests. In llama-server that room is the number of slots (-np). In vLLM it is --max-num-seqs plus enough KV memory.

vLLM 0.30.0 has two admission limits in SchedulerConfig. Both are enforced in the API server process and answered with HTTP 503:

• --max-num-queued-reqs limits the number of requests that are waiting or running.
• --max-num-queued-tokens limits the prompt tokens in the prefill phase. The source describes it as a TTFT control: target_TTFT * prefill_throughput.

Both default to no limit. llama-server queues requests it cannot place in a slot, also without a limit (llama-server: Endpoints, Slots, and Prompt Cache, Example 8).

Example 8: preemption when KV memory runs out: recompute versus swap

The problem. Every running request adds one token per step, so its KV cache grows. Eventually there is no free memory left, and a running request needs one more block. Something has to give.

The idea. The scheduler takes memory back from some running request. This is preemption. The preempted request stops, loses its place, and must continue later. There are two ways to give its memory back and get the work back afterwards:

• Recompute: drop the KV entries, and run the prompt and the tokens generated so far through prefill again later.
• Swap: copy the KV entries to CPU memory, and copy them back later.

The program models KV memory as 20 blocks of 16 tokens (a block is a fixed-size piece of KV memory, explained fully in the next lesson). Four requests have prompts of 60, 50, 70, and 40 tokens and decode one token per step. When a request needs a new block and none is free, the scheduler preempts the last running request, frees all its blocks, and puts it back in the waiting queue. Its tokens must be recomputed later. The last two lines compare the cost of the two methods for an 8B model with a 2,000-token context.

import java.util.ArrayList;
import java.util.List;

public class PreemptionByRecompute {
    static final int BLOCK = 16;

    static int blocksFor(int tokens) { return (tokens + BLOCK - 1) / BLOCK; }

    public static void main(String[] args) {
        int totalBlocks = 20;
        List<int[]> running = new ArrayList<>();               // {id, tokens}
        List<int[]> waiting = new ArrayList<>();
        int[][] start = {{0, 60}, {1, 50}, {2, 70}, {3, 40}};   // prompt lengths
        for (int[] r : start) running.add(r.clone());
        int recomputed = 0;
        for (int step = 1; step <= 40; step++) {
            for (int i = 0; i < running.size(); i++) {
                int[] r = running.get(i);
                int used = running.stream().mapToInt(x -> blocksFor(x[1])).sum();
                while (blocksFor(r[1] + 1) > blocksFor(r[1]) && used + 1 > totalBlocks) {
                    int[] victim = running.remove(running.size() - 1);  // FCFS: the last running request
                    used -= blocksFor(victim[1]);
                    System.out.println("step " + step + ": no free block for r" + r[0] + ", preempt r" + victim[0]
                            + " (frees " + blocksFor(victim[1]) + " blocks, " + victim[1] + " tokens to recompute)");
                    recomputed += victim[1];
                    waiting.add(0, victim);
                    if (victim == r) break;
                }
                if (running.contains(r)) r[1]++;                      // the request decodes one token
            }
        }
        StringBuilder state = new StringBuilder("after 40 steps: running");
        for (int[] r : running) state.append(" r").append(r[0]).append("=").append(r[1]);
        state.append(", waiting");
        for (int[] r : waiting) state.append(" r").append(r[0]);
        System.out.println(state + ", tokens to recompute " + recomputed);

        double kvBytes = 2000 * 131072.0;                            // 8B shape, 2000-token context
        System.out.printf(java.util.Locale.ROOT, "swap 2000 tokens over PCIe 4.0 x16 (31.5 GB/s), out and back: %.1f ms%n", 2 * kvBytes / 31.5e9 * 1000);
        System.out.printf(java.util.Locale.ROOT, "recompute 2000 tokens at 16 GFLOP/token, 165.2 TFLOP/s at 50%%: %.1f ms%n", 2000 * 16.06e9 / (165.2e12 * 0.5) * 1000);
    }
}

step 21: no free block for r0, preempt r3 (frees 4 blocks, 60 tokens to recompute)
after 40 steps: running r0=100 r1=90 r2=110, waiting r3, tokens to recompute 60
swap 2000 tokens over PCIe 4.0 x16 (31.5 GB/s), out and back: 16.6 ms
recompute 2000 tokens at 16 GFLOP/token, 165.2 TFLOP/s at 50%: 388.9 ms

The four prompts need 4 + 4 + 5 + 3 = 16 blocks (each prompt length divided by 16, rounded up). As the requests grow, each crosses a 16-token boundary and takes another block. At step 21, request r0 reaches 80 tokens and needs its sixth block, but all 20 are in use. The scheduler preempts r3, the last request in the running list. That frees 4 blocks, which held its 60 tokens: a 40-token prompt plus 20 generated tokens. After 40 steps, r0, r1, and r2 hold 7 + 6 + 7 = 20 blocks, and r3 waits with 60 tokens to recompute when memory frees up.

Choosing the last running request as the victim is vLLM's FCFS rule (preempted_req = self.running[-1] in scheduler.py). The newest request has done the least work, and the oldest requests keep their place. With --scheduling-policy priority, vLLM preempts the running request with the largest priority value (the lowest priority), and breaks ties by the latest arrival.

Now compare the two ways to give the memory back, using the last two output lines:

• Recompute costs compute. Running 2,000 tokens through prefill at 16 GFLOP per token on an RTX 4090 at 50% of its peak takes about 388.9 ms.
• Swap costs transfer. 2,000 tokens x 128 KiB = 250 MiB each way, which takes about 16.6 ms in total at the 31.5 GB/s of a PCIe 4.0 x16 link (the connection between the CPU and the GPU).

On these numbers swapping is cheaper per request. It also needs CPU memory, a copy path that does not stall the GPU, and bookkeeping for blocks in two places. vLLM 0.30.0 preempts by recompute only: _preempt_request frees the request's blocks, sets num_computed_tokens = 0, and puts the request at the front of the waiting queue. Recompute is often cheaper than the arithmetic suggests. Freed blocks keep their prefix-cache hashes until they are reused (Paged KV Cache and Prefix Caching), so a preempted request that resumes soon finds most of its blocks still cached.

vLLM counts preemptions in the vllm:num_preemptions metric and adds Preemptions: %d to its periodic log line. A rising count means that the batch is larger than the KV cache can hold. Lowering --max-num-seqs, or giving the cache more memory (Serving with vLLM, Example 3), reduces it.

Example 9: fairness and per-tenant limits

The problem. FCFS is fair to requests, but not to the people who send them. If one client sends 100 requests at once, it fills the queue, and everyone who arrives after it waits for all 100.

The idea. A tenant is a client, team, or customer that shares the server with others. A fair server must consider tenants, not only requests. Two simple tools are:

• Round-robin by tenant: take the next request from each tenant's queue in turn.
• Per-tenant cap: no tenant may hold more than a fixed number of running slots, so some capacity stays free for others.

The program gives a server 4 slots and requests of 10 steps each. Tenant A sends 12 requests at step 0, and tenant B sends 2 at step 1. It compares FCFS, round-robin by tenant, and round-robin with a cap of 3 running requests per tenant. It prints when tenant B's requests finish.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class TenantFairness {
    // 4 slots, every request runs 10 steps; tenant A sends 12 requests at step 0, tenant B sends 2 at step 1
    static void run(String name, boolean roundRobin, int perTenantCap) {
        Map<String, Deque<String>> queues = new LinkedHashMap<>();
        queues.put("A", new ArrayDeque<>());
        queues.put("B", new ArrayDeque<>());
        Deque<String> fifo = new ArrayDeque<>();
        for (int i = 0; i < 12; i++) { queues.get("A").add("A" + i); fifo.add("A" + i); }
        List<String> running = new ArrayList<>();
        List<Integer> endsAt = new ArrayList<>();
        StringBuilder bDone = new StringBuilder();
        String lastTenant = "B";
        for (int step = 0; step < 60; step++) {
            if (step == 1) for (String r : new String[] {"B0", "B1"}) { queues.get("B").add(r); fifo.add(r); }
            for (int i = running.size() - 1; i >= 0; i--)
                if (endsAt.get(i) == step) { if (running.get(i).startsWith("B")) bDone.append(running.get(i)).append("@").append(step).append(' '); running.remove(i); endsAt.remove(i); }
            while (running.size() < 4) {
                String pick = null;
                if (!roundRobin) pick = fifo.poll();
                else for (int k = 0; k < 2 && pick == null; k++) {
                    String tenant = lastTenant.equals("A") ? (k == 0 ? "B" : "A") : (k == 0 ? "A" : "B");
                    long active = running.stream().filter(r -> r.startsWith(tenant)).count();
                    if (!queues.get(tenant).isEmpty() && active < perTenantCap) { pick = queues.get(tenant).poll(); lastTenant = tenant; }
                }
                if (pick == null) break;
                queues.get(pick.substring(0, 1)).remove(pick);
                fifo.remove(pick);
                running.add(pick);
                endsAt.add(step + 10);
            }
        }
        System.out.println(name + ": tenant B finished " + bDone.toString().trim());
    }

    public static void main(String[] args) {
        run("fcfs                    ", false, 4);
        run("round-robin by tenant   ", true, 4);
        run("round-robin, cap 3/tenant", true, 3);
    }
}

fcfs                    : tenant B finished B1@40 B0@40
round-robin by tenant   : tenant B finished B1@20 B0@20
round-robin, cap 3/tenant: tenant B finished B0@11 B1@20

With FCFS, tenant B's two requests sit behind all 12 of A's. A's requests run in three waves (steps 0 to 10, 10 to 20, and 20 to 30), and B's requests finish at step 40.

With round-robin, the queue of each tenant is served in turn. At step 0 only A has requests, so A takes all 4 slots. At step 10 the slots free up, and the scheduler alternates: B0, then A4, then B1, then A5. B's requests finish at step 20.

With the cap, A can hold at most 3 slots, so one slot stays free at step 0. B0 arrives at step 1 and starts at once, and it finishes at step 11. B1 starts at step 10, when the next slot frees, and finishes at step 20. The cost is that a slot stayed idle during step 0, when only A had work.

The three results show the trade-off. A cap protects small tenants from waiting at all, at the price of unused capacity when only one tenant is active. Round-robin uses all the capacity, but small tenants still wait for the current requests to finish.

The vLLM 0.30.0 SchedulerConfig and llama-server have no tenant concept. vLLM offers a per-request priority (with --scheduling-policy priority) and global queue limits (Example 7). llama-server offers a fixed number of slots, and id_slot to pin a request to one slot. Per-tenant quotas, rate limits, and fair queuing are applied in front of the engine, in the gateway or router that receives requests, using the same rules as this program.

Example 10: disaggregated prefill and decode: pools and KV transfer arithmetic

The problem. Chunked prefill (Example 5) lets prefill and decode share one GPU, but they still compete for it. They also want different things: prefill is limited by arithmetic, and decode is limited by memory bandwidth. A GPU configured for one is not ideal for the other.

The idea. Disaggregated serving separates the two phases onto different machines. A prefill pool of GPUs processes prompts. A decode pool generates tokens. The KV cache of each prompt is sent from the first pool to the second. Each pool can then be sized and tuned for its own phase, and prefill no longer interrupts decoding. The price is the transfer: the KV cache can be large, and it must cross a network or an interconnect before decoding starts.

The program computes the KV size of an 8B model's prompts, the prefill compute time on an H100 GPU at half of NVIDIA's 989 TFLOP/s BF16 figure (BF16 is a 16-bit number format), and the transfer time over three links at their nominal rates. Compare the transfer times with the prefill time for each prompt length.

import java.util.Locale;

public class DisaggregatedKvTransfer {
    public static void main(String[] args) {
        double kvPerToken = 131072;                                  // 8B shape, F16 cache
        double flopsPerToken = 2 * 8.03e9;
        double prefillFlops = 989e12 * 0.5;                          // H100 BF16 dense peak at 50%
        String[] links = {"NVLink, H100 (450 GB/s per direction)", "InfiniBand NDR 400 Gb/s (50 GB/s)", "Ethernet 100 Gb/s (12.5 GB/s)"};
        double[] gbs = {450, 50, 12.5};
        for (int prompt : new int[] {1024, 8192, 32768}) {
            double bytes = prompt * kvPerToken;
            double prefillMs = prompt * flopsPerToken / prefillFlops * 1000;
            System.out.printf(Locale.ROOT, "prompt %5d: KV %7.0f MiB, prefill compute %7.1f ms%n", prompt, bytes / (1 << 20), prefillMs);
            for (int i = 0; i < links.length; i++)
                System.out.printf(Locale.ROOT, "    %-40s %8.2f ms%n", links[i], bytes / (gbs[i] * 1e9) * 1000);
        }
    }
}

prompt  1024: KV     128 MiB, prefill compute    33.3 ms
    NVLink, H100 (450 GB/s per direction)        0.30 ms
    InfiniBand NDR 400 Gb/s (50 GB/s)            2.68 ms
    Ethernet 100 Gb/s (12.5 GB/s)               10.74 ms
prompt  8192: KV    1024 MiB, prefill compute   266.1 ms
    NVLink, H100 (450 GB/s per direction)        2.39 ms
    InfiniBand NDR 400 Gb/s (50 GB/s)           21.47 ms
    Ethernet 100 Gb/s (12.5 GB/s)               85.90 ms
prompt 32768: KV    4096 MiB, prefill compute  1064.2 ms
    NVLink, H100 (450 GB/s per direction)        9.54 ms
    InfiniBand NDR 400 Gb/s (50 GB/s)           85.90 ms
    Ethernet 100 Gb/s (12.5 GB/s)              343.60 ms

A 1,024-token prompt has 128 MiB of KV cache and takes about 33.3 ms of prefill compute. Over NVLink between GPUs in one server, the transfer takes 0.30 ms, which is 1% of the prefill time. Over 400 Gb/s InfiniBand between servers it takes 2.68 ms (8%). Over 100 Gb/s Ethernet it takes 10.74 ms, a third of the prefill time.

The KV size and the prefill time both grow linearly with the prompt length in this model. (The program counts only the arithmetic for the weights. Attention arithmetic makes long prefills slower still, see Attention Optimizations and Long Context, Example 16.) The ratio of transfer time to prefill time therefore stays about the same for each link: NVLink adds about 1%, InfiniBand about 8%, and 100 Gb/s Ethernet about 32%. At 32,768 tokens, 4 GiB must move, and the Ethernet transfer takes 343.60 ms.

The transfer adds to TTFT. Disaggregation therefore pays off when the network is fast compared with the prefill, and when decode latency matters enough that removing prefill interference is worth the extra hardware and the transfer. Models with smaller KV caches make the transfer cheaper: GQA (grouped-query attention) with few KV heads, and MLA (multi-head latent attention) from the previous lesson. A quantized KV cache halves the transfer again.

vLLM implements the transfer with KV connectors, configured with --kv-transfer-config (a JSON object, KVTransferConfig in vllm/config/kv_transfer.py). Its kv_connector field names a connector registered in kv_connector/factory.py, among them NixlConnector, LMCacheConnectorV1, MooncakeConnector, OffloadingConnector, and MultiConnector. Its kv_role field is kv_producer, kv_consumer, or kv_both, which tells an instance whether it sends KV, receives it, or does both. llama.cpp has no disaggregated mode at the pinned commit.

Example 11: llama-server slots versus the vLLM scheduler

The problem. The earlier examples were simulations. This example checks a real server. The check is whether llama-server really mixes decode tokens and prompt chunks in one step, as chunked prefill describes.

The idea. llama-server's main loop is update_slots in tools/server/server-context.cpp. It builds one batch per step in two phases. First, every generating slot adds its last sampled token (handle_last_sampled_token). Then, under the comment "next, batch any pending prompts without exceeding n_batch", slots that are processing a prompt add prompt tokens until the batch holds n_batch tokens. This is chunked prefill with -b as the budget.

The real run below uses llama-server with a tiny model that has random weights, so the token texts mean nothing, but the batching behavior is real. The server has 2 slots and -b 256 -ub 256 (-ub is the physical micro-batch size, the largest group of tokens actually sent to the model at once). A request that generates 200 tokens runs on slot 0, and a 2,450-token prompt is sent to slot 1 while slot 0 is decoding.

llama-server -m tiny-random-qwen2vocab-f32.gguf -np 2 -c 8192 -b 256 -ub 256 --port 18431 -v

Selected lines from the log (timestamps and timing fields removed; the run was on a shared, loaded CPU):

I slot   operator(): id  1 | task 2 | new prompt, n_ctx_slot = 4096, n_keep = 0, task.n_tokens = 2450
D slot process_toke: id  0 | task 0 | n_gen = 2, n_remaining = 198, next token: 112360 '之城'
I slot print_timing: id  1 | task 2 | prompt processing, n_tokens =    255, progress = 0.10
D slot process_toke: id  0 | task 0 | n_gen = 3, n_remaining = 197, next token:  6787 ' skin'
I slot print_timing: id  1 | task 2 | prompt processing, n_tokens =    510, progress = 0.21
...
I slot print_timing: id  1 | task 2 | prompt processing, n_tokens =   2295, progress = 0.94
D slot process_toke: id  0 | task 0 | n_gen = 11, n_remaining = 189, next token: 136258 'ทิ้ง'
D slot process_toke: id  1 | task 2 | n_gen = 1, n_remaining = 4, next token: 57497 ' Ib'

Look at the lines in order. Slot 1 receives the prompt of 2,450 tokens. After that, the log alternates: slot 0 produces a token (n_gen goes up by one), then slot 1 reports more prompt progress (255, then 510, and so on). The two slots take turns in the log because each step contains one token for slot 0 and one chunk for slot 1.

The program below reads the same sequence of events from the log (reduced to the fields it needs) and reconstructs the composition of each batch.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class SlotLogSteps {
    public static void main(String[] args) {
        String log = """
            slot 0 n_gen = 2
            slot 1 prompt processing, n_tokens = 255
            slot 0 n_gen = 3
            slot 1 prompt processing, n_tokens = 510
            slot 0 n_gen = 4
            slot 1 prompt processing, n_tokens = 765
            slot 0 n_gen = 5
            slot 1 prompt processing, n_tokens = 1020
            slot 0 n_gen = 6
            slot 1 prompt processing, n_tokens = 1275
            slot 0 n_gen = 7
            slot 1 prompt processing, n_tokens = 1530
            slot 0 n_gen = 8
            slot 1 prompt processing, n_tokens = 1785
            slot 0 n_gen = 9
            slot 1 prompt processing, n_tokens = 2040
            slot 0 n_gen = 10
            slot 1 prompt processing, n_tokens = 2295
            slot 0 n_gen = 11
            slot 1 n_gen = 1
            """;
        int promptTotal = 2450, nBatch = 256, prev = 0, step = 0;
        Matcher m = Pattern.compile("slot (\\d) (n_gen = (\\d+)|prompt processing, n_tokens = (\\d+))").matcher(log);
        while (m.find()) {
            if (m.group(1).equals("0")) {                             // one decode step finished for slot 0
                step++;
                continue;
            }
            int done = m.group(4) != null ? Integer.parseInt(m.group(4)) : promptTotal;
            int chunk = done - prev;
            prev = done;
            System.out.printf("step %2d: slot 0 decodes 1 token, slot 1 prompt chunk %3d -> batch %3d of n_batch %d (prompt %4d/%d)%n",
                    step, chunk, chunk + 1, nBatch, done, promptTotal);
        }
    }
}

step  1: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt  255/2450)
step  2: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt  510/2450)
step  3: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt  765/2450)
step  4: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt 1020/2450)
step  5: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt 1275/2450)
step  6: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt 1530/2450)
step  7: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt 1785/2450)
step  8: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt 2040/2450)
step  9: slot 0 decodes 1 token, slot 1 prompt chunk 255 -> batch 256 of n_batch 256 (prompt 2295/2450)
step 10: slot 0 decodes 1 token, slot 1 prompt chunk 155 -> batch 156 of n_batch 256 (prompt 2450/2450)

Each of the first nine steps holds exactly 256 tokens: 1 decode token for slot 0 and a 255-token prompt chunk for slot 1. The tenth step holds the last 155 prompt tokens plus slot 0's token. In that same step slot 1's prompt completes, and it samples its first token (n_gen = 1). Slot 0 received one token in every one of the ten steps. It was never paused for a whole 2,450-token prefill. The token texts are meaningless because the model has random weights.

Both engines follow the same principle: decode tokens first, then prompt chunks up to a budget. They differ in how memory is managed and what happens when it runs out. Start with the big picture: llama-server gives each slot its own region, so it cannot pick a victim, while vLLM tracks every block and can. The table gives the details.

The difference in the "runs out" row follows from the memory row. A slot's cells are its own (or, with a unified cache, taken in order), so llama-server has no block-level accounting to decide which request to evict. vLLM tracks every block, so it can free one request's blocks exactly. The next lesson builds that block accounting.

Example 12: a guided read of the vLLM scheduler's main loop

The problem. The ideas so far (budget, chunking, running first, preemption) are separate. In a real engine they are one loop. Reading that loop shows how they fit together.

The idea. Scheduler.schedule() in vllm/v1/core/sched/scheduler.py (line 561 in 0.30.0) runs once per step. A comment at the top of the method states the design: "There's no 'decoding phase' nor 'prefill phase' in the scheduler" (the source puts the two phase names in double quotes). Instead, each request has a count of computed tokens (num_computed_tokens) and a total (num_tokens_with_spec). Every step, the scheduler gives each request enough tokens to bring num_computed_tokens closer to its total, within the token budget. A prompt of 10 tokens starts with 0 computed out of 10. A decoding request that has 13 known tokens and has computed 12 needs 1 more token. Both cases are the same rule.

The program is a reduced copy of that loop with small numbers. The budget is 8 tokens per step (max_num_batched_tokens), at most 3 requests run at once (max_num_seqs), and there are 7 KV blocks of 4 tokens. Three requests arrive: A (10-token prompt, 4 output tokens), B (6 and 6), and C (5 and 3). In each output line, A+8 means that request A receives 8 tokens in that step. The line also shows the free blocks after scheduling, any preemption, and any request that finished.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class MiniVllmScheduler {
    static final int BLOCK = 4;
    static int freeBlocks = 7;
    static final Map<Req, Integer> held = new HashMap<>();

    static class Req {
        final String id; final int prompt, maxTokens; int computed, output;
        Req(String id, int prompt, int maxTokens) { this.id = id; this.prompt = prompt; this.maxTokens = maxTokens; }
        int numTokens() { return prompt + output; }
    }

    static boolean allocate(Req r, int newTokens) {                  // kv_cache_manager.allocate_slots
        int need = (r.computed + newTokens + BLOCK - 1) / BLOCK - held.getOrDefault(r, 0);
        if (need > freeBlocks) return false;
        freeBlocks -= need;
        held.merge(r, need, Integer::sum);
        return true;
    }

    static void free(Req r) { Integer n = held.remove(r); if (n != null) freeBlocks += n; }

    public static void main(String[] args) {
        int maxNumBatchedTokens = 8, maxNumSeqs = 3;
        Deque<Req> waiting = new ArrayDeque<>(List.of(new Req("A", 10, 4), new Req("B", 6, 6), new Req("C", 5, 3)));
        List<Req> running = new ArrayList<>();
        for (int step = 1; !(waiting.isEmpty() && running.isEmpty()); step++) {
            int budget = maxNumBatchedTokens;
            Map<Req, Integer> scheduled = new LinkedHashMap<>();
            List<String> preempted = new ArrayList<>();
            for (int i = 0; i < running.size() && budget > 0; i++) {     // 1. RUNNING requests first
                Req r = running.get(i);
                int n = Math.min(r.numTokens() - r.computed, budget);
                boolean ok;
                while (!(ok = allocate(r, n))) {                       // no blocks: preempt the last running
                    Req victim = running.remove(running.size() - 1);
                    free(victim);
                    victim.computed = 0;                               // recompute later
                    waiting.addFirst(victim);
                    preempted.add(victim.id);
                    if (victim == r) break;
                }
                if (!ok) break;
                scheduled.put(r, n);
                budget -= n;
            }
            while (preempted.isEmpty() && !waiting.isEmpty() && budget > 0 && running.size() < maxNumSeqs) {
                Req r = waiting.peekFirst();                           // 2. WAITING requests, chunked
                int n = Math.min(r.numTokens() - r.computed, budget);
                if (!allocate(r, n)) break;
                running.add(waiting.pollFirst());
                scheduled.put(r, n);
                budget -= n;
            }
            StringBuilder line = new StringBuilder(String.format("step %2d:", step));
            scheduled.forEach((r, n) -> line.append(" ").append(r.id).append("+").append(n));
            line.append(String.format("  free blocks after scheduling %d", freeBlocks));
            if (!preempted.isEmpty()) line.append("  preempted ").append(preempted);
            for (Map.Entry<Req, Integer> e : scheduled.entrySet()) {   // 3. the model runs, then outputs update
                Req r = e.getKey();
                r.computed += e.getValue();
                if (r.computed == r.numTokens()) r.output++;           // all known tokens done: sample one
                if (r.output == r.maxTokens) { running.remove(r); free(r); line.append("  ").append(r.id).append(" finished"); }
            }
            System.out.println(line);
        }
    }
}

step  1: A+8  free blocks after scheduling 5
step  2: A+2 B+6  free blocks after scheduling 2
step  3: A+1 B+1 C+5  free blocks after scheduling 0
step  4: A+1 B+1 C+1  free blocks after scheduling 0
step  5: A+1 B+1  free blocks after scheduling 0  preempted [C]  A finished
step  6: B+1 C+7  free blocks after scheduling 2  C finished
step  7: B+1  free blocks after scheduling 4  B finished

The program follows the source in three phases, and each output line shows one step as request+tokens:

1. Running requests first. For each running request, the number of new tokens is num_tokens - num_computed_tokens, capped by the budget (long_prefill_token_threshold can cap it further; it defaults to 0, which means no cap). allocate_slots reserves blocks. If it fails, the scheduler preempts self.running[-1] and tries again. If the victim is the request itself, scheduling of running requests stops.
2. Waiting requests next, only if nothing was preempted in this step (if not preempted_reqs in the source). Each is admitted while the budget lasts and the running count is below max_num_seqs. With chunked prefill enabled (the default), a prompt larger than the remaining budget is cut to fit. The real code first asks the KV cache manager for cached prefix blocks (get_computed_blocks) and starts num_computed_tokens after them.
3. Update after the model runs. num_computed_tokens advances by the scheduled tokens. A request whose known tokens are all computed samples a new token. A request that reaches its length finishes and frees its blocks.

Reading the steps:

• Step 1: A is admitted with 8 of its 10 prompt tokens (chunked prefill) and takes 2 blocks. B is not admitted, because the budget is used up.
• Step 2: A, now running, gets its last 2 prompt tokens and samples its first output token. B is admitted with its whole 6-token prompt. Both prefill in the same step.
• Step 3: A and B decode one token each, and C's 5-token prompt fills part of the remaining budget. All 7 blocks are now in use.
• Step 4: three decodes. Each request stays within its blocks.
• Step 5: A reaches 13 tokens and needs a fourth block. None is free, so the scheduler preempts C, the last running request, and frees its 2 blocks. A takes one, and B takes the other. A produces its fourth token and finishes, freeing 4 blocks.
• Step 6: C is back at the front of the waiting queue and is recomputed: 7 tokens (its 5-token prompt plus the 2 tokens it had generated) in one chunk. It produces its third token and finishes.
• Step 7: B produces its sixth token and finishes.

The real schedule() adds the parts this copy leaves out: speculative-decoding tokens, encoder inputs for multimodal models, KV connectors (Example 10), LoRA limits, and pausing. After schedule() returns a SchedulerOutput, the model runner executes the batch. Then update_from_output() (line 1874) appends sampled tokens, checks stop conditions, and frees finished requests. This is the program's phase 3. The lesson on vLLM architecture and installation places this loop inside the engine core process.

Interview points

• A single decode request uses about 2% of an RTX 4090's arithmetic capacity on an 8B 4.5-bit model, because each step waits for the weights to be read from memory. Batching shares the weight reads across requests, and the per-sequence KV reads then limit throughput.
• Static batching wastes slots on padding and makes new requests wait for the longest request in the group. Continuous batching admits and retires requests at every step.
• A long prompt processed in one step stalls every decoding request, which shows up as a spike in inter-token latency. Chunked prefill with a token budget bounds the size of each step.
• The token budget should be large enough to reach the arithmetic-bound region and small enough to keep steps short. vLLM's defaults grow with the GPU, from 2,048 to 16,384.
• Shortest-first minimizes mean wait but starves long requests. Output lengths are unknown, so engines default to FCFS. vLLM also has a priority policy with no aging.
• Little's law L = λW sizes concurrency. It holds only in a stable system, so overload needs admission control (vLLM --max-num-queued-reqs and --max-num-queued-tokens, answered with HTTP 503).
• vLLM preempts the last running request (FCFS) or the lowest-priority one, frees its blocks, and recomputes it later. Prefix caching makes the recompute cheaper.
• Swapping moves KV over PCIe (about 17 ms for 250 MiB both ways). Recompute costs prefill arithmetic (hundreds of milliseconds for 2,000 tokens on one consumer GPU).
• Per-tenant fairness (caps, round-robin) is not built into vLLM or llama-server. It belongs in a gateway in front of the engine.
• Disaggregated serving moves the KV cache from a prefill pool to a decode pool. The transfer is about 1% of prefill time over NVLink and about 32% over 100 Gb/s Ethernet for an 8B model.
• llama-server batches the sampled token of each generating slot first, then prompt chunks up to -b. When KV memory runs out, it halves the batch and finally fails, without preemption.

Summary

• On an RTX 4090 with an 8B 4.5-bit model and 4,096-token contexts, batch 1 gives 199.5 tokens per second at 1.94% FLOP utilization, and batch 32 gives 1,487 tokens per second at 14.45%.
• Static batching of 8 requests in groups of 4 needs 35 steps and uses 53% of slot-steps. Continuous batching needs 27 steps, uses 69%, and lowers the mean finish step from 27.5 to 13.1.
• A 4,000-token prompt in one step raised the decoders' gap from 10 to 80.08 cost units. A 512-token budget kept the gap at 10.24 and delayed the new request's first token by 2%.
• Too small a budget (256 in the simulation) doubles the new request's time to first token, because each step pays the full weight-streaming cost.
• vLLM's --scheduling-policy is fcfs (default) or priority. A priority queue orders by priority value, then by arrival time.
• Little's law held within 0.1% in the stable simulations and failed under overload. A 16-request queue limit rejected 815 of 8,831 requests and kept the mean time at 50.71 ticks.
• vLLM 0.30.0 preempts by recompute: _preempt_request frees blocks, sets num_computed_tokens = 0, and puts the request at the front of the waiting queue. vllm:num_preemptions counts preemptions.
• Waiting requests are scheduled only in steps without preemption, and only while the budget and max_num_seqs allow.
• --kv-transfer-config selects a KV connector (for example NixlConnector) and a kv_role of kv_producer, kv_consumer, or kv_both.
• In a real llama-server run with -b 256, every step carried 1 decode token and a 255-token prompt chunk until the 2,450-token prompt was done.
• llama-server enables continuous batching by default (-cb). -nocb adds prompts only to an empty batch.