Lookahead improves online batching for efficient request serving
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Data Structures and Algorithms
Summary
Balancing when to serve online requests is tricky: serving immediately reduces waiting, but batching requests together uses hardware better. The authors study how knowing some future requests ahead (lookahead) helps scheduling. They find that with unpredictable arrivals, having limited glimpse of the future only slightly helps, but when arrivals follow common patterns like Poisson, even small lookahead can greatly improve efficiency. Their results also show performance degrades gracefully if predictions are imperfect, and tests on real and synthetic data confirm these benefits.
What this means in practice
- •For data center operators: Optimize request batching to reduce processing delays using limited future request information to improve server throughput.
- •For cloud service engineers: Develop scheduling policies that leverage short-term arrival forecasts to approach offline optimal response times under realistic workloads.
Authors
Dimitris Christou, Jiayi Chen, Nihal Sharma, Aditya Akella, Shuchi Chawla, Sanjay Shakkottai
Abstract
Modern inference systems rely on batching to exploit parallel execution and amortize serial execution overheads, but batching creates a fundamental online scheduling tradeoff: serving requests immediately reduces request queuing delay, while waiting can form larger batches that better utilize parallel hardware and improve serving efficiency. We study this tradeoff in a single-server online batching model with bounded batch capacity, fixed batch processing time, and the objective of minimizing total flow time. Our focus is on the value of finite lookahead into future arrivals over a purely online setting for scheduling. We show that the benefits of lookahead depend on the arrival model. In the adversarial setting, finite perfect lookahead has inherent limitations: for any bounded lookahead window, every online algorithm remains separated from the offline optimum by a constant factor. Thus, worst-case arrival sequences can prevent perfect knowledge of future events from fully overcoming online uncertainty. In contrast, under Poisson arrivals in the stable regime, finite lookahead is much more powerful. Although the best distribution-aware online algorithm has a nonzero asymptotic gap from the offline optimum, lookahead closes this gap exponentially fast in the window length. We prove matching upper and lower bounds up to constants in the exponent. Together, these results give a tight characterization of when lookahead can close the online--offline gap, incorporating insights from the competitive analysis of online algorithms into queueing-theoretic steady-state bounds. We also study imperfect predictions, showing that the benefit of lookahead degrades gracefully with prediction error. Simulations on synthetic arrivals and experiments on real request traces support the theory: modest lookahead substantially reduces flow time and brings online batching close to the offline benchmark.