High-Throughput LLM Inference Serving: Continuous Batching, PagedAttention, and Chunked Prefill

1. Problem and Motivation

Project Identity, Version & License Baseline

Serving Large Language Models (LLMs) in production is one of the most computationally demanding and economically critical disciplines in modern systems engineering. Unlike conventional web applications where stateless microservices handle HTTP requests in isolated CPU threads, LLM serving faces severe hardware and mathematical boundaries:

+---------------------------------------------------------------------------------------------------+
|                                 THE LLM SERVING TRILEMMA                                          |
+---------------------------------------------------------------------------------------------------+
|  1. The Two-Phase Computational Dichotomy:                                                        |
|     - Prefill Phase: Ingesting input prompts is COMPUTE-BOUND (matrix-matrix multiplication, GEMM).|
|       Arithmetic intensity is high; tensor cores operate near peak TFLOPS.                       |
|     - Decode Phase: Emitting tokens one-by-one is MEMORY-BANDWIDTH BOUND (matrix-vector, GEMV).   |
|       Arithmetic intensity is near zero; execution speed is throttled by GPU HBM memory bandwidth.|
|  2. Variable Output Lengths & Padding Collapse: Static batching forces all sequences to lockstep;  |
|     short sequences finish early and sit idle as padding waste for hundreds of iterations.        |
|  3. The KV Cache Memory Wall: Storing Keys and Values for multi-thousand token contexts consumes   |
|     tens of gigabytes of GPU HBM per active user. Pre-allocating contiguous memory wastes up to   |
|     80% of GPU memory due to internal fragmentation.                                              |
|  4. Conflicting Latency SLAs:                                                                     |
|     - Time-To-First-Token (TTFT): Prompt processing speed (target < 200ms).                       |
|     - Inter-Token Latency (ITL): Time between successive output words (target < 30ms for reading).|
+---------------------------------------------------------------------------------------------------+

2. Mental Model & Architectural Overview

Modern LLM inference engines (vLLM, TensorRT-LLM, HuggingFace TGI) abandon static request batching and contiguous memory buffers in favor of Continuous Iteration-Level Batching and PagedAttention.

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED AI

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 4

1. Static Batching Padding Bottleneck

Legacy batching locks all requests in a batch until the longest sequence completes, causing > 60% idle tensor core waste due to padding tokens.

Architectural Invariant: Throughput Loss: Static batching is bounded by slowest sequence length; GPU memory sits allocated but completely idle.

ARCHITECTURAL FLOW · STEP 2 OF 4

2. Continuous Batching Iteration-Level Eviction

vLLM evaluates batch membership at every token iteration. The instant Req 1 emits <EOS>, it is evicted and Req 4 is inserted at the very next forward pass.

Architectural Invariant: Zero Wasted Slots: Maintains > 95% GPU Tensor Core continuous occupancy, delivering 3x-5x higher serving throughput.

ARCHITECTURAL FLOW · STEP 3 OF 4

3. PagedAttention Non-Contiguous Block Mapping

Inspired by OS virtual memory page tables, PagedAttention partitions KV tensors into fixed-size physical blocks (16 tokens) allocated on-demand anywhere in HBM.

Architectural Invariant: Near-Zero Fragmentation: Memory waste plummets from 80% to under 4% (only the final partially-filled block of a request).

ARCHITECTURAL FLOW · STEP 4 OF 4

4. Chunked Prefill & Latency SLA Protection

Massive 8,000-token prompts are divided into 512-token chunks and co-scheduled alongside active decode tokens in the same forward pass.

Architectural Invariant: SLA Invariant: Prevents compute-heavy prefill bursts from stalling the inter-token latency (ITL < 30ms) of active streaming users.

The Three Foundational Innovations:

1. Continuous Batching (Iteration-Level Scheduling):
   • Instead of waiting for an entire batch to complete, the scheduler steps through model execution one iteration (token) at a time.
   • As soon as Request $A$ produces an <EOS> (End-of-Sequence) token at step 12, it is immediately removed from the batch.
   • Request $B$ waiting in the arrival queue is instantly inserted into the batch for step 13 without re-initializing other requests.
