acceptodds
Under review as a conference paper at ICLR 2027

Cost or Coverage: Agent Orchestration under Access Scopes

Abstract

As LLM-based multi-agent systems grow more complex, orchestration increasingly requires coordinating specialized agents while controlling resource use. When agents have overlapping access to information sources and different engagement costs, this becomes a joint inference-and-allocation problem: the orchestrator must infer which sources contain the required evidence and select a low-cost agent set that covers them. Whether current LLMs can coordinate these decisions remains unclear. To quantify the orchestrators' coordination capabilities, we compile a benchmark containing 178 two-source queries, a fixed team of eight access-scoped agents, two retrieval-grounded engagement-cost schemes, and oracle retrieval that isolates orchestration from retriever error. Across eight model configurations, first-attempt behavior separates into narrow commitment, which limits cost but frequently misses required sources, and broad hedging, which achieves higher coverage through substantial over-engagement. Revealing the required sources largely resolves the former but not the latter. In the revision round, outcome feedback facilitates correction, while cost feedback can induce more restrained routing but does not reliably reduce cost without sacrificing task success. Overall, models respond well to individual source or cost signals, but struggle to balance them when both coverage and cost must be optimized jointly.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, agent orchestration, cost-aware delegation, retrieval routing, evaluation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_1xr5OpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies cost-or-coverage orchestration: an LLM must infer which sources a query needs and engage a cheap set of access-scoped agents that covers them. It builds CoC-Bench (178 two-source questions, eight agents with overlapping scopes, two scope-based pricing schemes, oracle retrieval) and finds that models either route narrowly and miss sources or route broadly and overspend.

Critical strengths
  1. The setup isolates routing cleanly. Oracle retrieval, the corpus-wide uniqueness audit, and the gold_route condition separate source inference from agent allocation.
  2. The diagnostic conditions are well chosen: unit vs. agent pricing, repricing with known sources, re-granted teams, and paired bill-disclosure contrasts in revision.
  3. Uncertainty reporting is careful. Contrasts are paired by question and draw. An effect is flagged only when it exceeds both bootstrap and draw-level noise.
Critical weaknesses
  1. The central claim is not identified. Gold_route shows that allocation is easy once sources are known. Low first-attempt coverage may therefore only mean that source inference is hard, or even impossible for questions stripped of platform names. The paper never measures how inferable the sources are.
  2. There is no reference point for good performance. Costs are compared with the hindsight optimum c*, so every model falls short by construction, and no simple baselines are reported. Under access-scope pricing, a fixed product_mgmt + sre_oncall route covers all ten units at about 39% of full-team cost. IDENT also lacks a size-matched chance level: Scout’s 60% under agent_pricing is close to what random picks of 5.5 agents give.
  3. The cost model penalizes broad routing. Prices scale linearly with scope size, yet Appendix D shows prompt tokens growing only about 2.2x over an 80x larger scope. Oracle retrieval also removes the recall gain from redundant agents. The reported 7x to 12x over-engagement depends on these choices.
Questions for authors
  1. When asked only to name the required source units, how accurate are the models? How does a predict-then-solve pipeline (predicted sources passed to an exact set-cover solver) compare with direct routing?
  2. The round-one bill can be computed from prices the model already has. Would feedback that carries new information, such as the cheapest covering cost, change the conclusion that cost feedback does not produce cost-effective correction?
  3. With one top-up round, Qwen3.5-122B reaches 83% coverage at EFF-OPT 3.31. Llama-4-Scout, in a single round, scores 6.98. If both rounds are scored on total spend c(S1∪S2), is narrow commitment a failure mode or a reasonable exploration strategy?
2 comments
AuthorsOpenReview ↗

Author Response (Part 1/2): Critical Weaknesses

We thank the reviewer for the detailed feedback. We address the concerns below.

W1. Central claim

We would like to clarify that Gold-route is designed to isolate agent selection from source uncertainty, rather than suggest that agent allocation is universally easy. While some models achieve near-optimal selection when sources are known, others continue to over-engage agents even under Gold-route. Our central claim is that LLMs struggle to assign tasks to agents cost-efficiently while satisfying source coverage requirements under uncertainty. This joint task cannot be reduced to source identification alone or to agent selection when the required sources are given, as the orchestrator must make allocation decisions without knowing exactly where the required evidence is located. We further investigate this distinction through the new decomposition baseline reported in our response to Q1.

