Optimal Networks for Agentic Information Aggregation

1 Introduction

• Agents fit linear predictors from their assigned features and parent predictions, passing predictions forward; exact aggregation means the output matches the best linear predictor using all features.The model limits each agent to one raw feature and at most b parent predictions.Source: §1 · p. 2
• Earlier work analyzes given graphs and feature allocations, whereas this paper optimizes those choices and the output agent under adaptive or oblivious distribution knowledge.Kearns, Roth, and Ryu show convergence under a graph-and-allocation condition and give instances with inverse-polynomial-in-depth error; their stated depth lower bound applies only below d.Source: §1 · p. 2
• The paper frames the design problem around how quickly excess error falls with depth and how much depth and how many agents exact aggregation requires.Its stated excess-error bounds assume normalized feature second moments and global-predictor coefficient norm, while exact constructions require only finite second moments.Source: §1 · pp. 2–3, §1.1 · p. 3

1.1 Our results

• With one parent per agent and d≥3, the adaptive optimal worst-case excess error is Θ(1/D); the oblivious bound lies between Ω(1/D) and O(d²/D).The oblivious gap in d remains open.Source: §1.1 · p. 3
• With two parents per agent, exact aggregation is achievable at depth O(d) adaptively and O(d log d) obliviously, using O(d²) agents in both settings.A fixed gadget simulates each three-parent agent using a constant number of two-parent agents, though the constant is very large.Source: §1.1 · p. 3
• For d≥3, every fixed parent limit b≥2 requires oblivious depth Ω(d log d), and some adaptive distributions require depth at least d even without a parent limit.The adaptive depth-d construction with three parents is therefore worst-case optimal.Source: §1.1 · p. 3
• For every fixed b≥2, some normalized distribution requires Ω(d²) agents for exact aggregation, regardless of depth and even when the designer knows the distribution.This makes the quadratic agent count optimal in both designer settings.Source: §1.1 · p. 3

2 Preliminaries

• Each agent fits the best linear predictor from its assigned raw feature and its parents’ predictions, in topological order.The output predictor lies in the span of the raw features, as does every agent’s prediction.Source: §2 · p. 4, §2.2 · p. 5

2.1 Projection

• The fit is the orthogonal projection of the label onto the span of an agent’s inputs; projections onto finite-dimensional orthogonal subspaces split over their sum.Projection is linear in the projected variable and is unique even if its coefficients in a particular input set are not.Source: §2 · p. 4
• An agent’s excess error equals its squared distance from the global prediction, and error is non-increasing along every edge.For a parent prediction and its child’s fit, the MSE decrease equals the squared distance between those predictions; zero excess error is equivalent to exact aggregation.Source: §2 · p. 4, §2.1 · p. 5
• Replacing the label by its global linear prediction leaves every agent’s prediction unchanged.The label component orthogonal to the raw features therefore need not be retained in network analysis.Source: §2.1 · p. 5

2.2 Graph constraints and the two settings

• Excess-error bounds use bounded feature second moments and a bounded sum of absolute global-predictor coefficients; exact-aggregation constructions require only finite second moments.Rescaling to unit bounds scales excess-error bounds by (A*MX)², but exact aggregation does not require normalization.Source: §2.2 · p. 5
• The adaptive objective chooses a graph and allocation after the distribution is known, while the oblivious objective fixes them before the adversary chooses it.Both optimize over finite DAGs with in-degree at most b and output depth at most D; agents fit their coefficients from the distribution in either setting.Source: §2.2 · pp. 5–6

3 Related Work

• Kearns, Roth, and Ryu [KRR26] bound path excess MSE when every M consecutive agents collectively observe all features; Bateni et al. [BHH+26a] extend the protocol to binary classification and logits.The cited path guarantee assumes bounds on feature second moments and the global predictor’s coefficient ℓ1 norm.Source: §3 · p. 6
• Pal [Pal26] sharpens a lower bound for cyclic allocations and extends it to convex losses, while Bateni et al. [BHH+26b] establish the optimal covered-path rate Θ(M²/D) beyond depth of order M².Bateni et al. also obtain analogous bounds for logistic classification.Source: §3 · p. 6
• These rate results analyze given networks and allocations under coverage conditions, whereas this paper optimizes the graph, allocation, and output agent against worst-case distributions.The closest cited lower bound from Kearns, Roth, and Ryu [KRR26, Theorem 5.9] applies only when depth D<d.Source: §3 · p. 6

