PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhongling Xu, Shunan Zheng, Wei Wang

arXiv:2605.25424v1cs.LGcs.AI

TL;DR

Existing LLM routers generally treat queries independently, although real sessions share a global computational budget. SeqRoute formulates multi-turn routing as offline reinforcement learning, synthesizing budget-labeled trajectories and using a test-time λ-sweep. It reports lower costs with near-zero bankruptcy while outperforming behavior cloning across the cost-safety frontier.

  • Problem

    Existing routing frameworks treat queries independently rather than modeling real-world multi-turn sessions constrained by a global computational budget.

    Source: §1 · p. 1, §2.1 · p. 3

  • Method

    SeqRoute uses offline reinforcement learning on a finite-horizon MDP with remaining budget in the state, Hindsight Budget Relabeling, Conservative Q-Learning, and a deployment-time λ-sweep.

    Source: §1 · p. 2, §4.3 · p. 6

  • Results

    SeqRoute strictly dominates behavior cloning across the cost-safety frontier, reducing cost by up to 73.5% with 0.3% bankruptcy at λ = 5×10^-4.

    Source: §5.2 · p. 7

  • Takeaways & Limitations

    A single SeqRoute policy can navigate the cost-quality frontier at deployment without retraining for each budget level.

    Source: §1 · p. 2, §4.3 · p. 6

Abstract

from arXiv · show

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 $\lambda$-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.

1 Introduction

Existing routers optimize queries independently, while real sessions require decisions under a shared budget. SeqRoute treats routing as long-horizon planning and combines offline learning, budget relabeling, and test-time λ control.

1 Introduction

  • A single-turn router can spend heavily on an early easy query, leaving a later hard follow-up without enough budget for a capable model.The paper calls this failure budget bankruptcy.Source: §1 · p. 1
  • SeqRoute models multi-turn routing as a finite-horizon MDP whose state includes conversation context and remaining session budget.Its policy plans across turns, preserving resources for later high-stakes queries.Source: §1 · p. 2
  • A λ-sweep shifts the cost penalty at inference, letting one policy navigate the cost-quality frontier as deployment budgets vary.This avoids training separate policies for different budget levels.Source: §1 · p. 2
  • Hindsight Budget Relabeling expands recorded sessions into over 2.38 million bankruptcy-annotated transitions at no additional API cost, with a theoretical validity guarantee.Conservative Q-Learning penalizes out-of-distribution actions to discourage expensive calls in budget-impoverished states.Source: §1 · p. 2
  • SeqRoute reduces cost by up to 73.5% with near-zero bankruptcy and strictly dominates behavior cloning across the cost-safety frontier.The λ-sweep supports zero-shot navigation without retraining.Source: §1 · p. 2

2 Related Work

Prior work develops query-level routing, sequential orchestration, and conservative offline reinforcement learning, but the paper identifies session-wide budget management from static data as a distinct combination.

2.1 Evolution of LLM Routing Strategies

  • Routing research spans cascade and preference methods, confidence-aware signals, graph representations, contextual bandits, and retrieval-augmented or in-context settings.Examples include FrugalGPT [3], RouteLLM, and MixLLM [24].Source: §2.1 · p. 3
  • Existing routing methods commonly treat queries in isolation, leaving no mechanism to reason about cumulative costs across a multi-turn session.The paper positions holistic session-budget optimization from static offline data as its distinction from related sequential methods.Source: §2.1 · p. 3
  • Recent work adds token-budget control, selective reasoning, and multi-turn or multi-agent orchestration, but does not uniformly manage a global session budget.Examples include SelfBudgeter [16], GMTRouter [26], and RouteMoA [23].Source: §2.1 · p. 3

2.2 Offline Reinforcement Learning and Data Relabeling

  • Offline RL learns long-horizon policies from static datasets, but standard algorithms can overestimate out-of-distribution action values.Conservative Q-Learning penalizes such actions, whereas Implicit Q-Learning avoids querying unseen actions.Source: §2.2 · p. 3
  • Hindsight Experience Replay [1] relabels historical goals; SeqRoute adapts this principle by injecting hypothetical budget constraints into unconstrained logs.This addresses data starvation for budget-specific routing conditions.Source: §2.2 · p. 3

