acceptodds
Under review as a conference paper at ICLR 2027

Evaluating Compositional Failures in Multi-Agent Systems

Abstract

Multi-agent systems (MAS) are increasingly utilized in combination with tool use to empower agents to take on difficult real world tasks. In these systems, individually harmless actions can be composed into executions that result in system failures, making testing the safety of these multi-agent systems critical. These failures are difficult to discover because they emerge only when agents interact. Yet existing benchmarks do not test whether red teams can uncover compositional failures by learning how agents' actions affect one another. To solve this, we introduce MAS-Comp-Bench, a set of interactive realistic environments in which red teams are tasked with automatically finding compositional failures that only emerge through interaction. Our simulation engine allows for red teams to submit any possible sequence of agent actions as tools rather than being confined to a fixed attack plan. A finite catalog of failure taxonomies allows for comprehensive evaluation of what red teams find and miss. Additionally, we provide a multi-agent red-teaming harness designed to improve probing efficiency by learning unspecified dependencies between agents and using this knowledge to guide subsequent attacks. Experiments show that our harness discovers more compositional failures within the same budget than existing baselines.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
red-teaming, safety, multi-agent systems

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_b37sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper focuses on “compositional failures” in multi-agent systems: although each individual agent behaves in accordance with its local rules, the agents’ combined actions may violate system-level safety, correctness, or privacy requirements. For example, one agent may legitimately generate a data-export handle, while another may legitimately publish that handle as a shared link. Neither action is problematic in isolation, but their combination may result in cross-tenant data leakage. The paper makes two main contributions: it introduces the MAS-Comp-Bench benchmark and proposes RedExplorer, an automated red-teaming framework.

Critical strengths
  1. The paper introduces a relevant benchmark and an automated red-teaming framework.

  2. The paper conducts meaningful experiments to evaluate the proposed benchmark and framework.

Critical weaknesses
  1. The novelty over prior work is not sufficiently clear. The paper’s definition of compositional failure seems closely related to existing work on emergent failures, cascading failures, privacy leakage through composition, harmful tool/skill composition, and multi-agent collusion. The current differences, such as hidden dependencies and autonomous discovery, seem more like differences in the evaluation setting than a fundamentally new type of failure. The paper should clarify whether its main contribution is a new failure category or a new framework for discovering existing compositional risks, and compare more systematically with related work.

  2. The experiments are too limited to support broad generalization claims. The benchmark contains only three synthetic environments, apparently with one fixed instance per domain and little variation in topology, permissions, tools, or system dynamics. More importantly, all four additional failures found by RedExplorer come from the multi-tenant-records environment, while neither method finds any failures in the other two environments. This makes it difficult to conclude that RedExplorer works broadly across MAS settings. More independent environments, held-out variants, and ideally a real or semi-realistic MAS should be evaluated.

  3. The main results need repeated runs and uncertainty analysis. The headline result is an increase from one to five discoveries, reported as a 400% improvement, but it is unclear whether the experiments were repeated across independent runs. With such small absolute numbers, and with all additional discoveries coming from one environment, the percentage improvement can be misleading. The experiments should be repeated with multiple seeds, with confidence intervals or other statistical analysis reported. The paper should also emphasize the absolute recall improvement from 4% to 20%.

  4. More baselines and ablations are needed to explain why RedExplorer works. The main comparison is against a solo-memory baseline, without stronger search or planning baselines such as random search, beam search, MCTS, evolutionary search, or coverage-guided approaches. The paper also lacks ablations of key components such as the memory agent, orchestration agent, multiple execution agents, and diversity constraint. As a result, it is unclear whether the gain comes from the multi-agent design itself, greater search diversity, additional candidate generation, or simply more computation. Budget-, model-call-, and token-matched baselines and component-level ablations would make the conclusions much stronger.

