Prefill Optimisation: Prefix Caching, Chunked Prefill, and Disaggregation

In modern large language model (LLM) serving systems, request execution splits into two distinct operational regimes: prompt processing (prefill) and autoregressive token generation (decode). While decode processes a single new token per sequence at each iteration, prefill ingests complete input sequences spanning hundreds to tens of thousands of tokens to populate the Key-Value (KV) cache.

This asymmetry introduces two core challenges for high-performance serving engines:

1. Prefill-decode interference: Schedulers that run monolithic prompt prefills alongside ongoing decode iterations monopolize GPU compute and execution time, causing severe spikes in inter-token latency (ITL) for active generation streams.
2. Redundant prompt recomputation: Repeated prompt components—such as system prompts, conversation histories in multi-turn dialogues, few-shot examples, and ingested documents—force the system to repeatedly compute identical KV representations if prompts are treated in isolation.

To solve these problems without degrading generation quality, serving backends employ chunked prefill and prefix caching. This lesson details the mathematical, algorithmic, and architectural mechanisms of both techniques.

---

1. Prefill and decode: execution mechanisms and bottlenecks

Serving engines process requests through two alternating computational phases. Understanding where execution bottlenecks fall requires analyzing tensor dimensions, batching behavior, and memory access patterns.

Asymmetric execution profiles

Prefill Phase (Prompt Evaluation):
  Input:  [Batch, Prompt_Tokens, Hidden_Dim]
  Goal:   Compute KV tensors for all prompt tokens in parallel; produce first output token.
  State:  Populates empty or partial KV cache allocations.

Decode Phase (Autoregressive Generation):
  Input:  [Batch, 1, Hidden_Dim]
  Goal:   Attend to all prior KV tokens; project logits for exactly one new token per sequence.
  State:  Appends new K and V vectors to existing sequence allocations at each step.

In early or unbatched systems, prefill and decode were often characterized by a simple dichotomy: prefill was described as universally compute-bound, while decode was described as memory-bandwidth-bound matrix-vector multiplication (GEMV).

In modern production serving systems, this characterization is overly simplistic:

• Decode with batching executes as a GEMM: When a serving engine batches B concurrent decode sequences, the linear projections (QKV projections, output projection, and feed-forward network layers) operate on an input tensor of shape [B, 1, Hidden_Dim]. Multiplying this matrix by weight matrix [Hidden_Dim, Out_Dim] executes a General Matrix Multiply (GEMM), not an isolated GEMV. As batch size expands, arithmetic intensity in these projections increases; whether execution becomes compute-bound depends on the hidden dimensions, numerical precision, GPU compute-to-bandwidth ratio, and kernel tiling efficiency rather than an arbitrary batch threshold.
• Attention memory traffic scales with context length: During decode, the attention kernel reads the relevant accumulated KV cache for all B sequences through the memory hierarchy; a nominal traffic model charges those reads to HBM to evaluate attention against the single query token. For moderate-to-long context lengths, this memory loading typically dominates the attention step, making attention memory-bandwidth intensive.
• Prefill compute saturation depends on workload shape and kernels: On very long prompts with high KV head counts, intermediate tensor traffic and memory-bound operations can introduce significant memory bandwidth pressure. Conversely, short prompts may lack sufficient matrix dimensions to saturate hardware execution units or reach peak arithmetic intensity. Performance characteristics are dictated by matrix shape, operator fusion, and kernel implementation rather than fixed token count cutoffs.
• System bottlenecks are dynamic: The limiting resource of any execution step depends on the interaction between workload geometry (batch size, prompt length, accumulated context length), precision format (FP16, BF16, FP8, INT4), hardware specifications (memory bandwidth and Tensor Core throughput), and kernel implementation (such as FlashAttention, FlashDecoding, or PagedAttention; see vLLM Configuration and Optimization Guidelines, accessed 2026-11-03).

---

2. Chunked prefill: bounded token scheduling without latency guarantees

When an engine admits a long prompt (for example, 4096 tokens) in a monolithic execution block, that prefill forward pass (containing multiple kernels) can take significantly longer than an isolated decode step. Any decode requests co-scheduled in that iteration or queued behind it must wait for the entire prompt computation to finish, causing noticeable jitter in inter-token latency.

Chunked prefill addresses this scheduling conflict by slicing prompt sequences into smaller token chunks and budgeting them across multiple scheduling iterations alongside active decode tokens.

Causal equivalence and numerical tolerance

Splitting a prompt into chunks is valid because standard autoregressive language models use causal attention. Under causal masking, the token at sequence position i attends only to tokens at positions j ≤ i.

Let a prompt sequence of length P be partitioned into consecutive chunks C_1, C_2, ..., C_k. When computing attention for chunk C_m:

1. Tokens in C_m attend to all cached Key and Value vectors from preceding chunks C_1 through C_(m-1) stored in the KV cache.
2. Tokens in C_m apply a standard causal mask among themselves, ensuring token i in C_m only attends to tokens up to its position within C_m.
3. Global positional encodings (such as Rotary Position Embeddings / RoPE) are assigned using each token’s absolute position in the overall sequence, preserving exact positional geometry.

Monolithic Prefill:
[Token 0 .................................................... Token P-1]
Single forward pass: Full causal triangle over P tokens computed at once.

