Why Long Prompts Slow Generation: Estimating Prefill and Decode Cost

Long documents hurt LLM serving in two different ways. They require a large one-time computation before the first output token, and they increase the memory footprint that every later token must use. The first effect is called prefill; the second is exposed during decode. Treating both as one “tokens per second” number is the fastest way to mis-size a server.

This article builds a calculation model for an H100 deployment of Llama 3.1 70B. The numbers below are examples derived from explicit assumptions, not benchmark results. They are intended to help you estimate capacity, choose a measurement plan, and identify which variables must be replaced with measurements from your own stack.

The useful mental model: two phases, two bottlenecks

An autoregressive language model processes a request in two broad phases:

1. Prefill: process the input sequence and construct the attention state needed for generation.
2. Decode: generate output tokens one at a time, reusing the stored attention state.

The stored attention state is the KV cache. It contains key and value vectors for the prompt and for tokens generated so far. A long prompt therefore creates both more initial work and more state to read during generation.

The latency visible to a user can be approximated as:

time_to_first_token ≈ queue_time + prefill_time + scheduling_overhead

total_request_time ≈ queue_time + prefill_time
                    + output_tokens / decode_throughput

This is intentionally a service-level model. It omits tokenizer time, network time, sampling, logging, batching transitions, and other overheads unless you add them explicitly. That makes it useful for first-order sizing, but insufficient as a substitute for a benchmark.

A concrete case: one 32,000-token document

Consider a request with these inputs:

The hardware line is a deployment assumption. It does not assert that every Llama 3.1 70B serving system needs eight H100s. Weight quantization, tensor parallelism, memory utilization, runtime implementation, and context length all affect the actual placement.

Estimating prefill compute

A common first-order estimate for transformer inference is approximately 2P floating-point operations per token for the dense feed-forward and projection work. Under that approximation:

F_prefill ≈ 2 × P × L
           ≈ 2 × 70,000,000,000 × 32,000
           ≈ 4.48 × 10^15 FLOPs

The result is 4.48 petaFLOPs of model compute for the example prompt. This is a model estimate, not a measurement. It excludes or simplifies attention terms, routing, padding, fused-kernel effects, tensor-parallel communication, and runtime overhead.

To turn compute into time, use an effective—not advertised peak—throughput:

prefill_time ≈ F_prefill / effective_prefill_FLOPs_per_second

For an illustrative sensitivity calculation, assume the complete eight-GPU deployment sustains an effective 0.5 PFLOP/s on this workload:

prefill_time ≈ 4.48 PFLOPs / 0.5 PFLOP/s
              ≈ 8.96 seconds

The 8.96-second result is not a verified H100 benchmark. It simply shows how to use the equation. If your measured effective throughput is 1.0 PFLOP/s, the same estimate becomes 4.48 seconds. If it is 0.25 PFLOP/s, it becomes 17.92 seconds.

This linear approximation explains why doubling the input from 32,000 to 64,000 tokens approximately doubles the first-pass model work. In practice, the slope can change when the runtime changes kernels, runs out of memory bandwidth, pads batches, or communicates more frequently across GPUs.

Why decode behaves differently

During decode, the model produces one new token at a time. Each step still performs model-wide work, but the computation has a different shape: the new token is small while the attention operation must consult the existing KV cache.

A simplified compute estimate for O generated tokens is:

F_decode_model ≈ 2 × P × O

For 512 output tokens:

F_decode_model ≈ 2 × 70,000,000,000 × 512
                ≈ 7.168 × 10^13 FLOPs

That is much less model FLOP volume than the 32,000-token prefill. However, decode is commonly constrained by memory traffic, synchronization, and the need to perform many sequential steps. A high prefill throughput number therefore does not predict decode throughput.

Use a separately measured decode rate:

decode_time ≈ output_tokens / measured_decode_tokens_per_second

As a purely illustrative example, if the deployment sustains 160 output tokens per second for the selected batch and sampling configuration:

decode_time ≈ 512 / 160
             ≈ 3.2 seconds

The total model-side time for this example would then be approximately 8.96 + 3.2 = 12.16 seconds before queueing and other overheads. Neither 0.5 PFLOP/s nor 160 tokens/s should be presented as a measured result without running the corresponding workload.

Estimating KV-cache memory

The KV cache is often the hidden capacity limit for long documents. A useful per-token estimate is:

KV_bytes_per_token
  = 2 × layers × KV_heads × head_dim × bytes_per_element

The first factor of two accounts for keys and values. For an example Llama 3.1 70B configuration, use 80 layers, 8 KV heads, a head dimension of 128, and BF16 values at 2 bytes each:

