In shared computing environments, the simplest way to handle incoming requests is First-Come, First-Served (FCFS) scheduling. It requires no prior knowledge of the tasks and seems inherently fair. However, when workloads exhibit highly variable or heavy-tailed distributions, FCFS introduces a severe performance bottleneck known as Head-of-Line (HoL) blocking.
HoL blocking occurs when a massive, resource-intensive task sits at the front of the execution queue, forcing numerous smaller, latency-sensitive tasks behind it to wait. In large-scale GPU datacenters, Hu et al. observed that this exact phenomenon creates immense unfairness: a tiny fraction of long-running training jobs can stall short debugging or preprocessing tasks, drastically inflating average queuing delays. This problem is magnified in modern Large Language Model (LLM) inference serving, where the execution time of a request scales linearly with its output token length (Xu et al.). Because LLM workloads are heavily skewed—mixing short conversational greetings with massive document summarizations—a few long generation tasks can completely paralyze a queue, causing interactive users to experience unacceptable delays before receiving their first token (Sidik et al.).
To solve this, a growing body of research focuses on moving toward size-aware scheduling. By prioritizing shorter tasks, systems can dramatically reduce average wait times without significantly penalizing long jobs.
Standard FCFS Queue (Head-of-Line Blocking):
[ Long Request (Processing...) ] <- [ Short Job A (Waiting) ] <- [ Short Job B (Waiting) ]
* Result: High average latency. Short jobs are penalized.
Size-Aware Queue (Shortest Job First):
[ Short Job A (Processing) ] <- [ Short Job B (Next) ] <- [ Long Request (Deferred) ]
* Result: Low average latency. Short jobs finish instantly; long job is minimally delayed relative to its size.
The Information Asymmetry of Autoregressive Generation
In classical queueing theory, algorithms like Shortest Job First (SJF) or Shortest Remaining Processing Time (SRPT) are proven to minimize average latency. Mitzenmacher demonstrated that a scheduler does not even need perfect information to unlock these benefits; receiving just a single bit of "advice"—a simple label classifying a job as "large" or "small"—captures a massive portion of the performance gains of perfect knowledge.
The fundamental challenge in LLM serving is that we do not know the job size in advance. Because tokens are sampled stochastically one by one, the final output length is unknown until the model generates an end-of-sequence token. Furthermore, as Shahout et al. point out, when LLMs are augmented with external tools or APIs, execution times decouple from token counts entirely, as a request might stall while waiting for a third-party network response.
To implement size-aware scheduling without knowing the exact runtime, researchers have developed mechanisms to predict, rank, or bypass explicit length estimation.
Learning to See the Future
One approach to breaking HoL blocking is to infer the request length before or during the early stages of execution.
Instead of trying to predict exact token counts—which is notoriously difficult—Fu et al. demonstrate that a scheduler only needs to predict the relative rank of request lengths. By training a lightweight auxiliary model to compare pairs of incoming prompts, the scheduler can sort the queue from shortest to longest, achieving massive reductions in chatbot latency.
Other systems extract rich features directly from the model's execution context:
- Linguistic Uncertainty: Liu et al. analyze the prompt's structure and linguistic uncertainty to forecast generation lengths, using these insights to consolidate batches and prioritize urgent tasks.
- Embedding Recycling: Shahout et al. introduce TRAIL, a system that "recycles" the hidden state embeddings generated during the very first few tokens of an LLM's execution. These internal representations contain deep semantic clues about how long the model intends to elaborate, allowing real-time length prediction coupled with limited preemption.
Managing Uncertainty and Tail Latencies
Relying on deterministic "point estimates" (single-number predictions) can be dangerous. If a scheduler mistakenly predicts that a massive job will be short, it will place it at the front of the queue, inadvertently triggering the exact HoL blocking it was designed to avoid.
To mitigate this risk, Zheng et al. propose modeling output lengths as a heavy-tailed probability distribution rather than a fixed number. Their scheduling strategy, Tail Inflated Expectation (TIE), calculates a risk-aware metric that penalizes jobs with high length uncertainty, ensuring that the scheduler does not gamble cluster responsiveness on volatile predictions.
Alternatively, some researchers argue that prediction is a fragile foundation. Li et al. introduce UniBoost, a prediction-free framework that focuses on tail latency (the 99th percentile). Instead of guessing lengths, it utilizes a "soft" priority boosting mechanism and memory-aware preemption. If a job has been running for a long time, its priority is dynamically adjusted, preventing a few long-running requests from permanently masking the execution of incoming traffic.
Fine-Grained Co-Serving and Resource Harvesting
HoL blocking also manifests when different classes of workloads share the same hardware. For instance, data centers frequently co-locate latency-sensitive "online" requests (like interactive user chatbots) with throughput-oriented "offline" tasks (like batch document indexing). If resource allocation occurs at a coarse granularity, an online query might arrive and find the GPU entirely occupied by a massive batch iteration (Sun et al.).
To prevent batch tasks from blocking interactive traffic, Qiao et al. design ConServe, which operates at the token and layer level. Rather than letting a batch job run to completion, the system "harvests" idle GPU cycles dynamically. It interleaves batch computations strictly within the tiny, fine-grained pauses of online requests.
Coarse-grained Co-serving (High HoL Blocking):
[ Batch Job Iteration (Long) .................... ] -> Online Request Waits!
Fine-grained Harvesting (ConServe):
[ Online Token 1 ] -> [ Batch Layer 1 ] -> [ Online Token 2 ] -> [ Batch Layer 2 ]
By breaking monolithic execution blocks into these microscopic increments, modern schedulers ensure that large jobs can still utilize the hardware efficiently without ever standing in the way of immediate, interactive responses.
Key Foundational Work
Task Resource Allocation in Grid using Swift Scheduler (2009) — contributed 1 concept elements to this direction.
Héron: Taming Tail Latencies in Key-Value Stores Under Heterogeneous Workloads (2018) — contributed 1 concept elements to this direction.