Inference Acceleration

Appearance

Batching and Request Scheduling

At a glance Batching is the core performance knob of GPU inference — static batching waits until a batch is full (high latency), dynamic batching is a compromise, and continuous batching can swap requests in and out at every step (the innovation of vLLM/SGLang). This article covers scheduling policies, prefill/decode disaggregated scheduling, and the vLLM scheduler mechanism.

Batching and Request Scheduling ​

Concept Definition: Merging Many Requests into One Computation ​

GPUs are built on the philosophy of "tens of thousands of threads in parallel" — feed them a single request and most of the compute and bandwidth sits idle. Batching merges multiple independent requests into one large batch computed in a single pass, raising the arithmetic intensity (AI) on the Roofline and letting the GPU run at full tilt.

Two key insights for batching:

  1. Larger batch means higher throughput, but also higher latency — this is the direct expression of the Latency, Throughput, and Concurrency trade-off in batching;
  2. LLM batching is special — requests differ in input length, generation length, and KV cache footprint; traditional static batching cannot handle this.

LLM inference batching has evolved through three generations: static batching (wait until full) → dynamic batching (merge on arrival) → continuous batching (swap at every step). The last is the core innovation of vLLM and PagedAttention and SGLang.

1. The Evolution of Batching Across Three Generations ​

1. Static Batching ​

The most naive approach: wait until a batch is full (e.g. 8 requests), execute, and return only after all requests finish generating.

text
Time:     t=0           t=1   t=2  ...  t=50  t=200
Request1: [prefill]──────decode─────────────────[done]
Request2: [prefill]──────decode────[done]       [waiting]   ← done early, still waits
Request3: [prefill]──────decode────────────[done][waiting]
...
Request8: [prefill]──────decode─────────────────────────[done]
                                   ↑
                           the longest request sets the batch duration
  • Pros: simple to implement, low kernel-dispatch overhead;
  • Cons: ① short requests wait for long ones; ② a batch can't be dispatched until it's full (high latency); ③ the GPU spends much of its time waiting out the tail of the longest request.

The Tail Waste of Static Batching

If 7 of 8 requests generate 50 tokens and 1 generates 200, static batching runs the whole batch for 200 steps — the GPU is full for the first 50 steps and then runs a single request for 150 steps, 87% of compute idle. This is why almost nobody uses static batching for LLM serving.

2. Dynamic Batching ​

Merge on arrival — as soon as enough requests accumulate or a timeout fires, form a batch and execute. Different request batches may coexist.

text
t=0:    requests 1,2,3 arrive → form batch_A → execute
t=1:    requests 4,5 arrive → wait
t=2:    requests 4,5,6 reach 3 → form batch_B → execute
        (batch_A and batch_B run in parallel)
  • Pros: less waiting than static, higher throughput;
  • Cons: still switches in units of "batches" — a request can't change batches midway; this was the early default of NVIDIA Triton Inference Server.

3. Continuous Batching ​

Also called in-flight batching / iteration-level batching — the batch is re-formed after every generated token: new requests can join, and finished requests can leave.

text
t=0:    requests 1,2,3 are decoding
t=1:    request 3 finishes → evicted; request 4 arrives → admitted → now requests 1,2,4 are decoding
t=2:    request 5 arrives → admitted → now requests 1,2,4,5
t=3:    request 1 finishes → evicted → now requests 2,4,5
...
  • Pros: ① no tail waste; ② new requests don't wait for the current batch to finish; ③ the GPU stays continuously full;
  • Cons: scheduling is complex (dynamic batches, dynamic KV cache, dynamic attention masks must all be managed); only early vLLM/SGLang supported it.

Continuous Batching Is the Standard for LLM Serving

Modern LLM serving stacks (vLLM, SGLang, TensorRT-LLM, TGI) all use continuous batching — it is the key engineering that lifts single-GPU throughput from ~10 tokens/s to ~3000 tokens/s. Almost every online LLM service should use continuous batching. See vLLM and PagedAttention.

2. Scheduling Policies: Deciding Which Request Runs First ​

After requests arrive, how they queue and form batches depends on the scheduling policy:

Common Policies ​