2. PagedAttention Virtual Memory:
   • Inspired by classical OS virtual memory paging, the Key-Value (KV) cache is broken into fixed-size physical blocks (e.g., 16 tokens).
   • Blocks reside in non-contiguous physical GPU HBM frames.
   • A Block Table maps logical token sequences to physical frames on-the-fly, reducing memory fragmentation from $80\%$ to under $4\%$.
3. Chunked Prefill & Speculative Decoding:
   • Long prompts are partitioned into smaller chunks (e.g., 512 tokens) and co-scheduled alongside active decode tokens to prevent ITL latency spikes.
   • A lightweight Draft Model generates candidate tokens, verified in parallel by the target model in a single forward pass.

Foundational Bridge: Speculative Decoding Acceptance Math, Disaggregated Prefill/Decode & Token-Aware AI Gateways

At planetary serving scale, production LLM platforms combine three architectural optimizations above the single-node PagedAttention scheduler:

1. Speculative Decoding Speedup & Expected Token Acceptance:
   • Because autoregressive decoding is memory-bandwidth bound (loading $100\%$ of model weights per token), a small draft model $M_q$ (or Medusa/EAGLE head) proposes $\gamma$ candidate tokens sequentially, which the target model $M_p$ verifies in one parallel forward pass.
   • With per-token rejection-sampling acceptance probability $\alpha =\mathbb{E}[\min (1,p(x)/q(x))]$, the expected number of tokens generated per target verification step is: $$\mathbb{E}[\text{Tokens per Step}]=\frac{1-{\alpha }^{\gamma +1}}{1-\alpha }$$ Crucially, speculative decoding preserves the exact mathematical output distribution $p(x)$ of the target model (zero quality loss), though its latency advantage diminishes at large batch sizes where GPU compute reaches saturation.
2. Disaggregated Prefill and Decode Clusters (Splitwise / DistServe / Mooncake):
   • Co-locating compute-bound Prefill (high arithmetic intensity, high TTFT sensitivity) and memory-bandwidth-bound Decode (low arithmetic intensity, strict ITL $<25\text{ ms}$ SLO) on the same GPU causes prefill interference spikes. Disaggregated serving routes prompts to compute-optimized Prefill Nodes, transfers the resulting KV-cache blocks over RDMA/NVLink to bandwidth-optimized Decode Nodes, and scales each pool independently.
3. Token-Aware AI Gateways & Streaming Guardrails:
   • Traditional L7 proxies rate-limit by HTTP requests/sec, which fails when one prompt consumes $128\text{k}$ context tokens while another consumes $64$ tokens. Production AI Gateways enforce Tokens-Per-Minute (TPM) dual token buckets, Prefix-Cache Affinity Routing (hashing shared system-prompt prefixes to replicas holding warm RadixAttention KV trees in HBM), and asynchronous input/output guardrail classifiers (PII redaction and prompt-injection filtering).

3. Terminology & Core Mechanics

• KV Cache: The tensor memory storing the Key and Value representations of all previous tokens in an autoregressive sequence, preventing quadratic re-computation of attention history.
• Arithmetic Intensity: The ratio of floating-point operations (FLOPs) performed to bytes of memory transferred from DRAM: $$\text{Arithmetic Intensity}=\frac{\text{FLOPs}}{\text{Bytes Transferred}}$$
• PagedAttention: An attention algorithm that computes attention over non-contiguous physical memory blocks stored in a block table.
• Copy-on-Write (CoW): An optimization where multiple requests sharing a common prompt prefix (e.g. system prompts or parallel sampling) share identical physical KV blocks until a sequence generates a unique divergent token.
• TTFT (Time-To-First-Token): The latency from the user submitting a prompt to the first token rendering on screen.
• ITL (Inter-Token Latency / Time-Per-Output-Token): The average duration required to generate each subsequent token during the decode phase.

4. Internal Workings & Algorithms

1. PagedAttention: Block Tables and Allocation

In traditional engines, if the maximum context window is $L=4,096$ tokens, the engine pre-allocates contiguous memory for all 4,096 tokens upfront:

• A request that completes in 200 tokens leaves $95\%$ of its allocated memory completely unused (Internal Fragmentation).
• Other requests are rejected with Out-Of-Memory (OOM) errors even though $80\%$ of physical HBM is completely empty!

