PaperlayerView exact revision on arXiv

Source-linked AI summary

MAADBench: The Refreshable Paradigm for Anomaly Detection in Multi-Agent Systems

Lei Ma, Dennis Hofmann, Haowen Xu, Joshua DeOliveira, Peter VanNostrand, Lei Cao, Elke Rundensteiner

arXiv:2609.36556v1cs.AI

TL;DR

Systematic anomaly detection for multi-agent systems lacks a benchmark that stays useful as tasks, traces, and LLM backbones evolve. MAADBench provides refreshable task generation, trace collection, and deterministic step-level labels; evaluation finds current methods rely heavily on supervision and remain inconsistent across backbones and anomaly types.

  • Problem

    Systematic anomaly detection for multi-agent systems remains underexplored, while evolving backbones make benchmark tasks, traces, and labels difficult to keep current.

    Source: §1 · pp. 1–2

  • Method

    MAADBench combines sampled, coupled tasks, trace generation under configurable LLM backbones, and oracle-based deterministic step-level labels.

    Source: §1 · pp. 2–3, §2 · p. 3

  • Results

    Current MAS AD methods rely heavily on supervision, with an approximately 1.5× larger gap than tabular AD, and vary across backbones while struggling with long-horizon, task-failing, and propagation-origin anomalies.

    Source: §1 · p. 3

  • Takeaways & Limitations

    MAADBench provides a systematic, refreshable testbed for developing and evaluating MAS-specific anomaly detectors as LLMs evolve.

    Source: §5 · p. 9

    MAADBench does not exhaust the MAS design space; agent organization, communication, and memory variations may introduce other anomaly surfaces and propagation patterns.

    Source: §5 · p. 9

Abstract

from arXiv · show

Recent studies report that LLM-based multi-agent systems (MAS) fail at rates of 41%-87%, yet to our knowledge, no benchmark to date supports systematic anomaly detection (AD) for them. Building MAS AD benchmarks is hard because they must remain fresh as LLM systems evolve: tasks may leak into training data and thus be memorized by LLMs, traces and anomaly patterns expire as backbones evolve, and labels must be provided reliably for each refresh. To address these challenges, we present MAADBench (MA: multi-agent; AD: anomaly detection), the first refreshable MAS AD benchmark designed for diverse, evolving LLM backbones underlying the agents. MAADBench combines (1) sampled-and-coupled generative tasks over an approximately 10^37-task space to mitigate task leakage, (2) refreshable trace generation under configurable LLM backbones, and (3) automated provision of cost-free, deterministic step-level labels for fine-grained AD evaluation. Beyond offering the paradigm itself, we run MAADBench with five state-of-the-art LLM backbones and release the MAADBench-Full dataset with 5,200 step-labeled traces. Benchmarking 25 AD methods on the MAADBench dataset reveals substantial limitations in current approaches: they rely heavily on supervision, struggle with subtle MAS-specific anomalies, and lack robustness across LLM backbones. These gaps point to a rich research agenda for MAS-specific anomaly detection, with MAADBench providing a systematic and refreshable testbed for method development and evaluation. We open-source MAADBench-Full at https://huggingface.co/datasets/hww123/MAADBench-full.

1 INTRODUCTION

MAS anomaly detection remains underexplored despite reported high failure rates, and its textual, evolving traces create benchmark challenges unlike traditional AD targets. MAADBench addresses task leakage, trace expiration, and label fidelity with a refreshable benchmark; evaluation finds current methods supervision-dependent and uneven across backbones and anomaly types.

1 INTRODUCTION

  • MAS traces are evolving multi-step textual outputs with semantic, logic-rich anomalies, unlike fixed images or tabular records and their numerical or categorical deviations.The cited examples of MAS anomaly sources include reasoning and inter-agent communication errors.Source: §1 · p. 1
  • Benchmark refresh is difficult because leakage can undermine authentic anomaly patterns, traces change with LLM backbones, and fine-grained labels are costly to regenerate reliably.Step-level labeling requires inspection of long traces, while refreshed traces require labels to be regenerated on the fly.Source: §1 · p. 2

