- 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
-
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?
-
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
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.
| Model | Original run | First rerun | Second 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.58 | 0.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.
| Model | Optimality with original prompt | Optimality with search prompt | Change in pp [95% CI] |
|---|---|---|---|
| GLM-5.2 | 27.5% | 37.0% | +9.5 [+2.4, +16.4] |
| DeepSeek-V4-Pro | 47.5% | 56.5% | +9.0 [+1.4, +16.6] |
| GPT-5.6 Terra | 27.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.
Response to W1 and Q1
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.
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.
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.