Module 05 · Chapter 20

Chunked Prefill and Long-Context Limits

Split long prompt processing into scheduled pieces and examine why memory, computation, and useful recall become harder as context grows.

Intermediate15 min readUpdated Nov 8, 2026

Learning objectives

Explain how monolithic long-prompt prefills cause severe inter-token latency spikes for active decodes
Trace the chunked prefill scheduling loop that piggybacks prefill chunks with ongoing decode steps
Quantify the quadratic computation wall where prefill attention FLOPs overtake model parameter FLOPs
Analyze the escalating scaling limits of 100K+ context across memory, computation, and recall quality
Select and validate a complete KV cache architecture to support 64 concurrent 8K users in 48 GiB VRAM

Before you start

Use Less Memory: Quantization and Offloading (/llm-foundations/kv-precision-and-offloading/)

In the previous lesson, you learned how quantization (FP16 → FP8 → INT8 → INT4) reduces the bytes stored per cached token, and how tiered offloading moves older cache blocks from GPU HBM to CPU DDR5 RAM or NVMe SSD when VRAM fills up. Those techniques decide how much space each token uses and where it lives.

This lesson tackles a different problem: what happens when the prompt itself is long — and the processing of that long prompt interferes with other users who are already generating tokens.

We will cover:

The Prefill Interference Dilemma (Decode Starvation): Why a single 12,000-token prompt can freeze 20 active users for over a second.
Chunked Prefill (Sarathi-Serve / Interleaved Scheduling): The scheduling loop that breaks the prompt into fixed-size chunks and piggybacks each chunk with one decode step from every active request.
The Three Walls of Long-Context Scaling (100K+ tokens): Linear memory growth, quadratic attention compute, and attention diffusion that degrades retrieval quality.
Part V Capstone Exit Task: Choose a complete KV cache strategy (model, quantization, prefix caching) that supports 64 concurrent 8K-context streams in 48 GiB VRAM.

1. The Prefill Interference Dilemma (Decode Starvation)

1.1 Two Phases, One GPU

Recall from Part IV that LLM inference has two distinct phases:

Phase	What Happens	Compute Pattern	Typical Duration
Prefill	Process the entire prompt in parallel, build initial KV cache	Compute-bound (high arithmetic intensity)	`P` tokens at once
Decode	Generate one token at a time, reading from KV cache	Memory-bandwidth-bound (low arithmetic intensity)	1 token per step

When a server runs multiple requests concurrently, it interleaves these phases. The GPU executes one “scheduling step” after another. In each step, it can either:

Run prefill for a waiting request, or
Run decode for active requests that are generating tokens

1.2 Monolithic Prefill: The Problem

Imagine a server with 20 active decode streams (20 users currently generating text). Each decode step takes 20 ms (a typical inter-token latency for a 7B model on a modern GPU).

Now a new request arrives with a 12,000-token prompt (P = 12,000).

If the scheduler runs the entire prefill at once (monolithic prefill):

The GPU devotes 100% of its compute to that one prefill.
The 20 active decode streams stop completely — they get zero GPU time.
Prefill time for 12,000 tokens on a 7B model at 150 TFLOPS ≈ 1,120 ms (see Exercise 1).
During those 1,120 ms, the 20 users experience zero progress.
When prefill finishes, their next tokens finally run — but their inter-token latency has spiked from 20 ms to 1,140 ms (a 57× jitter).

This is decode starvation. The long prompt “starves” the decode streams of GPU time.

1.3 Why This Matters in Production

Tail latency SLOs break: A P99 latency budget of 100 ms is violated by a single long prompt.
User experience degrades: Users see the generation “freeze” for over a second.
Throughput drops: The GPU sits idle on memory-bound decode work while it could be doing compute-bound prefill work in parallel.

2. Chunked Prefill: Interleaved Scheduling (Sarathi-Serve)

2.1 Core Idea: Break the Prompt, Interleave with Decode

Chunked prefill (introduced in Sarathi-Serve, Agrawal et al., 2023) solves decode starvation by splitting the long prompt into fixed-size chunks and scheduling one chunk per iteration alongside all active decode steps.

