Whose turn is it? Context-guided model routing for stateful agents

Anikesh Parashar; Avik Dutta; Vashu Chauhan; Sumit Gulwani; Priyanshu Gupta; Hosein Hasanbeig; Vu Le; Ashish Tiwari

cs.AIOct 13, 2026

Whose turn is it? Context-guided model routing for stateful agents

Authors: Anikesh Parashar, Avik Dutta, Vashu Chauhan, Sumit Gulwani, Priyanshu Gupta, Hosein Hasanbeig, Vu Le, Ashish Tiwari,

Organizations: Microsoft

Abstract

Model routing can reduce the cost of LLM applications by assigning simpler requests to cheaper models without sacrificing the quality of the response. However, most routers treat requests as independent. Stateful agents do not operate under this assumption: a user turn may require multiple model and tool calls, its difficulty depends on the state produced by earlier turns, and changing models can sacrifice reuse of the conversational prompt cache. We study zero-shot, cost-aware routing at the user-turn boundary, systematically varying the routing rule, access to session history, candidate models that differ in size, reasoning effort, or model provider, and prompt-cache behavior. We evaluate on multi-turn versions of SheetCopilot and SpreadsheetBench 2, where persistent workbooks and cross-turn dependencies make isolated routing decisions especially brittle. At a matched offloading rate, giving the router session history improves task pass rate over the same router without history, with gains for every model pair; history-aware routing remains within one point of always using the expensive model. We also found that cost depends on execution dynamics rather than token prices alone: the cheaper model's per-task cost advantage narrows from 6.8x to 3.2x on longer sessions. A closed form cache analysis further shows that downward switches (expensive to cheap) recover their cache cost within two LLM calls, whereas upward switches do not break even under the evaluated conditions. Together, these results show that agent routing is a sequential decision problem: effective policies must account for what happened earlier in the session and for the asymmetric cost of switching models.

Figures & tables

Panel of Figure 1 — Figure 1: Routing policies for multi-turn agents. (a) Before turn $t$ , a zero-shot LLM router $\pi$ reads the request $u_{t}$ and, when routing with history context, the serialized history $h_{t}$ (dashed). It assigns the whole turn to the cheap model $m_{c}$ ( simple ) or the expensive model $m_{e}$ ( complex , or on timeout, malformed output, or service failure); under escalation and de-escalation, every turn instead starts on $m_{c}$ or $m_{e}$ , respectively. Routing without history drops the history input, and without routing, one model serves the whole session (dotted line). The selected model owns every LLM call and tool interaction of the turn, and the runtime appends the resulting messages, tool observations, errors, workbook state, and routing decision to form $h_{t+1}$ ; models exchange no hidden states or provider-side KV tensors. (b) Illustrative assignments over a four-turn session.

Policy	When	Decision signal	Assignment and state behavior
Expensive-only / Cheap-only	Fixed	None	Assign $m_{e}$ / $m_{c}$ to every turn; the quality–cost endpoints.
LLM router, no history	Per-turn	$u_{t}$	Assign the entire multi-call loop for turn $t$ to either model from the current request alone; adopts the information set of request-level routers ( Ding et al., 2024 ; Ong et al., 2025 ) .
LLM router, with history	Per-turn	$(u_{t},h_{t})$	Same assignment, conditioned on the serialized session history. DialRouter and MTRouter are the closest history-aware precedents but are learned and route at different granularities ( Zhang et al., 2026a ; Zhang et al., 2026b ) .
Escalation	Within turn	$(u_{t},h_{t})$	Start every turn on $m_{c}$ ; hand the rest of the turn to $m_{e}$ if the router decides to escalate.
De-escalation	Within turn	$(u_{t},h_{t})$	Start every turn on $m_{e}$ ; hand the rest of the turn to $m_{c}$ if the router decides to de-escalate.
Random	Per-turn	None	Select a model at random before every turn; controls for switching without a decision signal ( Zhang et al., 2026b ) .