The PagedAttention Mechanism:

1. Physical GPU memory is divided into a pool of Physical Blocks (e.g., 16 tokens per block).
2. Each active request maintains a Block Table:

   Logical Token Sequence:  [Token 0 - 15]   [Token 16 - 31]   [Token 32 - 47]
                                   |                |                 |
   Block Table:              Logical Block 0  Logical Block 1   Logical Block 2
                                   |                |                 |
   Physical GPU Frames:      Frame #14        Frame #3          Frame #78

3. During attention calculation, custom CUDA kernels read the block table to gather non-contiguous blocks on-the-fly.
4. When a request generates token 16, the engine allocates only one new 16-token physical block from the free frame list.

2. Copy-on-Write (CoW) Prefix Sharing

When running Parallel Sampling (e.g., generating $N=4$ independent completions for a single prompt) or multi-turn conversational agents with a common system prompt:

[ Common System Prompt: 2,000 tokens ]
          |
          +---> Physical Blocks #1 to #125 (Shared Reference Count = 4)
          |
    +-----+-----+-----+-----+
    |     |     |     |     |
 Output 1 Output 2 Output 3 Output 4
 (Fork)   (Fork)   (Fork)   (Fork)

All 4 candidate streams point to the exact same physical KV cache frames. Memory is only allocated when output streams generate unique tokens. This unlocks a $3\text{x}$ to $4\text{x}$ increase in concurrent batch capacity!

5. Mathematical Models & Capacity Sizing

Let us derive the exact memory footprint of the Key-Value cache.

1. KV Cache Memory Formulation

For a Transformer decoder model:

• $n_{\text{layers}}$: Number of Transformer layers.
• $n_{\text{q\_heads}}$: Number of Query attention heads (where $d_{\text{model}}=n_{\text{q\_heads}}\times d_{\text{head}}$).
• $n_{\text{kv\_heads}}$: Number of Key-Value heads ($n_{\text{kv\_heads}}=n_{\text{q\_heads}}$ in MHA; $1<n_{\text{kv\_heads}}<n_{\text{q\_heads}}$ in GQA; $n_{\text{kv\_heads}}=1$ in MQA).
• $d_{\text{head}}$: Dimension of each attention head.
• $b_{\text{elem}}$: Bytes per element ($2\text{ bytes}$ for FP16/BF16, $1\text{ byte}$ for FP8).
• $L_{\text{ctx}}$: Sequence context length in tokens.

For each token, we store one Key tensor and one Value tensor across all $n_{\text{layers}}$ layers: $$\text{Memory per Token (Bytes)}=2\times n_{\text{layers}}\times n_{\text{kv\_heads}}\times d_{\text{head}}\times b_{\text{elem}}$$ $$\text{Total KV Cache (Bytes)}=2\times n_{\text{layers}}\times n_{\text{kv\_heads}}\times d_{\text{head}}\times b_{\text{elem}}\times L_{\text{ctx}}$$

Worked Example: Llama-3-70B (BF16 Precision, $b_{\text{elem}}=2$)

• $n_{\text{layers}}=80$, $n_{\text{q\_heads}}=64$, $d_{\text{model}}=8,192$
• Grouped-Query Attention (GQA $8:1$): $n_{\text{kv\_heads}}=8$, $d_{\text{head}}=128$
• Context length: $L_{\text{ctx}}=8,192\text{ tokens}$

For a batch of 64 concurrent users at full 8,192 context: $$\text{Batch KV Cache Memory}=64\times 2.684\text{ GB}=171.80\text{ GB}(160.00\text{ GiB})$$

This proves why Grouped-Query Attention (GQA) and PagedAttention are mandatory: without GQA, unoptimized 64-head Multi-Head Attention ($n_{\text{kv\_heads}}=64$) would demand $8\times 171.80\text{ GB}=1.374\text{ TB}$ ($1.25\text{ TiB}$) of HBM, making interactive serving economically unviable.

6. Real Implementation & Systems Comparison

7. Production Code Engine: Continuous Batching & Block Manager

The following TypeScript implementation simulates:

