acceptodds
Under review as a conference paper at ICLR 2027

Which Graph Is Safest? Predicting Adversarial Capture of LLM Agent Groups from Local Kernels

Abstract

In multi-agent LLM deliberation, a single adversarial agent can steer the group to a wrong answer, and how often this happens depends on the communication graph. We show that the deliberation dynamics are well predicted by a few local quantities: the question under deliberation, an agent's own answer, its number of neighbours, and how many of them hold the adversary's answer, with the adversary counted separately from neighbours it has converted. On this state we approximate the deliberation by a Markov chain whose transitions come from a per-question switching kernel. We study three open-weight 8B models, 600 MMLU-Pro questions and three memory protocols, with one adversary among six agents. Calibrated on eight graph–placement configurations, the kernel predicts adversarial capture, the probability that the adversary's answer becomes the group's majority, on 52 other configurations with a mean error of , and it extends to groups of eight and twelve agents, two adversaries and ten rounds. Under a new question set or new adversary messages, question-specific susceptibility changes, so absolute capture needs four to five calibration runs there, but the ranking of graphs transfers much better. Ranking all 112 connected six-agent graphs, concentrating links on one agent is worst for every model, and which graph is best depends mainly on how the group starts: counterfactually raising how often the correct answer starts as a minority moves the most accurate graph from dense to sparse for models whose agents follow the majority strongly. On a second question set, LogiQA, reading these curves at its solo-answer distribution reproduces the ranking obtained after calibrating on LogiQA with rank correlation –. Our code is available on https://anonymous.4open.science/r/which-graph-is-safest-38C3/README.md.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
multi-agent systems, large language models, multi-agent debate, adversarial robustness, misinformation spread, network topology, opinion dynamics

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_EGwfOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates how communication topology influences the vulnerability of multi-agent LLM systems to adversarial answer propagation. The authors propose a local-to-global prediction framework that models individual agents' answer-switching behavior using a compact set of local features, including their previous answers, node degrees, and the number and identity of neighbors supporting the adversarial answer. These local switching probabilities are estimated through a hierarchical Beta-Binomial kernel and composed into a Markov chain to approximate group-level deliberation dynamics.

The framework is evaluated using three open-weight 8B language models, 600 MMLU-Pro questions, and three memory protocols. Experimental results show that the proposed kernel achieves a mean absolute prediction error of 0.012 on 52 unseen graph-placement configurations after calibration on eight configurations. Additional evaluations investigate larger agent groups, multiple adversaries, extended deliberation rounds, and distribution shifts involving new questions and adversarial messages.

The authors further apply the framework to rank all 112 connected six-agent graphs, revealing that topology safety depends on adversarial placement, model-specific response dynamics, and the initial distribution of agents' answers. The results suggest that centralized topologies are particularly vulnerable under worst-case adversarial placement, while the relative advantages of dense and sparse graphs depend on the initial correctness distribution and agents' conformity behavior.

Overall, the paper provides an empirical framework for predicting adversarial propagation and understanding topology-dependent robustness in multi-agent LLM systems.

Critical strengths

S1. A principled local-to-global framework for predicting adversarial propagation. The paper presents a systematic framework that connects individual agents' local switching behavior with group-level adversarial capture through a Markov-chain approximation. By decomposing complex multi-agent interactions into measurable local transition probabilities, the approach provides an interpretable alternative to repeatedly simulating every candidate communication topology. This is a meaningful methodological contribution because it enables systematic robustness evaluation while reducing the need for exhaustive multi-agent deliberation experiments.

S2. Strong predictive performance with relatively limited calibration data. The framework achieves a mean absolute prediction error of 0.012 on 52 unseen graph-placement configurations using only eight calibration configurations. The authors additionally evaluate alternative graph-level predictors, larger agent populations, multiple adversaries, and longer deliberation horizons. These results provide substantial empirical support for the proposed local-to-global decomposition and demonstrate its potential to reduce the computational cost of topology evaluation.

Critical weaknesses

W1. Limited generalizability to realistic and heterogeneous multi-agent systems. The experimental evaluation is primarily conducted on homogeneous groups of six agents using three instruction-tuned 8B language models. Although the authors provide additional results for larger groups, these experiments cover only a small number of regular graph structures and are conducted without memory. Consequently, it remains unclear whether the proposed framework can reliably characterize heterogeneous agent populations, larger and more irregular communication networks, or systems with specialized agent roles. This limitation reduces confidence in the applicability of the framework to realistic multi-agent deployments.