Table 1: Routing policies compared in our evaluation

Figure 2: Cost–quality tradeoff of the decision rules in Tables 3 and 4 ; rows are benchmarks, columns are candidate pairs, axes are scaled per panel. Colour gives the rule (legend), abbreviated at each marker as Exp, Chp, R

-

, R

+

, Esc, De, and Rnd. The filled wedge is

m_{c}

: empty

=0\%

, half

=50\%

, solid

=100\%

. The dashed curve traces all random mixes of the two pure candidates, and the shaded band above it is where a rule beats such a mix. A bold ring marks a Pareto-optimal rule and the dotted staircase joins them. Coincident markers are nudged apart for legibility.

Figure 3: Per-token price versus per-task cost. (a, b) SpreadsheetBench 2 single-model runs (repeated Sol runs averaged). (a) Arrows show the cost implied by GPT-5.6 Sol’s token usage at each model’s prices versus realized cost

\mathbb{E}[C_{i}]

, with the ratio in parentheses. (b) Pass rate

\mathbb{E}[Y_{i}]

versus realized cost; marker area denotes LLM calls per conversation and the dashed line the Pareto frontier. Haiku 4.5 makes about 1.6

\times

more calls and uses 1.7

\times

more input tokens, reducing its per-task discount to 3.2

\times

versus Sol; Luna costs about half as much as Haiku while passing 6 points more. Opus 4.8 at low effort is both cheaper and more accurate than at high effort. (c) Ratio of expensive-to-cheap

\mathbb{E}[C_{i}]

on SheetCopilot versus SpreadsheetBench 2; dotted lines show list-price ratios. Haiku’s discount shrinks with session length, while Luna’s remains stable.

Figure 4: Net cost of switching from Sol to Luna / Haiku per million uncached input tokens, as a function of LLM calls. The switch becomes cost-effective when net cost crosses zero.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Role	Model	Input	Cached	Output
Expensive	GPT-5.6 Sol	$5.00	$0.50	$30.00
Cheap, router	GPT-5.6 Luna	$1.00	$0.10	$6.00
Cheap	Haiku 4.5	$1.00	$0.10	$5.00
Expensive (high), cheap (low)	Opus 4.8	$5.00	$0.50	$25.00

Appendix

Table 2: Candidate models and prices per one million tokens.

	Sol / Haiku			Sol / Luna			Opus high / low
Policy	Pass	$m_{c}$	Cost	Pass	$m_{c}$	Cost	Pass	$m_{c}$	Cost
Expensive-only	27.7	0	0.364	25.9	0	0.341	29.5	0	0.365
Cheap-only	20.5	100	0.054	28.6	100	0.061	31.2	100	0.268
LLM router, no history	21.4	23.9	0.380	24.1	22.4	0.391	29.5	23.6	0.372
LLM router, with history	26.8	21.1	0.375	26.8	24.2	0.392	31.2	22.7	0.369
Escalation	24.1	97.8	0.112	27.7	90.4	0.130	26.8	99.4	0.467

Appendix

Table 3: Decision rules on SheetCopilot for the three candidate pairs. Pass: conversation-level pass rate, our estimate of

\mathbb{E}[Y_{i}]

(%).

m_{c}

: share of turns served by the cheap model (%); for escalation, turns never escalated; for de-escalation, turns handed to

m_{c}

. Cost: mean cost per task-run in dollars, our estimate of

\mathbb{E}[C_{i}]

, excluding the router call. LLM-router costs are exact only for Opus high/low, whose candidates share prices. Escalation, de-escalation, and random routing ran in a separate harness. Tasks: 112, except random (111) and de-escalation (110 for Sol/Haiku, 99 otherwise).

	Sol / Haiku			Sol / Luna			Opus high / low
