acceptodds
Under review as a conference paper at ICLR 2027

AgentQoSBench: Evaluating Quality-of-Service Awareness in Agents under Complex Tool Dependencies

Abstract

Agents increasingly handle tasks with complex tool dependencies. Beyond correct completion, users have service-quality requirements or preferences. Quality of service (QoS), rooted in networking and service computing, describes latency, cost, and reliability. We evaluate agents' QoS awareness by extending QoS-aware service composition to autonomous planning with tool-call graphs, jointly assessing tool selection, dependencies, and whole-graph optimization. We introduce QoSGen (Quality-of-Service-Aware Benchmark Generation), a construction and validation pipeline that produces AgentQoSBench: 600 synthetic tasks across consumer and workplace scenarios with multiple valid plans and exact optima under explicit service models grounded in tool characteristics and composition mechanisms. For 49.7% of functionally valid tool-call plans produced by mainstream models, we verify a complete alternative with strictly better QoS. Using failure diagnosis and reasoning traces, we analyze agents' graph-search behavior, showing how local choices can overlook sharing and parallelism or create cross-branch conflicts. These findings motivate training-free search prompting and prompt-guided graph-search assistance. Prompting improves optimization within valid plans for GLM and DeepSeek, while tool assistance highlights the importance of preserving task requirements during candidate integration. Together, these approaches offer practical directions for improving QoS awareness through whole-graph comparison and agent-tool collaboration.

Primary area:
datasets and benchmarks
Keywords:
quality of service, tool-use agents, tool-call graph planning, dependency reasoning, large language models, agent benchmarking

Reviews

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

The paper introduces AgentQoSBench, a benchmark of 600 synthetic tasks evaluating whether agents can construct functionally correct tool-call graphs while optimizing latency, cost, and reliability under ordered priorities. Its construction pipeline, QoSGen, provides multiple valid solutions, exact reference optima, and extensive evaluator checks. Experiments with five models find that 49.7% of functionally valid plans remain non-optimal. Search prompting improves some models, while a paired graph-search assistance study shows that incorporating candidate plans can introduce errors and reduce functional success.

Critical strengths

Careful evaluation of valid alternatives. The evaluator checks task obligations rather than requiring agreement with a single reference graph. Exact optima and complete better-plan witnesses make the reported optimization failures concrete and verifiable. This is a substantial strength for a benchmark with many acceptable solutions.

Useful separation of planning and optimization failures. Functional success, conditional optimality, optimal prefixes, and gap magnitudes provide a more informative picture than a single success rate. The tool-assistance study is also valuable: it shows that finding candidate plans does not ensure that agents preserve the original task requirements when integrating them.

Critical weaknesses

The experiments do not sufficiently isolate QoS planning difficulty. Each input contains 454–534 tools and roughly 249,000–323,000 characters. Without controlled catalog-size or distractor ablations, it is difficult to distinguish optimization limitations from difficulty locating and tracking relevant information. Likewise, objective-count groups contain different tasks, so their performance differences do not isolate the effect of adding objectives. This limits the diagnostic conclusions drawn from the benchmark.

The intervention results have limited evidence of robustness. The search prompt was developed and evaluated on the same benchmark, with one retained answer per task and condition at temperature 1. Serving configurations also differ across portions of the comparison; for example, Terra’s overall decline becomes much smaller in the matched-configuration subset. The reported bootstrap intervals are useful, but do not resolve these issues. The gains therefore support a promising benchmark-specific observation more strongly than a broadly reliable improvement method.

Questions for authors
  1. Controlled evaluation: Do the main optimization failures persist with a reduced relevant-tool catalog? Can the same tasks be evaluated under different objective orders or counts to separate objective complexity from task differences?

  2. Experimental clarification: What serving-configuration changes occurred between conditions, and how were the matched-configuration subsets selected? Are repeated evaluations under fixed configurations, using tasks held out from prompt development, available?

3 comments
AuthorsOpenReview ↗

Response to W1 and Q1

“Controlled evaluation: Do the main optimization failures persist with a reduced relevant-tool catalog? Can the same tasks be evaluated under different objective orders or counts to separate objective complexity from task differences?”

Thank you for suggesting these controls. We tested how models’ plans changed when we narrowed the catalog and when we changed the QoS objectives on the same tasks.

1. Do optimization failures persist with a smaller catalog?

We worked backward from each task’s requirements using the public tool contracts. We kept tools that could meet a requirement directly, provide an input or establish a condition for a later call, or support an alternative route. This reduced the average catalog from 499 tools to 175.

For every task, we verified that the original optimal plan and at least one structurally different, strictly suboptimal plan remained valid, with the same QoS as before. Five models built their own tool-call graphs on the same 210 tasks under both catalogs. Only the catalog changed.

