PaperlayerView exact revision on arXiv

Source-linked AI summary

Network topology shapes consensus and vulnerability in LLM populations

Roberto Passaro, Ariel Flint, Romualdo Pastor-Satorras, Andrea Baronchelli, Luca Maria Aiello

arXiv:2610.31165v1physics.soc-phcs.AIcs.CY

TL;DR

The paper asks how network topology shapes convention formation and robustness to committed minorities in LLM populations. It simulates naming games with policies from four LLMs on fully connected, random-regular, and heterogeneous networks. Topology affects consensus speed and sometimes whether consensus emerges, while tipping thresholds are lowest at hubs and highest at low-degree nodes.

  • Problem

    The paper asks how network topology shapes convention formation and robustness to committed minorities in LLM populations.

    Source: §1 · p. 2

  • Method

    Policies from four LLMs play naming games on fully connected, random-regular, and heterogeneous networks; annealed rewiring tests the role of persistent-neighbour correlations.

    Source: §1 · p. 2, §2.1 · p. 3, §2.2 · p. 4

  • Results

    Consensus is generally faster on denser topologies, persistent-neighbour correlations can rescue convergence, and tipping thresholds follow hubs ≤ random ≤ low-degree nodes.

    Source: §4 · p. 13

  • Takeaways & Limitations

    In most settings, networked populations are easier to overturn than well-mixed populations, so well-mixed estimates can overstate robustness.

    Source: §4 · p. 13

    Results are model-dependent and come from a simplified naming game with memory fixed at H = 5 and two competing conventions.

    Source: §4 · p. 13

Abstract

from arXiv · show

As large language models (LLMs) are deployed in interacting populations, their collective behaviour depends not only on the models but also on who interacts with whom. Studies of convention formation in LLM populations have mainly tested well-mixed interactions. We place policies extracted from four LLMs on fully connected, random regular, and heterogeneous networks, with $10^3$ to $10^5$ agents playing the naming game. Topology affects how quickly consensus emerges, sometimes whether it emerges at all, and, in rare cases, which convention wins. Sparsest networks slow consensus up to twelvefold. Yet, by preserving correlations between persistent neighbours, they restore consensus in some cases that fail to converge under well-mixed interactions. Networks also govern vulnerability to adversarial attack. We measure the critical mass of committed agents needed to overturn an established convention. Tipping thresholds follow the same ordering across models and conditions: hubs $\leq$ random $\leq$ low-degree nodes. On the most heterogeneous topology, median critical masses are 3%, 16%, and 35%, respectively; targeting hubs requires one-sixth as many committed agents as random placement. For most models, networked populations are easier to tip than well-mixed ones, so well-mixed estimates can overstate robustness. Assessing the safety of multi-agent AI requires mapping who interacts with whom.

1 Introduction

Prior work on LLM convention formation largely assumes well-mixed interactions, although deployed populations have structured communication; this study tests how topology shapes consensus and vulnerability to committed minorities.

1 Introduction

  • Naming-game studies show that conventions can emerge through repeated local interactions, while committed minorities can overturn them above a critical fraction.Earlier AI studies found that this critical fraction varies with the underlying LLM.Source: §1 · p. 2
  • Prior LLM coordination studies assume well-mixed populations, while networked naming-game evidence is limited and networked critical mass had not been measured.The prior networked study involved groups of 16 agents.Source: §1 · p. 2
  • Across four LLM-derived policies, topology changes consensus speed and sometimes which convention wins or whether consensus emerges, with persistent-neighbour correlations restoring convergence in a case that fails when well mixed.The study places policies from four LLMs on fully connected, random regular, and heterogeneous networks.Source: §1 · p. 2
  • Across tested conditions, committed minorities need the fewest agents at hubs and the most at low-degree nodes to overturn an established convention.Hubs also reach a given level of coordination earlier than low-degree nodes.Source: §1 · p. 3

2 Methods

The methods combine a minimal naming game using policies extracted from four LLMs with network and placement comparisons. They measure consensus, degree-resolved coordination, and the committed fraction needed to overturn a convention.

2.1 Naming game and agent model

  • Agents play a two-convention naming game using five-interaction memory and extracted stochastic policies from four instruction-tuned LLMs; consensus requires rolling coordination success above 0.98.A word pair that fails to cross this threshold within 100,000 population rounds is classified as a mixed-state pair.Source: §2.1 · p. 3

