CS Paper Radar

Population Scaling or Data Dilution? Dynamics of Local Topology Evolution in Decentralized Learning

Yin-Kuan Liang, Yan Gao, Yang Long

cs.LG cs.AI ·submitted 2026-10-04 19:34 UTC · v2
publishedposition

Abstract

Scaling decentralized learning changes not only the number of clients $N$, but also the dynamics of information propagation and consensus. We argue that the effect of increasing $N$ cannot be understood in isolation, because data allocation, topology-dependent mixing, and communication capacity may change simultaneously. We study these coupled effects on CIFAR-10 with $N\in\{10,50,100,200\}$, comparing a degree-two Ring, a Static Random graph, and Local-First Heuristic Evolution (LFHE), a locally adaptive topology process based on friend-of-friend discovery. The Ring provides an analytically transparent failure mode: its Metropolis spectral gap decays as $Θ(N^{-2})$, implying progressively slower contraction of model disagreement as the population grows. Experiments show that holding the nominal local dataset size fixed substantially reduces the apparent population penalty observed when a fixed total dataset is divided among more clients. The remaining degradation depends strongly on communication structure: Ring enters a high-disagreement regime, whereas Static Random and LFHE remain close to consensus. Increasing LFHE's degree threshold further improves accuracy and consensus, but at a substantially higher model-transmission cost. These results show that decentralized scaling is governed by coupled learning and communication dynamics, rather than by the number of clients alone.

Comment
11 pages, 6 figures. Accepted as a poster at DynaFront @ NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

LFHE: Local-First Heuristic Evolution for Bounded Local Topology Search in Decentralized Learning with Non-IID Data

cs.AI cs.LG ·2026-10-06 ·Yin-Kuan Liang, Yan Gao, Yang Long
similarity 0.66
Abstract · Preprint. 31 pages, 12 figures, 8 tables

Decentralized learning is highly sensitive to communication topology under non-IID data. Adaptive peer-selection methods can exploit local model information, but broader peer discovery may require increasingly large control state, whereas direct spectral optimization typically relies on graph-wide information. We study the intermediate setting of bounded local topology search and propose Local-First Heuristic Evolution (LFHE), a representation-driven rewiring framework whose candidate discovery and scoring use only ego-neighborhood and friend-of-a-friend (FoF) information. The structural score admits an exact interpretation through graph Dirichlet energy: its sum across clients equals twice the representation Dirichlet energy, which under standard linear consensus dynamics governs the instantaneous dissipation of representation disagreement. LFHE combines this state-dependent structural signal with early exploration and degree control, while algebraic connectivity remains an offline graph diagnostic. Under bounded sparse degree, its FoF candidate state remains local rather than expanding toward population-wide peer tracking. Across four image, speech, and text benchmarks, LFHE achieves competitive decentralized learning performance. Matched-protocol controls identify the structural term as the principal empirical topology-selection signal, while comparison with broader peer discovery exposes a trade-off between predictive performance and discovery-state locality. Together, these results motivate state-aware bounded local topology search between pairwise peer selection and globally informed topology optimization.

0.47

Connectivity-Aware Client Selection in Decentralized Federated Learning

cs.AI ·2026-10-30 ·Usevalad Milasheuski, Monica Nicoli, Stefano Savazzi
similarity 0.61
Abstract

Decentralized federated learning (DFL) has emerged as a scalable alternative to centralized federated learning, removing the single point of failure and communication bottleneck at the server. However, most existing decentralized approaches rely on full-neighborhood broadcasting, where each client transmits its model update to all of its neighbors in each communication round. While effective, this results in significant communication overhead and high energy consumption. This paper applies spectral graph tools as lightweight client selection methods that leverage the graph topology by analyzing the spectral properties of the graph Laplacian over a fixed communication graph. Specifically, we exploit eigenvector embeddings and heat/diffusion kernel similarities to guide each client in selecting only a subset of structurally relevant neighbors, i.e., those that are most beneficial for the convergence of the federation process. This topology aware randomization matches or outperforms uniform neighborhood subsampling and approaches the accuracy of full broadcasting. The largest gains, about $3$ percentage points, emerge under strong data heterogeneity on larger, structurally rich graphs, while the total number of transmitted messages is reduced by $50\%$ compared to naive broadcasting.

0.20

Data-Topology Compatibility Enables Personalization in Decentralized Learning

cs.LG stat.ML ·2026-10-10 ·Veronica Xu, Lingfei Wang, Chenlei Leng, Fengxiang He
theorycode/data similarity 0.61
Abstract

Decentralized learning must balance collaboration with personalization across heterogeneous agents. This paper studies when cooperation can support statistically coherent groups of personalized models. We show that data-topology compatibility enables robust orbit-wise personalization: when local objectives and communication topology have (approximately) compatible automorphisms, agents within an orbit share (approximately) equal limiting distributions, while different orbits remain distinct without explicit personalization. This creates a new intermediate regime between global consensus and independent local learning. Under exact data-topology compatibility, as a reference system, we decompose the stochastic learning dynamics into orbit-level and transverse components, derive a necessary and sufficient stability criterion for distributional synchronization, and characterize the orbit-structured stationary law. Modelling an approximate data-topology compatible system as an $\varepsilon$-perturbed reference system, we prove the introduced errors have uniform-in-time and stationary $O(\varepsilon)$ bounds in 2-Wasserstein distance. We also prove sufficient conditions for lower stationary average excess risk than both independent local training and the best single shared parameter. Experiments on synthetic data, MNIST, and CIFAR-10 are in full agreement with the theory. The code is available at https://github.com/Veronicaaa1/orbit-personalization.

