Technical Summary: Budgeted Act-or-Defer Multi-Agent LLM Deliberation with Local Reliability Bounds

1. Problem Statement

The paper addresses the deployment challenge of multi-agent Large Language Model (LLM) deliberation systems. While multi-agent debates improve reasoning capabilities, practical deployment requires a principled mechanism to decide when the system should act autonomously and when it should defer to human review. Existing approaches typically rely on fixed stopping rounds with marginal coverage guarantees (e.g., split conformal prediction) or heuristic consensus thresholds that lack explicit control over the probability of wrong actions.

The core problem is formulated as budgeted act-or-defer decision making: given a user-specified "wrong-action budget" ($\beta$), the system must determine a stopping rule $\tau$ such that the probability of acting on an incorrect answer is bounded by $\beta$, while maximizing the rate of autonomous action (automation). This requires per-instance, per-round reliability bounds that adapt to the local state of the debate.

2. Methodology

The proposed method constructs local lower confidence bounds on the correctness probability using a $k$-nearest-neighbor ($k$-NN) approach in a metric space of debate states.

2.1 State Representation and Calibration

• State Embedding: At each round $t$, the debate history (filtration $F_t$) is compressed into a low-dimensional state $U_t = \phi_t(F_t)$ in a metric space $(\mathcal{U}, d)$. The default state consists of the top social probability ($p^{(1)}_t$) and the margin ($\Delta_t$) between the top two options.
• Calibration: A calibration dataset $D_{cal}$ is used where full debates are run. For each instance and round, the state $U_{i,t}$ and correctness indicator $Z_{i,t}$ are recorded. The data is split into a modulus estimation set ($D_{mod}$) and a lookup set ($D_{loc}$).

2.2 The Lower Bound Construction

For a test instance at round $t$ with state $U_t$, the method computes a lower bound $L_t$ on the local correctness $q_t(U_t) = \Pr(Y = \hat{Y}_t | U_t = u)$.

1. $k$-NN Lookup: For a family of neighborhood sizes $K$, the method identifies the $k$ nearest neighbors in $D_{loc}$.
2. Bias-Variance Correction: The raw empirical mean of correctness in the neighborhood is penalized by two terms:
   • Local Bias Envelope ($b_{t,k}$): A plug-in interface controlling the approximation error within the neighborhood. The paper uses an empirical modulus (fitted via a logistic GAM on $D_{mod}$) as the default, which measures the maximum variation of a pilot smoother within a radius.
   • Sampling Variance: A Hoeffding concentration term $\sqrt{\frac{\log(T|K|/\delta)}{2k}}$.
3. Adaptive Selection: The final bound is the maximum over all $k \in K$:
   $$L_t = \max_{k \in K} \left[ \hat{q}_{t,k}(U_t) - b_{t,k}(U_t) - \sqrt{\frac{\log(T|K|/\delta)}{2k}} \right]$$
   This allows each instance to automatically select the $k$ that offers the tightest bias-variance trade-off.

2.3 Budget Decomposition and Stopping Rule

The user specifies a total wrong-action budget $\beta$. The method decomposes this budget into three components:
$$\beta = \underbrace{\delta}_{\text{Calibration Failure}} + \underbrace{\alpha}_{\text{Residual Action Risk}} + \underbrace{\epsilon_{act}}_{\text{Representation Gap}}$$

• $\delta$: Controls the probability that the lower bound $L_t$ exceeds the true correctness (calibration failure).
• $\alpha$: The residual risk when the system acts. The stopping threshold is set to $1 - \alpha$, where $\alpha = \beta - \delta - \epsilon_{act}$.
• $\epsilon_{act}$: A one-sided bound on the "representation gap," accounting for information lost when compressing the full debate history $F_t$ into the state $U_t$.

Stopping Rule: The system acts at round $\tau = \inf \{ t \le T : L_t \ge 1 - \alpha \}$. If the bound is never met by round $T$, the instance is deferred to human review.

2.4 Relative-Risk Deployment

