acceptodds
Under review as a conference paper at ICLR 2027

BRIGADE: Bayesian Runtime Inference Guiding Agentic DAG Execution under Budget Constraints

Abstract

Decomposing a complex task into a workflow of subtasks lets large language model (LLM) agents work on focused contexts instead of one long context that hurts understanding or exceeds the context window. However, multi-agent workflows are rarely cost-effective: they consume much more budget without a matching gain in performance, because the execution path is unclear, outputs are verified repeatedly, and no principled rule says when to stop. Effective orchestration therefore requires deciding not only which subtask to execute, but also when to acquire verification evidence or stop. To this end, we introduce BRIGADE, a Bayesian decision-theoretic framework for budget-constrained orchestration over a fixed task directed acyclic graph. BRIGADE combines prior knowledge of the model's ability with posterior beliefs over artifact correctness updated by evidence obtained at runtime, and controls the workflow by solving the constrained optimization problem. To make this problem tractable, we derive a lightweight two-step lookahead controller that selects execution, verification, and submission actions online under the budget, without calling an LLM planner at each round. By conditioning the second decision on possible observations, the controller values verification for guiding later actions, even when verification does not directly improve an artifact. Controlled simulations show gains from two-step lookahead when budgets permit additional decisions beyond the cheapest completion. On AppWorld with Doubao executors, BRIGADE shows favorable task-success-cost trade-offs at low and intermediate operating points.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Multi-agent orchestration, Bayesian decision theory, Large language model agents.

Reviews

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

BRIGADE maintains beliefs about intermediate output correctness and uses two-step lookahead to select execution, verification, or submission actions within a task DAG. Calibration data support action and observation models. Simulations examine the benefit of feedback and lookahead, while AppWorld experiments report favorable completion/cost trade-offs at lower budgets.

Critical strengths
  1. Extending Bayesian agent control to dependent subtasks is useful. Tracking output versions and assessing dependent work addresses a practical difficulty that a controller over a single candidate does not encounter.
  2. The simulations separate feedback-based updating from lookahead and include an informative failure case, where adaptive controllers fail at the smallest budget. This helps find out when additional planning is useful.
Critical weaknesses
  1. The AppWorld evidence does not isolate the controller's contribution. Appendix E reports one run on 57 development tasks, uncontrolled code revisions across batches, and costs excluding planning, calibration, and attempts outside terminal records. These limitations affect the completion/cost comparison.
  2. The benefit of two-step lookahead is demonstrated primarily in simulation. AppWorld lacks a corresponding one-step controller and an ablation of the additional repetition penalty. The initial correctness priors use only 29 labelled outputs, without held-out validation or sensitivity evidence. Consequently, the respective contributions of Bayesian updating, lookahead, and implementation heuristics remain uncertain.
Questions for authors
  1. Can you provide comparisons with more detailed cost accounting, separating reusable calibration costs from per-task costs?
  2. Under the same AppWorld implementation and repetition penalty, how does one-step planning compare with two-step planning? How sensitive are the results to the estimated calibration tables?
8 comments

We thank the reviewer for the constructive review and for the two concrete requests. We ran both and answer them in two comments.

Q1: cost accounting that separates the reusable calibration cost from the per-task cost

Answer. We now report the per-task cost with every component, and the one-time calibration cost separately. Per task, BRIGADE completes more tasks than ReAct at a lower cost when the budget is restricted. The calibration is recovered after roughly one to two thousand tasks. Above about ¥0.9 per task ReAct is the better choice.

Setup. 50 held-out test tasks, with the configuration frozen on the development set; K=16 is the mean of three runs, K=8 and K=32 are single runs; realized spending in CNY. The per-task cost is execution + retried attempts + planning (the one-off generation of the task DAG). Calibration is paid once per model pair and reused across tasks and splits. ReAct is one saved run, scored at its first K steps (K = 8, 16, 24, 32); its cost is its realized spending.

