How Much Slower Is TTFT When Context Length Doubles?

If Context Length Doubles, How Much Slower Is TTFT? Measuring Prefill Complexity in Practice

Everyone knows that longer prompts produce the first token later. The question is: how much later? 2×? 4×? More? Even after Flash Attention, this question has lacked a clean answer — and the reason is simple: people conflate FLOP complexity with IO complexity.

Why Prefill Is Sensitive to Sequence Length

In Transformer self-attention, the bottleneck is the QK^T matrix multiplication. For batch size 1, sequence length n, hidden dim d, and L layers, total Prefill FLOPs break into two terms:

Total FLOPs = L × (24nd² + 4n²d)

The first term (24nd²) comes from the linear layers. Q, K, V projections at 2nd² each, output projection at 2nd², and FFN at 16nd² sum to 24nd² — linear in n. The second term (4n²d) comes from the attention matrix multiplications (QK^T and AV, each 2n²d) and is quadratic in n.

For d=4096, L=32 (a 7B-class MHA model), the per-range FLOPs look like this:

Below 4K, the linear term dominates overwhelmingly. The attention term starts to matter at 8K, and the two terms cross over beyond 32K. At 128K, 84% of total FLOPs come from attention.

The crossover point where the two terms are equal — solving 4n²d = 24nd² — is n = 6d. For d=4096, that's n ≈ 24,576, around 24K tokens.

Why Superlinearity Persists Even After Flash Attention

The problem Flash Attention 2 (Dao, 2023) solved is HBM I/O complexity. Standard attention writes and then re-reads the n×n score matrix to HBM, giving O(n²) I/O. Flash Attention eliminates those writes using block-wise tiling and online softmax, reducing I/O to O(n).

Arithmetic FLOPs are unchanged. The forward pass still performs the same O(n²d) computation — it just reads and writes HBM less.

The right tool for determining whether Prefill is compute-bound or memory-bound is roofline analysis. Start with arithmetic intensity (AI).

Flash Attention AI for one layer:

AI = FLOPs / Bytes = O(n²d) / O(nd) = O(n)

Q, K, V, and O are read/written from HBM as nd-sized blocks, so memory access is O(nd) and FLOPs are O(n²d) — AI scales with n.

Plugging in GPU specs and roofline thresholds:

Since AI = n, any n > 153 is compute-bound on A100. Even a 256-token Prefill is already compute-bound. Linear layers share the same structure: weight size 2d² bytes, FLOPs 2nd² → AI = n.

After Flash Attention, Prefill is almost always compute-bound, and TTFT scales proportionally to total FLOPs divided by GPU peak FLOP/s. So in the regime where FLOPs grow as O(n²), TTFT grows at the same rate.

The TTFT scaling ratio when n doubles:

ratio(n→2n) = (48nd² + 16n²d) / (24nd² + 4n²d)
             = (48d + 16n) / (24d + 4n)

• n ≪ 24K (linear-dominated): 48d/24d = 2×
• n ≈ 24K (crossover): 144d/48d = 3×
• n ≫ 24K (attention-dominated): 16n/4n → approaches 4×

Empirical Measurements: TTFT vs. Context Length

Here's whether theory matches practice. Measured TTFT for Llama-3-8B on A100 SXM4 with FlashAttention-2, batch size 1:

The 1K→10K range (slope ≈ 1.0) is linear-term-dominated, so TTFT scales nearly proportionally to token count. The slope climbs in the 10K→50K range and reaches 1.5–1.7 around 100K.

Why doesn't the slope reach 2.0 even at 128K? Llama-3-8B uses GQA (8 KV heads), which puts the crossover at ~21K tokens. At 128K — more than 6× past the crossover — the slope is still converging toward the theoretical limit of 2.0. The reason convergence is incomplete is that the linear term still accounts for 16% of total FLOPs at 128K.

A common misconception in practice is that "TTFT scales linearly with length." That holds up to about 10K, but beyond 32K it's a completely different game.

How Model Size and Head Structure Shift the Crossover

GQA models have smaller K and V projection matrices. Comparing Llama-3-8B (GQA, 8 KV heads) against Llama-2-7B (MHA, 32 KV heads):

• MHA linear term: 24nd²
• GQA linear term: 21nd² (K and V projections shrink to d_kv=d/4, reducing the combined K+V projection FLOPs from 4nd² to nd² — a savings of 3nd²)

The attention FLOPs (4n²d) are identical for both. GQA trims the linear term by 12.5%, but it doesn't touch the quadratic term.

Llama-3-70B has d=8192, pushing the crossover to ~168K tokens. Even running 128K context on a 70B model keeps you in the linear-dominated regime, where the TTFT log-log slope can be close to 1. By contrast, 7B–8B models already show a steep slope starting around 32K.

The practical benefit of GQA is reducing KV cache memory during decoding, not mitigating the superlinear TTFT growth during Prefill.

Why One Long Request in a Batch Ruins p99

In a continuous batching setup, when a long Prefill request starts, decoding for every other request in the same batch is blocked until that forward pass completes. If a 10K-token Prefill takes 832ms, any 100-token request batched alongside it won't receive its first token until those 832ms are up. A single request poisons the TTFT distribution of the entire batch.

Chunked Prefill eliminates this bubble. It splits large Prefills into chunks of max_num_batched_tokens tokens and processes each chunk alongside Decode requests at every step. vLLM's default is 512 tokens — the official documentation notes this is empirically optimal for minimizing ITL (inter-token latency) on A100.

# Enable Chunked Prefill in vLLM
llm = LLM(
    model="meta-llama/Llama-3-8B",
    enable_chunked_prefill=True,
    max_num_batched_tokens=512,  # default; lower for ITL, higher for TTFT
)

The tradeoff is clear. Smaller chunk sizes improve ITL for short requests, but a 10K prompt gets split into 20 steps, increasing its TTFT. Larger chunk sizes lower TTFT for long requests but bring the Prefill bubble back.

Defining a single TTFT SLA (e.g., "under 500ms") will always be violated in services with a wide context-length distribution. Two practical approaches work in production. First, separate SLA tiers per input-length bucket — e.g., 200ms for ≤4K, 1s for 4K–16K, 5s for >16K. Second, derive chunk_size from the SLA: if the p99 TTFT target for short requests is T_max, then one chunk must complete within T_max, giving an upper bound of chunk_size ≤ T_max × GPU peak FLOP/s / (FLOPs per token).

It's also worth noting that length-based routing — directing requests over 16K exclusively to a dedicated endpoint — is a practical option. Beyond that threshold, a single Prefill carries a sharply elevated risk of blocking an entire batch, and separating it from general-purpose batching is what makes p99 guarantees achievable.