Chunked Prefill:
Chunk 1: [Tok 0 .. Tok C-1]     -> Attends causally to Chunk 1; writes KV to cache.
Chunk 2: [Tok C .. Tok 2C-1]    -> Attends fully to Chunk 1 KV + causally to Chunk 2.
Chunk 3: [Tok 2C .. Tok 3C-1]   -> Attends fully to Chunks 1 & 2 KV + causally to Chunk 3.

Mathematically, exact causal attention over chunks produces the identical analytical result as a monolithic forward pass when evaluated with infinite precision.

However, in finite-precision floating-point arithmetic (such as FP16 or BF16), floating-point addition is non-associative:

(a + b) + c != a + (b + c)

Online softmax algorithms rescale running normalizers across tiled reduction blocks. Because chunking alters tile partitioning boundaries and reduction order across chunks, intermediate accumulators vary. These numerical deviations are not guaranteed to remain bounded by machine epsilon, nor are long autoregressive trajectories guaranteed to preserve identical token choices: slight logit variations can alter top-1 greedy token selection or diverge sampling paths. Production systems validate chunked prefill against unchunked baselines using statistical output tolerance checks and downstream task evaluation benchmarks rather than assuming bitwise or token-identical equivalence.

Mechanics of chunked scheduling

Rather than scheduling an arbitrary mix of requests, the scheduler enforces a global token budget per iteration, denoted as max_batched_tokens (see Sarathi-Serve: Chunked-Prefills for LLM Serving, accessed 2026-11-03).

In each scheduling cycle:

1. Active decode sequences claim budget first: each active decode sequence requires exactly 1 token slot.
2. The remaining token budget is allocated to prefill chunks:

   available_prefill_budget = max_batched_tokens - active_decodes

3. If available_prefill_budget > 0, waiting or partially processed prompts receive slices up to this remaining limit.

A monolithic 2048-token prefill can occupy one long iteration while decodes wait. With a total budget of 512 and four ongoing decodes, the chunked trace is:

Iteration	Decode queries	Prefill queries	Prompt positions cached
1	4	508	508
2	4	508	1016
3	4	508	1524
4	4	508	2032
5	4	16	2048

Each row respects the total query-token budget. Assume those four decoders remain active, a sequence slot is available, and KV reservations succeed throughout. The last chunk produces logits for Prompt A’s first output token; subsequent iterations consume that output in decode.

Important scheduling realities

• Token budget bounds new query tokens, not total attention cost or wall-clock time: Capping max_batched_tokens bounds the number of query tokens admitted to linear projection GEMMs in that step. However, a model forward pass executes multiple sequential GPU kernels (linear projections, RoPE, KV cache writes, attention reductions, layer norms, and logit sampling). Total iteration execution time is not fixed by token count alone.
• Later chunks attend to longer contexts and can take longer: In step 1 of the example above, Chunk 1 (508 tokens) computes attention across only its own 508 tokens. In step 4, Chunk 4 (508 tokens) reads cached KV blocks for the preceding 1524 tokens through the memory hierarchy and compute attention over all 2032 positions. Because attention compute and KV memory traffic expand with prefix depth, later chunks in a long prompt can take noticeably longer to execute than early chunks.
• Latency tradeoffs are conditional: Chunking trades off prompt time-to-first-token (TTFT) against decode continuity. Slicing a prompt across 5 iterations spreads its completion across five model iterations (each containing multiple kernels), adding scheduler overhead and delaying TTFT compared to an unobstructed monolithic prefill. In return, it mitigates prolonged stalls for co-scheduled decodes, but does not eliminate ITL variance.

Tradeoffs in chunk sizing

There is no universally optimal chunk size; parameter selection depends on latency targets and hardware characteristics:

• Smaller chunk sizes: Limit fresh query rows per step and can reduce interference with concurrent decodes; attention cost also depends on history length. However, smaller chunks increase the number of scheduling iterations required to complete a prompt, multiplying CPU dispatch overhead and increasing total TTFT. If the chunk size falls below the hardware’s efficient tile dimension, Tensor Core arithmetic efficiency drops.
• Larger chunk sizes: Increase compute density and Tensor Core efficiency during prefill, reducing TTFT for long prompts. However, large chunks consume a larger fraction of the per-iteration token budget, increase step duration, and risk spiking decode latency.

---

3. Prefix caching and block-level reuse

Many real-world serving workloads feature repeated text across requests:

Request 1: [System Prompt (2000 tok)] + [User Query A (50 tok)]
Request 2: [System Prompt (2000 tok)] + [User Query B (40 tok)]
Request 3: [System Prompt (2000 tok)] + [User Query A (50 tok)] + [Assistant Resp (100 tok)] + [User Query C]

Computing KV tensors for the identical 2000-token system prompt on every incoming request wastes GPU cycles and memory bandwidth. Prefix caching allows an engine to retain previously computed KV blocks in GPU memory and bind them directly to new requests sharing that prefix.

The scope of prefix cache identity

A common misconception is that matching token IDs alone is sufficient to safely reuse cached KV data. In production systems, identical token IDs produce valid KV re-use only when all of the following identity dimensions match:

1. Model weights and base architecture: The identical checkpoint, weight precision, and architectural hyperparameters.
2. Adapter and fine-tuning state: Active LoRA adapters, soft prompts, or runtime rank modifications. A token evaluated under Adapter A yields different key-value projections than under Adapter B.
3. Positional and structural configuration: The identical RoPE base frequency (rope_theta), scaling factors, sequence position offsets, and attention mask configurations.
4. KV cache data representation: Identical numerical data type (e.g., FP16, BF16, FP8 E4M3, FP8 E5M2), quantization scales, and memory layout.
5. Engine configuration and extra cache keys: Cache keys must incorporate the engine configuration, active LoRA identifiers, and any user-specified or tenant-specified isolation keys to prevent unintended sharing across security boundaries.

Serving backends scope cache entries using composite keys combining these environmental factors with sequence content, rather than assuming token IDs in isolation define valid state.

Prefix caching architectures: vLLM and SGLang RadixAttention

Different serving backends organize prefix caching around distinct data structures:

A KV-only cache does not necessarily retain the logits needed to sample the next token. Even when every prompt block matches, an engine may re-evaluate the last prompt token to obtain logits. The lookup example below reports reusable KV positions, not a complete generation procedure.

vLLM block hash chain

In vLLM’s paged design (see vLLM Prefix Caching Architecture, accessed 2026-11-03), the KV cache is divided into fixed-size physical blocks (typically 16 or 32 tokens). Prefix caching operates at block granularity using a parent-hash chain.

Some identity factors are fixed by the engine/cache instance; others appear as extra hash keys. Do not assume every listed configuration value is literally serialized into each block hash.

Each block’s hash digest depends on:

1. The hash digest of its immediate parent block (parent_hash).
2. The ordered token IDs contained in the current block (block_tokens).
3. The scope identifier and engine configuration attributes.

Scope: Model + Adapter + Config + Tenant

   Root State
       |
       v
+--------------+     parent_hash      +--------------+     parent_hash      +--------------+
| Block 0 Hash | -------------------> | Block 1 Hash | -------------------> | Block 2 Hash |
| Tokens 0..15 |                      | Tokens 16..31|                      | Tokens 32..47|
+--------------+                      +--------------+                      +--------------+
       |                                     |                                     |
       v                                     v                                     v
 Physical Block 42                    Physical Block 108                   Physical Block 19
 [KV Tensor Data]                     [KV Tensor Data]                     [KV Tensor Data]

Because each block’s hash incorporates the parent hash, any variation in earlier tokens alters all subsequent hashes downstream:

• If two requests share tokens 0 through 47, Blocks 0, 1, and 2 match and are reused.
• If a single token at index 5 is altered, Block 0’s hash changes completely. Consequently, the input parent_hash for Block 1 changes, preventing incorrect reuse of subsequent blocks even if tokens 16 through 31 are identical.

In vLLM, prefix reuse is governed by a full-block-only policy (reusing tokens in multiples of the block size). This is an engineering policy chosen to align memory allocations with paged kernel execution and simplify free-list management; it is not a theoretical barrier preventing partial-block hashing.

SGLang RadixAttention

SGLang introduces RadixAttention (accessed 2026-11-03), which structures prefix caching as a shared radix tree over token sequences:

• The radix tree represents prompt prefixes hierarchically across all active and completed requests, where edges hold sequences of token IDs and nodes point to cached KV tensors.
• Protected referenced nodes: Nodes currently referenced by active requests (e.g., executing decodes or prefills) are pinned and protected from eviction.
• Tree-based eviction: When GPU memory is needed, the engine traverses the tree and reclaims unreferenced leaf nodes using an LRU policy, pruning unused branch paths.
• Granularity: While RadixAttention describes prefix matching down to arbitrary token boundaries in the logical tree, underlying memory backends frequently align physical allocations to pages or blocks for kernel efficiency.

Cache granularity and eviction in preallocated pools

In an engine with paged memory, physical GPU allocation differs fundamentally from general-purpose operating system paging:

• Configured physical memory pools: At initialization, the engine configures one or more KV cache memory pools based on runtime parameters (such as gpu_memory_utilization), rather than relying on a universal contiguous 90–98% VRAM allocation.
• Three disjoint block buckets:
  1. Active blocks (ref_count > 0): Blocks currently referenced by in-flight prefill or decode requests. These can never be recycled or overwritten while in flight.
  2. Reclaimable cached blocks (ref_count == 0): Blocks whose requests have completed. Their KV data remains intact in GPU memory. If a new request matches their hash, the engine increments their reference count and reuses them immediately. Under memory pressure, these blocks are evicted and reassigned.
  3. Empty free blocks: Unallocated memory buffers containing no valid prefix data.
• Accounting considerations: In systems like vLLM, the internal free block queue may hold or manage zero-refcount reclaimable blocks directly. Schedulers and monitoring scripts must not sum free_blocks + reclaimable_blocks when the reported free count already includes reclaimable cached blocks.
• Eviction is host metadata management: Evicting a prefix block does not call cudaFree or trigger OS driver churn. The physical GPU memory remains allocated within the engine’s pool. Eviction unlinks the block metadata from the hash table or radix tree and marks it available for overwrite.
• Working-set thrashing: If the combined working set of active requests and frequently reused prefixes exceeds pool capacity, the engine enters cache thrashing: reclaimable blocks are overwritten immediately before subsequent requests can match them. This incurs CPU lookup and locking overhead, forces redundant GPU recomputations, and introduces latency variance. High device memory allocation alone does not prove whether the pool is healthy, thrashing, or exhausted.

---

4. Worked mathematical derivations

To quantify the computational savings of prefix caching, we must evaluate both the attention pair reductions and the overall model FLOP reductions.