OutcomeFull catalogReduced catalogChange (pp)
Overall optimality rate (1,050 model–task pairs)34.4%40.1%+5.7
Suboptimal when both plans were valid (643 pairs)48.5%40.4%−8.1

Narrowing the catalog helped, but models still missed better plans with fewer tools to search. Among the 643 pairs where the model completed the task both times, suboptimality fell from 48.5% to 40.4%. In each of the 260 remaining cases, a better valid plan could be built using tools in the smaller catalog.

2. Varying the objectives and the tasks separately

We tested 70 benchmark tasks with a cost–latency trade-off under three requests. The functional requirements, tools, dependencies, and per-tool QoS values stayed fixed. We verified the optimum for each task under both priority orders. On all 70 tasks, switching priorities required a different plan to attain the optimum. DeepSeek-V4-Pro, GPT-5.6 Terra, and GLM-5.2 each answered every version.

On one reimbursement task, for example, DeepSeek’s cost-only plan had cost 40 and latency 40. Asked to break cost ties by latency, it kept the cost at 40 and cut latency to 34. With latency first, it chose a plan with cost 47 and latency 22. Each plan was optimal for the request the model saw.

Each row holds the tasks fixed. Each column holds the objectives fixed. Row labels give the original task groups. Each cell reports the percentage of plans optimal for the request the model actually saw.

Original task groupCost onlyCost first, then latencyLatency first, then cost
Two objectives originally (36 tasks)48.1%43.5%29.6%
Three objectives originally (34 tasks)55.9%55.9%39.2%

Adding an objective. From the first column to the second, adding latency as a tie-breaker lowered optimality by 4.6 percentage points in the first group and left it unchanged in the second. In 77 pairs the model achieved minimum cost both times. When the tie-breaker was explicit, 13 of those pairs went from a slower plan to the fastest at that cost. None went the other way. The extra objective set a stricter standard, but it also helped models choose among equally cheap plans.

Reversing the two priorities. The second and third columns use the same tasks and the same two objectives. With latency first, optimality was 13.9 and 16.7 percentage points lower in the two groups.

In 98 pairs the model achieved the best possible value of the first objective under both orders. With cost first, 94 of 98 plans were also the fastest at minimum cost. With latency first, only 58 of 98 were also the cheapest at minimum latency. On these tasks, models more often missed the tie-breaker when they had to find a cheaper plan among equally fast alternatives.

Same objectives, different tasks. Under all three requests, the models reached the optimum more often on the 34 tasks from the original three-objective group than on the 36 from the two-objective group. With cost first and latency as the tie-breaker, optimality was 55.9% in the three-objective group and 43.5% in the two-objective group under the same scoring rule, a difference of 12.4 percentage points. Differences between the original groups may therefore partly reflect which tasks they contain.

AuthorsOpenReview ↗

Response to W2 and Q2

“Experimental clarification: What serving-configuration changes occurred between conditions, and how were the matched-configuration subsets selected? Are repeated evaluations under fixed configurations, using tasks held out from prompt development, available?”

Thank you for suggesting that we repeat the prompt comparison under fixed serving configurations. We checked the serving records from the original experiment, ran both prompts twice more on the original tasks, and tested the finalized prompts on 200 held-out tasks.

1. What changed between conditions, and how did we select the matched subset?

In Table 4, both prompts used the same task input, sampling temperature, and reasoning setting. Several providers could serve the same model, so requests for the two prompts sometimes went through different routes and could return different model identifiers.

To reduce the influence of provider differences, we paired answers by model and task ID. The matched subsets in Appendix E include pairs for which both answers could be scored and the recorded serving route was the same.

2. Do the gains recur on the original tasks under fixed configurations?

The bootstrap intervals in the paper came from resampling the answers already collected. To measure variation across independent generations, we ran both prompts twice more on the 600 original tasks at temperature 1 and High reasoning effort.

For each model and task, both prompts had to yield scorable answers in all three runs. All six answers had to share the same recorded route and returned model identifier. The table shows how much the search prompt changed the overall optimality rate relative to the original prompt, in percentage points.

ModelOriginal runFirst rerunSecond rerun
GLM-5.2+16.13+12.10+16.94
DeepSeek-V4-Pro+7.87+11.81+11.02
GPT-5.6 Terra−1.95+1.95+2.44
Gemini-3.1-Pro+3.580.00−0.83
Qwen3.5-Flash+0.35−0.17+0.69

Under matched serving configurations, some models benefited from the search prompt in all three runs. For Terra, the model highlighted in the review, optimality was slightly lower with the search prompt in the original run and slightly higher in both reruns.

