Truthful and Expected-Payment-Optimal Model Routing in Graph-Based Agentic Workflows

Jiayuan Liu; Mingyu Guo; Jiarui Gan; Vincent Conitzer

cs.GTOct 13, 2026

Truthful and Expected-Payment-Optimal Model Routing in Graph-Based Agentic Workflows

Authors: Jiayuan Liu, Mingyu Guo, Jiarui Gan, Vincent Conitzer

Organizations: Carnegie Mellon University · Foundations of Cooperative AI Lab (FOCAL) · Adelaide University · University of Oxford

Abstract

Assigning routine tasks to cheaper large language model (LLM) providers can reduce generation cost, but switching providers may require processing accumulated context again. Keeping dependent tasks with the same provider can instead reuse eligible context. Graph-based workflows therefore couple routing decisions across tasks. Independent providers may also privately know their real-time unit costs and strategically misreport them. We formulate this routing problem as a single-parameter procurement auction and propose STAR (Strategy-proof Topology-aware Agent Routing), which minimizes virtual-cost-weighted graph workloads. Its allocation rule and payments, computed by integrating workload over possible cost reports, make truthful reporting utility-maximizing regardless of other providers' reports and cover each truthful provider's execution cost. With independent cost distributions and non-decreasing virtual costs, STAR additionally minimizes the user's expected total payment to providers. Controlled synthetic experiments separate the execution-cost benefit of topology awareness from the payment benefit of virtual-cost optimization: the former grows with fan-out and transferred payload, while the latter increases gradually along the tested prior-shape heterogeneity path. A paired sensitivity study quantifies how payment savings vary with prior misspecification while strategy-proofness is preserved.

Figures & tables

Figure 1: Star overview. Star assigns a fixed workflow’s tasks to eligible model providers and determines their payments. Providers privately know unit costs $c_{i}$ ; assignment-dependent workloads include generation and upstream-context processing with eligible reuse. Star uses reported costs $b_{i}$ to optimize virtual-cost-weighted workloads and compute payments that make truthful reporting utility-maximizing and cover truthful providers’ execution costs. The figure uses $w_{i}=q_{i}(A)$ and, because of strategy-proofness, depicts truthful cost reports $b_{i}=c_{i}$ . With independent, correctly specified cost priors and non-decreasing virtual costs, Star minimizes the user’s expected total payment among truthful, cost-covering mechanisms.

Figure 2: Payment savings under heterogeneous regular priors. A: Each point is one of the 24 pre-specified structural cells for the indicated prior profile; the larger marker and range summarize the cell-level point estimates, and the annotation reports how many paired 95% intervals are strictly above zero. B: In the representative degree-100 high-payload graph, Star ’s payment reduction along the continuous prior-shape path. Provider supports, graph semantics, and latent cost quantiles remain fixed; the band denotes a paired-bootstrap 95% confidence interval.

Prior profile	Reduction range	Positive cells
Uniform	1.49%–3.34%	2/24
Heterogeneous mild	10.23%–10.30%	24/24
Heterogeneous strong	21.99%–31.48%	24/24

Table 1: Star payment reductions across prior profiles. Ranges are the minimum and maximum point estimates over all 24 pre-specified structural cells; all cells are retained. A positive cell has a paired-bootstrap 95% interval strictly above zero.

True cost distribution	Correct-prior Star reduction (95% CI)	$\|\delta\|$	Negative-direction error $\delta=-\|\delta\|$ (95% CI)	Positive-direction error $\delta=+\|\delta\|$ (95% CI)
Uniform	0.79% [0.31,1.25]	0.05	0.85% [0.28,1.38]	0.72% [0.26,1.15]
		0.1	0.71% [0.07,1.32]	0.56% [0.10,0.97]
		0.2	0.34% [-0.54,1.16]	0.20% [-0.31,0.69]
Heterogeneous power priors	30.04% [27.88,32.21]	0.05	30.01% [27.84,32.14]	29.98% [27.79,32.09]
		0.1	30.15% [28.02,32.29]	29.92% [27.76,32.03]
		0.2	30.16% [28.06,32.27]	30.13% [27.93,32.23]