3 Problem Formulation

The formulation maximizes response quality subject to a global session cost budget, then incorporates the constraint into a finite-horizon MDP by tracking remaining budget in the state.

3 Problem Formulation

  • The objective is to maximize expected cumulative response quality while keeping expected total routing cost within the global session budget.The paper reformulates this constrained objective as a finite-horizon MDP by augmenting the state with remaining budget.Source: §3 · pp. 3–4
  • Each state combines a semantic embedding of conversation history with normalized remaining budget, and actions select between 8B and 70B models.The session starts with normalized budget 1.0; depletion ends the episode.Source: §3 · p. 4
  • Transitions combine stochastic conversation generation with deterministic budget depletion, and episodes end at four turns or when budget is depleted.The reward focuses on response quality and survival rather than step-wise operational cost.Source: §3 · p. 4
  • The reward uses ArmoRM-scored quality and applies a bankruptcy penalty of η = 5.0 when the next budget is depleted.The stated discount factor is γ = 0.99.Source: §3 · p. 4

4 Methodology: The SeqRoute Framework

SeqRoute treats multi-turn routing as an offline finite-horizon MDP whose state includes conversation context and remaining budget. It synthesizes budget-conditioned training data, uses conservative Q-learning for resource-aware decisions, and adjusts deployment trade-offs through a λ-sweep.

4.1 Data Synthesis via Hindsight Budget Relabeling (HBR)

  • HBR replays unconstrained logs under hypothetical budgets, adding bankruptcy signals and over 2.38 million transitions for offline training.Its validity argument relies on budget depletion being bookkeeping that does not alter model generations or user queries; the pipeline encodes history with MiniLM and appends normalized remaining budget to form a 385-dimensional state.Source: §4.1 · p. 5, Figure 1 · p. 5

4.2 Budget-Aware Offline RL via Conservative Q-Learning

  • CQL penalizes out-of-distribution actions, suppressing the value of costly 70B selections in low-budget states and favoring 8B without a hand-crafted rule.Because low-budget data rarely contains 70B selections, the conservative penalty suppresses that action more than 8B, producing delayed gratification through HBR bankruptcy signals and CQL conservatism.Source: §4.2 · pp. 5–6

4.3 Dynamic Inference via Lagrangian λ-Sweep

  • At inference, λ penalizes token cost in action selection, letting one CQL-trained policy trace the feasible cost-quality Pareto frontier without retraining.Sweeping λ shifts the cost penalty at deployment; near zero favors quality subject to the session budget, while larger values trade marginal quality for frugality.Source: §4.3 · p. 6

5 Experiments

The experiments evaluate SeqRoute against routing baselines and ablations, testing cost-safety performance, delayed gratification, HBR, and explicit budget state. Across the reported results, CQL offers a cost-safety frontier, while budget-conditioned behavior depends on the training data and state representation.

5.1 Experimental Setup

  • On the held-out 10k-episode test split, evaluation sweeps λ at inference and measures session cost, bankruptcy rate, 70B usage, and logged-path quality.Baselines include Always-8B, Always-70B, random routing, and a budget-aware heuristic.Source: §5 · p. 6, §5.1 · p. 7

5.2 Main Results: Cost-Safety Pareto Frontier (RQ1)

  • CQL at λ=0 achieves 6.0% lower cost (3275 vs. 3482), 7.5 percentage points lower bankruptcy (24.3% vs. 31.8%), and higher quality return (−3.44 vs. −3.65) than BC.At λ=5×10−4, bankruptcy is 0.3% at cost 921, a 73.5% cost reduction vs. BC; the Table 1 caption describes the final-test comparison.Source: Table 1 · p. 7, §5.2 · p. 7