KV_bytes_per_token
  = 2 × 80 × 8 × 128 × 2
  = 327,680 bytes
  ≈ 320 KiB

For 32,000 input tokens:

prompt_KV
  ≈ 32,000 × 327,680
  ≈ 10,485,760,000 bytes
  ≈ 9.77 GiB

Generated tokens add to the same cache. With 512 output tokens, the total sequence length becomes 32,512 tokens and the estimated KV cache becomes approximately 9.93 GiB, before allocator metadata, padding, fragmentation, replicated state, and runtime-specific layout.

Check the actual model configuration before using this equation. A quantized weight format does not automatically mean that the KV cache uses the same format. Some runtimes support FP8 or other KV-cache formats; those reduce memory per token but may change quality, kernel behavior, or supported features.

Throughput is a queueing problem, not only a FLOP problem

A server usually handles multiple requests. A long prefill can occupy the GPU while short requests wait, even if the long request eventually completes efficiently. Conversely, a decode-heavy batch can leave large matrix-multiplication units underused while still consuming memory bandwidth and cache capacity.

For a rough capacity model, define:

request_service_time
  ≈ prefill_time(L) + output_tokens / decode_rate(batch, KV_size)

If requests arrive at rate λ and the average service time is S, the offered utilization is approximately:

ρ ≈ λ × S

This is only a first-order queueing signal. Real LLM servers use continuous batching, admission control, token budgets, and sometimes priority scheduling. Once utilization approaches saturation, a modest increase in document length can cause a disproportionately large increase in queue time.

Measure at least these distributions rather than only averages:

• time to first token;
• inter-token latency;
• total request latency;
• prefill tokens per second;
• decode tokens per second;
• queue time;
• peak and resident KV-cache memory;
• batch size and active sequence count.

Chunked prefill: same work, different interference

Chunked prefill divides a long prompt into smaller scheduling units. With a chunk size of 2,048 tokens, the 32,000-token prompt becomes 16 chunks, with the final chunk containing 1,280 tokens.

chunks = ceil(32,000 / 2,048) = 16

If the implementation performs the same operations, the total model work is approximately unchanged:

total_chunked_prefill_compute
  ≈ Σ compute(chunk_i)
  ≈ compute(32,000 tokens)

Chunking changes scheduling. The runtime can insert decode work between prefill chunks, reducing the time a long prompt monopolizes the device. This can improve fairness and tail latency for already-running generations. It can also increase overhead through more scheduling decisions, less favorable kernel shapes, more synchronization, or extra padding.

A simple planning model is:

chunked_prefill_time
  ≈ prefill_time
  + number_of_chunks × per_chunk_overhead
  + overlap_penalty_or_benefit

Do not assume chunking makes a single request faster. Its primary purpose is usually to control interference between long prefills and active decode. The correct test compares both single-request latency and mixed-workload tail latency.

Disaggregated serving: moving prefill and decode apart

Disaggregated serving assigns prefill and decode to separate worker pools. Prefill workers process long inputs; decode workers maintain the active generation workload. The design can protect decode latency from long document ingestion, but it introduces a transfer boundary.

If the full KV cache is transferred between workers, the network payload is approximately:

transfer_bytes
  ≈ sequence_tokens × KV_bytes_per_token

For the 32,000-token prompt in BF16:

transfer_bytes
  ≈ 32,000 × 327,680
  ≈ 9.77 GiB

A theoretical transfer-time lower bound for a link with usable bandwidth B is:

transfer_time ≥ transfer_bytes / B

For an illustrative 400 GB/s usable path:

transfer_time ≥ 10.49 GB / 400 GB/s
               ≥ 26 milliseconds

This is an optimistic lower bound. It excludes serialization, protocol framing, contention, copies, synchronization, topology effects, and any conversion or compression. A system with a much slower network path can make KV movement a material part of first-token latency.

Disaggregation is most attractive when the operational value of isolation exceeds the cost of moving state. It may improve decode predictability while leaving total compute unchanged. It can also reduce locality: a cache that would have remained on one worker may now need to cross a device or host boundary.

A reproducible estimation worksheet

Replace the example values with your model and measurements. Keep assumptions in a separate configuration file or notebook so that a capacity review can distinguish measured values from estimates.

model_params = 70_000_000_000
input_tokens = 32_000
output_tokens = 512

layers = 80
kv_heads = 8
head_dim = 128
kv_bytes = 2

effective_prefill_flops = 0.5e15       # assumption, replace with measurement
decode_tokens_per_second = 160         # assumption, replace with measurement
usable_transfer_bytes_per_second = 400e9

