Source-linked AI summary
BRA-Audit: Budgeted Runtime Auditing for LLM Multi-Agent Systems via Cumulative-Exposure Audit-Point Placement
Kaixiang Wang, Yidan Lin, Jiong Lou, Jie Li
TL;DR
LLM multi-agent systems face a cost-effectiveness dilemma in runtime auditing: sparse checks may weaken oversight, while frequent checks consume many tokens. BRA-Audit places a fixed audit budget over dynamic dependency graphs to limit unchecked exposure, restoring performance close to clean baselines while reducing token use by 17.2%–40.6%.
Problem
Runtime auditing in LLM multi-agent systems must preserve audit effectiveness while allocating limited audit calls between sparse and frequent checking strategies.
Method
BRA-Audit models execution dependencies as a dynamic graph and greedily places limited audit points in stale, influential regions to minimize cumulative unchecked exposure and localize rollback.
Results
17.2%–40.6% fewer tokens than heavy guard baselines while restoring task performance close to clean settings across coordination, reasoning, and open-ended tasks.
Takeaways & Limitations
BRA-Audit supports a favorable balance between recovered task performance and runtime auditing cost across the evaluated multi-agent settings.
Takeaways & Limitations
The runtime dependency graph is represented as a directed acyclic graph after interactions are unrolled across rounds.
Abstract
from arXiv · showhide
LLM-based multi-agent systems (LLM-MAS) solve complex tasks through specialized collaboration, but inter-agent dependencies can propagate hallucinated or malicious outputs into system-level failures. Auditor agents mitigate these risks, yet existing strategies face an efficiency dilemma: end-only auditing reviews long trajectories and final outputs, potentially weakening audit effectiveness and enlarging rollback scope, while auditing every agent each round improves detection and localization at high token cost. How can guard performance be preserved while minimizing token cost? To address this problem, we propose BRA-Audit, a budget-aware runtime auditing framework that models MAS execution as a dynamic dependency graph and formulates audit scheduling as audit-point placement under a fixed audit-call budget to minimize cumulative unchecked exposure. Its greedy scheduler prioritizes influential and long-unaudited regions, while trusted audit points enable localized recovery. Across structured coordination, complex reasoning, and open-ended tasks, BRA-Audit restores performance close to the clean setting, remains competitive with heavy guard methods and reduces end-to-end token consumption by \(17.2\%\)--\(40.6\%\).
Introduction
BRA-Audit addresses failure propagation in LLM multi-agent systems by placing limited runtime audits at critical points in a dynamic dependency graph. Its budget-aware scheduling preserves performance near clean baselines while reducing token consumption by 17.2%–40.6% versus heavy guards.
- Problem: Hallucinated or malicious messages can propagate through inter-agent dependencies, turning local errors into difficult-to-localize system-level failures.Long, dependency-dense trajectories can obscure failure sources, weaken audit effectiveness, delay intervention, and increase rollback costs.
- Problem: Interaction-level auditing improves early detection and localization but repeated auditor calls impose substantial token costs on benign interactions.This motivates determining when and where to audit while preserving guard performance and minimizing token cost.
- Method: BRA-Audit models communication and execution dependencies as a dynamic graph and formulates fixed-budget audit scheduling as audit-point placement minimizing cumulative unchecked exposure.Runtime outputs are graph nodes, information flow forms edges, and limited audit resources are directed toward critical execution points.
- Results: 17.2%–40.6% lower token consumption is achieved versus heavy guards such as PeerGuard and Multi-Agent Debate, while task performance is restored close to clean baselines.The reported results span MAS collaboration environments and complex open-ended tasks, with competitiveness against stronger auditing baselines.
- Method: The online scheduler sequentially selects audit points by marginal cumulative-exposure reduction, combining audit gaps with downstream dependency reachability.This weighting targets influential regions that have remained unaudited longer.
Related Work
Prior work shows that LLM-MAS dependencies enable local errors and adversarial instructions to propagate into system-level failures. Existing safeguards trade off detection and rollback precision against token and latency costs, motivating BRA-Audit’s budgeted audit-point placement.
- Attacks and Failures in LLM-MAS: Inter-agent dependencies allow local errors to escalate into system-level failures and enable malicious instructions to self-propagate across agents.Manipulated knowledge can also spread through conversations and persist in shared retrieval memories.
- LLM Multi-Agent Safeguarding: Prompt-based self-reflection can inherit the generator’s failure modes, while graph-based guards may depend on labeled attacks and generalize poorly to unseen threats.These limitations motivate more reliable approaches based on LLM auditors.
- Motivation: Existing safeguards either inspect trajectories too coarsely, weakening detection and enlarging rollback scope, or audit every interaction at substantial token and latency cost.The resulting efficiency dilemma concerns preserving effective auditing while reducing redundant checks.
- Motivation: BRA-Audit addresses this trade-off through budgeted audit-point placement that preserves effective trajectory auditing while reducing redundant checks.The framework is introduced as a response to the limitations of coarse and exhaustive auditing.
System Model
BRA-Audit models LLM-MAS execution as a dynamic dependency graph whose nodes and edges capture runtime objects and information or error propagation. Runtime auditing places audit points on this graph to detect unsafe content and enable localized containment or rollback of affected trajectories.
- Execution model: Each agent has a predefined role, interaction pattern, information sources, and tools within the LLM-MAS execution model.
- Execution graph: Runtime execution is represented as a dynamic dependency graph of agent messages, intermediate results, tool interactions, retrieved evidence, and aggregation results.Nodes carry producing-agent, timestamp, and content information; directed edges encode communication, evidence usage, tool execution, or aggregation dependencies.
- Audit model: Auditing places selected nodes under inspection, designating safe nodes as trusted audit points and enabling blocking, sanitization, isolation, or rollback when unsafe behavior is found.The auditor uses context from the previous audit point to the selected node.
- Threat model: Unsafe outputs from compromised agents, hallucinations, tool errors, poisoned knowledge bases, corrupted websites, or misleading documents can propagate through dependencies and affect later reasoning or final results.The threat model treats these varied causes as corrupted information entering the execution graph, including fabricated evidence, omitted constraints, incorrect intermediate results, distorted aggregation, and unsafe tool usage.
Method
BRA-Audit models runtime auditing as audit-point placement on a causal dependency DAG under a limited audit-call budget. It greedily minimizes cumulative unchecked exposure by prioritizing audit points that reduce downstream exposure and enable localized recovery.
- Audit semantics: Each audit point bounds its inspected dependency region, and a passing audit makes its output trusted input for downstream execution.Unsafe regions are blocked and recovered before execution continues, limiting rollback and preserving trusted information flow.
- Scheduling priorities: The scheduler prioritizes influential nodes and agents with long verification gaps, while the final-round producer is mandatorily selected within the budget.Influence is represented through downstream reach, and verification age captures risk accumulation while outputs remain unchecked.
- Optimization objective: The scheduler minimizes cumulative unchecked exposure, jointly reducing audit-context size and delayed-detection exposure under a fixed number of auditor calls.The objective captures repeated inheritance of unchecked information into downstream computation, while the audit budget controls auditor-call count.
- Runtime model: BRA-Audit unrolls causal agent interactions into a directed acyclic runtime dependency graph and schedules audits online before each execution round.The scheduler updates the graph after each interaction round and selects points before the next round begins.
- Scheduling algorithm: BRA-Audit greedily selects the candidate with maximum marginal exposure reduction, recomputing gains after each selection until the audit budget is exhausted.This accounts for overlapping downstream effects among audit points rather than scoring candidates independently.
Experiment
Experiments evaluate BRA-Audit across coordination, reasoning, and multi-agent settings for defense effectiveness, cost, robustness, and component behavior. Results show strong recovery under attack, favorable defense–cost trade-offs, and stability across models, budgets, graph sizes, and topologies.
- Datasets and settings: BRA-Audit is evaluated on AgentsNet, BIG-Bench Hard, and MultiAgentBench-Research using AutoGen multi-agent systems.AgentsNet tests controlled multi-round coordination, while BBH evaluates complex logical reasoning; 20% of agents are designated malicious, and Qwen3-235B-A22B-Instruct-2507 is the main backbone.
- Attack vulnerability: 46.0% relative degradation occurs on AgentsNet under attack, with the overall score falling from 0.8162 clean to 0.4407.The result demonstrates that a small number of malicious or hallucinating agents can propagate faulty outputs through communication and aggregation.
- Defense effectiveness and cost: 0.8208 overall score is restored on AgentsNet with 54.5K tokens, while using 17.2% fewer tokens than PeerGuard and 28.4% fewer than Multi-Agent Debate.BRA-Audit outperforms AuditAgent, GuardAgent, and TrinityGuard and matches clean results on Consensus, Coloring, and VertexCover; similar defense–cost trade-offs appear on BBH and MultiAgentBench-Research.
- Backbone model ablation: 0.8208 score with 54.5K tokens provides Qwen the best performance–cost balance among the tested backbone models.Across six backbones, overall scores range from 0.7830 to 0.8550; GPT-5 reaches 0.8550 at 76.2K tokens, while Gemini-3 uses 48.8K tokens.
- Audit-budget ablation: 0.4 audit ratio reaches 0.860 on BBH with 8.18K tokens and 0.902 on MultiAgentBench-Research with 38.5K tokens.Larger budgets further improve BBH to 0.873 at ρ = 0.6 and 0.893 at ρ = 1.0, while Research reaches 0.906 at ρ = 0.6.
- Robustness and component ablations: 0.8458, 0.8127, and 0.8040 scores are achieved on Watts–Strogatz, Barabási–Albert, and Delaunay graphs, respectively.With 4, 8, and 16 agents, scores are 0.8370, 0.8473, and 0.7781, while token consumption rises from 18.9K to 41.9K and 102.8K; removing AuditAge lowers the overall score from 0.821 to 0.758, and removing ClosedImpact lowers it to 0.793.
Conclusion
BRA-Audit is a cost-aware runtime defense for LLM multi-agent systems that places limited audit points using dependency structure and cumulative unchecked exposure. It targets long-unaudited, influential regions to reduce propagation, shorten audit contexts, and localize rollback.
- Conclusion: BRA-Audit models LLM-MAS communication as a dependency graph and formulates auditing as cumulative-exposure audit-point placement.This provides the framework’s basis for scheduling audits under limited resources.
- Conclusion: By combining audit gaps with topological impact, BRA-Audit selects limited audit points in long-unaudited and influential regions.The scheduler prioritizes regions that are both insufficiently audited and structurally consequential.
- Conclusion: The selected audit points shorten audit contexts, limit unchecked propagation, and localize rollback.These mechanisms address both auditing overhead and the scope of recovery after detected failures.
- Conclusion: BRA-Audit was evaluated on structured coordination, complex reasoning, and open-ended tasks.The experiments span three task categories identified in the conclusion passage.