KBRIGADE cost per task (¥): execution + retried + planning = totalBRIGADE TGC (%)ReAct cost per task (¥)ReAct TGC (%)
80.244 + 0.000 + 0.033 = 0.277380.2950
160.557 + 0.007 + 0.033 = 0.59751.30.74536
320.745 + 0.000 + 0.033 = 0.778481.33380

BRIGADE's TGC at K=16 and K=32 (51.3% against 48%) differs by one to two tasks out of 50, which is within run-to-run variation.

What is countedOne-time cost (¥)Tasks needed to pay it back
Calibration on training tasks337about 1,050
The same, plus extra data collected for the final table689about 2,150

How to read this, at K=16: BRIGADE costs ¥0.60 per task and completes 51% of the tasks. To complete the same share, ReAct needs about ¥0.92 per task (it completes 36% at ¥0.75 and 70% at ¥1.13). So BRIGADE saves about ¥0.32 per task, and the ¥337 is paid back after 337 / 0.32 ≈ 1,050 tasks.

Analysis.

  • Per task. Execution dominates; planning and retried attempts add less than ¥0.05. At K=8 and K=16 BRIGADE completes more tasks than ReAct at a lower cost, and at K=8 it already completes more than ReAct at K=16.
  • Reusable cost. The method pays off when one calibrated model pair is used for many tasks. For a one-off evaluation of a few hundred tasks ReAct is cheaper in total.
  • Large budget. From K=16 to K=32 BRIGADE's completion rate stays at about 50% while its cost rises; ReAct completes far more tasks there, at a higher cost.

Conclusion. The efficiency gain holds per task under a restricted budget, and in total only after the calibration is amortized over on the order of a thousand tasks. We will report this accounting in the paper and replace the "same K" comparison with the cost–completion comparison above.

Q2: one-step against two-step planning under the same implementation, and sensitivity to the calibration tables

Answer. (a) On AppWorld, two-step lookahead gives no measurable gain over the identical one-step controller; we will limit that claim to the simulation. (b) The results are insensitive to errors in verifier reliability and repair success and to over-estimated correctness priors, and sensitive to under-estimated priors when the budget is close to the minimum cost of the task.

Setup (a). BRIGADE-Q1 is BRIGADE with the lookahead depth set to one; everything else is identical. 50 held-out test tasks; three runs at K=16, one at K=8 and K=32. Differences are paired, with 95% bootstrap intervals over task families. The table gives TGC on AppWorld and the success rate in the simulation.

SettingTwo-step (%)One-step (%)Two-step − one-step, points [95%]
AppWorld, K=83844−6 [−20, +8]
AppWorld, K=1651.352.0−0.7 [−8.7, +7.3]
AppWorld, K=324850−2 [−16, +10]
AppWorld, averaged over budgets−2.9 [−9.8, +3.8]
Simulation, pooled over budgets25.420.0+5.4 [+3.9, +6.9]

Setup (b). We replay the 2,400 episodes of the paper's simulation. The environment keeps the true parameters, and the controller plans with one family of its estimates shifted by a constant bias δ. The table gives the change in the success rate of BRIGADE in points (unbiased: BRIGADE 25.4%, Fixed 16.9%).

Biased estimateδ = −0.15−0.05+0.05+0.15
Correctness prior−6.3−6.3+0.1−1.2
Verifier reliability−0.5−0.2+0.5+1.8
Repair success−2.6−0.8+0.2+0.5

Analysis.

  • Lookahead depth. No difference is significant on AppWorld at any budget, and the second step needs 6 to 12 times more controller computation. In the simulation the gain is significant. A likely reason is self-correction: on AppWorld a repair after a FAIL verdict fixes an incorrect output about half of the time and breaks a correct one about a quarter of the time, while in the simulation repairs are far more reliable (61–95% and 7–11%). This suggests that the second step becomes worthwhile as models get better at self-correction (details in our response to Reviewer 8jdC, Q1).
  • Robust to calibration error. Errors in verifier reliability and repair success, and optimistic priors, change the success rate by a few points at most.
  • One sensitive case. With pessimistic priors the whole loss comes from the budget just above the minimum cost of the task, where the controller keeps verifying and repairing the first nodes and exhausts the budget.