Table 2: User-payment savings (%) under prior-estimation errors. All three result columns and their bracketed paired 95% bootstrap confidence intervals show the user’s total-payment savings relative to Raw-DSIC in percent:

100(1-\overline{P}_{\textsc{Star}}/\overline{P}_{\mathrm{Raw}})\%

. Positive values mean lower user payments. The perturbation magnitude

|\delta|

is dimensionless. Only assumed shapes change:

\widehat{k}_{i}=k_{i}e^{\delta r_{i}}

, with fixed

r=(1,-1,0,1,-1)

. Uniform uses

k_{i}=1

for every provider; heterogeneous power priors use

k=(0.5,2,0.2,5,1)

. Each three-row group shares 1,000 cost draws and correct-prior and Raw-DSIC baselines; the merged correct-prior entry applies to all three magnitudes. True distributions, graph, and cost ranges stay fixed. Appendix I.7 provides payment details.

Control	Execution cost reduction	Paired 95% CI
Low payload (ratio 1)	2.13%	[1.16%, 3.24%]
Higher payload (ratio 16)	67.47%	[66.12%, 68.48%]
No cache advantage ( $\kappa=1$ )	0.00%	[0.00%, 0.00%]

Table 3: Degree-100 fan-out controls (

\rho=1/3

, uniform priors). Ratio is transferred context per edge divided by each child’s

20,000

-token output: ratios 1 and 16 transfer

20,000

and

320,000

tokens, respectively, with

\kappa=0.1

; the no-cache row transfers

1,000,000

tokens with

\kappa=1

. Hub output is

1,000,000

tokens throughout. Table 8 instead uses ratio 50 and

\kappa=0

. Reductions compare graph-aware Raw-DSIC execution cost with Myopic; intervals are paired-bootstrap 95% confidence intervals. The

\kappa=1

zeros are exact, not rounded: without reuse discounts and with common

\rho

, Raw-DSIC and Myopic attain the same execution cost.

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Tier	Base-cost anchors	Providers
Tier 1	$0.10,$ 0.20, $0.30	3
Tier 2	$0.50,$ 1.00, $1.50	3
Tier 3	$2.50,$ 5.00, $7.50	3

Appendix

Table 4: Synthetic base-cost anchors in dollars per million standardized output-workload units.

Setting	Role	Count	Difficulty	Nominal output (k)
S1	Planner	5	1	300 each
	Writers	15 (3 per stage)	2	40 each
	Aggregator	5	1	50 each
	Final Editor	1	1	20
S2	Scanner / Analyzer / Planner	1 each	1 / 2 / 3	3 / 5 / 8
	SpecGenerator	1	1	350

Appendix

Table 5: Nominal synthetic workflow configurations. S1 repeats the Planner–Writers–Aggregator stage five times. In S2, the Scanner root context is sampled from the configured truncated-Pareto range, and the Merger receives all 30 file outputs, giving approximately 450k nominal fan-in tokens. The S3 Architect root input has 5k nominal tokens. The S4 Expert Assessment root input has 50k nominal tokens.

Panel of Figure 3 — Figure 3: S1: Repeated Broadcasters. Five repeated stages each contain one Diff-1 planner broadcasting a 300k-token plan to three Diff-2 writers, followed by a Diff-1 aggregator. The grouped writer boxes represent three parallel nodes per stage; stages 2–4 are omitted visually but are instantiated in the generator.

Panel of Figure 4 — Figure 4: S2: Nested Fan-Out. A Diff-1 SpecGenerator broadcasts a 350k-token specification to ten modules, which decompose into thirty file tasks. All thirty file outputs feed the Merger, producing approximately 450k nominal fan-in tokens.

Panel of Figure 5 — Figure 5: S3: Two-Level Team Fan-Out. A Diff-1 SpecWriter broadcasts a 300k-token specification to three Diff-2 team leads, which route work to twelve developers with heterogeneous capability requirements.