1. The PagedAttention Physical Block Manager managing fixed-size token pages.
2. The Continuous Batching Scheduler evicting completed sequences and admitting new requests dynamically at every single token iteration.

/**
 * Production-Grade LLM Serving Engine Simulator
 * Demonstrates Continuous Iteration-Level Batching and PagedAttention Block Management.
 */

export const BLOCK_SIZE = 16; // 16 tokens per physical block

export interface InferenceRequest {
  id: string;
  promptTokens: number;
  maxOutputTokens: number;
  tokensGenerated: number;
  isFinished: boolean;
  blockIds: number[]; // Logical to physical block pointers
}

export class PagedBlockManager {
  private freeBlocks: number[];
  private blockRefCounts: Map<number, number> = new Map();

  constructor(public readonly totalPhysicalBlocks: number) {
    this.freeBlocks = Array.from({ length: totalPhysicalBlocks }, (_, i) => i);
  }

  public allocateBlock(): number | null {
    if (this.freeBlocks.length === 0) return null; // Out of GPU memory
    const blockId = this.freeBlocks.pop()!;
    this.blockRefCounts.set(blockId, 1);
    return blockId;
  }

  public freeBlock(blockId: number): void {
    const refs = (this.blockRefCounts.get(blockId) ?? 1) - 1;
    if (refs <= 0) {
      this.blockRefCounts.delete(blockId);
      this.freeBlocks.push(blockId);
    } else {
      this.blockRefCounts.set(blockId, refs);
    }
  }

  public getAvailableBlocks(): number {
    return this.freeBlocks.length;
  }
}

export class ContinuousBatchingScheduler {
  private waitingQueue: InferenceRequest[] = [];
  public activeBatch: InferenceRequest[] = [];

  constructor(
    private readonly blockManager: PagedBlockManager,
    public readonly maxBatchSize: number = 8
  ) {}

  public submitRequest(req: InferenceRequest): void {
    this.waitingQueue.push(req);
  }

  /**
   * Executes ONE token iteration across all active requests in the batch.
   */
  public step(): { iterationFinishedTokens: number; activeRequests: number } {
    // 1. Evict finished requests and free their physical KV cache blocks
    const ongoing: InferenceRequest[] = [];
    for (const req of this.activeBatch) {
      if (req.isFinished) {
        req.blockIds.forEach((b) => this.blockManager.freeBlock(b));
      } else {
        ongoing.push(req);
      }
    }
    this.activeBatch = ongoing;

    // 2. Admit new requests from waiting queue if slots and memory are available
    while (
      this.activeBatch.length < this.maxBatchSize &&
      this.waitingQueue.length > 0
    ) {
      const nextReq = this.waitingQueue[0];
      const neededPrefillBlocks = Math.max(1, Math.ceil(nextReq.promptTokens / BLOCK_SIZE));
      if (this.blockManager.getAvailableBlocks() < neededPrefillBlocks) break; // GPU HBM full

      for (let b = 0; b < neededPrefillBlocks; b++) {
        const allocated = this.blockManager.allocateBlock();
        if (allocated !== null) {
          nextReq.blockIds.push(allocated);
        }
      }
      this.activeBatch.push(this.waitingQueue.shift()!);
    }

    // 3. Step execution: generate exactly 1 token per active request
    let finishedThisStep = 0;
    for (const req of this.activeBatch) {
      req.tokensGenerated++;

      // Check if current block is full (needs next 16-token page)
      const totalTokens = req.promptTokens + req.tokensGenerated;
      if (totalTokens % BLOCK_SIZE === 1 && totalTokens > BLOCK_SIZE) {
        const newBlock = this.blockManager.allocateBlock();
        if (newBlock !== null) {
          req.blockIds.push(newBlock);
        } else {
          // OOM handling: preempt or truncate
          req.isFinished = true;
          continue;
        }
      }

      // Check for sequence completion
      if (req.tokensGenerated >= req.maxOutputTokens) {
        req.isFinished = true;
        finishedThisStep++;
      }
    }

    return {
      iterationFinishedTokens: finishedThisStep,
      activeRequests: this.activeBatch.length,
    };
  }
}