PolicyHow It WorksStrengthsWeaknesses
FIFO (first-come-first-served)Queue by arrival orderFair, simple to implementShort requests held back by long ones
SJF (shortest job first)Prioritize requests predicted to be shortLowest average latencyPredicting prompt→generation length is hard; long requests starve
PriorityBy business priorityVIPs firstComplex; requires business-side coordination
Fair SchedulingRound-robin across users/tenantsFair, avoids starvationSlightly higher overall latency
SRTF (Shortest Remaining Time First)Prioritize the fewest remaining tokensTheoretically optimalFrequent-switching overhead

Practical Choices for LLM Serving ​

  • vLLM defaults to FCFS — simple and stable;
  • Add a priority queue — VIP users get a separate queue with separate batch scheduling;
  • Token-budget-based fairness — N tokens per second per user; the scheduler tries to meet the quota;
  • Schedule prefill and decode separately (see below).

3. Prefill vs. Decode: Phase-Disaggregated Scheduling ​

LLM inference prefill (compute-intensive) and decode (memory-intensive) have completely different bottlenecks (see Latency, Throughput, and Concurrency). The optimal scheduling policy treats them separately:

PhaseOperator CharacterScheduling GoalPolicy
prefillcompute-boundSaturate compute per prompt; prompt lengths vary widelyBatch each prompt alone; bucket prompts by length
decodememory-boundFill memory; decode all concurrent requests togetherMerge into large batches; pack up to the memory ceiling

Why Prefill and Decode Must Be Scheduled Separately

  • A long prompt in prefill is compute-bound — batching it alone lets a single prompt saturate Tensor Core compute;
  • Mixing short and long prompts in prefill is unfair — short prompts wait for the long one's compute;
  • In decode, all requests share the weights, so piling on batch is almost free (bandwidth unchanged, compute amortized) — large merged batches are optimal;
  • When prefill and decode run at the same time, prefill competes with decode for bandwidth → use chunked prefill to smooth resource usage.

Chunked Prefill ​

The prefill of a long prompt (e.g. 8K tokens) running in one shot monopolizes the GPU for hundreds of milliseconds, blocking requests that are decoding. Chunked prefill cuts the long prefill into chunks (e.g. 256 tokens) that alternate with decode requests:

text
Before:   long prefill (8K) ━━━━━━━━━━━━━━ → decode must wait until the long prefill finishes
Chunked:  prefill_chunk1(256) | decode*3 | prefill_chunk2(256) | decode*3 | ...
          ↑ alternating with decode: prefill doesn't steal bandwidth, decode doesn't starve

vLLM 0.5+ enables chunked prefill by default — a win-win for TTFT and decode throughput.

4. Inside the vLLM Scheduler ​

As the industrial exemplar of continuous batching, let's look at how the vLLM scheduler works:

1. Core Data Structures ​

2. The Scheduling Loop ​

text
Loop:
1. Check the memory budget (available KV blocks)
2. Decide this step's batch:
   a. Put all requests in the running queue into the batch (decode)
   b. If memory remains, pick prompts from the waiting queue for prefill
   c. If memory runs out, swap some running requests out (fallback)
3. Execute one step (prefill + decode together)
4. Check whether each request has finished generating → evict
5. Back to 1

3. Memory Budget and Preemption ​

When memory can't hold all running + new waiting requests, vLLM uses preemptive scheduling:

  • Recompute the KV cache of some running requests or swap them to CPU memory;
  • Swap them back in and resume decoding once memory frees up.

The cost is high but fairness is guaranteed — vLLM keeps the service available in extreme scenarios. See vLLM and PagedAttention.

4. Prefix Caching Optimization ​

Multiple requests sharing the same system prompt reuse the KV cache:

text
Request1: [system_prompt + Q1] → prefill computes [system_prompt]
Request2: [system_prompt + Q2] → reuses the KV of system_prompt; only Q2 is computed
          ↑
          TTFT drops sharply

vLLM's enable_prefix_caching is on by default.

5. Scheduling Metrics: What "Good Scheduling" Looks Like ​

Good scheduling is measured by four classes of metrics:

MetricMeaningOptimization Lever
Throughput (tokens/s)Total tokens produced per secondSaturate memory and bandwidth
TTFT percentiles (p50/p99)Distribution of time-to-first-tokenchunked prefill + prefix cache
TPOT percentiles (p50/p99)Distribution of per-token latencySufficient memory budget; no swapping
Tail latency (p99.9)Extreme long tailFair scheduling; prevent request starvation