Panel of Figure 6 — Figure 6: S4: Hourglass. A Diff-1 Case Retriever broadcasts a 400k-token payload to five analysts. Their outputs contract at a Diff-1 aggregator, expand to three Diff-2 strategists, and reconverge at the final Diff-3 synthesis node.

Workflow	Payment reduction	Paired 95% CI
S1	1.44%	[0.14%, 2.72%]
S2	0.36%	[-0.39%, 1.13%]
S3	0.91%	[0.07%, 1.79%]
S4	0.92%	[0.11%, 1.71%]

Appendix

Table 6: Synthetic S1–S4 uniform-prior boundary reference. Intervals are paired-bootstrap 95% confidence intervals for Star relative to graph-aware Raw-DSIC.

Provider ID	Capability tier	Unit-cost range ($/million work units)		Uniform $k_{i}$	Mild $k_{i}$	Strong $k_{i}$
		$a_{i}$	$d_{i}$
0	1	0.05	0.50	1.0	0.5	0.5
1	1	0.10	0.80	1.0	2.0	2.0
2	2	0.25	1.40	1.0	0.5	0.2
3	2	0.35	1.10	1.0	1.0	5.0
4	2	0.45	1.25	1.0	2.0	1.0

Appendix

Table 7: Fixed provider cost ranges and distribution shapes for the structural-prior stress suite. Work units are the standardized workloads in Eq. ( 3 ). The cost ranges stay fixed across profiles; the listed shape parameters determine the virtual costs

\phi_{i}(c)=(1+1/k_{i})c-a_{i}/k_{i}

Cell	Topology	Degree	$\rho$	Paired trials
C01	Fanout	1	$1/3$	50
C02	Fanout	1	1.00	50
C03	Fanout	10	$1/3$	50
C04	Fanout	10	1.00	50
C05	Fanout	30	$1/3$	50
C06	Fanout	30	1.00	50

Appendix

Table 8: The 24 frozen structural cells used separately under each of the uniform, mild, and strong prior profiles. The fixed settings are

\kappa=0.0

, a transferred payload of

1,000,000

tokens, a generated hub payload of

1,000,000

tokens, and child outputs of

20,000

tokens.

Topology	Degree	$\rho$	Star –Raw payment	Paired 95% CI	Raw–Myopic execution	Paired 95% CI
Fanout	1	$1/3$	3.34%	[0.52%, 6.07%]	1.77%	[0.57%, 3.31%]
Fanout	1	1.00	1.49%	[-0.36%, 3.41%]	24.15%	[20.89%, 27.28%]
Fanout	10	$1/3$	1.49%	[-0.44%, 3.49%]	67.79%	[66.31%, 68.86%]
Fanout	10	1.00	1.49%	[-0.39%, 3.48%]	87.84%	[87.16%, 88.34%]
Fanout	30	$1/3$	1.49%	[-0.46%, 3.48%]	84.60%	[83.79%, 85.19%]
Fanout	30	1.00	1.49%	[-0.37%, 3.41%]	94.47%	[94.12%, 94.71%]

Appendix

Table 9: Complete frozen structural-grid results for the uniform prior. Payment columns compare Star with graph-aware Raw-DSIC; execution columns compare graph-aware Raw with Myopic. All 24 pre-specified cells are retained, and intervals are paired-bootstrap 95% confidence intervals.

Topology	Degree	$\rho$	Star –Raw payment	Paired 95% CI	Raw–Myopic execution	Paired 95% CI
Fanout	1	$1/3$	10.30%	[3.26%, 16.70%]	2.27%	[0.71%, 4.17%]
Fanout	1	1.00	10.23%	[3.42%, 16.73%]	22.65%	[18.73%, 26.62%]
Fanout	10	$1/3$	10.23%	[3.26%, 16.47%]	67.75%	[66.33%, 68.85%]
Fanout	10	1.00	10.23%	[2.85%, 16.82%]	87.92%	[87.29%, 88.35%]
Fanout	30	$1/3$	10.23%	[3.45%, 16.98%]	84.68%	[83.88%, 85.21%]
Fanout	30	1.00	10.23%	[3.25%, 16.81%]	94.52%	[94.22%, 94.72%]