Conclusion. Under one implementation, lookahead depth does not explain the AppWorld gains; they come from adaptive allocation from calibrated estimates. The calibration does not need to be exact, with one stated failure mode. The revision will report BRIGADE-Q1 next to BRIGADE, limit the two-step claim to the simulation, add the sensitivity experiment to the appendix, and state the failure mode in the Limitations.

We thank the reviewer again. If the cost accounting, the one-step ablation and the sensitivity analysis address your concerns, we would be grateful if you would consider raising your score.

Thank you for the additional experiments and the appropriately adjusted statements. The revised cost accounting and one-step comparison address these parts of my review. My remaining concern is the explanation of the AppWorld improvements. The new results do not report the frozen posterior baseline or an ablation of the repetition penalty under the same held-out setup. Also, the calibration sensitivity analysis is confined to simulation, so robustness of the sparse AppWorld calibration estimates remains uncertain. Could you clarify what evidence supports explaining the held-out improvements as a result of Bayesian adaptive allocation?

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

The aper poses BRIGAGEm a bayesian decision theoretic framework for budget constrained orchestration of LLM agents over a fixed DAG of dependent subtasks. The framework combines offline-calibrated estimates of execution qulity, verfication reliability, repari outcomes, and action costs with runtime Bayesian belief updates. Its main contribution is a light weight two step lookahead controller that dynamically selects subtasks, executor models, and interventions without requiring an LLM planner at every decision.

The authors validate BRIGADE through controlled simulations and experiments on AppWorld. Simulations demonstrate improvements over fixed, frozen-prior, and one-step Bayesian policies at moderate and higher budgets. On a single AppWorld development-set evaluation, BRIGADE achieves 70.18% task completion at K=16, compared with 56.14% for the frozen-belief baseline and 47.37% for ReAct, while reporting lower mean execution costs than ReAct.

Critical strengths
  1. the paper have sound decision theoretical framing: it have formulates multi-agent workflow scheduling over a fixed DAG as a budget - constrained POMDP, using a 2 step lookahead belief space controller instead of expensive LLM orchestrators.
  2. Decision-aware verification: The two-step lookahead controller explicitly considers how verification outcomes influence subsequent actions. This is a meaningful distinction from approaches that treat verification as a fixed procedural step or optimize only immediate expected gains.
  3. Practical efficiency: The controller makes orchestration decisions without additional LLM planner calls at every step, offering a computationally lightweight approach to dynamically allocating execution and verification resources. Its handling of DAG dependencies and invalidation of downstream outputs also addresses practical workflow challenges.
Critical weaknesses
  1. Fragile Empirical Evaluation: The real LLM agent evaluation is conducted only on AppWorld dev split (57 tasks) using a single run with a single model pair (Doubao).
  2. Insufficient ablation of the central methodological contribution. The main novelty is the Bayesian two-step lookahead controller, particularly its ability to account for the value of verification. However, the AppWorld experiments do not directly compare two-step lookahead against an otherwise identical one-step Bayesian controller. While this comparison is included in synthetic simulations, it remains unclear how much of the improvement in real agent execution comes specifically from two-step lookahead.
Questions for authors
  1. Isolating two-step lookahead: Could the authors ablate the two-step controller against an identical one-step baseline on AppWorld to quantify the exact performance gain of two-step lookahead?
  2. Experimental reproducibility and statistical reliability: Appendix E indicates that the AppWorld results come from a single development-set run and that code revisions were not fully controlled across experimental batches. Could the authors clarify which implementation differences existed between experiments and provide repeated evaluations with consistent implementations?
  3. The compared methods differ in their execution architectures, and the same budget parameter K does not necessarily correspond to equal realized costs. Furthermore, some planning and calibration expenses are excluded from the reported cost accounting. Could the authors clarify whether the reported efficiency gains remain when all computational costs are included and methods are compared under equivalent total budgets?
5 comments

