Paper deep dive
Cayley Graph Optimization for Scalable Multi-Agent Communication Topologies
Jingkai Luo, Yulin Shao
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 4/14/2026, 1:37:20 AM
Summary
The paper introduces CayleyTopo, a framework for optimizing multi-agent communication topologies using circulant Cayley graphs. By treating the generator set as a design variable and employing a reinforcement learning approach with number-theoretic priors and message-propagation feedback, the authors achieve topologies that outperform hand-crafted rules like ExpoComm in diameter, resilience, and communication efficiency.
Entities (5)
Relation Signals (3)
CayleyTopo → outperforms → ExpoComm
confidence 95% · the resulting CayleyTopo consistently outperforms existing hand-crafted topologies
Reinforcement Learning → optimizes → CayleyTopo
confidence 94% · we develop a lightweight reinforcement learning framework that injects a number-theoretic prior to favor structurally rich generators
CayleyTopo → approaches → Moore bound
confidence 92% · discovered topologies approach the theoretical Moore lower bound
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Large-scale multi-agent communication has long faced a scalability bottleneck: fully connected networks require quadratic complexity, yet existing sparse topologies rely on hand-crafted rules. This paper treats the communication graph itself as a design variable and proposes CayleyTopo, a family of circulant Cayley graphs whose generator sets are optimized to minimize diameter, directly targeting worst-case information propagation speed. To navigate the enormous search space of possible generator sets, we develop a lightweight reinforcement learning framework that injects a number-theoretic prior to favor structurally rich generators, alongside a message-propagation score that provides dense connectivity feedback during construction. The resulting CayleyTopo consistently outperforms existing hand-crafted topologies, achieving faster information dissemination, greater resilience to link failures, and lower communication load, all while approaching the theoretical Moore bound. Our study opens the door to scalable, robust, and efficient communication foundations for future multi-agent systems, where the graph itself becomes optimizable rather than a fixed constraint.
Tags
Links
- Source: https://arxiv.org/abs/2604.09703v1
- Canonical: https://arxiv.org/abs/2604.09703v1
Trouble viewing inline? Open PDF directly →
Full Text
34,926 characters extracted from source content.
Expand or collapse full text
Cayley Graph Optimization for Scalable Multi-Agent Communication Topologies Jingkai Luo and Yulin Shao The authors are with the Department of Electrical and Computer Engineering, The University of Hong Kong, Hong Kong, China (e-mails: lo563456@gmail.com, ylshao@hku.hk). Abstract Large-scale multi-agent communication has long faced a scalability bottleneck: fully connected networks require quadratic complexity, yet existing sparse topologies rely on hand-crafted rules. This paper treats the communication graph itself as a design variable and proposes CayleyTopo, a family of circulant Cayley graphs whose generator sets are optimized to minimize diameter, directly targeting worst-case information propagation speed. To navigate the enormous search space of possible generator sets, we develop a lightweight reinforcement learning framework that injects a number-theoretic prior to favor structurally rich generators, alongside a message-propagation score that provides dense connectivity feedback during construction. The resulting CayleyTopo consistently outperforms existing hand-crafted topologies, achieving faster information dissemination, greater resilience to link failures, and lower communication load, all while approaching the theoretical Moore bound. Our study opens the door to scalable, robust, and efficient communication foundations for future multi-agent systems, where the graph itself becomes optimizable rather than a fixed constraint. I Introduction Imagine a swarm of thousands of autonomous drones performing a coordinated search-and-rescue mission, or a fleet of connected vehicles navigating dense urban traffic. In such large-scale multi-agent systems, the ability to share information quickly and reliably is the bedrock of coordinated behavior [1, 12]. Yet, as the number of agents N grows, the communication protocol that binds them faces a daunting challenge. A fully connected network, where every agent talks to every other, becomes an impossibility: its (N2)O(N^2) overhead would drown the system in congestion and scheduling conflicts. The central question is therefore how to design a sparse communication topology [9, 7, 13, 2] that remains scalable, fast, and robust under realistic constraints. The importance of communication structure has been recognized across multiple domains. In networked control theory, the connectivity of the graph directly influences the convergence rate of consensus [9]. In multi-agent reinforcement learning, differentiable communication schemes like CommNet [14] and DIAL/RIAL [3] enable agents to share information, and subsequent work has explored attentional or targeted communication [2, 6]. However, these methods primarily optimize message content and routing policies under a fixed or weakly constrained interaction pattern. The structure of the communication graph itself, i.e., which links exist, is rarely treated as a first-class design variable, especially under realistic degree constraints that reflect resource and hardware limits. A recent advance made by Li et al. [7] showed what is possible when structure is deliberately engineered. Their exponential topology-enabled scalable communication protocol (ExpoComm) employs a deterministic exponential graph, connecting each agent to peers at distances 202^0, 212^1, …. This rule-based topology achieves a logarithmic diameter ⌈log2(N−1)⌉ _2(N\!-\!1) , and demonstrates strong scalability and zero-shot transferability on large benchmarks. ExpoComm is a powerful example of how a fixed, hand-crafted topology can break the scaling bottleneck. Yet, it highlights a deeper opportunity: is the exponential rule itself optimal? This question motivates us to shift the perspective: instead of relying on hand-crafted rules, we treat the communication topology as an optimization variable. Specifically, we model the network as a circulant Cayley graph [4], a family that generalizes the exponential construction and is parameterized by a set of generator steps. The design problem then becomes a discrete combinatorial optimization: find the generator set of limited size (i.e., respecting a degree budget) that minimizes the graph diameter, which directly governs worst-case information propagation speed. Solving this optimization is non-trivial, as the search space of possible generator sets is enormous, and evaluating each candidate requires costly graph distance computations. To navigate this complexity, we develop a lightweight reinforcement learning (RL) framework tailored for topology selection. Our framework incorporates two key ideas: (1) a prior based on multiplicative order, which biases the search toward number-theoretically rich generators known to enhance connectivity; and (2) a message-propagation procedure that provides structural feedback during topology construction. In summary, this paper makes the following contributions: • We formulate multi-agent communication topology design as a discrete optimization over circulant Cayley graphs, directly targeting diameter minimization under degree constraints. The resulting family of topologies, CayleyTopo, achieves superior connectivity and propagation speed compared to existing hand-crafted constructions. • To address the challenging combinatorial optimization, We develop a lightweight RL framework that integrates number-theoretic priors and a dense, propagation-based connectivity score. This enables efficient discovery of high-quality generator sets that respect the degree budget. • Through comprehensive experiments, we demonstrate that CayleyTopo consistently outperforms rule-based baselines (ExpoComm, Fibonacci, primes) across multiple metrics: information dissemination latency, link-failure robustness, and communication load. Furthermore, our discovered topologies approach the theoretical Moore lower bound. I System Model We consider a multi-agent system consisting of N agents, indexed by 0,1,…,N−10,1,…,N-1. Communication occurs in discrete time steps. At each step, every agent may send messages to a subset of other agents, and the set of active communication links defines a graph. In this work, we focus on undirected graphs, meaning that if agent i can send to agent j, then j can also send to i. I-A Communication Process and Key Metrics The communication structure is described by an undirected graph =(,ℰ)G=(V,E), where =0,…,N−1V=\0,…,N-1\ and an edge (i,j)∈ℰ(i,j) indicates that agents i and j can exchange messages directly in a single time step. Messages can be relayed over multiple hops: if i and j are not directly connected, information can travel along a path i=v0i=v_0, v1v_1, …, vk=jv_k=j where each consecutive pair is an edge. The number of hops needed to propagate a message from i to j is the length of the shortest such path, denoted d(i,j)d(i,j). Two fundamental metrics characterize the quality of a communication topology. Definition 1 (Diameter). The diameter of G is the maximum shortest-path distance between any two agents: D()=maxu,v∈d(u,v).D(G)= _u,v d(u,v). (1) The diameter represents the worst-case number of time steps required for a message to propagate from any agent to any other, assuming each step uses one-hop transmissions. Definition 2 (Degree). For an undirected graph, the degree of agent i is the number of its direct neighbors: deg(i)=|j:(i,j)∈ℰ|.deg(i)=|\j:(i,j) \|. (2) The total number of edges |ℰ||E| reflects the overall communication overhead. In practice, each agent has limited resources (e.g., bandwidth, power, or hardware constraints), which impose an upper bound on its degree. We denote this maximum allowed degree by dmaxd_ , so the graph must satisfy deg(i)≤dmax (i)≤ d_ for all i. The goal of topology design is to construct a graph with small diameter (for fast information propagation) while respecting a given degree budget dmaxd_ . I-B Exponential Graphs To make the above concepts concrete, we revisit the ExpoComm protocol proposed by Li et al. [7], which leverages exponential graphs as the underlying communication topology to achieve both scalability and low diameter. Exponential graphs are defined on the cyclic ordering of agents, as shown in Fig. 1, and follow a deterministic rule: each agent i connects to agents at distances that are powers of two, i.e., i±20,i±21,…,i±2⌈log2(N−1)⌉(modN).i± 2^0,i± 2^1,…,i± 2 _2(N-1) ~(mod~N). (3) This yields a regular graph where • Every agent has degree 2⌈log2(N−1)⌉2 _2(N-1) (or ⌈log2(N−1)⌉ _2(N-1) if only outgoing edges are counted in a directed interpretation). • Its diameter is ⌈log2(N−1)⌉ _2(N-1) : any integer distance d between 0 and N−1N-1 can be written as a sum of distinct powers of two (its binary representation). A message can therefore reach an agent at distance d by taking jumps corresponding to the bits of d, using at most ⌈log2(N−1)⌉ _2(N-1) hops. Figure 1: Illustration of the exponential graph for N=8N=8 agents. Each agent connects to others at distances that are powers of two, resulting in a regular topology with diameter ⌈log2(N−1)⌉=3 _2(N-1) =3. The exponential graph family thus demonstrates that a carefully chosen communication topology can achieve a logarithmic diameter with degree (or per-step edge count) that grows only logarithmically in N, making it highly scalable. I-C Generalizing the Topology Design Problem In the exponential graph, each agent i connects to agents at offsets that are powers of two. Critically, the connection pattern is identical for every agent: the neighborhood of any agent looks the same up to a cyclic shift of indices. This property, known as vertex-transitivity, is not unique to the exponential construction. It suggests that we can capture a broad family of structured topologies using Cayley graphs on the cyclic group. Definition 3 (Cayley graph on ℤNZ_N). Let ℤN=0,1,…,N−1Z_N=\0, 1, …, N-1\ denote the additive group of integers modulo N. A Cayley graph on this group is defined by a set S⊂ℤN∖0S _N 0, called the generator set. The resulting graph Cay(ℤN,S)Cay(Z_N,S) has vertex set ℤNZ_N, and for every vertex u and every generator s∈Ss∈ S, there is a directed edge from u to u+su+s (mod N). To obtain an undirected graph as in our multi-agent setting, we impose that S is symmetric: if s∈Ss∈ S then its additive inverse −s-s (mod N) must also be in S. In that case, each generator s contributes two undirected edges per vertex: one to u+su+s and one to u−su-s. To avoid redundancy, we often describe the graph using a set of positive generators S+⊂1,…,N−1S^+⊂\1,…,N-1\ and then set S=S+∪(−S+)S=S^+∪(-S^+). The degree of every vertex is then |S|=2|S+||S|=2|S^+|. Each positive generator s∈S+s∈ S^+ acts as a fixed step size: every agent i can communicate directly with agents i+si+s and i−si-s (mod N). The entire graph is built by applying these steps from every vertex. The exponential graph from ExpoComm is a special case of this construction. Its positive generator set is precisely the powers of two: Sexp+=20,21,…,2⌈log2(N−1)⌉S^+_exp=\2^0,2^1,…,2 _2(N-1) \. Instead of fixing S+S^+ to the standard ExpoComm (powers-of-two) generator set, this paper treats it as a design variable. The goal is to select a set of positive generators, subject to a degree budget, that yields a graph with favorable communication properties. Since the graph is vertex-transitive, its global characteristics, such as the worst-case number of hops needed for a message to travel between any two agents, are determined solely by the generator set. Specifically, we denote by D(S+)D(S^+) the diameter of Cay(ℤN,S)Cay(Z_N,S). For a given degree budget dmaxd_ (the maximum number of neighbors each agent can support), the undirected degree of each vertex is 2|S+|2|S^+|, so we must satisfy 2|S+|≤dmax2|S^+|≤ d_ , i.e., |S+|≤⌊dmax/2⌋|S^+|≤ d_ /2 . Let K≜⌊dmax/2⌋K d_ /2 denote the maximum number of positive generators. Our core optimization problem then becomes: minS+⊂D(S+),s.t.|S+|≤K, _S^+ D(S^+), .t. |S^+|≤ K, (4) where C is a candidate pool of positive integers. To ensure the graph is connected, the set S+S^+ must be able to generate the whole group ℤNZ_N, which holds if and only if the greatest common divisor (gcd) of all elements in S and N is 11. A convenient sufficient condition is to restrict all generators to be coprime to N; then any non-empty subset automatically satisfies this gcd condition. Thus, we restrict C to numbers that are coprime to N (e.g., all such numbers, or a subset like primes less than N). Remark 1. The diameter D(S+)D(S^+) serves as the primary objective, as it directly captures worst-case information dissemination latency. In practice, when two different generator sets yield the same diameter, we may compare them using the average shortest-path length L(S+)=1N(N−1)∑u≠vdS+(u,v),L(S^+)= 1N(N-1) _u≠ vd_S^+(u,v), (5) where dS+(u,v)d_S^+(u,v) is the distance in the corresponding Cayley graph. L(S+)L(S^+) is useful as a tie-breaker when observed diameters are small and many candidates achieve the same D(S+)D(S^+). By treating topology design as a discrete optimization over generator sets, we open the door to systematically searching for structures that go beyond fixed designs such as ExpoComm. However, the search space of possible generator sets is enormous: the number of subsets of C grows combinatorially, making exhaustive enumeration infeasible. Moreover, evaluating D(S+)D(S^+) requires computing all-pairs shortest paths (or at least distances from a single source due to vertex-transitivity), which becomes expensive as N scales. Therefore, an efficient optimization method is required. I Topology Optimization via RL with Number-Theoretic Priors In this section, we present a RL framework that integrates number-theoretic priors and a structural connectivity score to discover near-optimal Cayley graph topologies under a degree budget. I-A Theoretical Baseline and The Multiplicative Order Before searching for optimal topologies, it is useful to understand the fundamental limits of what a graph can achieve. For a regular graph where every vertex has degree Δ , the number of vertices reachable within D hops is bounded below. Theorem 1 (Moore bound [8]). For a Δ -regular graph with diameter D, the total number of vertices N cannot exceed N≤1+Δ∑h=0D−1(Δ−1)h.N≤ 1+ _h=0^D-1( -1)^h. (6) This bound arises from a breadth-first expansion argument: starting from a single vertex, at most Δ new vertices can be reached in the first step, and at most (Δ−1)( -1) new vertices from each subsequent step, as one neighbor is already accounted for. For a given N and degree Δ , this inequality provides a lower bound on the achievable diameter D. In our context, Δ=2K =2K, the undirected degree of the circulant graph. The Moore bound serves as a theoretical reference: no topology can have a diameter smaller than the smallest D satisfying (6). We will use this bound to gauge how close our discovered topologies come to the theoretical optimum. The search space for generator sets is enormous, but not all generators are equally promising. A classical concept from number theory offers a powerful heuristic for identifying generators that promote good connectivity. Definition 4 (Multiplicative order [5]). For an integer a coprime to N, the multiplicative order of a modulo N, denoted ordN(a)ord_N(a), is the smallest positive integer k such that ak≡1(modN)a^k≡ 1 N. This quantity is directly tied to the structure of the multiplicative group ℤN×Z_N^×. A generator a with a large multiplicative order generates a large cyclic subgroup of ℤN×Z_N^×. The residues a0,a1,…,ak−1a^0,a^1,…,a^k-1 are therefore spread relatively uniformly across the set of numbers coprime to N. When these residues are used as additive step sizes in a circulant graph, they tend to cover the additive group ℤNZ_N more evenly, which can lead to smaller diameters and average path lengths. While this relationship is heuristic for composite N, empirical evidence and insights from additive number theory [15] suggest that high-order generators are strong candidates for constructing low-diameter graphs. To incorporate this prior into our optimization, we precompute for each candidate generator p∈p its normalized multiplicative order: ω(p)=ordN(p)maxq∈ordN(q).ω(p)= ord_N(p) _q ord_N(q). (7) This normalization maps the order to the interval [0,1][0,1], allowing us to use it as a scalar feature and a bias term in our RL agent. The prior effectively guides the search toward generators that are number-theoretically rich, reducing the need to explore less promising candidates. I-B RL for Generator Selection We now transform the topology design problem as a sequential decision process. The goal is to construct a generator set S+S^+ of size K by selecting K generators from the candidate pool C without replacement. This process is naturally modeled as an RL episode with K steps. I-B1 State and action spaces At step t, where t=1,…,Kt=1,…,K, the state encodes the history of selections and the current progress. It consists of: • The set of already selected generators ℐselt−1I_sel^t-1, which implicitly defines the partial positive generator set St−1+S^+_t-1. • A normalized step index t/Kt/K, indicating how many selections remain. • For each candidate generator pi∈p_i , its normalized multiplicative order ω(pi)ω(p_i) and its index i/||i/|C| (a positional feature). The action space is the set of candidates not yet selected. The policy π(at∣state)π(a_t ) is a probability distribution over these available actions. I-B2 Policy network We use a lightweight multilayer perceptron (MLP) to parameterize the policy. For each candidate pip_i, the input feature vector is t,i=[ω(pi),i/||,t/K]⊤ x_t,i= [ω(p_i),i/|C|,t/K ] . These features are passed through a two-layer MLP: st,i=2tanh(1t,i+1)+2+η⋅ω(pi),s_t,i= W_2 ( W_1 x_t,i+ b_1)+ b_2+η·ω(p_i), (8) where 1 W_1, 2 W_2, 1 b_1, 2 b_2 are learnable parameters of the MLP; η is a bias coefficient that amplifies the influence of the multiplicative order prior. The logits are then masked to exclude already chosen generators, and a softmax yields the policy πt(i)=exp(st,i)⋅i∉ℐsel∑j∉ℐselexp(st,j). _t(i)= (s_t,i)·I_\i _sel\ _j _sel (s_t,j). (9) Note that the order prior is injected both implicitly via input features and explicitly via the additive logit bias term η⋅ω(pi)η·ω(p_i), improving exploration stability in early training. I-B3 Reward The ultimate objective is to minimize the diameter D(SK+)D(S^+_K). However, providing this as a sparse reward only at the end of the episode makes learning difficult. We therefore augment it with a dense, step-wise reward signal that reflects the quality of the partial topology. This signal has two components. First, we track the average normalized multiplicative order of the selected generators: ωt=1t∑j=1tω(paj). _t= 1t _j=1^tω(p_a_j). (10) Second, we compute a structural score g(St+)g(S^+_t) based on a message-propagation procedure, which will be detailed in the next subsection. This score provides immediate feedback on how well information can spread through the partial graph. The step-wise shaped reward is then defined as the incremental improvement in these metrics: rtshape=λ(ωt−ωt−1)+λg(g(St+)−g(St−1+)),r_t^shape=λ( _t- _t-1)+ _g(g(S^+_t)-g(S^+_t-1)), (11) with ω0=g(S0+)=0 _0=g(S^+_0)=0. At the final step t=Kt=K, we compute the exact diameter D(SK+)D(S^+_K) (via breadth-first search from vertex 0, exploiting vertex-transitivity) and incorporate it into the reward: rK=rKshape−D(SK+).r_K=r_K^shape-D(S^+_K). (12) The total return for an episode is therefore R=∑t=1Krt=−D(SK+)+λωK+λgg(SK+).R= _t=1^Kr_t=-D(S^+_K)+λ _K+ _gg(S^+_K). (13) This formulation allows the agent to receive dense feedback during topology construction while ensuring that minimizing the diameter remains the primary objective of the return. Our complete framework operates as follows. The RL agent sequentially selects K generators from a candidate pool C. At each step, its policy is influenced by a prior that favors numbers with high multiplicative order (7). The agent receives dense rewards (11), based on the average order of selected generators (10) and a structural score (17) derived from a fast message propagation (Section I-C). At the end of each episode, the exact diameter of the final topology is computed and incorporated into the final reward (12). The policy is trained using proximal policy optimization (PPO) [11]. Our implementation follows the standard PPO but is adapted for our problem. Key aspects include: • We collect a batch of complete episodes (each constructing a topology of K generators) before performing updates. • A separate MLP, with inputs [ωt,g(St+)]⊤[ _t,g(S^+_t)] , estimates the value function of the state. This low-dimensional input focuses the value network on the key metrics of progress. • We compute generalized advantage estimation (GAE) [10] using the step rewards and value predictions. • For each candidate topology, we cache computed graph metrics (diameter, average path length, etc.) to avoid redundant computation. I-C Connectivity Scoring via Message Propagation The structural score g(S)g(S) used in the reward function is designed to provide a smooth, differentiable proxy for the graph’s communication efficiency. It is derived from a fixed, parameter-free message-propagation procedure that simulates how quickly local information spreads through the graph. Given a generator set S, we first construct its undirected adjacency matrix ∈ℝN×N A ^N× N, where i,j=1 A_i,j=1 if j=i±s(modN)j=i± s N for any s∈Ss∈ S. We then add self-loops to obtain ~=+ A= A+ I. The normalized propagation operator is ^=~−1/2~~−1/2, A= D^-1/2 A D^-1/2, (14) where ~ D is the diagonal degree matrix of ~ A. Each node i is initialized with a fixed three-dimensional feature: i(0)=[cos(2πiN),sin(2πiN), 1]. x_i^(0)= [ \! ( 2π iN ),\ \! ( 2π iN ),\ 1 ]. (15) Stacking all node features yields (0)∈ℝN×3 X^(0) ^N× 3. We apply two rounds of nonlinear propagation: (k+1)=tanh(^(k)),k=0,1. X^(k+1)= \! ( A X^(k) ), k=0,1. (16) This operation measures how quickly local information mixes over the graph. After two propagation steps, we compute the variance vjv_j of each feature channel j across all nodes: vj=Var(:,j(2))v_j=Var\! ( X^(2)_:,j ). The structural score is the negative sum of these variances: g(S)=−∑j=13vj.g(S)=- _j=1^3v_j. (17) A graph that mixes information quickly will have node features that become similar after a few propagation steps, leading to low variance and thus a high score g(S)g(S). Conversely, a poorly connected graph will retain high variance. This procedure is computationally lightweight (relying on sparse matrix operations) and provides a dense, deterministic measure of global connectivity that can be used to shape the reward at every step of the RL process. IV Experimental Results and Discussion This section evaluates the communication topologies discovered by our RL-based optimization framework. All experiments are conducted with N=1024N=1024 agents, and each topology is constrained to an undirected degree of 1414 (i.e., K=7K=7 positive generators). We compare our method, denoted by CayleyTopo, against several baselines: • ExpoComm: the exponential-graph baseline from Li et al. [7] (generators 20,21,…2^0,2^1,…). • Fibonacci: generators taken from the Fibonacci sequence. • Simple Prime: the first K primes in increasing order. • Broadcast: a fully connected network (or a broadcast protocol) that serves as a high-overhead baseline. All topologies are evaluated under the same degree budget, ensuring a fair comparison of their communication efficiency and robustness. IV-A Information Dissemination Latency We first examine how quickly a message can spread through the network. We simulate a push-style epidemic process: at each round, every informed node attempts to transmit a message to each of its neighbors, with a per-link success probability of 0.750.75. The process continues until all nodes are informed, or until a maximum of 120120 rounds is reached. For each topology, we run 3030 independent trials and report the average number of rounds needed to reach 90%90\% (T90T90) and 100%100\% (T100T100) of the agents, as well as the total number of transmissions (AvgTX). Figure 2: Information dissemination latency under degree budget 1414: average rounds to 90%90\% (T90T90) and 100%100\% (T100T100) informed agents. Fig. 2 compares mean T90T90 and T100T100 across topologies. CayleyTopo achieves the fastest dissemination, with T90≈17.8T90≈ 17.8 rounds and T100≈24.5T100≈ 24.5. ExpoComm requires about 33.333.3 rounds for 90%90\% coverage and about 42.042.0 for full coverage, while Fibonacci and Simple Prime need roughly 7474-9898 rounds depending on the threshold. Broadcast hits the 120120-round cap without full coverage. The AvgTX of CayleyTopo is about 1.05×1041.05× 10^4, about 2.02×1042.02× 10^4 for ExpoComm, about 3.05×1043.05× 10^4 for broadcast, about 4.28×1044.28× 10^4 for Simple Prime, and about 4.98×1044.98× 10^4 for Fibonacci. Thus, CayleyTopo attains both the lowest latency and the lowest AvgTX among the designs shown, improving over ExpoComm on both metrics. IV-B Link-Failure Robustness A practical communication topology must tolerate link failures. We evaluate robustness by randomly removing edges at rates of 30%30\%, 50%50\%, 70%70\%, and 85%85\%. For each failure rate, we generate 2020 random failure realizations per topology. We report (i) the average rounds to 90%90\% informed nodes (T90T90) under random failures, illustrated in Fig. 3, and (i) at 85%85\% failures, the size of the largest connected component (LCC) as a percentage of agents, together with Pr[LCC≥80%] [LCC≥ 80\%] under random (Pr80-R) and distance-biased (Pr80-D) removals, summarized in Table I. Figure 3: Average dissemination delay (T90T90, rounds) versus link failure rate. TABLE I: Robustness at 85%85\% link failures: mean LCC size (% of agents) and Pr[LCC≥80%] [LCC\!≥\!80\%] under random (Pr80-R) and distance-biased (Pr80-D) removals. Topology LCC@85% Pr80-R Pr80-D CayleyTopo 84.27% 100% 100% ExpoComm 83.12% 85% 0% Fibonacci 69.22% 55% 0% Simple Prime 74.99% 65% 0% Broadcast Mode 14.10% 0% 0% Fig. 3 shows that, for failure rates below about 70%70\%, CayleyTopo maintains substantially lower T90T90 than ExpoComm and the other rule-based topologies; averaged over the 30%30\%-70%70\% regime, CayleyTopo is about 40%40\% faster than ExpoComm in terms of T90T90. At 85%85\% failures, all curves approach the same high delay (≈120≈\!120-121121 rounds), i.e., performance becomes comparable to the broadcast-style cap, because the underlying graphs are heavily fragmented. Table I reports the complementary LCC and Pr80 metrics at 85%85\% failures: CayleyTopo attains the strongest giant component and full Pr80-R/Pr80-D under both failure models, whereas distance-biased removal can yield Pr80-D=0=0 even when Pr80-R remains nonzero (e.g., ExpoComm). TABLE I: Per-step bandwidth consumption over 5050 simulation time steps under the hybrid communication schedule (same scenario as Fig. 4). Values are scaled by 10−310^-3 relative to raw simulator counts. Lower average indicates lower overhead; standard deviation and range (max-min) quantify temporal variability. Topology Avg. Std. dev. Range CayleyTopo 140.7140.7 16.116.1 76.876.8 ExpoComm 325.3325.3 212.1212.1 614.4614.4 Fibonacci 271.3271.3 188.7188.7 599.0599.0 Simple Prime 178.5178.5 82.282.2 399.4399.4 Broadcast Mode 768.0768.0 0.00.0 0.00.0 Figure 4: Cumulative communication-count over time. Lower values indicate fewer occupied transmission blocks. IV-C Communication Overhead in Information Sharing Beyond latency and robustness, a topology must also support efficient communication under realistic message loads. We simulate a scenario where agents exchange information over 5050 discrete time steps using a hybrid communication schedule (messages are sent only when needed, as opposed to broadcast). We track the cumulative number of transmissions (i.e., resource-block occupancy) and the resulting bandwidth consumption. Table I and Fig. 4 present communication-load results. The optimized topology consistently incurs the lowest cumulative transmissions and bandwidth usage among all compared designs; in particular, CayleyTopo achieves the lowest average per-step bandwidth and comparatively small temporal variability, whereas broadcast is non-fluctuating but incurs the highest average load. Notably, it achieves these savings while maintaining the fast dissemination and robustness demonstrated earlier. This confirms that CayleyTopo strikes a favorable balance between connectivity and communication overhead. IV-D Comparison to the Moore bound To contextualize the optimized topology quality, we compare the graph diameter against the Moore bound under the same degree budget. Fig. 5 shows that CayleyTopo remains close to the theoretical limit while preserving stronger practical behavior in dissemination and communication load. Figure 5: The graph diameter against the Moore bound under matched degree. Finally, for an intuitive structural view, Fig. 6 presents the CayleyTopo on a reduced-size ring with N=20N=20 agents. Figure 6: Visualization of CayleyTopo on a reduced ring, where N=20N=20. V Conclusion This work shifts the perspective on large-scale multi-agent communication from hand-crafted rules to optimizable design. By formulating topology selection as a discrete optimization over circulant Cayley graphs, we demonstrate that superior communication structures can be discovered rather than prescribed. The resulting CayleyTopo family is not only performant but also practical: it remains vertex-transitive, deterministic, and easy to implement, requiring no per-agent coordination beyond the shared generator set. More broadly, our study suggests that the communication graph itself should be treated as a first-class design variable, not a fixed constraint. As multi-agent systems scale to thousands or millions of agents, we believe that the paradigm of CayleyTopo, grounded in algebraic graph theory, will become a cornerstone for scalable, robust, and efficient multi-agent communication. References [1] W. Chen, B. Liu, H. Huang, S. Guo, and Z. Zheng (2019) When UAV swarm meets edge-cloud computing: the QoS perspective. IEEE Network 33 (2), p. 36–43. Cited by: §I. [2] A. Das, T. Gervet, J. Romoff, D. Batra, D. Parikh, M. Rabbat, and J. Pineau (2019) Tarmac: targeted multi-agent communication. In International Conference on machine learning, p. 1538–1546. Cited by: §I, §I. [3] J. Foerster, I. A. Assael, N. De Freitas, and S. Whiteson (2016) Learning to communicate with deep multi-agent reinforcement learning. Advances in neural information processing systems 29. Cited by: §I. [4] C. Godsil and G. F. Royle (2013) Algebraic graph theory. Springer Science & Business Media. Cited by: §I. [5] K. Ireland and M. I. Rosen (1990) A classical introduction to modern number theory. Vol. 84, Springer Science & Business Media. Cited by: Definition 4. [6] J. Jiang and Z. Lu (2018) Learning attentional communication for multi-agent cooperation. Advances in neural information processing systems 31. Cited by: §I. [7] X. Li, X. Wang, C. Bai, and J. Zhang (2025) Exponential topology-enabled scalable communication in multi-agent reinforcement learning. In The Thirteenth International Conference on Learning Representations (ICLR), Cited by: §I, §I, §I-B, 1st item. [8] M. Miller and J. Sirán (2012) Moore graphs and beyond: a survey of the degree/diameter problem. The electronic journal of combinatorics, p. DS14–May. Cited by: Theorem 1. [9] R. Olfati-Saber, J. A. Fax, and R. M. Murray (2007) Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE 95 (1), p. 215–233. Cited by: §I, §I. [10] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel (2015) High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438. Cited by: 3rd item. [11] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §I-B3. [12] Y. Shao, Q. Cao, and D. Gündüz (2024) A theory of semantic communication. IEEE Trans. Mobile Comp. 23 (12), p. 12211–12228. Cited by: §I. [13] Y. Shao, D. Gündüz, and S. C. Liew (2021) Federated edge learning with misaligned over-the-air computation. IEEE Transactions on Wireless Communications 21 (6), p. 3951–3964. Cited by: §I. [14] S. Sukhbaatar, R. Fergus, et al. (2016) Learning multiagent communication with backpropagation. Advances in neural information processing systems 29. Cited by: §I. [15] T. Tao and V. H. Vu (2006) Additive combinatorics. Vol. 105, Cambridge University Press. Cited by: §I-A.