MAADBENCH: The Refreshable Benchmarking Paradigm for MAS AD

  • MAADBench addresses task leakage, trace expiration, and label fidelity through sampled coupled tasks, trace refresh under new backbones, and oracle-grounded deterministic labeling.The passage describes the label mechanism as oracle-based; the introduction also highlights cost-free deterministic step-level labels.Source: §1 · pp. 2–3

Multi-LLM-as-Backbone MAS AD Datasets

  • MAADBench-Full contains 5,200 MAS traces with deterministic step-level labels, generated using five LLM backbones and multiple configurations.The benchmark also elicits capabilities across domains and difficulty levels, producing diverse anomaly types.Source: §1 · p. 3

Broad Evaluation Across AD Methods and LLM Backbones

  • The paper evaluates 25 AD methods across supervision levels and detector families, profiling anomalies by action, backbone, observability, and propagation.Prior MAS trace-analysis benchmarks include fixed task sets, static traces, and one-time labeling tied to particular backbones.Source: §1 · pp. 2–3

New Findings on MAS Anomaly Detection

  • Current MAS AD methods rely heavily on supervision, vary across LLM backbones, and struggle most with long-horizon reasoning, task-failing, and propagation-origin anomalies.The supervision gap is approximately 1.5× larger than in tabular AD; these findings motivate less supervision, backbone robustness, semantic understanding, and root-cause awareness.Source: §1 · p. 3

2 MAADBENCH CONSTRUCTION AND INSTANTIATION

MAADBench constructs complex multi-agent tasks from verified atomic tasks, connecting them through oracle dependencies to support deterministic labels at multiple levels. Its escape-room instantiation composes actions into puzzles and rooms, while structured traces record execution and telemetry.

Bottom-up Oracle-Guided Construction

  • MAADBench composes verified atomic tasks through oracle dependencies, allowing deterministic propagation of labels along input-output dependencies and across task hierarchy levels.The bottom-up construction supports flexible combinations of tasks from different domains and benchmarks.Source: §2 · p. 3

An Instantiation of MAADBENCH

  • The benchmark organizes atomic actions into puzzles and puzzles into rooms, with configurable task counts and dependency complexity across difficulty levels.Atomic tasks span capabilities including math and code reasoning, planning, distraction handling, environment interaction, tool use, and verification.Source: §2 · p. 3
  • At room level the MAS plans puzzle order under cross-puzzle dependencies; within each puzzle, agents execute interdependent actions with input-output dependencies.SOLVE_CLUE tasks use GSM-Hard for math and LiveCodeBench-Execution for code; remaining actions come from parameterized templates with algorithmic ground truth.Source: Figure 2 · p. 4

MAS Workflow and Trace Collection

  • The MAS harness records the acting agent, action type, input and output messages, and runtime telemetry while agents communicate through structured JSON.Telemetry includes token usage and latency.Source: §2 · p. 4

3 PROFILING MAS ANOMALIES: ACTIONS, BACKBONES, OBSERVABILITY, AND PROPAGATION

MAADBench-Full is used to profile MAS anomalies across capabilities, backbones, observability, and propagation. Results show difficulty-sensitive execution, distinct capability-by-backbone anomaly profiles, silent failures, and workflow-shaped propagation.

MAADBENCH is Challenging for SOTA LLMs

  • Room- and puzzle-level success drops sharply as difficulty increases; Claude Opus 4.8 ranks first and GPT-4.1 last at both levels.The comparison uses the same rooms across LLM instantiations.Source: Table 2 · p. 4, §3 · p. 5

Anomalies Across Capabilities and LLM Backbones

  • Verification anomalies remain below 3%, tool-use anomalies are approximately 27–39%, and reasoning anomalies range roughly 24%–59%.Planning and distraction-handling anomaly rates range from near zero to around 40% across backbones, whose capability profiles differ.Source: §3 · p. 5, Figure 3 · p. 5

Silent vs. Loud Anomalies

  • Overall, 7.7%–30.4% of anomalies are silent; planning errors are always silent, while final-step APPLY_DELTA errors are always loud.Intermediate actions show mixed behavior, so monitoring must account for both task-fatal failures and latent behavioral deviations.Source: §3 · p. 5, Table 4 · p. 5

