Prediction-passing agent chains need quadratic depth to emulate centralized learners: excess error can persist until depth M^2 and thereafter falls at Θ(M^2/D), a rate the authors prove optimal for linear regression and logistic classification using explicit Gaussian worst-case constructions.

Main Finding

The paper characterizes the optimal rate at which prediction error shrinks along a chain (or M-covered path) of linear agents who each see only part of the raw features and forward a single prediction. Key results: - Upper bound: For any M-covered path of depth D, the excess mean-squared error (MSE) of the final linear predictor satisfies MSE(f_D) − MSE(f*) = O(M^2 / D), (improving the prior O(M / √D) bound). - Lower bounds: the O(M^2 / D) rate is tight up to constants. In particular: - There exist instances where excess MSE remains Θ(1) for all depths D ≤ M^2 (a constant lower bound). - For D ≥ M^2 there are M-covered paths with excess MSE Ω(M^2 / D). - The cyclic example of Kearns–Roth–Ryu (previously Ω(M/D)) actually yields an improved lower bound Ω(√(M/D)) in the shallow regime D < M^2. - No single fixed finite distribution can exhibit the worst-case M^2/D slow rate at all depths: for any fixed distribution the excess error contracts geometrically in blocks of M agents (there exists q < 1 with E_{s+M} ≤ q E_s), so eventually convergence is fast. - Analogous optimal upper and lower bounds hold for binary classification in the logit-passing (BCE) protocol. A Gaussian transfer theorem shows that, in Gaussian examples, logistic predictors align with least-squares predictors up to scaling, so lower-bound examples transfer to classification.

Key Points

• Model: agents placed in a DAG act in topological order; each agent sees a subset of raw features and the scalar predictions (or logits) from its parents, fits a linear predictor to minimize population loss (MSE or BCE), and forwards only its scalar prediction.
• M-covered path: a directed path A1→...→AD is M-covered if every block of M consecutive agents collectively sees all raw features. M quantifies how rapidly raw information is reintroduced along the chain.
• Improved upper bound (Theorem 1): via an inductive argument that “feeds the argument its own output,” the authors tighten the previous O(M/√D) to O(M^2/D). The bound assumes bounded feature second moments and bounded ℓ1 norm of the global predictor.
• Matching lower bounds:
  • Depth-dependent construction (Theorem 3): a Gaussian construction (rotating weak signals across M features) gives excess error Ω(M^2/D) for D ≥ M^2 and a constant Ω(1) up to depth M^2.
  • Cyclic example analysis (Theorem 2): improved analysis of the earlier cyclic construction yields excess error Ω(1/√p) after p passes (so Ω(√(M/D)) when D = pM and p ≤ M−1).
• Fixed-distribution geometric convergence (Theorem 5): for any fixed finite distribution and fixed M there exists q < 1 (depending on distribution and M) so that every block of M agents reduces excess error by factor q, implying exponential (geometric) decay in depth in that regime.
• Classification results: The improved O(M^2/D) upper bound holds for logistic agents (BCE, logits passed). The Gaussian transfer theorem (Theorem 7) shows for Gaussian inputs with logistic link, agent logits are proportional to least-squares predictors, and losses map between MSE and BCE bounds; hence the regression lower-bound instances carry over.

Data & Methods

• Nature of results: fully theoretical / population-level (no empirical training-sample noise). Assumptions typically include bounded second moments of features and bounded ℓ1 norm of the optimal linear weights; analyses work in the population loss setting.
• Main technical tools and constructions:
  • Inductive tightening of the pigeonhole/block-drop argument used by Kearns–Roth–Ryu to convert a block-wise small drop into a tighter global rate (key to O(M^2/D)).
  • Careful spectral/basis change analysis for the cyclic example: rewrite in orthonormal basis {z_i}, derive recursion for residual mass, relate to a random walk encoded by Catalan-type combinatorics to get Ω(1/√p).
  • Depth-dependent Gaussian construction: features are small-rotation perturbations of a hidden direction so successive agents only remove an O(ρ^2 sin^2 δ) fraction of residual, choose ρ^2 = Θ(M^2/D) to make residual survival produce Ω(M^2/D) excess.
  • Geometric contraction proof: for fixed finite distributions, examine each M-consecutive-agent block (which spans all features) to show a block-wise multiplicative improvement q < 1; finite feature subset space ensures a global q works.
  • Gaussian transfer for classification: show single-agent BCE minimizer lies on the line spanned by least-squares predictor when targets are logistic of a Gaussian linear function; induct topologically to extend to the network and bound BCE excess in terms of MSE excess.
• Scope/limitations of methods:
  • Lower-bound constructions are Gaussian and may depend on depth D (i.e., worst-case distributions change with required depth).
  • All results are population-level (infinite-sample) and assume exact empirical minimizers—finite-data/sample-complexity effects are not the focus.

Implications for AI Economics

• Quantifies the depth vs. accuracy tradeoff and cost of agentic chaining:
  • Formula: to achieve excess error ≤ ε, a sufficient depth is D = Θ(M^2 / ε). Thus marginal cost of reducing excess error scales linearly in 1/ε and quadratically in M.
  • If each hop/agent has a monetary or latency cost c, total cost to reach ε is roughly c·D = Θ(c·M^2 / ε). Designing systems therefore requires weighing per-hop marginal cost against the quadratic dependence on coverage M.
• Design prescriptions for multi-agent pipelines and federated/vertical setups:
  • Minimize M (the number of consecutive agents needed to cover all features): smaller M (more frequent / overlapping coverage of raw features) reduces both constant floors and asymptotic cost (since excess ∝ M^2 / D). Practically, ensure features needed to predict critical signals are reintroduced more often down the chain.
  • If reducing M is expensive/unavailable, realize that shallow chains (D ≤ M^2) may exhibit a constant error floor — additional small increases in D may produce little benefit until depth reaches ~M^2.
  • If depth (number of hops) is costly, consider richer messages than a single scalar (e.g., passing multiple summary statistics, compressed feature embeddings, or small vector representations) to speed aggregation beyond the scalar-prediction limitation studied here.
• Policy and economic implications:
  • For systems where each hop incurs cost (compute, latency, privacy overhead), the analysis gives planners concrete scaling laws to budget depth vs. accuracy: e.g., halving the excess error roughly doubles the needed D (given fixed M).
  • For vertically partitioned data (vertical federated learning), the results suggest structuring the order or overlap of parties so that “coverage M” is small, or investing in protocols that allow richer intermediate information sharing to avoid the M^2/D bottleneck.
• Robustness and practical caveats:
  • The model assumes linear predictors and population loss minimization; real-world agents (nonlinear models, finite data, stochastic optimization) may behave differently. Still, the scaling laws give a useful baseline for expected returns to adding hops or changing feature coverage.
  • The worst-case slow instances are engineered (Gaussian, depth-dependent); for a fixed real-world distribution, error typically contracts geometrically in blocks of M, so practical systems may converge faster than worst-case bounds indicate.
• High-level takeaway for AI economics: when orchestrating chains of specialized agents, the structure of feature coverage (M) matters at least as much as depth (D). Achieving low excess error cheaply requires either (a) small M (frequent/full reintroduction of raw signal), (b) sufficiently large depth (D ≳ M^2), or (c) richer intermediate messaging to break the scalar-prediction bottleneck.