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

Details

In LLM-based multi-agent systems, a hallucinated or adversarially manipulated output from one agent can propagate through inter-agent dependencies into system-level failures. Auditor agents mitigate this, but the cost-performance trade-off is difficult: auditing every agent every round is expensive, while end-only auditing lets problems propagate before detection. BRA-Audit, from Kaixiang Wang and colleagues, models MAS execution as a dynamic dependency graph and frames audit checkpoint placement as an optimization problem: minimize cumulative unchecked exposure within a fixed audit-call token budget. A greedy scheduler prioritizes agents with high influence scores and those that have gone longest without an audit check. Trusted audit points enable localized recovery when an issue is detected, limiting blast radius. Tested across structured coordination, complex reasoning, and open-ended tasks, BRA-Audit recovers performance close to the clean baseline while cutting end-to-end token consumption by 17.2–40.6% compared to full-round auditing. The 17-40% range varies by task type, with the largest savings on structured coordination tasks. This is directly applicable to production multi-agent pipelines where auditing costs are a real budget constraint.