Appendix

Table 10: Complete frozen structural-grid results for the heterogeneous mild prior. Payment columns compare Star with graph-aware Raw-DSIC; execution columns compare graph-aware Raw with Myopic. All 24 pre-specified cells are retained, and intervals are paired-bootstrap 95% confidence intervals.

Topology	Degree	$\rho$	Star –Raw payment	Paired 95% CI	Raw–Myopic execution	Paired 95% CI
Fanout	1	$1/3$	21.99%	[14.04%, 29.82%]	2.52%	[0.80%, 4.58%]
Fanout	1	1.00	31.48%	[21.92%, 40.29%]	21.82%	[17.46%, 25.88%]
Fanout	10	$1/3$	31.48%	[21.96%, 40.40%]	65.32%	[62.29%, 67.52%]
Fanout	10	1.00	31.48%	[21.78%, 40.66%]	86.63%	[84.98%, 87.72%]
Fanout	30	$1/3$	31.48%	[21.78%, 40.41%]	83.13%	[81.04%, 84.43%]
Fanout	30	1.00	31.48%	[21.60%, 40.12%]	93.88%	[93.05%, 94.40%]

Appendix

Table 11: Complete frozen structural-grid results for the heterogeneous strong prior. Payment columns compare Star with graph-aware Raw-DSIC; execution columns compare graph-aware Raw with Myopic. All 24 pre-specified cells are retained, and intervals are paired-bootstrap 95% confidence intervals.

Prior profile	Raw graph-aware vs. Myopic execution reduction	Star vs. Raw-DSIC payment reduction
Uniform	$91.11\%\,[90.63,91.48]$	$1.49\%\;[-0.39,3.58]$
Heterogeneous mild	$91.19\%\,[90.67,91.50]$	$10.23\%\;[3.44,16.73]$
Heterogeneous strong	$90.20\%\,[88.91,91.03]$	$31.48\%\;[22.56,40.73]$

Appendix

Table 12: Representative degree-100 high-payload cell at

\rho=1/3

. The middle column isolates topology awareness, whereas the right column compares two graph-aware DSIC mechanisms and isolates the additional effect of virtual-cost scoring.

$\lambda$	Payment reduction	Paired 95% CI	Pair-reversal rate	Allocation-disagreement rate
0.0	2.11%	[1.11%, 3.10%]	0.072	0.060
0.1	2.97%	[1.51%, 4.44%]	0.072	0.090
0.2	4.71%	[2.58%, 6.78%]	0.079	0.100
0.3	6.73%	[3.91%, 9.52%]	0.089	0.140
0.4	8.96%	[5.79%, 12.10%]	0.100	0.210
0.5	11.35%	[7.86%, 14.93%]	0.115	0.250

Appendix

Table 13: Complete degree-100 prior-shape continuum. Supports and high-payload graph semantics are fixed; the mild prior serves as a separate off-path reference. Rank reversal and allocation disagreement are reported as rates, and payment intervals are paired-bootstrap 95% confidence intervals.

Figure 7: Prior-continuum diagnostics for degree 100. The left panel reports the feasible-provider raw/virtual rank-reversal rate across

\lambda

; the right panel summarizes its descriptive association with Star ’s payment reduction along the fixed synthetic path.

Degree	Absolute saving ($)	Reduction
10	0.276	27.22%
20	0.322	27.22%
100	0.687	27.22%

Appendix

Table 14: Degree scaling at

\lambda=1

. Absolute savings grow with replicated workload, while normalized reductions coincide under the frozen replication-scaled construction.

