The head of line effect breaks latency even when GPUs are available

A long request rarely looks dangerous in a test environment. It is simply slower to answer on its own. In production, it can delay dozens of short requests that arrive after it, even when the GPU is busy and average latency has barely changed. This is the head of line effect: work at the front of the queue determines how long the work behind it must wait.

The problem is especially unpleasant in an LLM service because of prefill. The model must process the entire input context before producing the first output token. A request containing several pages of a contract, an agent's tool history, and a large JSON object can consume significantly more compute than a short user question. If all requests enter one FIFO stream, a short request waits for someone else's context rather than its own work.

Neither autoscaling nor high average throughput fixes this by itself. First understand the shape of the workload, then separate the work classes, and only after that choose scheduler parameters.

The head of line effect starts before the first token

In LLM inference, the head of line effect most often appears as worse TTFT for short requests queued behind a long prefill. TTFT, or time to first token, measures the path from request acceptance to delivery of the first token. It includes queue time, input processing, batch admission, and a small part of the network path.

Do not confuse this metric with total generation time. An interactive chat user will usually tolerate a long answer if they see it begin within an acceptable time. By contrast, an API that returns a complete response after processing a document may not need strict TTFT, but it does need a predictable completion time. One latency number cannot describe both modes.

A request has two distinct phases:

• Prefill runs the input tokens through the model and creates the KV cache. Input processing is parallel, so this phase usually uses GPU compute well.
• Decode adds output tokens one at a time. Here, active batch size, available KV-cache memory, and time per token, TPOT, matter more.

The authors of DistServe explicitly separate these SLOs: TTFT applies to prefill, while TPOT applies to decode. The value of their work is not that every service urgently needs separate GPUs. It is that it breaks the harmful habit of treating both modes as one workload. Running prefill and decode together creates interference, while one shared concurrency limit forces you to choose which of the two metrics to damage.

The queue may be outside the service, inside the API gateway, or already inside the inference engine. The user cannot tell the difference. They only see that the short question «what is the payment status?» sometimes takes several seconds to start answering because a task to «extract the details from 180 pages of scans» arrived first.

Average prompt length hides the culprit

The average number of input tokens is almost useless for queue management. It answers a convenient reporting question, but not the scheduler's question: how long will this particular request hold the prefill budget before allowing the next work class through?

Measure the input_tokens distribution for each endpoint, tenant, and task type. At a minimum, collect p50, p90, p95, p99, and the maximum over a selected window. Then overlay TTFT for the same buckets. Usually, one of two patterns becomes visible:

1. Short requests are fast on their own, but their p95 TTFT rises in sync with the appearance of long inputs.
2. Long requests make up a small share of traffic but consume a disproportionate share of prefill time.

The second situation often appears after an “innocent” product change. The team adds the entire chat, search results, several documents, and the tool schema to an agent. From the application's perspective, this is one request. For the inference server, it is a different class of work.

Do not use HTTP body size as a substitute for prompt length. Base64 attachments, whitespace, JSON structure, and tokenizer behavior make bytes a poor predictor. Classify the request after tokenization, or estimate token count before sending it with the tokenizer that matches the model. If one route serves different models, store the estimate separately for each model family.

A useful table can be built in an analytics warehouse using one-minute windows:

class        requests  p50 input   p95 input   p95 queue   p95 TTFT   cancellations
interactive  12,400    420         1,100       180 ms      720 ms     3.1%
document     380       18,600      47,900      4,900 ms    8,200 ms   0.4%
agent        1,900     3,100       12,400      1,600 ms    3,100 ms   8.7%

Numbers in this form matter more than overall p95 API latency. They show what is happening to different kinds of work. If interactive and document requests sit in one queue, the first row is often harmed by the workload in the second, not by its own load.

Agent requests create another unpleasant case. Their input may be moderate on the first call, but after several tool calls, the history and tool results expand the context. If you log only the endpoint, you will see an “unstable chat.” If you log the turn number, history size, and tool-output size, you will see a predictable cause.

An idle GPU does not mean a free queue

High GPU utilization does not prove that the service is working well. The GPU may be busy with a long prefill while urgent requests accumulate outside. Low utilization does not justify a simple FIFO queue either: the engine may be limited by KV cache, a small number of sequences, or frequent evictions, while monitoring looks only at compute utilization.

To investigate the head of line effect, add five timestamps to the request trace:

