Online Linear Programming for Multi-Objective Routing in LLM Serving

• URL: http://arxiv.org/abs/2607.03948v1
• Date: Sat, 04 Jul 2026 16:48:37 GMT
• Title: Online Linear Programming for Multi-Objective Routing in LLM Serving
• Abstract summary: We study the online routing problem in large language model serving.<n>We introduce a multi-objective optimization framework that formulates routing as an online linear programming with interpretable decision rewards.<n>A big picture from our result: a science-based approach outperforms others based on millisecond decodes.
• Score: 9.541681114575812
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the online routing problem in large language model serving, where requests arrive sequentially and must be dispatched to parallel decode workers under tight batch-size and KV-cache constraints. Unlike widely used routing heuristics that are not tied to explicit service-level objectives (SLOs) and offer limited control over latency-throughput trade-offs, we introduce a multi-objective optimization framework that formulates routing as an online linear programming with interpretable decision rewards. We apply an efficient bid-price control policy based on the online linear programming that admits requests when their SLO-weighted benefit exceeds their shadow prices. To meet millisecond decision requirements, we develop a warm-started, projected first-order updates that track the evolving dual shadow prices online with predictable runtime. We integrate our router into the Vidur simulator and demonstrate substantial improvements over standard baselines across multiple SLO regimes, including end-to-end latency, time-to-first-token, throughput, and tail performance. A big picture from our result: a science-based approach outperforms others based on heuristics.

Related papers

• End-to-End Latency-Minimizing and Load-Balanced Request Scheduling for Edge LLM Inference in Agentic AI Services [13.04369901641143]
  Large language model (LLM)-powered agentic AI services increasingly demand low-latency inference.<n>We develop a cross-slot inference model that captures transmission, prefill, redistribution-level decoding, and key-value cache evolution for each diverse request.<n>We propose the LYREO approach that transforms the long-term load-balancing constraint via Lyapunov optimization and employs reward with sequencebased return prediction.
  arXiv  Detail & Related papers  (2026-09-15T13:50:54Z)
• Goal-Conditioned Supervised Learning for LLM Fine-Tuning [10.43951412455864]
  We propose goal-conditioned supervised learning as an offline fine-tuning framework for large language models.<n>Our core idea is to treat feedback signals directly as an explicit goal and train the model, purely through supervised learning, to generate responses that achieve that goal.
  arXiv  Detail & Related papers  (2026-05-08T01:55:40Z)
• Efficient and Interpretable Multi-Agent LLM Routing via Ant Colony Optimization [58.59491516762626]
  We propose AMRO-S, an efficient and interpretable routing framework for Multi-Agent Systems (MAS)<n>AMRO-S models MAS routing as a semantic-conditioned path selection problem, enhancing routing performance through three key mechanisms.<n>Extensive experiments on five public benchmarks and high-concurrency stress tests demonstrate that AMRO-S consistently improves the quality--cost trade-off over strong routing baselines.
  arXiv  Detail & Related papers  (2026-03-13T12:26:05Z)
• Multi-task Offline Reinforcement Learning for Online Advertising in Recommender Systems [54.709976343045824]
  Current offline reinforcement learning (RL) methods face substantial challenges when applied to sparse advertising scenarios.<n>We propose MTORL, a novel multi-task offline RL model that targets two key objectives.<n>We employ multi-task learning to decode actions and rewards, simultaneously addressing channel recommendation and budget allocation.
  arXiv  Detail & Related papers  (2025-06-29T05:05:13Z)
• CITER: Collaborative Inference for Efficient Large Language Model Decoding with Token-Level Routing [74.14816777318033]
  Collaborative Inference with Token-lEvel Routing (CITER) is a framework that enables efficient collaboration between small and large language models.<n>We formulate router training as a policy optimization, where the router receives rewards based on both the quality of predictions and the inference costs of generation.<n>Our experiments show that CITER reduces the inference costs while preserving high-quality generation, offering a promising solution for real-time and resource-constrained applications.
  arXiv  Detail & Related papers  (2025-02-04T03:36:44Z)
• AdaServe: Accelerating Multi-SLO LLM Serving with SLO-Customized Speculative Decoding [12.106234303559571]
  We present AdaServe, the first serving system designed to support efficient multi-SLO serving through SLO-customized speculative decoding.<n>AdaServe formulates multi-SLO serving as a constrained optimization problem and introduces a hardware-aware algorithm.<n>It features a speculate-select-verify pipeline that enables fine-grained control over decoding speed while maximizing system throughput.
  arXiv  Detail & Related papers  (2025-01-21T14:15:01Z)
• HyGen: Efficient LLM Serving via Elastic Online-Offline Request Co-location [6.727166537196941]
  Large language models (LLMs) have facilitated a wide range of applications with distinct service-level objectives (SLOs)<n>Existing deployment model, which dedicates machines to each workload, simplifies SLO management but often leads to poor resource utilization.<n>This paper introduces HyGen, an interference-aware LLM serving system that enables efficient co-location of online and offline workloads.
  arXiv  Detail & Related papers  (2025-01-15T16:32:27Z)
• ConServe: Fine-Grained GPU Harvesting for LLM Online and Offline Co-Serving [61.35068981176018]
  ConServe is a large language model (LLM) serving system that achieves high throughput and strong online latency guarantees.<n>We show that ConServe delivers an average of 2.2$times$ higher throughput and reduces online serving tail latency by 2.9$times$ on average compared to state-of-the-art systems.
  arXiv  Detail & Related papers  (2024-10-02T04:12:13Z)
• ENOTO: Improving Offline-to-Online Reinforcement Learning with Q-Ensembles [52.34951901588738]
  We propose a novel framework called ENsemble-based Offline-To-Online (ENOTO) RL. By increasing the number of Q-networks, we seamlessly bridge offline pre-training and online fine-tuning without degrading performance. Experimental results demonstrate that ENOTO can substantially improve the training stability, learning efficiency, and final performance of existing offline RL methods.
  arXiv  Detail & Related papers  (2023-06-12T05:10:10Z)
• Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints [27.84415856657607]
  We propose a new machine learning (ML) assisted unrolling approach, called LAAU (Learning-Assisted Algorithm Unrolling) For efficient training via backpropagation, we derive gradients of the decision pipeline over time. We also provide the average cost bounds for two cases when training data is available offline and collected online, respectively.
  arXiv  Detail & Related papers  (2022-12-03T20:56:29Z)
• A Graph Neural Networks based Framework for Topology-Aware Proactive SLA Management in a Latency Critical NFV Application Use-case [0.34376560669160383]
  Recent advancements in 5G and 6G have led to the emergence of latency-critical applications delivered via a Network-series (NFV) enabled paradigm. We propose a proactive SLA management framework leveraging Graph Neural Networks (GNN) and Deep Reinforcement Learning (DRL) to balance the trade-off between efficiency and reliability.
  arXiv  Detail & Related papers  (2022-11-10T23:22:05Z)
• JUMBO: Scalable Multi-task Bayesian Optimization using Offline Data [86.8949732640035]
  We propose JUMBO, an MBO algorithm that sidesteps limitations by querying additional data. We show that it achieves no-regret under conditions analogous to GP-UCB. Empirically, we demonstrate significant performance improvements over existing approaches on two real-world optimization problems.
  arXiv  Detail & Related papers  (2021-06-02T05:03:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.