Latency: inter-token latency, speculative decoding and tail latency

Three interview problems about time. How do you make each token arrive sooner without serving fewer users? When does guessing ahead with a draft model pay off, and when does it cost you? And when the slowest 1% of requests take ten times longer than the typical one, where do you look first?

Source: Vishal Singh's post listing 25 inference-engineering interview problems · saved in sources/09-vishal-inference-25.md

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings and the "Why it matters for robotics" box, and come back for the rest later.

Problem 9 · Cut inter-token latency without tanking throughput

What the interviewer is testing: whether you know why decode is slow (memory bandwidth, not arithmetic), that latency and throughput are coupled through batch size, and which levers move one without wrecking the other.

The concepts

During decode, each step produces one token for every sequence in the batch. To do it, the GPU streams all the weights once (shared by the batch) plus each sequence's own KV cache. At normal batch sizes the arithmetic is tiny compared with the bytes moved, so the step time is close to a bandwidth floor:

t_step  ≈  (W + B × KV_seq) / BW  +  t_overhead

W       = weight bytes            (params × bytes per weight)
KV_seq  = KV-cache bytes per sequence (see Module 08, Stage 08)
B       = sequences in the batch
BW      = HBM bandwidth (bytes/s)

ITL (per user)        = t_step
throughput (tokens/s) = B / t_step

Two things follow. First, raising B grows throughput almost linearly while the weights dominate, but each step also gets longer because every sequence adds its own cache. Second, anything else that runs in the same step adds to everyone's ITL. The biggest offender is a prefill: processing a new prompt is compute-bound, and a long one can take longer than a hundred decode steps.

Worked answer with real numbers