3. How did the search prompt perform on held-out tasks?

After finalizing both prompts, we used QoSGen to create 200 new tasks from tool APIs we collected from four real-world applications. We compared the original and search prompts on these held-out tasks.

Each model answered all 200 tasks, and we counted one answer per task and prompt. For each model and task, both prompts used the same serving route and returned the same model identifier. We estimated the 95% confidence intervals by clustering tasks that shared the same parent tool world.

ModelOptimality with original promptOptimality with search promptChange in pp [95% CI]
GLM-5.227.5%37.0%+9.5 [+2.4, +16.4]
DeepSeek-V4-Pro47.5%56.5%+9.0 [+1.4, +16.6]
GPT-5.6 Terra27.5%31.0%+3.5 [−3.5, +10.2]

On 116 held-out tasks, we had two runs of both prompts for Terra under the same serving configuration within each task. Terra’s optimality rate was slightly higher with the search prompt in both runs. It reached the optimum on three more tasks in the first run and five more in the second. Six GLM tasks and no DeepSeek tasks had two complete runs under this criterion.

All three models found optimal plans more often with the search prompt on the 200 held-out tasks, with gains of 3.5 to 9.5 percentage points. This provides evidence that the method generalizes across tasks. On the original tasks, some models benefited in all three runs under matched serving configurations, showing that the gains can be reproduced.

Thank you again for your careful review. We hope these new results address your concerns. We would be happy to discuss any remaining questions.

Thank you for the clarifications and additional experiments. They address my main concerns, but I believe my current rating remains appropriate.

Reviewer_sk4oOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

AgentQoSBench evaluates whether agents can construct functionally correct tool-call graphs that also optimize user-specified priorities over latency, cost, and reliability. The paper introduces QoSGen to generate 600 synthetic tasks with public tool contracts, multiple valid solutions, and exact reference optima under the stated execution semantics. Experiments with five models distinguish functional correctness from QoS optimality and analyze optimization gaps, priority attainment, and selected failure cases. The paper also evaluates search-oriented prompting and exposure to programmatic search results as training-free interventions.

Critical strengths
  1. The evaluation accommodates valid alternatives and provides concrete evidence of suboptimality. Plans are checked against public task and tool requirements rather than matched to a single reference graph. Within the declared semantics, the benchmark combines reference optima with valid plan witnesses and evaluator checks. In particular, the reported better complete plans for all 960 valid but non-optimal answers substantiate the existence of optimization headroom. This makes the evaluation more informative than functional success alone.

  2. The experiments demonstrate an optimization gap even when task completion is strong. DeepSeek-V4-Pro achieves 95.33% functional correctness but only 62.76% optimality among valid plans (Table 2). The prefix and gap analyses further distinguish failure on the highest-priority objective from remaining improvements on later priorities. These results provide useful evidence that producing a valid plan does not imply satisfying the user's service preferences optimally.

Critical weaknesses
  1. The incremental diagnostic value is not sufficiently established empirically. The paper appropriately positions its contribution as combining complex tool dependencies and task obligations with QoS optimization. However, the experiments establish that this combined setting is challenging more clearly than they establish what distinct capability gaps the combination reveals beyond existing QoS and cost-aware planning evaluations. The functional/optimality split, prefix analysis, and selected cases are useful, but they do not sufficiently separate difficulty in discovering relevant alternatives from difficulty in optimizing over them. The construction-side strategies in Appendix B use different information conditions and task subsets, so they do not resolve this attribution issue. A small set of matched controls, such as supplying relevant tools or a correct dependency structure, could clarify the additional diagnostic value. This matters because that value is central to the benchmark's significance.

  2. The main text does not explain the core benchmark construction clearly enough. Sections 4.1–4.3 describe task–world co-design, QoS assignment, alternative verification, and optimality checking in compressed terms. Important context about the generation units, input scale, and the semantic scope of exact verification appears mainly in Appendices A–C. Although Figures 1–2 and Appendix B.1 provide illustrations, the main text would benefit from a numerical example connecting a user request and tool contracts to two complete valid graphs, their QoS comparison, and the verification of the reference optimum. Since construction and evaluation are the central contributions, this presentation gap makes their novelty and measurement scope unnecessarily difficult to assess.

Questions for authors

AgentQoSBench uses synthetic tasks and predefined service attributes, and Appendix F acknowledges the assumptions of sufficient parallel capacity and independent call successes. To what extent should the observed optimization gaps be expected to transfer to deployed tool-using agents, where latency, resource contention, and failures can vary during execution? Is there evidence from execution traces or simulations with variable latencies and resource constraints supporting this transfer? Please clarify which findings are expected to generalize and which should remain limited to the current static setting.