4 One parent per agent

• For d≥3, one parent per agent cannot guarantee exact aggregation at any finite depth, while worst-case excess error scales as Θ(1/D).Source: §4 · p. 6

4.1 Lower bound

• An arbitrary depth-D graph has error at least 1/(320D) on the constructed three-feature distribution, whose features share a large common component and small informative components.Source: §4.1 · pp. 6–7

4.2 Upper bound in the adaptive designer setting

• The adaptive designer greedily selects the feature most correlated with the residual, yielding e_D ≤ 1/(D+1) under the stated normalization bounds.Source: §4.2 · p. 7

5.1 The oblivious designer setting

• The oblivious construction runs rounds that find an improving prediction and preserve progress by combining it with earlier predictions; its balanced-tree gadget adds O(log d) depth per round.Source: §5.1 · pp. 7–8
• Three parents per agent suffice for exact aggregation in both settings; the oblivious construction uses at most 4d^2 agents and depth O(d log d).Source: §5.1 · pp. 7–8, §5 · p. 7

5.2 The adaptive designer setting

• When the designer knows the distribution, exact aggregation is achievable at depth at most the feature rank r, with the output predicting f∗.Source: §5.2 · pp. 8–9

5.3 Depth lower bounds

• The depth bounds are optimal up to constants: some rank-d distributions require depth d adaptively, and every fixed parent limit b≥2 requires Ω(d log d) depth obliviously.Source: §5.3 · p. 9

• The fixed replacement gadget uses O(1) agents and adds O(1) depth while reproducing a three-parent agent’s prediction for every distribution.To remove distribution dependence, it runs all two-parent graphs with at most 303 agents in parallel; the resulting constant is very large.Source: §6 · pp. 9–10
• With at most two parents per agent, exact aggregation is possible for every finite-second-moment distribution, using O(d^2) agents and depth O(d log d) obliviously or O(r^2) agents and depth O(r) adaptively.Source: §6 · p. 10

7 Lower bound on the number of agents for exact aggregation

• For every fixed parent limit b≥2, Θ(d^2) agents are necessary and sufficient for exact aggregation in both designer settings.The adversary can choose a normalized distribution requiring this many agents even when the designer knows the distribution and depth is unrestricted.Source: §7 · p. 10
• The lower-bound proof perturbs the feature covariance while preserving fitted coefficients, then uses a matrix-constraint count to rule out exact networks below the agent bound.Source: §7 · p. 11

AI use statement

• The authors report using GPT-6 Astra to develop proof ideas and assist with gadget and agent-count proofs, and say they verified all AI-assisted proofs.Source: AI use statement · p. 11

A Extended Related Work

• Related work connects prediction exchange to calibration-based agreement protocols and multiaccuracy auditing, where correlated residual tests provide correction directions.Source: A Extended Related Work · p. 14
• The discussion also distinguishes repeated-averaging social learning from stacked generalization and vertical federated learning, which combine predictions or collaborate across feature holders.Source: A Extended Related Work · p. 14

B Proofs for the preliminaries

• Replacing Y with the global prediction f∗ leaves every agent’s prediction unchanged.The proof proceeds by induction in topological order, using orthogonality of Y − f∗ to each agent’s input space.Source: B Proofs for the preliminaries · p. 15
• The worst-case quantities lie between 0 and 1, are non-increasing in parent bound b and depth D, and non-decreasing in feature count d.The supplied proof explains monotonicity by the expanded design choices for larger b or D, and by duplicating a feature for larger d.Source: B Proofs for the preliminaries · p. 15

C.1 One or two features

• For d ≤ 2, a designer can achieve exact aggregation on a path of d agents; for d = 2, the fixed allocation x1, x2, x1 works for every finite-second-moment distribution.With this fixed allocation, the third agent’s inputs span the feature space whenever an earlier prediction has not already matched the global predictor.Source: §C.1 · p. 15

C.2 The lower bound

• After a path first combines distinct features, each later agent removes at most a 10ρ^2 fraction of its parent’s error.The proof uses a bound on the error decrease at each step and iterates it across the remaining path.Source: §C.2 · pp. 17, 19

C.3 The upper bound

• Under the coefficient and feature bounds, the upper-bound construction uses a greedy allocation on a path of D agents.At each step, fitting with the selected raw feature can reduce the residual error; the fitted prediction has no greater error than that candidate fit.Source: §C.3 · pp. 19–20

