Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints

A team of researchers has proposed new online scheduling algorithms designed to manage the memory constraints of large language model inference, a process that can cost providers more than $700,000 per day [1][2]. The work, led by Ruicheng Ao, addresses a core challenge in serving large language models (LLMs): the growth of the Key-Value (KV) cache as models generate tokens token-by-token. When this cache exceeds GPU memory, in-progress requests can be evicted, wasting the computation already performed [1][2]. The researchers frame this as a multi-stage online scheduling problem with endogenous memory growth and linear iteration times [1][7]. To tackle this, they first developed a fluid model that replaces stochastic sample paths with average flows. This model characterizes an equilibrium batch composition, the memory required to support it, and a stability region defining the arrival rates a system can handle without eviction-driven restarts [5][7]. The fluid model provides a benchmark for throughput and memory use that the scheduling algorithms aim to approximate [5]. Guided by this model, the team designed two threshold-based admission rules. The first, WAIT (Waiting for Accumulated Inference Threshold), is for scenarios where output lengths are known in advance. The second, Nested WAIT, handles unknown output lengths by organizing the decoding process into nested segments and regulating how requests advance across them [1][3]. Nested WAIT uses an additional safety buffer to hedge against memory-overflow-induced evictions when output length is uncertain [2][4]. The algorithms were tested in Vidur simulations configured for a Llama-2-7B model on an A100 GPU, with supplemental real-GPU validation [1][2]. The results showed that the policies enlarged the stable operating range compared to widely used baselines and reduced latency, particularly in near-overloaded and overloaded regimes [1][5]. The research was submitted to arXiv on April 15, 2025, and most recently revised on June 13, 2026 [1].