Don't Look at Throughput Alone

High throughput ≠ good service. A service delivering 1000 tokens/s with a p99 TTFT of 30s (VIP users waiting 30 seconds for the first token) is still a bad experience. Production services must watch percentile latency — for interactive scenarios, p99 matters 10× more than the mean.

6. Scheduling Highlights of Other Engines ​

EngineScheduling Highlights
vLLMcontinuous batching + PagedAttention + chunked prefill (see vLLM and PagedAttention)
SGLangcontinuous batching + RadixAttention (automatic prefix caching via a prefix tree)
TensorRT-LLMin-flight batching + memory planner + INT8/FP8/FP4 quantized scheduling
TGIcontinuous batching (an early contributor)
Triton Inference Servergeneral dynamic batching (supports LLM backends; see Triton Inference Server)
DeepSpeed-FastGenDynPI (Dynamic Prefill and decode batching with Importance)

7. Engineering Trade-offs in Scheduling and Concurrency Control ​

DimensionTrade-offRules of Thumb
Batch size ceilingLarge = high throughput vs. small = low latencymax_batch=128-256 for online serving; 1024+ for batch processing
max_num_seqs (vLLM)Large = more concurrency vs. small = enough memory128-256 recommended for Llama-70B on an 80GB H100
prefill chunk sizeLarge = full compute vs. small = decode doesn't starve128-512 tokens
Request timeoutLong = no interruption vs. short = prevents stuck requests60-300 seconds
Queue lengthLong = high utilization vs. short = fast response< 8 online; larger for batch processing
Swap enabledon = keeps service alive in extremes vs. off = no wasteOff when memory suffices; on when memory is tight

Starting Points for Tuning

  • vLLM defaults are good enough for most scenarios — max_num_seqs=128, enable_prefix_caching=True, use_cuda_graph=True;
  • To lower TTFT: enable prefix cache, increase the prefill chunk size;
  • To lower TPOT: increase max_num_seqs (mind the memory);
  • To lower p99 tail latency: reduce max_batch, enable fair scheduling, turn off swap;
  • To cut cost: raise max_num_seqs until the memory ceiling.

8. Combining Scheduling with the Latency Model ​

Applying Little's Law from Latency, Throughput, and Concurrency to scheduling:

text
Concurrency = throughput × average latency

Example: a single GPU running Llama-2-70B
- Throughput ceiling: 3000 tokens/s (H100 + AWQ + continuous batching)
- Per-request average: 200 output tokens / 50ms = 4 req/s × 5s = 20 concurrent
- Check: 20 concurrent × 200 tokens = 4000 tokens in flight (reasonable — KV cache ≈ 100GB)
- Inference: to carry 1000 QPS (short requests, input+output), you need ~50 H100s

This is the starting point of capacity planning — the scheduler should hold concurrency at the knee of the curve (Latency, Throughput, and Concurrency).

9. Common Scheduling Pitfalls ​

  1. Watching throughput but not latency — many benchmarks report "vLLM 3000 tokens/s on a single GPU," but production p99 TTFT may be 5s;
  2. No grouping or bucketing — when long and short requests mix, long requests occupy memory slots and short requests starve;
  3. Prefix cache off — a long system prompt gets recomputed for every request, inflating TTFT;
  4. CUDA graphs vs. continuous batching conflict — CUDA graphs need fixed shapes while continuous batching needs dynamism; solved by bucketed capture (see Computation Graph Optimization);
  5. Frequent swapping — a memory budget too small triggers repeated swaps and throughput collapses; keep 10-20% memory headroom.

10. Trade-offs ​

  • Throughput vs. latency: interactive → small batch + continuous batching + chunked prefill; batch processing → large batch + simple scheduling;
  • Fairness vs. priority: fairness by default; add priority queues for VIP business;
  • Memory utilization vs. stability: max out concurrency vs. leave headroom against swaps — usually leave 10-20%;
  • Complex vs. simple scheduling: vLLM defaults are enough; go to SGLang or in-house only for extreme optimization (e.g. separating VIP from regular users);
  • Self-hosted vs. platform: self-host with vLLM for simplicity and control; at scale use Triton Inference Server or Volcano Ark.

Further Reading ​

References ​