C.4 The bounds for the unit case

• For every d ≥ 3, 1/(640D) ≤ R1(d, D) ≤ 1/(D + 1), and in particular R1(d, D) = Θ(1/D).Source: §C.4 · p. 20

C.5 A fixed allocation at depth below the number of features

• If the path omits a feature on which the label depends entirely, every prediction on that path can remain zero, leaving output error 1.The proof chooses independent standard Gaussian features and sets the label to the unobserved feature.Source: §C.5 · p. 21
• When D < d, the oblivious designer’s worst-case value is R1(d, D) = 1.A path shorter than the feature count omits some feature, which an adversary can make the label equal.Source: §C.5 · p. 21

D.1 A fixed graph for exact aggregation

• The interval gadget computes a fit from interval predictions together with x1, pt, and q, using at most 4(t − 1) added agents and O(log t) additional depth.Its agents have at most three parents, and its graph and allocation do not depend on the distribution.Source: §D.1 · pp. 21, 25, 26
• The gadget joins fits from two shorter intervals using their shared prediction and a fit from the shared inputs.The recursive construction combines the interval fits and the shared-input fit to compute the larger interval’s fit.Source: §D.1 · pp. 23, 25
• The construction’s retained prediction space gains a dimension in every round before exact aggregation, and after at most d − 1 rounds its fit equals f∗.Once the retained space reaches the feature space, its fit is the global predictor.Source: §D.1 · pp. 26–27
• For every d ≥ 2, a fixed graph achieves exact aggregation for every finite-second-moment distribution with at most 4d^2 agents, at most three parents per agent, and depth O(d log d).The construction uses one source and d − 1 rounds; each round tests raw features, combines predictions, and applies an interval gadget.Source: §D.1 · pp. 26–27

D.2 Selecting features and updating predictions

• At each step, the construction selects the unselected feature with the smallest nonzero prediction improvement and uses its prediction as the next selected prediction.If the current prediction is not global, a feature with nonzero improvement exists; after r selections, the selected features span the feature space and the prediction equals the global predictor.Source: §D.2 · pp. 27, 29
• The update lemma preserves the invariant and ensures each required next prediction lies in the span of the current and selected predictions and the agent's observed feature.This span condition lets an agent produce the required prediction from its available inputs.Source: §D.2 · p. 27
• For every finite-second-moment distribution of rank r ≥ 1, exact aggregation is achievable with at most three parents per agent and depth at most r.The construction uses one source and adds at most r − t agents after selection t; it stops early if a selected prediction equals the global predictor.Source: §D.2 · p. 29
• The first update needs agents receiving only the selected prediction, while later updates use three predictions as parents; each update adds at most one layer.The selected prediction reuses an existing agent, and the construction reaches p_t by depth t and q_t,i by depth t + 1.Source: §D.2 · p. 29

D.3 The feature order required along a path

• When the longest ordered feature prefix on a path to the output has length ℓ < d, the excess error is at least 1/(2d^2(ℓ + 1)).The bound applies to the normalized rank-d construction described in the proof.Source: §D.3 · pp. 29–30
• An agent's prediction lies in the span of the longest ordered feature prefix appearing along a path to that agent.At the output, this confines its prediction to the span of the first ℓ features, whose best possible predictor still incurs the stated lower bound when ℓ < d.Source: §D.3 · pp. 29–30
• D ≥ d in the adaptive setting, while every fixed parent limit b ≥ 2 requires D = Ω(d log d) in the oblivious setting for exact aggregation.The adaptive lower bound holds even without a parent limit.Source: §D.3 · p. 30
• The oblivious lower bound follows because source-to-output paths must contain every permutation of the d features, but depth D permits at most (2b)^D possible feature orders.Counting these orders yields (2b)^D ≥ d!, which implies the stated asymptotic depth bound.Source: §D.3 · pp. 30–31

E.1 Combining three predictions exactly

