Skip to content

Optimal Networks for Agentic Information Aggregation

Sep 2026 · arXiv.org · Vol abs/2609.35537 · 0 citations · 13 references
Computer Science Economics

TL;DR

Kearns, Roth, and Ryu show that the output agent's error approaches the global predictor's error along sufficiently deep paths with suitable feature coverage, while insufficient depth can prevent aggregation even in large networks.

Abstract

We study information aggregation in the networked learning model introduced by Kearns, Roth, and Ryu (SODA 2026). There is a fixed distribution over $d$ features and a common label. Agents learn in topological order on a directed acyclic graph. Each observes a subset of the features and its parents'predictions, fits a linear predictor to minimize mean squared error, and passes only its prediction forward. The global predictor is the best linear predictor using all features. Kearns, Roth, and Ryu show that the output agent's error approaches the global predictor's error along sufficiently deep paths with suitable feature coverage, while insufficient depth can prevent aggregation even in large networks. In contrast to their main focus on a given graph and feature allocation, we consider the limits of the model under two settings. In the adaptive designer setting, a designer chooses the graph, feature allocation, and output agent knowing the distribution. In the oblivious designer setting, the designer fixes all three before an adversary chooses the distribution. Each agent observes one feature and receives predictions from a limited number of parents. We call the aggregation exact when the output agent matches the global predictor exactly. For $d\ge3$, we show that no finite depth guarantees exact aggregation for every distribution with one parent per agent, even when the designer knows the distribution. In contrast, two parents per agent suffice for exact aggregation even in the oblivious designer setting. A fixed graph, feature allocation, and output agent achieve this for every distribution at depth $O(d\log d)$. Knowing the distribution reduces the depth to $O(d)$. Both constructions use $O(d^2)$ agents, with a very large constant for two parents. We show the bounds on the depth and number of agents are all optimal up to constant factors.

View source

Similar papers

#machine learning Preprint Sep 2026

Optimal Rates for Agentic Networked Information Aggregation

Building on the pioneering paper of Kearns, Roth, and Ryu (SODA'26), we study information aggregation in a networked learning model. The model captures a central pattern in agentic AI: each agent sees only part of the data and passes on only its own conclusion. Their model considers a linear regression problem with the...

M. Bateni, Z. Hadizadeh, Mohammadtaghi Hajiaghayi et al. · 1 citation
Preprint Aug 2026

Optimal Lower Bounds for Networked Information Aggregation

The problem of networked information aggregation, studied in Kearns et al. (2026), involves a group of learners situated on the vertices of a directed acyclic graph $G$, each learning a linear predictor $\widehat Y$ for a fixed random variable $Y$ given access to a local feature, as well as the predictors learnt by its...

Ambar Pal · 0 citations
#artificial intelligence Preprint Sep 2026

Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems

Codebook Agent is the most accurate method on all six benchmarks the authors compare, and an MLP proxy that reads the flattened adjacency, regressed on measured utility and per-task normalized token cost, reranks the top decoded candidates in a single batched forward pass.

Jin-Xi Yu, Yu-Bei Li, E. Jiang et al. · 1 citation
Preprint Sep 2026

Navigating Small-World Networks with Distance Predictions

Results show that a modest amount of predicted information is enough to accelerate decentralized routing well below Kleinberg's classical bound, and that even when nodes reveal no coordinates at all, reliable delivery remains achievable.

Ladan Kian, M. Tan, Dariusz R. Kowalski · 0 citations
Preprint Oct 2026

Network Intervention by Polling Strategic Agents

Poll, a polling algorithm, shows that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents'preferences across activities.

Chenyu Zhang, R. Parasnis, Saurabh Amin · 0 citations
Preprint Aug 2026

Test-Time Collaborative Classification over Multi-Agent Networks

This work develops a theoretical and experimental study of this independent training and cooperative inference paradigm, and establishes classification error guarantees under sufficient, finite-round, and finite-precision communication, together with PAC-style generalization bounds.

Ping Hu, Mert Kayaalp, Ali H. Sayed · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.