Assumptions: a Llama-3-8B-shaped model (32 layers, 8 KV heads, head dim 128, about 8.0B parameters), BF16 weights (≈16 GB) and BF16 KV cache (128 KiB = 131,072 B per token), an average of 2,048 tokens of context per sequence (≈268 MB of cache each). GPU: H100 SXM, 80 GB, 3.35 TB/s and 989 TFLOPS dense BF16 (NVIDIA's table lists 1,979 TFLOPS with sparsity; dense is half). The bandwidth floor ignores kernel overhead and assumes 100% of peak bandwidth, so real numbers will be slower.

B = 1:    (16 GB +   1 × 0.268 GB) / 3.35 TB/s =  4.86 ms  → 206 tok/s per user,    206 tok/s total
B = 32:   (16 GB +  32 × 0.268 GB) / 3.35 TB/s =  7.34 ms  → 136 tok/s per user,  4,360 tok/s total
B = 128:  (16 GB + 128 × 0.268 GB) / 3.35 TB/s = 15.03 ms  →  67 tok/s per user,  8,515 tok/s total
B = 256:  needs 16 + 68.7 = 84.7 GB of weights + cache  → does not fit in 80 GB

Compute check at B = 128: 2 × 8.0e9 × 128 = 2.0 TFLOP per step
                          ÷ 989 TFLOPS ≈ 2.1 ms  < 15 ms, so still bandwidth-bound

Going from B = 32 to B = 128 doubles throughput and doubles ITL. That is the core trade-off. Now the prefill problem. Prefill costs about 2 × params FLOPs per prompt token. Assume 50% of dense peak is achieved (an assumption; measure yours):

4,096-token prompt in one step:  2 × 8.0e9 × 4,096 / (0.5 × 989e12) ≈ 133 ms
512-token chunk per step:        2 × 8.0e9 ×   512 / (0.5 × 989e12) ≈  17 ms

With B = 32 decoding: a normal step is 7.3 ms.
  unchunked prefill step → ~140 ms  (a visible stall for 32 users)
  chunked (512) steps    → ~24 ms each, for 8 steps

So the answer has a clear shape: first remove interference (chunked prefill, Sarathi-Serve style, or move prefill to separate GPUs), then shrink bytes per step (FP8 weights and FP8 KV), then cut fixed overhead (CUDA graphs, fused kernels), and only then reach for speculative decoding or more GPUs per replica. With FP8 weights (8 GB) and FP8 KV (134 MB per sequence), the floor at B = 128 becomes (8 + 17.2) GB / 3.35 TB/s = 7.5 ms. That is the same ITL as BF16 at B = 32, with four times the users.

Trade-offs

Common mistakes

• Treating latency and throughput as independent. They share one dial, the batch, so always quote both.
• Reporting average ITL. Users feel the spikes, so track ITL at p99 and the maximum gap per stream.
• Assuming a bigger GPU fixes ITL. Only bandwidth per token and interference move it; FLOPs barely matter for decode.
• Forgetting that memory caps the batch: in the example, B = 256 simply doesn't fit.

Problem 10 · Speculative decoding: when it helps and when it hurts

What the interviewer is testing: whether you can derive the expected speedup from the acceptance rate, and whether you know it is a latency tool that can lose throughput when the GPU is already busy.

The concepts

A cheap draft proposes k tokens. The target model scores all k in one forward pass, accepts a prefix of them using a modified rejection-sampling rule, and adds one token of its own (either the correction at the first rejection, or a bonus token if all were accepted). The rule keeps the output distribution exactly the same as the target's. Leviathan, Kalman and Matias (2023) and Chen et al. (2023) derived this independently.

If each drafted token is accepted with probability α, independently, the expected tokens produced per verify round are:

E[tokens per round] = 1 + α + α² + … + α^k = (1 − α^(k+1)) / (1 − α)

cost per round (in units of one target forward pass):
    k × c        drafting (c = draft cost per token ÷ target cost)
  + 1            the verify pass
  + k × v        extra verify cost per drafted token (≈ 0 when memory-bound,
                 grows when the GPU is compute-bound at large batch)

speedup = E[tokens per round] / (k·c + 1 + k·v)

With v = 0 this is the improvement factor in the Leviathan paper. The key assumption is v ≈ 0: verifying k + 1 tokens costs about the same as producing one, because the pass is bound by reading weights, not by arithmetic. That holds at small batch. At large batch the GPU is closer to compute-bound, every rejected token is wasted arithmetic, and v grows.

Worked answer with real numbers

α = 0.8, k = 4, c = 0.05, v = 0:
  E = (1 − 0.8⁵) / 0.2 = (1 − 0.328) / 0.2 = 3.36 tokens per round
  cost = 4 × 0.05 + 1 = 1.20
  speedup = 3.36 / 1.20 = 2.80×

Same, but α = 0.6:    E = 2.31,  speedup = 2.31 / 1.20 = 1.92×
α = 0.5, k = 8, c = 0.1:   E = 2.00,  cost = 1.8,  speedup = 1.11×
α = 0.3, k = 4, c = 0.1:   E = 1.43,  cost = 1.4,  speedup = 1.02×  (break-even)

α = 0.8, k = 4, c = 0.05, but at high load v = 0.25:
  cost = 0.2 + 1 + 1.0 = 2.2   → speedup = 1.53×
Best k at α = 0.8, c = 0.05, v = 0:  k = 8, speedup ≈ 3.09×

The published numbers fit this picture. Leviathan et al. report 2–3× on T5-XXL; Chen et al. report 2–2.5× on Chinchilla 70B. EAGLE-3 (Li et al., 2025), which drafts from the target's own hidden features, reports up to 6.5× in its best setting but a 1.38× throughput gain at batch 64 in SGLang. The gain shrinks as the batch grows, exactly as the v term predicts. Module 05 covers training an EAGLE-3 draft directly on acceptance rate.

When it helps, when it hurts

Common mistakes

• Saying it changes model quality. With the proper acceptance rule the output distribution is identical; only speed changes. (Lossy "accept if top-1 matches" shortcuts are a different, approximate thing.)
• Quoting a speedup without a batch size. The same setup can give 2.8× at batch 1 and nothing at batch 128.
• Forgetting the draft's own KV cache and weights in the memory budget.
• Picking k by gut. The best k depends on α and c; too long a draft wastes work on tokens that will be rejected.

Problem 17 · Your p99 latency is 10× your p50. Diagnose it

What the interviewer is testing: a calm, data-first method. Can you decompose latency, separate "slow because the request is big" from "slow because the system is unhealthy", and know the usual suspects in LLM serving?

The concepts

End-to-end latency for one request breaks into parts, and the first job is to log them per request:

E2E = t_network + t_queue + t_tokenise + TTFT_compute + (N_out − 1) × TPOT + t_stalls

TTFT_compute grows with prompt length (prefill)
(N_out − 1) × TPOT grows with output length
t_queue grows sharply as utilisation ρ → 1
t_stalls = preemption / recompute when the KV cache runs out, GC, retries

Three effects create a heavy tail even in a healthy system:

• Length variance. E2E is proportional to output tokens. If most answers are 100 tokens and 1% are 2,000, then at 20 ms TPOT the p50 is about 2 s and the p99 about 40 s. That is a 20× ratio with nothing broken. Always normalise: look at TTFT and TPOT percentiles, not only E2E.
• Queueing. In the textbook M/M/1 queue the time in system is exponential with rate μ − λ. Its p99/p50 ratio is ln(100)/ln(2) ≈ 6.6 at any load, and its mean scales as 1/(1 − ρ). Going from 50% to 90% utilisation makes the mean wait five times longer. Real LLM servers are not M/M/1, but the lesson holds: near saturation, small bursts create huge waits.
• Fan-out. Dean and Barroso's "The Tail at Scale": if a request touches 100 servers and each is slow 1% of the time, 1 − 0.99¹⁰⁰ = 63% of requests hit at least one slow server. Agents that call the model many times per task inherit this.

Worked answer: a diagnosis plan

Assume a chat service, p50 E2E 2 s, p99 20 s. Work in this order:

1. Split by phase. Plot p50 and p99 for queue time, TTFT and TPOT separately. If TPOT p99 is flat and only E2E is bad, it is mostly output length. Report per-token latency and set a max-tokens policy.
2. Slice by request shape. Bucket by prompt length and output length. If TTFT p99 tracks long prompts, and short requests that arrived alongside them also have high TTFT, it is head-of-line blocking from prefill. Fix: chunked prefill, a per-step token budget, a separate queue or pool for long prompts.
3. Check queueing. Plot queue time against concurrency and utilisation. If queue time explodes at traffic peaks, you're over ρ ≈ 0.8. Fix: admission control, more replicas, autoscaling with warm capacity (Page 09).
4. Check KV-cache pressure. Look for preemptions and recomputes in the engine metrics (vLLM logs and exposes these). If they spike with p99, the cache is full. Fix: lower max concurrency, FP8 KV, prefix caching, more memory per replica.
5. Slice by replica and node. One slow GPU, a thermally throttled node, a noisy neighbour or a bad NIC shows up as a per-host outlier. Fix: drain it; add hedged or retried requests for idempotent calls.
6. Check the CPU side. Tokenisation, detokenisation, JSON grammar constraints, Python GC pauses and the HTTP layer all live outside the GPU and show up as gaps in a timeline trace.

A numeric sanity check for step 2: with the Problem 9 numbers, a 4,096-token prompt prefilled in one step costs about 133 ms. If 30 such prompts arrive in a burst on one replica, a short chat queued behind them waits about 4 s before its own prefill even starts.

Trade-offs

Common mistakes

• Jumping to fixes before splitting the latency into parts.
• Using averages. The mean hides the tail; p99 needs enough samples (at least a few thousand requests) to be stable.
• Treating p99/p50 = 10 as broken by itself. With mixed output lengths it can be normal; per-token metrics tell you.
• Forgetting client-side and network time, which the server's metrics never see.

Practise it

(a) Speculative decoding simulator (laptop, 20 minutes). Confirm the formula by Monte Carlo, then add a batch-dependent verify cost:

import random

def sim(a, k, c, v=0.0, rounds=200_000, seed=0):
    rng = random.Random(seed)
    toks = 0
    for _ in range(rounds):
        n = 0
        while n < k and rng.random() < a:
            n += 1
        toks += n + 1                      # accepted drafts + 1 target token
    return toks / rounds, toks / rounds / (k * c + 1 + k * v)

for a in (0.3, 0.6, 0.8):
    print(a, sim(a, 4, 0.05))              # expect E ≈ (1 - a**5) / (1 - a)

(b) Measure the latency/throughput dial with vLLM (one 16–24 GB GPU or Colab). Serve a small model such as Qwen2.5-1.5B-Instruct. Run vllm bench serve with random prompts (512 in, 256 out) at several request rates, and record TTFT, TPOT and ITL at p50 and p99, plus output tokens/s. Plot ITL against throughput: that curve is Problem 9.

• Repeat with a few 8K-token prompts mixed in, with and without chunked prefill, and compare short-request TTFT at p99.
• Enable n-gram speculative decoding (--speculative-config; check your vLLM version's docs for the exact keys) and compare ITL at request rates of 1 and at saturation. Note where the speedup disappears.
• Log per-request prompt and output lengths, then reproduce Problem 17's diagnosis: compute p99/p50 for E2E and for TPOT and explain the difference.

In this course

• Module 05 · Serving: speculative decoding with an EAGLE-3 draft trained on acceptance rate, and fleet scheduling.
• Module 08 · Inference-aware design: the KV-cache maths behind KV_seq, and design choices that make speculation cheap.
• Module 04 · Latency is a safety number: measuring wait-after-speech on a device.
• Module 01 · Decision-model evals: setting thresholds and choosing metrics, which applies to latency SLOs too.
• Page 03 · Batching and scheduling and Page 04 · Prefix caching and disaggregation: the scheduling fixes referenced above.

Why it matters for robotics

Self-check

Resources

• Fast Inference from Transformers via Speculative Decoding (Leviathan, Kalman, Matias, ICML 2023)
• Accelerating Large Language Model Decoding with Speculative Sampling (Chen et al., 2023)
• EAGLE-3: Scaling up Inference Acceleration of LLMs via Training-Time Test (Li et al., 2025)
• Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads (Cai et al., 2024)
• Sarathi-Serve: Taming Throughput-Latency Tradeoff in LLM Inference (Agrawal et al., 2024): chunked prefill and stall-free batching
• Orca: A Distributed Serving System for Transformer-Based Generative Models (Yu et al., OSDI 2022): iteration-level scheduling
• DistServe (Zhong et al., 2024) and Splitwise (Patel et al., 2024): prefill/decode disaggregation
• Efficient Memory Management for LLM Serving with PagedAttention (Kwon et al., 2023)
• The Tail at Scale (Dean and Barroso, CACM 2013)
• Docs: vLLM speculative decoding · vLLM bench serve · SGLang · TensorRT-LLM · Nsight Systems user guide
• Specs: NVIDIA H100 · NVIDIA Jetson Orin