Budgeted Act-or-Defer Multi-Agent LLM Deliberation with Local Reliability Bounds
Mengdie Flora Wang, Haochen Xie, Guanghui Wang, Devin Zhang, Jae Oh Woo · 2026
Read Budgeted Act-or-Defer Multi-Agent LLM Deliberation with Local Reliability Bounds by Mengdie Flora Wang, Haochen Xie, Guanghui Wang, Devin Zhang, Jae Oh Woo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29654.txt.
Introduction
Wang and four colleagues address a deployment question for multi-agent language model deliberation: when is the current answer reliable enough to act on, and when should a human review it? Deliberation among models can improve reasoning, but acting on every answer is risky. They formulate budgeted act-or-defer decision making, with a user-declared wrong-action budget.
Each round, the system maps the debate so far to a low-dimensional state. A k-nearest-neighbor lower confidence bound on correctness, computed from calibration data, gates the decision: the system acts only once the bound exceeds a user-set reliability threshold. The guarantee is conditional, relying on stated assumptions with diagnostics. On six benchmarks, the method uses only a small share of its declared budget, reaching high automation and acted-on accuracy. On stress tests it defers instead.
Catalog record
| CREATOR | Mengdie Flora Wang, Haochen Xie, Guanghui Wang, Devin Zhang, Jae Oh Woo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 114 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29654
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Budgeted Act-or-Defer Multi-Agent LLM Deliberation with Local Reliability Bounds Mengdie Flora Wang, Haochen Xie, Guanghui Wang, Devin Zhang, Jae Oh Woo Abstract Multi-agent deliberation among LLMs can improve reasoning, but deployment requires deciding when the current answer is reliable enough to act on and when it should be escalated to human review. We formulate this as budgeted act-or-defer decision making. At each round, the system maps the debate prefix to a low-dimensional state, computes a k k -nearest-neighbor lower confidence bound on state-conditional correctness using calibration data, and acts only when the bound exceeds a user-specified reliability threshold. The certificate controls wrong actions through the decomposition β = δ + α + ε act \beta=\delta+\alpha+\varepsilon_{\mathrm{act}} , separating calibration failure, residual action risk, and representation gap. The guarantee is conditional, not distribution-free: it relies on a valid local bias envelope and an action-region representation-gap bound, and each assumption is paired with falsification-style diagnostics. Because the same absolute wrong-action budget has different meanings across tasks of different difficulty, we set budgets relative to each task’s final-round error using training data only, and evaluate safety by normalized budget usage WA / β \mathrm{WA}/\beta . On six benchmarks against nine baselines, the method uses 9–12% of the pre-declared budget on activated datasets, reaching up to 84% automation and 96% acted-on accuracy; on stress-test datasets, it defers rather than forcing unreliable automation. Rather than relying on per-task post-hoc threshold search, the method prospectively converts a user-declared wrong-action budget into an auditable act-or-defer operating point before deployment, under explicitly stated assumptions. 1 Introduction Multi-agent debate, where multiple LLM instances exchange responses over several rounds, has been shown to improve reasoning ( 21 ; 51 ) . To deploy such systems in practice, one needs a stopping criterion with principled control over the probability of acting on a wrong answer. In human-in-the-loop deployments this stopping decision is also an escalation decision: the system should act autonomously only when the local reliability bound supports action, and otherwise defer the instance to human review. Existing approaches either operate at a fixed final round with only marginal coverage (e.g., split conformal prediction ( 78 ; 4 ) ) or rely on heuristic consensus thresholds without explicit wrong-action budgets. Neither provides per-instance, per-round reliability bounds that enable adaptive stopping. We address this gap by constructing local lower confidence bounds on the correctness probability using k -nearest-neighbor ( k -NN) neighborhoods in a debate-state metric space. The debate prefix at round t is mapped to a state U_{t} in a metric space (\mathcal{U},d) . The local correctness function q_{t}(u)=\Pr(Y=\hat{Y}_{t}\mid U_{t}=u) is bounded from below via a local bias envelope b_{t,k}(u) that controls the k -NN approximation error. For each candidate neighborhood size k in a pre-specified family \mathcal{K} , we subtract the bias envelope and a Hoeffding concentration term from the k -NN empirical mean, then take the maximum over \mathcal{K} : L_{t}=\max_{k\in\mathcal{K}}\left[\widehat{q}_{t,k}(U_{t})-b_{t,k}(U_{t})-\sqrt{\frac{\log(T|\mathcal{K}|/\delta)}{2k}}\right], (1) where the \log|\mathcal{K}| penalty absorbs the adaptivity in k . The bias envelope b_{t,k}(u) is a generic primitive (Lipschitz, Hölder, bounded-oscillation models are special cases). The first correction controls approximation bias, the second controls sampling variance, and the maximization over \mathcal{K} selects the tightest local scale per instance. A central design choice is budget alignment . The user specifies a risk budget \beta and the method decomposes it as \beta\;=\;\underbrace{\delta}_{\begin{subarray}{c}\text{statistical}\\ \text{failure}\end{subarray}}\;+\;\underbrace{\alpha}_{\begin{subarray}{c}\text{residual}\\ \text{action risk}\end{subarray}}\;+\;\underbrace{\varepsilon_{\mathrm{act}}}_{\begin{subarray}{c}\text{representation}\\ \text{gap}\end{subarray}}. (2) The residual \alpha=\beta-\delta-\varepsilon_{\mathrm{act}} directly sets the stopping threshold 1-\alpha . The stopping rule \tau=\inf\{t:L_{t}\geq 1-\alpha\} then satisfies \Pr(\text{act and wrong})\leq\beta conditional on local assumptions (Theorem 3 ). The contribution is not the mathematical tools (Hoeffding + union bound, which are classical) but a risk-decomposition framework for adaptive deliberation stopping under auditable local assumptions. Figure 1: Overview. Top : (1) Agents debate over T rounds; (2) each transcript is compressed to state U_{t}=\phi(\mathcal{F}_{t}) ; (3) k -NN lookup yields lower bound L_{t} ; (4) act if L_{t}\geq 1-\alpha , continue if t<T , else defer to human review. Bottom left : calibration states colored by correctness; the test state drifts from low- to high-confidence as debate progresses. Bottom right : L_{t} grows from 0.72 to 0.96, crossing 1-\alpha=0.90 at \tau=3 . The guarantee is conditional on auditable local assumptions, not distribution-free. Our contributions: (i) We formalize adaptive stopping for multi-agent deliberation as a local state-conditional risk-control problem with budget decomposition \beta=\delta+\alpha+\varepsilon_{\mathrm{act}} . (ii) We introduce a local bias envelope b_{t,k}(u) as a plug-in interface and prove simultaneous validity L_{t}\leq q_{t}(U_{t}) for all (t,k) with probability \geq 1-\delta , plus a wrong-action guarantee (Theorems 1 – 3 ) and an oracle slack inequality (Theorem 6 , Appendix A ). Each assumption is paired with a diagnostic proxy. (iii) Lipschitz, Hölder, and bounded-oscillation envelopes are recovered as corollaries. Our default empirical modulus absorbs estimation failure into \delta (Corollary 8 ) and converges at O(n^{-1/(2+D)}) . (iv) We introduce a relative-risk deployment policy: \beta_{d}=\lambda^{\star}_{d}\widehat{e}_{T,d}^{\,\mathrm{train}} is induced from training data alone, making budgets comparable across tasks and turning normalized budget usage \mathrm{WA}/\beta into the primary safety metric. (v) Experiments on six benchmarks ( n=546 – 8{,}678 ) against nine baselines show that, on activated datasets, the method uses \leq 12% of the pre-declared budget at up to 97% acted-on accuracy. Matched-automation diagnostics show that tuned scalar thresholds can achieve similar subset quality after per-task search, but the proposed certificate constructs the operating point prospectively from a declared wrong-action budget and makes the required assumptions explicit. 2 Problem Setup Consider a multiple-choice task with input space \mathcal{X} and label space \mathcal{Y}=\{1,\ldots,C\} . An ensemble of N LLM agents debates for at most T rounds. At round t , the debate has produced a filtration \mathcal{F}_{t} containing all agent responses and per-agent belief distributions \{P^{(t)}_{j}(y\mid x)\}_{j=1}^{N} up to round t . We aggregate these into a social belief P_{\mathrm{social}}^{(t)}(y\mid x)\;=\;\frac{1}{N}\sum_{j=1}^{N}P^{(t)}_{j}(y\mid x), (3) and take \hat{Y}_{t}=\arg\max_{y}P_{\mathrm{social}}^{(t)}(y\mid x) as the round- t prediction (Appendix B specifies how each P^{(t)}_{j} is elicited). State embedding. Each debate prefix is mapped to a state U_{t}=\phi_{t}(\mathcal{F}_{t}) in a metric space (\mathcal{U},d) via a deterministic, \mathcal{F}_{t} -measurable \phi_{t} . Typical components include the top social probability p_{t}^{(1)}=\max_{y}P_{\mathrm{social}}^{(t)}(y\mid x) , the margin \Delta_{t}=p_{t}^{(1)}-p_{t}^{(2)} , inter-agent disagreement, and top-answer stability; the metric d reflects correctness relevance (e.g., Euclidean on a normalized feature vector). Geometry–sufficiency trade-off. The choice of \phi_{t} jointly controls three quantities central to the framework: (a) smoothness of q_{t} , which governs the bias envelope b_{t,k} ; (b) representation gap \varepsilon_{\mathrm{act}} , the information lost in compressing \mathcal{F}_{t} to U_{t} ; (c) intrinsic dimension D , which enters the certification rate O(n^{-1/(2+D)}) . Richer states reduce \varepsilon_{\mathrm{act}} but raise D and may roughen q_{t} ; minimal states keep D small and q_{t} smooth but risk larger \varepsilon_{\mathrm{act}} . We investigate this trade-off empirically in Section H.5 . Local correctness and goal. The target is the local correctness function q_{t}(u):=\Pr(Y=\hat{Y}_{t}\mid U_{t}=u), (4) a pointwise quantity conditioning on the exact state rather than averaging over a region. We seek a stopping rule \tau=\inf\{t\leq T:L_{t}\geq 1-\alpha\} with a data-driven lower bound L_{t} for q_{t}(U_{t}) , so that \Pr(\tau\leq T,\;\hat{Y}_{\tau}\neq Y)\leq\beta . The budget decomposition ( 2 ) controls each term separately: \delta by Hoeffding with a (t,k) union bound, \alpha by the stopping threshold, and \varepsilon_{\mathrm{act}} by the action-region representation