W2. Evaluation metrics

We would like to clarify that c* is the query-specific minimum covering cost, providing an exact reference for evaluating routing efficiency rather than an arbitrary fixed baseline. Models can achieve COST-R = 1, as demonstrated under Gold-route.

The suggested fixed product_mgmt + sre_oncall route guarantees coverage by accessing all ten sources, but does not perform query-specific cost optimization. While this solution may appear straightforward to a human observer, some models engage even more agents than this fixed pair. This illustrates that models do not necessarily succeed at reasoning about source requirements and selecting appropriate agents, even when a simple full-coverage solution exists. Identifying where and why models struggle with these decisions is precisely the motivation for our evaluation.

Importantly, our five metrics are designed to capture complementary aspects of routing performance and should be interpreted jointly. IDENT measures whether the selected agents include an optimal covering combination, not whether the entire assignment is cost-efficient. For example, Scout's relatively high IDENT comes with substantial redundant engagement, reflected in its high COST-R and EFF-OPT. Therefore, our conclusions do not rely on IDENT in isolation or require it to serve as a size-adjusted measure of routing quality.

W3. Cost assumptions

We agree that excess-cost magnitudes depend on pricing, but making broader engagement more expensive does not itself establish an unfair penalty: our benchmark asks whether models choose economical routes under explicitly stated costs. Crucially, under gold_route, source uncertainty is removed, yet Scout still spends 5.82× and 7.97× the minimum covering cost under the two schemes, while several other models achieve essentially complete coverage near the optimum. This demonstrates avoidable expenditure under the specified costs. Appendix D motivates breadth-based proxies rather than proving linear scaling; moreover, the reviewer’s 80× scope range and 2.2× aggregate token comparison are not matched scaling measurements. Oracle retrieval deliberately isolates routing from retrieval reliability, so redundancy’s potential recall benefits fall outside this controlled setting. We will clarify that the quantitative ratios are conditional on our pricing assumptions.

AuthorsOpenReview ↗

Author Response (Part 2/2): Questions

We address the three questions below.

Q1. Source inference baselines

To further investigate this distinction, we implemented the Source-inference baseline where an LLM predicts candidate sources and an exact minimum-cost set-cover algorithm selects the agents. The results are shown in the table below.

ModelConditionCOVER#AGENTSCOSTCOST-R
GPT-5.6-solAgent-pricing28%1.24124.21.36
Gold-route100%1.48219.81.00
Source-inference (k=2)44%1.07222.81.87
Source-inference (k=4)62%1.44322.82.31
Source-inference (k=6)82%1.70421.82.98
Source-inference (k=8)96%2.00511.73.71
Fixed-agents (Full-coverage)100%2.00534.03.85
Qwen3.5-122BAgent-pricing38%1.86207.42.35
Gold-route100%1.48219.81.00
Source-inference (k=2)35%1.09224.62.05
Source-inference (k=4)58%1.38326.92.53
Source-inference (k=6)83%1.74412.43.15
Source-inference (k=8)97%2.01501.03.67
Fixed-agents (Full-coverage)100%2.00534.03.85
Llama-4-ScoutAgent-pricing90%5.53934.27.28
Gold-route99%4.39830.25.82
Source-inference (k=2)17%1.01118.81.46
Source-inference (k=4)43%1.61262.92.57
Source-inference (k=6)63%2.01367.62.90
Source-inference (k=8)90%2.19483.53.35
Fixed-agents (Full-coverage)100%2.00534.03.85

Table: Access-scope pricing. Source-inference uses LLM-ranked top-k sources and an exact solver; Fixed-agents covers all sources. COST averages all queries; COST-R is the mean ratio of cost to the query-specific minimum cost over covered queries.

For GPT and Qwen3.5-122B, Gold-route achieves near-optimal agent selection, while direct routing suffers from low coverage. The predict-then-solve approach achieves substantially higher coverage as the predicted source set expands, although at additional cost. In contrast, Llama-4-Scout exhibits weaker source inference performance and continues to over-engage agents even when gold sources are provided. Notably, the predict-then-solve approach achieves comparable coverage to Scout's direct routing at substantially lower cost.

The fixed full-coverage baseline is also included in the table for comparison. As clarified in W2, it guarantees coverage but does not provide query-specific cost-efficient routing.