Suffix-to-prefix self-attention pairs

Consider a model with a prompt of P = 3000 tokens.

• Block size = 16 tokens.
• A cached prefix matches the first 2500 tokens.
• Full blocks matched: 2500 // 16 = 156 full blocks.
• Cached tokens reused: K = 156 * 16 = 2496 tokens.
• Uncached fresh suffix tokens: U = 3000 - 2496 = 504 tokens.

Because this is an autoregressive decoder, computing the fresh suffix tokens requires self-attention across the sequence, not encoder-decoder cross-attention:

1. Suffix-to-prefix pairs: Each of the U = 504 fresh tokens attends to all K = 2496 previously cached prefix tokens:

   Pairs_suffix_prefix = U * K = 504 * 2496 = 1,257,984 token pairs

2. Suffix-to-suffix pairs: Within the fresh suffix itself, each token attends causally to preceding fresh tokens:

   Pairs_suffix_suffix = U * (U + 1) / 2 = 504 * 505 / 2 = 127,260 token pairs

3. Total attention pairs computed:

   Total Pairs = 1,257,984 + 127,260 = 1,385,244 token pairs

By contrast, computing the full 3000-token prompt from scratch requires:

Pairs_full = P * (P + 1) / 2 = 3000 * 3001 / 2 = 4,501,500 token pairs

The prefix-to-prefix attention pairs (2496 * 2497 / 2 = 3,116,256 pairs) are completely skipped.

Projection FLOP estimation and its boundaries

In transformer architectures, linear feed-forward and projection layers account for the dominant share of floating-point operations outside of extreme context lengths.

A standard heuristic for transformer linear layers is:

FLOPs_linear ~= 2 * P * N

where P is the number of evaluated tokens and N is the active model parameter count.

For an 8-billion parameter model (N = 8 * 10^9) processing the U = 504 fresh tokens:

FLOPs_linear ~= 2 * 504 * (8 * 10^9) = 8.064 * 10^12 FLOPs = 8.064 TFLOPs

Analytical boundaries of these estimates

1. The 2 * P * N formula excludes non-linear operations: It accounts only for standard matrix multiplications (QKV projections, attention output projection, MLP gate/up/down projections). It excludes non-linear activations (SwiGLU, GELU), LayerNorm / RMSNorm, Rotary Position Embedding application, and the attention softmax calculation.
2. Attention pairs require structural multipliers to yield FLOPs: A token pair count alone is not a FLOP count. In attention, computing Q * K^T requires 2 * d_head FLOPs per pair, and computing Softmax(A) * V requires another 2 * d_head FLOPs per pair. For a model with L layers and H_Q query heads, the attention FLOP count is:

   FLOPs_attention = 4 * L * H_Q * Pairs * d_head

3. FLOP counts do not predict TTFT: A mathematical count of arithmetic operations divided by the GPU’s theoretical peak throughput represents an idealized compute time under perfect utilization. Real time-to-first-token is dictated by memory bus saturation, HBM read bandwidth for model weights and cached KV blocks, kernel launch latencies, and pipeline stalls. Neither the attention-pair reduction ratio nor the projection FLOP ratio translates directly into a linear TTFT speedup.

---

5. Operational decision framework

In production environments, engineers frequently encounter ambiguous telemetry when optimizing inference systems. Misinterpreting these signals leads to misdirected optimizations.

Scenario: interpreting latency regression and memory reservation

Suppose an engineer monitors a cluster serving an 8B parameter model and observes the following metrics:

• Prefix cache hit rate: 40%
• Inter-token latency (ITL): 3x regression (sharp latency spikes during generation)
• GPU device memory allocation: 98%

A superficial analysis might conclude: “Device memory is at 98%, meaning the KV cache is nearly exhausted and causing thrashing that spikes ITL. We should immediately reduce prefix cache size or reduce concurrency.”

This conclusion is structurally flawed.

Competing explanations and diagnostic checklist

In systems with preallocated block allocators, 98% GPU memory allocation can reflect configured pool reservation. The engine allocates a static pool at initialization. Device memory allocation metrics report how much memory the CUDA runtime has reserved, not how much memory is actively occupied by live sequence context.

Before altering cluster configuration, engineers must evaluate competing hypotheses:

Observed Symptom	Potential Root Cause	Mechanism
High ITL Spikes	Unbounded Prefill Chunks	Prefill chunk size is set too high or chunking is disabled; prompt chunks monopolize the GPU and starve concurrent decodes.
High ITL Spikes	Scheduler Lock Contention	High request concurrency combined with prefix cache lookups creates CPU-side lock contention on the global block table.
High ITL Spikes	Memory Bandwidth Saturation	Batch size during decode has grown large enough that fetching KV caches for all sequences saturates HBM bandwidth.
High Memory Allocation	Expected Pool Reservation	Configured pools can reserve substantial VRAM; inspect active, reclaimable cached and empty-free capacity separately.

Required diagnostic protocol

Correlations in telemetry support hypotheses but do not confirm causality. To establish causality, gather the following measurements before making architectural or parameter changes:

1. Disjoint block pool breakdown: Measure active_blocks (in-flight sequences) versus reclaimable_blocks (zero-refcount cached prefixes) versus empty_free_blocks. Verify whether the allocator’s free list already subsumes reclaimable blocks to avoid double-counting available capacity. If reclaimable and free capacity is substantial, high device allocation reflects normal reservation rather than memory exhaustion.
2. Kernel execution duration: Profile step execution times separated into prefill GEMMs, attention kernels, and decode steps. If mixed iterations take significantly longer than pure decode steps, prefill compute interference is a strong candidate.
3. Host scheduling latency: Measure CPU-side scheduler dispatch duration and block table lock contention to ensure host overhead is not delaying kernel launches.
4. Controlled A/B comparison: Under matched request arrival rates, context lengths, prefix cache warmth, and precision, test alternative chunk sizes (e.g., 512 versus 256) and compare p95 and p99 ITL distributions.

Decision Rule: If an explicit, verifiable hard failure occurs (such as an Out-Of-Memory abort, connection drops, or an absolute latency SLA breach), immediate bounded containment or rollback (such as reducing chunk size or concurrency limits) is warranted before full profiling completes. However, a relative 3x ITL increase without an absolute SLO baseline, paired only with 98% memory reservation, provides insufficient evidence to conclude memory exhaustion; gather allocator bucket breakdowns and kernel execution profiles before modifying cache policies.

---

6. Disaggregated serving and network transfer dynamics

To separate prefill GPU computation from decode GPU computation, modern large-scale architectures explore prefill-decode disaggregation. In this model, prefill and decode execute on physically separate GPU nodes optimized for their respective execution profiles.

+-------------------------------------------------------------+
|                        Prefill Worker                       |
| - High compute density (Tensor Cores saturated)             |
| - Computes prompt KV cache; produces first output token     |
+-------------------------------------------------------------+
                              |
                              | Network KV Transfer
                              | (PCIe -> NIC -> Network -> NIC -> PCIe)
                              v
+-------------------------------------------------------------+
|                         Decode Worker                       |
| - High memory bandwidth (Optimized for KV cache loading)    |
| - Appends single tokens autoregressively                    |
+-------------------------------------------------------------+

Nominal KV transfer arithmetic

When disaggregating nodes (see DistServe: Disaggregating Prefill and Decoding for Goodput-oriented LLM Serving, accessed 2026-11-03), the generated KV cache must be transmitted over the network from the prefill worker to the decode worker before autoregressive generation can continue. Disaggregation isolates GPU compute resources between prefill and decode, but does not remove all system interference: network switch contention, NIC queuing delays, and memory bus transfers remain.

Consider a model with the following architecture:

• Number of layers (L): 32
• Grouped-Query Attention (GQA) Key-Value heads (H_KV): 8 (not 32 query heads)
• Head dimension (d_head): 128
• Numerical precision: FP16 (2 bytes per element)
• Prompt length: 2048 tokens

1. Per-token KV cache memory calculation

For each layer and each token, the cache stores two vectors (Key and Value):

Size_K = H_KV * d_head * sizeof(FP16) = 8 * 128 * 2 = 2,048 bytes
Size_V = H_KV * d_head * sizeof(FP16) = 8 * 128 * 2 = 2,048 bytes
Size_token_layer = Size_K + Size_V = 4,096 bytes (4 KiB)

Total per-token footprint across all 32 layers:
Size_token = 32 * 4,096 bytes = 131,072 bytes = 128 KiB

2. Total sequence payload size

For a prompt of 2048 tokens:

Payload_bytes = 2048 * 131,072 bytes = 268,435,456 bytes
Payload_MiB   = 268,435,456 / (1024 * 1024) = 256 MiB = 0.25 GiB

(Note: Calculating this using 32 query heads would incorrectly yield 1.07 GB. Under Grouped-Query Attention, only the 8 KV heads are retained in memory).

3. Ideal network payload transfer time

Assuming an interconnect with an effective payload bandwidth of 100 Gb/s running at ideal 100% payload capacity:

Bandwidth_bytes_per_sec = (100 * 10^9) / 8 = 12,500,000,000 bytes/sec (12.5 GB/s)

Transfer_time_ideal = 268,435,456 / 12,500,000,000
                    ~= 0.021475 seconds = 21.475 ms

4. Practical systems interpretation

This 21.475 ms calculation represents an ideal payload transmission time under an unconstrained link. It does not represent measured end-to-end transfer latency and does not prove that network transfer is faster or slower than prefill computation:

• Protocol overheads: Real transfers incur Ethernet/IP/TCP framing or InfiniBand/RoCE packet encapsulation overhead.
• Memory copies and bus traversal: On a possible PCIe/NIC path, KV tensors leave prefill GPU memory, cross the fabric, and reach decode GPU memory. Staging copies and bus costs depend on the deployed transport; this arithmetic does not assume a particular data-transfer implementation.
• Pipelining and overlap: Advanced engines can stream KV chunks across the network as intermediate prefill chunks complete, overlapping network transfer with subsequent prefill computation. Overlap is an optional and beneficial optimization, not a mandatory architectural requirement.
• Architectural viability: Disaggregation is not exclusively viable at 400 Gb/s or 800 Gb/s. Its viability depends on sequence length distributions, network placement (intra-rack vs cross-rack), whether transfer overlaps with compute, and the hardware cost savings realized by decoupling compute-heavy prefill GPUs from memory-heavy decode GPUs. Node specialization is an architectural tradeoff, not a single hardware requirement.

---

7. Python implementation: prefix lookup and token-budget scheduling

Below is a complete, single-file Python 3 script combining the pedagogical block-level prefix cache, the deterministic chunk scheduler, and a verification test suite.