5.3 Behavioral Analysis: Delayed Gratification (RQ2)

  • CQL conditions 70B use on remaining budget and retains 41.6% of initial budget after five steps, versus 34.5% for BC.CQL's budget-sensitivity slope is +0.13, versus +0.02 for BC and −0.01 for the no-budget-state variant; λ shifts 70B use from 31.1% to 7.8%.Source: §5.3 · pp. 7–8, Figure 3 · p. 8

5.4.1 Hindsight Budget Relabeling

  • At B0 = 1500, no-HBR uses the strong model more often (66.9% vs. 57.3%) and has higher bankruptcy (83.3% vs. 79.4%) than HBR.At B0 = 3000, HBR reduces cost by 5.5% (2590 vs. 2742); at higher budgets the models converge in cost, while no-HBR has modestly lower bankruptcy.Source: §5.4.1 · pp. 8–9, Table 2 · p. 9

5.4.2 Budget State Ablation

  • Without the budget dimension, strong-model use at λ=0 rises to 58.5% from 39.3%, and bankruptcy is substantially higher across cost penalties.The no-budget agent needs roughly double the cost for comparable safety: at λ=0.0005, cost is 1762 vs. 921.Source: §5.4.2 · p. 9, Table 3 · p. 9

6 Conclusion

The conclusion presents SeqRoute as an offline RL framework for budget-constrained multi-turn routing, combining budget relabeling, conservative learning, and test-time λ control. It reports cost-safety and behavioral gains, while noting limits in reward proxies and model coverage.

6 Conclusion

  • SeqRoute combines HBR-generated budget-annotated trajectories, CQL, and a λ-sweep for zero-shot Pareto navigation at deployment.Source: §6 · p. 9
  • At λ=0, SeqRoute lowers cost by 6.0% and bankruptcy by 7.5pp versus BC; λ-sweep reduces cost by up to 73.5% with near-zero bankruptcy.Source: §6 · p. 9
  • Behavioral analysis finds that SeqRoute suppresses strong-model use in budget-tight states, while BC does not learn this behavior.Source: §6 · p. 9
  • The evaluation relies on offline reward proxies and a single model pair; the authors identify online validation and multi-tier model ecosystems as future work.Source: §6 · p. 9

A.1 Data Generation

The appendix describes how the authors create counterfactual multi-turn data, score responses, and construct state representations for training and evaluation.

A.1 Data Generation

  • The seed pool contains 10,000 first-turn queries from ShareGPT, WildChat, and Chatbot Arena, filtered to 5–1000 words and shuffled.For turns 1–4, both Llama-3.1-8B-Instruct and Llama-3.1-70B-Instruct-AWQ generate responses; a shadow simulator generates follow-up queries for both branches.Source: §A.1 · p. 12
  • Responses are scored with ArmoRM-Llama3-8B, and HBR replays trajectories under five virtual budgets with bankruptcy penalty η = 5.0.Source: §A.1 · p. 12

A.2 State Representation and Training

  • Each observation concatenates a 384-dimensional MiniLM context embedding with normalized remaining budget, producing a 385-dimensional state.The data is deterministically split 80%/10%/10% for training, validation, and sealed final testing; CQL and BC use the same three-layer MLP architecture.Source: §A.2 · p. 12

B HBR Details and Dataset Statistics

HBR replays counterfactual rollout paths under alternative initial budgets and marks bankruptcy as terminal. The resulting dataset contains over 2.38 million HBR-augmented transitions.

B HBR Details and Dataset Statistics

  • For each leaf path, HBR replays the trajectory under five initial budgets, decrementing budget by step cost and marking nonpositive remaining budget terminal with reward −5.0.The stated step costs are 1× tokens for the weak model and 10× for the strong model.Source: B HBR Details and Dataset Statistics · p. 12
  • HBR expands 476,632 raw transitions from 10,000 sessions to 2,383,158 transitions; the dataset has 486,841 total episodes and a 15.3% bankruptcy rate.Bankruptcy varies by budget tier, from 38.2% at B0 = 500 to 3.1% at B0 = 8000.Source: B HBR Details and Dataset Statistics · p. 12