function runDemo(): void {
  console.log("=== LLM Serving: Continuous Batching & PagedAttention Simulation ===");
  const blockManager = new PagedBlockManager(64);
  const scheduler = new ContinuousBatchingScheduler(blockManager, 4);
  console.log(`Initialized PagedBlockManager (64 physical blocks, Block Size: ${BLOCK_SIZE} tokens)`);
  scheduler.submitRequest({ id: "req-1", promptTokens: 32, maxOutputTokens: 8, tokensGenerated: 0, blockIds: [], isFinished: false });
  scheduler.submitRequest({ id: "req-2", promptTokens: 16, maxOutputTokens: 4, tokensGenerated: 0, blockIds: [], isFinished: false });
  console.log(`Submitted 2 inference requests to continuous batch scheduler`);
  for (let step = 1; step <= 5; step++) {
    const res = scheduler.step();
    console.log(`Iteration ${step}: Active requests: ${res.activeRequests}, Completed: ${res.iterationFinishedTokens}, Free blocks: ${blockManager.getAvailableBlocks()}`);
  }
}

runDemo();

8. Speculative Decoding & Prefix Caching

1. Speculative Decoding Mechanics & Speedup Derivation

Autoregressive decoding is bottlenecked by the fact that the entire 70B parameter model ($140\text{ GB}$ in BF16) must stream from HBM to SRAM to generate a single token ($I\approx B\ll 295.4\text{ FLOPs/byte}$ on H100 SXM5).

In Speculative Decoding (Leviathan et al., ICML 2023):

1. A small Draft Model $M_p$ (e.g., Llama-3.2-1B) proposes $\gamma$ candidate tokens autoregressively.
2. The large Target Model $M_q$ (Llama-3-70B) executes a single parallel forward pass evaluating all $\gamma +1$ positions under a causal mask, accepting each draft token $x_i$ with probability $\min \left(1,\frac{q(x_i)}{p(x_i)}\right)$ and sampling one bonus/correction token from the normalized residual $\max (0,q(x)-p(x))$.
3. Let $\alpha \in [0,1)$ denote the expected token acceptance probability and $c=\frac{T_{\text{draft}}}{T_{\text{target}}}$ denote the relative wall-clock latency of one draft step versus one target verification pass. The expected tokens generated per verification cycle and net wall-clock speedup are:

• Worked Example: For $\gamma =4$, $\alpha =0.80$, and $c=0.05$ ($1\text{B}$ draft vs. $70\text{B}$ target colocated on NVLink): $$\mathbb{E}[\text{Tokens}]=\frac{1-0.80^5}{1-0.80}=\frac{1-0.32768}{0.20}=3.3616\text{ tokens/cycle},\text{Speedup}=\frac{3.3616}{4(0.05)+1}=2.80\times$$

9. Failure Modes, Preemption Thrashing & Operational Recovery

10. Knowledge Check

Review the core serving principles, then complete the 4-question interactive assessment quiz at the end of this lesson:

1. Continuous vs. Static Batching: Explain how iteration-level scheduling eliminates padding waste caused by variable-length completions.
2. PagedAttention: Describe how block tables decouple logical token sequences from physical GPU memory frames.
3. Chunked Prefill: Trace why long prompts cause Inter-Token Latency (ITL) jitter and how chunking restores smooth generation.
4. Speculative Decoding: Derive why evaluating $\gamma$ draft tokens in a single target model forward pass achieves $\frac{1-{\alpha }^{\gamma +1}}{(1-\alpha )(\gamma c+1)}$ acceleration.

11. Practical Exercises & Deliverables

Exercise 1: Benchmark Contiguous vs. Paged KV Allocation

Problem: Calculate the maximum concurrent user capacity of an 80 GiB NVIDIA H100 GPU under contiguous vs. paged allocation. Deliverable:

1. Write a Python or TypeScript simulation with 100 requests having variable output lengths sampled from a Pareto distribution (mean 150 tokens, max 4,096 tokens).
2. Measure the total HBM consumed when pre-allocating 4,096 tokens contiguously vs. allocating 16-token blocks on-demand.
3. Prove that PagedAttention supports at least $3.5\times$ more concurrent requests before triggering Out-Of-Memory preemption.

Exercise 2: Implement Speculative Verification Sampling

