In traditional online scheduling, the standard intuition is to minimize latency by processing requests as soon as they arrive. However, across domains ranging from deep learning inference to warehouse logistics and ride-sharing, a counter-intuitive strategy has emerged: strategic waiting. By intentionally delaying the execution of early-arriving requests, systems can aggregate them into larger, more efficient batches, ultimately improving throughput and reducing end-to-end latency.
The Efficiency-Latency Trade-off
The core problem addressed by this research direction is the inefficiency of "eager" scheduling. When a system processes requests one by one (First-In-First-Out), it often fails to saturate hardware capabilities or misses opportunities for global optimization.
John C.S. Lui, Leana Golubchik, and Richard R. Muntz first formalized this in the context of continuous media systems in I/O Stream Sharing for Continous Media Systems. They demonstrated that a timeout-based batching policy—waiting for a short window before starting a disk read—allows a single data stream to satisfy multiple users. This trades a small, predictable initial delay for a massive reduction in aggregate I/O demand.
In modern AI workloads, this trade-off is even more pronounced. Arvind Krishnamurthy and colleagues introduced deferred batch scheduling in Symphony: Optimized Model Serving using Centralized Orchestration. They argue that keeping hardware constantly busy with small batches is actually inefficient. Instead, they define a "schedulable window" between a request's arrival and its Service Level Objective (SLO) deadline, using that time to accumulate larger batches that maximize GPU utilization.
Transforming Online Problems into Offline Ones
One of the most powerful aspects of strategic waiting is its ability to bridge the gap between online and offline optimization. In a purely online setting, a scheduler must make decisions with zero knowledge of the future. By buffering requests into discrete "decision epochs," the scheduler gains a local "offline" view of a group of requests.
This mechanism is central to modern ride-pooling. Samitha Samaranayake describes in Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics how aggregating requests into short time windows allows for global matching that considers spatial and temporal interactions. Similarly, Qi Luo shows in A Framework for the Joint Optimization of Assignment and Pricing in Mobility-on-Demand Systems with Shared Rides that the marginal benefit of this global matching far outweighs the minor delay introduced by the batching interval.
The theoretical foundation for this "windowing" approach was explored by Yiding Feng and Rad Niazadeh in Batching and Optimal Multi-stage Bipartite Allocations. They proved that processing demand in $K$ discrete batches allows algorithms to achieve competitive ratios that significantly outperform classic fully-online limits, effectively "bridging the gap" to offline optimality.
Optimizing Hardware Shapes and Flow
In high-performance computing, the shape of a batch often matters as much as its size. Jianshu She and the team behind LAPS: A Length-Aware-Prefill LLM Serving System utilize adaptive batch accumulation to ensure LLM requests are grouped into hardware-optimized shapes. They found that under high concurrency, waiting to form a perfectly shaped batch for a specific CUDA kernel is faster than running an imperfect batch immediately.
This logic extends to multi-stage physical systems, like automated warehouses or pharmaceutical manufacturing. Christoph Hertrich, Christian Weiß, and their co-authors analyzed this in Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines. They demonstrated that intentionally delaying a batch at an early stage of production can optimize the workload for subsequent stages, preventing downstream bottlenecks and reducing the total time to complete all tasks (makespan).
Preventing Internal Queuing Bubbles
Recent work in Large Language Model (LLM) inference has identified a specific type of inefficiency called "internal queuing." When requests are dispatched immediately to a device, they often sit in invisible hardware-level queues, causing head-of-line blocking.
Tian Jian and researchers at Baidu addressed this with Staggered Batch Scheduling (SBS) in Staggered Batch Scheduling: Co-optimizing Time-to-First-Token and Throughput for High-Efficiency LLM Inference. By deliberately buffering requests at the scheduler level instead of the device level, they transform sequential dispatch into a bin-packing problem. This "staggering" eliminates internal bubbles and, counter-intuitively, reduces the Time-to-First-Token (TTFT) by ensuring that when a request is finally dispatched, the hardware is perfectly prepared to handle it.
Theoretical Guarantees and Resource Augmentation
To prove that waiting is mathematically sound, researchers often use resource augmentation, a technique where the online algorithm is compared against an optimal offline adversary that has a slightly slower processor. Chandra Chekuri and Benjamin Moseley used this in Online Scheduling to Minimize the Maximum Delay Factor to show that threshold-based batching—waiting until a specific "urgency" or "density" criteria is met—is a robust strategy for minimizing maximum delay.
Furthermore, Yossi Azar and Noam Touitou established in Beyond Tree Embeddings - a Deterministic Framework for Network Design with Deadlines or Delay that "upgrading" the priority of requests that have already waited ensures they are eventually forced into large, cost-effective future transmissions, preventing the system from ever serving requests in an inefficient, fragmented manner.