W2. Strong dependence on simplified state representations and conditional independence assumptions. The Markov approximation assumes that agents make independent decisions conditioned on their local states, while the primary state representation only records whether an agent holds the adversary's answer. Although the paper provides pairwise co-switching tests and a three-state extension, these analyses do not fully establish the validity of the assumptions under more complex interactions. In particular, semantic dependencies among messages, accumulated conversational context, and higher-order correlations between agents may introduce dependencies that are not adequately represented by the proposed kernel. This potentially limits the framework's predictive reliability beyond the controlled experimental setting.

Questions for authors

Q1. Generalization to heterogeneous agent populations. The current evaluation mainly considers homogeneous groups composed of instances of the same language model. How would the proposed kernel handle heterogeneous groups containing agents with different model architectures, capabilities, or communication roles? Would separate kernels be required for different agent types, and how would this affect the calibration cost and predictive accuracy?

Q2. Validity of the conditional independence assumption. The proposed Markov-chain approximation assumes conditional independence among agents given their local states. While the pairwise co-switching analysis provides supporting evidence, could the authors further clarify whether higher-order dependencies or shared semantic information may violate this assumption? In particular, how sensitive are the predictions to dependencies introduced by shared conversation histories or correlated reasoning errors?

Q3. Reliability of topology rankings under prediction uncertainty. The paper indicates that differences in capture rates below approximately 0.03 cannot be reliably distinguished. How many of the reported safest-topology rankings remain statistically distinguishable after accounting for prediction uncertainty and sampling variability? Could the authors provide confidence intervals for the performance gaps between the top-ranked graphs and demonstrate that the recommended topology offers meaningful improvements over competitive alternatives?

Q4. Transferability under stronger adaptive adversaries. The framework requires additional calibration when the question set or adversarial messages change. How robust are the predicted topology rankings when the adversary dynamically changes its target, message content, or attack strategy based on the evolving group state? Could the authors clarify whether the current adaptive-adversary evaluation adequately captures such strategic behavior, or whether the reported ranking stability primarily reflects the restricted attack protocols considered?

Q5. Scalability and calibration efficiency. The paper reports promising extrapolation results for eight- and twelve-agent groups. However, the state space of the exact Markov formulation grows exponentially with the number of agents, and larger groups may introduce local states not covered by the original calibration data. Could the authors provide a more explicit analysis of prediction accuracy, computational cost, and calibration coverage as the number of agents and their maximum degrees increase?

Q6. Applicability beyond multiple-choice deliberation. The proposed state representation relies on tracking whether agents adopt a designated adversarial answer. How would this framework extend to open-ended reasoning tasks, where agents may produce semantically equivalent but lexically different answers or progressively modify their conclusions? Is the discrete answer-state assumption essential for the reported predictive accuracy?

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

This paper investigates how the communication topology of a multi-agent LLM system influences its vulnerability to adversarial answer propagation. The authors propose a local-to-global predictive framework that estimates the probability of adversarial capture without exhaustively evaluating every graph configuration. Specifically, the method learns question-specific response kernels that characterize how an agent changes its answer based on its current state, the number and proportion of neighboring agents supporting the adversarial answer, and whether the adversary is directly connected. These local response probabilities are then integrated into a Markov-chain model to predict group-level adversarial capture across different communication topologies. The framework is evaluated using three open-weight LLMs, multiple memory protocols, and different graph structures. The authors report a mean absolute prediction error of approximately 0.012 on 52 held-out six-agent configurations after calibration on eight configurations. Additional experiments examine larger agent groups, multiple adversaries, longer interaction horizons, and changes in tasks and attack strategies. The framework is further applied to rank 112 connected six-agent graphs according to their predicted vulnerability, revealing that the safest topology depends on the underlying LLM, the adversary's placement, and the initial distribution of agents' answers. Overall, the paper's primary contribution is a computational framework for predicting topology-dependent adversarial propagation from local agent behavior, rather than relying on exhaustive graph-level simulations. Its central claim is that relatively limited calibration data can support accurate predictions of adversarial capture across previously untested communication structures.