0.25

Network topology shapes consensus and vulnerability in LLM populations

cs.AI physics.soc-phcs.CY ·2026-10-22 ·Roberto Passaro, Ariel Flint, Romualdo Pastor-Satorras, Andrea Baronchelli, Luca Maria Aiello
similarity 0.60
Abstract

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.

0.44

Distributed Consensus, Optimization, and Learning under Communication Constraints

cs.IT cs.DCeess.SP ·2026-11-04 ·Zheng Chen, Nicolò Michelusi, Themistoklis Charalambous, Kaibin Huang
published similarity 0.58
Abstract · 20 pages, 3 figures, to appear in IEEE JSAC

Many modern engineering applications require distributed problem-solving in which multiple nodes in a network cooperate to achieve a common optimization objective. Numerous distributed optimization and learning algorithms rely on consensus-based distributed coordination to ensure network-wide agreement via iterative local interactions. In these algorithms, the accuracy, frequency, and reliability of information exchange among network nodes directly influence system performance, including convergence behavior, training delay, and model accuracy. This tutorial article adopts a bottom-up approach to present the fundamentals of consensus averaging and distributed optimization methods, and highlights the impact of network connectivity, information flow, and communication uncertainty on network cooperation and optimization performance. Building on these theoretical insights, we discuss key design principles for communication-constrained distributed learning across diverse network topologies and review common approaches to communication-efficient learning, particularly in wireless networks. Despite substantial progress, further efforts are needed to bridge the gap between theory and practice and fully realize the potential of cooperative and networked intelligence.

0.32

A Large-Dimensional Analysis of Least-Squares Federated Learning via Generalized Total Variation Minimization

cs.LG stat.ML ·2026-10-14 ·Ekkehard Schnoor, Malik Tiomoko, Alexander Jung
similarity 0.58
Abstract · 21 pages, 9 figures

Federated learning over decentralized networks inherently trades off the suppression of local finite-sample noise through collaboration against the bias that collaboration introduces between heterogeneous nodes. We study this tension by performing a large-dimensional analysis of Generalized Total Variation Minimization with least-squares models. Using tools from random matrix theory, we show that Lipschitz observations of the global GTVMin solution concentrate in large dimensions, universally for any underlying network structure. We provide exact analytic expressions for the asymptotically precise performance under both i.i.d. and non-i.i.d. Gaussian mixture distributions on a fixed network. For the latter, these expressions quantify how regularization balances local adaptation against collaboration. Our theoretical results are confirmed by experiments on synthetic and real-world data.

0.25

A Fundamental Limit in Decentralized Decision-Making

cs.IT cs.MA ·2026-09-07 ·Marco Carpentiero, Felice Scala, Vincenzo Matta, Ali H. Sayed
theory similarity 0.57
Abstract · This work has been submitted to the IEEE for possible publication

In decentralized decision-making, several agents connected according to a network graph aim at solving a classification problem by collecting streaming observations. Due to decentralization, they run an iterative algorithm where, at each iteration, they can only exchange information locally with their neighbors. While decentralized estimation solutions have been shown to match the performance of optimal centralized systems, we show here that surprisingly this conclusion does not hold for decentralized decision-making. Specifically, we prove that the error probability for the best decentralized decision strategy exhibits an irreducible loss with respect to the optimal centralized classifier. This result establishes a fundamental limit for the performance of any decentralized decision strategy. We obtain an analytical relation showing that this limit is related to the interplay between decentralization and classification. The first aspect appears through the distances between the nodes in the graph, while the second aspect plays through the moment generating functions of the likelihood ratios that describe the decision problem. By applying the derived closed-form relation to different network topologies and inference problems, we observe some interesting and perhaps unexpected behavior emerging. In particular, we characterize the scaling law (with the network size) for the loss over popular network topologies, showing that the error probabilities might differ by orders of magnitude; and we examine how performance is affected by the relative distance between informative and uninformative agents over the graph.

0.19

Network Topology Does Not Matter: The Breakdown of Classical Consensus in LLM Populations

cs.MA cs.AI ·2026-10-24 ·Sahil Rajesh Dhayalkar
similarity 0.57
Abstract · 19 pages, 3 figures, 3 tables

As multi-agent language model networks become widely deployed, predicting their collective behavior is a critical challenge. Classical distributed consensus theory relies on network topology to predict convergence, structurally assuming that agent updates are convex combinations, population means are conserved, and weights are content-independent. In this work, we demonstrate that these foundational assumptions fail for large language models (LLMs). By deterministically extracting continuous credence from token-level probabilities across eight instruction-tuned models and 73,080 controlled exchanges, we directly measure the empirical LLM update operator. We find that LLMs systematically violate convexity by updating outside the hull of observed opinions, exhibiting active repulsion (negative weights) that fundamentally breaks row-stochastic modeling and standard bounded-confidence repairs. Scaling these empirically fitted operators to simulations of 10,000 agents reveals that algebraic connectivity explains almost none of the final outcome variance. Instead, population dynamics are governed entirely by the model's internal update bias and message framing. Consequently, populations of several models, including those with up to 7B parameters, reliably compound small local drifts to reach confident agreement on objectively false claims regardless of their network structure. Our results prove that classical graph-theoretic metrics are inadequate for LLM populations, highlighting a profound deployment risk where multi-agent deliberation predictably saturates in collective delusion.

0.20