4 comments
AuthorsOpenReview ↗

Response to W1 and W2

W1. Incremental diagnostic value

“The functional/optimality split, prefix analysis, and selected cases are useful, but they do not sufficiently separate difficulty in discovering relevant alternatives from difficulty in optimizing over them.”

Thank you for the suggestion. To distinguish route discovery from route selection, we designed a two-stage experiment on 60 tasks with multiple verified valid routes.

Stage 1. Constructing routes. We asked three models (DeepSeek-V4-Pro, GPT-5.6 Terra, and GLM-5.2) to propose 2–4 tool-call graphs per task from the full catalog. We compared the QoS of each model’s best valid proposal with the task’s verified global optimum.

Stage 2. Blind selection. For the 75 model–task pairs with at least two valid routes that differed in QoS, we shuffled and anonymized the model's valid proposals and hid their whole-graph QoS scores. We asked the same model to choose under the user's priorities and checked whether its final choice was among the best in its set.

Across 75 comparable candidate setsRate
Set contained a globally optimal route16.0% (12/75)
Final answer explicitly chose a best route in the set100% (75/75)

In 63 of the 75 sets, the model chose its best proposal, but none of its proposals reached the global optimum. The gap arose during construction. On one cost-only task, DeepSeek chose the cheapest of its four routes (217). None attained the verified minimum of 151.

“A small set of matched controls, such as supplying relevant tools or a correct dependency structure, could clarify the additional diagnostic value.”

We tested five models on the same 210 tasks, keeping all main experimental settings fixed except the tool catalog. Using the task requirements and public tool contracts, we kept tools that could meet a requirement, supply a necessary input, or support another valid route. Each reduced catalog retained a verified optimal route and at least one strictly suboptimal valid route. In both conditions, the models chose and connected the tools themselves.

OutcomeFull (avg. 499 tools)Reduced (avg. 175 tools)Change (pp)
Overall optimality rate34.4%40.1%+5.7
Suboptimality when both graphs were valid48.5%40.4%−8.1

A smaller catalog helped models find optimal routes even on tasks they could already complete. In pairs with valid graphs under both catalogs, suboptimality fell by 8.1 points, yet 40.4% of plans from the smaller catalog still had a better valid alternative.

In the blind test, models chose their best proposal in all 75 sets. In 63 of them, the global optimum required a route they had not proposed.

W2. Benchmark construction

“Although Figures 1–2 and Appendix B.1 provide illustrations, the main text would benefit from a numerical example connecting a user request and tool contracts to two complete valid graphs, their QoS comparison, and the verification of the reference optimum.”

In Sections 4.1–4.3 of the revision, we will use one workplace migration task to illustrate QoSGen. Starting from the user request and public tool contracts, we will show two complete graphs side by side, compare their QoS, and show how we verify the reference optimum.

The user asks to migrate group relationships, create three independent copies, and send records to internal and external recipients. One copy must accompany the migration result, and external recipients may see only public fields. The user prioritizes reliability, then latency, then cost. DeepSeek built two valid graphs from the full catalog of 491 tools.

  • Plan A uses the fast service for all three copies and reads the full and public records separately. It costs 55.
  • Plan B keeps the fast service for the copy due with the migration result. The other two finish in time with the slower service, saving 10 units (each costs 3 instead of 8). Reading the full records once and redacting them for external recipients costs 7+27+2 instead of 6+66+6, saving another 3.

Both graphs make 11 calls, each with success probability 0.99, so both have reliability 0.99110.99^{11}. Both also have latency 8. Within the finite domain of the public contracts, the solver followed the user's priorities in order. It verified that 0.99110.99^{11} is the highest attainable reliability and that 8 is the shortest latency at that reliability. With both fixed, it proved a lower bound of 42 on cost. Plan B passes the functional checks and costs 42, so it attains the reference optimum.

AuthorsOpenReview ↗

Response to Q1

“To what extent should the observed optimization gaps be expected to transfer to deployed tool-using agents, where latency, resource contention, and failures can vary during execution? Is there evidence from execution traces or simulations with variable latencies and resource constraints supporting this transfer? Please clarify which findings are expected to generalize and which should remain limited to the current static setting.”

Thank you for the suggestion. On 200 benchmark tasks where latency could affect the ranking, we varied tool latencies and limited concurrent calls. We tested correlated failures separately. For each task, we replayed the model’s valid submission A and a valid alternative B that ranked above A under the original assumptions. Both plans faced the same conditions and were compared using the user’s QoS priorities.

Variable latency. We simulated 200 runs per task. For each run, we set each tool's latency to 80%, 100%, or 120% of its nominal value with probabilities of 25%, 50%, and 25%, respectively. All calls to the same tool used the same multiplier in both plans for that run.