To handle tasks of varying difficulty, the paper introduces a relative-risk deployment policy. Instead of fixing an absolute $\beta$ across all tasks, the budget is induced from the task's final-round error ($\hat{e}_T$) on the training data: $\beta_d = \lambda \cdot \hat{e}_T$. The multiplier $\lambda$ is selected on the training split to maximize automation while keeping the normalized budget usage ($WA/\beta$) below a target (e.g., 0.10).

3. Key Contributions

1. Formalization of Adaptive Stopping: The paper formalizes multi-agent deliberation stopping as a local state-conditional risk-control problem with a three-way budget decomposition ($\beta = \delta + \alpha + \epsilon_{act}$).
2. Local Bias Envelope Interface: It introduces a generic, plug-in bias envelope $b_{t,k}(u)$ (with Lipschitz, Hölder, and empirical modulus as special cases) to control local approximation error, proving simultaneous validity of the lower bounds.
3. Conditional Guarantees with Explicit Assumptions: Unlike distribution-free methods, the guarantee is conditional on auditable local assumptions (validity of the bias envelope and the action-region representation gap). The cost of assumption failure is explicitly added to the risk bound via Proposition 4.
4. Relative-Risk Deployment: The method converts a user-declared wrong-action budget into an auditable operating point prospectively, using training data to normalize budgets across tasks of different difficulties.
5. Empirical Validation: Experiments on six benchmarks (MMLU-Pro, LogiQA, ARC, BBH, MuSR, GPQA) against nine baselines demonstrate that the method uses only 9–12% of the pre-declared budget on activated datasets while achieving high automation (up to 84%) and acted-on accuracy (up to 96%). On stress-test datasets (GPQA, MuSR), the method correctly defers rather than forcing unreliable automation.

4. Results

• Activated Datasets: On MMLU-Pro, BBH, LogiQA, and ARC, the method achieves automation rates between 28% and 84% with acted-on accuracies of 89%–97%. Crucially, the wrong-action rate ($WA$) consumes only 9–12% of the pre-declared budget ($WA/\beta \in [0.09, 0.12]$).
• Stress-Test Datasets: On GPQA and MuSR (characterized by small sample sizes and high base error), the induced budgets are large, but the method defers on most instances (0%–53% automation) because the local lower bounds fail to cross the threshold. This is presented as intended behavior to avoid unreliable automation.
• Comparison to Baselines:
  • Risk-Control Baselines (CRC, Selective Prediction): These methods achieve near-100% automation but consume 18–82% of the same budget, indicating they cannot convert a declared budget into a specific automation level without per-task tuning.
  • Matched-Automation Comparison: When baselines are tuned post-hoc to match the automation rate of the proposed method, their acted-on accuracy and budget usage are statistically indistinguishable. The paper argues the value of the proposed method lies in prospective policy construction from a declared budget without per-task threshold search.
• Ablations: Removing the bias envelope ($b_{t,k}$) leads to a 2–3× increase in budget usage. Using only the final round (no adaptive stopping) eliminates early-stopping savings.

5. Significance and Claims

The paper claims its primary contribution is not achieving higher subset quality than tuned scalar thresholds (which it matches in matched-automation tests) but rather providing a prospective, auditable framework for converting a user-declared wrong-action budget into an act-or-defer policy.

• Explicit Assumptions: The method exposes the structural assumptions required for the guarantee (local smoothness via the bias envelope and the representation gap) and pairs them with diagnostic proxies (e.g., modulus inflation, predictor-gap checks) to falsify insufficient representations.
• Graceful Degradation: The guarantee degrades gracefully; if assumptions are violated, the failure probability is explicitly added to the risk bound rather than causing a catastrophic failure of the guarantee.
• Template for Inference-Time Compute: The authors view this as a template for other inference-time compute pipelines where repeated autonomous action is cheap, but occasional wrong actions are costly.

The paper explicitly states it does not provide distribution-free conditional correctness. Instead, it offers a risk-decomposition framework that makes the cost of local assumptions explicit, allowing for auditable deployment under stated conditions.