Critical strengths
  1. Relevant and practically motivated research problem. The paper addresses an important problem in multi-agent LLM systems: understanding how communication topology affects vulnerability to adversarial influence. As LLM-based multi-agent systems become increasingly common, predicting adversarial propagation without exhaustively evaluating every possible configuration is a meaningful research objective.
  2. A systematic local-to-global modeling framework. The authors propose a structured framework that estimates local agent response probabilities and propagates them through a Markov-chain model to predict group-level adversarial capture. This provides an interpretable way to connect individual agent behavior with collective outcomes and offers an alternative to evaluating each graph configuration independently.
  3. Extensive evaluation within the considered experimental setting. The paper evaluates the framework across three LLMs, multiple memory protocols, and various graph configurations. Additional experiments consider larger groups, multiple adversaries, longer interaction horizons, and distribution shifts. The reported prediction errors are generally low, suggesting that the framework can effectively approximate adversarial capture under the evaluated conditions.
  4. Interesting observations regarding topology-dependent vulnerability. The experiments reveal that the safest communication topology depends on the underlying LLM, adversary placement, and initial answer distribution. These findings provide useful empirical insights into the relationship between network structure and adversarial propagation in multi-agent LLM systems.
Critical weaknesses
  1. Limited methodological novelty and insufficient differentiation from existing approaches.

My primary concern is the limited methodological novelty of the proposed framework. Modeling local state transitions and predicting global propagation through a Markov-chain formulation is closely related to established approaches in opinion dynamics, information diffusion, and contagion modeling. Although applying these ideas to adversarial propagation in LLM-based multi-agent systems is potentially useful, the paper does not sufficiently establish what is fundamentally new about its methodological formulation.

In particular, the authors should clarify which components represent genuine methodological advances over existing propagation models, rather than adaptations of established techniques to a new application domain. Without a stronger distinction from prior work, the contribution appears primarily incremental.

  1. Insufficient comparison with strong and recent baselines.

The experimental comparisons are not sufficiently comprehensive to establish the advantages of the proposed approach over existing methods. The main baselines include relatively simple predictors based on adversary degree and graph connectivity, while direct experimental comparisons with closely related methods from prior studies are missing.

More importantly, the paper reports that an alternative logistic response model achieves a numerically lower prediction error than the proposed kernel (0.0094 versus 0.0115). Although the authors interpret these results as comparable, they raise an important question about the necessity and advantages of the proposed estimator.

Given that the paper's central contribution is a predictive framework, comparisons against stronger and more representative methods are essential to demonstrate its methodological significance.

  1. Strong modeling assumptions and insufficient validation of their generality.

The framework relies on the assumption that agent-level transitions can be adequately characterized using a restricted set of local state variables and propagated through a Markov-chain model. However, real multi-agent LLM interactions may involve complex dependencies arising from conversation history, heterogeneous agent capabilities, semantic information, and correlated responses.

Although the proposed model demonstrates good predictive performance in the evaluated setting, the experiments do not sufficiently establish whether these simplifying assumptions remain valid in more realistic multi-agent environments. Consequently, the theoretical and empirical justification for the broader applicability of the framework remains limited.

  1. Heavy dependence on question-specific calibration.

The predictive framework relies substantially on question-specific calibration information. The paper shows that removing question-level information increases prediction error, while transferring to different tasks or adversarial strategies requires additional calibration.

This raises concerns about the practical utility and generalizability of the approach. If the framework requires repeated calibration for new tasks or attack settings, its advantages over directly evaluating candidate graph configurations become less clear. A more explicit analysis of calibration cost, computational savings, and predictive performance under genuinely unseen conditions would strengthen the contribution.

  1. Limited practical significance beyond simplified experimental settings.

Although the research question is relevant, the experimental setting is substantially simplified compared with realistic multi-agent LLM systems. The evaluation primarily considers homogeneous agents, fixed communication topologies, and multiple-choice question-answering tasks with constrained answer states.

Real-world multi-agent systems often involve heterogeneous agents, dynamically changing interactions, open-ended reasoning, and tool-mediated communication. It is therefore unclear whether the observed predictive accuracy and topology rankings would remain meaningful in these settings.

Furthermore, the paper's main findings regarding the influence of topology and adversary placement are broadly consistent with existing knowledge about network-based information propagation. The authors should more clearly articulate what fundamentally new insights are obtained and why these findings represent a significant advance beyond prior research.

Overall, while the paper addresses a relevant problem and presents a reasonably systematic empirical investigation, I am not sufficiently convinced of its methodological novelty, comparative advantages over existing approaches, or broader significance. These concerns substantially weaken the contribution despite the generally promising prediction results within the evaluated setting.

Questions for authors
  1. Methodological novelty and distinction from existing propagation models