import hashlib
from typing import List, Tuple, Dict

class ToyPrefixCache:
    """
    A pedagogical prefix cache demonstrating parent-hash block chaining.

    Disclaimer: This is a non-production teaching simulation illustrating logical
    key lookup. It uses SHA-256 string hashing for transparent serialization;
    it does not manage real GPU KV tensors, track pool capacity, execute memory
    evictions, or provide tenant isolation guarantees.
    """
    def __init__(self, block_size: int = 16):
        if block_size <= 0:
            raise ValueError(f"block_size must be positive, got {block_size}")
        self.block_size = block_size
        # Maps block_hash -> tokens in that block
        self.blocks: Dict[str, List[int]] = {}

    # Contract: token IDs are unsigned 32-bit integers; namespace is fixed per cache scope.
    def _hash_block(self, parent_hash: str, block_tokens: List[int], namespace: str) -> str:
        hasher = hashlib.sha256()
        hasher.update(parent_hash.encode("utf-8"))
        hasher.update(namespace.encode("utf-8"))
        for tok in block_tokens:
            hasher.update(tok.to_bytes(4, byteorder="big", signed=False))
        return hasher.hexdigest()

    def insert_sequence(self, tokens: List[int], namespace: str = "default") -> int:
        num_blocks = len(tokens) // self.block_size
        parent_hash = "ROOT"
        for i in range(num_blocks):
            block_tokens = tokens[i * self.block_size : (i + 1) * self.block_size]
            block_hash = self._hash_block(parent_hash, block_tokens, namespace)
            self.blocks[block_hash] = list(block_tokens)
            parent_hash = block_hash
        return num_blocks

    def match_prefix(self, tokens: List[int], namespace: str = "default") -> Tuple[List[int], List[int]]:
        num_blocks = len(tokens) // self.block_size
        matched_tokens: List[int] = []
        parent_hash = "ROOT"

        matched_blocks = 0
        for i in range(num_blocks):
            block_tokens = tokens[i * self.block_size : (i + 1) * self.block_size]
            expected_hash = self._hash_block(parent_hash, block_tokens, namespace)
            if expected_hash in self.blocks:
                matched_tokens.extend(block_tokens)
                parent_hash = expected_hash
                matched_blocks += 1
            else:
                # Stop at the first missing block
                break

        split_index = matched_blocks * self.block_size
        fresh_tokens = tokens[split_index:]
        return matched_tokens, fresh_tokens

class ChunkedScheduler:
    """
    Schedules prompt tokens and active decodes under a strict token budget.
    """
    def __init__(self, max_batched_tokens: int):
        if max_batched_tokens <= 0:
            raise ValueError(f"max_batched_tokens must be positive, got {max_batched_tokens}")
        self.max_batched_tokens = max_batched_tokens

    def schedule_prompt(self, total_prompt_tokens: int, active_decodes: int) -> List[int]:
        if total_prompt_tokens < 0:
            raise ValueError(f"total_prompt_tokens must be non-negative, got {total_prompt_tokens}")
        if active_decodes < 0:
            raise ValueError(f"active_decodes must be non-negative, got {active_decodes}")

        available_prefill_budget = self.max_batched_tokens - active_decodes
        if available_prefill_budget <= 0:
            raise RuntimeError(
                f"No prefill progress possible: active_decodes ({active_decodes}) "
                f">= max_batched_tokens ({self.max_batched_tokens}). "
                f"Prefill cannot be scheduled without violating budget."
            )

        chunks: List[int] = []
        remaining = total_prompt_tokens
        while remaining > 0:
            chunk_size = min(remaining, available_prefill_budget)
            chunks.append(chunk_size)
            remaining -= chunk_size
        return chunks