Chunk size C = 1,000 tokens (example)
Prompt length P = 12,000 tokens → 12 chunks
Active decode streams B_decode = 20

Scheduling loop (each iteration):

Iteration 1: [Prefill chunk 1 (1000 tokens)] + [Decode step for 20 streams]
Iteration 2: [Prefill chunk 2 (1000 tokens)] + [Decode step for 20 streams]
...
Iteration 12: [Prefill chunk 12 (1000 tokens)] + [Decode step for 20 streams]

Total tokens processed per iteration: C + B_decode = 1,000 + 20 = 1,020 tokens

2.2 Why This Works

Property	Monolithic Prefill	Chunked Prefill
Decode progress during prefill	Zero (starved)	One token per iteration (steady)
ITL for active users	Spikes to prefill duration	Capped at ~chunk time + decode time
GPU utilization	Alternates: 100% prefill → 100% decode	Blended: compute-bound prefill + memory-bound decode in same step
Prefill latency (TTFT)	Single long block	Slightly longer total (overhead), but predictable

2.3 Choosing the Chunk Size `C`

C is a tuning parameter. Typical values: 512 – 2048 tokens.

Smaller C → lower ITL jitter, more scheduling overhead, better decode fairness.
Larger C → fewer iterations, less overhead, but longer pauses for decode streams.

The Sarathi-Serve paper recommends C = 1024 or 2048 for 7B–70B models on A100/H100. The optimal C balances:

Chunk prefill time ≈ (2 × C × N) / GPU_FLOPS
Decode step time  ≈ KV cache read bandwidth / GPU_memory_bandwidth
Target: chunk prefill time ≈ 2–3× decode step time

2.4 Implementation Note: KV Cache Growth During Chunked Prefill

During chunked prefill, the KV cache grows incrementally. After chunk i, the cache holds i × C tokens. The next chunk’s attention sees all previous chunks’ keys and values (causal attention within the prompt). This is exactly the same as monolithic prefill — just split across iterations.

No quality loss. The mathematical result is identical. Only the scheduling changes.

3. The Three Walls of Long-Context Scaling (100K+ Tokens)

Even with chunked prefill, quantization, and offloading, pushing context to 100K, 1M, or 10M tokens hits three fundamental walls.

3.1 Wall 1: Linear Memory Growth — O(T)

KV cache memory scales linearly with context length T:

bytes = 2 × L × H_kv × d_head × T × b

Where:

L = number of layers
H_kv = number of KV heads (GQA: H_kv < H_q; MHA: H_kv = H_q)
d_head = head dimension
b = bytes per element (FP16=2, FP8/INT8=1, INT4=0.5)

Example: Llama 3 8B (GQA: L=32, H_kv=8, d_head=128)

Context T	FP16 (b=2)	FP8/INT8 (b=1)	INT4 (b=0.5)
4,096 (4K)	0.5 GiB	0.25 GiB	0.125 GiB
32,768 (32K)	4.0 GiB	2.0 GiB	1.0 GiB
131,072 (128K)	16.0 GiB	8.0 GiB	4.0 GiB
1,048,576 (1M)	128 GiB	64 GiB	32 GiB

At 1M tokens, even with GQA and INT4, a single sequence needs 32 GiB — exceeding the VRAM of most single GPUs (H100: 80 GiB, but weights + activations + workspace consume ~40 GiB).

Solutions: Multi-GPU tensor parallelism, CPU/NVMe offloading (Lesson 19), prefix caching (Lesson 18), sliding-window attention (Lesson 18).

3.2 Wall 2: Quadratic Computation — O(T²) Attention FLOPs

In prefill, attention computation scales quadratically with sequence length because every token attends to every prior token.

Attention FLOPs (prefill, causal):

Attention_FLOPs ≈ 4 × L × T² × d_head

Projection + FFN FLOPs (scales linearly):

Projection_FF_FLOPs ≈ 2 × T × N

Where N = total model parameters.

Ratio: Attention / (Attention + Projections)

Let’s compute for Llama 3 8B (N ≈ 8×10⁹, L=32, d_head=128):