Problem: Implement the rejection sampling algorithm used by speculative decoding.
Deliverable:

1. Given output probability distributions from a draft model $p(x)$ and target model $q(x)$, implement the acceptance criterion: $$\text{Acceptance Probability }=\min \left(1,\frac{q(x)}{p(x)}\right)$$
2. If rejected, resample from the normalized residual distribution $\frac{\max (0,q(x)-p(x))}{{\sum }_{x^{\prime }}\max (0,q(x^{\prime })-p(x^{\prime }))}$.
3. Verify across 10,000 trials that the empirical token distribution matches $q(x)$ within statistical sampling noise.

/**
 * Lossless Speculative Decoding Rejection Sampler (Leviathan et al., ICML 2023)
 * Guarantees output token is distributed strictly according to target distribution q(x).
 */
export function speculativeVerifySample(p: number[], q: number[]): { tokenIdx: number; acceptedDraft: boolean } {
  // 1. Sample draft candidate x ~ p(x)
  let r1 = Math.random();
  let draftIdx = 0;
  for (let i = 0; i < p.length; i++) {
    r1 -= p[i];
    if (r1 <= 0) {
      draftIdx = i;
      break;
    }
  }

  // 2. Accept draft token with probability min(1, q(x) / p(x))
  const acceptProb = Math.min(1.0, q[draftIdx] / p[draftIdx]);
  if (Math.random() < acceptProb) {
    return { tokenIdx: draftIdx, acceptedDraft: true };
  }

  // 3. On rejection, sample from normalized residual: max(0, q(x') - p(x'))
  const residual = q.map((qx, i) => Math.max(0, qx - p[i]));
  const normSum = residual.reduce((acc, v) => acc + v, 0);
  let r2 = Math.random() * normSum;
  for (let i = 0; i < residual.length; i++) {
    r2 -= residual[i];
    if (r2 <= 0) {
      return { tokenIdx: i, acceptedDraft: false };
    }
  }
  return { tokenIdx: residual.length - 1, acceptedDraft: false };
}

12. Summary & Architectural Decision Guide

1. Always Enable Iteration-Level Continuous Batching & PagedAttention: Eliminates $>60\%$ contiguous reservation waste and finished-sequence padding, multiplying sustainable QPS by $3\times \text{–}5\times$ on identical GPUs.
2. Protect Decode TPOT SLAs with Chunked Prefill: Cap per-iteration token budgets (max_num_batched_tokens) so incoming long prompts piggyback onto decode steps rather than starving streaming clients.
3. Deploy Speculative Decoding Selectively: Speculative decoding shines at low-to-medium concurrency ($B\le 32$) where target verification utilizes idle Tensor Core FLOPs; disable it automatically at high batch saturation ($B\ge 128$) where target verification becomes compute-bound.
4. Use Automatic Prefix Caching (APC / RadixAttention): For RAG and multi-turn agents sharing system prompts, Copy-on-Write KV block sharing cuts TTFT by $>50\%$ and dramatically expands effective HBM capacity.

13. Authoritative References & Version Context

• Version & Hardware Baseline: Verified against vLLM v0.6+, SGLang v0.3+, NVIDIA TensorRT-LLM v0.12+, and NVIDIA H100 SXM5 (80 GiB HBM3, 989.5 TFLOPS dense BF16, 3.35 TB/s).
• Kwon et al. (SOSP ‘23) — Efficient Memory Management for Large Language Model Serving with PagedAttention: Canonical specification of PagedAttention block tables, Copy-on-Write prefix sharing, and swap/recompute preemption.
• Yu et al. (OSDI ‘22) — Orca: A Distributed Serving System for Transformer-Based Generative Models: Foundational iteration-level scheduling and selective batching architecture.
• Agrawal et al. (OSDI ‘24) — Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve: Introduces chunked prefill and stall-free decode piggybacking.
• Leviathan, Kalman & Matias (ICML ‘23) — Fast Inference from Transformers via Speculative Decoding: Exact mathematical proof of lossless rejection sampling and the $\frac{1-{\alpha }^{\gamma +1}}{(1-\alpha )(\gamma c+1)}$ wall-clock speedup equation.