def run_verification():
    print("=== TEST 1: Prefix Cache Matching (2496 hit out of 3000) ===")
    cache = ToyPrefixCache(block_size=16)

    # Base sequence: 2500 tokens
    base_prompt = list(range(1, 2501))
    inserted_blocks = cache.insert_sequence(base_prompt, namespace="model_shared")
    print(f"Inserted {inserted_blocks} blocks from base prompt of {len(base_prompt)} tokens.")

    # Query prompt: 3000 tokens (first 2500 shared, 500 new)
    query_prompt = list(range(1, 2501)) + list(range(5000, 5500))
    cached, fresh = cache.match_prefix(query_prompt, namespace="model_shared")
    print(f"Matched cached tokens: {len(cached)}")
    print(f"Remaining fresh tokens: {len(fresh)}")
    assert len(cached) == 2496, f"Expected 2496 cached tokens, got {len(cached)}"
    assert len(fresh) == 504, f"Expected 504 fresh tokens, got {len(fresh)}"
    print("Test 1 Passed: Exactly 156 blocks (2496 tokens) matched; 504 tokens left fresh.")

    print("\n=== TEST 2: Altered Early Block Stops Subsequent Reuse ===")
    seq_original = list(range(100, 164))
    cache.insert_sequence(seq_original, namespace="model_shared")

    # Modify token at index 5 (in block 0)
    seq_mutated = list(seq_original)
    seq_mutated[5] = 999999
    cached_mut, fresh_mut = cache.match_prefix(seq_mutated, namespace="model_shared")
    print(f"Matched cached tokens after early mutation: {len(cached_mut)}")
    print(f"Remaining fresh tokens after early mutation: {len(fresh_mut)}")
    assert len(cached_mut) == 0, f"Expected 0 cached tokens, got {len(cached_mut)}"
    assert len(fresh_mut) == 64, f"Expected 64 fresh tokens, got {len(fresh_mut)}"
    print("Test 2 Passed: Block 0 hash mismatch halted matching; zero subsequent blocks reused.")

    print("\n=== TEST 3: Namespace Isolation ===")
    cached_ns, fresh_ns = cache.match_prefix(base_prompt, namespace="tenant_isolated")
    print(f"Matched cached tokens under different namespace: {len(cached_ns)}")
    assert len(cached_ns) == 0, f"Expected 0 cached tokens, got {len(cached_ns)}"
    print("Test 3 Passed: Namespace boundary prevented cross-tenant cache hit.")

    print("\n=== TEST 4: Chunked Scheduler Budget Tracing ===")
    scheduler = ChunkedScheduler(max_batched_tokens=512)
    chunks = scheduler.schedule_prompt(total_prompt_tokens=2048, active_decodes=4)
    print(f"Scheduled chunks for 2048 prompt with 4 decodes: {chunks}")
    assert chunks == [508, 508, 508, 508, 16], f"Unexpected chunks: {chunks}"
    print("Test 4 Passed: Exact 5-step trace [508, 508, 508, 508, 16] verified.")

    print("\n=== TEST 5: Chunked Scheduler Boundary Condition ===")
    try:
        scheduler.schedule_prompt(total_prompt_tokens=100, active_decodes=512)
    except RuntimeError as e:
        print(f"Test 5 Passed: Caught expected RuntimeError: {e}")
    else:
        raise AssertionError("Test 5 Failed: Did not raise expected RuntimeError on budget exhaustion.")

if __name__ == "__main__":
    run_verification()

Running the script and expected output

Save the combined code as test_prefill_cache.py and run it under Python 3:

python3 test_prefill_cache.py

Expected terminal output:

=== TEST 1: Prefix Cache Matching (2496 hit out of 3000) ===
Inserted 156 blocks from base prompt of 2500 tokens.
Matched cached tokens: 2496
Remaining fresh tokens: 504
Test 1 Passed: Exactly 156 blocks (2496 tokens) matched; 504 tokens left fresh.

=== TEST 2: Altered Early Block Stops Subsequent Reuse ===
Matched cached tokens after early mutation: 0
Remaining fresh tokens after early mutation: 64
Test 2 Passed: Block 0 hash mismatch halted matching; zero subsequent blocks reused.

=== TEST 3: Namespace Isolation ===
Matched cached tokens under different namespace: 0
Test 3 Passed: Namespace boundary prevented cross-tenant cache hit.

=== TEST 4: Chunked Scheduler Budget Tracing ===
Scheduled chunks for 2048 prompt with 4 decodes: [508, 508, 508, 508, 16]
Test 4 Passed: Exact 5-step trace [508, 508, 508, 508, 16] verified.

=== TEST 5: Chunked Scheduler Boundary Condition ===
Test 5 Passed: Caught expected RuntimeError: No prefill progress possible: active_decodes (512) >= max_batched_tokens (512). Prefill cannot be scheduled without violating budget.

---

8. Practical exercises and checked solutions

Exercise 1: Attention pair savings under partial prefix hits

A serving cluster hosts a model with a block size of 32 tokens. A user submits a 4000-token prompt that shares a 3100-token prefix with a cached system prompt.

1. Calculate the number of full blocks reused and the exact number of cached tokens bound to the sequence.
2. Calculate the number of fresh suffix tokens that must be evaluated.
3. Compute the exact number of suffix-to-prefix self-attention token pairs and suffix-to-suffix causal attention pairs required to process the fresh tokens.

Solution

• 1. Reused blocks and cached tokens: Full blocks reused = 3100 // 32 = 96 blocks. Cached tokens bound = K = 96 * 32 = 3072 tokens.
• 2. Fresh suffix tokens: Fresh tokens = U = 4000 - 3072 = 928 tokens.
• 3. Attention token pairs:
  • Suffix-to-prefix self-attention pairs: U * K = 928 * 3072 = 2,850,816 pairs.
  • Suffix-to-suffix causal attention pairs: U * (U + 1) / 2 = 928 * 929 / 2 = 431,056 pairs.
  • Total attention pairs: 2,850,816 + 431,056 = 3,281,872 pairs (skipping 3072 * 3073 / 2 = 4,720,128 prefix-to-prefix pairs).

Exercise 2: Chunk budget boundary conditions

An inference scheduler has max_batched_tokens = 1024.

1. If 300 active decode sequences are currently running, calculate the chunk schedule for a new prompt of 3500 tokens.
2. State the assumptions required for this schedule to hold across iterations.
3. If an arrival burst increases active decodes to 1024 on the next step, describe scheduler behavior and production handling.

Solution

• 1. Chunk schedule: Available prefill budget per iteration = 1024 - 300 = 724 tokens. Slicing 3500 tokens yields 3500 = 4 * 724 + 604. The schedule is [724, 724, 724, 724, 604] across 5 iterations.
• 2. Operational assumptions: Assumes active decodes remain constant at 300 across all 5 iterations; physical KV memory pool has sufficient unallocated or reclaimable blocks to hold both decode and growing prompt KV allocations; total sequence capacity limits are not exceeded.
• 3. Budget exhaustion guard: If active decodes reach 1024, available_prefill_budget = 1024 - 1024 = 0. The scheduler must explicitly halt prefill progress (raising an error or deferring the prompt) rather than dividing by zero or silently dropping decode sequences. Production schedulers prioritize ongoing decodes and pause or queue new prompt chunks until decode sequences complete.

