acceptodds
Under review as a conference paper at ICLR 2027

Optimal Networks for Agentic Information Aggregation

Abstract

We study information aggregation in the networked learning model introduced by Kearns et al. (SODA 2026). There is a fixed distribution over 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 et al. 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 , 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 . Knowing the distribution reduces the depth to . Both constructions use 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.

Primary area:
learning theory
Keywords:
Networked information aggregation, Distributed learning, Linear regression, Network design

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_oyeeOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper provides new exact thresholds for sizing networks optimally in DAG-based agentic prediction aggregation scenarios. The authors provide analyses under the oblivious and adaptive setting each, which can give insights for feasibility and generality of sizing networks. The analysis is rigorous and the contribution is theoretical. No experimental validation was performed.

Critical strengths
  • The direction seems promising and potentially useful: Use the theoretical model of aggregation over predictors to apply in agentic AI
  • The presentation of the work is technical and rigorous, and novelty is organized by stating new results in a table.
  • The analysis via oblivious and adaptive settings appears important for the setting of designing an actual network in any more practical scenario.
Critical weaknesses
  • The contribution is theoretical. There is no experimental section validating the theoretical contributions. Some simulation studies and discussion on realistic assumptions could help. Also, from the title, I would have expected some agentic AI use cases for validation, such as LLM agents feeding into each other.
  • The theoretical framework itself is not significantly novel, given the work is building upon various related prior works.
  • I think an experimental validation in the direction of use cases would be useful for the paper, as none is given currently.
  • Presentation-wise, part of the paper is hard to place. Some overview figures could be helpful to easily understand the architectures of interest. Similarly, a discussion or conclusion would be helpful for less-familiar readers.
  • The discussion of related work is a bit sparse, I wonder does this area of research allow a connection to recent work on circuit complexity / collaboration (for LLMs, e.g. [A, B]) or network coding?

[A] Feng et al. "Towards revealing the mystery behind chain of thought: a theoretical perspective." Advances in neural information processing systems 36 (2023): 70757-70798.

[B] Zhang et al. "Chain of agents: Large language models collaborating on long-context tasks." Advances in Neural Information Processing Systems 37 (2024): 132208-132237.

Questions for authors
  1. What use cases does this work provide? For agentic, I wonder if it is possible to consider LLM agents feeding into each other?
  2. What main limitations does this theoretical analysis have that could potentially be relaxed in future work (such as 1 feature per agent)?
  3. Does this area of research allow a connection to recent work on circuit complexity (for LLMs) or network coding?
2 comments

We thank the reviewer for their time and careful review.

On the contribution being theoretical. Yes, this is true. However, the model of Kearns, Roth, and Ryu (SODA 2026) and its subsequent works are motivated by more practical scenarios such as agentic AI, where each agent sees part of the information and later agents build on the outputs of earlier ones. As we say in the introduction, this is our motivation as well. Our goal in this paper is to find the limits of their model: what the best network can do, and what no network can do.

On experiments and use cases. We agree that experiments in the direction of use cases, such as LLM agents feeding into each other, would be valuable. Our focus in this paper is on the limits of the model, and we leave its practical applications for future work. The model is well motivated by agentic AI, which makes this direction attractive.

On novelty. Yes, we do not introduce the model. There is an active line of work on it: Kearns, Roth, and Ryu (SODA 2026), Bateni et al. (2026a, 2026b), and Pal (2026), all discussed in Section 3. These works mostly analyze a given graph and feature allocation. Our framing is different: a designer chooses the network, and we ask what the best choice achieves. This perspective is new and sheds more light on the model.

On presentation. We thank the reviewer for these suggestions. In the revised version, we added a figure of the three-parent network in the adaptive designer setting (Figure 1), a figure for the two-parent replacement (Figure 2), and a conclusion with limitations and future work (Section 8). All changes are marked in blue.

On related work. We thank the reviewer for these papers. We added a discussion of [A] and [B] to the revised version, in the introduction and Appendix A. Systems like the one in [B] are the kind of practical setting that motivates this model. Its worker agents form a path with one parent per agent, which our Section 4 studies in a simpler form, with scalar predictions in place of text messages.

What use cases does this work provide? For agentic, I wonder if it is possible to consider LLM agents feeding into each other?

Again, the motivation is agentic AI, and LLM agents feeding into each other, as in [B], is the setting we have in mind. We hope that our theoretical results can help in that direction.

What main limitations does this theoretical analysis have that could potentially be relaxed in future work (such as 1 feature per agent)?

We thank the reviewer for pointing out the one-feature assumption. It is indeed easy to relax. If each agent may observe up to a constant number cc of features, our upper bound constructions still apply and the same arguments give the lower bounds for exact aggregation up to constant factors. We added a brief discussion of this in Appendix G.

As the reviewer says, moving the model toward practical settings is the most important direction for future work. The main gaps are exact population fits, linear learners, and scalar messages.