We thank the reviewer for the careful and constructive review. The three requests were the right tests of our claims. We ran all three and report the results in three comments, including where they narrow the claims of the submission.

Q1: two-step lookahead against an identical one-step controller on AppWorld

Answer. We ran the requested ablation on held-out test tasks. On AppWorld, two-step lookahead gives no measurable gain over the identical one-step controller. We will limit the claim about two-step lookahead to the simulation.

Setup. BRIGADE-Q1 is BRIGADE with the lookahead depth set to one; the action set, beliefs and belief updates, calibration table, executors, task DAGs and budgets are identical. 50 held-out test tasks, with the configuration frozen on the development set; three runs at K=16, one at K=8 and K=32. Differences are paired, with 95% bootstrap intervals over task families. The table gives TGC on AppWorld and the success rate in the simulation.

SettingTwo-step (%)One-step (%)Two-step − one-step, points [95%]
AppWorld, K=83844−6 [−20, +8]
AppWorld, K=1651.352.0−0.7 [−8.7, +7.3]
AppWorld, K=324850−2 [−16, +10]
AppWorld, averaged over budgets−2.9 [−9.8, +3.8]
Simulation, pooled over budgets25.420.0+5.4 [+3.9, +6.9]
Reliability of a repairAppWorld (measured on training tasks, after a FAIL verdict)Simulation (model parameters)
Fixes an incorrect output48% (26 of 54)61–95%
Breaks a correct output26% (20 of 77)7–11%

Analysis.

  • No gain on AppWorld. No difference is significant at any budget, and the pooled interval excludes a two-step advantage larger than about 4 points.
  • Higher cost. The two controllers spend the same per task on model calls, but the second step needs 6 to 12 times more controller computation.
  • A likely reason: self-correction. The second step plans what to do after a verification, so it is only as valuable as what the executor can do with the verdict. On AppWorld, current models are unreliable at correcting themselves from verifier feedback (second table), so planning the verify-then-repair step ahead changes few outcomes.
  • What the simulation shows. Where repairs are far more reliable, the same two-step lookahead gives a significant gain. This suggests that two-step lookahead becomes the better choice as models get better at self-correction. We have not tested this on AppWorld.

Conclusion. On AppWorld the benefit of BRIGADE does not come from the depth of the lookahead. In the revision, (i) BRIGADE-Q1 will be reported next to BRIGADE in the AppWorld results; (ii) the claim that two-step lookahead improves over one-step control will be limited to the simulation; (iii) the AppWorld gains will be attributed to adaptive allocation from calibrated estimates (BRIGADE against Fix, Q2); (iv) the dependence of the second step on the executor's ability to self-correct will be discussed as above.

Q2: implementation differences, and repeated evaluation with a consistent implementation

Answer. We now report every AppWorld number under one frozen configuration, with three runs per method, on the development set and on held-out test tasks. The comparisons are stable across runs and agree between the two sets.

TGC (%),Dev setHeld-out test set
BRIGADE67.8 ± 7.951.3 ± 1.2
BRIGADE-Q1 (one-step)not run52.0 ± 5.3
BFW65.5 ± 5.450.0 ± 2.0
Fix42.7 ± 1.025.3 ± 5.8
BRIGADE − Fix+25.1 [+10.5, +40.4]+26.0 [+14.0, +38.0]
BRIGADE − BFW+2.3 [−4.7, +9.4]+1.3 [−4.0, +6.7]
BRIGADE − BRIGADE-Q1not run−0.7 [−8.7, +7.3]

Differences are paired, in points, with 95% bootstrap intervals over task families.

Conclusion. With a consistent implementation and repeated runs, the gain of adaptive control over the fixed pipeline is reproducible, and the other differences are within noise. The revision will report these runs, the number of configurations tried, and the limitations above.

Q3: efficiency with all costs included, and comparison at equal total budget

Answer. We agree that the same K is not the same cost and that planning and calibration must be counted. With planning and retried attempts included, BRIGADE is more efficient than ReAct per task when the budget is restricted (below about ¥0.9 per task) and less efficient above. With the one-time calibration included, the advantage holds in total only after roughly one to two thousand tasks.