Structural cell	$\eta$	Treatment [95% CI]	Control [95% CI]	Treatment–control [95% CI]	CI $>0$
Degree-100 fan-out	0.25	0.000% [0.000%, 0.000%]	0.000% [0.000%, 0.000%]	0.000% [0.000%, 0.000%]	No
Degree-100 fan-out	0.50	0.096% [-1.718%, 1.804%]	-0.323% [-2.167%, 1.088%]	0.419% [-0.972%, 1.723%]	No
Degree-100 fan-out	1.00	2.538% [-0.658%, 5.790%]	1.658% [-0.545%, 4.082%]	0.879% [-2.050%, 3.744%]	No
S4 cached input	0.25	0.005% [0.000%, 0.012%]	0.000% [0.000%, 0.000%]	0.005% [0.000%, 0.012%]	No
S4 cached input	0.50	0.256% [-0.919%, 1.429%]	-0.316% [-1.393%, 0.595%]	0.572% [-0.387%, 1.477%]	No
S4 cached input	1.00	3.385% [0.973%, 5.752%]	1.748% [-0.232%, 3.741%]	1.637% [-0.271%, 3.602%]	No

Appendix

Table 15: Region-inspired support-width contrasts. Treatment and control preserve provider means while varying support widths and aggregate dispersion. The parameter

\eta

scales each cost range’s half-width around its fixed mean: treatment half-widths are 20%, 50%, or 90% of the mean, multiplied by

\eta

; control half-widths are uniformly

50\%\times\eta

. The S4 cell uses cached-input fraction

\kappa=0.1

. Each paired-bootstrap interval resamples

n=50

seed blocks, retaining all six profile assignments together within each block. The pre-specified materiality assessment uses a 5-percentage-point threshold; the final column checks whether the treatment–control interval lies strictly above zero.

True prior	Scoring condition	$P$	$C_{\rm exec}$	$R$	$P-P_{\rm correct}$ (95% CI)	Allocation disagreement
Uniform	Correct prior	0.939	0.686	0.254	+0.0000 [+0.0000,+0.0000]	0.0%
Uniform	$\delta=-0.2$	0.944	0.692	0.252	+0.0043 [-0.0012,+0.0096]	7.0%
Uniform	$\delta=-0.1$	0.940	0.688	0.252	+0.0008 [-0.0019,+0.0035]	3.5%
Uniform	$\delta=-0.05$	0.939	0.686	0.253	-0.0005 [-0.0019,+0.0008]	1.0%
Uniform	$\delta=+0.05$	0.940	0.685	0.255	+0.0007 [-0.0006,+0.0020]	1.9%
Uniform	$\delta=+0.1$	0.942	0.685	0.256	+0.0023 [-0.0002,+0.0047]	3.4%

Appendix

Table 16: Complete decomposition for the prior-estimation-error magnitude grid. All rows use the same 1,000 paired cost draws per true profile as Table 2 . Uniform denotes

k_{i}=1

for all providers; heterogeneous denotes the provider-specific vector

k=(0.5,2,0.2,5,1)

in Table 2 . Only assumed shapes vary, with

\delta=\pm 0.05,\pm 0.1,\pm 0.2

. Payment is

P=C_{\rm exec}+R

before rounding. Payment changes and assignment disagreement are relative to correct-prior Star ; intervals use 2,000 paired bootstrap resamples. Disagreement is the fraction of draws with at least one task assigned differently.

$\|\mathcal{V}_{T}\|$	Completed instances	Task-assignment time (seconds)	All-provider payment time (seconds)	Maximum total time (seconds)
8	12/12	0.069	0.118	0.285
32	12/12	0.094	0.219	0.512
64	12/12	0.134	0.361	0.767

Appendix

Table 17: Full-mechanism CPU scaling. Times aggregate the chain and original sparse-DAG generators, provider counts

N\in\{3,5\}

, and three seeds. Allocation and all-provider payment columns are medians; max total retains the slowest completed instance.

family	$\|\mathcal{V}_{T}\|$	$N$	solved	allocation (s)	payments (s)	peak RSS (MiB)
chain	8	3	3/3	0.124	0.120	183.3
chain	8	5	3/3	0.067	0.115	182.0
chain	32	3	3/3	0.078	0.214	183.7
chain	32	5	3/3	0.104	0.262	187.2
chain	64	3	3/3	0.113	0.278	187.8
chain	64	5	3/3	0.194	0.421	268.9

