💻 computer science

Astrolabe: Balancing Load in LLM Serving with Randomized Prediction-Guided Scheduling

Astrolabe is a randomized prediction-guided scheduler for multi-instance LLM serving that achieves superior load balancing and reduced latency by combining response-length estimation, simulation-based latency prediction, and a power-of-two-choices dispatch policy, thereby eliminating the need for costly migration-based rebalancing.

Original authors: Wei Da, Evangelia Kalyvianaki

Published 2026-08-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Wei Da, Evangelia Kalyvianaki

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-tech bakery that specializes in baking "thought-cakes" for millions of customers at once. In this bakery, the ovens are incredibly powerful, but the recipes are tricky. Sometimes a customer asks for a simple cookie (a short answer), and sometimes they ask for a ten-layer wedding cake (a long, complex answer). The problem is that the bakers (the computers) don't know how big the cake will be until they start baking it. If a baker gets stuck with a huge order while everyone else is idle, the line backs up, and customers get angry.

To fix this, many bakeries used to have a "runner" who would run between ovens, grabbing half-baked cakes and moving them to a freer oven if one got too busy. This is called "migration." But in the world of artificial intelligence, moving these half-baked cakes is messy and slow. It's like trying to carry a giant, fragile, half-frozen cake across a crowded room without dropping it; it takes up a lot of energy, clogs the hallways, and often makes the whole bakery slower. This paper, titled "Astrolabe," asks a bold question: What if we didn't need to move the cakes at all? What if we could just guess the size of the order before it even hits the oven, and send it to the right baker immediately?

The authors of this paper, Wei Da and Evangelia Kalyvianaki from the University of Cambridge, built a new system called Astrolabe to solve this exact problem. They found that instead of frantically running back and forth to shuffle work around, you can use a clever "guessing game" to send orders to the right place instantly.

Here is how Astrolabe works, using a simple game of chance. Imagine you have a dozen bakers. When a new order comes in, instead of asking every single baker how busy they are (which takes too long) or just picking one at random (which is risky), the system picks two bakers at random. It quickly asks them, "If you took this order right now, how long would it take?" One of them might say, "About 10 seconds," and the other might say, "About 50 seconds." The system instantly picks the 10-second baker and sends the order there.

This trick is called "power-of-two choices." It's like walking into a crowded cafeteria and picking the shortest line by only checking two lines instead of scanning the whole room. The paper shows that this simple random check is surprisingly powerful. By combining this with a "crystal ball" (a prediction model) that guesses how long the AI's answer will be, Astrolabe can route requests to the best baker before the line even starts to form.

The results are quite impressive. In their tests, Astrolabe managed to handle just as many requests as the old "runner" method (migration), but without the messy overhead of moving data around. In fact, when the bakery got super busy, the old method started to collapse, with wait times jumping from seconds to minutes. Astrolabe, however, kept things smooth. It reduced the time it took to get the first word of an answer by up to 77% in some cases and cut down on the number of times orders had to be interrupted and restarted by about 6 times compared to the competition.

The paper also tested what happens if the "crystal ball" isn't perfect. Even when the predictions were a bit off (which happens in real life), the system still worked better than the old ways. It turns out that because the system only compares two bakers at a time, small mistakes in guessing don't matter as much as you'd think. If both bakers are guessed to be slow, the system just picks the "less slow" one, and the math still works out.

The authors also checked if this would work if they changed the type of oven or the kind of cake being baked. They tried different models and different settings, and Astrolabe kept winning. It seems that this "guess-and-check" approach is a robust way to keep AI systems running fast, even when the workload is chaotic and unpredictable.

In short, the paper suggests that we don't need to build complex, heavy-duty systems to move work around to balance the load. Instead, a little bit of randomness and a good guess about the future can do the job much faster and more efficiently. It's a reminder that sometimes, the smartest way to manage a crowd isn't to micromanage every single person, but to give them a few good options and let them choose the best path.

Technical Summary: Astrolabe

Problem Statement

Large Language Model (LLM) inference serving faces significant challenges in load balancing due to the inherent unpredictability of request workloads. Unlike traditional cloud tasks, LLM requests exhibit variable response lengths, dynamic memory consumption (KV cache), and high variance in decoding-step latency caused by batch-size fluctuations and inter-request interference.

Current multi-instance serving frameworks often rely on simple heuristics (e.g., round-robin) or reactive rebalancing strategies like live migration (e.g., Llumnix).

Heuristics: Fail to account for the specific load a new request will impose, leading to "herding" where multiple requests are routed to the same instance, causing transient overloads.
Live Migration: While effective at redistributing load, migrating KV caches between instances introduces substantial network, memory, and orchestration overhead. Under high load, these costs can accumulate, contend with normal serving traffic, and degrade tail latency or even collapse cluster performance.

The core challenge is to achieve high-quality load balancing in a multi-instance LLM cluster without relying on expensive migration or suffering from the "thundering herd" problem, while minimizing the control-plane overhead of the scheduler itself.