Q2. Cost feedback in revision

We tested a third feedback condition, bill + c*, to both revision settings (blind do-over and outcome-shown top-up). Specifically, we added the following information to the prompt: "The minimum possible total cost for this question is X." We evaluated this condition using Qwen3.5-122B under access-scope pricing, following the same three-draw protocol.

ConditionCOVERIDENT#AGENTSCOST-R
Round one38%20%1.862.35
Do-over + bill31%20%1.631.79
Do-over + bill + c*90%89%1.591.00
Top-up + bill78%40%2.402.35
Top-up + bill + c*87%84%1.811.09

Table: Revision results for Qwen3.5-122B under access-scope pricing. c* denotes the query-specific minimum covering cost. Metrics are computed on the complete second-turn assignment.

The results show substantial improvements, but also reveal an important issue: providing c* can indirectly reveal the optimal agent combination. For example, if support_eng is the only agent combination costing 296, telling the model that the minimum cost is 296 effectively identifies the agent to select.

This explains the large improvement from do-over + bill to do-over + bill + c*, even without retrieval outcome feedback. Therefore, the improvement cannot be attributed solely to better cost-aware reasoning, since the additional information may effectively reveal the answer.

Q3. Narrow commitment and multi-round exploration

We agree that narrow initial routing may be a reasonable exploration strategy in a multi-round setting. However, our primary task evaluates a single agent-selection decision before retrieval feedback is available. The revision experiments in Section 5 are designed to examine whether models can repair earlier routing failures after receiving feedback, rather than to evaluate an optimized multi-round routing strategy. We agree that studying how models balance initial exploration, subsequent correction, and cumulative costs in multi-round orchestration is an interesting direction for future work.

Reviewer_zsSoOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces CoC-Bench, a benchmark for evaluating cost-aware orchestration in multi-agent systems with heterogeneous access scopes. The key motivation is that LLM orchestrators must jointly infer the information sources required by a query and select a low-cost set of agents that covers them. The authors construct 178 two-source queries involving eight agents and two engagement-cost schemes. They evaluate eight model configurations under different pricing, source-information, and revision conditions.

Overall, the paper addresses a practically relevant problem and provides a systematic empirical analysis of the trade-off between source coverage and agent engagement cost.

Critical strengths
  1. The paper identifies an important challenge in multi-agent orchestration. Evaluating the ability to jointly infer required sources and allocate agents is meaningful and valuable.

  2. The experimental design includes multiple diagnostic conditions, such as gold-route information, alternative pricing representations, and agent access-scope reassignment. These experiments help distinguish failures caused by source inference from those caused by redundant agent engagement.

  3. The experiments span eight model configurations and more than 51,000 routing decisions, revealing two distinct routing styles: some models trade coverage for lower cost, while others achieve higher coverage through substantial over-engagement.

Critical weaknesses
  1. The paper lacks a baseline that separates source inference from agent selection. For example, an LLM could first predict the required sources, followed by an optimization algorithm to select the cheapest agents. Although the gold-route experiments show that source uncertainty is a major challenge, it remains unclear whether jointly performing these two tasks is more difficult than solving them in two separate stages.

  2. The benchmark is limited to 178 questions from a single synthetic enterprise corpus, each requiring exactly two source units. According to Table 2, 144 of the 178 questions can be covered by a single agent. Also, oracle retrieval removes actual retrieval failures. These simplifications raise concerns about whether the observed behaviors generalize to more complex multi-agent orchestration scenarios.

Questions for authors
  1. Can the authors compare against a decomposition-based baseline that first predicts the required sources and then uses an exact optimization algorithm to select the minimum-cost agent set?

  2. How well do the findings generalize to more complex multi-agent scenarios, particularly those involving more than two required sources and real retrieval failures?

2 comments

We thank the reviewer for recognizing the importance of jointly evaluating source inference and cost-aware agent allocation, as well as the value of our diagnostic experiments. We address the two concerns below.

Q1. Decomposition-based baseline

We added a two-stage baseline, Source-inference, where an LLM first ranks the ten source units by their likelihood of containing the required evidence. We also tested asking the model to directly select k sources and found that the selected sources largely matched the top-k sources from its ranking. We therefore use a prompt consistent with our original routing setup, but remove the agent information and ask the model to rank the most likely sources. An exact minimum-cost set-cover algorithm then selects the cheapest agent set covering the top-k inferred sources, based on agent access scopes and prices.

