acceptodds
Under review as a conference paper at ICLR 2027

BRA-Audit: Budgeted Runtime Auditing for LLM Multi-Agent Systems via Cumulative-Exposure Audit-Point Placement

Abstract

LLM-based multi-agent systems (LLM-MAS) rely on inter-agent dependencies that can amplify local hallucinations or malicious outputs into system-level failures. Runtime auditors can contain these failures, but auditing effectiveness depends not only on how an auditor judges a trajectory, but also on where limited audit calls are placed. End-only auditing leaves long dependency chains unchecked and enlarges rollback scope, whereas exhaustive interaction-level auditing incurs substantial token cost. We propose BRA-Audit, a budgeted runtime auditing framework that treats auditing as audit-point placement over a dynamic execution graph. Its key principle is that an audit point has non-local value: once verified, it prevents accumulated unchecked exposure from being repeatedly inherited by downstream audit contexts. BRA-Audit weights exposure by verification staleness and downstream reachability, minimizes cumulative unchecked exposure under a fixed audit-call budget, and greedily selects points by marginal exposure reduction. Verified points become trusted boundaries for localized auditing and rollback. Across AgentsNet, BBH, and MultiAgentBench-Research, BRA-Audit recovers performance close to clean execution while using \(17.2%\)–\(40.6%\) fewer tokens than strong auditing baselines; under the same budget, its placement strategy also outperforms random auditing. Our code is available at https://anonymous.4open.science/r/BRA-7CC6/.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM, Agent, MAS

Reviews

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

The paper addresses runtime auditing for LLM multi-agent systems under a limited audit-call budget. Its core point is that auditing effectiveness depends on two things: how an auditor judges a trajectory, and where the limited audit calls are placed. The authors argue that an audit point has non-local value. Once an upstream node is checked, its unchecked exposure no longer propagates into downstream audit contexts. The method models execution as a dynamic dependency graph. Each node receives a weight, the product of a staleness term and a downstream-reachability term. The paper then defines cumulative unchecked exposure over audit contexts and states the placement problem as minimising that quantity under a cardinality budget, which it notes is combinatorial. The objective is not solved directly. Instead, the paper adopts a greedy rule that takes the largest marginal exposure reduction at each step and recomputes the marginal gains after every selection. No submodularity result or approximation guarantee is claimed for this rule, so its optimality is left open. Verified points become trusted boundaries that bound later audit contexts and localise rollback. Experiments on AgentsNet, BBH and MultiAgentBench-Research report recovery close to clean execution with 17.2%-40.6% fewer tokens than PeerGuard and Multi-Agent Debate, plus a same-budget gain over random placement of 0.040 (BBH) and 0.081 (Research) at ρ=0.4\rho=0.4. The paper claims three contributions: a new problem formulation, a new placement objective, and a better efficiency-recovery trade-off. Random auditing is the only comparison.

Critical strengths

S1. The paper's clearest strength is the reformulation of a runtime scheduling question into a well-defined problem. A runtime question, where to spend a limited number of audit calls, becomes a set-selection problem on a dependency graph: weight the nodes, define an exposure quantity, and choose a set of audit points. Because the nodes are runtime objects rather than agents, each candidate can be scored individually and the partial order among them can be handled explicitly. The construction is intuitive enough to explain in a few equations, and it is stated precisely: the audit context of a node is obtained by traversing backward and stopping at the first selected point (Eq. 8), with a node kept in the context when any path bypasses those points. The objective, the greedy rule and the audited region are all expressed in terms of the same construction, so the model stays easy to hold in mind.

S2. The paper's most distinctive mechanism is what happens to an audit point that passes. It is recorded as a trusted point, and that status does two jobs at once: it shortens the audit contexts downstream of it, and it fixes the point to which recovery rewinds when a later audit fails (Appendix G). The fault-attribution and re-audit protocol built on this is specified in implementable detail. A single verified point serving as both the boundary of the remaining audit scope and the boundary of recovery is a reuse I have not encountered elsewhere, and it is the part of the design I would most like to see developed. It is currently a mechanism rather than a theory, and I would encourage the authors to develop it further.

S3. The paper also quantifies both sides of the cost. Audit calls and rollback are reported separately as the budget is varied (Table 5), and the two move in opposite directions, with audit tokens rising from 0.74K to 5.57K while rollback tokens fall from 2.84K to 0.94K on BBH. This is more informative than the aggregate token count that an efficiency claim usually rests on, because it shows where the savings come from rather than only that they exist.