Questions for authors
  1. Does the paper introduce a new type of failure, or does it propose a new evaluation framework for existing compositional risks? I suggest adding a systematic comparison with related work along dimensions such as the failure definition, information visible to the attacker, interaction setting, whether an attack plan is provided in advance, whether discovery is autonomous, and whether a complete failure catalog is available. The novelty claims in the title, abstract, and contribution statements should be adjusted accordingly.

  2. Could the authors explain why the evaluation considers only the three scenarios of software engineering, e-commerce operations, and multi-tenant records?

  3. In the no-feedback control reported in Table 5, why do both GPT-4o and Claude Opus 4.8 produce zero schema-valid plans, even though the environment descriptions and tool schemas are retained, as stated in Table 9?

Reviewer_Z16oOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces MAS-Comp-Bench, a benchmark for evaluating whether automated red teams can discover compositional failures in multi-agent systems through iterative interaction. A compositional failure is defined as a trajectory in which the participating agents and tools remain locally compliant, but their combined effects violate a global requirement. The benchmark contains three deterministic simulated environments covering software engineering, e-commerce operations, and multi-tenant records. Across these environments, it exposes 103 callable tools and defines 25 certified failure mechanisms through hidden state predicates and replayable canonical plans.

The paper also proposes RedExplorer, a multi-agent red-teaming architecture with separate memory, orchestration, and execution roles. The memory agent summarizes previous attempts, the orchestration agent proposes distinct exploration paths, and two execution agents instantiate those paths as concrete tool-call sequences. Under a matched budget of 40 submitted attacks per environment, GPT-4o with RedExplorer discovers five distinct mechanisms, compared with one for a GPT-4o solo-memory baseline, while the estimated API cost decreases from $3.54 to $3.21. All four additional discoveries occur in the multi-tenant-records environment; neither method discovers a failure in the software-engineering or e-commerce environments. The paper further compares several closed- and open-weight models and studies the effect of execution feedback and three identifier interfaces.

Critical strengths
  1. The benchmark targets an important and well-defined gap in multi-agent safety evaluation. Requiring a red team to infer hidden cross-agent dependencies from execution feedback is materially different from evaluating a fixed attack plan or a predefined harmful composition. The distinction is clearly formalized in the interaction protocol and supported by a deterministic execution and replay mechanism.

  2. The evaluator-side failure catalog enables coverage-based evaluation. Associating each mechanism with an explicit state predicate, canonical plan, initial state, and replay trace is a strong design choice. It supports reproducible scoring and, at least relative to the designed catalog, measures both discoveries and misses under a fixed interaction budget.

Critical weaknesses
  1. The empirical validation of RedExplorer is too narrow. All four additional discoveries in the one-to-five improvement occur in the multi-tenant-records environment, while both methods remain at zero in software engineering and e-commerce. The comparison is limited to GPT-4o, and the paper does not clearly report independent repetitions, uncertainty, or per-mechanism discovery frequency. The current evidence therefore directly constrains the assessment of the method's effectiveness and stability. The result is a promising proof of concept, but the empirical scope remains too narrow for a paper presenting RedExplorer as one of its main methodological contributions.

  2. The benchmark interface does not sufficiently separate plan validity from compositional-security reasoning. In the GPT-4o solo-cold interface ablation, the semantic-neutral interface is the strongest variant but reaches only a 19.3% valid-plan rate and a mean execution depth of 0.483. This indicates that the interaction interface itself may be a substantial bottleneck: low mechanism recall may reflect tool arguments, cross-step references, or output-format failures rather than difficulty in discovering hidden dependencies. Low scores therefore do not by themselves demonstrate that the benchmark is meaningfully unsaturated or that compositional reasoning is the dominant challenge.

  3. The main experiments omit plan-level diagnostic metrics. The primary model comparison and the RedExplorer comparison mainly report final mechanism counts, mechanism recall, and cost, but do not provide valid-plan rate, execution depth, invalidity causes, or attack success conditioned on validity for each model and method. It is therefore unclear at which stage the low recall arises across models, or how much of RedExplorer's five-versus-one gain comes from improved plan executability rather than stronger hidden-dependency discovery.

  4. Controls and component attribution are insufficient. RedExplorer jointly introduces memory, orchestration, two execution agents, and parallel candidate paths. Matching submitted attacks and reporting total cost are useful controls, but the study does not adequately match or separate model calls, token use, candidate multiplicity, and the contribution of each role. A key baseline would let the solo method generate two independent candidates per round under a similar call or token budget, or compare against a planner-executor decomposition without specialized memory and orchestration.

  5. The analysis and visual presentation do not explain the dominant failure modes. The paper does not provide an error taxonomy or representative trajectories explaining the persistent zero discoveries in software engineering and e-commerce. Aggregate tables alone cannot distinguish safety refusals, formatting errors, argument-binding failures, premature termination, insufficient exploration, and valid but unsuccessful attacks. I recommend adding a small number of targeted figures rather than decorative illustrations: per-environment recall plots, a validation/execution error breakdown, and one successful and one failed exploration trajectory. These would substantially improve both the presentation and the diagnostic value of the benchmark.