Anomaly Propagation

  • Across GPT and Claude backbones, early OBSERVE_CLUE failures often precede failures in SOLVE_CLUE, TOOL_CALL, and especially APPLY_DELTA.APPLY_DELTA is a common sink for propagated errors, while DeepSeek-R1 shows failures spread more broadly across observation, solving, and tool-use steps.Source: §3 · pp. 5–6, Figure 4 · p. 6

4 EVALUATING ANOMALY DETECTION STRATEGIES ON MAADBENCH

The evaluation finds that current MAS anomaly detectors benefit substantially from supervision, with performance varying by method family, anomaly type, backbone, and propagation role. It identifies long-horizon reasoning and propagation origins as difficult detection settings, while motivating less-supervised, backbone-robust, and propagation-aware methods.

4.1 EXPERIMENTAL SETUP

  • MAADBENCH-EVAL contains 17,180 labeled actions, a 19.68% anomaly ratio, and an 8:2 stratified train/test split; 25 methods span four supervision settings and four families.The evaluation uses method-specific tabular, graph, MAS-aware interaction-graph, or raw-text inputs.Source: §4.1 · p. 6, §4 · p. 6

4.2 OVERALL EFFECTIVENESS OF EXISTING AD METHODS

  • MAADBench’s supervision gap is ∼0.28 AUROC, versus ∼0.20 on tabular ADBench, while top semi- and fully supervised methods reach AUROC ≥0.80.The authors note that large-scale step-level anomaly labels are often expensive to obtain in deployed MAS.Source: §4.2 · p. 6, Figure 5 · p. 7
  • AUCROC winners shift by supervision: Gemma zero-shot 0.54–0.60, DOMINANT OCC 0.70, DeepSAD/G-Safeguard semi-supervised 0.80, and XGBoost supervised 0.88.Few-shot LLM supervision brings modest overall improvement but a clearer scaling benefit; TAM remains near random at 0.42 in OCC. LLM-as-a-judge costs two orders of magnitude more than conventional detectors, motivating cascading, distillation, or selective invocation.Source: §4.2 · p. 7

4.3 DETECTION PERFORMANCE ACROSS DIFFERENT MAS ANOMALY TYPES

  • AUCROC detectability only weakly tracks action success: SELECT_PUZZLE is hardest (0.51) despite 87.0% success, while SOLVE_CLUE leads (0.64).The authors identify long-horizon reasoning over cross-puzzle dependencies as a challenge for current detectors.Source: §4.3 · pp. 7–8, Figure 6 · p. 8
  • Detection is generally easier on DeepSeek-R1 than GPT-series traces; Gemma-4-31B few-shot has cross-backbone AUCROC gaps approaching 0.38.The authors call for backbone-robust detectors and evaluation across multiple backbones.Source: Figure 7 · p. 8, §4.3 · pp. 8–9
  • Under unsupervised and OCC settings, loud anomalies are often harder than silent ones; stronger non-LLM supervision reverses this, with supervised AUCROC reaching 0.80–0.88.The authors propose richer signals for logical failures and consistency- or verification-based detection for task-failing anomalies that may remain locally plausible.Source: Figure 7 · p. 8, §4.3 · pp. 8–9

4.4 DETECTION PERFORMANCE UNDER MAS ANOMALY PROPAGATION

  • Propagation affects anomaly roles differently: origin recall falls by up to −0.04, while supervised middle-step recall gains +0.12 versus isolated failures.The results suggest propagation most clearly exposes accumulated intermediate errors.Source: Figure 8 · p. 9, §4.4 · p. 9
  • The authors recommend propagation-aware models that use inter-step dependencies; real-time root-cause localization would go beyond post-hoc attribution on completed traces.They distinguish detecting an anomaly from identifying which step initiates a cascade.Source: §4.4 · p. 9

5 CONCLUSION

MAADBench proposes a refreshable benchmark for MAS anomaly detection, with generative tasks, reproducible traces, and deterministic step-level labels. The paper positions it against benchmarks for trace analysis, general anomaly detection, agent task completion, and contamination mitigation, while acknowledging that it does not exhaust the MAS design space.