Resource contention. We allowed up to two concurrent calls per plan. Once all its dependencies had finished, a call joined the queue. If both slots were occupied, it waited until a slot opened. Calls started in the order they became ready, and waiting time counted toward the plan's latency. For the concurrency-only condition, we used nominal latencies and ran each plan once per task. The table reports how often B still ranked above A under the user’s priorities, weighting each task equally.

How the plans compared under the original assumptionsVariable latency aloneTwo-call concurrency limit aloneBoth
B was faster (76 tasks)96.07%76.32%71.70%
Latency was tied and a lower-priority objective favored B (124 tasks)70.46%48.39%44.34%

In deployments with similar latency variation and queuing, we expect initially faster plans to retain their advantage more often than plans that originally won on a lower-priority objective after a latency tie. We verified each task’s optimum under the static benchmark conditions and used it to measure how often a functionally valid plan could still be improved.

Correlated failures. We restored nominal latencies and sufficient parallel capacity. For repeated calls to the same tool, we assigned equal probability to sharing one uniform draw between 0 and 1 or taking an independent draw for each call. Each call succeeded if its draw was below its original success probability. This preserves each call's success rate while allowing several calls to fail together. Recomputing plan reliability under this assumption put A ahead of B in 4 of the 200 pairs.

Thank you again for reading our paper so carefully and for your thoughtful suggestions on how to strengthen the experiments. We hope our responses address your concerns and that you will consider the new results in your final assessment. We would be happy to discuss any remaining questions.

Thank you for the detailed response and additional experiments. The new analyses and clarifications address my main concerns about the benchmark. I will raise my overall rating accordingly.

AuthorsOpenReview ↗

Thank you for your follow-up

We’re glad our additional analyses and clarifications addressed your main concerns about AgentQoSBench. We appreciate your decision to raise your overall rating. Your feedback means a lot to us.

It looks like the update hasn’t appeared on OpenReview yet. If you have any further questions or concerns, we’d be very happy to discuss them with you.

Thank you again for your thoughtful review and for supporting our work.

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

This paper investigates quality-of-service (QoS)-aware planning under complex tool dependencies and introduces QoSGen, a benchmark generation and validation pipeline for constructing AgentQoSBench. The benchmark evaluates agents' ability to construct functionally valid tool-call graphs while optimizing latency, cost, and reliability against verified exact optima. The authors evaluate several LLMs and explore search prompting and graph-search assistance. Experiments reveal a substantial gap between functional correctness and QoS optimality. While search prompting improves some models, graph-search assistance provides inconsistent benefits. The paper offers a systematic evaluation framework and useful failure analyses, but questions remain regarding real-world generalization, comparisons with existing planning methods, and the effectiveness of tool-assisted optimization.

Critical strengths
  1. Clear and meaningful problem formulation. The paper goes beyond functional task completion by evaluating whether agents can optimize user-specified QoS objectives. Its graph-based formulation explicitly considers tool dependencies, shared operations, and parallel execution, providing a useful perspective on tool-use planning.

  2. Systematic benchmark construction and validation. QoSGen generates multiple valid plans and establishes exact reference optima through search or SMT solving and functional verification. Extensive validation controls further strengthen the benchmark's reliability and reproducibility.

  3. Informative experimental analysis. The paper investigates different QoS objectives, failure categories, optimal prefixes, optimization gaps, and plan rankings. These analyses reveal important limitations of current agents, particularly in cost optimization and candidate integration.

Critical weaknesses

Major Weaknesses:

  1. Limited task diversity and real-world generalization. AgentQoSBench contains synthetic tasks constructed from a limited set of predefined mechanisms and contracts. Despite the large tool catalogs, the paper lacks evaluation on real-world workflows or unseen tool mechanisms. Moreover, the lengthy tool descriptions may affect models differently due to context-window limitations. I suggest evaluating unseen tool environments and reporting actual input token counts and potential truncation across models.

  2. Insufficient comparisons with existing cost-aware planning methods. The experiments mainly compare general-purpose LLMs without evaluating specialized planning approaches. CATP-LLM [1], for example, investigates cost-aware tool planning with non-sequential branching plans and is relevant to this benchmark. Although related work is discussed, no direct performance comparison is provided. I suggest evaluating representative planning methods on compatible tasks, particularly single-objective cost optimization, or clarifying why such comparisons are infeasible.

  3. Unclear effectiveness of graph-search assistance. Table 5 shows that exposing graph-search results reduces average overall optimality from 30.82% to 29.65%, with larger declines for GLM and DeepSeek. It remains unclear whether this degradation results from poor search candidates or errors in their integration. I suggest reporting candidate-level functional validity, QoS optimality, and cases where better candidates are generated but incorrectly integrated into final plans.

  4. Insufficient cross-run stability and prompt component analysis. Although Appendix E.3 reports bootstrap confidence intervals, each model–task–condition combination contains only one generated response, leaving variability across independent runs insufficiently examined. Moreover, the same search prompt improves GLM and DeepSeek but degrades GPT-5.6 Terra. I suggest repeated runs and component-level ablations of backtracking, dependency checking, and whole-graph comparison to clarify the sources of these differences.