2.2 Networks and parameters

  • Populations of 1,000–100,000 occupy fully connected, two power-law UCM, or random-regular networks; annealed rewiring controls for persistent-neighbour correlations.Each condition is simulated 1,000 times at population sizes up to 10,000 and 300 times at 100,000.Source: §2.2 · pp. 3–4

2.3 Degree-resolved success on UCM

  • Degree-resolved coordination tracks cumulative success by degree bin on UCM2.5 at N = 10,000, using crossings at success levels 0.6, 0.7, and 0.8 to summarize hub-versus-low-degree timing.Five degree bins are used, with the lowest designated low-degree nodes and the highest designated hubs.Source: §2.3 · pp. 4–5

2.4 Committed minorities

  • To measure robustness, committed agents always promote one convention while the rest begin in consensus on the alternative; the critical fraction is the smallest fraction with flip probability at least 0.5.On UCM networks, committed agents are placed at hubs, at low-degree nodes, or randomly.Source: §2.4 · p. 5

3 Results

Across four LLMs, network topology changes consensus speed, can rescue some mixed states, and sometimes changes which convention wins. It also shapes how readily committed minorities overturn conventions, with placement and topology affecting critical thresholds.

3.1 Consensus dynamics across topologies

  • Topology changes which convention wins in two GPT word pairs, while the other 40 consensus-reaching model–pair combinations retain the same most frequent winner across conditions.For {she/he} and {tall/short}, reversals grow with population size; node activation yields the same pattern.Source: §3.1 · p. 5

3.1.1 Speed of consensus

  • For QwQ, GPT, and Phi, consensus speed ranks FC < UCM2.5 < UCM5.0 < RRN; Llama departs from this pattern for eight pairs.On RRN, QwQ pairs are 1.3–12.2 times slower than FC at K = 4, but none is more than 1.05 times slower at K = 256.Source: §3.1.1 · pp. 6–7, Figure 1 · p. 6

3.1.2 Degree-resolved success on UCM

  • Across conditions, normalised tilt has median 0.16 and is below 0.5 in 113 of 115 cases, while hubs reach a given success level first in 109 of 115.At S = 0.6, low-degree nodes can sometimes agree with a few neighbours before hubs settle amid conflicting conventions; hubs have taken part in about 8.4 times as many interactions at median τ = 0.16.Source: §3.1.2 · pp. 7–9
  • Removing persistent neighbourhoods makes consensus 14% faster overall across conditions, with a 45% drop for the ten slowest conditions.The annealed network delays low-degree success at S = 0.6 more than hub success, consistent with persistent neighbours supporting early local agreement while delaying global consensus.Source: §3.1.2 · p. 9

3.1.3 Topology effect on mixed-state pairs

  • For Llama, network structure rescues the mixed {young/old} pair on UCM5.0 and RRN, while {more/less} is rescued only by RRN at N = 1,000 among tested sizes.For {young/old}, median convergence time on UCM5.0 rises from 108 to 267 rounds between N = 1,000 and 100,000, versus 64 to 79 on RRN. Annealed UCM5.0 and RRN controls fail to rescue either mixed pair; consensus fraction is 0.00 at N = 1,000, 5,000, 10,000, and 100,000 (300 runs per condition).Source: §3.1.3 · pp. 9–10

3.2.1 Degree-dependent placement on UCM

  • The critical-fraction ordering is p*(hub) ≤ p*(random) ≤ p*(low-degree nodes) in every tested condition on both UCM exponents.In 15 conditions p* = 0 because the established consensus does not hold without committed agents; seven conditions require p* = 1.00, all under low-degree placement.Source: §3.2.1 · pp. 10–11

3.2.2 Topology effects on the critical mass

  • Under random placement, topology effects on critical fraction follow the predicted ordering for three models in the weak direction and two in the strong direction, with stated exceptions.The predicted ordering is reversed for Llama in the strong direction, absent for QwQ in the strong direction, and not significant for Llama in the weak direction.Source: §3.2.2 · p. 11, Table 4 · p. 11

4 Discussion

