🤖 AI

Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics

This position paper argues that LLM inference serving has outgrown generic heuristics and requires the development of mathematical optimization models and algorithmic foundations tailored to its unique characteristics to ensure provable performance guarantees across diverse workloads.

Original authors: Zijie Zhou

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zijie Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive, high-speed restaurant kitchen. This kitchen doesn't just cook burgers; it creates complex, multi-course meals based on orders that arrive one by one. The catch? You don't know how long each meal will take to cook, and the more the chef cooks, the more counter space the meal takes up, crowding out other orders.

This is exactly the situation with Large Language Models (LLMs) today. They are the "kitchens" powering search engines, coding assistants, and chatbots.

The paper argues that right now, these digital kitchens are running on guesswork and simple rules (heuristics). The author believes it's time to switch to mathematical precision and solid algorithmic foundations to make them faster, cheaper, and more reliable.

Here is the breakdown of the paper's argument using everyday analogies:

1. The Problem: "Good Enough" Rules Are Failing

Currently, systems like vLLM and SGLang (the software that runs these models) use old-school rules borrowed from general computing.

The Queue: If you have a line of customers, the kitchen just serves them in the order they arrived (First-Come, First-Served).
The Routing: If you have multiple chefs, the kitchen sends the next order to the chef with the shortest line, or just spins a wheel to pick one.
The Cleanup: If the counter gets full, the kitchen throws away the oldest item on the counter to make room for a new one.

The Paper's Point: These rules work fine for a standard burger joint. But LLMs are weird.

The "Growing" Meal: Unlike a burger that takes up the same space from start to finish, an LLM meal grows as it's cooked. Every word the AI generates takes up more memory.
The "Two-Phase" Cooking: The first part of the order (reading the prompt) is fast and requires a lot of brainpower (compute). The second part (generating the answer) is slow and requires a lot of memory bandwidth.
The Unknown: The kitchen doesn't know how long the meal will be until it's finished.

Because of these quirks, the old "shortest line" or "oldest item out" rules often cause chaos, leaving some chefs idle while others are overwhelmed, or causing the counter to run out of space unexpectedly.

2. The Solution: Bring in the Mathematicians

The author says we need to stop guessing and start using mathematical optimization. Think of this as hiring a master logistics planner who uses a super-computer to calculate the perfect way to run the kitchen, rather than just following a rulebook.

The paper highlights four specific areas where math can fix the kitchen:

Balancing the Chefs (Load Balancing):
- Current Way: Send orders to the chef with the fewest tickets.
- Math Way: Calculate exactly how much "counter space" and "brainpower" each order will need as it grows, and distribute them so no single chef ever gets stuck waiting for the slowest one. The paper cites a real system (DeepSeek) that uses Linear Programming (a type of math) to do this perfectly, saving time and money.
The Waiting Line (Scheduling):
- Current Way: Serve the first person in line.
- Math Way: Look at the line and realize, "That person ordered a 10-page essay, but the next person only wants a one-sentence joke." Serve the joke first! It clears the counter faster and lets more people eat. Math can predict which orders will finish quickly to keep the kitchen moving.
The Counter Space (Caching):
- Current Way: Throw away the oldest item when the counter is full.
- Math Way: Realize that throwing away a "high-resolution video" to make room for a "tiny thumbnail" is a bad deal. Re-making the video takes forever and costs a fortune. Math can calculate the "cost" of throwing things away and keep the expensive items on the counter.
Planning the Staff (Capacity Planning):
- Current Way: Keep adding chefs when the line gets too long.
- Math Way: Use formulas to know exactly how many chefs you need before you even open the doors, based on how many customers are expected. This prevents the kitchen from ever getting overwhelmed in the first place.

3. Why Not Just Stick with the Rules?

The paper addresses the skeptics who say, "The current rules work fine, why change?"

"It works at scale": The author admits the current rules work okay, but they are fragile. If a viral app suddenly sends a weird type of order, the kitchen might crash. Math provides a safety net (guarantees) that ensures the kitchen won't fail, even in the worst-case scenarios.
"Hardware changes too fast": The author argues that while the hardware (the ovens) changes, the logic of how to organize the kitchen remains the same. Math gives you a blueprint that works even if you swap the ovens.
"Systems engineering is more important": The author says math and engineering are partners. You can have the fastest oven in the world, but if your scheduling is bad, the oven sits idle. Math tells you how to keep the oven busy.

4. The Big Picture

The paper concludes that the field of LLM serving has outgrown its "childhood" of simple rules. It has matured into a complex system that demands adult supervision from mathematicians and algorithm experts.

By treating these problems as math puzzles rather than just engineering tweaks, we can get:

Predictability: Knowing exactly how the system will behave.
Efficiency: Saving massive amounts of energy and money.
Reliability: Ensuring the system doesn't crash when things get crazy.

In short: Stop guessing. Start calculating. The future of AI serving isn't just about building bigger models; it's about building smarter, mathematically proven ways to run them.

Technical Summary: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics

1. Problem Statement

The paper argues that Large Language Model (LLM) inference serving has evolved beyond the capabilities of generic heuristics inherited from classical distributed systems. While modern serving frameworks (e.g., vLLM, SGLang) have achieved significant architectural innovations—such as continuous batching, paged attention, and prefill-decode disaggregation—their core algorithmic decision-making processes remain rooted in simple, general-purpose policies.

The central problem is a structural mismatch: LLM inference possesses unique characteristics that generic heuristics fail to exploit, including:

