- 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 . 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 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. sums exposure over the audit contexts, and the paper shows that the budget affects score, but not that lowering 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 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
- Is submodular or weakly submodular, and what guarantee follows if so; if not, is there a counterexample? Does minimising correspond to better detection in practice, for example in relation to false negatives?
- Under matched auditor-call counts, how does the method compare against
TopoImpact-only greedy,AuditGap-only or round-robin selection, and uniform spacing? - 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)?
- 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?
- How are and the audit records obtained, and are the edges trusted? How are the candidate set and the mandatory final-round audit defined and budgeted?
Please engage in the discussion
Reviewers: if you have not responded to the authors' reply, please read it and engage in the discussion. Thanks!