5 CONCLUSION

  • MAADBench combines generative tasks, reproducible traces, and deterministic step-level labels in a benchmark intended to remain useful as LLMs evolve.The authors instantiate the paradigm as MAADBENCH-FULL, a labeled-trace dataset, and conclude that MAS anomaly detection remains largely unsolved.Source: §5 · p. 9
  • The benchmark does not exhaust MAS configurations; changes in agent organization, communication, or memory may expose additional anomaly surfaces and propagation patterns.The limitation is discussed further in Appendix B.Source: §5 · p. 9

A RELATED WORK

  • Existing MAS trace-analysis and robustness work focuses on post-hoc failure analysis or targeted defense, rather than long-lived infrastructure for systematic anomaly-detection evaluation.Related efforts include failure taxonomies, error localization, attribution, and automated trace annotation.Source: A RELATED WORK · p. 16
  • Unlike broader anomaly-detection benchmarks that curate existing datasets, MAADBENCH generates traces from a live MAS framework and labels steps through deterministic oracle verification.The paper draws on benchmark design principles of structured evaluation, accurate labeling, and careful data curation.Source: A RELATED WORK · p. 16
  • LLM-agent benchmarks primarily assess task completion, and their verification approaches do not scale well to step-level trace labels; MAADBENCH targets behavioral anomaly detection instead.Prior process-supervision work motivates fine-grained step labels, while MM-Escape focuses on multimodal perception in a single-agent setting.Source: A RELATED WORK · p. 16
  • MAADBENCH extends template-based dynamic benchmarking by composing tasks from parameterizable puzzle subtasks with hidden dependencies, creating a large combinatorial instance space.This approach is presented as a way to make benchmark contamination practically infeasible.Source: A RELATED WORK · p. 17

B DISCUSSION AND LIMITATIONS

The discussion frames MAADBENCH as a foundation for repeatable MAS anomaly-detection evaluation, not an exhaustive representation of MAS designs. Its design principles are intended to persist across configurations, with modular automation identified as a future direction.

B DISCUSSION AND LIMITATIONS

  • Because anomaly distributions may shift as MAS components evolve, MAADBENCH is intended to regenerate labeled traces under new configurations rather than provide a permanently fixed dataset.The authors identify anomaly drift, detector transferability, and continual adaptation as directions this supports studying.Source: B DISCUSSION AND LIMITATIONS · p. 17
  • MAADBENCH prioritizes reproducible trace generation, configurable task construction, and deterministic fine-grained labeling over exhaustive coverage of MAS architectures.The paper presents these principles as a foundation for constructing and maintaining benchmarks as models and anomaly distributions evolve.Source: B DISCUSSION AND LIMITATIONS · p. 17
  • New harnesses, workflows, agent organizations, communication, tools, or memory can expose new anomaly surfaces; extending the paradigm requires corresponding execution structures, anomaly granularity, and labeling oracles.A future direction is more modular automation that incorporates components while generating workflows, oracles, and labels.Source: B DISCUSSION AND LIMITATIONS · p. 17

C LABELING COST ANALYSIS

MAADBench labels traces at effectively zero marginal cost, while the merged sections describe an escape-room example, puzzle construction, and dependency-based planning. Its examples and task design combine clue solving, instrument-state updates, distractors, and planning traps.

C LABELING COST ANALYSIS

  • MAADBench generates ground-truth answers and labels with each puzzle and action, requiring no human annotator or LLM judge and yielding effectively $0 marginal labeling cost per trace.Existing benchmark estimates include $38 per TRAIL trace and $9.2 per Who&When trace; MAST reports $1.80 in API cost per trace, with additional human effort unquantified.Source: C LABELING COST ANALYSIS · pp. 17–18

D.1 AN EXAMPLE OF ESCAPE ROOMS.

  • The easy escape-room example requires selecting a runnable two-program clue, computing its result, applying the delta to the matching instrument, and rejecting a broken clue and inconsistent instrument.The example transforms the code result into a 1,000,016-Kelvin delta and produces an adjusted reading of 1,000,104 Celsius.Source: §D.1 · pp. 18, 20

D.2 PUZZLE GENERATION

  • Each puzzle pairs a sampled math or coding problem with an instrument and unit; its answer becomes a converted delta, while fake clues, fake items, and misleading descriptions add traps.The instrument set includes thermometers, compasses, clocks, and scales, with distractor scenery also placed in rooms.Source: §D.2 · pp. 20–21

