Model routing strategy cuts costs with truthful reports and context reuse

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

Computer Science and Game TheoryComputation and LanguageMultiagent Systems

Summary

Assigning different parts of a multi-step task to various large language model providers can save money, but switching providers means redoing some work. The authors present a method called STAR that decides how to route tasks to providers by considering the workflow structure and the providers’ costs, encouraging them to honestly reveal their prices. This approach not only saves costs by reusing previous work when possible but also ensures the total payment to providers is minimized on average. Experiments show the benefits come from both smarter task grouping and optimizing payments under provider cost uncertainty.

What this means in practice

  • For cloud service operators: Assign tasks to multiple external AI providers to reduce computation costs while avoiding redundant work by reusing previous results.
  • For data pipeline engineers: Optimize task routing in complex workflows to minimize overall payment and ensure truthful cost reporting from independent compute providers.

Authors

Jiayuan Liu, Mingyu Guo, Jiarui Gan, Vincent Conitzer

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.