C HBR Ablation: Multi-Budget Analysis

HBR’s budget generalization advantage is strongest under stringent budgets; at higher budgets, its cost advantage narrows and no-HBR has somewhat lower bankruptcy rates.

C HBR Ablation: Multi-Budget Analysis

  • At B0 = 1500, no-HBR uses the strong model 66.9% vs. 57.3% and has a 3.9pp higher bankruptcy rate than HBR.The passage describes this as the most stringent budget and reports that no-HBR incurs higher cost.Source: C HBR Ablation: Multi-Budget Analysis · p. 12
  • 5.5% lower cost for HBR at B0 = 3000 shows its cost advantage persists at moderate budgets.The passage does not specify which variant has lower cost in this clause, so the comparison is stated as reported for HBR.Source: C HBR Ablation: Multi-Budget Analysis · p. 13
  • At higher budgets, the variants converge in cost, while no-HBR achieves somewhat lower bankruptcy rates, a modest in-distribution advantage at the training budget.The passage characterizes HBR’s practical advantage as robustness at tight budgets, where bankruptcy risk is highest.Source: C HBR Ablation: Multi-Budget Analysis · p. 13

D State Space Ablation Variants

The state-space ablation compares log-budget and budget-bin encodings with the retained linear encoding, finding that outcomes vary by representation and budget penalty.

D State Space Ablation Variants

  • The two budget alternatives are log-budget, b′_t = log(b_t + 10^-6), with dimensionality 385, and budget-bins, a 10-bin one-hot encoding of b_t with dimensionality 394.Source: D State Space Ablation Variants · p. 13
  • At λ = 0, budget-bins encoding achieves cost 2469 and BR 25.2%, while log-budget encoding has cost 5048, BR 65.0%, and 94.2% 70B usage.The passage says budget-bins has comparable safety to linear encoding with moderately lower cost, while log-budget compresses budget differences too aggressively.Source: D State Space Ablation Variants · p. 13
  • At higher λ values, all encodings converge to Always-8B behavior, and linear encoding is retained for simplicity and consistent performance.The passage notes that discrete budget representations merit further study.Source: D State Space Ablation Variants · p. 13

E Multi-Seed Training Stability

CQL’s reported advantage over behavior cloning is stable across seeds; this block also reports preliminary OOD transfer, persona-driven rollout prompts, and deployment trade-offs.

E Multi-Seed Training Stability

  • At λ = 0, CQL has mean cost 3338 ± 95, mean BR 24.4 ± 0.5%, and mean 70B usage 40.3 ± 1.7%, versus BC’s 3543 ± 53, 32.4 ± 0.6%, and 48.8 ± 1.6%.CQL strictly dominates BC across all seeds with low inter-seed variance.Source: E Multi-Seed Training Stability · p. 13

F Out-of-Domain Generalization

  • Preliminary evaluation on a held-out coding/math subset suggests near-zero bankruptcy under modest distribution shift, while systematic cross-domain evaluation is deferred.The current evaluation focuses on in-domain data from the ShareGPT, WildChat, and Chatbot Arena distribution.Source: F Out-of-Domain Generalization · p. 13

G Shadow Simulator Prompts

  • The counterfactual rollout uses an 8B shadow simulator with 12 randomly sampled critical personas to generate diverse follow-up queries.The persona prompts include roles such as a critical software engineer, skeptical academic, security auditor, and confused user.Source: G Shadow Simulator Prompts · pp. 13–14

H Broader Impacts

  • A high deployment λ may lead users to consistently receive lower-quality weak-model responses, while the λ-sweep lets operators choose a Pareto-frontier point post hoc.The passage also states that offline RL avoids online exploration that could expose users to degraded service quality.Source: H Broader Impacts · p. 14
Loading 2605.25424v1…