Setup. 50 held-out test tasks; K=16 is the mean of three runs, K=8 and K=32 are single runs; realized spending in CNY. The per-task cost is execution + retried attempts + planning (the one-off generation of the task DAG). ReAct is one saved run, scored at its first K steps (K = 8, 16, 24, 32); its cost is its realized spending.

KBRIGADE cost per task (¥): execution + retried + planning = totalBRIGADE TGC (%)ReAct cost per task (¥)ReAct TGC (%)
80.244 + 0.000 + 0.033 = 0.277380.2950
160.557 + 0.007 + 0.033 = 0.59751.30.74536
320.745 + 0.000 + 0.033 = 0.778481.33380

BRIGADE's TGC at K=16 and K=32 (51.3% against 48%) differs by one to two tasks out of 50, which is within run-to-run variation.

What is countedOne-time cost (¥)Tasks needed to pay it back
Calibration on training tasks337about 1,050

How to read this, at K=16: BRIGADE costs ¥0.60 per task and completes 51% of the tasks. To complete the same share, ReAct needs about ¥0.92 per task (it completes 36% at ¥0.75 and 70% at ¥1.13). So BRIGADE saves about ¥0.32 per task, and the ¥337 is paid back after 337 / 0.32 ≈ 1,050 tasks.

Analysis.

  • Restricted budget. At K=8 and K=16 BRIGADE completes more tasks than ReAct at a lower cost. BRIGADE at K=8 already completes more than ReAct at K=16, at less than half the cost.
  • Similar cost. BRIGADE at K=32 costs about as much as ReAct at K=16 and completes more tasks.
  • Large budget. BRIGADE does not convert a larger budget into more completed tasks: from K=16 to K=32 it runs the same number of model rounds, uses the strong model and the verifier more often, and its completion rate stays at about 50%. Above about ¥0.9 per task ReAct is better.
  • Calibration. For a one-off evaluation of a few hundred tasks the calibration cost dominates, and ReAct is cheaper in total.

Conclusion. The efficiency gain is real per task under a restricted budget, is conditional on amortizing the calibration over on the order of a thousand tasks, and does not extend to large budgets. We will state all three points in the paper and replace the "same K" comparison with the cost–completion comparison above.

We thank the reviewer again. These requests made the paper more accurate about what it shows. If this addresses your concerns, we would be grateful if you would consider raising your score.

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

This paper presents BRIGADE, a Bayesian controller for managing multi-agent workflows under limited budgets. It uses feedback from intermediate execution and verification steps to decide whether a task should continue, be checked, or be repaired. The authors evaluate the method using simulated workflows and AppWorld. The results are promising in some settings, but I have some concerns about the experimental validation.

Critical strengths

1.The paper considers a practical problem: how to allocate a limited budget across execution, verification, and repair in agent workflows. The proposed controller provides a structured way to make these decisions based on intermediate feedback.

2.The experiments also offer some evidence that adapting decisions to the current workflow state can be useful, particularly when the available budget is limited.

Critical weaknesses

1.BRIGADE relies on estimates of execution correctness, verification reliability, repair success, and cost. I would like to better understand how these estimates are obtained and how sensitive the results are to their accuracy.

2.The AppWorld evaluation uses 57 development tasks and reports a single run with one model configuration. This makes it difficult to assess how stable the reported improvements are. Additional runs or evaluation on held-out tasks would strengthen the evidence.

3.The benefit of BRIGADE appears to depend on the budget setting. At higher budgets, ReAct achieves better task completion in the reported comparison. It would be helpful to clarify the situations in which BRIGADE is most useful and whether the additional controller complexity is justified by the gains.

Questions for authors

See Weakness

4 comments

We thank the reviewer for the careful and constructive review. Each of your three questions led to a new experiment; we answer them in three comments.

Q1: how the estimates are obtained, and how sensitive the results are to their accuracy

