Where does head-of-line blocking come from under FCFS, when does shortest-job-first help, and how does it work without job lengths?

TL;DR: Under FCFS with chunked prefill, a long prompt takes the whole token budget for several steps, so short prompts behind it wait. On an H100 serving an 8B model, a 32K-token prompt ahead of ten 500-token prompts gives the short ones 1.80 s TTFT; ordering by prompt length cuts them to 0.27 s and delays the long one by 10%, mean TTFT 1.78 s to 0.41 s. Prompt length is known on arrival, so prefill SJF is exact; output length is not, so decode ordering uses prediction or least-attained-service.

How to approach it

Split the job length into its two parts before answering: prompt tokens, known the moment the request arrives, and output tokens, unknown until the end-of-sequence token. Then ask which resource the queue is waiting on. If it is the prefill token budget, the known part is enough. If it is KV capacity or decode slots, the unknown part decides it. Ask about the prompt-length spread too, since SJF only matters when lengths vary by an order of magnitude.

A strong answer

Continuous batching removed one kind of head-of-line blocking, waiting for the longest sequence in a static batch to finish. It left two others. A long prompt occupies the token budget for $\lceil L / \text{budget} \rceil$ steps under FCFS, and a long-running decode holds KV blocks that a waiting request needs.

Measure the first one. A step-level simulation of chunked prefill on Llama 3.1 8B, budget 8,192 tokens, H100 at 50% MFU, attention FLOPs included:

N, F = 8.03e9, 0.5 * 989e12        # 8B params; 50% MFU on an H100
A = 4 * 32 * 32 * 128              # attention FLOPs per (query, key) pair

def ttft(prompts, budget=8192):
    """Chunked prefill, one step at a time, in list order. Returns TTFT (s)."""
    left, done, t, out = list(prompts), [0] * len(prompts), 0.0, {}
    while len(out) < len(prompts):
        b, flops = budget, 0.0
        for i, n in enumerate(left):
            if n == 0 or b == 0:
                continue
            c = min(n, b)
            flops += 2 * N * c + A * (c * done[i] + c * c / 2)
            left[i], done[i], b = n - c, done[i] + c, b - c
        t += max(4.79e-3, flops / F)           # never faster than the weight read
        out.update({i: t for i, n in enumerate(left) if n == 0 and i not in out})
    return [out[i] for i in range(len(prompts))]

fcfs = ttft([32768] + [500] * 10)
sjf = ttft([500] * 10 + [32768])
print(f"mean TTFT {sum(fcfs)/11:.2f} s -> {sum(sjf)/11:.2f} s")   # 1.78 s -> 0.41 s

The long prompt fills four full steps (32,768 = 4 x 8,192), so nothing else gets budget until the fifth. Moving it to the back costs it one step, 0.16 s. This is the classic SJF result: it minimizes mean waiting time, and the cost lands on the long job, which barely notices in relative terms.

That part needs no prediction. The scheduler can order the waiting queue by remaining prefill tokens, or, closer to what engines ship, cap the per-step share any one prompt can take. vLLM v0.31 exposes this as long_prefill_token_threshold (off by default). With a cap of 2,048, short prompts get budget in the first step even under FCFS order.

The unknown half is output length. It matters when KV or slots are full and the scheduler must pick which waiting request to admit, or which running one to preempt. Three ways to proceed:

• Predict a length bucket or, better, a rank. Ranking only needs relative order, an easier target for a small model reading the prompt than absolute length.
• Use least-attained-service: priority falls as a request generates more tokens, so short jobs finish before the scheduler has spent much on long ones. A multilevel feedback queue does this without any prediction, at the cost of some preemptions of long generations.
• Use the client's max_tokens as an upper bound. Cheap, but it is a ceiling, not an estimate.

Every SJF variant can starve long jobs under sustained load. Add aging: order by predicted cost minus a weight times time waited, or guarantee a slot after a maximum wait.

The reversal: with uniform prompt lengths, SJF on prefill buys nothing and only adds starvation risk; keep FCFS. With very long outputs and short prompts (reasoning traces), the prefill fix is irrelevant and the decision moves entirely to KV admission, where prediction quality decides whether SJF beats FCFS at all.

What interviewers probe next

"Why not just shrink the budget?" A smaller budget shortens every step but does not reorder anything: the long prompt still goes first, and below the roofline ridge each chunk re-reads all weights for less work.

"Your length predictor is wrong 30% of the time." SJF degrades gracefully with a noisy ranking, since the mean-wait gain comes from getting most pairs in the right order; feed back actual lengths and fall back to least-attained-service when confidence is low.

"Does disaggregated prefill remove the problem?" It moves it. The prefill pool still has a queue, and ordering it by prompt length is the same decision.

How it's scored

Weak: says continuous batching already solved head-of-line blocking, or proposes SJF on total length without noting the output half is unknown.

Hire: separates prompt length from output length, computes the TTFT gain of prompt-ordered admission, and mentions starvation.

Strong Hire: quantifies blocking in steps of the token budget, names the per-request prefill cap as the shipping mechanism, offers prediction-free least-attained-service for decode, and adds aging.

Common mistakes

• Treating SJF as a fairness improvement. It lowers mean latency and makes the tail worse for long jobs.
• Scheduling by max_tokens, which most clients set to the model maximum, so every job looks equally long.
• Forgetting that the running decodes consume budget too, so the prefill room per step is the budget minus the batch.
• Measuring the gain on a closed-loop benchmark where requests never queue.