Policy	Pass	$m_{c}$	Cost	Pass	$m_{c}$	Cost	Pass	$m_{c}$	Cost
Expensive-only	27.9	0	1.159	27.9	0	1.168	32.1	0	2.009
Cheap-only	15.8	100	0.367	27.4	100	0.193	36.7	100	1.081
LLM router, no history	26.0	1.5	1.179	22.3	1.5	1.158	35.8	1.7	1.993
LLM router, with history	27.8	0.4	1.192	27.8	0.7	1.208	32.4	1.7	2.080
Random	23.3	49.2	0.709	24.2	49.1	0.751	32.2	49.6	1.705

Appendix

Table 4: Decision rules on SSB-2 for the three candidate pairs. Pass: conversation-level pass rate, our estimate of

\mathbb{E}[Y_{i}]

(%).

m_{c}

: share of turns served by the cheap model (%); for escalation, turns never escalated; for de-escalation, turns handed to

m_{c}

. Cost: mean cost per task-run in dollars, our estimate of

\mathbb{E}[C_{i}]

, excluding the router call. LLM-router costs are exact only for Opus high/low, whose candidates share prices. Escalation, de-escalation, and random routing ran in a separate harness.

LLM Routing

Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.

See all 345 papers

MTRouter: Cost-Aware Multi-Turn LLM Routing with History-Model Joint Embeddings
Apr 26, 2026Yiqun Zhang, Hao Li, Zihan Wang +6Cost-Aware Inference LLM Routing
School of Computer Science and Engineering, Northeastern University Shenyang 110819, China · Shanghai Artificial Intelligence Laboratory
RSI-Router: Evolving Subtask-Level LLM Routing and Skills for Cost-Efficient Agents
Sep 28, 2026Hao Li, Hangfan Zhang, Zhiyao Cui +5Cost-Aware Inference LLM Agent Workflow Optimization
Shanghai Artificial Intelligence Laboratory · Northwestern Polytechnical University
AgentRouter: Heterogeneous Model Routing for Cost-Optimal Multi-Step Agentic Workflows
Sep 19, 2026Rudrendu Kumar Paul, Sourav NandyLLM Agent Routing Cost-Aware Inference
Boston University, Boston, MA, USA · University of Texas at Austin, Austin, TX, USA

Apr 26, 2026J/K move · Enter open · S save

MTRouter: Cost-Aware Multi-Turn LLM Routing with History-Model Joint Embeddings

Yiqun Zhang, Hao Li, Zihan Wang, Shi Feng+5

School of Computer Science and Engineering, Northeastern University Shenyang 110819, China · Shanghai Artificial Intelligence Laboratory

Cost-Aware Inference LLM Routing

Open paper AskPDF arXiv

Multi-turn, long-horizon tasks are increasingly common for large language models (LLMs), but solving them typically requires many sequential model invocations, accumulating substantial inference costs. Here, we study cost-aware multi-turn LLM routing: selecting which model to invoke at each turn from a model pool, given a fixed cost budget. We propose MTRouter, which encodes the interaction history and candidate models into joint history-model embeddings, and learns an outcome estimator from logged trajectories to predict turn-level model utility. Experiments show that MTRouter improves the performance-cost trade-off: on ScienceWorld, it surpasses GPT-5 while reducing total cost by 58.7%; on Humanity's Last Exam (HLE), it achieves competitive accuracy while reducing total cost by 43.4% relative to GPT-5, and these gains even carry over to held-out tasks. Further analyses reveal several mechanisms underlying its effectiveness: relative to prior multi-turn routers, MTRouter makes fewer model switches, is more tolerant to transient errors, and exhibits emergent specialization across models. Code: https://github.com/ZhangYiqun018/MTRouter

Abstract

LLM Routing

Explore similar work

MTRouter: Cost-Aware Multi-Turn LLM Routing with History-Model Joint Embeddings

RSI-Router: Evolving Subtask-Level LLM Routing and Skills for Cost-Efficient Agents

AgentRouter: Heterogeneous Model Routing for Cost-Optimal Multi-Step Agentic Workflows