{
  "request_id": "r_7f31",
  "class": "interactive_short",
  "input_tokens": 684,
  "max_output_tokens": 320,
  "accepted_at": "2026-07-23T10:14:01.184Z",
  "prefill_started_at": "2026-07-23T10:14:02.016Z",
  "first_token_at": "2026-07-23T10:14:02.441Z",
  "completed_at": "2026-07-23T10:14:05.920Z",
  "finish_reason": "stop"
}

These fields produce three numbers that must not be mixed:

• queue_ms = prefill_started_at - accepted_at;
• prefill_to_first_token_ms = first_token_at - prefill_started_at;
• generation_ms = completed_at - first_token_at.

If queue_ms grows, investigate admission rules, queue order, competing classes, and insufficient capacity. If the second number grows while the queue remains stable, check input length, model, context window, prefix cache, and batching parameters. If the problem is in the third number, look at decode, output limits, sampling, and KV-cache pressure.

This distinction is regularly blurred. The team sees high TTFT and starts changing to a faster model, even though the short request never entered prefill for two seconds. Or it adds workers even though decode is already filled with long responses and another prefill will only worsen memory evictions.

Continuous batching is necessary, but it does not promise fairness. Hugging Face documentation describes it as rescheduling the batch at every generation step so that newly freed slots can immediately accept new requests. This improves GPU utilization, but admission policy and the amount of work one request may contribute per iteration still determine the latency tail.

One large prefill can block the system in a perfectly ordinary way

Imagine one inference pool and a FIFO queue. At 09:00:00, a document summarization task containing 42,000 input tokens arrives. Eighty milliseconds later, six short requests of 300 to 800 tokens arrive: an operator chat, address verification, an internal search, and a user response.

The scheduler starts the large task first. While it processes the input, the short requests receive no first token. If the engine mixes prefill and decode, it may continue producing tokens for already active generations, but new short requests still wait for the point at which they are admitted to the schedule. With a high stream of such documents, the queue quickly stops recovering.

The worst case is when the product limits only max_output_tokens but not input size. The team believes that responses are short and the workload is under control. Then a client sends a CRM export, a long conversation, or uncleaned HTML. The model has to generate 100 tokens in response, but first it must read tens of thousands.

The check for this failure is simple. Take the time series for p95 TTFT in the short class and mark requests where input_tokens is above your interactive-traffic p99. If TTFT peaks appear in the same windows, FIFO is creating a head of line effect. Do not demand perfect correlation: active decode, available memory, and concurrency also affect the result. But if short requests suffer during the minutes when long inputs arrive, that is already enough reason to change the route.

The problem is not solved by the simple rule “shortest first.” That rule can push documents back indefinitely under constant chat traffic. It also encourages clients to understate their length estimates. You need an explicit class policy, request age in the queue, and a limited budget for background work.

Separate queues according to the user promise

A good queue design starts with what the user expects, not with the endpoint name. Chat, synchronous form validation, and an agent working in an operator interface need a fast first token. Overnight classification, archive summarization, and document-queue processing can tolerate delay if the system reports task status honestly.

For most teams, three classes are enough:

• interactive_short: short context, streaming response, strict TTFT;
• interactive_long: an agent or analytical request with a large input, while the user is still waiting in the interface;
• batch_long: documents and bulk operations without a requirement for an immediate start.

Do not define a class by model name. The same model may serve both chat and batch processing, while two models with different speeds may support the same user promise. Routing should consider estimated input tokens, allowed output, streaming, tenant priority, and deadline.

Example gateway-level rules might look like this:

classes:
  interactive_short:
    when:
      streaming: true
      input_tokens_lte: 4000
      max_output_tokens_lte: 1200
    ttft_target_ms: 1200
    concurrency_share: 0.60

  interactive_long:
    when:
      streaming: true
      input_tokens_lte: 24000
    ttft_target_ms: 5000
    concurrency_share: 0.25

  batch_long:
    when:
      streaming: false
    admission: rate_limited
    concurrency_share: 0.15
    max_wait_ms: 180000

This is not the configuration of a particular engine. It is a contract that your gateway must turn into separate queues, pools, or admission limits. The most common mistake here is giving the background class 15% “at all times.” At night, this leaves capacity unused, while during the day it may still give documents too much. Use spare-capacity borrowing: batch work can take unused resources but must release them when an interactive queue appears.

Fairness between clients is a separate concern. One tenant with a thousand long documents should not fill the entire batch_long class and deprive others even of background processing. Per-key concurrent-request limits, a token budget per interval, and a weighted fair queue are suitable options. Request-count limits without token accounting provide poor protection against one enormous prompt.