Phase Asymmetry: A compute-bound prefill phase versus a memory-bandwidth-bound decode phase.
Dynamic Resource Consumption: KV cache memory grows monotonically with each generated token, with the final size unknown until generation completes.
Sticky Assignments: Once a request is routed to a worker, migrating it is prohibitively expensive due to KV cache transfer costs.
Barrier Synchronization: In data-parallel or expert-parallel settings, the slowest worker (often determined by KV cache size) dictates the latency for the entire batch.

Current practices rely on heuristics such as Join-Shortest-Queue, Round-Robin, First-In-First-Out (FIFO) scheduling, and Least-Recently-Used (LRU) eviction. The paper contends these policies ignore the specific constraints of LLM workloads, leading to unpredictable performance under diverse or adversarial conditions and preventing the derivation of fundamental performance limits.

2. Methodology and Proposed Framework

The paper advocates for a shift from empirical heuristic tuning to mathematical optimization and algorithmic foundations. The proposed methodology involves:

Formal Modeling: Casting serving decisions (routing, scheduling, caching, capacity planning) as rigorous mathematical programs (e.g., Linear Programming, Integer Programming, Queueing Theory).
Structural Analysis: Deriving theoretical insights (e.g., dual variables, stability conditions, competitive ratios) from these models to understand the fundamental limits of the system.
Algorithm Design: Developing algorithms that either solve these programs directly (where computationally feasible) or use the structural insights to design practical approximations with provable performance guarantees.

The paper draws a historical parallel to Airline Revenue Management, where linear programming was used not to solve for every booking in real-time, but to derive "bid-price" control policies that are simple, fast, and grounded in optimality conditions.

3. Key Contributions and Representative Examples

The paper identifies four critical bottleneck areas where principled optimization offers superior alternatives to current heuristics, supported by emerging research:

A. Expert Routing and Load Balancing (MoE)

Current State: Relies on auxiliary loss functions during training or reactive heuristics (e.g., random noise, expert choice) to balance token distribution across GPUs.
Optimization Approach: Formulating load balancing as a constrained assignment problem.
Example: DeepSeek's LPLB system casts per-batch token redistribution as a Linear Program (LP). It minimizes the maximum per-GPU load subject to capacity constraints on redundant expert replicas.
Result: The LP is solved via an embedded GPU solver in ~100µs, achieving optimal token balance without the interference gradients of auxiliary losses.

B. Request Routing in Data Parallelism

Current State: Uses stateless dispatch policies (Round-Robin, Power-of-Two-Choices) that ignore the "sticky" nature of KV cache assignments and the unknown duration of decode steps.
Optimization Approach: Modeling routing as an online integer optimization problem with barrier synchronization constraints.
Example: Chen et al. (2026) propose a "Balance-Future" principle. Instead of predicting total decode length (which is hard), the algorithm uses short-horizon forecasts to minimize accumulated imbalance over a lookahead window.
Result: Theoretical analysis proves the algorithm reduces long-run average imbalance by a factor of $\Omega(\sqrt{B} \log G)$ compared to default policies, even under adversarial arrival sequences.

C. Scheduling and Capacity Planning

Current State: Relies on reactive autoscaling (adjusting worker counts based on queue depth) and FCFS scheduling.
Optimization Approach: Applying queueing theory to derive closed-form stability conditions and combinatorial optimization for admission control.
Example: Anonymous (2025) derives stability conditions accounting for both compute and memory constraints, allowing operators to calculate minimum fleet size before deployment. Jaillet et al. (2025) establish lower bounds via LP relaxations to benchmark online scheduling algorithms.
Result: Proactive capacity planning prevents runtime instability; optimal scheduling policies (e.g., Shortest-Job-First under specific assumptions) can be proven near-optimal.

D. Caching and Eviction

Current State: Uses LRU eviction, which ignores the heterogeneous sizes of multimodal embeddings and the varying costs of recomputation.
Optimization Approach: Formulating caching as a cost-minimization problem rather than a hit-rate maximization problem.
Example: Zhu et al. (2023) introduce the Least Expected Cost (LEC) algorithm, which scores items by cost-per-unit-size multiplied by access probability.
Result: The approach achieves optimal regret (converging to the best possible cost as fast as information theory allows) and demonstrates up to 50x cost reduction in multimodal scenarios.

4. Results and Significance

The paper does not present a single new system but synthesizes emerging work to demonstrate that principled methods can match or exceed heuristic performance while providing guarantees that heuristics cannot.

Key Claims of Significance:

Robustness: Algorithms with provable worst-case bounds (e.g., competitive ratios) ensure reliability under adversarial workloads or distribution shifts, unlike heuristics tuned only on average benchmarks.
Capacity Planning: Theoretical analysis provides closed-form stability conditions, enabling precise resource provisioning before deployment rather than reactive scaling.
Engineering Guidance: Even when optimal algorithms cannot be deployed directly, their structural insights (e.g., which constraints are binding) guide the design of efficient, robust heuristics.
New Research Frontier: LLM serving introduces novel problem classes (e.g., scheduling with growing memory constraints, online allocation with sticky assignments) that require dedicated algorithmic study beyond classical distributed systems.

The paper concludes by calling for cross-disciplinary engagement: systems researchers must understand optimization theory to uncover fundamental limits, while algorithm researchers must engage with system constraints to ensure theoretical models translate to practical impact. The ultimate goal is to treat algorithmic design for LLM serving as a durable research frontier, moving the field from ad-hoc engineering to mathematically grounded optimization.