Head-of-Line Blocking

The fundamental cause of head-of-line blocking is the synchronous execution model of a batch. In a standard forward pass, a GPU executes the same operation across all sequences in the batch simultaneously. The batch cannot complete until the longest-running sequence in that batch has finished its computation. This creates a direct dependency where one slow request dictates the completion time for all others.

• Parallelism Constraint: Hardware (GPUs/TPUs) is designed for lock-step parallel execution.
• Barrier Synchronization: All sequences in the batch must reach the same computational step before proceeding to the next layer or iteration.

In natural language inference, sequences have highly variable lengths. A single batch may contain a mix of short queries (e.g., 10 tokens) and long documents (e.g., 10,000 tokens). During the prefill phase, processing the long document dominates the compute time for the entire batch. During the decoding phase, sequences finish generation at different times, but the batch remains occupied until the last token is produced for the longest sequence.

• Imbalanced Workload: The computational cost for a sequence is roughly proportional to its length.
• Padding Overhead: To handle variable lengths, shorter sequences are padded with dummy tokens, wasting FLOPs but not eliminating the synchronization wait.

Individual requests can experience delays unrelated to pure compute time, propagating stalls to the entire batch.

• Network I/O: A client may be slow to receive outputs, causing buffer backpressure.
• Downstream Dependencies: A request might involve tool calling or external API lookups that block the model's forward pass.
• Resource Contention: A request may trigger sporadic, high-latency memory operations (e.g., cache misses, memory swapping).
• Faulty Hardware: Uncorrected GPU ECC errors or thermal throttling can slow a specific compute unit affecting the batch.

Static batching is a primary enabler of head-of-line blocking. In this paradigm, a batch is formed at a fixed interval or size and must fully complete before any results are released and a new batch is created. All requests arriving after the batch is formed wait in the queue. Dynamic batching improves this by allowing more flexible scheduling but can still exhibit blocking if not paired with iteration-level scheduling.

• Queue Theory: Blocking severity increases with higher variance in request service times.
• Batching Window Trade-off: A longer window increases batch size (good for throughput) but also increases the chance of incorporating a very long request that will block others.

The inherently sequential nature of token generation in LLMs exacerbates blocking. Each decoding iteration produces one token per sequence. While a short sequence may finish after 50 iterations, a long one continues for 200. The system cannot release the finished sequences mid-batch in a standard static execution graph.

• Iteration Lockstep: Every iteration, the GPU runs the forward pass for all active sequences, even those that have already generated their end-of-sequence token.
• Cumulative Delay: The total wasted time is the sum of the idle cycles across all finished sequences for each extra iteration they are forced to wait.

During decoding, inference is memory-bandwidth-bound, reading the KV cache and model weights. A single slow sequence can indirectly block others by saturating the memory bus with its data fetches, increasing the effective iteration time for the entire batch. This is a more subtle form of resource-mediated head-of-line blocking.

• Shared Resource: High Bandwidth Memory (HBM) on a GPU is a shared resource across all streaming multiprocessors.
• Non-Uniform Memory Access (NUMA): In multi-GPU settings, imbalanced requests can cause cross-device memory transfers, creating a slow link that affects all co-located requests.