# Lodestar: An Online-Learning LLM Inference Router

arXiv: https://arxiv.org/abs/2606.00946 · HTML: https://mlsanity.com/paper/2606.00946/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 62 references that are in the map.
- First posted on arXiv 31 May 2026.

## Builds on (most cited first, 30 of 33)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset](https://mlsanity.com/paper/2309.11998/) (2023)
- [DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale](https://mlsanity.com/paper/2207.00032/) (2022)
- [Prompt Cache: Modular Attention Reuse for Low-Latency Inference](https://mlsanity.com/paper/2311.04934/) (2023)
- [InfiniGen: Efficient Generative Inference of Large Language Models with Dynamic KV Cache Management](https://mlsanity.com/paper/2406.19707/) (2024)
- [Fast Distributed Inference Serving for Large Language Models](https://mlsanity.com/paper/2305.05920/) (2023)
- [LMCache: An Efficient KV Cache Layer for Enterprise-Scale LLM Inference](https://mlsanity.com/paper/2510.09665/) (2025)
- [Serving DNNs like Clockwork: Performance Predictability from the Bottom Up](https://mlsanity.com/paper/2006.02464/) (2020)
- [GCR: Gradient Coreset Based Replay Buffer Selection For Continual Learning](https://mlsanity.com/paper/2111.11210/) (2021)
- [NanoFlow: Towards Optimal Large Language Model Serving Throughput](https://mlsanity.com/paper/2408.12757/) (2024)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [TurboTransformers: An Efficient GPU Serving System For Transformer Models](https://mlsanity.com/paper/2010.05680/) (2020)
- [Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads](https://mlsanity.com/paper/2008.09213/) (2020)
- [Helix: Serving Large Language Models over Heterogeneous GPUs and Network via Max-Flow](https://mlsanity.com/paper/2406.01566/) (2024)
- [KVCache Cache in the Wild: Characterizing and Optimizing KVCache Cache at a Large Cloud Provider](https://mlsanity.com/paper/2506.02634/) (2025)
- [Prism: Cost-Efficient Multi-LLM Serving via GPU Memory Ballooning](https://mlsanity.com/paper/2505.04021/) (2025)
- [PrefillOnly: An Inference Engine for Prefill-only Workloads in Large Language Model Applications](https://mlsanity.com/paper/2505.07203/) (2025)
- [JITServe: SLO-aware LLM Serving with Imprecise Request Information](https://mlsanity.com/paper/2504.20068/) (2025)
- [Prefill-as-a-Service: KVCache of Next-Generation Models Could Go Cross-Datacenter](https://mlsanity.com/paper/2604.15039/) (2026)
- [Hetis: Serving LLMs in Heterogeneous GPU Clusters with Fine-grained and Dynamic Parallelism](https://mlsanity.com/paper/2509.08309/) (2025)
- [DynaServe: Unified and Elastic Execution for Dynamic Disaggregated LLM Serving](https://mlsanity.com/paper/2504.09285/) (2025)
- [Towards Efficient and Practical GPU Multitasking in the Era of LLM](https://mlsanity.com/paper/2508.08448/) (2025)

## Abstract (arXiv)

Efficiently serving large language model (LLM) inference tasks is crucial both for user-perceived latency such as time-to-first-token (TTFT) and for GPU utilization. However, LLM request routing, that is, assigning each inference request to a GPU instance, is particularly challenging: execution is highly input-dependent; batching and KV-cache reuse create strong cross-request coupling; and latency responds nonlinearly to context length, model/engine settings, and heterogeneous accelerators. As a result, simple traditional load balancing algorithms, and even heuristics tailored for LLM inference, fail to achieve good performance. We present Lodestar, a novel learning-based request routing system for distributed GPU clusters. Lodestar continuously collects a snapshot of the cluster at per-request level, including real-time instance state, request characteristics, and observed performance, and trains an online reward predictor that it uses to route inference requests to the instance that will maximize given reward (e.g., minimizing TTFT). Lodestar is cloud-native and works seamlessly with existing serving stacks (vLLM). With continuous online adaptation to changing workloads and infrastructure conditions, Lodestar achieves 1.41x lower average TTFT and 1.47x lower P99 TTFT on average (up to 2.15x/1.86x on homogeneous and 4.38x/4.42x on heterogeneous clusters) compared to a state-of-the-art prefix cache and load-aware heuristic, and learns these efficient routing strategies within about 5 minutes, based on experiments in a public cloud GPU cluster.