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

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/.