Does this area of research allow a connection to recent work on circuit complexity (for LLMs) or network coding?

Yes, our questions are motivated by and connected to both. As in circuit complexity, we measure depth and size under a bound on the number of inputs to each node, and as in network coding, intermediate nodes forward combinations of what they receive. The results are not directly applicable there right now, since each of our nodes must output its own least-squares prediction. Again, we leave moving the model of Kearns, Roth, and Ryu toward these more practical settings as future work.

Thank you for the response. My concerns have been addressed. I think the theoretical results are of potential interest. Thus, in light of the provided discussions and clarifications, I increased my score in favor of acceptance.

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

This paper studies information aggregation in a networked learning model on a directed acyclic graph. Each agent observes one raw feature and its parents’ predictions, and fits a linear predictor of a common label by minimizing population mean squared error. Exact aggregation means matching the best linear predictor with access to all features. The paper studies network design both with knowledge of the data distribution (adaptive designer) and before the distribution is chosen (oblivious designer). For d≥3d\ge3, single-parent networks have no finite-depth uniform guarantee of exact aggregation. The authors first construct exact-aggregation networks with at most three parents per agent, then simulate these using two-parent gadgets with constant-factor overhead in depth and size. The resulting two-parent networks achieve exact aggregation at depth O(d)O(d) in the adaptive setting and O(dlog⁡d)O(d\log d) in the oblivious setting, using O(d2)O(d^2) agents. Matching worst-case depth lower bounds and an Ω(d2)\Omega(d^2) agent-count lower bound for every fixed parent limit b≥2b\ge2 establish optimality up to constant factors. The universal two-parent construction has very large constants.

Critical strengths

S1: The paper systematically studies the structural limits of network constructions for optimal aggregation. The analysis follows a clear path from single-parent networks to three-parent networks, then to two-parent networks through constant-overhead simulation. The research question is clear, and the paper makes a well-defined advance over prior work. S2: The difference in capability between single-parent and two-parent networks is insightful. S3: The theoretical model and lower-bound analysis are well developed, and the key proofs establish nontrivial results.

Critical weaknesses

W1. The practical interpretation of the model remains insufficiently concrete. Agents fit population-optimal linear predictors, observe one raw feature, and communicate scalar predictions; the adaptive designer additionally knows the data distribution. These assumptions define a clear theoretical aggregation problem, but the paper provides limited guidance on which concrete collaborative tasks they capture. An explicit mapping between a representative task and the model’s information, prediction, and communication assumptions would clarify the applicability of the results.

W2. The universal, distribution-independent two-parent construction has very large constants because it enumerates bounded-size candidate networks and combines their outputs. This limits its direct practical use and leaves the consequences of the one-parent versus two-parent distinction under finite network budgets unclear. The asymptotic optimality results are informative, but a concrete illustration of the construction and its overhead would help readers assess their practical meaning.

Presentation Comment: an example in Section 6 would make the transition from the distribution-dependent replacement to the universal enumeration-based gadget easier to follow. There is also a minor counting typo: the summation at line 379 starts at (t=0), whereas the corresponding summation in Appendix D.2, line 1316, correctly starts at (t=1).

Questions for authors

Q1. Could you illustrate a concrete collaborative task and explain how its information, predictions, and communication correspond to the assumptions of this model?

Q2. Could you illustrate the two-parent simulation on a small example and clarify which aspects of the enumeration-based proof produce the very large constants?

Q3. Which parts of the exact-aggregation argument critically rely on exact population fits, and what limits does this place on interpreting the results in finite-sample settings?

2 comments

We thank the reviewer for their time and positive review.

On the practical interpretation of the model. We adopt the model and its assumptions from Kearns, Roth, and Ryu (SODA 2026). As we say in the introduction, it is motivated by scenarios such as agentic AI, where a task is split across several agents and later agents build on the outputs of earlier ones. We agree that a concrete task makes this clearer, and we give one in our answer to the first question below.

On the large constants. Yes, this is true, and we say so in the abstract, the introduction, and Section 6. The two-parent construction in the oblivious designer setting is a theoretical result, mostly meant to show the limits of the model: two parents are already enough for exact aggregation, in contrast to one parent. From a practical point of view, the three-parent constructions seem to be the better choice, since they do not have this issue.

On presentation. We thank the reviewer for the suggestion and for catching the typo. In the revised version, we added an example with a figure to Section 6 and fixed the typo. All changes are marked in blue.

Could you illustrate a concrete collaborative task and explain how its information, predictions, and communication correspond to the assumptions of this model?

A concrete example is answering a question about a long document with several LLM agents, as in Chain of Agents (Zhang et al., NeurIPS 2024). Each agent reads one chunk of the document together with the outputs of earlier agents. The chunks are the features, the outputs are the predictions, and the choice of who reads whose output is the network. Of course, the model of Kearns, Roth, and Ryu is a simpler theoretical version of this, with linear predictors and scalar predictions. We now mention this example in the introduction.