prefill_flops = 2 * model_params * input_tokens
prefill_seconds = prefill_flops / effective_prefill_flops

decode_seconds = output_tokens / decode_tokens_per_second

kv_bytes_per_token = 2 * layers * kv_heads * head_dim * kv_bytes
kv_prompt_bytes = input_tokens * kv_bytes_per_token
transfer_seconds = kv_prompt_bytes / usable_transfer_bytes_per_second

print("prefill seconds:", prefill_seconds)
print("decode seconds:", decode_seconds)
print("prompt KV GiB:", kv_prompt_bytes / 2**30)
print("KV transfer lower bound:", transfer_seconds)

The script produces an estimate, not a benchmark. For a benchmark, capture the same fields from the serving runtime and compare them against the worksheet.

Measurement procedure

A useful experiment varies one dimension at a time:

1. Choose fixed model weights, precision, GPU count, runtime version, tensor-parallel configuration, sampling settings, and maximum output length.
2. Test input lengths such as 1,024, 4,096, 8,192, 16,384, and 32,000 tokens.
3. Run a single-request prefill test and record time to first token.
4. Run a decode-only or short-prompt test and record output tokens per second.
5. Repeat under a mixed workload containing short prompts, long prompts, and active generations.
6. Repeat with chunked prefill enabled and record the chunk size.
7. If using disaggregation, record serialized KV size, transfer time, and the link or transport used.
8. Report median and tail values, preferably p50, p95, and p99.

Keep prompt content semantically similar when comparing lengths. Token count matters more directly than character count, and different token distributions can alter padding, compression, and kernel behavior.

A minimal command pattern might look like this, but the flags are runtime-specific and must be adapted to the server you actually use:

python benchmark.py \
  --model /models/llama-3.1-70b \
  --input-tokens 1024,4096,8192,16384,32000 \
  --output-tokens 512 \
  --concurrency 1,4,16 \
  --record-ttft \
  --record-itl \
  --record-throughput \
  --record-kv-memory

Treat the command as a test-plan template, not a verified command for a particular runtime.

Common failure cases

Using advertised peak FLOPs as observed throughput

Peak hardware FLOPs describe a ceiling under a specific operation mix. Long-context inference may be limited by memory traffic, communication, synchronization, or kernel efficiency. Use measured effective throughput for planning.

Comparing prefill tokens per second with decode tokens per second

These are different workloads. Prefill often uses larger matrix operations and parallelizes across the input sequence. Decode is sequential and repeatedly reads model and KV-cache state. Keep the metrics separate.

Ignoring the prompt already in the cache

Prefix caching can avoid recomputing a shared prefix, but it consumes memory and depends on exact prefix identity and runtime policy. A cached result is not free: it still occupies cache capacity and may require lookup or transfer.

Assuming chunked prefill reduces total compute

Chunking primarily changes scheduling. It may improve mixed-workload behavior while adding a small amount of overhead or increasing single-request latency.

Estimating KV memory from parameter count

KV size depends on layers, KV heads, head dimension, sequence length, and cache precision—not directly on the number of model parameters. Read these values from the model configuration.

Measuring only average latency

Long prompts can create queueing effects that averages hide. A stable p50 with a worsening p99 is a capacity warning, especially for interactive systems.

Limitations of this model

The equations intentionally simplify several important details:

• attention cost is not modeled exactly as a function of sequence length;
• mixture-of-experts routing is not applicable to every model and is not included here;
• tensor-parallel and pipeline-parallel communication are omitted;
• batching, padding, sequence packing, and scheduler policy are represented only indirectly;
• GPU memory capacity does not equal usable KV-cache capacity;
• network transfer estimates use usable bandwidth, not link-rate marketing numbers;
• tokenization, HTTP, serialization, sampling, logging, and safety filters are excluded;
• the illustrative throughput values are assumptions, not measurements.

Use the model to choose experiments and identify bottlenecks. Use measured traces to make production commitments.

Practical conclusions

For a 32,000-token document, the first-order prefill work scales with input length and can dominate time to first token. Decode adds a separate sequential cost whose throughput must be measured independently. The same long prompt also creates roughly 9.77 GiB of BF16 KV state under the example Llama 3.1 70B configuration, before runtime overheads.

Start with three numbers: measured prefill throughput, measured decode throughput, and measured KV-cache bytes per token. Then test the scheduler under the concurrency and prompt-length distribution that resembles production. Chunked prefill is a scheduling control; disaggregated serving is an architectural trade-off that exchanges interference for KV-transfer cost.

For related implementation patterns, continue with the guides and use the glossary for the serving terms used here.