Continuous batching did not abolish first-come-first-serve — your inference server still admits requests in arrival order, so one long generation blocks every short request behind it and p99 explodes. Shortest-job-first is the tempting fix and it just moves the tail.
A team puts a chat model behind a serving stack — vLLM, TGI, SGLang, whichever — and the headline feature is continuous batching. They read the explainer: instead of waiting for a whole batch to finish before starting the next, the server interleaves at the token level, retiring finished sequences and slotting new ones into the running batch every step. GPU utilization goes up, throughput goes up, the benchmark graph looks great. The team ships it, and the average latency is fine. Then the p99 latency graph comes in, and it is terrible — not a little high, but multiples of the median, and spiking in a way the average never hinted at.
The reflex is to assume continuous batching is misconfigured, or the batch size is wrong, or the GPU needs to be bigger. None of those is the cause. The cause is one layer underneath the batching, in the part of the server almost nobody configured: the scheduler that decides which queued request gets admitted into the running batch next. By default, it admits them in the order they arrived. First come, first served. And continuous batching, for all that it interleaves execution, did not change the admission order — it is still FIFO at the door, and FIFO at the door is the structural reason the tail is bad.
“Continuous batching” and “the scheduler stopped being first-come-first-serve” are different claims. The first is true of every modern stack. The second does not follow from it, and on a stock server it is false. The gap between the two is where your p99 lives. This post is about why arrival-order admission combined with unpredictable, heavy-tailed output length is the structural cause of bad tail latency, why the obvious fix — shortest-job-first — starves long requests and just relocates the tail, and what the real scheduler has to look like.
Static batching ran every member of a batch to completion before accepting new work — so a batch finished when its slowest member finished, and one long generation left finished slots idle while the GPU ran a batch of one. Continuous batching fixed exactly that: it retires a sequence the instant it emits its end-of-sequence token and admits a waiting request into the freed slot, keeping the GPU full so short requests are no longer held hostage to the longest request in their own batch. That is real, and it is why the throughput numbers are good.
What it did not change is the order in which waiting requests are admitted. When a slot frees, the default pick is the request that has waited longest — arrival order. So the long generation that no longer blocks the requests batched with it still blocks every request queued behind it: it occupies a slot for its entire, possibly very long, decode while the short requests stack up in the queue. Continuous batching moved the head-of-line blocking from inside the batch to the admission queue — which is exactly where a token-level explainer stops looking.
The clearest evidence is the defect surviving every batching regime at once. Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction (arXiv 2404.08509) reports a shortest-job-first scheduler that “reduces average job completion times by 30.5-39.6% and increases throughput by 2.2-3.6x compared to FCFS schedulers, across no batching, dynamic batching, and continuous batching settings.” The list of settings is the load-bearing part: the fix helps under continuous batching too, which can only be true if continuous batching did not already solve it. The same paper names the root cause — “Existing LLM serving systems exploit first-come-first-serve (FCFS) scheduling, suffering from head-of-line blocking issues” — and locates it in “the unpredictable execution times originating from the autoregressive nature of generative models.”
Why default to FIFO when its tail behavior is this bad? Not laziness — the scheduler is missing the one input that would let it do better, for a real reason. To avoid parking a thirty-second generation in front of a stack of half-second ones, a scheduler would need to know, at admission time, which requests are short. But the server does not know how long a generation will be. A request arrives as a prompt; its length is decided one token at a time by the model as it decodes, and is final only when an end-of-sequence token is sampled. You cannot read output length off a request the way you read a file size off a download — so the server falls back to the one ordering it can compute with zero information about job size: arrival order.
Efficient LLM Scheduling by Learning to Rank (arXiv 2408.15792) states the chain exactly: because output length “is typically regarded as not known a priori,” it follows that “most LLM serving systems employ a simple First-come-first-serve (FCFS) scheduling strategy, leading to Head-Of-Line (HOL) blocking and reduced throughput and service quality.” Length treated as unknown → FCFS → HOL blocking. The default is a consequence of the missing information, not a policy anyone defends on its merits.
And the consequence is about the tail specifically, not just the average. EWSJF: An Adaptive Scheduler with Hybrid Partitioning for Mixed-Workload LLM Inference (arXiv 2601.21758) puts it in the sharpest terms: “Standard First-Come, First-Served (FCFS) policies suffer from severe head-of-line blocking, leading to high tail latency and underutilized hardware.” It is worst where production traffic is messiest — “short, latency-sensitive interactive queries alongside long, throughput-oriented batch requests” on one server. That mixed profile is the one-long-generation-blocks-the-short-ones mechanism exactly, and it is the traffic most real deployments have, because the same endpoint serves a chat box, a batch summarizer, and a long agent transcript at once. EWSJF reports up to a 4× reduction in average Time-To-First-Token for short requests versus FCFS — the short requests were paying a 4× TTFT tax to sit behind the long ones.
The magnitude is large and consistent across the systems built to remove arrival-order blocking. Fast Distributed Inference Serving for Large Language Models (arXiv 2305.05920) — the foundational diagnosis — starts from “Existing LLM serving systems use run-to-completion processing for inference jobs, which suffers from head-of-line blocking and long latency,” and answers with preemption: “FastServe uses preemptive scheduling to minimize latency with a novel skip-join Multi-Level Feedback Queue scheduler.” That it “improves the throughput by up to 31.4x and 17.9x under the same average and tail latency requirements, respectively” means that at a fixed tail-latency target, the default scheduler was leaving an order of magnitude of throughput on the floor. And the lever is the scheduler, not the hardware: SSJF notes its implementation “does not require changes to memory management or batching strategies.” The team that answered bad p99 by buying a bigger GPU was treating a scheduling defect as a capacity problem.
If FCFS is bad because it parks long jobs in front of short ones, the textbook answer is shortest-job-first: always admit the shortest waiting request. The principle is genuinely favorable — Scheduling LLM Inference with Uncertainty-Aware Output Length Predictions (arXiv 2604.00499) states it directly: “To schedule LLM inference, the shortest job first (SJF) principle is favorable by prioritizing requests with short output lengths to avoid head-of-line (HOL) blocking.” SJF is provably optimal for mean completion time. So why is this not the end of the post? Two reasons, both structural.
The first is starvation. Under a steady arrival of short requests, a long request can sit unadmitted indefinitely — every freed slot goes to something shorter that just arrived. Its mean latency improved nothing because it never ran; the tail got worse, because the worst-case wait now belongs to long jobs and is unbounded. SJF does not remove the tail, it relocates it from “short requests stuck behind long ones” to “long requests starved forever.” This is why serious schedulers do not optimize job time alone — EWSJF is built “to jointly improve fairness and throughput,” fairness being the constraint that bounds how long any request can be starved. The same lesson runs through agent-level reliability: a number that looks fine on average can hide a distribution that fails most of the time, and optimizing the average is not optimizing the tail.
The second reason is that you cannot run SJF anyway, because it needs the job sizes the whole problem started without. The learning-to-rank paper draws the line precisely: “although predicting the exact generation length of each request is infeasible, it is possible to predict the relative ranks of output lengths in a batch of requests, using learning to rank.” Output length is rankable, not knowable — you can train a model to say “A will probably finish before B” far more reliably than “A will produce 312 tokens.” The achievable scheduler is not true SJF on known lengths; it is an approximation of SJF on predicted ranks, which is why the gains are real but bounded, and approximating it yields “2.8x lower latency in chatbot serving and 6.5x higher throughput in synthetic data generation.”
The uncertainty paper makes the deepest point: a point prediction is the wrong object. Output length “is uncertain by nature and determined by when the end-of-sequence (EOS) token is sampled,” and “output length follows a heavy-tailed distribution and can be fitted with the log-t distribution.” Heavy-tailed is the operative word: the rare very-long generation is far more probable than a thin-tailed intuition expects, and those rare monsters are exactly what wreck tail latency — so a scheduler predicting a single expected length per request systematically under-weights the risk that this request is one of them. Their fix schedules on a risk-adjusted quantity: “Tail Inflated Expectation (TIE) … adjusts the expectation of a log-t distribution with its tail probabilities to account for the risk that a request generates long outputs,” reducing “per-token latency by 2.31x for online inference.” The right scheduler reasons about the distribution of a request’s length, especially its tail, not a single guess.
Put the pieces together and the correct scheduler is neither FCFS nor naive SJF. It admits in an order informed by predicted relative length, not arrival order; treats each request’s length as a heavy-tailed distribution and schedules on a risk-adjusted quantity; bounds starvation so prioritizing short jobs does not push long jobs into an unbounded tail; and controls the rate of admission into the running batch, not only the ordering — because what makes naive admission unstable is not just latency but memory.
That last constraint has its own paper. Flow-Controlled Scheduling for LLM Inference with Provable Stability Guarantees (arXiv 2604.11001) ties unknown length to instability, not just slowness: “A key challenge in LLM inference is that decode lengths are unknown. The memory usage for each request grows with generated tokens, which may lead to overflow and cause system instability.” Because each admitted request’s KV cache grows as it decodes, admitting too many at once risks running out of memory mid-generation — the long-tail request you could not predict is also the one that blows the memory budget. The answer makes admission an explicit control surface: “we propose a simple flow-control framework that controls the rate at which prompts join the active set,” with “sufficient conditions under which our algorithm provably achieves stability,” yielding “higher token and request throughput, lower average and tail latency, and more stable KV cache utilization” versus arrival-order strategies. Admission policy is a control surface with a stability condition attached, and the stock FIFO door satisfies none of it.
Independent corroboration that length-blindness is the structural cost comes from CascadeInfer: Length-Aware Scheduling of LLM Serving with Low Latency and Load Balancing (arXiv 2512.19179): “current inference engine schedulers overlook the attention backend’s sensitivity to request-length heterogeneity within a batch,” and at modern context windows “this once-tolerable inefficiency has escalated into a primary system bottleneck, causing severe performance degradation through GPU underutilization and increased latency.” Making the scheduler length-aware “reduces end-to-end latency by up to 67%, tail latency by up to 69%, improving overall system throughput by up to 2.89 times.” A 69% tail-latency reduction from changing the scheduler, no new hardware, is the size of the p99 prize you are leaving unclaimed.
The unifying claim across all seven papers is narrow and well-supported: you cannot schedule LLM inference well without reasoning about output length; output length is heavy-tailed and only rankable, not knowable; and the resulting scheduler must be uncertainty-aware and starvation-bounded — none of which a stock server’s arrival-order door does.
Several honest qualifications, because the overstated version loses the reader who runs these systems.
First, the multipliers are not one comparable number, and you should not average them. “31.4x throughput” (against run-to-completion), “69% tail-latency reduction” (against length-blind scheduling), “4× TTFT for short requests,” and “2.31x per-token latency” are measured against different baselines, workloads, hardware, and objectives. They establish the prize is large and consistent in direction; they do not compose into “FCFS is 30× slower.” Quote the one whose baseline and metric match your situation, not the biggest.
Second, the gains are workload-dependent, and the dependence is the point. Head-of-line blocking is most severe under mixed workloads with high length variance — the heavy-tailed traffic these papers assume. A deployment whose requests are genuinely homogeneous in length (every request a roughly equal classification, say) has a short tail to begin with and buys correspondingly less from a smart scheduler. Measure your own output-length distribution before assuming you have the problem; if your tail is thin, the scheduler is not your bottleneck.
Third, “stock server defaults to FCFS” is the published characterization across these papers, and modern engines are moving — adding priority scheduling, length-aware policies, preemption knobs. “Your server is FIFO” is the out-of-the-box default the literature targets, not a claim every deployed server is stuck there; check which policy yours is actually running rather than assume either FIFO or that the defaults fit your traffic.
Fourth, length prediction is a real component with real cost and real error. The rank predictors and proxy models above must be trained, served, and kept calibrated, and a wrong prediction can mis-schedule — admit a long request as short and you have manufactured the head-of-line block you were avoiding. The net wins are reported after these costs; the win is an engineering investment with its own failure surface, not “add ranking, get 2.8× for free.”
Before you call an inference deployment’s tail latency understood:
The team’s p99 graph was the architecture’s promise read one layer too shallow: continuous batching really did interleave execution and fill the GPU, and the throughput number was honest. But interleaving execution is not reordering the queue, and the door of a stock server still admits requests in the order they arrived — so one long, unpredictable generation still parks in front of every short request behind it, and that is the tail. The fix is not a bigger GPU, and not naive shortest-job-first, which only moves the tail onto the long requests by starving them. It is a scheduler that admits on predicted rank rather than arrival time, prices in the heavy tail of output length rather than a single guess, bounds starvation as a first-class goal, and controls admission for stability — the scheduler your server is almost certainly not running by default. Check which policy yours is actually using, measure the tail your traffic actually has, and treat the order requests enter the batch as the design decision it is, not the default you inherited.
A membership-inference attack that separates your book from a held-out one is usually reading the calendar, not the weights. A successful attack is not a sound proof — and the null it would need to test against cannot be sampled.
17 min →
Unlearning promises a model can forget specific data without a full retrain. What it delivers is output suppression: a small benign relearning set — or simply quantizing the model — brings the 'forgotten' knowledge back.
14 min →
The EU AI Act requires AI output to be marked in a robust, reliable way. A formal impossibility theorem says strong watermarking cannot exist. Five words in the statute carry the collision.
13 min →