Could you illustrate the two-parent simulation on a small example and clarify which aspects of the enumeration-based proof produce the very large constants?

We construct the two-parent networks from the three-parent ones, by replacing each three-parent agent with a gadget of two-parent agents. The three-parent constructions do not have a large constant. When the distribution is known, the replacement has a moderate constant factor of at most 303303. When it has to work for all distributions, we enumerate all two-parent graphs on at most 303303 agents and combine their outputs, which gives the very large constant. The details are in Section 6 and Appendix E.

Which parts of the exact-aggregation argument critically rely on exact population fits, and what limits does this place on interpreting the results in finite-sample settings?

All our results for exact aggregation rely on exact fits. However, they hold for every distribution, including the empirical distribution of a finite dataset. So if all agents fit on the same finite dataset, the output agent matches the global least-squares fit on that dataset, which is what a single learner with all the features would compute from the same data. The network therefore loses nothing compared to this learner, and what remains is only the finite-sample error of the global fit itself. We now state this in the conclusion.

Thank you for your response. I believe this is an interesting topic, and I will maintain my positive rating.

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

The paper studies information aggregation in directed acyclic networks. Each agent observes one of d features and its parents’ predictions, computes the population least-squares prediction of a common target, and forwards one scalar. It asks what architectures can achieve under a parent limit bb, distinguishing distribution-adaptive architectures from oblivious architectures.

One parent per agent gives worst-case excess error Θ(1/D) at depth D, so exact aggregation is impossible at any finite depth even with a known distribution. Three parents give exactness for every distribution at depth O(d log d) with at most 4d² agents, and depth d with 1 + C(d,2) agents when the distribution is known. Two parents achieve the same asymptotics via a constant-size gadget.

Critical strengths
  1. The paper provides a nontrivial structural characterization. Kearns et al. (SODA 2026) analyze a given graph and allocation. This paper asks what the best graph can do under a parent limit and settles the depth and the number of agents needed for exact aggregation up to constants, in both the adaptive and the oblivious setting (Table 1). The one-parent versus two-parent dichotomy is a crisp message. 2: The principal theories and proofs are solid and directly establish the central claims. The explicit three-parent construction, the reduction to two-parent networks, and the size lower bound provide substantial mathematical content. In particular, the lower bounds help distinguish limitations intrinsic to the protocol from limitations of a particular construction.
Critical weaknesses

This paper's major focus of learning theory is out of my expertise. Based on my understanding, the barrier depends a restrictive protocol: each agent must transmit its own least-squares prediction of the label, not a message chosen for downstream use, so the results characterize mandatory local prediction, not aggregation in general. With free linear messages and known coefficients, a one-parent chain of d agents recovers the global predictor by forwarding the partial sum Σj≤iw∗jxjΣ_{j≤i} w*_j x_j, and a depth-two star with d parents does the same, so the one-parent Θ(1/D) barrier and the adaptive depth-d bound follow from the restriction. This makes the restriction the central modeling choice, which the paper never justifies for the agentic systems in its framing.

Questions for authors

What application specifically requires every intermediate message to be a locally optimal prediction of the same target? Which principal separations survive if agents may instead transmit a learned scalar linear summary?

2 comments

We thank the reviewer for their time and positive review.

On requiring agents to pass predictions. We adopt this protocol from Kearns, Roth, and Ryu (SODA 2026). Their model is the subject of an active line of work and is quite popular in the ML community, as can be seen in Bateni et al. (2026a, 2026b), Pal (2026), and discussed in our related work section. We study their model from a different, network-design perspective.

On the partial-sum alternative. As the reviewer says, this alternative requires the global coefficients to be known. But computing the global coefficients raises the same question again: how are they computed, and what information or feedback is available to compute them? Furthermore, since it needs knowledge of the distribution, this alternative only covers the adaptive designer setting. This shows the strength of our results in the oblivious designer setting: even without any knowledge of the distribution, let alone its global coefficients, the restricted networks recover the global predictor exactly and efficiently, using only local computations.

On the depth-two star. The star needs one agent with dd parents. As we say in the introduction, we bound the number of parents because otherwise a single agent's learning problem is as large as the global one.

What application specifically requires every intermediate message to be a locally optimal prediction of the same target?

As said above, passing predictions keeps the network computations efficient when the number of features given to each agent is bounded. Furthermore, passing predictions is a natural choice by Kearns, Roth, and Ryu: without knowledge of the distribution, an agent's own best prediction is the natural message to pass on.

Which principal separations survive if agents may instead transmit a learned scalar linear summary?

If arbitrary linear summaries are allowed, the proposed partial sum of course works in the adaptive designer setting. But this raises the same question as above: how are the global coefficients computed, and what information or feedback is available to compute them? Our results answer this question for agents that learn by predicting the label.

I thank the author for the clarifications. I have no remaining concerns and would like to maintain my positive rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.