The study tests how network structure affects convention formation and committed-minority attacks in populations of LLM agents. It finds topology-dependent consensus and tipping behavior, with limits tied to the model and simplified naming-game setting.

4 Discussion

  • The study embeds LLM-agent policies in networks to measure convention convergence and resistance to committed minorities.It identifies interaction structure as a factor in collective outcomes relevant to multi-agent-system safety; well-mixed estimates can overstate robustness in most settings tested.Source: §4 · pp. 11, 13
  • Across tested conditions, the critical committed fraction is lowest for hubs and highest for low-degree nodes.On UCM2.5, Figure 3 plots placement and topology results at N = 10,000; its zero-threshold cases are excluded.Source: Figure 3 · p. 12, §4 · p. 13
  • For most word pairs, denser topologies reach consensus faster, ordered FC < UCM2.5 < UCM5.0 < RRN.Hubs reach a given success level slightly earlier; persistent neighbourhoods can stabilize local agreements while slowing global convergence.Source: §4 · p. 13
  • Topology sometimes changes the winning convention or restores consensus for a pair that fails in well-mixed populations.Rescue disappears when neighbours are reshuffled, indicating that correlations between persistent neighbours are necessary for it.Source: §4 · p. 13
  • Results are model-dependent and use a simplified naming game with H = 5 and W = 2.The authors call for more models and richer, more ecological interaction scenarios.Source: §4 · p. 13

A1.1 Mean-field naming game for LLMs

The mean-field model represents LLM agents by bounded histories and probabilistic word-selection policies. Interactions update both agents’ histories, and success or failure changes their scores.

A1.1 Mean-field naming game for LLMs

  • An agent’s state records the words it proposed and received, up to maximum memory length H.The state is empty before the first interaction; its length h is at most H.Source: A1.1 Mean-field naming game for LLMs · p. 19
  • The policy q(S) gives the probability that an agent in state S outputs word 0; it outputs word 1 with probability 1 − q(S).The policy depends on the agent’s own state, irrespective of the other agent’s state.Source: A1.1 Mean-field naming game for LLMs · p. 19
  • In the well-mixed dynamics, two agents are randomly selected, exchange proposed and received words, and update their histories with that pair.The transition kernel assigns probabilities to the possible state transitions using each agent’s policy.Source: A1.1 Mean-field naming game for LLMs · p. 19
  • At mean-field level, the system state is the normalized fraction of agents in each possible state, with transitions governed by a rate equation.The interaction kernel is expressed through the policies and possible transitions; a factor of 2 is retained to match the networked model’s time scale.Source: A1.1 Mean-field naming game for LLMs · pp. 19–20

A1.2 The naming game in complex networks

The network model places agents on nodes connected by edges and specifies two ways to select interacting pairs. The policies are assumed not to change with network structure.

A1.2 The naming game in complex networks

  • A network is represented by an adjacency matrix, and a node’s degree counts its directly connected neighbours.The population consists of N agents placed on the network’s nodes.Source: A1.2 The naming game in complex networks · p. 20
  • In symmetric node update, a random node and one of its random neighbours interact, and both nodes update.Each node is selected first with equal probability under this rule.Source: A1.2 The naming game in complex networks · p. 20
  • In edge update, a random edge is selected and both endpoint nodes interact and update.The model assumes network structure does not affect the probability policies; updates depend on the interacting agents’ states.Source: A1.2 The naming game in complex networks · p. 20

A1.3 Quenched mean-field theory

The quenched mean-field formulation tracks each node’s probabilities of occupying the possible agent states. It approximates node states as independent, while topology enters through the interaction-selection probabilities.

A1.3 Quenched mean-field theory

  • Quenched mean-field theory represents each node’s state as probabilities over the M possible states, normalized to sum to one.Each node’s state is a point in an M-dimensional simplex.Source: A1.3 Quenched mean-field theory · p. 20
  • The approximation treats the states of neighbouring nodes as independent, although interactions create dynamical correlations between them.The text notes that pair approximation can incorporate higher-order dynamical correlations.Source: A1.3 Quenched mean-field theory · p. 20
  • Topology enters the mean-field equations through the probabilities of selecting each node pair for interaction.The state-transition kernel itself is independent of network structure.Source: A1.3 Quenched mean-field theory · p. 21