D.3 EXTREME ROOM DESIGN

  • Extreme rooms require solving four interdependent puzzles in a valid order; exhaustive enumeration verifies solution paths and configured deadends, including traps that require lookahead to avoid.The current constraints include at least two deadend paths and a deadend of depth at least two.Source: §D.3 · p. 21

D.4 TASK INSTANCE SPACE

The task instance space grows as independent per-puzzle choices are multiplied, with additional DAG variants for Extreme rooms. The accompanying sections describe oracle-based action labels, the execution harness, and structured agent prompts.

D.4 TASK INSTANCE SPACE

  • The task instance space is the product of per-puzzle question, instrument-state, and unit choices, with Extreme rooms additionally varying over 2,376 valid DAG configurations.The described factors exclude additional variation from distractors and traps.Source: §D.4 · pp. 21–22

D.5 ACTION LABELING

  • Actions are checked against pre-generated ground truth and failed actions receive error codes; checks include invalid or deadend puzzle choices, incorrect clue answers or units, and tool-call failures.Tool-call failures are counted as action-level anomalies, while their downstream effect is captured through the parent APPLY_DELTA action.Source: §D.5 · pp. 22–23

E.1 MAS HARNESS

  • A sequential role-based harness passes structured agent outputs and messages downstream, updates the environment from submitted readings, and records action, model-call, and tool-call data for oracle annotation.The same role structure and action pipeline support both Tool and No-Tool settings.Source: §E.1 · p. 23

E.2 ACTION AND AGENT PROMPTS

  • Agent prompts specify ordered task instructions and require JSON outputs with structured fields, including the converted delta and final instrument reading for APPLY_DELTA.The APPLY_DELTA instructions require converting the delta before addition and applying wrapping where needed.Source: §E.2 · p. 24

E.3 COMPUTATIONAL COST OF MAADBENCH-FULL

Generating MAADBENCH-FULL across five backbones costs $394.32 for 5,200 traces, averaging $0.076 per trace; costs vary with backbone and configuration coverage.

E.3 COMPUTATIONAL COST OF MAADBENCH-FULL

  • $394.32 generates 5,200 traces, averaging $0.076 per trace across five backbones and sampled configurations.Claude Opus 4.8 covers only 400 traces at temperature 0.0, so its total cost is not directly comparable with other backbones.Source: §E.3 · p. 27, Table 7 · p. 27
  • Claude Sonnet 4.6 costs $146.63, while DeepSeek-R1 costs $39.57 despite producing 13.05M output tokens.The passage attributes the difference primarily to output-token volume and price per million tokens.Source: §E.3 · p. 27
  • Claude Opus 4.8 costs $93.44 across 400 traces and is the most expensive backbone per trace at $0.234.It covers only the temperature-0.0 configurations, so its per-backbone total is not directly comparable.Source: §E.3 · p. 27, Table 7 · p. 27

F ADDITIONAL ANOMALY PROFILING

MAADBench extends MAST with agent-capability and error-propagation failure families, then profiles their prevalence across backbones. Reasoning errors and error propagation dominate across all five backbones.

F ADDITIONAL ANOMALY PROFILING

  • MAADBench maps action-level error codes to MAST failure modes using deterministic rules, including a cascade rule for downstream failures after an upstream failure.Table 8 summarizes the mapping rules; a downstream failure on the same puzzle is labeled FM-5 when any upstream action has failed.Source: F ADDITIONAL ANOMALY PROFILING · p. 27, Table 8 · p. 28
  • FC4 captures single-agent capability failures, including distractor susceptibility and reasoning errors, while FC5 captures downstream failures caused by upstream failures.These families are orthogonal to MAST’s FC1–FC3 focus on coordination and prompt-design failures.Source: F ADDITIONAL ANOMALY PROFILING · p. 27
  • FM-4.2 (Reasoning Error) and FM-5 (Error Propagation) dominate failures across all backbones.Figure 9 presents distributions across five LLM backbones, separating MAST modes from MAADBench’s extended modes.Source: F ADDITIONAL ANOMALY PROFILING · p. 27, Figure 9 · p. 28

G EXPERIMENTAL SETUP DETAILS

  • The experimental setup details organize anomaly-detection algorithms into four supervision levels.The supplied passage introduces this organization but does not enumerate the levels.Source: G EXPERIMENTAL SETUP DETAILS · p. 28