Answer. The estimates come from an offline, one-time calibration on training tasks only. The results are insensitive to errors in verifier reliability and repair success and to over-estimated correctness priors. They are sensitive to under-estimated priors when the budget is close to the minimum cost of the task.

Setup (calibration). We use 90 AppWorld training tasks from 30 task families, never development or test tasks. A fixed-seed sampling policy exercises both executor tiers, both verifier tiers and both repair modes (6,417 action records). Each node output is labelled against the AppWorld ground-truth state; outputs that cannot be checked this way are adjudicated offline by the strong model, and undecidable ones are excluded. Sparse cells are shrunk towards their parent cell (hierarchical partial pooling), and the tables are frozen and hashed before evaluation.

Estimated quantityConditioned onSamplesHeld-out log-loss
Correctness priornode type × executor tier3730.333
Verifier likelihoodnode type × verifier tier × truth5840.665
Repair transitionnode type × tier × verdict × repair mode × old truth5170.329

Setup (sensitivity). We replay the 2,400 episodes of the paper's simulation. The environment keeps the true parameters, and the controller plans with one family of its estimates shifted by a constant bias δ. The table gives the change in the success rate of BRIGADE in points (unbiased: BRIGADE 25.4%, Fixed 16.9%).

Biased estimateδ = −0.15−0.05+0.05+0.15
Correctness prior−6.3−6.3+0.1−1.2
Verifier reliability−0.5−0.2+0.5+1.8
Repair success−2.6−0.8+0.2+0.5

Analysis.

  • Robust cases. Errors in verifier reliability and repair success, and optimistic priors, change the success rate by a few points at most, and BRIGADE stays well above Fixed.
  • Sensitive case. With pessimistic priors the whole loss comes from the budget just above the minimum cost of the task: the controller keeps verifying and repairing the first nodes and exhausts the budget.
  • On AppWorld. Replacing the calibration estimator and the label definition, with everything else fixed, moved TGC on the development set only within run-to-run variation.

Conclusion. The controller does not need exact estimates, with one failure mode: a pessimistic prior at a near-minimal budget. We will add the experiment to the appendix, state the failure mode in the Limitations, and update the appendix on calibration to the procedure above.

Q2: stability across runs and on held-out tasks

Answer. With three runs per method and a held-out test set, the gain of BRIGADE over the fixed pipeline is stable across runs and has the same size on held-out tasks. The absolute level is lower on held-out tasks, and the margin over ReAct is smaller there.

Setup. One configuration, frozen on the development set (57 tasks) and then run unchanged on 50 held-out test tasks from 50 task families. K=16, three runs per method; ReAct is one saved run. Differences are paired on tasks, with 95% bootstrap intervals over task families.

TGC (%)Dev setHeld-out test set
BRIGADE67.8 ± 7.951.3 ± 1.2
BFW65.5 ± 5.450.0 ± 2.0
Fix42.7 ± 1.025.3 ± 5.8
ReAct (one run)40.436

Analysis.

  • What is stable. The gap to Fix has the same size on both sets and is well above the run-to-run SD. BRIGADE and BFW cannot be separated on either set, so we claim no ranking between them.
  • What does not fully carry over. On held-out tasks the level is lower, and the margin over ReAct at K=16 is roughly halved, with an interval that narrowly includes zero.
  • Limitations. ReAct was not repeated, and all results use one model pair.

Conclusion. The main comparison of the paper, adaptive control against the fixed pipeline, is stable across runs and holds on held-out tasks; the advantage over ReAct at K=16 is smaller than the development set suggested. The revision will report these runs and state the limitations above.

Q3: when BRIGADE is most useful, and whether the controller complexity is justified

Answer. BRIGADE is most useful under a restricted budget: on held-out tasks it is ahead of ReAct below about ¥0.9 per task and behind it above. The complexity that the AppWorld results justify is adaptive allocation from calibrated estimates. A one-step controller is sufficient for it; belief updating and the second lookahead step add no measurable gain there.