Context T	Projection+FFN FLOPs	Attention FLOPs	Attention % of Total
4,096 (4K)	57.3 TFLOPs	8.8 TFLOPs	13.3%
32,768 (32K)	458.8 TFLOPs	563.2 TFLOPs	55.1%
131,072 (128K)	1.84 PFLOPs	9.01 PFLOPs	83.1%
1,048,576 (1M)	14.68 PFLOPs	576.46 PFLOPs	97.5%

At 128K context, attention is 83% of all prefill compute. At 1M, it is 97.5%.

This is the quadratic attention wall. Beyond ~32K, prefill becomes almost entirely attention-bound. FlashAttention (Dao et al., 2022/2023) reduces memory traffic but not arithmetic operations — the FLOPs remain quadratic.

Solutions: Sparse attention, linear attention (RWKV, Mamba), attention approximations, or accepting the cost for high-value workloads.

3.3 Wall 3: Attention Diffusion & “Lost in the Middle”

As T grows, the softmax denominator sums over millions of exponentials:

softmax(q·k_j / √d) = exp(q·k_j / √d) / Σ_{i=1..T} exp(q·k_i / √d)

When T = 1,000,000, the denominator has 1 million terms. Unless the query has extremely sharp peaks (large dot products with a few keys), the softmax weights become diffuse — nearly uniform across the context.

Consequences:

Needle-in-a-haystack retrieval fails: The model cannot reliably attend to a specific fact buried at position 500,000.
“Lost in the Middle” phenomenon (Liu et al., 2023): Performance degrades when relevant information is in the middle of a long context, vs. the beginning or end.
Positional encoding limits: Standard RoPE (Rotary Position Embedding) uses a fixed base frequency (θ = 10,000). Beyond the training context (e.g., 4K or 8K), the rotation angles wrap and lose discriminative power.

Solutions:

YaRN (Yet another RoPE extensioN): Scale the RoPE frequency base by a factor (e.g., 0.1× or 0.01×) to extend effective context.
Long-context continued training: Train on 32K–1M sequences with scaled RoPE.
Retrieval-augmented generation (RAG): Don’t stuff everything into context; retrieve relevant chunks.
Specialized architectures: Mamba/SSM, RWKV, or sliding-window attention (local attention only).

4. Three Hands-On Exercises with Step-by-Step Checked Solutions

Notation used below:

1 KiB = 1,024 bytes

1 MiB = 1,024 KiB

1 GiB = 1,024 MiB

FLOPs = floating-point operations (total count, a scalar)

FLOPS = floating-point operations per second (rate, a throughput)

N = model parameter count

L = number of layers

H_kv = number of KV heads

d_head = head dimension

T = sequence length (context)

P = prompt length

C = chunk size (tokens per prefill chunk)

B_decode = number of active decode streams

Exercise 1: Decode Jitter & Latency Spike Without Chunking

Scenario: A server runs 16 active decode streams on a 7B model (N = 7 × 10⁹ parameters) at 150 TFLOPS sustained compute throughput. Steady-state inter-token latency (ITL) = 20 ms per token per stream.

A new request arrives with a monolithic prompt of P = 12,000 tokens.

Calculate:

Step 1: Prefill FLOPs for the monolithic prompt

Prefill FLOPs ≈ 2 × P × N
             = 2 × 12,000 × 7 × 10⁹
             = 168 × 10¹²
             = 168 TFLOPs

Step 2: Monolithic prefill time

Prefill_time = Prefill_FLOPs / GPU_FLOPS
             = 168 TFLOPs / 150 TFLOPS
             = 1.12 s
             = 1,120 ms

Step 3: Decode stream ITL spike

During the 1,120 ms prefill, zero decode steps occur for the 16 active streams.

ITL_spike = steady_state_ITL + prefill_time
          = 20 ms + 1,120 ms
          = 1,140 ms

Jitter factor: 1,140 / 20 = 57×

Step 4: With Chunked Prefill (C = 1,000 tokens)