Appendix

Table 18: Optimization runtime by graph family, task count, and provider count. Each row contains three fixed seeds.

N

is the number of available providers; task eligibility follows the capability requirements. Memory is the maximum sampled sum of resident set sizes (RSS) of the Python worker and all solver processes it launches, sampled at 20-millisecond intervals.

LLM Agent Routing

LLM agent routing selects models, tools, skills, or collaboration workflows for each task or step to balance capability, cost, latency, and reliability.

See all 99 papers

Planner-as-Router: Joint Plan-Time Model Routing for Cost-Efficient Multi-Agent Workflows
Sep 26, 2026Vivek Kumar Singh, Preeti Priyam, Gautam BhowmickLLM Agent Workflow Optimization LLM Routing
Independent Researcher McKinney, TX, USA · Independent Researcher Chicago, IL, USA
Which Model for Which Role? Cost-Efficient Pareto Recommendation for LLM Agentic Workflows
Oct 19, 2026Qian Xie, Wenyue Hua, Yueli He +7LLM Agent Workflow Optimization Multi-Objective Optimization
Columbia University · Cornell University · Microsoft +2
ProgRouter: Online Progress-Guided Orchestration for Multi-Agent LLM Workflows under Quality-Cost Tradeoffs
Aug 26, 2026Songyuan Li, Ahmed M. Abdelmoniem, Shiqiang WangLLM Inference Efficiency Multi-Agent Orchestration
Aston University, UK · Queen Mary University of London, UK · University of Exeter, UK

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

Planner-as-Router: Joint Plan-Time Model Routing for Cost-Efficient Multi-Agent Workflows

Vivek Kumar Singh, Preeti Priyam, Gautam Bhowmick

Independent Researcher McKinney, TX, USA · Independent Researcher Chicago, IL, USA

LLM Agent Workflow Optimization LLM Routing Multi-Agent LLM Systems LLM Planning

Open paper AskPDF arXiv

Running large language model (LLM) agents in production gets expensive fast. A frontier model (the largest, most capable tier) is accurate but can cost 25 times what a small model costs per token, and the gap compounds once a workflow chains several calls together. Planner-as-Router (PaR) attacks this from a different angle. Instead of leaving model-tier selection to some component downstream, it folds the choice into planning itself. As the planner breaks a query into subtasks, it also assigns each one a model size tier (small, mid, or frontier, ordered by capability and price), so the dependencies between subtasks are visible before any specialist runs. Unlike per-call routers such as cascade routing, which look at one node at a time, PaR sees the whole workflow up front and needs no separate router model or training data. We evaluate PaR with EntBench, a benchmark of 54 enterprise agentic tasks across seven classes, graded by actually running the generated Structured Query Language (SQL) and MongoDB queries against live databases. Over 1,157 evaluations spanning eight routers and three seeds, PaR stays on the observed cost-accuracy frontier. It matches a sink-frontier heuristic (frontier model on terminal nodes only) in accuracy at comparable cost and a faithful FrugalGPT cascade at lower cost, and cuts cost 44% against all-frontier routing while giving up 2.9 points of accuracy. Several accuracy gaps fall inside the plus-or-minus six-point confidence interval of a 54-task study, so we frame PaR's advantage as frontier position rather than a clean accuracy win. We also report a preliminary observation, not a validated result: a small pilot hints that cheap routing may carry a hidden compounding penalty on compositional workflows, which we frame as a hypothesis for future measurement. PaR, EntBench, and all evaluation code are open source.

Abstract

LLM Agent Routing

Explore similar work

Planner-as-Router: Joint Plan-Time Model Routing for Cost-Efficient Multi-Agent Workflows

Which Model for Which Role? Cost-Efficient Pareto Recommendation for LLM Agentic Workflows

ProgRouter: Online Progress-Guided Orchestration for Multi-Agent LLM Workflows under Quality-Cost Tradeoffs