Setup. 50 held-out test tasks at K ∈ {8, 16, 32} (three runs at K=16, one otherwise). Cost per task includes execution, retried attempts and DAG planning. BRIGADE-Q1 is the identical controller with one-step lookahead; BFW freezes the beliefs; Fix always uses the strong model.

TGC (%) / cost per task (¥)K=8K=16K=32
BRIGADE38 / 0.27751.3 / 0.59748 / 0.778
BRIGADE-Q144 / 0.27152.0 / 0.60050 / 0.762
BFW40 / 0.26050.0 / 0.56852 / 0.673
Fix0 / 0.21025.3 / 0.58350 / 0.758
ReAct0 / 0.29536 / 0.74580 / 1.333
Paired difference, points [95% interval]K=8K=16K=32
BRIGADE − ReAct+38 [+24, +52]+15.3 [−0.7, +31.3]−32 [−48, −16]
Adaptive allocation: BRIGADE − Fix+38 [+24, +52]+26.0 [+14.0, +38.0]−2 [−18, +14]
Belief updating: BRIGADE − BFW−2 [−14, +10]+1.3 [−4.0, +6.7]−4 [−16, +6]
Second lookahead step: BRIGADE − BRIGADE-Q1−6 [−20, +8]−0.7 [−8.7, +7.3]−2 [−16, +10]

Analysis.

  • Restricted budgets. At K=8 and K=16 the adaptive controllers complete more tasks than ReAct at a lower cost, because they shift model rounds to the cheap model when the budget is tight. ReAct reaches their completion rate only at about ¥0.9 per task.
  • Large budget. At K=32 ReAct is better: BRIGADE stops when no remaining action has positive estimated value and leaves the rest of the budget unspent, while ReAct keeps observing and correcting.
  • Components. Only adaptive allocation has a clear effect, and only under a restricted budget. Belief updating and the second lookahead step make no measurable difference, and the second step needs 6 to 12 times more controller computation.
  • Why the second step does not pay off. A likely reason lies in the executor models rather than in the controller. A verification is only as valuable as what the executor can do with its verdict, and current models are unreliable at correcting themselves from verifier feedback: in our calibration data on training tasks, a repair after a FAIL verdict fixed an incorrect output in about half of the cases and broke a correct output in about a quarter. Planning the verify-then-repair step ahead therefore changes few outcomes. Consistently, BRIGADE verifies about three times as often as BFW without completing more tasks. In the simulation, where a repair succeeds far more often (61–95%) and rarely breaks a correct output (7–11%), the same second step adds 5.4 points. This suggests that two-step lookahead becomes the better choice as models get better at self-correction, which is where we see the limit of today's models.

Conclusion. The method is preferable to ReAct when the per-task budget is restricted, and what earns this advantage is mainly calibrated adaptive allocation. The revision will report BRIGADE-Q1 next to BRIGADE, limit the claims about belief updating and two-step lookahead to the simulation, and state the budget range in which the method is preferable.

We thank the reviewer again for these questions. If the new experiments and the planned revisions answer them, we would be grateful if you would consider raising your score.

Thank you for the detailed responses and additional experiments. The held-out evaluation and repeated runs alleviate my concerns about experimental stability, and I appreciate the clarified calibration procedure and more carefully scoped claims. However, the AppWorld ablations show no statistically detectable benefit from Bayesian updating or two-step lookahead, leaving the justification for the added controller complexity insufficient; robustness to calibration errors on AppWorld also remains uncertain. While the rebuttal strengthens the empirical evidence, these remaining concerns lead me to maintain my original score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: summary of the rebuttal

This comment summarizes our responses to the three reviewers in one place. The reviewers asked for (1) held-out, repeated evaluation with ablations, (2) complete cost accounting, and (3) the calibration procedure and its sensitivity. We ran all of them. The results confirm the low-budget gain of the framework and narrow two claims of the submission; the revised manuscript states both.

1. New experiments and ablations