Number of chunks = P / C = 12,000 / 1,000 = 12 chunks
FLOPs per chunk = 2 × C × N = 2 × 1,000 × 7 × 10⁹ = 14 TFLOPs
Chunk prefill time = 14 TFLOPs / 150 TFLOPS = 93.3 ms
Each iteration also runs 16 decode steps (memory-bound, ~1–2 ms overhead)
Effective step time ≈ 93.3 ms + 2 ms ≈ 95 ms

ITL with chunking: Capped at ~95–110 ms per step (predictable, no 1-second freeze).

Conclusion: Chunked prefill transforms a catastrophic 57× latency spike into a bounded, predictable ~5× overhead.

Exercise 2: The Quadratic Attention Compute Wall

Model: 7B parameters (N = 7 × 10⁹), L = 32, d_model = 4,096, d_head = 128 (since d_model = H_q × d_head, and H_q = 32 for MHA).

Formulas:

Projection + FFN FLOPs (linear in T): 2 × T × N = 14 × 10⁹ × T
Attention FLOPs (quadratic in T): 4 × L × T² × d_head = 4 × 32 × T² × 128 = 16,384 × T²

Wait — let’s derive carefully:

**Standard Attention FLOPs Derivation:**

For causal attention during prefill across $H$ heads (each head of dimension $d_{head} = d_{model} / H$):

1. **Query-Key matrix product ($Q K^T$):** Across all $H$ heads, multiplying $[T, d_{head}] \times [d_{head}, T]$ yields $H \times (2 \times T^2 \times d_{head}) = 2 \times T^2 \times d_{model}$ FLOPs.
2. **Attention-Value product ($A \cdot V$):** Multiplying $[T, T] \times [T, d_{head}]$ across all $H$ heads yields $H \times (2 \times T^2 \times d_{head}) = 2 \times T^2 \times d_{model}$ FLOPs.
3. **Softmax:** Adds $\approx 3 \times H \times T^2$ FLOPs (negligible relative to matrix multiplication).

Summing per layer:

FLOPs_attention_layer ≈ 4 × T² × d_model

Across all $L = 32$ layers (with $d_{model} = 4,096$):

Total Attention FLOPs = 4 × L × T² × d_model = 4 × 32 × 4,096 × T² = 524,288 × T²

**Projection and FFN FLOPs (linear in $T$):**

FLOPs_linear = 2 × T × N = 2 × T × (7 × 10⁹) = 14 × 10⁹ × T

---

#### Calculate for 3 sequence lengths:

| T                  | Projection+FFN FLOPs                             | Attention FLOPs                                        | Total FLOPs   | Attention % |
| ------------------ | ------------------------------------------------ | ------------------------------------------------------ | ------------- | ----------- |
| **4,096 (4K)**     | `14e9 × 4096 = 57.34e12` = **57.34 TFLOPs**      | `524,288 × 4096² = 8.80e12` = **8.80 TFLOPs**          | 66.14 TFLOPs  | **13.3%**   |
| **131,072 (128K)** | `14e9 × 131,072 = 1.835e15` = **1.835 PFLOPs**   | `524,288 × 131,072² = 9.007e15` = **9.007 PFLOPs**     | 10.842 PFLOPs | **83.1%**   |
| **1,048,576 (1M)** | `14e9 × 1,048,576 = 14.68e15` = **14.68 PFLOPs** | `524,288 × 1,048,576² = 576.46e15` = **576.46 PFLOPs** | 591.14 PFLOPs | **97.5%**   |

> **Verification:**
>
> - At 4K: 8.80 / (57.34 + 8.80) = 8.80 / 66.14 = 13.3% ✓
> - At 128K: 9.007 / (1.835 + 9.007) = 9.007 / 10.842 = 83.1% ✓
> - At 1M: 576.46 / (14.68 + 576.46) = 576.46 / 591.14 = 97.5% ✓

> **Conclusion:** Attention compute shifts from **13%** at 4K to **97.5%** at 1M. The quadratic wall is real and dominant.

---

### Exercise 3: Part V Capstone — Module Exit Task

**Enterprise Deployment Scenario:**

- **GPU:** H100 with **48 GiB VRAM dedicated strictly to KV cache pool**
  (`48 × 2³⁰ = 51,539,607,552 bytes`)