Exercise 3: Root-cause diagnosis under conflicting metrics

An operations engineer observes that cluster P99 inter-token latency has doubled over the past hour. Telemetry shows:

• GPU memory reservation is constant at 95%.
• Prefix cache hit rate has increased from 20% to 55%.
• The average prompt length of incoming requests has increased from 256 tokens to 2048 tokens.
• The chunk budget is currently set to max_batched_tokens = 2048.

Explain why high memory reservation does not prove memory exhaustion, identify the likely hypothesis for the P99 ITL increase, list two specific measurements required to test it, and outline a controlled mitigation.

Solution

• 1. Memory reservation context: In engines with preallocated memory pools, 95% allocation reflects reserved pool capacity, not active sequence memory exhaustion. It does not indicate thrashing on its own.
• 2. Hypothesis: With average prompt lengths rising to 2048 tokens and max_batched_tokens = 2048, unchunked or large-chunk prefill kernels execute up to 2048 prompt tokens in a single step, monopolizing GPU compute and delaying concurrent decodes.
• 3. Testing the hypothesis: (a) Measure step execution times broken down by prefill versus pure decode steps to identify prefill kernel stalls. (b) Inspect the disjoint block pool to distinguish active_blocks from reclaimable_blocks and free_blocks.
• 4. Controlled mitigation: Under matched arrival rate and context length, reduce chunk size (e.g., test 512 tokens) and evaluate p95/p99 ITL distributions. Note that telemetry correlations support hypotheses but do not constitute definitive proof without controlled validation.

Exercise 4: Disaggregated KV transfer pipeline design

A model with 40 layers, 8 KV heads, head dimension 128, and FP16 precision is deployed in a disaggregated architecture.

1. Calculate the per-token KV footprint in KiB.
2. For a 4096-token prompt, calculate the total KV cache payload size in GiB.
3. Calculate the ideal payload transfer time over a 200 Gb/s network link.
4. Explain how chunked prefill can be integrated with network transmission to hide transfer latency.

Solution

• 1. Per-token footprint: 2 (K and V) * 40 layers * 8 heads * 128 dim * 2 bytes = 163,840 bytes = 160 KiB per token.
• 2. Total payload size: For 4096 tokens, 4096 * 163,840 bytes = 671,088,640 bytes = 640 MiB = 0.625 GiB.
• 3. Ideal network transfer time: At 200 Gb/s (25 * 10^9 bytes/sec), 671,088,640 / 25,000,000,000 = 0.0268435456 seconds = 26.8435 ms (ideal nominal payload transfer excluding protocol/bus overhead).
• 4. Pipelined streaming: By prefilling the prompt in chunks (e.g., 512 tokens), the prefill worker can transmit KV blocks across the network as soon as each chunk finishes, overlapping transmission with the prefill computation of subsequent chunks.

---

9. Summary of core concepts

Dimension	Monolithic Prefill	Chunked Prefill	Prefix Caching	Disaggregated Serving
Primary Goal	Process a complete prompt in one iteration	Mitigate decode stalls; bound query token budget	Avoid redundant prompt computation	Decouple compute-heavy prefill from memory-heavy decode
Scheduling Metric	All prompt tokens in 1 step	Capped by max_batched_tokens - decodes	Hash / radix matching against block table	Prefill requests routed to dedicated prefill workers
Memory Behavior	Rapid allocation of full sequence KV	Incremental allocation per chunk	Zero allocation for matched prefix blocks	Transmits KV tensors across network to decode workers
Latency Impact	Can delay co-scheduled decodes	Can reduce prefill interference; adds scheduling and traffic costs	Skips reusable work; TTFT benefit depends on other costs	Separates these GPU workloads; transfer and shared-resource delays remain
Core Invariant	Standard causal masking	Same causal dependencies; validate floating-point tolerance	Composite identity matching (model, config, adapters, tokens)	KV must arrive before dependent decode computation

10. Sources and implementation scope

• Sarathi-Serve, OSDI 2024: chunked-prefill scheduling and its workload-dependent tradeoffs.
• SGLang / RadixAttention: radix-tree prefix reuse and cache management; §3.
• vLLM prefix-cache design: chained block hashes, full-block reuse, reference counts and eviction.
• vLLM V1 optimization guide: decode-first scheduling and remaining query-token budgets.
• DistServe: disaggregated prefill/decode and placement/transfer tradeoffs.

The vLLM stable documentation is a moving reference, accessed 2026-11-03. Pin the engine release/backend when applying its policies. Numerical examples here are analytical teaching calculations, not measured TTFT, ITL or transfer benchmarks.

Related lessons

• Inference Optimisation & AI Infrastructure · Schedule Requests and Manage KV MemoryContinuous Batching: Iteration-Level Scheduling30 min
• Inference Optimisation & AI Infrastructure · Schedule Requests and Manage KV MemoryPagedAttention: Virtual Memory for the KV Cache35 min
• Inference Optimisation & AI Infrastructure · Measure and Explain Inference PerformanceFlashAttention and GPU Data Movement16 min