• After normalization, fitting the target to two predictions corresponds to applying F to their orthogonal residual points.The residual map sends the target prediction to zero, and the pairwise fit's residual is F of the two input residuals.Source: §E.1 · pp. 31–32
• Sequences of F operations on triples can represent complex expressions using multiplication, division by nonzero values, and F; a zero expression yields a triple of zeros.The construction maintains numerator and denominator triples, with a nonzero denominator, so division is implemented without requiring a division operation on points.Source: §E.1 · pp. 32–33
• From an ordered noncollinear triple, at most five operations either produce zero or yield a triple T and a nonreal contraction µT with F(1, µ) = µ and 0 < |µ| < 1.The construction obtains µT in three operations after forming T in two; its entries have strictly decreasing norms.Source: §E.1 · pp. 33–34
• For distinct u and v with real part one, F(uv, m²) is purely imaginary at their midpoint m, and F(1, q²) = 0.The construction derives such u and v from the nonreal µ, then applies these operations to produce zero.Source: §E.1 · pp. 35–36
• At most 300 applications of F produce zero from any three noncollinear points in C.This yields exact combination of the three starting points into the desired prediction, which corresponds to zero in the normalized plane.Source: §E.1 · p. 36
• At most 300 projections combine three predictions exactly, and at most 303 added agents reproduce a three-parent agent’s fit while observing its raw feature.The latter distribution-dependent gadget uses agents with at most two parents and works for every distribution with finite second moments.Source: §E.1 · pp. 38–39

E.2 Replacing a three-parent agent by a fixed gadget

• A fixed gadget reproduces any three-parent agent’s prediction for every finite-second-moment distribution using O(1) agents and adding O(1) depth.Its graph and output are fixed independently of the distribution.Source: §E.2 · p. 40

E.3 Applying the gadget to the three-parent constructions

• O(d^2) agents and depth O(d log d) suffice obliviously for d ≥2, while O(r^2) agents and depth O(r) suffice adaptively for rank r ≥1.With at most two parents per agent and single-feature allocation, exact aggregation holds for every distribution with finite second moments; for d = 1, one agent suffices.Source: §E.3 · p. 41

F.1 The distribution

• For every d ≥2, a symmetric E with |Eij| < 1/(8d) can make the upper-triangular entries of Σ = 1/2 I + E algebraically independent over Q.The entry bound also ensures Σ is positive definite.Source: §F.1 · pp. 41–42
• For every u ∈ Rd, ⟨u^T x, Y⟩ = u^T c.This follows from ⟨u^T x, Y⟩ = u^T E[xY] = u^T c.Source: §F.1 · pp. 42–43
• Σ = I/2 + E is positive definite, with v^TΣv ≥ 3v^Tv/8 for every nonzero v.This ensures that x ∼ N(0, Σ) and w* = Σ^-1c are well defined.Source: §F.1 · p. 42
• The features are linearly independent because E[xx^T] = Σ and v^TΣv > 0 for every nonzero v.Their second moments are determined by Σ.Source: §F.1 · p. 42

F.2 Counting the input inner products

• A nonzero symmetric matrix Δ with zero diagonal can satisfy the required inner-product constraints for every agent’s input coefficient vectors.The construction counts homogeneous linear constraints on the matrix’s free entries.Source: §F.2 · p. 43
• The imposed constraints, together with the zero diagonal and induction over agents, imply the required condition for every input pair.The proof handles distinct inputs through the imposed equations and self-pairs through the zero diagonal and induction.Source: §F.2 · pp. 43–44

F.3 What exact aggregation requires

• Each agent’s fitted coefficient vector can be expressed as a ratio of polynomials in the covariance-matrix entries, with a positive denominator at Σ.The output agent’s polynomials represent its coefficient vector as K(Σ)/L(Σ), with L(Σ) > 0.Source: §F.3 · pp. 44, 46
• Under the input constraints, these polynomial representations remain unchanged when Σ is replaced by Σ+tΔ.The induction preserves the selected input columns and the polynomials’ values along the perturbation.Source: §F.3 · pp. 44, 46
• Exact aggregation forces Δ=0: det C divides L(C), but a nonzero Δ yields singular Σ+tΔ and contradicts the invariant positive value of L.Algebraic independence supplies the polynomial identity used to show det C divides L(C).Source: §F.3 · pp. 47–48

F.4 Proof of the lower bound

• For each d≥2, the proof uses a normalized adversary-chosen distribution with linearly independent features and Y=f∗.The designer may choose any graph, single-feature allocation, and output agent that achieves fG=Y.Source: §F.4 · p. 49
• If an exact graph violated equation 10, Lemma 7.2 would supply a nonzero Δ satisfying equation 13 at every agent.The proof applies this implication to the fixed distribution.Source: §F.4 · p. 49
• Lemma 7.3 then forces Δ=0, a contradiction, so every exact graph satisfies equation 10.Source: §F.4 · p. 49