Methodology: Astrolabe

Astrolabe is a randomized, prediction-guided scheduler designed for one-shot request dispatch. It avoids migration by making high-quality placement decisions before execution based on simulated latency predictions.

System Architecture

The system consists of four main components:

Query Length Tagger: A lightweight service (using a fine-tuned RoBERTa regression model) that estimates the response length of an incoming request based on its prompt.
Global Scheduler: A stateless service that receives requests and selects a target instance.
Predictor Sidecars: Per-instance services that run alongside the inference backend. They query the local runtime state (e.g., running requests, memory blocks) and simulate the incoming request to estimate a target metric (default: End-to-End latency).
Inference Backends: The actual LLM serving frameworks (e.g., vLLM, SGLang) which are agnostic to the scheduling logic.

Core Dispatch Policy: Power-of-Two Choices (Po2)

Instead of querying all $N$ instances (full fanout), which incurs $O(N)$ control-plane costs and exacerbates herding, Astrolabe employs a Power-of-Two Choices strategy:

For each incoming request, the scheduler samples two random instances.
It queries the Predictor sidecars of these two instances in parallel.
The request is dispatched to the instance with the lower predicted latency.

This approach breaks the herding effect by randomizing the probe set (simultaneous requests are unlikely to sample the same pair) and reduces the per-request scheduling CPU cost by a factor of $\sim N/2$ compared to full fanout.

Prediction Mechanism

The Predictor sidecar utilizes a simulation-based approach (adapted from the Vidur framework) to estimate latency:

Input: The request prompt, the estimated response length, and the current local runtime state.
Process: It simulates the request through the local scheduler's batching logic and uses a linear model to predict execution times for the resulting batches.
Output: A scalar metric (e.g., expected E2E latency).
Robustness: The system handles prediction errors by relying on relative ranking between the two sampled candidates rather than absolute values. Common-mode errors (e.g., system noise) cancel out, and the system is designed to tolerate significant noise (up to 100% Gaussian noise in experiments) with minimal performance degradation.

Key Contributions

Analysis of Unpredictability: The paper identifies why runtime metrics (memory, throughput) are insufficient for LLM load balancing and highlights the specific "herding" issues caused by deterministic dispatch in high-variance environments.
Astrolabe System Design: It proposes and implements a one-shot, randomized scheduler that combines response-length estimation, per-instance simulation, and Po2 dispatch. This design achieves high-quality load balancing without live migration.
Comprehensive Evaluation: The authors evaluate Astrolabe across two clusters (12-GPU A30 and 2-node A100), two models (Llama-2-7B/70B, Qwen2-7B), and multiple datasets (ShareGPT, BurstGPT). They compare against five baselines (Random, Round-Robin, Min QPM, INFaaS++, Llumnix-) and analyze sensitivity to prediction errors, bursty traffic, and configuration shifts.

Experimental Results

Evaluated on a 12-GPU A30 cluster with Llama-2-7B and ShareGPT:

Capacity: Astrolabe matches the Service Level Objective (SLO) capacity of the best load-aware baseline (Llumnix- without migration) at 31.6 QPS (vs. 31.5 QPS).
Latency:
- Mean TTFT: 8–36% lower than the best baseline.
- P99 TTFT: 16–77% lower than the best baseline.
- Mean E2E: Up to 5.6% lower.
Stability: At capacity (QPS=32), Astrolabe experiences ~6× fewer preemptions (~~300) compared to Llumnix- (~~1,800).
Overhead: The per-predictor CPU utilization is reduced by ~2.8× compared to a full fanout approach.
Comparison with Migration (A100 Cluster): When compared to full Llumnix (with live migration enabled) on an A100 cluster, Astrolabe outperforms it by up to 2.6× in throughput at saturation and achieves orders-of-magnitude lower per-token latency. This demonstrates that migration overhead can collapse serving performance under high load.
Robustness: Astrolabe maintains performance under configuration shifts (different batch sizes, models, datasets) and is resilient to injected prediction noise.

Significance and Claims

The paper claims that Astrolabe demonstrates that prediction-guided one-shot dispatch can provide equal or better load balancing than migration-based rebalancing, while avoiding the substantial overhead of KV-cache transfers.

Key takeaways emphasized by the authors:

Migration is not always the answer: Under high load, the network and orchestration costs of migration can degrade tail latency and throughput more than the benefits of rebalancing.
Randomization is effective: The Power-of-Two Choices policy effectively mitigates request herding and reduces control-plane overhead without needing complex global state.
Simulation is viable: Despite the unpredictability of LLMs, simulation-based latency prediction combined with length estimation is accurate enough to drive effective scheduling decisions, even with imperfect predictors.

The authors conclude that Astrolabe offers a practical, scalable solution for multi-instance LLM serving that improves latency and throughput while remaining compatible with existing backends and avoiding the complexity of live migration.