Reference

[1] Wu D, Wang J, Meng Y, et al. CATP-LLM: Empowering Large Language Models for Cost-Aware Tool Planning[C]//Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). 2025: 8699–8709.

Minor Weaknesses:

  1. The scope of exact optimality should be clarified. Appendix C indicates that optimality certification applies to a restricted semantic domain and supported tool operations. I suggest explicitly stating these limitations in the main text to avoid implying optimality guarantees for arbitrary real-world workflows.

  2. Reproducibility details could be more accessible. Given the extensive tool catalogs and reliance on closed-source APIs, I suggest providing a concise table of model versions, evaluation dates, input token counts, reasoning configurations, and context-window handling procedures.

Questions for authors
  1. Have the authors evaluated AgentQoSBench on unseen tool mechanisms or alternative tool catalog organizations? Could they also clarify the actual input token counts and whether any model experienced input truncation?

  2. Is it feasible to compare CATP-LLM [1] or other cost-aware planning methods on compatible benchmark subsets? If not, what prevents a meaningful comparison?

  3. In Table 5, does the performance degradation mainly originate from the quality of graph-search candidates or from errors during candidate integration? Could the authors provide candidate-level validity and optimality statistics?

  4. Could the authors report results across independent generation runs and provide ablations to distinguish the contributions of different search-prompt components?

6 comments
AuthorsOpenReview ↗

Response to W1 and Q1 — Tool environments, catalog order, and input length

“Have the authors evaluated AgentQoSBench on unseen tool mechanisms or alternative tool catalog organizations? Could they also clarify the actual input token counts and whether any model experienced input truncation?”

1. Generalization to new tool environments

Thank you for suggesting that we test the benchmark in new tool environments. We collected 55 actions from Pipedream’s public catalog for two consumer applications (Eventbrite for ticketing and Splitwise for shared expenses) and two workplace applications (Notion for documents and Gmail for email). We used QoSGen to create 200 new tasks, one from each of 200 original tasks, with 50 per application. Each adaptation preserved the original QoS priorities and changed one part of the task to reflect the API rules documented in the action code and the official API reference. For example, when a Splitwise query specifies both a group and a friend, the API filters by group alone. The plan must then identify the expenses shared with that friend.

We took one verified optimal graph from each original task and scored it unchanged on the corresponding new task. None of the 200 graphs satisfied the new task requirements. For each new task, we also verified an optimal route and at least one valid alternative with strictly worse QoS.

We evaluated all three models on both sets using the original prompt from the main experiment and high reasoning effort. The suboptimality rate is the fraction of functionally valid plans for which a better valid route exists under the user’s QoS priorities.

ModelSuboptimality rate (600 original tasks)Suboptimality rate (200 new tasks)Validity rate (new)Overall optimality rate (new)
DeepSeek-V4-Pro37.2%48.9%93.0%47.5%
GLM-5.256.9%69.3%89.5%27.5%
GPT-5.6 Terra57.1%67.5%84.5%27.5%

We also paired each new task with its original. For each model, we considered only pairs where both plans were valid. All three models had suboptimality rates above 40% on the original tasks and on their adaptations. In every application, each model produced plans that met the task requirements but missed a better route. These results suggest that AgentQoSBench can generalize to unseen tool mechanisms.

2. Tool order in the full catalog

We tested whether catalog order affected how often models found an optimal plan on the same tasks. The original catalog lists tools in lexicographic order by ID, so functionally related tools with a common prefix often appear together. We shuffled the tool order on 210 original tasks and evaluated all three models.

ModelOptimality rate (original order)Optimality rate (shuffled)Change (shuffled − original, percentage points)
DeepSeek-V4-Pro59.9%58.0%−1.9
GLM-5.234.8%32.9%−1.9
GPT-5.6 Terra35.7%27.1%−8.6

In this comparison, all three models had more difficulty finding an optimal plan with the shuffled catalog. Terra’s optimality rate fell the most, by 8.6 percentage points.

3. Input length and truncation