We evaluate this baseline with different values of k and compare it with Agent-pricing, Gold-route, and Fixed-agents, a question-independent baseline covering all ten source units. We follow the same three-draw evaluation protocol as in the original paper. Below, we report results for three representative models; the full results will be added to the appendix.

ModelConditionCOVER#AGENTSCOSTCOST-R
GPT-5.6-solAgent-pricing28%1.24124.21.36
Gold-route100%1.48219.81.00
Source-inference (k=2)44%1.07222.81.87
Source-inference (k=4)62%1.44322.82.31
Source-inference (k=6)82%1.70421.82.98
Source-inference (k=8)96%2.00511.73.71
Fixed-agents (Full-coverage)100%2.00534.03.85
Qwen3.5-122BAgent-pricing38%1.86207.42.35
Gold-route100%1.48219.81.00
Source-inference (k=2)35%1.09224.62.05
Source-inference (k=4)58%1.38326.92.53
Source-inference (k=6)83%1.74412.43.15
Source-inference (k=8)97%2.01501.03.67
Fixed-agents (Full-coverage)100%2.00534.03.85
Llama-4-ScoutAgent-pricing90%5.53934.27.28
Gold-route99%4.39830.25.82
Source-inference (k=2)17%1.01118.81.46
Source-inference (k=4)43%1.61262.92.57
Source-inference (k=6)63%2.01367.62.90
Source-inference (k=8)90%2.19483.53.35
Fixed-agents (Full-coverage)100%2.00534.03.85

Table: Access-scope pricing. Source-inference uses LLM-ranked top-k sources and an exact solver; Fixed-agents covers all sources. COST averages all queries; COST-R averages cost/c* on covered queries.

The results suggest that separating source inference from agent selection can alleviate some difficulties, but does not fully resolve the problem under source uncertainty.

By comparing joint routing with the two settings where the LLM handles only agent selection (Gold-route) or only source inference (Source-inference), we observe different behaviors across models.

GPT and Qwen3.5-122B achieve near-optimal agent selection when given the gold sources. Although their source inference is less accurate, expanding the predicted source set allows the two-stage approach to achieve substantially higher coverage than joint routing, at the expense of additional cost. While it remains less efficient than Gold-route, this suggests that performing source inference and cost-aware agent selection jointly introduces additional challenges.

Llama-4-Scout, in contrast, exhibits substantial over-engagement in joint routing, achieving high coverage at a much higher cost. Its agent selection remains inefficient even with gold source information. The decomposition baseline further reveals weaker source inference performance than GPT and Qwen3.5-122B, as reflected by its consistently lower coverage at the same k.

Q2. Generalization to more complex orchestration scenarios

Regarding the concern that 144 of 178 questions can be covered by a single agent, this does not mean that selecting one agent is always the most cost-efficient solution. In some cases, selecting two agents with narrower access scopes can be cheaper than selecting one broad-access agent. Narrower search scopes may also improve retrieval efficiency and accuracy in practice. Our benchmark is designed to evaluate whether models can recognize these cost differences and select more efficient agent combinations.

Indeed our controlled setting does not equal real-world orchestration which may include many tasks requiring more than two source units and imperfect retrieval. Our experiments with alternative pricing schemes and reassigned agent access scopes provide additional robustness checks. We will further clarify the generalization potential in the paper and consider more complex source requirements and imperfect retrieval in future work.

I appreciate the rebuttal. It has fully resolved my concerns.

Reviewer_ZHwiOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates cost-aware orchestration in LLM-based multi-agent systems with overlapping access scopes. It introduces CoC-Bench, comprising 178 two-source questions, and evaluates eight model configurations under different cost schemes. Using oracle retrieval, it isolates orchestration errors and examines how source information, outcome feedback, and cost feedback affect routing and correction.