A1.3.1 Symmetric node update

The symmetric node-update rule selects a node uniformly, then selects one of its neighbors according to the node’s degree-normalized adjacency weights.

A1.3.1 Symmetric node update

  • Each step selects node n with probability 1/N, then neighbor m with probability A_nm/k_n.Combining these selection probabilities with Eq. (A9)'s gain-loss structure yields the mean-field equations for symmetric node update.Source: A1.3.1 Symmetric node update · p. 21
  • Absorbing a factor of 1/N into a time rescaling gives the stated mean-field equations for symmetric node update.The rescaling changes the time unit used to write the equations.Source: A1.3.1 Symmetric node update · p. 21

A1.3.2 Symmetric edge update

The symmetric edge-update rule selects an edge uniformly from the network, then derives mean-field equations from the gain-loss structure.

A1.3.2 Symmetric edge update

  • Each step selects edge (n, m) with probability A_nm/E, where E is the total number of edges.The gain-loss structure in Eq. (A9) yields the mean-field equations for symmetric edge update.Source: A1.3.2 Symmetric edge update · p. 21
  • Using E = N⟨k⟩/2 and absorbing a factor of 1/N into the time rescaling gives the stated equations.This is the mean-field formulation for symmetric edge update.Source: A1.3.2 Symmetric edge update · p. 21

A1.4 Annealed network approximation

The appendix describes annealed-network and random-regular-network approximations, then catalogs additional tests and figures on consensus speed, success by degree, and committed minorities.

A1.4 Annealed network approximation

  • The annealed approximation replaces adjacency entries with expected connection probabilities; for uncorrelated configuration-model networks, the sparse-limit replacement is specified.The approximation assumes edges rewire much faster than node dynamics, removing dynamical correlations between neighboring states; quenched networks can deviate.Source: A1.4 Annealed network approximation · pp. 21–22

A1.5 Random regular networks

  • For random regular networks, QMF equations for symmetric node and edge updates are identical.The annealed approximation instead predicts dynamics independent of degree K, and identical to fully connected dynamics for any K.Source: A1.5 Random regular networks · pp. 22–23

A2.1 Statistical tests for speed of consensus across topologies

A2.3 Speed of consensus on increasing values of K for RRN

  • Figure A1 presents mean convergence time under edge activation at N = 10000; Figure A3 compares mean times across population sizes for two mixed-state Llama pairs.Figure A3 includes FC, UCM2.5, UCM5.0, and RRN with K = 4; curves stop where not all runs reach consensus within the horizon.Source: Figure A1 · p. 25, Figure A3 · p. 28

A2.2 Statistical tests for speed of consensus on increasing values of K for RRN

  • Figure A2 plots RRN convergence-time mode divided by the fully connected baseline across degrees K; ratios above 1 indicate slower convergence.Table A2 tests the RRN degree sweep against the fully connected baseline at N = 10000.Source: Table A2 · p. 26, Figure A2 · p. 27

A2.5 Convergence time on RRN at increasing K for the mixed-state Llama pairs

  • For two mixed-state Llama pairs, Figure A4 compares quenched and annealed RRN convergence times across K at N = 100 and 200.Table A3 reports median convergence times and consensus fractions, while Table A4 defines degree-sweep quantities including K50, K90, and KFC.Source: Figure A4 · p. 29, Table A3 · p. 30, Table A4 · p. 30

A2.6 Iso-success contours for Llama, QwQ and Phi

  • Figures A5–A7 show exposure and success by degree on UCM2.5 for Llama-3.1-70B, QwQ-32B, and Phi-4, with quenched tilt levels marked.Table A5 identifies six conditions where hubs reach success level S = 0.6 later than low-degree nodes on quenched UCM2.5.Source: Figure A5 · p. 31, Table A5 · p. 31, Figure A6 · p. 32

A2.7 Statistical tests for committed minorities

  • Tables A6–A8 cover tests of committed-minority placement and topology orderings, plus critical fractions for three QwQ pairs requiring near-complete minorities.Table A6 tests hub < random < low-degree placement; Table A7 tests RRN < UCM5.0 < UCM2.5 < FC under random placement.Source: Table A6 · p. 34, Table A7 · p. 34, Table A8 · p. 35
Loading 2610.31165v1…