The table gives the input token counts reported by each provider in the main experiment with high reasoning effort. Inputs under the original prompt ranged from 62,025 to 90,177 tokens, with about four English characters per token on average. Counts for the search prompt also include the system message. No provider reported a context-limit error, and we observed no input truncation for any model.

ModelOriginal prompt (median / max)Search prompt (median / max)
DeepSeek-V4-Pro79,862 / 89,27580,348 / 89,761
Gemini-3.1-Pro80,769 / 90,17781,271 / 90,677
GLM-5.272,947 / 81,63273,420 / 82,122
Qwen3.5-Flash75,235 / 84,22075,766 / 84,723
GPT-5.6 Terra74,631 / 85,68677,703 / 192,152
AuthorsOpenReview ↗

Response to W2 and Q2 — Comparing CATP-LLM and general-purpose models

“I suggest evaluating representative planning methods on compatible tasks, particularly single-objective cost optimization, or clarifying why such comparisons are infeasible.”

“Is it feasible to compare CATP-LLM [1] or other cost-aware planning methods on compatible benchmark subsets? If not, what prevents a meaningful comparison?”

Thank you for suggesting CATP-LLM. It is a cost-aware planner for image and text tasks that can combine tools such as classification, detection, and translation in a branching plan. AgentQoSBench covers consumer and workplace tasks. Even the 67 original tasks with cost as their sole objective have catalogs of 454–527 business tools each. These tools fall outside the released CATP model’s action vocabulary, which prevents a direct evaluation on those tasks.

We used QoSGen to build a cost-only extension with 10 native CATP tools for all four models. We set two different user requirements for each of 50 COCO images, giving 100 task conditions. For example, one request asks for the subject’s class, while another also asks for visual evidence supporting that label. All models received the same tasks, tools, and OpenCATP fee schedule. We summed the estimated fees for every tool call in each submitted graph. Planner inference charges are separate from this total. For each task, we verified at least two valid plans with different tool fees and established the minimum attainable fee. We also tested both Qwen models with a format example that used placeholders to illustrate how to write a tool-call graph.

ModelInterface or promptFormat-compliant graphTask completedCompleted at minimum tool cost
CATP-LLM (Qwen2.5-3B backbone)Native planning interface100%50%0%
GPT-5.6 Terra HighOriginal prompt99%98%88%
Qwen2.5-3B-InstructOriginal prompt0%0%0%
Qwen2.5-3B-InstructWith format example49%40%11%
Qwen3-4B-Instruct-2507Original prompt0%0%0%
Qwen3-4B-Instruct-2507With format example100%75%25%

GPT incurred a lower tool fee on each of the 49 tasks that it and CATP both completed. Across those tasks, estimated tool fees totaled USD 1.99 for GPT and USD 5.33 for CATP under the OpenCATP fee schedule.

CATP completed 50 tasks, compared with 40 for the similarly sized Qwen2.5-3B with a format example. Of the 36 tasks both completed, 25 required only the subject’s class. CATP denoised the image and then classified it. Qwen2.5 also generated a caption the user had not requested. CATP’s plans cost less on each of the 25 tasks, and its total tool fees were 37.8% lower. The other 11 tasks required both the class and an English caption. Qwen2.5 reached the minimum cost on all 11.

With the format example, all 100 of Qwen3-4B’s graphs met the output protocol. Of these, 25 failed to complete the task, 50 completed it at more than the minimum cost, and 25 reached the minimum.

A specialized planner can keep tool costs down by reusing familiar plans when the tools and tasks are stable. CATP was less expensive than the similarly sized Qwen2.5 on all 25 classification-only tasks. When users also asked for visual evidence on those same images, CATP kept its original plan. In 15 cases, GPT switched to a single detection call that returned both the class label and a bounding box at minimum cost. When user requirements change or new tools become available, planners need to choose a route based on the current goal and tool descriptions. This is where a general-purpose model’s ability to generalize becomes more valuable.

AuthorsOpenReview ↗

Response to W3 and Q3 — Why optimality fell with graph-search assistance

“It remains unclear whether this degradation results from poor search candidates or errors in their integration. I suggest reporting candidate-level functional validity, QoS optimality, and cases where better candidates are generated but incorrectly integrated into final plans.”

Thank you for suggesting that we compare the search candidates with the final plans. The net loss of optimal answers when candidates were shown came mainly from cases where the final plan no longer met the task requirements. We found errors at both stages of tool use. In one case the model omitted a requirement from the search goal. In another, it dropped a useful step that the search tool had already supplied.