- **SLA Requirement:** Support at least **64 concurrent requests** with context length up to **8,192 (8K) tokens**
- **Task:** Compare two model designs and select a complete KV cache strategy (model + quantization + prefix caching) that meets the SLA.

---

#### Model 1: Llama 2 7B (MHA)

- `L = 32`
- `H_kv = 32` (MHA: all heads have separate K/V)
- `d_head = 128`
- FP16 (`b = 2`)

**Per-token KV cache size:**

bytes_per_token = 2 × L × H_kv × d_head × b = 2 × 32 × 32 × 128 × 2 = 524,288 bytes = 512 KiB

**Single 8K request:**

8,192 × 512 KiB = 4,194,304 KiB = 4,096 MiB = 4.0 GiB

**64 concurrent streams:**

64 × 4.0 GiB = 256.0 GiB

**Verdict:** ❌ **FAILS** — exceeds 48 GiB budget by **>5×**.

---

#### Model 2: Llama 3 8B (GQA)

- `L = 32`
- `H_kv = 8` (GQA: 32 query heads, 8 KV heads shared 4:1)
- `d_head = 128`

**Per-token KV cache size (FP16, b=2):**

bytes_per_token = 2 × 32 × 8 × 128 × 2 = 131,072 bytes = 128 KiB

**Strategy A: FP16 (no quantization)**

Single 8K request = 8,192 × 128 KiB = 1,048,576 KiB = 1,024 MiB = 1.0 GiB 64 streams = 64 × 1.0 GiB = 64.0 GiB

**Verdict:** ❌ **FAILS** — exceeds 48 GiB budget (64 > 48).

---

**Strategy B: FP8 Quantization (b = 1 byte, E4M3 format)**

bytes_per_token_FP8 = 2 × 32 × 8 × 128 × 1 = 65,536 bytes = 64 KiB

Single 8K request = 8,192 × 64 KiB = 524,288 KiB = 512 MiB = 0.5 GiB 64 streams = 64 × 0.5 GiB = 32.0 GiB

**Verdict:** ✅ **SUCCEEDS** — fits in 48 GiB with **16 GiB headroom** (33% margin).

---

**Strategy C: FP8 + Prefix Caching (shared 2K system prompt)**

Assume all 64 requests share a **2,048-token system prompt** (common in enterprise: instructions, few-shot examples, schema).

- Shared prefix stored **once**: `2,048 × 64 KiB = 131,072 KiB = 128 MiB = 0.125 GiB`
- Unique suffix per request: `8,192 - 2,048 = 6,144 tokens`
- Suffix memory per request: `6,144 × 64 KiB = 393,216 KiB = 384 MiB = 0.375 GiB`
- 64 unique suffixes: `64 × 0.375 GiB = 24.0 GiB`
- **Total cache memory = 0.125 GiB (shared) + 24.0 GiB (unique) = 24.125 GiB**

**Verdict:** ✅ **SUCCEEDS with massive headroom** — uses only **24.125 / 48 = 50.3%** of the KV cache pool.

**Implied capacity:** At this efficiency, the same 48 GiB pool could support up to:

48 GiB / (24.125 GiB / 64) ≈ 127 concurrent streams

---

### Architectural Recommendation

| Decision               | Choice                                  | Rationale                                                                      |
| ---------------------- | --------------------------------------- | ------------------------------------------------------------------------------ |
| **Model**              | **Llama 3 8B (GQA)**                    | 4× fewer KV heads than Llama 2 7B MHA → 4× less cache per token                |
| **Quantization**       | **FP8 (E4M3)**                          | 2× compression vs FP16; `<0.05%` quality loss; native H100 Tensor Core support |
| **Prefix Caching**     | **Enabled (2K shared prompt)**          | Eliminates duplicate storage of common system prompt; 50% further reduction    |
| **Resulting Capacity** | **127 concurrent 8K streams** in 48 GiB | Exceeds 64-stream SLA by 2× with safety margin                                 |
| **Headroom**           | **23.875 GiB free**                     | Absorbs burst traffic, longer contexts, or activation workspace                |