The proposed framework estimates local state-transition probabilities and propagates them through a Markov-chain model to predict global outcomes. However, this formulation appears conceptually similar to established approaches in opinion dynamics, information diffusion, and contagion modeling.

Could the authors clarify the fundamental methodological novelty of the proposed framework compared with these existing approaches? Specifically, which components constitute new methodological contributions, rather than adaptations of established stochastic propagation models to LLM-based multi-agent systems?

  1. Direct comparison with closely related prior work

The related work discusses several studies investigating adversarial propagation and topology-dependent vulnerability in multi-agent systems, including Yu et al. (2025) and other recent approaches. However, the experimental evaluation does not appear to include direct comparisons with their methods under matched conditions.

Why were these closely related approaches not included as experimental baselines? Could the authors provide a more systematic comparison with representative existing methods, particularly those designed to characterize or predict network-level adversarial influence?

If these approaches are not directly comparable, the authors should explicitly explain the methodological or experimental differences that prevent such comparisons.

  1. Advantages over alternative response models

The paper reports that the logistic response model achieves a numerically lower prediction error than the proposed kernel (0.0094 versus 0.0115). This raises questions about the necessity of the proposed kernel estimator.

What specific advantages does the proposed kernel offer over the logistic alternative in terms of predictive accuracy, robustness, computational efficiency, interpretability, or generalization? If the two methods perform comparably, should the principal contribution be understood as the local-state representation and propagation framework rather than the kernel estimator itself?

  1. Validity of the local-state and conditional independence assumptions

The framework assumes that agent transitions can be adequately modeled using a restricted set of local variables and then combined to predict global dynamics. However, LLM agents may exhibit correlated behaviors arising from shared prompts, question difficulty, semantic context, and interaction history.

What evidence supports the sufficiency of the selected local-state variables and the conditional independence assumptions? Could the authors provide additional validation showing how violations of these assumptions affect graph-level prediction accuracy?

In particular, how would the proposed framework behave when agents have heterogeneous capabilities or when their responses depend on richer conversational context?

  1. Generalization to unseen questions, tasks, and attack strategies

The proposed approach relies on question-specific calibration, and the paper reports increased prediction errors when question-level information is removed. Additional calibration is also required when transferring to different tasks or adversarial strategies.

To what extent can the framework predict adversarial capture for genuinely unseen questions without collecting question-specific transition observations? Could the authors clarify whether the method is intended primarily for predicting unseen graph configurations on previously calibrated questions, rather than generalizing to unseen questions or attack distributions?

This distinction seems important for understanding the scope of the paper's main claim.

  1. Practical significance and calibration efficiency

A central motivation of the paper is to avoid exhaustive evaluation of graph configurations. However, the proposed framework still requires calibration experiments, and its accuracy depends on the coverage of relevant local states.

Could the authors quantify the total computational cost of calibration, kernel estimation, and graph-level prediction relative to directly evaluating candidate graph configurations?

Furthermore, under what conditions does the proposed approach provide a substantial practical advantage over simpler predictors or direct empirical evaluation? A clearer cost–accuracy trade-off would help establish the practical significance of the framework.

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

This paper models adversarial answer propagation in multi-agent LLM deliberation using question-specific local switching probabilities and a Markov approximation. It predicts capture rates on unseen graph configurations and uses the model to rank communication topologies under different initial conditions and adversarial placements.

Critical strengths
  • The paper provides extensive experiments, ablations, and uncertainty analyses, with accurate predictions on held-out graph configurations.
  • The systematic comparison of graph structures reveals interesting trade-offs between adversarial capture, final accuracy, and adversary placement.
Critical weaknesses
  • Prior studies such as NetSafe and Conformity Dynamics have examined topology-dependent adversarial propagation, while Physics of Agents already models collective LLM behavior through local stochastic update rules and generalizes to unseen graphs. Although these works are all cited in this paper, the proposed Markov approximation appears incremental, and the authors did not sufficiently justify the distinct contribution over these works.
  • The strongest predictions are obtained on held-out graphs using the same questions and attack protocol. Cross-task rankings are largely validated against another fitted kernel rather than comprehensive empirical measurements.
Questions for authors
  • Beyond predicting capture rates accurately, what new understanding of LLM-specific adversarial influence does the proposed framework provide that cannot already be explained by existing stochastic opinion-dynamics models? What is the methodological advance over Physics of Agents and other prior works?
  • Can the authors validate topology rankings more directly on unseen tasks and isolate the effect of initial-answer distributions while keeping question-specific switching dynamics fixed?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.