Related papers: SeqRoute: Global Budget-Aware Sequential LLM Routing via Offline Reinforcement Learning

SeqRoute: Global Budget-Aware Sequential LLM Routing via Offline Reinforcement Learning

URL: http://arxiv.org/abs/2605.25424v1
Date: Mon, 25 May 2026 04:52:10 GMT
Title: SeqRoute: Global Budget-Aware Sequential LLM Routing via Offline Reinforcement Learning
Abstract summary: SeqRoute is a framework that formulates multi-turn routing as a finite-horizon Markov Decision Process.<n>It learns delayed gratification to strategically preserve resources for high-stakes turns later in the session.<n>It reduces operational costs by 6.0-73.5% while maintaining or improving quality, and suppresses bankruptcy rates to under 1%.
Score: 2.6853734738584047
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Existing LLM routing frameworks treat queries as independent events, neglecting the sequential nature of real-world user sessions constrained by global computational budgets. This mismatch inevitably leads to budget bankruptcy: myopic routing policies exhaust resources on early interactions, forcing subsequent and often more complex queries onto inadequate models. We introduce SeqRoute, a framework that formulates multi-turn routing as a finite-horizon Markov Decision Process and solves it via offline reinforcement learning. By incorporating the remaining budget into the state space and training with Conservative Q-Learning (CQL), SeqRoute learns delayed gratification to strategically preserve resources for high-stakes turns later in the session. To overcome data starvation, we propose Hindsight Budget Relabeling (HBR). This technique retrospectively simulates historical trajectories under diverse hypothetical budgets, expanding 10,000 raw sessions into 2.38 million transitions enriched with critical bankruptcy signals. At deployment, a dynamic $λ$-sweep mechanism enables zero-shot navigation of the cost-quality Pareto frontier without retraining. Extensive evaluations demonstrate that SeqRoute reduces operational costs by 6.0-73.5% while maintaining or improving quality, and suppresses bankruptcy rates to under 1%, strictly dominating behavior cloning, budget-aware heuristics, and static baselines across the entire Pareto frontier.

Related papers

A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing [0.0]
Vehicle routing problem with demands and outsourcing options (VRP-SDO)<n>We learn an offline routing policy that estimates costs almost instantly for any committed subset.<n> Experiments show that our policy reduces routing costs by 19.6% relative to a state-of-the-art method.
arXiv Detail & Related papers (2026-07-18T16:27:05Z)
RouteLMT: Learned Sample Routing for Hybrid LLM Translation Deployment [57.588738943463646]
Large Language Models (LLMs) have achieved remarkable performance in Machine Translation (MT)<n> deploying them at scale remains prohibitively expensive.<n>We propose textbfRouteLMT, an in-model router that predicts the expected gain by probing the small translators prompt-token representation.
arXiv Detail & Related papers (2026-04-24T13:02:45Z)
ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving [0.0]
LLM serving often relies on multi-model portfolios spanning a 530x cost range.<n>This trade-off is non-stationary; providers revise pricing, model quality can regress silently, and new models must be integrated without downtime.<n>We present an open-source adaptive router built on cost-aware contextual bandits.
arXiv Detail & Related papers (2026-03-31T18:41:53Z)
Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints [18.52522897906341]
We study the problem of routing queries to large language models (LLMs)<n>We propose a batch-level, resource-aware routing framework that jointly optimize assignment for each batch.<n> Experiments on two multi-task benchmarks show that improves accuracy by 1-14% on non-robust counterparts.
arXiv Detail & Related papers (2026-03-25T22:24:11Z)
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)
M$^2$: Dual-Memory Augmentation for Long-Horizon Web Agents via Trajectory Summarization and Insight Retrieval [64.06936170117943]
M$2$ is a training-free, memory-augmented framework designed to optimize context efficiency and decision-making.<n>Our approach incorporates a dual-tier memory mechanism that synergizes Dynamic Trajectory Summarization (Internal Memory) to compress verbose interaction history into concise state updates, and Insight Retrieval Augmentation (External Memory) to guide the agent with actionable guidelines retrieved from an offline insight bank.
arXiv Detail & Related papers (2026-02-28T06:59:51Z)
Budget-Aware Agentic Routing via Boundary-Guided Training [24.0709108941881]
Budget-Aware Agentic Routing selects between a cheap and an expensive model at each step to optimize the cost-success frontier.<n> Boundary-Guided Training builds a difficulty taxonomy to anchor learning under sparse rewards.<n>Experiment results show that our method improves the efficiency frontier, matching strong routing baselines at substantially lower cost.
arXiv Detail & Related papers (2026-02-04T07:39:27Z)
EvoRoute: Experience-Driven Self-Routing LLM Agent Systems [100.64399490164959]
EvoRoute is a self-evolving model routing paradigm that transcends static, pre-defined model assignments.<n> Experiments on challenging agentic benchmarks demonstrate that EvoRoute, when integrated into off-the-shelf agentic systems, not only sustains or enhances system performance but also reduces execution cost by up to $80%$ and latency by over $70%$.
arXiv Detail & Related papers (2026-01-06T04:06:46Z)
xRouter: Training Cost-Aware LLMs Orchestration System via Reinforcement Learning [104.63494870852894]
We present x, a tool-calling-based routing system in which a learned router can either answer directly or invoke one or more external models.<n>Our implementation encompasses the full reinforcement learning framework, including reward and cost accounting.<n>Across diverse benchmarks, x achieves strong cost-performance trade-offs.
arXiv Detail & Related papers (2025-10-09T16:52:01Z)
No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback.<n>It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time.<n>We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget
arXiv Detail & Related papers (2025-06-16T08:42:31Z)
Keeping Up with the Models: Online Deployment and Routing of LLMs at Scale [6.911384287238722]
We present a hierarchical algorithm that selects up to $M_max$ models for the next stage using reward upper-confidence and cost lower-confidence bounds.<n>We prove that StageRoute achieves a regret of order $T2/3$ and provide a matching lower bound, thereby establishing its near-optimality.
arXiv Detail & Related papers (2025-06-08T12:25:26Z)

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