> **This is the complete, validated KV cache architecture for the Part V Capstone Exit Task.**

---

## 5. Summary Reference Table: Part V Curriculum (KV Cache Foundations)

| Lesson | Title                                             | Core Concept                                 | Memory Impact                          | Latency Impact                       | Key Formula / Technique                                       |
| ------ | ------------------------------------------------- | -------------------------------------------- | -------------------------------------- | ------------------------------------ | ------------------------------------------------------------- |
| 15     | Why Cache Keys and Values?                        | Causal attention enables reuse               | Baseline (no cache = recompute)        | Decode: O(1) per token vs O(T)       | KV cache = stored K, V per layer                              |
| 16     | Calculate KV Cache Memory by Hand                 | Derive byte formula                          | `2 × L × H_kv × d_head × T × b`        | —                                    | Per-token bytes × context × batch                             |
| 17     | Allocate the Cache: Blocks, Waste, PagedAttention | Block allocation, fragmentation              | PagedAttention: near-zero waste        | Block table lookup                   | Logical → physical block mapping                              |
| 18     | Reuse, Evict, or Limit Earlier Context            | Prefix caching, eviction, sliding window     | Prefix cache: shared blocks            | Eviction: reclaims VRAM              | Sliding window: fixed `W` tokens                              |
| 19     | Use Less Memory: Quantization and Offloading      | FP8/INT8/INT4 + CPU/NVMe tiers               | 2–4× (quantization) + 10–50× (offload) | PCIe/NVMe transfer must be pipelined | Per-token symmetric quantization                              |
| **20** | **Chunked Prefill and Long-Context Limits**       | **Interleaved scheduling + 3 scaling walls** | **O(T) memory wall**                   | **Chunked prefill caps ITL jitter**  | **C + B_decode per step; O(T²) attention; YaRN/RoPE scaling** |

---

## 6. Primary Source Citations

| #   | Citation                                                                                                            | Link                                                 |
| --- | ------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------- |
| 1   | **Agrawal et al. (2023)**, _SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills_       | [arXiv:2308.16369](https://arxiv.org/abs/2308.16369) |
| 2   | **Dao et al. (2022)**, _FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness_                | [arXiv:2205.14135](https://arxiv.org/abs/2205.14135) |
| 3   | **Dao et al. (2023)**, _FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning_           | [arXiv:2307.08691](https://arxiv.org/abs/2307.08691) |
| 4   | **Liu et al. (2023)**, _Lost in the Middle: How Language Models Use Long Contexts_                                  | [arXiv:2307.03172](https://arxiv.org/abs/2307.03172) |
| 5   | **Peng et al. (2023)**, _YaRN: Efficient Context Window Extension of Large Language Models_                         | [arXiv:2309.00071](https://arxiv.org/abs/2309.00071) |
| 6   | **Rozière et al. (2023)**, _Code Llama: Open Foundation Models for Code_ (Long-context RoPE scaling)                | [arXiv:2308.12950](https://arxiv.org/abs/2308.12950) |
| 7   | **Sheng et al. (2023)**, _FlexGen: High-throughput Generative Inference of Large Language Models with a Single GPU_ | [arXiv:2303.04665](https://arxiv.org/abs/2303.04665) |

---

## 7. What Comes Next

- **Next lesson (Part VI opener):** [From CPU Instructions to GPU Threads](/llm-foundations/cpu-gpu-and-cuda-basics/) — Now that we understand KV cache memory, scheduling, and long-context limits, we descend to the hardware level: how a GPU actually executes the matrix multiplications, attention kernels, and memory transfers we've been analyzing.
- **Previous lesson:** [Use Less Memory: Quantization and Offloading](/llm-foundations/kv-precision-and-offloading/)
- **Track overview:** [Start Here: LLM Foundations](/tracks/llm-foundations/)

---

> **Part V Complete.** You now have a full toolkit for KV cache architecture: memory calculation, block allocation, prefix reuse, eviction policies, quantization, tiered offloading, chunked prefill scheduling, and long-context scaling analysis. The capstone exit task validates that you can compose these techniques into a production-ready design under real constraints.