AI Router can be the policy point for teams that need one OpenAI-compatible endpoint: classification before routing is more useful than trying to fix every delay inside one model server. Separate key-level rate limits and request audits help verify which class and client create the tail, but the team still has to define the class rules.

Chunked prefill reduces blocking, but it has a cost

Chunked prefill splits a long input into pieces and gives the scheduler a chance to insert other work between them. Instead of processing 32,000 tokens as one long block, the engine can process several fragments while continuing to decode already started requests and admitting new short prefills.

The vLLM documentation states this directly: chunked prefill lets large prefills run in smaller pieces and mix with decode. A request that does not fit within the batched-token limit can be split automatically. This is useful protection against severe blocking, but it is not a reason to choose a very small chunk without measuring.

A small fragment gives the scheduler more switching points. At the same time, it increases the number of scheduling decisions and can reduce execution efficiency. A large fragment provides good compute density but again makes short requests hostage to long work. Sarathi-Serve describes the same trade-off: its chunked prefill creates a schedule where new requests can be added without stopping active decode, but fragment size remains a trade-off between latency and throughput.

Evaluate changes to chunk size using an SLO table, not average throughput:

Do not draw conclusions from one run with a fixed number of requests. Reproduce the real mix: short streaming requests, several long documents, the distribution of max_output_tokens, client cancellations, and bursty arrivals. Otherwise, you will optimize a neat synthetic batch in which the head of line effect does not exist.

Separate pools are needed when SLOs constantly conflict

If chunked prefill and class-based queues cannot keep TTFT within target, separate prefill and decode, or at least separate the interactive pool from the batch pool. This costs more to operate, but it makes the conflict explicit: you allocate capacity for fast response starts and capacity for long input processing instead of hoping that one batch setting will solve everything.

DistServe proposes full prefill and decode disaggregation across different GPUs specifically to eliminate their mutual interference. This is a strong architectural decision, not a setting to copy without a reason. It adds state transfer, separate scaling, and more failure points.

Start with a less radical design:

1. Give the interactive queue its own concurrency limit and token budget.
2. Run batch work only on spare capacity or on a separate replica.
3. Set a strict input-token limit for the synchronous API.
4. Move documents above the limit into an asynchronous task with status updates and a result when ready.
5. Cancel pending requests when the client disconnects or the deadline expires.

A separate pool is justified when you see the conflict not once a week but as a property of normal traffic: interactive p95 violates its target specifically during batch load, and batch work cannot be moved to another time. For a bank, telecom operator, or service with a large document stream, this is a normal situation, not a sign of bad code.

Context limits are often more useful than another GPU

The cheapest way to remove much of the head of line effect is to stop uncontrolled context from entering the interactive path. Many applications send the model far more than is needed for the current answer: the full conversation, every search result, duplicate instructions, unfiltered tables, and complete tool responses.

Make the input budget part of the API contract. For example, an interface agent receives up to 12,000 input tokens. If retrieval returns more, the ranker must select the relevant passages. If a tool returns a large document, the agent gets a concise summary or a reference ID for the next targeted request, not the entire raw text. If the task really requires reading the file, move it to the interactive_long or batch_long class.

Prefix caching helps only when the beginning of the context actually matches. It works well for a shared system instruction, an unchanging set of policies, or the same template. It does not compensate for every request carrying a new long history and unique search results. Do not treat a reduction in TTFT from a cache hit as proof that the queue is healthy: a cache miss during peak hours will bring the old problem back.

Also limit max_output_tokens. Long output primarily puts pressure on decode and the KV cache, but it keeps active sequences alive longer, reduces room for new prefills, and increases the queue. Input and output budgets must work together.

Measure goodput, not the maximum number of requests

The maximum number of requests per second says little about LLM API quality if half of the interactive requests begin answering after their target. It is more useful to count goodput: the number of requests that complete the required work within their SLO. For chat, this is usually TTFT plus an acceptable TPOT. For the document class, it is the time to readiness, result correctness, and the absence of endless retries.

Set a simple alerting rule: notify not only when the overall queue grows, but also when p95 queue_ms for the short class exceeds its budget while long pending requests exist. A second alert should fire when p99 input_tokens grows. This often warns about a regression after an agent release before users have time to complain.

Then test changes one at a time. First separate the classes, then enable chunked prefill, then configure input limits, and only afterward add separate replicas. If you change everything at once, you will not know what kept the SLO within target and what merely increased the GPU bill.

A queue does not have to be equally fair to every request. It has to be fair to the promise you made the user. A long document deserves to be processed, but it does not have the right to delay a short operator question merely because it entered the system a fraction of a second earlier.