One configuration was frozen on the development set and run unchanged on 50 held-out test tasks (50 task families) at K = 8, 16 and 32. K=16 has three runs per method; ReAct is one saved run. Entries are TGC (%) / cost per task (¥).

KBRIGADEBRIGADE-Q1 (one-step)BFW (frozen beliefs)BRIGADE-noRepeatFixReAct
838 / 0.27744 / 0.27140 / 0.26036 / 0.2720 / 0.2100 / 0.295
1651.3 / 0.59752.0 / 0.60050.0 / 0.56846 / 0.61825.3 / 0.58336 / 0.745
3248 / 0.77850 / 0.76252 / 0.67354 / 0.83650 / 0.75880 / 1.333
BRIGADE minus, points [95%]K=8K=16K=32
Fix+38 [+24, +52]+26.0 [+14.0, +38.0]−2 [−18, +14]
ReAct+38 [+24, +52]+15.3 [−0.7, +31.3]−32 [−48, −16]
BFW (belief updating)−2 [−14, +10]+1.3 [−4.0, +6.7]−4 [−16, +6]
BRIGADE-Q1 (second lookahead step)−6 [−20, +8]−0.7 [−8.7, +7.3]−2 [−16, +10]
BRIGADE-noRepeat (repetition penalty)+2 [−8, +12]+6 [−2, +14]−6 [−16, +4]
  • What holds. The overall allocation framework improves over the fixed pipeline at K=8 and K=16, and over ReAct at K=8. With three runs on the development set, the gain over Fix has the same size (+25.1 [+10.5, +40.4]).
  • What is narrowed. At K=16 the interval of the margin over ReAct narrowly includes zero, and at K=32 ReAct is better. The ablations show no statistically detectable benefit of each individual component on AppWorld. The benefits of belief updating (+2.3 [+0.9, +3.7]) and of two-step lookahead (+5.4 [+3.9, +6.9]) are supported only in the simulation.

2. Cost analysis

The cost per task is execution + retried attempts + DAG planning (¥0.033). The one-time calibration is reported separately.

  • Per task. At K=8 and K=16 BRIGADE completes more tasks than ReAct at a lower cost (first table). To match BRIGADE's completion at K=16, ReAct needs about ¥0.92 per task. BRIGADE is ahead below about ¥0.9 per task and behind above.
  • One-time cost. Calibration costs ¥337, or ¥689 with the extra data collected for the final table. At a saving of about ¥0.32 per task, it is paid back after about 1,050 or 2,150 tasks.

3. Calibration: procedure and sensitivity to estimation error

  • Procedure. Calibration is offline and one-time. It uses 90 training tasks from 30 task families, never development or test tasks. A fixed-seed sampling policy exercises both executor tiers, both verifier tiers and both repair modes (6,417 action records). Outputs are labelled against the AppWorld ground-truth state. Sparse cells are shrunk towards their parent cell (hierarchical partial pooling), and the tables are frozen before evaluation.
  • Sensitivity in the simulation. We bias one family of estimates by δ between −0.15 and +0.15. Errors in verifier reliability or repair success cost at most 2.6 points, and over-estimated priors have no detectable effect. Under-estimated priors cost about 6 points, all at the budget just above the minimum cost of the task.
  • Evidence on AppWorld. Over the 331 voluntary submissions on held-out tasks, the predicted success is 0.71 and the realized success 0.69, with an AUC of 0.67. The two agree within 5 points in four of six confidence groups and differ by 16 and 18 points in the other two. An alternative calibration table changed the development TGC within noise (BRIGADE −3.5 [−13.5, +5.3]).
  • Limits. The evidence does not show calibration at every confidence level, and robustness to estimation error is tested only in the simulation.

Revised manuscript. Section 4.2 (Figure 4, Tables 1 and 2) reports the held-out results and ablations. The introduction and conclusion state the narrowed claims. The new Appendix F reports the sensitivity analysis and the calibration evidence. The cost accounting and the calibration procedure above will be added to the final version.

We sincerely thank all reviewers, the ACs and the PCs for their time and constructive feedback, which made the paper more precise.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.