S4. The evaluation covers three complementary benchmarks, six backbones, agent counts, three topologies, budget and component ablations, and false-positive rates, with code released.

Critical weaknesses

W1. The greedy rule has no stated guarantee, so its behaviour outside the evaluated settings is unknown.

The paper adopts a greedy rule for a minimisation it calls combinatorial, but does not say what that rule preserves. Section 4.2 explains the objective and then selects the largest marginal reduction at each step, without stating whether JJ is submodular or weakly submodular, and without an approximation ratio for the case where it is not. A counterexample would be as useful as a proof here, since either would tell a reader when the rule can be trusted. As it stands I cannot distinguish the rule from a heuristic that happens to work on the three evaluated settings.

This also leaves the objective itself unvalidated. JJ sums exposure over the audit contexts, and the paper shows that the budget affects score, but not that lowering JJ produces earlier or more complete detection. If the connection does not hold, a lower exposure can coexist with missed failures, which for an auditing defence is the outcome that matters. A relationship between JJ and an outcome measure such as false negatives would settle it, and would also show whether the quantity defined here is worth minimising.

I would add one point about framing rather than substance: budgeted placement of verification on a graph is not itself a new setting. The sentence in Section 1 that the paper identifies this as a distinct problem would be more accurate if narrowed to what is specific here, namely audit points over runtime objects together with the recovery boundary.

W2. The placement comparison is against random auditing only, which leaves the source of the reported gain unclear.

The only placement comparison is against random auditing, and only at a single budget (Table 5). Random placement is a weak point of reference, because it cannot separate the contribution of the composite objective from the contribution of one of its terms: TopoImpact-only or AuditGap-only selection, or uniform spacing, would each test that. The component ablations in Tables 7-8 are informative about the terms themselves, but because the remaining term is still combined with the other, they do not tell a reader what a single-term selection rule would achieve.

The accounting also does not let a reader check that the comparison is like-for-like. The paper states that all methods share the attack settings and backbones, which does not establish equal auditor-call counts; since BRA-Audit is capped at a fraction of the candidate set per round while the other methods audit during interactions, part of the token difference may come from the setup rather than from placement. On the outcome side, the aggregate claim hides its own trade-off: on BBH, BRA-Audit spends 8175 tokens against 5355 for the clean run while its defended accuracy (0.8600) is below Multi-Agent Debate (0.9333), so on two of three benchmarks the savings accompany a lower accuracy than the strongest comparison method. False positives are reported; false negatives are not.

W3. The description of two cited defences does not match what those works report.

The sentence in Section 2 that graph-based detection "relies on labeled attacks and may generalize poorly to unseen threats" is attached to two references at once. It applies to the first, a supervised detector, but not to the second, which is unsupervised by construction and reports learning without attack labels; the second also uses the first as its supervised point of comparison. Splitting that sentence per source would make the attribution match the works cited. A second case concerns the method described as "a round-level auditing baseline adapted from AgentAuditor": it is published under a different title and is itself selective, auditing only decision-critical divergence points at 973 tokens per sample against 1762 for LLM-as-Judge. Stating the adaptation would let a reader tell how much of the reported gap comes from it, rather than from placement, given how close that work is to this paper's own premise that auditing should be selective.

Questions for authors
  1. Is J(St)J(S_t) submodular or weakly submodular, and what guarantee follows if so; if not, is there a counterexample? Does minimising JJ correspond to better detection in practice, for example in relation to false negatives?
  2. Under matched auditor-call counts, how does the method compare against TopoImpact-only greedy, AuditGap-only or round-robin selection, and uniform spacing?
  3. What are the false-negative rates, and how are they measured? Under what conditions are the token savings worth a lower defended accuracy than the strongest comparison method (BBH 0.8600 vs 0.9333; Research 0.902 vs 0.925)?
  4. Which model serves as the auditor, and how sensitive are the results to that choice? How often does the auditor's localisation identify an agent whose replacement repairs the failure, rather than a benign agent on the same path?
  5. How are GtG_t and the audit records obtained, and are the edges trusted? How are the candidate set Qt+1Q_{t+1} and the mandatory final-round audit defined and budgeted?
