Paper deep dive
Truthful and Expected-Payment-Optimal Model Routing in Graph-Based Agentic Workflows
Jiayuan Liu, Mingyu Guo, Jiarui Gan, Vincent Conitzer
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 10/15/2026, 6:18:36 AM
Summary
The paper introduces STAR (Strategy-proof Topology-aware Agent Routing), a mechanism for routing tasks in graph-based agentic workflows involving Large Language Model (LLM) providers. STAR addresses the trade-off between minimizing execution costs (by reusing context within the same provider) and minimizing user payments (by accounting for providers' private cost distributions). It formulates the problem as a single-parameter procurement auction, using virtual costs derived from Myerson's optimal auction theory to ensure strategy-proofness (truthful reporting is a dominant strategy) and expected-payment optimality. The mechanism integrates graph topology (context reuse) with economic incentives to assign tasks to providers.
Entities (8)
Relation Signals (6)
STAR → implements → Strategy-Proofness
confidence 95% · STAR ... make truthful reporting utility-maximizing regardless of other providers' reports
STAR → optimizes → Expected Payment
confidence 92% · STAR additionally minimizes the user's expected total payment to providers.
Jiayuan Liu → affiliatedwith → Carnegie Mellon University
confidence 90% · Jiayuan Liu1,2 ... 1Carnegie Mellon University
STAR → uses → Virtual Cost
confidence 90% · Star instantiates Eq. (5) with s_i=φ_i ... The procurement virtual cost is defined as φ_i(c)=c+F_i(c)/f_i(c).
Graph-Based Agentic Workflows → enables → Context Reuse
confidence 88% · Keeping dependent tasks with the same provider can instead reuse eligible context. Graph-based workflows therefore couple routing decisions across tasks.
STAR → basedon → Myerson's Optimal Auction
confidence 85% · It scores providers by the procurement analogue of Myerson’s virtual value
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.19316v1
- Canonical: https://arxiv.org/abs/2610.19316v1
Trouble viewing inline? Open PDF directly →
Full Text
96,526 characters extracted from source content.
Expand or collapse full text
Truthful and Expected-Payment-Optimal Model Routing in Graph-Based Agentic Workflows Jiayuan Liu1,2 Mingyu Guo3 Jiarui Gan4 Vincent Conitzer1,2 1Carnegie Mellon University 2Foundations of Cooperative AI Lab (FOCAL) 3Adelaide University 4University of Oxford jiayuan4@cs.cmu.edu mingyu.guo@adelaide.edu.au jiarui.gan@cs.ox.ac.uk conitzer@cs.cmu.edu 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. Keywords: Mechanism design, procurement auctions, strategy-proofness, LLM routing, graph-based agentic workflows, context reuse. Figure 1: Star overview. Star assigns a fixed workflow’s tasks to eligible model providers and determines their payments. Providers privately know unit costs cic_i; assignment-dependent workloads include generation and upstream-context processing with eligible reuse. Star uses reported costs bib_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 wi=qi(A)w_i=q_i(A) and, because of strategy-proofness, depicts truthful cost reports bi=cib_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. Introduction Large language model (LLM) systems increasingly organize model calls into dependent workflows. Frameworks such as Graph of Thoughts [2], MetaGPT [7], and ChatDev [12] use structured interactions to address complex tasks. Routing can reserve more capable models for demanding tasks and assign routine tasks to cheaper models that meet their requirements, reducing the cost of executing the workflow [3, 11, 20]. We consider a user who needs a workflow executed and selects a model provider for each task node. Providers independently supply model services and seek to maximize profit. Before they submit bids, the orchestrator identifies the providers that meet each task’s requirements and specifies how their inference work is measured. Provider i privately knows its unit cost cic_i: the cost of one unit of this measured work. Multiplying cic_i by its assigned workload gives its execution cost. The user seeks to minimize the total payment to providers while satisfying the workflow’s service requirements. Two features shape this routing problem. First, a task’s cost depends on the providers assigned to neighboring tasks. Its provider must generate output and process the context received from upstream tasks. Keeping adjacent tasks with the same provider can reuse cached input; switching providers requires fresh processing. For example, a coding assistant may use a more capable, more expensive model for planning, switch to a cheaper, less capable model for a routine edit it can handle, and return to the more capable model for verification. With separate serving contexts and no eligible cache reuse for the transferred context, the cheaper model processes the accumulated context, and the more capable model processes the updated context on return. These two context-processing charges can exceed the saving on the routine edit. Globally economical routing therefore balances cheaper task execution against the cost of context switches, especially when a large context feeds many downstream tasks. Second, providers may privately know their instantaneous unit execution costs. These costs can vary with hardware utilization, available capacity, electricity prices, and local demand.11 1 Capacity-sensitive compute pricing is already illustrated by AWS EC2 Spot Instances (https://aws.amazon.com/ec2/spot/) and Google Cloud Spot VMs (https://cloud.google.com/solutions/spot-vms), which advertise discounts of up to 90% and 91%, respectively, relative to regular on-demand prices. If paid their submitted bids, providers have incentives to quote costs above their actual costs. A truthful mechanism jointly designs task assignments and payments so that reporting the actual cost maximizes each provider’s utility. We propose Star, a strategy-proof mechanism that assigns workflow tasks and pays providers using their reported unit costs and public graph-dependent workloads. It scores providers by the procurement analogue of Myerson’s virtual value: the virtual cost ϕi(c)=c+Fi(c)/fi(c) _i(c)=c+F_i(c)/f_i(c), where FiF_i and fif_i are the cumulative distribution function (CDF) and density of provider i’s cost [9]. Its cost prior is the probability distribution of its private unit cost. The added term accounts for the payment incentive associated with that distribution. Under normalized truthful payments, expected total payment equals expected virtual-cost-weighted workload. Minimizing this objective for each reported cost profile therefore minimizes the user’s expected total payment under independent regular priors, meaning independent cost distributions with non-decreasing virtual costs. Star is dominant-strategy incentive compatible (DSIC): reporting the true unit cost maximizes a provider’s utility for any reports by the others. This strategy-proofness follows from a simple allocation property: increasing a provider’s reported unit cost can only decrease or preserve its assigned workload. Comparing the optimal assignments before and after the increase proves this property even when neighboring assignments and cache reuse change together. Integrating the allocated workload over possible cost reports yields truthful payments and ex-post individual rationality (IR): each truthful provider receives at least its execution cost [1]. Virtual-cost scoring selects the expected-payment-optimal allocation within this truthful framework. Figure 1 summarizes this direct-report mechanism: providers submit their unit costs, and Star jointly computes task assignments and payments. We distinguish two sources of economic improvement. Topology awareness can reduce realized execution cost by avoiding repeated fresh-input processing. Separately, virtual-cost optimization can reduce the user’s expected payment relative to a graph-aware raw-score truthful mechanism. This second effect reflects differences in providers’ cost distributions: provider-specific priors induce different virtual-cost markups and can change the globally preferred workflow allocation. Contributions. First, we model task assignment and provider payments through graph-dependent workloads that capture the trade-off between cheaper models and repeated context processing. Second, we establish strategy-proofness and expected-payment optimality using the single-parameter framework, give exact allocation formulations, and derive an efficient payment formula for affine scores. Third, our controlled experiments quantify execution savings from topology awareness, payment savings from heterogeneous priors, and their sensitivity to prior specification, together with the runtime of the complete mechanism. Related Work We provide a condensed overview here. Appendix A gives a comprehensive discussion. LLM orchestration and routing. Chain-, tree-, and graph-structured prompting and multi-agent frameworks organize LLM calls into dependent workflows [14, 17, 2, 15, 7, 12]. Cost-aware routers and cascades select among heterogeneous models [3, 11, 20]. MasRouter jointly selects collaboration modes, roles, and LLMs [18]; BAMAS selects model pools and collaboration topologies under a budget [16]. Our setting adds strategic provider cost reports and truthful payments to routing on a public workflow. Mechanism design. Our mechanism uses procurement virtual costs from Myerson’s optimal-auction framework [9] and the single-parameter monotonicity/payment characterization of Archer and Tardos [1]. Prior work studies truthful cloud-resource and crowdsourcing procurement [19, 13], and frugal procurement over public set systems including paths and vertex covers [4]. Our model accounts for workload changes across the complete task assignment and optimizes the user’s expected payment. Public workload functions connect these graph interactions to the single-parameter incentive framework. Context reuse. PagedAttention, SGLang, and prompt caching reduce repeated context processing [8, 21, 6]. We represent the applicable reuse discount by a public edge-level cached-input fraction κu,v _u,v, determined by cache eligibility and the serving configuration. System Model .1 Workflow and Feasible Allocations We represent a workflow as a finite directed acyclic graph (DAG) =(,ℰ)G=(V,E). Let vuser∈v_user be a virtual source node representing the initial user input, and let T=∖vuserV_T=V \v_user\ be the set of task nodes. There are N providers ℳ=1,…,NM=\1,…,N\. For every task node v, the public set ℳv⊆ℳM_v specifies the providers that are capable of executing v. An allocation is a mapping A:T→ℳA:V_T such that A(v)∈ℳvA(v) _v for every v∈Tv _T. Let A denote the bid-independent set of all feasible allocations. For notational convenience, we set A(vuser)=0A(v_user)=0, where 0∉ℳ0 . We partition the dependency edges into source and internal edges: ℰsrc=(vuser,v)∈ℰ,ℰint=ℰ∖ℰsrc.E_src=\(v_user,v) \, _int=E _src. (1) All token quantities below are measured in millions of tokens. Let LvoutL_v^out denote the expected generated output at task node v, and let Lu,vtransL_u,v^trans denote the expected payload transmitted along edge (u,v)(u,v). In particular, Lvuser,vtransL_v_user,v^trans is the initial user input provided to a root task. .2 Public Graph-Dependent Workloads For allocation A, define xv,i(A)=A(v)=ix_v,i(A)=1\A(v)=i\. We set xvuser,i(A)=0x_v_user,i(A)=0. For every edge (u,v)(u,v), define δu,v,i(A)=xv,i(A)(1−xu,i(A)). _u,v,i(A)=x_v,i(A) (1-x_u,i(A) ). (2) Thus, δu,v,i(A)=1 _u,v,i(A)=1 exactly when provider i executes v but does not execute its parent u. Provider i has a public input-to-output workload coefficient ρi _i. For each edge (u,v)(u,v), let κu,v∈[0,1] _u,v∈[0,1] denote its public cached-input fraction: κu,v=0 _u,v=0 represents free cached input, whereas κu,v=1 _u,v=1 represents no same-provider discount. We set κu,v=1 _u,v=1 for edges that are not cache eligible. Running example. Consider a hub h and two children fixed to provider H. Each outgoing edge carries payload L, with discount κ. Assigning h to H contributes 2ρHκL2 _Hκ L to the children’s input workload; assigning it to another provider contributes 2ρHL2 _HL. The saved input work, 2ρH(1−κ)L2 _H(1-κ)L, must be weighed against the hub’s output generation and incoming-input processing. Proposition 6 accounts for both in the corresponding score threshold. The total standardized workload assigned to provider i under allocation A is qi q_i (A)=∑v∈TLvoutxv,i(A) (A)= _v _TL_v^outx_v,i(A) (3) +ρi∑(u,v)∈ℰLu,vtrans[κu,vxv,i(A)+(1−κu,v)δu,v,i(A)]. + _i _(u,v) L_u,v^trans [ _u,vx_v,i(A)+(1- _u,v) _u,v,i(A) ]. For an internal edge whose endpoints are both assigned to provider i, the edge contributes ρiκu,vLu,vtrans _i _u,vL_u,v^trans. If the provider changes, the same edge contributes the full fresh-input workload ρiLu,vtrans _iL_u,v^trans. Since the virtual source is not assigned to any provider, every source-to-root payload is charged as fresh input. Equation (3) measures input-processing work using public cache eligibility and discounts: κu,v=1 _u,v=1 charges full fresh-input work, while smaller values represent eligible reuse. .3 Private Costs, Reports, and Utilities Provider i privately knows its unit cost, a single number ci∈[ai,di]c_i∈[a_i,d_i] where [ai,di][a_i,d_i] is its publicly known range of possible costs. This number is the cost per unit of the publicly measured workload qi(A)q_i(A), so its realized execution cost under allocation A is Ci(A,ci)=ciqi(A)C_i(A;c_i)=c_iq_i(A). Provider i submits a report bi∈[ai,di]b_i∈[a_i,d_i]. Given payment pi()p_i(b), its quasi-linear utility is ui(,ci)=pi()−ciqi(A()).u_i(b;c_i)=p_i(b)-c_iq_i(A(b)). (4) The provider’s private information is the single number cic_i. Its complete workload function qi:→ℝ≥0q_i:A _≥ 0, token quantities, ρi _i, cache eligibility, κu,v _u,v, and feasible-provider sets ℳvM_v are public and fixed before reports are submitted. These public service specifications define the single-parameter model used throughout the incentive analysis. Star: Strategy-Proof Topology-Aware Routing .1 Score-Based Graph Allocation We first define a general score-based allocation rule. For each provider i, let si:[ai,di]→ℝs_i:[a_i,d_i] be a public non-decreasing score function. Given reports =(b1,…,bN)b=(b_1,…,b_N), define As()∈argmin∑j∈ℳA∈sj(bj)qj(A).A^s(b)∈ _A _j s_j(b_j)q_j(A). (5) When multiple allocations attain the same primary objective, the mechanism uses a fixed deterministic tie-breaking order that is independent of all reports. For Star, provider costs are independently drawn from provider-specific distributions with CDF FiF_i and density fif_i on [ai,di][a_i,d_i]. The procurement virtual cost is defined as ϕi(c)=c+Fi(c)fi(c). _i(c)=c+ F_i(c)f_i(c). (6) We assume regularity, so that ϕi _i is non-decreasing. Star instantiates Eq. (5) with si=ϕis_i= _i: AStar()∈argmin∑iA∈ϕi(bi)qi(A).A Star(b)∈ _A _i _i(b_i)q_i(A). (7) As a special case, for the uniform prior ci∼Uniform[ai,di]c_i [a_i,d_i] used in our reference configuration, ϕi(c)=2c−ai _i(c)=2c-a_i. The term Fi(c)/fi(c)F_i(c)/f_i(c) adjusts the allocation score for the provider’s cost distribution. The payment rule determines its realized information rent, the payment in excess of execution cost: pi−ciqi(A)p_i-c_iq_i(A). .2 Workload Monotonicity We prove workload monotonicity by comparing the optimal assignments at two reported costs. The graph determines the workload functions and thus the objective minimized in each comparison, incorporating all neighboring assignments and cache effects. Proposition 1 (Workload Monotonicity). Fix provider i and the other reports −ib_-i. Suppose that sis_i is non-decreasing and that Eq. (5) is solved exactly using the fixed report-independent tie-breaking rule. Then qi(As(bi,−i))q_i\! (A^s(b_i,b_-i) ) (8) is non-increasing in bib_i. Proof. Take two reports z<z′z<z and let A=As(z,−i),A′=As(z′,−i).A=A^s(z,b_-i), A =A^s(z ,b_-i). Define the contribution of all other providers as Ri(B)=∑j≠isj(bj)qj(B).R_i(B)= _j≠ is_j(b_j)q_j(B). (9) Optimality of A at report z gives si(z)qi(A)+Ri(A)≤si(z)qi(A′)+Ri(A′).s_i(z)q_i(A)+R_i(A)≤ s_i(z)q_i(A )+R_i(A ). (10) Optimality of A′A at report z′z gives si(z′)qi(A′)+Ri(A′)≤si(z′)qi(A)+Ri(A).s_i(z )q_i(A )+R_i(A )≤ s_i(z )q_i(A)+R_i(A). (11) Adding Eqs. (10) and (11) yields (si(z′)−si(z))(qi(A′)−qi(A))≤0. (s_i(z )-s_i(z) ) (q_i(A )-q_i(A) )≤ 0. (12) If si(z′)>si(z)s_i(z )>s_i(z), then qi(A′)≤qi(A)q_i(A )≤ q_i(A). If the two scores are equal, the two optimization problems have the same objective, and the fixed report-independent tie-breaking rule selects the same allocation. Hence the selected workload is non-increasing in the report. □ The proof covers changes to several neighboring assignments at once. Their effects on cache reuse and provider workloads are captured by the functions qj(A)q_j(A) and the contribution Ri(A)R_i(A) of the other providers. .3 Payments, Strategy-Proofness, and Individual Rationality For fixed −ib_-i, abbreviate qi(z)=qi(As(z,−i))q_i(z)=q_i\! (A^s(z,b_-i) ). For any public non-decreasing score functions, we compute a provider’s payment by adding its reported execution cost to the area under its workload curve over higher possible cost reports: pi()=biqi(bi)+∫bidiqi(z)z.p_i(b)=b_iq_i(b_i)+ _b_i^d_iq_i(z)\,dz. (13) Equation (13) pays each marginal unit of workload at its critical cost report: the highest reported cost at which that unit remains assigned to the provider. The integral is an area under a workload curve; payments are monetary amounts. Theorem 2 (DSIC and Ex-Post Individual Rationality). Under the conditions of Proposition 1, the score-based allocation rule in Eq. (5) together with the payment rule in Eq. (13) is dominant-strategy incentive compatible and ex-post individually rational. Proof. Fix provider i, its true cost cic_i, and the other reports −ib_-i. Its truthful utility is ui(ci,−i,ci)=∫cidiqi(z)z≥0,u_i(c_i,b_-i;c_i)= _c_i^d_iq_i(z)\,dz≥ 0, (14) which establishes ex-post individual rationality. For an alternative report ri>cir_i>c_i, ui(ci,−i,ci)−ui(ri,−i,ci) u_i(c_i,b_-i;c_i)-u_i(r_i,b_-i;c_i) =∫ciri(qi(z)−qi(ri))z≥0, = _c_i^r_i (q_i(z)-q_i(r_i) )\,dz≥ 0, (15) because qiq_i is non-increasing. For ri<cir_i<c_i, ui(ci,−i,ci)−ui(ri,−i,ci) u_i(c_i,b_-i;c_i)-u_i(r_i,b_-i;c_i) =∫rici(qi(ri)−qi(z))z≥0. = _r_i^c_i (q_i(r_i)-q_i(z) )\,dz≥ 0. (16) Thus truthful reporting maximizes provider i’s utility for every fixed −ib_-i. □ Theorem 2 is the standard single-parameter payment characterization applied to the graph-dependent workload in Eq. (3) [1]. .4 Expected-Payment Optimality The preceding truthfulness result applies to any non-decreasing score function. The particular choice si=ϕis_i= _i provides the additional expected-payment guarantee. Theorem 3 (Expected-Payment Optimality). Suppose costs are independent, provider i has support [ai,di][a_i,d_i], every virtual cost ϕi _i is non-decreasing, and payments use the normalization ui(di,−i,di)=0u_i(d_i,c_-i;d_i)=0. Then Star minimizes [∑ipi()]E_c [ _ip_i(c) ] among deterministic DSIC and ex-post individually rational mechanisms whose allocations lie in A. Proof. Fix provider i and the other costs −ic_-i, and write qi(c)=qi(A(c,−i))q_i(c)=q_i(A(c,c_-i)). Independence leaves i’s conditional cost distribution equal to FiF_i. Taking the expectation of the payment integral and exchanging the order of integration gives ci[∫cidiqi(z)z] _c_i\! [ _c_i^d_iq_i(z)\,dz ] =∫aidiqi(z)(∫aizfi(c)c)z = _a_i^d_iq_i(z)\! ( _a_i^zf_i(c)\,dc )dz =∫aidiFi(z)qi(z)z. = _a_i^d_iF_i(z)q_i(z)\,dz. (17) Thus the expected payment, conditional on −ic_-i, is ci[pi(ci,−i)] _c_i[p_i(c_i,c_-i)] =∫aidi[cfi(c)+Fi(c)]qi(c)c = _a_i^d_i [cf_i(c)+F_i(c) ]q_i(c)\,dc =ci[ϕi(ci)qi(ci)]. =E_c_i[ _i(c_i)q_i(c_i)]. (18) Taking expectation over the other costs and summing over providers yields [∑ipi()]=[∑iϕi(ci)qi(A())].E_c [ _ip_i(c) ]=E_c [ _i _i(c_i)q_i(A(c)) ]. Equation (7) minimizes the expression inside the expectation pointwise for every type profile. Regularity makes the virtual scores non-decreasing, so Proposition 1 and Theorem 2 make this minimizing allocation truthful and individually rational. For any DSIC allocation, the payment characterization adds the provider’s utility at its upper cost endpoint did_i to the normalized payment. Ex-post individual rationality makes this boundary utility nonnegative, so setting it to zero minimizes payments for the same allocation. Together these facts establish expected-payment optimality. Appendix B records the normalization details. □ Execution cost, virtual objective, and payment. We distinguish three economic quantities: Cexec(A,) C_exec(A;c) =∑iciqi(A), = _ic_iq_i(A), (19) Jϕ(A,) J_φ(A;b) =∑iϕi(bi)qi(A), = _i _i(b_i)q_i(A), (20) P() P(b) =∑ipi(). = _ip_i(b). (21) Star minimizes JϕJ_φ for each reported profile and hence minimizes the user’s expected total payment [P]E[P] under the correct priors. Execution cost CexecC_exec measures providers’ resource expenditure, whereas P measures the money the user pays them; the payment includes compensation for execution and incentive rent. Corollary 4 (Raw-Score DSIC). Setting si(bi)=bis_i(b_i)=b_i in Eq. (5) and using Eq. (13) yields a DSIC and ex-post individually rational mechanism. Under truthful reports, its allocation minimizes realized execution cost: Araw()∈argmin∑iA∈ciqi(A).A^raw(c)∈ _A _ic_iq_i(A). (22) Corollary 5 (Misspecified Monotone Scores). Any public non-decreasing score functions preserve DSIC and ex-post IR with the payment rule in Eq. (13). Using the true virtual costs additionally gives expected-payment optimality under Theorem 3. .5 Exact Allocation We give a mixed-integer linear program (MILP) for finite directed acyclic graphs (DAGs), used in all reported experiments, followed by an exact dynamic program for rooted trees and chains. Appendix G extends dynamic programming to graphs of bounded treewidth [5]. Using the edge partition in Eq. (1), let xv,i∈0,1x_v,i∈\0,1\ indicate that task node v∈Tv _T is assigned to provider i∈ℳi . For every edge (u,v)∈ℰ(u,v) , let δu,v,i∈[0,1] _u,v,i∈[0,1] indicate that v is assigned to provider i while its parent u is not assigned to i. For generic provider scores si(bi)s_i(b_i), the allocation problem is minx,δ _x,δ ∑i∈ℳsi(bi)[∑v∈TLvoutxv,i _i s_i(b_i) [ _v _TL_v^outx_v,i +ρi∑(u,v)∈ℰLu,vtrans(κu,vxv,i+(1−κu,v)δu,v,i)] + _i _(u,v) L_u,v^trans ( _u,vx_v,i+(1- _u,v) _u,v,i ) ] (23) s.t. ∑i∈ℳvxv,i=1,v∈T, _i _vx_v,i=1, v _T, (24) xv,i=0,v∈T,i∉ℳv, x_v,i=0, v _T,\ i _v, (25) δu,v,i≥xv,i−xu,i,(u,v)∈ℰint,i∈ℳ, _u,v,i≥ x_v,i-x_u,i, (u,v) _int,\ i , (26) δu,v,i≤xv,i,(u,v)∈ℰint,i∈ℳ, _u,v,i≤ x_v,i, (u,v) _int,\ i , (27) δu,v,i≤1−xu,i,(u,v)∈ℰint,i∈ℳ, _u,v,i≤ 1-x_u,i, (u,v) _int,\ i , (28) δvuser,v,i=xv,i,(vuser,v)∈ℰsrc,i∈ℳ, _v_user,v,i=x_v,i, (v_user,v) _src,\ i , (29) xv,i∈0,1,v∈T,i∈ℳ, x_v,i∈\0,1\, v _T,\ i , 0≤δu,v,i≤1,(u,v)∈ℰ,i∈ℳ. 0≤ _u,v,i≤ 1, (u,v) ,\ i . (30) The objective is the score-weighted workload in Eq. (3); Eqs. (24)–(25) assign each task to exactly one eligible provider. Constraints (26)–(28) enforce δu,v,i=xv,i(1−xu,i) _u,v,i= x_v,i(1-x_u,i). Thus a shared provider processes the cached-input fraction κu,v _u,v, while a provider switch charges full fresh-input workload. Equation (29) charges every source-to-root payload as fresh input. Star uses si(bi)=ϕi(bi)s_i(b_i)= _i(b_i) and Raw-DSIC uses si(bi)=bis_i(b_i)=b_i. Both optimize the same feasible assignments and graph-dependent workloads, differing only in their provider scores. Equal-objective allocations are resolved by the lexicographic order of public node ordering and provider identifiers. This tie order is fixed before reports are submitted. All reported allocations are computed with the COIN-OR Branch-and-Cut (CBC) optimization solver through the Python modeling library PuLP, requesting zero relative and absolute optimality gap. We retain solutions with solver status Optimal, using documented floating-point tolerances. Exact score minimization supplies the workload monotonicity required by Proposition 1; an approximation-based extension would likewise need a monotone allocation rule to preserve strategy-proofness. Exact optimization on rooted trees. For rooted trees and chains, exact dynamic programming combines optimal child assignments from leaves to root, accounting for their connecting edges and fresh user input. It computes the optimal objective in O(|T|N2)O(|V_T|N^2) operations; Appendix F gives the recurrence, correctness proof, assignment reconstruction, and extension to forests. .6 A Computational Special Case: Affine Scores For affine scores, which are linear functions of the reported cost plus a constant, si(b)=αib+γis_i(b)= _ib+ _i with αi>0 _i>0, define Ji(t,−i)=minA∈[tqi(A)+∑j≠isj(bj)qj(A)].J_i(t;b_-i)= _A [tq_i(A)+ _j≠ is_j(b_j)q_j(A) ]. (31) The payment in Eq. (13) then equals pi()=biqi(As())+Ji(si(di),−i)−Ji(si(bi),−i)αi.p_i(b)=b_iq_i(A^s(b))+ J_i(s_i(d_i);b_-i)-J_i(s_i(b_i);b_-i) _i. (32) This formula evaluates the payment integral through repeated optimization of the same task-assignment problem. We first find the optimal assignment at the submitted costs; its objective value is reused for every provider’s payment. For each provider assigned positive workload, we then recompute the optimum with that provider’s report set to its upper endpoint did_i, holding the other reports fixed. Thus all payments need one shared optimization and at most one additional optimization per active provider, plus tie-breaking computations. Raw, uniform, and power-prior scores have slopes 11, 22, and 1+1/ki1+1/k_i, respectively. Appendix C proves the optimal-value identity and specifies these score families. .7 When Topology Awareness Matters Proposition 6 (Broadcaster Threshold). Consider a hub node h with m outgoing edges of equal payload LtransL^trans and cached-input fraction κ to children assigned to provider H. Hold every other task’s assignment fixed, and compare assigning h to eligible providers L and H, with scores sLs_L and sHs_H. Let ILI_L and IHI_H be the score-weighted costs of processing all input arriving at h under these two choices, including their respective cache discounts, and write Δin=IH−IL _in=I_H-I_L. Assigning h to H is strictly preferred exactly when m(1−κ)ρHLtranssH>Lhout(sH−sL)+Δin.m(1-κ) _HL^transs_H>L_h^out(s_H-s_L)+ _in. (33) Proof. Assigning h to L contributes sLLhout+mρHLtranssH+ILs_LL_h^out+m _HL^transs_H+I_L, whereas assigning it to H contributes sHLhout+mκρHLtranssH+IHs_HL_h^out+mκ _HL^transs_H+I_H. The latter is smaller exactly under Eq. (33). □ The left side is the saved input-processing cost at the children; the right side is the extra generation and incoming-input cost at the hub. When h has no incoming input, Δin=0 _in=0. At equality, the fixed tie-breaking rule applies. The outgoing-context saving grows linearly with fan-out and payload and is zero at κ=1κ=1. Both Star and graph-aware raw-score routing capture this trade-off; virtual-cost scoring further accounts for provider-specific payment incentives. Experiments We validate the incentive and payment implementation, separate execution-cost gains from payment gains, and test prior-shape heterogeneity, deliberate prior misspecification, and payload/cache controls. Appendix I.7 reports computational costs. .1 Experimental Setup Structural-prior stress suite. Our primary payment study uses a frozen broadcaster-market construction and three pre-specified regular-prior profiles. Each provider follows the power family Fi(c)=(c−aidi−ai)ki,c∈[ai,di],F_i(c)= ( c-a_id_i-a_i )^k_i, c∈[a_i,d_i], (34) whose virtual cost is given in Appendix C. The shape parameter ki>0k_i>0 controls how probability is distributed within the provider’s cost range: ki=1k_i=1 is uniform, ki>1k_i>1 places more probability near the upper endpoint, and ki<1k_i<1 places more near the lower endpoint. The mild and strong profiles use fixed provider-specific kik_i vectors. For each profile, we evaluate the same 24 pre-specified structural cells with 50 paired holdout trials per cell. Provider cost ranges, shape vectors, capability tiers, and the structural grid are specified in Appendix I.2. Scope and workflows. Four hand-constructed synthetic DAG families inspired by creative writing, software engineering, web development, and legal analysis provide the S1–S4 reference. They vary fan-out, fan-in, and high-bandwidth broadcaster motifs, with eligibility specified by manually assigned capability tiers. Appendix H gives each workflow’s graph and task requirements. Synthetic workflow reference. S1–S4 use nine providers in three capability tiers, with fixed base-cost anchors in a 1:5:251:5:25 progression and uniform cost draws within provider-specific ranges. We set ρi=1/3 _i=1/3, κu,v=0.1 _u,v=0.1 on cache-eligible edges, and κu,v=1 _u,v=1 otherwise. Nominal token quantities receive lognormal variation with σ=0.3σ=0.3; the S2 source context follows a truncated-Pareto distribution on 5k5k–100k100k tokens. Appendix H gives the cost and token distributions and base-cost anchors. Mechanisms and routing diagnostics. Star minimizes the full graph-dependent virtual-cost objective and uses Eq. (13), evaluated by Eq. (32) for affine scores. Raw-DSIC minimizes ∑ibiqi(A) _ib_iq_i(A) over the same allocation space and applies the corresponding payment rule; under truthful reports, its allocation minimizes realized execution cost and coincides with the true-cost oracle. The True-Cost Oracle directly minimizes ∑iciqi(A) _ic_iq_i(A), serving as an execution-cost benchmark. Myopic independently selects the cheapest feasible provider at each node. We compare Star and Raw-DSIC by payments to providers and execution costs. The true-cost oracle provides the execution-cost benchmark, while Myopic is evaluated by execution cost only. Metrics. We separately report realized execution cost Cexec=∑iciqi(A)C_exec= _ic_iq_i(A), procurement payment P=∑ipiP= _ip_i, and information rent R=P−CexecR=P-C_exec. If CoracleC_oracle denotes the true-cost oracle objective, then PStar−Coracle=CStar−Coracle⏟allocation distortion+PStar−CStar⏟information rent.P_ Star-C_oracle= C_ Star-C_oracle_allocation distortion+ P_ Star-C_ Star_information rent. (35) We use the same random draws for each mechanism in a comparison and report paired-bootstrap 95% confidence intervals (CIs). 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. .2 Implementation Validation The theorems establish DSIC and ex-post individual rationality; exhaustive small-instance enumeration and dense bid sweeps validate the implementation. The final suite contains 159 passing tests. Across all reported exact experiment rows, CBC returns status Optimal with zero reported gap; when providers report their actual costs, Raw-DSIC assigns each task to exactly the provider selected by the execution-cost oracle; the minimum truthful provider utility is zero; and all payment-decomposition checks pass up to floating-point tolerance. The monotonicity case study evaluates 901 bids and contains four workload plateaus. Workload never increases with the bid, and no sampled misreport gives higher utility than reporting the actual cost. .3 Payment Savings under Heterogeneous Regular Priors We first isolate the condition that distinguishes Star from Raw-DSIC: provider-specific regular cost distributions. Both mechanisms optimize the same graph-dependent workload and use the DSIC payment rule, with Raw-DSIC scoring provider i by bib_i and Star scoring it by ϕi(bi) _i(b_i). We evaluate three pre-specified prior profiles over the same 24 frozen structural cells, using 50 paired holdout trials per cell and retaining every cell regardless of effect size. 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. Table 1 shows consistent payment savings across all 24 structural cells for the tested mild and strong prior-shape profiles. Under the strong profile, Star reduces payment relative to Raw-DSIC by 21.99%21.99\%–31.48%31.48\%, and all 24 paired 95% confidence intervals lie strictly above zero. The mild profile yields reductions of 10.23%10.23\%–10.30%10.30\%, again with positive intervals in all 24 cells. The uniform profile yields 1.49%1.49\%–3.34%3.34\%, with a strictly positive interval in 2 of 24 cells. In the representative degree-100 high-payload cell with ρ=1/3ρ=1/3, the payment reductions are 1.49% with 95% CI: [−0.39%, 3.58%][-0.39\%,\,3.58\%] under the uniform profile, 10.23%, [3.44%,16.73%][3.44\%,16.73\%] under the mild profile, and 31.48%, [22.56%,40.73%][22.56\%,40.73\%] under the strong profile. The fixed synthetic distributions enable a paired comparison of prior shape while preserving the same graph and workload rules. True cost distribution Correct-prior Star reduction (95% CI) |δ||δ| Negative-direction error δ=−|δ|δ=-|δ| (95% CI) Positive-direction error δ=+|δ|δ=+|δ| (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−P¯Star/P¯Raw)%100(1- P_ Star/ P_Raw)\%. Positive values mean lower user payments. The perturbation magnitude |δ||δ| is dimensionless. Only assumed shapes change: k^i=kieδri k_i=k_ie^δ r_i, with fixed r=(1,−1,0,1,−1)r=(1,-1,0,1,-1). Uniform uses ki=1k_i=1 for every provider; heterogeneous power priors use k=(0.5,2,0.2,5,1)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. .4 Continuous Prior-Shape Heterogeneity To test whether the heterogeneous-prior gain depends on a selected endpoint, we hold each provider’s support [ai,di][a_i,d_i] fixed and vary only its regular prior shape. For λ∈0,0.1,…,1λ∈\0,0.1,…,1\, define ki(λ) k_i(λ) =(kistrong)λ, = (k_i^strong )^λ, (36) Fi(c,λ) F_i(c;λ) =(c−aidi−ai)ki(λ). = ( c-a_id_i-a_i )^k_i(λ). The corresponding virtual cost is ϕi(c,λ)=(1+1ki(λ))c−aiki(λ). _i(c;λ)= (1+ 1k_i(λ) )c- a_ik_i(λ). (37) We use 200 paired holdout trials per λ and common latent cost quantiles throughout the sweep. Figure 2B shows a gradual increase in payment savings across the prior-shape path. The payment reduction rises from 2.11%2.11\% at λ=0λ=0 to 27.22%27.22\% at λ=1λ=1. The point estimate increases at all ten adjacent grid steps and forms an approximately smooth curve, with the final step adding 2.142.14 percentage points. For each cost draw, a rank reversal occurs when a pair of providers eligible for the same task have opposite orderings under raw and virtual costs. Counting each eligible pair once, the fraction with a reversal increases from 0.0720.072 to 0.1710.171 along the path. Across the eleven grid points, payment reduction has Spearman correlation 0.9980.998 with this rate and 0.9360.936 with the fraction of draws in which Star and Raw-DSIC choose different task assignments. These descriptive associations summarize how allocation decisions and payment savings co-vary along the tested synthetic path. At λ=0λ=0, all providers have uniform-shaped priors with different lower support endpoints aia_i. The virtual scores ϕi(c)=2c−ai _i(c)=2c-a_i therefore contain provider-specific offsets, which can change the preferred allocation and produce a nonzero Star/Raw-DSIC difference at this endpoint. At λ=1λ=1, mean (P,Cexec,R)(P,C_exec,R) is (1.8382,1.4530,0.3851)(1.8382,1.4530,0.3851) for Star and (2.5256,1.2587,1.2670)(2.5256,1.2587,1.2670) for Raw-DSIC; the oracle execution cost is 1.25871.2587. Hence the absolute payment difference is 0.68750.6875: Star reduces information rent by 0.88180.8818 while increasing execution cost by 0.19440.1944. The payment saving is primarily lower incentive rent, partially offset by allocation distortion. The degree-10, degree-20, and degree-100 continuum instances replicate the same consumer structure. Their coincident normalized payment-reduction and unique-pair rank-reversal curves provide a consistent view of the prior-shape sweep at three scales. Increasing degree scales the absolute saving from 0.2760.276 at degree 10 to 0.6870.687 at degree 100 when λ=1λ=1. .5 Sensitivity to Prior-Estimation Error Magnitude We test how Star’s payment advantage changes as errors in estimated provider cost distributions increase. True costs follow the power family in Eq. (34): the uniform profile has ki=1k_i=1 for every provider, while the heterogeneous power-prior profile has provider-specific shapes k=(0.5,2,0.2,5,1)k=(0.5,2,0.2,5,1) (Appendix I.2). We change only the assumed shapes, k^i=kieδri k_i=k_ie^δ r_i, with fixed r=(1,−1,0,1,−1)r=(1,-1,0,1,-1) and both signs of |δ|∈0.05,0.1,0.2|δ|∈\0.05,0.1,0.2\. These magnitudes permit shape increases of at most 5.13%5.13\%, 10.52%10.52\%, and 22.14%22.14\%, respectively. We pre-specify all six perturbations and 1,000 new cost vectors per true profile. Each condition shares the same true costs, truthful reports, graph, eligibility, and cost ranges with correct-prior Star and Raw-DSIC. Table 2 reports correct-prior savings of 0.79%0.79\% (uniform) and 30.04%30.04\% (heterogeneous). Under heterogeneous power priors, all six perturbations retain payment reductions of 29.92%29.92\%–30.16%30.16\%, with every paired 95% interval strictly above zero. Under uniform priors, all six sample-mean reductions remain positive: 0.72%0.72\%–0.85%0.85\% at |δ|=0.05|δ|=0.05, 0.56%0.56\%–0.71%0.71\% at |δ|=0.1|δ|=0.1, and 0.20%0.20\%–0.34%0.34\% at |δ|=0.2|δ|=0.2. Both directions at |δ|=0.05|δ|=0.05 and 0.10.1 have intervals strictly above zero. At |δ|=0.2|δ|=0.2, both intervals span zero, indicating less precise evidence for these smaller savings. The grid characterizes the payment benefit and its precision as prior-estimation error grows. All tested assumed scores are increasing and used consistently in allocation and payments, preserving strategy-proofness. Correctly specified priors additionally yield the expected-payment optimum in Theorem 3. At |δ|=0.2|δ|=0.2, the entire task assignment matches correct-prior routing in at least 93%93\% of uniform draws and 96.9%96.9\% of heterogeneous draws in each error direction. Appendix I.7 reports the full assignment-stability and payment-decomposition results. .6 Topology Stress Tests and Structural Controls 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 (κ=1κ=1) 0.00% [0.00%, 0.00%] Table 3: Degree-100 fan-out controls (ρ=1/3ρ=1/3, uniform priors). Ratio is transferred context per edge divided by each child’s 20,00020,000-token output: ratios 1 and 16 transfer 20,00020,000 and 320,000320,000 tokens, respectively, with κ=0.1κ=0.1; the no-cache row transfers 1,000,0001,000,000 tokens with κ=1κ=1. Hub output is 1,000,0001,000,000 tokens throughout. Table 8 instead uses ratio 50 and κ=0κ=0. Reductions compare graph-aware Raw-DSIC execution cost with Myopic; intervals are paired-bootstrap 95% confidence intervals. The κ=1κ=1 zeros are exact, not rounded: without reuse discounts and with common ρ, Raw-DSIC and Myopic attain the same execution cost. Table 3 isolates the roles of payload and reuse at fixed degree 100 and ρ=1/3ρ=1/3, matching Proposition 6. Raising the transferred-context/child-output ratio from one to sixteen increases execution-cost reduction from 2.13% to 67.47%; removing reuse with κ=1κ=1 makes it exactly zero. The paired intervals identify repeated fresh-input processing as the source of the large topology gains. Topology awareness and virtual-cost optimization generate distinct effects. In the tested degree-100 high-payload fan-out construction, graph-aware raw-cost routing reduces realized execution cost by 90.20%90.20\%–96.91%96.91\% relative to Myopic routing, depending on ρ and the prior profile. Comparing Star with the already topology-aware Raw-DSIC then isolates the additional payment benefit of provider-specific virtual-cost scoring. Appendices I.1, I.3, I.4, and I.6 report the synthetic S1–S4 uniform-prior reference, the complete stress grid, prior-continuum diagnostics, and the support-width comparison, respectively. Conclusion and Future Directions Star combines topology-aware workflow assignment with truthful provider payments. Workload monotonicity and the workload-integrating payment rule establish DSIC and ex-post IR; independent, correctly specified regular cost priors yield expected-payment optimality. Controlled synthetic experiments distinguish execution savings from avoided context processing and payment savings from virtual costs, with prior-shape sweeps and paired misspecification tests characterizing the latter. Affine scores enable efficient payment computation. Learned cost priors, measured serving workloads, and richer private service attributes provide directions for future work. Acknowledgments Jiayuan Liu and Vincent Conitzer thank the Cooperative AI Foundation, Macroscopic Ventures (formerly Polaris Ventures / the Center for Emerging Risk Research) and Jaan Tallinn’s donor-advised fund at Founders Pledge for financial support. References [1] A. Archer and É. Tardos (2001) Truthful mechanisms for one-parameter agents. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, p. 482–491. Cited by: Appendix A, §1, §2, §4.3. [2] M. Besta, N. Blach, A. Kubicek, R. Gerstenberger, M. Podstawski, L. Gianinazzi, J. Gajda, T. Lehmann, H. Niewiadomski, P. Nyczyk, et al. (2024) Graph of thoughts: solving elaborate problems with large language models. In Proceedings of the AAAI conference on artificial intelligence, Vol. 38, p. 17682–17690. Cited by: Appendix A, §1, §2. [3] L. Chen, M. Zaharia, and J. Zou (2024) FrugalGPT: how to use large language models while reducing cost and improving performance. Transactions on Machine Learning Research. Note: Featured Certification External Links: ISSN 2835-8856, Link Cited by: Appendix A, §1, §2. [4] N. Chen, E. Elkind, N. Gravin, and F. Petrov (2010) Frugal mechanism design via spectral techniques. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, p. 755–764. Cited by: Appendix A, §2. [5] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh (2015) Parameterized algorithms. Vol. 5, Springer. Cited by: Appendix G, §4.5. [6] I. Gim, G. Chen, S. Lee, N. Sarda, A. Khandelwal, and L. Zhong (2024) Prompt cache: modular attention reuse for low-latency inference. Proceedings of Machine Learning and Systems 6, p. 325–338. Cited by: Appendix A, §2. [7] S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, J. Wang, C. Zhang, Z. Wang, S. K. S. Yau, Z. Lin, et al. (2023) MetaGPT: meta programming for a multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, Cited by: Appendix A, §1, §2. [8] W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica (2023) Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles, p. 611–626. Cited by: Appendix A, §2. [9] R. B. Myerson (1981) Optimal auction design. Mathematics of operations research 6 (1), p. 58–73. Cited by: Appendix A, §1, §2. [10] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds.) (2007) Algorithmic game theory. Cambridge University Press. Cited by: Appendix A. [11] I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica (2024) RouteLLM: learning to route LLMs with preference data. arXiv preprint arXiv:2406.18665. Cited by: Appendix A, §1, §2. [12] C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, et al. (2024) Chatdev: communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 15174–15186. Cited by: Appendix A, §1, §2. [13] A. Singla and A. Krause (2013) Truthful incentives in crowdsourcing tasks using regret minimization mechanisms. In Proceedings of the 22nd international conference on World Wide Web, p. 1167–1178. Cited by: Appendix A, §2. [14] J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. (2022) Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 35, p. 24824–24837. Cited by: Appendix A, §2. [15] Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, et al. (2024) Autogen: enabling next-gen LLM applications via multi-agent conversations. In First Conference on Language Modeling, Cited by: Appendix A, §2. [16] L. Yang, J. Luo, X. Liu, Y. Lou, and Z. Chen (2026) BAMAS: structuring budget-aware multi-agent systems. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 29802–29810. Cited by: Appendix A, §2. [17] S. Yao, D. Yu, J. Zhao, I. Shafran, T. Griffiths, Y. Cao, and K. Narasimhan (2023) Tree of thoughts: deliberate problem solving with large language models. Advances in neural information processing systems 36, p. 11809–11822. Cited by: Appendix A, §2. [18] Y. Yue, G. Zhang, B. Liu, G. Wan, K. Wang, D. Cheng, and Y. Qi (2025) Masrouter: learning to route llms for multi-agent systems. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 15549–15572. Cited by: Appendix A, §2. [19] S. Zaman and D. Grosu (2013) A combinatorial auction-based mechanism for dynamic vm provisioning and allocation in clouds. IEEE Transactions on Cloud Computing 1 (2), p. 129–141. Cited by: Appendix A, §2. [20] Y. Zhang, S. Lu, Q. Chen, W. Luo, D. Zhan, and H. Ye (2025) Let the LLM stick to its strengths: learning to route economical LLM. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: Appendix A, §1, §2. [21] L. Zheng, L. Yin, Z. Xie, J. Huang, C. Sun, C. Yu, S. Cao, C. Kozyrakis, I. Stoica, J. E. Gonzalez, et al. (2023) Efficiently programming large language models using sglang.. Cited by: Appendix A, §2. Appendix A Detailed Related Work Structured LLM workflows and economical routing. Chain-, tree-, and graph-based reasoning and multi-agent systems structure dependent model calls [14, 17, 2, 15, 7, 12]. FrugalGPT, RouteLLM, and economical model routing select among models using performance and cost information [3, 11, 20]. Building on this motivation for economical model selection, our formulation incorporates independently compensated providers and incentives for truthful cost reporting. Joint multi-agent configuration. MasRouter selects collaboration modes, roles, and LLMs in a cascaded router [18]. BAMAS jointly selects a model pool and collaboration topology subject to a budget [16]. These systems demonstrate joint optimization of multi-agent configurations. Our complementary procurement setting fixes the workflow and eligibility sets before bidding, then uses strategic provider cost reports to determine task assignments and payments. Single-parameter procurement. Our incentive analysis applies the single-parameter characterization for providers whose private information is one unit-cost value [1]. For any bid-independent feasible set and public quantities qi(A)q_i(A), exact minimization of ∑isi(bi)qi(A) _is_i(b_i)q_i(A) with monotone scores and fixed tie-breaking yields workload monotonicity. Public quantity functions incorporate graph interactions directly into this argument. Procurement virtual costs then provide the expected-payment objective under independent regular priors [9, 10]. We develop the graph-dependent workload formulation, exact allocation methods, payment computation, and economic comparisons within this framework. Graph and infrastructure procurement. Truthful cloud-resource allocation and crowdsourcing procurement study related incentive problems [19, 13]. Frugal mechanism design on public set systems includes path and vertex-cover procurement [4]; its overpayment benchmarks and worst-case frugality objectives differ from our correct-prior expected-payment objective. A provider here can execute multiple tasks, and its public amount of work changes with neighboring assignments and input-reuse terms. Our public quantity functions represent this allocation-dependent work while preserving a single private unit cost per provider. The same framework also accommodates public setup- and placement-dependent workload rules. Context processing and caching. PagedAttention, SGLang, and prompt caching motivate attention to context-processing work [8, 21, 6]. Actual reuse depends on the model, serving instance, cache state, and token-prefix structure. Our workload model encodes the applicable eligibility and discount in public edge parameters, with κu,v=1 _u,v=1 charging fresh input. The synthetic experiments fix these parameters to isolate the routing and payment effects of repeated context processing. Appendix B Expected-Payment Identity Section 4.4 proves the expected-payment identity by exchanging the order of integration in the payment rule. This appendix records how the choice of upper-type utility enters that identity. For fixed other types −ic_-i, write qi(z)=qi(A(z,−i))q_i(z)=q_i(A(z,c_-i)) and let Uitop(−i)U_i^top(c_-i) be provider i’s utility when its true cost and report are both did_i. The single-parameter payment characterization gives pi(ci,−i)=ciqi(ci)+∫cidiqi(z)z+Uitop(−i).p_i(c_i,c_-i)=c_iq_i(c_i)+ _c_i^d_iq_i(z)\,dz+U_i^top(c_-i). (38) Ex-post individual rationality implies Uitop(−i)≥0U_i^top(c_-i)≥ 0. The normalized rule sets it to zero and minimizes payment for the given allocation. With a general upper-type utility, the identity proved in the main text becomes [pi]=[ϕi(ci)qi(A())]+[Uitop(−i)]E[p_i]=E[ _i(c_i)q_i(A(c))]+E[U_i^top(c_-i)]. This separates the allocation-dependent virtual-cost term from the nonnegative normalization term. Appendix C Derivation of the Affine-Score Payment Shortcut Equation (13) defines the general truthful payment for any monotone score-based allocation rule. We now give a computational specialization for the case in which provider i’s score is affine in its report: si(b)=αib+γi,αi>0s_i(b)= _ib+ _i,\ _i>0. Affine scores permit the payment integral to be evaluated using optimal-value differences, while Theorem 2 establishes the incentive guarantee for general monotone scores. For fixed −ib_-i, define Ji(t,−i)=minA∈[tqi(A)+∑j≠isj(bj)qj(A)].J_i(t;b_-i)= _A [tq_i(A)+ _j≠ is_j(b_j)q_j(A) ]. (39) Then the general integral payment in Eq. (13) has the exact affine-score representation pi()=biqi(As())+Ji(si(di),−i)−Ji(si(bi),−i)αi.p_i(b)=b_iq_i\! (A^s(b) )+ J_i(s_i(d_i);b_-i)-J_i(s_i(b_i);b_-i) _i. (40) All score families used in our reported experiments are affine. In particular: Raw score: si(b)=b,(αi,γi)=(1,0), s_i(b)=b,\ ( _i, _i)=(1,0), (41) Uniform prior: ϕi(b)=2b−ai,(αi,γi)=(2,−ai), _i(b)=2b-a_i,\ ( _i, _i)=(2,-a_i), (42) Power prior: ϕi(b)=(1+1ki)b−aiki, _i(b)= (1+ 1k_i )b- a_ik_i, (αi,γi)=(1+1ki,−aiki). 18.00005pt( _i, _i)= (1+ 1k_i,- a_ik_i ). (43) The allocation is solved once at the submitted profile. For each provider with positive allocated workload, we solve one additional allocation problem with that provider’s score set to its upper-support value and apply Eq. (32). If the current workload is zero, monotonicity implies that all higher-report workloads are also zero, so the provider’s normalized payment is zero. For a general regular prior with a non-affine virtual cost, Eq. (13) directly supplies the truthful payment used in Theorems 2 and 3. Our implementation and reported experiments use the affine families above, enabling the optimal-value shortcut in Eq. (32). The main paper defines the general normalized payment as pi()=biqi(As())+∫bidiqi(As(z,−i))z.p_i(b)=b_iq_i\! (A^s(b) )+ _b_i^d_iq_i\! (A^s(z,b_-i) )\,dz. (44) This section derives a computational shortcut for the special case si(b)=αib+γi,αi>0.s_i(b)= _ib+ _i, _i>0. (45) For fixed −ib_-i, define Ji(t,−i)=minA∈[tqi(A)+∑j≠isj(bj)qj(A)].J_i(t;b_-i)= _A [tq_i(A)+ _j≠ is_j(b_j)q_j(A) ]. (46) As the pointwise minimum of affine functions of t, JiJ_i is concave, piecewise linear, and absolutely continuous. At almost every t, its derivative is the workload of an optimal allocation: ∂Ji(t,−i)∂t=qi(Ai(t,−i)), ∂ J_i(t;b_-i)∂ t=q_i\! (A_i(t;b_-i) ), (47) where Ai(t,−i)∈argminA∈[tqi(A)+∑j≠isj(bj)qj(A)].A_i(t;b_-i)∈ _A [tq_i(A)+ _j≠ is_j(b_j)q_j(A) ]. The fixed report-independent tie rule determines the selected optimizer at breakpoints; these finitely many points do not affect the integral. Therefore, Ji(si(di),−i)−Ji(si(bi),−i) J_i(s_i(d_i);b_-i)-J_i(s_i(b_i);b_-i) =∫si(bi)si(di)qi(Ai(t,−i))t = _s_i(b_i)^s_i(d_i)q_i\! (A_i(t;b_-i) )\,dt =αi∫bidiqi(As(z,−i))z, = _i _b_i^d_iq_i\! (A^s(z,b_-i) )\,dz, (48) where the final equality uses t=si(z)=αiz+γit=s_i(z)= _iz+ _i and dt=αidzdt= _i\,dz. Substituting Eq. (48) into Eq. (44) yields pi()=biqi(As())+Ji(si(di),−i)−Ji(si(bi),−i)αi.p_i(b)=b_iq_i\! (A^s(b) )+ J_i(s_i(d_i);b_-i)-J_i(s_i(b_i);b_-i) _i. (49) This identity evaluates the general truthful payment exactly for affine scores. For arbitrary monotone scores, the workload integral in Eq. (44) remains the applicable payment formula. Appendix D Relation of Raw-Score DSIC to Vickrey–Clarke–Groves Payments The raw-score mechanism selects Araw()∈argmin∑iA∈biqi(A)A^raw(b)∈ _A _ib_iq_i(A) (50) and uses the normalized single-parameter integral payment. The Vickrey–Clarke–Groves (VCG) rule compensates a provider according to the reduction in the other providers’ reported costs made possible by its participation. When provider i can be excluded and reporting its upper type induces zero workload, qi(Araw(di,−i))=0,q_i(A^raw(d_i,b_-i))=0, (51) the payment can be written as piraw()= p_i^raw(b)= minA:qi(A)=0∑j≠ibjqj(A) _A:q_i(A)=0 _j≠ ib_jq_j(A) −∑j≠ibjqj(Araw()), - _j≠ ib_jq_j(A^raw(b)), (52) which is the Clarke-pivot VCG payment for the efficient allocation. A provider may also retain unavoidable workload at its upper type, for example when it is the sole feasible provider for a task. The top-type-normalized payment accommodates this case and preserves DSIC and ex-post individual rationality, using the upper-type assignment as its normalization reference. Appendix E Equivalent Breakpoint Representation We give an equivalent mathematical breakpoint representation of the general workload-integrating payment. The reported affine-score experiments compute the same payment through optimal-value differences. For fixed −ib_-i, the workload qi(z)q_i(z) is a non-increasing step function. When bi<dib_i<d_i, partition the integration range at every interior workload change: bi=t0<t1<⋯<tK=di.b_i=t_0<t_1<·s<t_K=d_i. Let QkQ_k be the constant workload on the open interval (tk−1,tk)(t_k-1,t_k). Then Eq. (13) becomes pi()=biqi(bi)+∑k=1KQk(tk−tk−1).p_i(b)=b_iq_i(b_i)+ _k=1^KQ_k(t_k-t_k-1). (53) The first term uses the workload actually selected by the fixed tie-breaking rule at the current report, including when bib_i is a change point. Values at the other individual change points and at did_i do not affect the integral. When bi=dib_i=d_i, the integration range is empty and the payment is diqi(di)d_iq_i(d_i). Workload changes can arise from task reassignment or cache-status changes; the number of intervals need not equal the number of tasks currently assigned to provider i. Appendix F Exact Dynamic Programming for Rooted Trees Section 4.5 uses an exact dynamic program for rooted trees and chains. We give its value recurrence and correctness proof before detailing assignment reconstruction and workflow forests. For each task node v and eligible provider i, define Dv(i)D_v(i) as the minimum contribution to the allocation objective from v and all its descendant tasks, when v is assigned to i. It includes their output generation and input processing on edges between those tasks. An edge from v’s parent is accounted for when combining v with that parent; fresh user-context processing is included at the root r. Thus the complete workflow optimum is mini∈ℳrDr(i) _i _rD_r(i). We compute these values from leaves to root by dynamic programming. Write si=si(bi)s_i=s_i(b_i) and let ch(v)ch(v) denote v’s children. The local generation contribution is gv(i)=siLvoutg_v(i)=s_iL_v^out for v≠rv≠ r; at the root, gr(i)=si[Lrout+ρiLvuser,rtrans]g_r(i)=s_i[L_r^out+ _iL_v_user,r^trans] also includes fresh source input. The edge contribution ηv,u(i,j)=sjρjLv,utrans[κv,u+(1−κv,u)i≠j] _v,u(i,j)= s_j _jL_v,u^trans[ _v,u+(1- _v,u)1\i≠ j\] accounts for processing the parent–child context. The recurrence is Dv(i) D_v(i) =gv(i) =g_v(i) (54) +∑u∈ch(v)minj∈ℳuDu(j)+ηv,u(i,j). + _u (v) _j _u\D_u(j)+ _v,u(i,j)\. Correctness. With v’s provider fixed, its child branches can be optimized independently. Each minimizing term combines the child’s best assignment with its connecting edge, charging that edge once. At a leaf, Dv(i)=gv(i)D_v(i)=g_v(i); induction up the tree establishes every entry and hence the optimal root value. Computing all values takes O(|T|N2)O(|V_T|N^2) operations. Backtracking recovers an optimal assignment with the public tie order. Root choice and reconstruction. Equivalently, the context-processing edge factor can be written as ηv,u(i,j)=sj(bj)ρjLv,utrans[κv,u+(1−κv,u)i≠j]. _v,u(i,j)=s_j(b_j) _jL_v,u^trans [ _v,u+(1- _v,u)1\i≠ j\ ]. (55) The root entry already includes fresh user-context processing, so the complete objective is mini∈ℳrDr(i). _i _rD_r(i). (56) A workflow forest with several task roots is handled by applying Eq. (56) independently to each root and summing the resulting objectives. For reconstruction, each dynamic-programming entry stores its minimizing child-provider choices. Backtracking from an optimal root choice determines the assignment of every task. Among equal-objective subtree assignments, the public node and provider ordering selects the lexicographically smallest assignment; this ordering is fixed before reports are submitted, just as in the main mechanism. Evaluating the objective values requires O(∑v∈T|ℳv|+∑(v,u)∈ℰint|ℳv||ℳu|)O ( _v _T|M_v|+ _(v,u) _int|M_v||M_u| ) (57) operations, bounded by O(|T|N2)O(|V_T|N^2) for a task tree. The first term accounts for node values, including single-node trees; the second enumerates eligible parent–child provider pairs. Appendix G Exact Tree-Decomposition Dynamic Programming This section gives an exact junction-tree dynamic program for finite DAGs whose underlying undirected task graph has bounded treewidth. A directed DAG may induce cycles in this underlying undirected graph, for example through multi-parent fan-in. This is distinct from a directed control-flow cycle: workflows with directed loops must first be unrolled into finite DAGs. Pairwise factorization. Let ℋ=(T,ℰH)H=(V_T,E_H) be the underlying undirected task graph, where u,v∈ℰH\u,v\ _H whenever either (u,v)(u,v) or (v,u)(v,u) is an internal dependency edge. Each task v has assignment domain ℳvM_v. The source-edge and generation contributions can be combined into the unary factor ψv(i)=si(bi)[Lvout+ρi∑(vuser,v)∈ℰsrcLvuser,vtrans],i∈ℳv. _v(i)=s_i(b_i) [L_v^out+ _i _(v_user,v) _srcL_v_user,v^trans ], i _v. (58) For every internal directed edge (u,v)(u,v), define the pairwise factor ψu→v(i,j)=sj(bj)ρjLu,vtrans[κu,v+(1−κu,v)i≠j], _u→ v(i,j)=s_j(b_j) _jL_u,v^trans [ _u,v+(1- _u,v)1\i≠ j\ ], (59) where i∈ℳui _u and j∈ℳvj _v. The complete score objective is therefore ∑v∈Tψv(A(v))+∑(u,v)∈ℰintψu→v(A(u),A(v)). _v _T _v(A(v))+ _(u,v) _int _u→ v(A(u),A(v)). (60) Equation (60) is exactly the objective in Eq. (5), expressed as unary and pairwise factors. Tree decomposition. A tree decomposition of ℋH is a tree =(ℐ,ℱ)T=(I,F) together with bags Bt⊆T:t∈ℐ\B_t _T:t \ satisfying: 1. for every vertex v, the bags containing v form a connected subtree of T; 2. for every edge u,v∈ℰH\u,v\ _H, at least one bag contains both u and v. The width is w=maxt∈ℐ|Bt|−1.w= _t |B_t|-1. We root T at an arbitrary bag t0t_0. Each unary and pairwise factor in Eq. (60) is assigned to exactly one bag containing all variables in its scope. For example, one may assign each factor to the highest such bag under the rooted decomposition. Let tQ_t be the factors assigned to bag BtB_t. For an assignment t∈∏v∈Btℳv,a_t∈ _v∈ B_tM_v, define the local bag cost Ψt(t)=∑ψ∈tψ(t|scope(ψ)). _t(a_t)= _ψ _tψ\! (a_t |_scope(ψ) ). (61) Because every factor is assigned to exactly one bag, no subtraction or double-counting correction is required. For every non-root bag t, let p(t)p(t) be its parent and define the separator St=Bt∩Bp(t).S_t=B_t∩ B_p(t). The message from bag t to its parent is mt→p(t)(St)=minBt∖St[Ψt(t)+∑c∈ch(t)mc→t(Bc∩Bt)]. m_t→ p(t)(a_S_t)= _a_B_t S_t [ _t(a_t)+ _c (t)m_c→ t (a_B_c∩ B_t ) ]. (62) At the root bag t0t_0, the optimal objective is minBt0[Ψt0(t0)+∑c∈ch(t0)mc→t0(Bc∩Bt0)]. _a_B_t_0 [ _t_0(a_t_0)+ _c (t_0)m_c→ t_0 (a_B_c∩ B_t_0 ) ]. (63) Backtracking through the minimizing assignments recovers a globally optimal workflow allocation. Let Mmax=maxv∈T|ℳv|.M_ = _v _T|M_v|. For a supplied tree decomposition of width w, the running time is bounded by O(|ℐ|Mmaxw+1)O (|I|M_ ^w+1 ) (64) up to polynomial factors for evaluating local potentials and messages [5]. For fixed treewidth, the dynamic program runs in polynomial time; it is fixed-parameter tractable when parameterized jointly by w and MmaxM_ . With an available low-width decomposition, this junction-tree formulation provides an exact theoretical allocation algorithm. Its complexity is parameterized by the supplied decomposition width. The reported experimental pipeline uses the MILP in Section 4.5. Appendix H Synthetic Market and Workflow Configurations All four workflow families are hand-constructed finite DAGs. Nominal token values below are reported in thousands of tokens for readability; the solver converts them to millions of tokens before applying per-million-token costs. Unless otherwise stated, nominal values are sampled using Eq. (67) below. H.1 Cost and Token Sampling We simulate nine providers in three capability tiers, with synthetic base-cost anchors following a 1:5:251:5:25 progression. This progression provides a controlled separation between provider tiers. In the synthetic S1–S4 reference configuration, ci=CibaseSi,Si∼Uniform(0.1,1.0),c_i=C_i^baseS_i, S_i (0.1,1.0), (65) so provider i has support [ai,di]=[0.1Cibase,Cibase],ϕi(c)=2c−ai.[a_i,d_i]=[0.1C_i^base,C_i^base], _i(c)=2c-a_i. (66) We set ρi=1/3 _i=1/3 for every provider, use κu,v=0.1 _u,v=0.1 on cache-eligible edges, and set κu,v=1 _u,v=1 on non-cacheable edges. The base-cost anchors remain fixed throughout this configuration. For each nominal token quantity L¯ L, we sample L∼LogNormal(logL¯−σ22,σ2),σ=0.3.L ( L- σ^22,σ^2 ), σ=0.3. (67) The S2 source context is sampled separately from the configured truncated-Pareto distribution on 5k5k–100k100k tokens. H.2 Provider Tiers A provider in capability tier t can execute tasks of difficulty at most t. In the workflow diagrams, D1, D2, and D3 denote public task-difficulty tiers 1, 2, and 3; “Diff-1” likewise means difficulty tier 1. 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 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 Modules 10 1×3, 7×2, 2×11× 3,\;7× 2,\;2× 1 25 each File tasks 30 10×3, 20×110× 3,\;20× 1 15 each Merger / Tester 1 each 1 / 2 15 / 8 S3 Architect / SpecWriter 1 each 2 / 1 10 / 300 Frontend / Backend / Interactive Lead 1 each 2 / 2 / 2 50 / 40 / 30 Frontend developers 5 3×1, 2×23× 1,\;2× 2 15 each Backend developers 4 1×1, 3×21× 1,\;3× 2 20 each Interactive developers 3 1×2, 2×31× 2,\;2× 3 15 each S4 Expert Assessment / Case Retriever 1 each 3 / 1 5 / 400 Analysts 5 3×1, 2×23× 1,\;2× 2 40, 35, 30, 20, 18 Aggregator 1 1 80 Strategists 3 2 20 each Expert Synthesis 1 3 10 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. Planner 1D1, 300k3 WritersD2, 40k eachAggregator 1D1, 50kStages 2–4Planner 5D1, 300k3 WritersD2, 40k eachAggregator 5D1, 50kFinal EditorD1, 20k 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. ScannerD1AnalyzerD2PlannerD3SpecGeneratorD1, 350k10 Modules1 D3, 7 D2, 2 D130 File Tasks10 D3, 20 D1MergerD1TesterD2 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. ArchitectD2SpecWriterD1, 300kBackend LeadD2, 40kFrontend LeadD2, 50kInteractive LeadD2, 30k5 Frontend Devs3 D1, 2 D24 Backend Devs1 D1, 3 D23 Interactive Devs1 D2, 2 D3 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. Expert AssessmentD3Case RetrieverD1, 400k5 Analysts3 D1, 2 D2AggregatorD1, 80k3 StrategistsD2, 20k eachExpert SynthesisD3, 10k 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. Appendix I Additional Experimental Results I.1 Synthetic S1–S4 Uniform-Prior Reference 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%] Table 6: Synthetic S1–S4 uniform-prior boundary reference. Intervals are paired-bootstrap 95% confidence intervals for Star relative to graph-aware Raw-DSIC. The synthetic reference evaluates the four richer S1–S4 DAG families under provider-specific uniform priors. Star lowers sample-mean payment relative to Raw-DSIC by 1.44%1.44\%, 0.36%0.36\%, 0.91%0.91\%, and 0.92%0.92\%, respectively; the paired interval for S2 includes zero. This is a useful boundary case: when the raw and virtual score trade-offs are closely aligned, Star and Raw-DSIC often select similar allocations, so the additional payment benefit of virtual-cost optimization is modest. I.2 Heterogeneous-Prior Stress Configuration Table 7 specifies the fixed provider cost ranges and prior shapes. Experimental provider identifiers are 0–4; capability tier 2 can also execute tier-1 tasks. The structural cells are specified below. Provider ID Capability tier Unit-cost range ($/million work units) Uniform kik_i Mild kik_i Strong kik_i aia_i did_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 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 ϕi(c)=(1+1/ki)c−ai/ki _i(c)=(1+1/k_i)c-a_i/k_i. Cell Topology Degree ρ Paired trials C01 Fanout 1 1/31/3 50 C02 Fanout 1 1.00 50 C03 Fanout 10 1/31/3 50 C04 Fanout 10 1.00 50 C05 Fanout 30 1/31/3 50 C06 Fanout 30 1.00 50 C07 Fanout 100 1/31/3 50 C08 Fanout 100 1.00 50 C09 Fanin 1 1/31/3 50 C10 Fanin 1 1.00 50 C11 Fanin 10 1/31/3 50 C12 Fanin 10 1.00 50 C13 Fanin 30 1/31/3 50 C14 Fanin 30 1.00 50 C15 Fanin 100 1/31/3 50 C16 Fanin 100 1.00 50 C17 Hourglass 1 1/31/3 50 C18 Hourglass 1 1.00 50 C19 Hourglass 10 1/31/3 50 C20 Hourglass 10 1.00 50 C21 Hourglass 30 1/31/3 50 C22 Hourglass 30 1.00 50 C23 Hourglass 100 1/31/3 50 C24 Hourglass 100 1.00 50 Table 8: The 24 frozen structural cells used separately under each of the uniform, mild, and strong prior profiles. The fixed settings are κ=0.0κ=0.0, a transferred payload of 1,000,0001,000,000 tokens, a generated hub payload of 1,000,0001,000,000 tokens, and child outputs of 20,00020,000 tokens. The uniform, mild, and strong profiles use the same frozen structural cells. Every pre-specified cell is retained, including weak or nonsignificant effects. The documented provider-to-prior assignment is fixed across these cells, making the comparison reproducible for each specified market profile. I.3 Complete Heterogeneous-Prior Results Topology Degree ρ Star–Raw payment Paired 95% CI Raw–Myopic execution Paired 95% CI Fanout 1 1/31/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/31/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/31/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%] Fanout 100 1/31/3 1.49% [-0.39%, 3.58%] 91.11% [90.63%, 91.48%] Fanout 100 1.00 1.49% [-0.38%, 3.41%] 96.88% [96.68%, 97.02%] Fanin 1 1/31/3 1.49% [-0.47%, 3.50%] 9.07% [7.47%, 10.74%] Fanin 1 1.00 1.49% [-0.53%, 3.50%] 24.15% [20.77%, 27.45%] Fanin 10 1/31/3 1.49% [-0.49%, 3.41%] 10.09% [8.56%, 11.62%] Fanin 10 1.00 1.49% [-0.52%, 3.42%] 25.07% [21.80%, 28.15%] Fanin 30 1/31/3 1.49% [-0.37%, 3.53%] 10.17% [8.68%, 11.76%] Fanin 30 1.00 1.49% [-0.48%, 3.47%] 25.14% [22.02%, 28.34%] Fanin 100 1/31/3 1.49% [-0.49%, 3.43%] 10.19% [8.68%, 11.74%] Fanin 100 1.00 1.49% [-0.55%, 3.52%] 25.17% [21.90%, 28.29%] Hourglass 1 1/31/3 2.31% [0.58%, 4.11%] 6.28% [5.01%, 7.65%] Hourglass 1 1.00 1.49% [-0.54%, 3.48%] 24.51% [21.19%, 27.61%] Hourglass 10 1/31/3 1.49% [-0.43%, 3.47%] 24.98% [23.36%, 26.52%] Hourglass 10 1.00 1.49% [-0.40%, 3.54%] 52.57% [50.53%, 54.19%] Hourglass 30 1/31/3 1.49% [-0.42%, 3.42%] 28.30% [26.73%, 29.65%] Hourglass 30 1.00 1.49% [-0.50%, 3.50%] 55.01% [53.12%, 56.48%] Hourglass 100 1/31/3 1.49% [-0.40%, 3.47%] 29.49% [28.00%, 30.82%] Hourglass 100 1.00 1.49% [-0.46%, 3.44%] 55.88% [53.94%, 57.45%] 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 ρ Star–Raw payment Paired 95% CI Raw–Myopic execution Paired 95% CI Fanout 1 1/31/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/31/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/31/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%] Fanout 100 1/31/3 10.23% [3.44%, 16.73%] 91.19% [90.67%, 91.50%] Fanout 100 1.00 10.23% [3.50%, 16.60%] 96.91% [96.72%, 97.02%] Fanin 1 1/31/3 10.23% [3.53%, 16.63%] 8.31% [6.44%, 10.26%] Fanin 1 1.00 10.23% [3.21%, 16.91%] 22.65% [18.64%, 26.61%] Fanin 10 1/31/3 10.23% [3.27%, 16.88%] 9.38% [7.61%, 11.21%] Fanin 10 1.00 10.23% [3.54%, 16.95%] 23.61% [19.60%, 27.38%] Fanin 30 1/31/3 10.23% [3.68%, 16.96%] 9.47% [7.72%, 11.24%] Fanin 30 1.00 10.23% [3.28%, 16.66%] 23.69% [19.99%, 27.49%] Fanin 100 1/31/3 10.23% [3.73%, 17.08%] 9.49% [7.73%, 11.35%] Fanin 100 1.00 10.23% [3.17%, 16.94%] 23.71% [19.82%, 27.42%] Hourglass 1 1/31/3 10.26% [4.23%, 16.00%] 6.06% [4.49%, 7.70%] Hourglass 1 1.00 10.23% [3.21%, 16.57%] 22.99% [19.09%, 26.89%] Hourglass 10 1/31/3 10.23% [3.40%, 16.92%] 24.51% [22.74%, 26.19%] Hourglass 10 1.00 10.23% [3.45%, 16.79%] 52.16% [50.08%, 54.01%] Hourglass 30 1/31/3 10.23% [3.23%, 16.66%] 27.96% [26.39%, 29.50%] Hourglass 30 1.00 10.23% [3.27%, 16.39%] 54.66% [52.74%, 56.47%] Hourglass 100 1/31/3 10.23% [3.49%, 16.92%] 29.20% [27.70%, 30.64%] Hourglass 100 1.00 10.23% [3.50%, 16.69%] 55.55% [53.69%, 57.16%] 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 ρ Star–Raw payment Paired 95% CI Raw–Myopic execution Paired 95% CI Fanout 1 1/31/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/31/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/31/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%] Fanout 100 1/31/3 31.48% [22.56%, 40.73%] 90.20% [88.91%, 91.03%] Fanout 100 1.00 31.48% [22.30%, 40.32%] 96.53% [96.05%, 96.84%] Fanin 1 1/31/3 31.48% [22.27%, 40.39%] 8.02% [6.05%, 9.96%] Fanin 1 1.00 31.48% [21.98%, 40.82%] 21.82% [17.44%, 26.01%] Fanin 10 1/31/3 31.48% [21.82%, 40.50%] 8.96% [7.09%, 11.02%] Fanin 10 1.00 31.48% [21.65%, 40.27%] 22.70% [18.51%, 26.69%] Fanin 30 1/31/3 31.48% [21.87%, 40.61%] 9.03% [7.13%, 10.98%] Fanin 30 1.00 31.48% [21.48%, 40.63%] 22.76% [18.55%, 26.72%] Fanin 100 1/31/3 31.48% [21.84%, 40.35%] 9.06% [7.19%, 11.00%] Fanin 100 1.00 31.48% [22.18%, 40.90%] 22.78% [18.55%, 26.99%] Hourglass 1 1/31/3 27.55% [18.85%, 35.28%] 5.87% [4.17%, 7.77%] Hourglass 1 1.00 31.48% [21.52%, 41.01%] 22.15% [17.71%, 26.42%] Hourglass 10 1/31/3 31.48% [22.28%, 40.38%] 22.85% [20.33%, 25.12%] Hourglass 10 1.00 31.48% [22.19%, 40.72%] 49.70% [45.98%, 52.66%] Hourglass 30 1/31/3 31.48% [21.86%, 40.62%] 26.03% [23.33%, 28.28%] Hourglass 30 1.00 31.48% [21.73%, 40.69%] 52.17% [48.63%, 54.82%] Hourglass 100 1/31/3 31.48% [21.53%, 40.47%] 27.17% [24.50%, 29.44%] Hourglass 100 1.00 31.48% [21.85%, 40.53%] 53.05% [49.61%, 55.75%] 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. For the representative degree-100 high-payload cell with ρ=1/3ρ=1/3, the two distinct effects are visible in the same comparison: Prior profile Raw graph-aware vs. Myopic execution reduction Star vs. Raw-DSIC payment reduction Uniform 91.11%[90.63,91.48]91.11\%\,[90.63,91.48] 1.49%[−0.39,3.58]1.49\%\;[-0.39,3.58] Heterogeneous mild 91.19%[90.67,91.50]91.19\%\,[90.67,91.50] 10.23%[3.44,16.73]10.23\%\;[3.44,16.73] Heterogeneous strong 90.20%[88.91,91.03]90.20\%\,[88.91,91.03] 31.48%[22.56,40.73]31.48\%\;[22.56,40.73] Table 12: Representative degree-100 high-payload cell at ρ=1/3ρ=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. The graph-aware execution reduction remains near 90%90\% across the three prior profiles, whereas the payment advantage varies strongly with prior shape. Thus, graph coupling and prior heterogeneity affect different comparisons. I.4 Complete Prior-Shape Continuum λ 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 0.6 15.69% [11.87%, 19.54%] 0.124 0.235 0.7 19.02% [14.81%, 23.22%] 0.136 0.220 0.8 22.02% [17.44%, 26.35%] 0.146 0.240 0.9 25.08% [20.28%, 29.65%] 0.163 0.255 1.0 27.22% [22.41%, 32.02%] 0.171 0.285 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 λ; 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% Table 14: Degree scaling at λ=1λ=1. Absolute savings grow with replicated workload, while normalized reductions coincide under the frozen replication-scaled construction. The normalized curves coincide across degrees 10, 20, and 100 because the frozen construction replicates identical consumer branches while preserving the set of competing provider pairs. Degree increases absolute payment savings. The mild profile serves as a separate off-path reference: its least-squares log-k projection is λ=0.338λ=0.338, with a non-negligible residual. I.5 Structural Negative Controls Table 3 in Section 5.6 reports all three structural controls. The no-cache control makes graph-aware and myopic allocations agree row by row. The payload controls therefore support the mechanism in Proposition 6: fan-out creates a large topology advantage only when each repeated edge carries substantial avoidable fresh-input workload. I.6 Support-Width Heterogeneity as a Boundary Case Structural cell η Treatment [95% CI] Control [95% CI] Treatment–control [95% CI] CI >0>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 Table 15: Region-inspired support-width contrasts. Treatment and control preserve provider means while varying support widths and aggregate dispersion. The parameter η scales each cost range’s half-width around its fixed mean: treatment half-widths are 20%, 50%, or 90% of the mean, multiplied by η; control half-widths are uniformly 50%×η50\%×η. The S4 cell uses cached-input fraction κ=0.1κ=0.1. Each paired-bootstrap interval resamples n=50n=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. The region-inspired experiment varies synthetic support-width profiles while holding normalized provider means fixed, allowing aggregate dispersion to change with the treatment. In the tested degree-100 and S4 cells, the additional treatment-control payment reduction is modest and its 95% interval includes zero. These paired estimates characterize the payment effect and uncertainty for the documented synthetic profiles, complementing the prior-shape comparisons above. I.7 Prior Misspecification and Runtime Details Prior-estimation-error magnitude grid (E2). The experiment uses the original five provider cost ranges, eligibility rules, degree-10 fan-out graph, ρ=1/3ρ=1/3, and cache semantics. The uniform profile has ki=1k_i=1 for all providers; the heterogeneous power-prior profile uses k=(0.5,2,0.2,5,1)k=(0.5,2,0.2,5,1), the same provider-specific shapes used in Table 2. Appendix I.2 gives their cost ranges. For each profile, we evaluate eight scoring conditions: correct-prior Star, six signed shape perturbations k^i=kieδri k_i=k_ie^δ r_i with r=(1,−1,0,1,−1)r=(1,-1,0,1,-1) and δ∈−0.2,−0.1,−0.05,+0.05,+0.1,+0.2δ∈\-0.2,-0.1,-0.05,+0.05,+0.1,+0.2\, and Raw-DSIC. These controlled parameter errors leave each provider’s true cost and truthful report unchanged. Before execution, we fix 1,000 new draw identifiers (30,000–30,999) per profile and retain every draw and signed perturbation. Each draw’s latent quantiles are shared across the two true profiles, and within a profile all scoring conditions share the identical true cost vector. The shapes obey k^i/ki∈[e−m,em] k_i/k_i∈[e^-m,e^m] at magnitude m=|δ|m=|δ|. For m=0.05,0.1,0.2m=0.05,0.1,0.2, the maximum decreases are 4.88%4.88\%, 9.52%9.52\%, and 18.13%18.13\%, and the maximum increases are 5.13%5.13\%, 10.52%10.52\%, and 22.14%22.14\%, respectively. The fixed direction permits a matched comparison of both signs as the error magnitude grows. Table 16 gives all condition-level payment decompositions and changes from correct-prior routing. All 95% intervals use 2,000 resamples of the 1,000 paired draw identifiers, with scoring conditions resampled together. The new cohort is analyzed separately from earlier runs; its means are not pooled with earlier draws. True prior Scoring condition P CexecC_ exec R P−PcorrectP-P_ correct (95% CI) Allocation disagreement Uniform Correct prior 0.939 0.686 0.254 +0.0000 [+0.0000,+0.0000] 0.0% Uniform δ=−0.2δ=-0.2 0.944 0.692 0.252 +0.0043 [-0.0012,+0.0096] 7.0% Uniform δ=−0.1δ=-0.1 0.940 0.688 0.252 +0.0008 [-0.0019,+0.0035] 3.5% Uniform δ=−0.05δ=-0.05 0.939 0.686 0.253 -0.0005 [-0.0019,+0.0008] 1.0% Uniform δ=+0.05δ=+0.05 0.940 0.685 0.255 +0.0007 [-0.0006,+0.0020] 1.9% Uniform δ=+0.1δ=+0.1 0.942 0.685 0.256 +0.0023 [-0.0002,+0.0047] 3.4% Uniform δ=+0.2δ=+0.2 0.945 0.686 0.260 +0.0056 [+0.0013,+0.0102] 6.8% Uniform Raw-DSIC 0.947 0.682 0.265 +0.0075 [+0.0029,+0.0119] 8.9% Heterogeneous Correct prior 0.694 0.564 0.130 +0.0000 [+0.0000,+0.0000] 0.0% Heterogeneous δ=−0.2δ=-0.2 0.693 0.557 0.136 -0.0012 [-0.0052,+0.0025] 3.1% Heterogeneous δ=−0.1δ=-0.1 0.693 0.560 0.133 -0.0010 [-0.0042,+0.0018] 1.7% Heterogeneous δ=−0.05δ=-0.05 0.694 0.563 0.132 +0.0003 [-0.0013,+0.0018] 0.7% Heterogeneous δ=+0.05δ=+0.05 0.695 0.565 0.129 +0.0006 [-0.0009,+0.0027] 0.5% Heterogeneous δ=+0.1δ=+0.1 0.695 0.567 0.128 +0.0013 [-0.0010,+0.0037] 1.1% Heterogeneous δ=+0.2δ=+0.2 0.693 0.567 0.126 -0.0008 [-0.0045,+0.0028] 2.0% Heterogeneous Raw-DSIC 0.992 0.476 0.516 +0.2980 [+0.2754,+0.3195] 26.6% 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 ki=1k_i=1 for all providers; heterogeneous denotes the provider-specific vector k=(0.5,2,0.2,5,1)k=(0.5,2,0.2,5,1) in Table 2. Only assumed shapes vary, with δ=±0.05,±0.1,±0.2δ=± 0.05,± 0.1,± 0.2. Payment is P=Cexec+RP=C_ 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. Optimization runtime (E1). These central processing unit (CPU) measurements time the task-assignment and payment optimizations required to run Star on a supplied workflow and provider reports. Synthetic graphs provide controlled inputs to those same computations. The reported mechanism time includes constructing and solving the allocation problems, report-independent tie-breaking, and every active provider’s payment computation; graph generation is outside this timer. On one Apple M2 Pro processor, all 36 chain/sparse-DAG instances complete within the time limits. We test 8, 32, and 64 task nodes, with 3 or 5 providers and three seeds. The largest complete-mechanism time is 0.7670.767 seconds. Peak sampled memory is 268.9268.9 mebibytes (MiB), measured as the summed resident set size (RSS, physical memory occupied) of the Python worker and all CBC solver processes it launches, including their subprocesses. Memory is sampled every 20 milliseconds. CBC uses one thread, zero requested relative and absolute optimality gap, and a 30-second limit for each allocation optimization. Each complete mechanism has a 180-second limit. Table 17 summarizes the timings by workflow size, and Table 18 gives the graph-family and provider-count breakdown. |T||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 Table 17: Full-mechanism CPU scaling. Times aggregate the chain and original sparse-DAG generators, provider counts N∈3,5N∈\3,5\, and three seeds. Allocation and all-provider payment columns are medians; max total retains the slowest completed instance. family |T||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 sparse DAG 8 3 3/3 0.068 0.101 182.6 sparse DAG 8 5 3/3 0.070 0.119 181.6 sparse DAG 32 3 3/3 0.090 0.175 187.0 sparse DAG 32 5 3/3 0.122 0.245 189.1 sparse DAG 64 3 3/3 0.134 0.296 193.1 sparse DAG 64 5 3/3 0.201 0.513 204.3 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. I.8 Experiment Coverage and Validation The evaluation includes every pre-specified synthetic structural-stress and prior-continuum cell. E1 completes 36/36 instances, and E2 includes all 16,000 pre-specified condition-level results across both true profiles and all eight scoring conditions per profile. Every allocation optimization reports status Optimal with zero reported gap; the E2 minimum truthful provider utility is zero and payment-decomposition errors are at numerical precision. In every checked instance, when providers report their actual unit costs, Raw-DSIC assigns each task to exactly the same provider as the execution-cost-minimizing oracle. Appendix J Disclosure of AI Assistance OpenAI Codex assisted with language editing, LaTeX formatting, and implementing, running, and checking experiment code under the authors’ direction. The authors are responsible for the final manuscript, experiments, and references.