Questions for authors
  1. How many independent runs were performed for the main model comparison and the RedExplorer comparison? If the current table summarizes a single run, can the authors report repeated API runs or state this limitation explicitly? Even a modest number of repetitions with per-mechanism discovery frequencies would substantially improve confidence in the 5-versus-1 result.

  2. Please report valid-plan rate, execution depth, invalidity causes, and attack success conditioned on plan validity for every model and method in the main experiments. Does RedExplorer's discovery gain remain after controlling for plan validity?

  3. Was a baseline considered that matches both submitted attacks and model calls or token budget? Letting the solo method generate two independent candidates per round, or using a planner-executor decomposition without specialized memory/orchestration, would help separate multi-path sampling from role specialization.

  4. Could the authors provide representative complete failure trajectories from the software-engineering and e-commerce environments and categorize them as safety refusals, formatting/parsing errors, argument-binding errors, execution failures, or valid plans that missed a mechanism? This would clarify whether the zero-discovery results indicate intrinsic difficulty or an interface bottleneck.

Reviewer_kYmYOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces MAS-Comp-Bench to evaluate the ability of a red team to discover compositional failures in MAS. The benchmark provides simulated environments with predefined failure mechanisms and execution feedback to assess how effectively red teams identify hidden cross-agent dependencies. The authors also propose RedExplorer, a multi-agent red-teaming framework. It leverages memory, planning, and execution agents to explore and discover compositional failures.

Critical strengths
  • It addresses the important problem of "compositional failure" in MAS.

  • It introduces a benchmark that systematically evaluates the ability of LLM-based red teams to discover compositional failures.

  • It also proposes a red-teaming framework for exploring and discovering compositional failures through interactions with MAS.

Critical weaknesses
  • The paper lacks a detailed explanation of the 25 compositional failure mechanisms. It is unclear whether these mechanisms were collected from real-world MAS execution failures or arbitrarily designed by the authors. Furthermore, since the diversity and representativeness of these failure mechanisms are not examined, it is questionable whether the benchmark adequately reflects diverse compositional failure patterns observed in real-world MAS execution.

  • RedExplorer lacks technical novelty and contributions. The authors claim that RedExplorer learns cross-agent dependencies. However, RedExplorer does not provide any explicit methodology or mechanism for such learning. Furthermore, the proposed memory-orchestration-execution architecture is well-known and widely used, which raises concerns about the technical contribution of the proposed methodology.

  • Given the methodology design, the performance improvement of RedExplorer does not appear to stem from cross-agent dependency learning. It is unclear what actually drives this improvement. Moreover, the multi-agent architecture could be replaced by a single LLM performing each process sequentially. Why is a multi-agent architecture necessary? More experiments are needed to investigate the underlying reasons for the performance improvement.

  • The performance improvement is limited. RedExplorer discovers only four more failure mechanisms than the solo-memory baseline. More critically, the improvement is confined to the multi-tenant records environment, while no improvement is observed in the other two environments. These results do not sufficiently support the claim that RedExplorer consistently improves compositional failure discovery across diverse MAS environments.

Questions for authors

See Weakness

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.