Reviewer_TJYaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents BRA-Audit, a framework for allocating a limited auditing budget in LLM-based multi-agent systems. The key idea is to select audit points based on cumulative unchecked exposure, taking into account both how long an agent has gone without being audited and how many downstream nodes may be affected by its outputs. A greedy algorithm then selects audit points that yield the largest marginal reduction in exposure. When an audit detects unsafe behavior, the system rolls back the affected region and re-executes it. The authors evaluate BRA-Audit on AgentsNet, 150 sampled BBH questions adapted into multi-agent workflows, and the Research scenario of MultiAgentBench. Their results suggest that BRA-Audit can recover performance close to clean execution while using fewer tokens than several existing auditing baselines. It also outperforms random audit-point selection under the same budget on BBH and MultiAgentBench-Research. The paper addresses a practical problem in multi-agent systems, and the idea of accounting for how unchecked outputs propagate through a dependency graph is appealing. However, I am not yet convinced that the experiments sufficiently establish the advantage of the proposed placement strategy over simpler alternatives, or that the security claims are supported by sufficiently broad and rigorous evaluations.

Critical strengths

1.Rather than focusing only on whether an auditor can identify problematic behavior, BRA-Audit considers where to place audits when resources are limited. The cumulative-exposure formulation captures an important aspect of multi-agent execution: unchecked upstream outputs can affect multiple downstream steps, making the placement of an audit point consequential beyond the node being inspected. 2.The experiments span structured coordination, multi-step reasoning, and open-ended research tasks. The authors also examine different audit budgets, graph topologies, backbone models, and exposure-weight components. Reporting token consumption alongside task performance is useful for understanding the practical trade-offs involved.

Critical weaknesses

1.The paper compares BRA-Audit with random audit-point selection under the same budget, but does not compare it against several straightforward alternatives, such as selecting the top-k nodes by AuditGap, TopoImpact, or their product. The component ablations do not answer this question. 2.The analysis does not establish how well the greedy strategy performs relative to the optimal placement, particularly in graphs with multiple dependency paths. An audit point does not necessarily prevent information from reaching downstream nodes through alternative paths. 3.The evaluation emphasizes task-level recovery rather than directly measuring attack detection. Explicit false-negative rates or detection recall would help establish whether the method reliably identifies and contains compromised behavior. The paper also does not report confidence intervals or variability across repeated runs.

Questions for authors

1.Could the authors compare BRA-Audit with same-budget top-k baselines ranking nodes by AuditGap, TopoImpact, and AuditGap × TopoImpact? And for small graphs, compare the greedy solution with optimal placement? 2.How exactly is audit history updated after an audit? Algorithm 1 updates LastAudit for the producing agent associated with the selected audit point. If an audited region contains outputs from several agents, are the audit histories of all those agents refreshed, or only that of the selected point's producer? 3.Could the authors report detection-level metrics, such as attack detection recall and false-negative rates, in addition to task-level recovery? It would also be helpful to report variability across repeated runs and clarify how the subjective Research scores are evaluated.

Reviewer_v45SOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies where to place a limited number of auditor calls in LLM multi-agent systems. Nodes are weighted by staleness and downstream reach, and audit points are chosen greedily to reduce unchecked exposure. Failed audits trigger rollback and replacement of the blamed agent. On three benchmarks, BRA-Audit gets close to clean performance with fewer tokens than PeerGuard and Multi-Agent Debate, though both still score higher.

Critical strengths

S1. The idea that a verified audit point also limits later audit contexts and serves as the rollback boundary is simple and useful. This is the main reason I find the paper interesting.

S2. Cost and accuracy are reported together on three different tasks, and BRA clearly beats TrinityGuard on AgentsNet and Research at similar cost.

Critical weaknesses

W1. The benefit of the placement strategy is not well isolated. The only placement baseline is random, at one budget and without variance, and the gap is small. Simple alternatives such as top-k by weight, uniform spacing or end-only auditing are missing. Since recovery uses a clean replica without the attack instruction, I suspect much of the gain comes from recovery rather than placement. This is the main reason for my rating.

W2. The efficiency claim compares single operating points. At a similar token budget, BRA seems roughly on par with PeerGuard, and it never reaches Multi-Agent Debate’s scores. No error bars are given.

Questions for authors

Do the baselines get the same rollback and clean-replica recovery? How does BRA compare with simpler placement rules at the same budget, over several seeds? In Table 5, why is the non-audit, non-rollback token cost on BBH lower than the clean run?

Comments on the paper

1 comment
Area_Chair_e7wkOpenReview ↗

Please engage in the discussion

Reviewers: if you have not responded to the authors' reply, please read it and engage in the discussion. Thanks!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.