arXiv：cs.CL· Jiayuan Liu, Mingyu Guo, Jiarui Gan, Vincent Conitzer·· 16 小时前
STAR：图结构智能体工作流中真实且期望支付最优的模型路由
Truthful and Expected-Payment-Optimal Model Routing in Graph-Based Agentic Workflows
AI 导读
针对图结构智能体工作流中跨任务耦合的路由问题，研究者提出单参数采购拍卖框架 STAR（Strategy-proof Topology-aware Agent Routing），通过最小化虚拟成本加权的图工作量，使各提供商如实报告实时单位成本成为效用最大化策略，并覆盖其执行成本。
正文
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.
| Subjects: | Computer Science and Game Theory (cs.GT); Computation and Language (cs.CL); Multiagent Systems (cs.MA) |
| Cite as: | arXiv:2610.19316 [cs.GT] |
| (or arXiv:2610.19316v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2610.19316 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Jiayuan Liu [view email]
[v1]
Tue, 13 Oct 2026 23:59:09 UTC (639 KB)
来源：arXiv：cs.CL · arxiv.org