How good were the candidates? The search tool works from the goals and dependencies specified by the model. Of the 5,183 candidates returned, we could directly map the tools, ports, dependencies, and final outputs of 817 (15.8%, across three models) to the original tasks. These candidates came from 391 model–task pairs. We retained the calls, edges, and final outputs as returned, applied the published default service settings, and scored each graph against the original task requirements and global QoS optimum. The table measures how these candidates fared as complete plans. A partial candidate may still supply a useful step.

Candidate outcome on the original taskCountRate
Completed the task76/8179.30%
Completed the task at the global QoS optimum12/8171.47%

The 76 valid candidates came from 38 model–task pairs. We compared each candidate with the final plan submitted after the search result was shown. Under the user’s priorities, the final plan ranked higher in 62 comparisons and tied in 14. We found no complete, valid candidate in this replayable subset that ranked above the corresponding final plan.

Where did the drop occur? Mean optimality in Table 5 fell from 30.82% to 29.65% when the search result was shown. Among the 2,337 complete pairs with candidates, there were 904 optimal answers with the result withheld and 868 with it shown, a net loss of 36. Each pair compares independent final answers from the same model and task, with the same search specification. In 1,474 pairs both final plans met the requirements. In 570 pairs only one did. Neither plan was valid in the other 293 pairs.

From result withheld to result shownOptimality gainsOptimality lossesNet change
Both final plans met the task requirements (1,474 pairs)179176+3
Only one final plan met the task requirements (570 pairs)84123−39

Before search. On task 041, an internal export had to contain exactly three specified records. DeepSeek left the exact-set requirement out of its search goal, so a candidate with one extra record satisfied that goal. After seeing the candidate, the model also omitted the filter in its final plan. With the result withheld, it applied the filter and reached the optimum.

After search. Task 057 required a complete enrollment roster. The candidate explicitly listed the result of coverage:complete_roster as an output. Under the original tool contract, that call returns exactly the seven required records. Terra omitted the call from its final plan after seeing the candidate and failed the roster check. With the result withheld, it used that same call and reached the optimum. Here we can identify a correct step in the candidate that was lost in the final plan.

The search tool met the goal DeepSeek specified on task 041 and supplied the roster call Terra needed on task 057. In light of these cases and the paired results, we think the most likely explanation for the drop is that models lost task requirements when specifying the search goal or using its results.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal Summary

We formalize quality of service (QoS) for the entire tool-call graph under complex dependencies and define optimality according to the user’s priorities. We introduce QoSGen, a pipeline that builds AgentQoSBench by generating tasks with multiple valid plans and verifying their reference optima. Our analysis of planning failures and suboptimal plans led us to develop QoS-aware search prompting and a graph-search tool to help LLMs find better plans.

All three reviewers valued AgentQoSBench’s distinction between task completion and optimality under the user’s QoS priorities. As sk4o noted, the benchmark accepts multiple valid plans. For every valid but suboptimal plan in our evaluation, we verified a tool-call graph that meets the same task requirements with strictly better QoS. HMpx found that separating planning failures from optimization failures gives a clearer picture of model performance than a single task success rate. wuvQ highlighted the benchmark’s systematic construction and validation, noting that QoSGen generates multiple valid plans and verifies the reference optimum for each task.

sk4o suggested controls such as supplying relevant tools to distinguish the difficulty of finding alternatives from that of optimizing over them. HMpx asked whether optimization failures persist with a smaller tool catalog. We added a controlled comparison on the same tasks, varying only the tools shown to the models. We verified that the reduced catalog retained each task’s original optimal plan. Among model–task pairs with valid plans under both catalogs, the share of suboptimal plans fell from 48.5% to 40.4%. Many valid plans could still be improved even with fewer tools to search. To address wuvQ’s question about unseen tool mechanisms, we adapted 200 tasks to reflect the documented API rules of four applications and evaluated three models on them. As in the main evaluation, many valid plans on these new tasks had alternatives with strictly better QoS. We paired the adapted tasks with their originals, keeping only pairs for which the same model produced valid plans on both versions. All three models had suboptimality rates above 40% on the original tasks and on their adaptations.

We are grateful for the reviewers’ suggestions, which helped us improve the paper. We have uploaded the revised PDF to OpenReview with the changes we committed to in response to their suggestions. Section 4.2 clarifies the scope of the optimality guarantee and uses the migration example in Figure 3 to illustrate how we verify a reference optimum. Table 6 in Appendix A now reports model versions, evaluation dates, reasoning settings, and observed input token counts. Appendix F addresses sk4o’s question about deployment by examining how latency variation and queuing can change the ranking of fixed plans in simulation.

During the rebuttal period, both HMpx and sk4o said the additional experiments and clarifications addressed their main concerns. HMpx retained their original overall rating, and sk4o raised theirs.

We thank all the reviewers again for their careful reading and thoughtful suggestions!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.