G.1 DATA PROCESSING

The data-processing methods represent traces as tabular features or heterogeneous execution graphs, with additional MAS-specific and LLM-based detectors built on those representations or complete traces.

G.1 DATA PROCESSING

  • The test set is shared across methods, while training uses a stratified random 80% of actions and varies by supervision level.The remaining 20% of actions are reserved for testing; each random seed produces a different sample combination.Source: §G.1 · p. 28
  • Tabular methods clean reasoning outputs, extract LLM-call and token-use statistics, and embed each action’s cumulative outputs for context.The contextual representation uses all outputs up to the current action and a 384-dimensional all-MiniLM-L6-v2 sentence-transformer embedding.Source: §G.1 · p. 28
  • Graph-based methods encode execution order as directed agent-to-agent edges, with embedded system prompts on agent nodes and reasoning outputs plus call duration on edges.Source: §G.1 · p. 29
  • G-Safeguard and BlindGuard use the graph representation described for graph-based methods.Source: §G.1 · p. 29
  • LLM-based detectors receive complete JSON execution traces and a system prompt describing task context and MAS components.Their anomaly-definition prompts are revised based on MAST’s LLM-as-a-judge prompts.Source: §G.1 · p. 29

G.2 METHOD DETAILS

The benchmark compares unsupervised, one-class, semi-supervised, and supervised detectors, including graph-based and LLM-based approaches. In semi-supervised evaluation, several non-LLM methods achieve higher AUC at much lower runtime cost than LLM-based detectors.

G.2 METHOD DETAILS

  • Unsupervised methods require no labels, while one-class methods train only on normal samples and detect deviations from learned normality.Source: §G.2 · p. 30
  • The one-class method set includes OC-SVM, Autoencoder, DeepSVDD, TAM, DOMINANT, and BlindGuard, using boundaries, reconstruction, compact representations, node affinity, or corruption-guided training.Source: §G.2 · p. 30
  • Semi-supervised methods use a small set of labeled anomalies; Gemma few-shot variants receive three normal and three abnormal examples without gradient-based training.The listed methods include DeepSAD, DevNet, GGAD, G-Safeguard, and Gemma variants.Source: §G.2 · pp. 30–31
  • Supervised methods require labeled normal and abnormal training data; the listed approaches include SVM, Random Forest, XGBoost, and G-Safeguard.Source: §G.2 · p. 31
  • All methods score each test sample, then threshold scores using the known number of test anomalies; LLM detectors use constrained yes/no token logits as scores.Source: §G.2 · p. 31
  • ∼0.79–0.80 AUC is achieved by DeepSAD, DevNet, and G-Safeguard at much lower cost, versus ∼0.57–0.63 AUC for LLM-based detectors with orders-of-magnitude higher runtime cost.Figure 10 compares semi-supervised methods’ detection performance and normalized runtime GPU cost; the authors conclude that scaling LLM detectors alone is not cost-effective for MAS AD.Source: Figure 10 · p. 31, §G.2 · pp. 31–32

H ADDITIONAL EVALUATION RESULTS

Additional evaluations report overall anomaly-detection performance across supervision settings and examine propagation-chain detection by step role. Middle steps are easier to detect on average than origin or downstream steps.

H ADDITIONAL EVALUATION RESULTS

  • Table 9 reports overall anomaly-detection performance across four supervision settings, marking results significant relative to Random at p < 0.01 or p < 0.05.Dark-blue and light-blue cells denote the respective significance thresholds.Source: Table 9 · p. 32
  • Middle-step recall averages 0.47 across methods, versus 0.29 for both origin and downstream steps; Random Forest leads overall propagation-role recall at 0.59.DOMINANT leads on origin steps (0.53), OC-SVM on middle steps (0.70), and DevNet on downstream steps (0.77).Source: Figure 11 · p. 32
  • Table 10 reports one-tailed two-sample t-test p-values for comparisons of methods against Random across four performance metrics.Source: Table 10 · p. 33
  • Table 11 reports AUCROC by method and action, with mean and standard deviation over available train-test splits and action success rates in parentheses.Per-column maxima are bolded.Source: Table 11 · p. 33

Related papers

Loading 2609.36556v1…