Critical strengths
  1. Access control, information coverage, and cost management are important practical challenges in deploying multi-agent systems. The paper's strongest contribution is not simply identifying a cost–coverage trade-off. It attempts to separate source inference from cost-aware agent selection, then tests whether LLMs can solve these two decisions jointly.

  2. The benchmark contains 178 automatically generated two-source questions, and the evaluation uses a fixed team of access-scoped agents with oracle retrieval. This controlled setup is useful for diagnosing routing behaviour, although it does not establish whether the observed patterns persist in more diverse tasks, larger source spaces, or systems with more complex agent interactions.

  3. The analysis of routing behaviours and corrective decisions is potentially useful for future work on reliable and efficient multi-agent orchestration.

Critical weaknesses
  1. The coverage–cost trade-off is intuitive, and the paper needs to clarify its novel conceptual or empirical insights beyond this basic trade-off. Its contribution should also be better distinguished from existing work on cost-aware retrieval, resource allocation, and selective agent delegation.

  2. The engagement-cost models may not reflect real-world costs. The two pricing schemes help study cost sensitivity but are simplified proxies. Actual costs may also include latency, token usage, repeated calls, tool failures, and recovery overhead. The authors should clarify which conclusions hold across different cost models and which depend on the chosen schemes.

  3. The results suggest that models struggle to balance source coverage and cost. However, it is unclear how well this finding generalises beyond the tested settings. The authors should clarify whether models fail to interpret cost feedback, identify the cheapest suitable agents, or deliberately accept higher costs for better coverage or confidence.

Questions for authors
  1. What is the principal insight that distinguishes this work from existing evaluations of cost-aware retrieval, agent selection, and resource allocation? Can the authors articulate a generalisable finding beyond the observed narrow-versus-broad routing spectrum?

  2. How sensitive are the conclusions to the use of two-source questions and a fixed team of eight agents? Would the main routing patterns be expected to persist with more required sources, larger agent teams, or more complex access-scope overlap?

  3. To what extent do the conclusions depend on the two structural pricing schemes? Could the authors provide additional analysis showing whether the main findings hold under alternative cost distributions or more deployment-oriented cost measures?

1 comment

We thank the reviewer for the constructive feedback and for recognizing the importance of our controlled evaluation. We address the three questions below.

Q1. Main contribution and novel insights

We agree that the existence of a cost–coverage trade-off is intuitive. We want to emphasize that making cost-efficient orchestration decisions is not straightforward, especially when the required information sources are unknown and agents have overlapping access scopes.

Existing studies have explored workflow optimization, resource allocation, selective agent delegation, and cost-aware retrieval. Our work focuses on a complementary question: whether current LLM orchestrators can jointly (1) infer uncertain source requirements and (2) select cost-efficient agents.

Our controlled evaluation is designed to identify the capability boundaries of LLMs in this setting. We find that some models can select nearly optimal agents when the required sources are explicitly provided, but struggle when they must also infer the sources, as in more realistic retrieval scenarios. Other models struggle to select cost-efficient agent combinations even when the required sources are known. Our revision experiments further show that models may respond to changes in agent prices without consistently making cost-efficient routing decisions.

In summary, our main contribution goes beyond observing the trade-off itself. We identify the challenges involved in (1) source inference and (2) cost-aware agent selection. Additionally, we demonstrate the limitations of current LLMs in jointly handling these decisions.

Q2. Generalization across source requirements and agent teams

Our controlled setting can be applied to larger agent teams or tasks requiring more than two sources without loss of generality. Our experiments include two independently re-granted agent teams (Section 4.5), where source access is reassigned while the questions and agent count remain unchanged. Qwen3.5-122B continues to exhibit narrow routing, while Llama-4-Scout maintains broad engagement across these configurations, including under Gold-route. These results suggest that the observed routing behaviors are not specific to the original access-scope assignment.

Q3. Robustness to pricing schemes

The two pricing schemes are designed to be substantially different: access-scope pricing based on total accessible documents and candidate-breadth pricing based on customer-specific candidate documents. Although the numerical cost ratios differ, the main routing patterns remain consistent across both schemes.

Indeed, these structural proxies are not real-world deployment costs, and the exact cost ratios depend on the pricing assumptions. However, our main claim concerns the difficulty LLMs face in balancing source coverage and cost-efficient agent selection, which is supported by consistent observations across both pricing schemes.

Comments on the paper

1 comment
Area_Chair_drC9OpenReview ↗

Author-Reviewer Discussion

Dear Reviewers,

The authors have provided the rebuttal. Please have a look and let the authors know if you need further clarification or still have follow-up questions.

Thanks, Your AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.