PaperlayerView exact revision on arXiv

Source-linked AI summary

SpatialPC: Deep Computation with Sublinear Local Credit Propagation

Benjamin Prada, Shion Matsumoto, Ankur Arjun Mali

arXiv:2610.36139v1cs.LG

TL;DR

Local learning on a chain couples credit latency to depth, leaving open how much bounded-range spatial geometry can reduce that latency. SpatialPC constructs a circuit with long represented depth but short credit reachability, and propagates credit through local adjoint prediction dynamics. The paper proves the separation tight and reports aligned finite-round gradients and benchmark results.

  • Problem

    On a chain, bounded-range local learning needs Θ(N) rounds for loss information to reach early parameters, and the latency limit for local rules on spatial layouts was not established.

    Source: §1 · pp. 1–2

  • Method

    SpatialPC compiles a long Hamiltonian computation onto a bounded-degree spatial graph and uses local adjoint prediction dynamics to propagate credit.

    Source: §1 · p. 2, §8 · p. 18

  • Results

    The tight separation is Θ(N^(1−1/d)); at N = 256, gradient cosine is 0.93 on MNIST and 0.97 on Fashion-MNIST, matching a depth-128 backpropagation reference.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Communication cost for credit assignment can be chosen through graph design rather than inherited from computation depth.

    Source: §9 · p. 19

    The bounds apply under bounded range, bounded degree, and constant density; global broadcasts, growing interaction range, or reduction trees fall outside that model.

    Source: §4.3 · p. 8, §8 · p. 17

Abstract

from arXiv · show

On a chain of $N$ states, any local learning rule with bounded communication range needs $\Theta(N)$ rounds before the loss can influence the earliest parameters, and this latency is usually attributed to depth. We show that it is a property of the communication geometry rather than of depth. For $N=m^d$ states placed at constant density in $d$ dimensions, a light-cone argument gives an $\Omega(N^{1/d})$ lower bound on the number of bounded-range rounds that any local algorithm needs before its gradient estimates can be sign-correct at every parameter. We construct a unit-range, degree-$2d$ directed acyclic graph that contains a Hamiltonian computation of length $N-1$ and in which every state lies within directed distance $d(m-1)=\Theta(N^{1/d})$ of the output, matching the lower bound. In the realizable-circuit model, depth and credit depth are therefore independent parameters: represented depth $\Theta(N)$ and causal credit latency $\Theta(N^{1/d})$ coexist, with a separation of order $N^{1-1/d}$. SpatialPC realizes this separation within predictive coding. Credit is propagated by adjoint prediction dynamics (APD), a local update whose $K$-round state on a settled acyclic graph is the truncated reverse-path sum $a^K=\sum_{k<K}(J^\top)^k b$, with error exactly $(J^\top)^K a^\star$. Graph geometry fixes when credit can first arrive at a state; the Jacobian-weighted path tail fixes how many further rounds accurate credit requires. A sparse two-dimensional Moore compiler retains the $N-1$ backbone with $\tfrac32N-2$ unit-range edges and has measured worst-node reachability $\sqrt N+2$ up to $N=65{,}536$, where a 65,535-edge backbone is reached in 258 local hops. With $T=2\sqrt N$ rounds, SpatialPC keeps finite-round task gradients aligned with settled gradients (cosine $0.93$ on MNIST and $0.97$ on Fashion-MNIST at $N=256$) and reaches $97.6\%$ and $88.1\%$ test accuracy after 20 epochs.

1 Introduction

Local learning on a chain ties credit latency to computation depth, but spatial geometry can shorten the path from loss to parameters without shortening the represented computation. SpatialPC combines this separation with local predictive-coding updates and reports aligned finite-round gradients and benchmark results.

1 Introduction

  • On a chain, local rules need Θ(L) rounds for loss information to reach the earliest parameters, motivating work on dynamics that still inherits the chain's communication distance.The paper instead treats the chain's geometry as a design choice.Source: §1 · p. 2
  • A light-cone lower bound and a unit-range compiler establish tight Θ(N^(1/d)) credit latency while retaining an N −1 computation, making depth and credit depth independent.The compiler has degree at most 2d and directed distance d(m −1) to the output.Source: §1 · p. 2
  • APD sums reverse paths shorter than K on a settled graph; reachability sets first arrival, while Jacobian-power decay determines further rounds needed for accurate credit.The K-round error is (J⊤)^K a⋆.Source: §1 · pp. 2–3
  • At N = 256, gradient cosine is 0.93 on MNIST and 0.97 on Fashion-MNIST; after 20 epochs, test accuracy is 97.64% and 88.10%, matching a depth-128 backpropagation reference.The measurements use N synchronous rounds.Source: §1 · p. 2
  • The sparse two-dimensional compiler retains the N −1 backbone with 3/2N −2 unit-range edges and measured worst-node reachability √N +2 through N = 65,536.The paper also reports gradient cosine rising from 0.35 to 0.93 with the feasibility weight at constant accuracy, with fidelity improving beyond Dreach.Source: §1 · p. 3

2 Related Work

The related work spans local learning rules, predictive coding, realizable circuit complexity, parallel differentiation, and spatial traversals. The paper distinguishes approaches that change credit dynamics on a given graph from its approach of changing the graph's layout.

Local learning rules

  • Equilibrium propagation, forward-forward, and random-feedback rules use local information, but output signals still cross layers one at a time; synthetic gradients avoid that dependence at the cost of learned approximation and locality [7] [8] [26].The paper's locality model covers these rules and its lower bound applies to them.Source: §2 · pp. 3–4

Predictive coding on graphs and at scale

  • Predictive coding extends to arbitrary graph topologies and recovers reverse-mode gradients at equilibrium [12] [13]; prior scaling work changes dynamics on a given graph, whereas this work changes the graph.The paper says its approach can be combined with those methods.Source: §2 · p. 4

Realizable circuit complexity

  • Realizable circuit complexity bounds circuits embedded in d-dimensional space under causality and bounded information flux; this paper singles out represented depth and credit depth within that model [23].Its light-cone proof combines a causal-ball argument with indistinguishability reasoning from distributed computing.Source: §2 · p. 4

Parallel differentiation and implicit models

  • Parallel differentiation can reduce span using long-range reductions or operator composition, which bounded-range substrates lack; SpatialPC instead differentiates through finite local unrolling and penalizes terminal residual [32] [33].Hilbert and Moore curves preserve spatial locality, while this paper's traversals use oriented shortcuts to give each point a short directed route to the output.Source: §2 · p. 4

3 Preliminaries

The preliminaries formulate predictive coding as constrained optimization, derive local adjoint prediction dynamics, and distinguish computation depth from communication reachability depth.

3 Preliminaries

  • The preliminaries set up the paper's separation between a graph's computational length and the communication rounds required for loss information to reach its states.The subsequent result states that no local algorithm improves on the d-dimensional reachability scaling.Source: §3 · p. 4, §3.3 · p. 5

3.1 Predictive coding as constrained optimization

  • Predictive coding treats a feedforward state as satisfying zero prediction residual and relaxes the constraints with a quadratic penalty, alternating local state inference and parameter updates [12].Each non-input state is predicted from its parents, with a local prediction error.Source: §3.1 · pp. 4–5

3.2 Adjoint prediction dynamics

  • APD solves the adjoint equation a = b + J⊤a through synchronous local updates; for a linear edge, the parameter-gradient block is the postsynaptic adjoint times presynaptic activity, scaled by edge gain.The same stationarity condition appears in augmented-Lagrangian predictive coding.Source: §3.2 · p. 5

3.3 Represented depth and reachability depth

  • Represented depth is the longest directed computation, whereas reachability depth is the largest shortest-path distance from a node to the output.A message moving one edge per round cannot reach every node before Dreach rounds; on a chain, both depths equal N −1.Source: §3.3 · p. 5

4 Spatial Compilation: Linear Depth with Sublinear Reachability

Spatial compilation separates computation length from communication distance: a bounded-range grid can retain a Hamiltonian computation of length N−1 while bringing every state within Θ(N^1/d) directed hops of the output. A light-cone lower bound makes this reachability scale unavoidable for local credit assignment.

4.1 Realizable circuits and the compilation problem

  • The compiler model fixes a length-N−1 computational backbone and seeks bounded-range shortcut edges that minimize the rounds until every state can receive output-generated information.It assumes constant-density substrates, bounded communication range and degree, and targets written only at output sites.Source: §4.1 · p. 6

4.2 Upper bound: the snake-ordered grid

  • In the snake-ordered grid DAG, every vertex’s directed distance to output vout equals its ℓ1 distance, so maximum directed depth is d(m−1); edges have unit length and vertex degree at most 2d.Source: §4.2 · p. 7

4.3 Lower bound: a light cone for loss information

  • A light-cone lower bound requires Ω(N^1/d) rounds for any bounded-range local learner to deliver sign-correct estimates at every loss-sensitive parameter.The bound applies to every local algorithm, whether or not it follows a fixed computation graph.Source: §4.3 · p. 8

4.4 The sparse Moore compiler

  • For even m with N = m², the Moore-curve compiler uses an N−1-edge backbone, a retained cut edge, and separating unit-grid edges; its maximum undirected degree is four, with unit-length edges only.Source: §4.4 · p. 8

5 SpatialPC: Local Dynamics on the Compiled Graph

SpatialPC runs synchronous local dynamics for a fixed round budget on a compiled graph, then computes the exact gradient of that finite-round objective with local adjoint prediction dynamics. Its predictive-coding formulation uses a feasibility penalty, not a relaxation-based inference phase.

5 SpatialPC: Local Dynamics on the Compiled Graph

  • SpatialPC trains the finite-round predictor and uses APD to obtain the exact gradient of that fixed-round objective, with operations local to graph edges.The separation between represented depth and reachability permits a round budget of order N^1/d rather than N.Source: §5 · p. 9, §5.3 · p. 11

5.1 Synchronous forward dynamics

  • The synchronous forward iteration reaches the settled state only after Dseq+1 rounds; before then, the state is a path-length-truncated computation.SpatialPC instead trains the T-round state to be nearly a fixed point.Source: §5.1 · p. 10

5.2 Finite-round objective

  • The finite-round objective adds the predictive-coding energy at hT as a residual that is zero exactly when hT is a fixed point of Fθ.The objective’s gradient is then computed by the local mechanism for the settled problem.Source: §5.2 · p. 10

5.3 Exact gradients by APD on the space–time graph

  • APD on the unrolled space–time graph computes the exact gradient through reverse messages along the same spatial edges used in the forward pass.The reverse recursion is reverse-mode differentiation of the unrolled computation, rather than an approximation at an inference equilibrium.Source: §5.3 · p. 11, §5.4 · p. 11

5.4 Relation to predictive coding

  • SpatialPC is predictive coding with finite-round states and separate adjoint credit, not a relaxation-based network with a clamped-output inference phase.The PC energy is a penalty that pulls the finite-round state toward a fixed point; the local rule itself is unchanged.Source: §5.4 · p. 11

6 Credit Fidelity Beyond Reachability

APD accumulates credit by reverse-path length, separating the graph-determined arrival time from the Jacobian-determined accuracy of the credit. The feasibility residual also connects the truncated forward state to its settled counterpart.

6.1 Finite reverse-path expansion

  • After K rounds, APD has accumulated reverse paths of length less than K, and its remaining error is the settled adjoint propagated through K further edges.The size of the omitted credit depends on the Jacobian-weighted path tail, not just the shortest path.Source: §6.1 · p. 12

6.2 Causal arrival and the effective credit radius

  • Output-dependent credit cannot appear at v before the (dO(v)+1)st APD iterate, and Dreach+1 iterates are necessary for every state to carry nonzero credit.This is a causal-arrival condition; additional rounds may be needed for accurate credit.Source: §6 · p. 11, §6.2 · p. 12

6.3 From adjoint error to update fidelity

  • For local linear parameter blocks, bounding adjoint error by the global tolerance bounds the angle between each local update and its settled update by arcsin ϵ.The effective credit radius depends on both the learned Jacobian and the loss forcing, unlike graph-only Dreach.Source: §6.2 · p. 12, §6.3 · p. 13

6.4 Forward–reverse duality and the residual as a certificate

  • For affine dynamics, the feasibility residual is the first omitted forward-path shell and provides a computable certificate of distance from the settled state.For the nonlinear dynamics used in practice, the identities hold to first order about hT when the residual is small.Source: §6.4 · p. 13

7 Experiments

The experiments test whether spatial compilation preserves a long computation while reducing causal reachability, and whether finite-round credit remains useful during training. Structural scaling, gradient fidelity, feasibility, round-budget, and training measurements address these claims.

7.1 Setup

  • The reference uses a 16 × 16 Moore graph with N = 256, width 128, and 32 rounds; results average three seeds on standard MNIST and Fashion-MNIST splits.Gradient cosine compares finite-round APD task gradients with settled task gradients of the same network.Source: §7.1 · pp. 13–14

7.2 Structural scaling to 65,536 states

  • At N = 65,536, the Moore compiler retains a 65,535-edge backbone with worst-node output distance 258, and the structural separation reaches 254×.Across measured sizes, Dseq = N −1 and the separation follows the N^1/2 exponent.Source: §7.2 · p. 14

7.3 Gradient fidelity under a geometric round budget

  • With T = 2√N, MNIST gradient cosine reaches 0.928 at N = 256, while Fashion-MNIST reaches 0.974.At N = 256, the forward computation receives 32 rounds despite a 255-edge backbone.Source: §7.3 · p. 15, Table 2 · p. 15

7.4 Feasibility controls credit accuracy

  • At N = 256 and T = 32, raising λ from 0 to 100 increases MNIST gradient cosine from 0.353 to 0.928 while accuracy changes from 92.67% to 92.75%.Residual RMS falls from 0.0245 to 0.0079; Fashion-MNIST shows the same pattern, with cosine rising from 0.628 to 0.974.Source: §7.4 · p. 15, Table 3 · p. 16

7.5 Fidelity continues to improve past causal arrival

  • On Fashion-MNIST, increasing T from 8 to 64 raises gradient cosine from 0.795 to 0.990, even though all states are reachable once T > 18.On MNIST, cosine reaches 0.955 at T = 64, with a small non-monotonicity at T = 32.Source: §7.5 · p. 15, Table 4 · p. 16

7.6 Twenty epochs of training

  • The 20-epoch evaluation compares N = 256, T = 32 SpatialPC-v1 models with a depth-128, width-128 chain trained by backpropagation.Finite-round and settled accuracies stay within one point, while gradient cosine drifts downward during training despite flat or decreasing residual.Source: §7.6 · pp. 15, 17
  • After 20 epochs, SpatialPC-v1 reaches 97.64% on MNIST and 88.10% on Fashion-MNIST versus 97.55% and 88.03% for the backpropagation reference.At epoch 20, task-gradient cosines are 0.883 and 0.920, respectively.Source: §7.6 · p. 17, Figure 4 · p. 17

7.7 Chain control and external baselines

  • With T = 32, a 256-state chain stays at chance because input information does not reach its output in fewer than 256 rounds; at matched widths, SpatialPC-v1 leads at H ≤32 and is within one point of backpropagation at H = 128.The chain control also changes depth-dependent residual scaling, so it is not an isolated topology intervention.Source: §7.7 · p. 17

8 Discussion

The discussion separates communication latency from computation depth and distinguishes credit arrival from credit accuracy. It also describes the bounds’ scope, practical costs, and unresolved questions about the compiler and credit dynamics.

8 Discussion

  • The bounds apply under bounded range, bounded degree, and constant density; global broadcast, reduction trees, growing-range interactions, and synthetic gradients fall outside their scope.Within the model, dimensional embedding reduces chain latency without shortening the computation, but the bounds do not specify accuracy after credit arrives.Source: §8 · pp. 17–18
  • At N = 256, every state is reachable after 18 rounds, but gradient fidelity continues improving through T = 64 because accuracy depends on the Jacobian-weighted tail.The bounds constrain causal availability, not accuracy after arrival; the tail depends on learned weights and the task.Source: §8 · p. 18
  • The T-round circuit has width N and depth T, while its wiring supports represented depth N −1; at T = 2√N, its function uses paths of length at most T −1.The T-round function is a truncation, and the feasibility penalty trains it to be self-consistent.Source: §8 · p. 18
  • Spatial compilation reduces reachability depth, while changing the credit dynamics shortens the gap between reachability and accurate credit; the two interventions can be composed.For relaxation-based models, comparing Rϵ with Dreach separates distance-driven latency from latency due to the Jacobian tail.Source: §8 · pp. 18–19
  • The synchronization saving is not an arithmetic saving: each round costs O(|E|H2) operations, so T rounds perform T times one topological sweep’s work.A parameter update uses 2T + 2 local message phases, with T on the order of Rϵ.Source: §8 · p. 19
  • Open questions include proving the Moore reachability identity for all k, determining optimal reach with O(N) edges, and measuring how much of the long backbone trained circuits use.The experiments measure Rϵ through gradient alignment only up to N ≤ 256; its growth with N remains open.Source: §8 · p. 19

9 Conclusion

The conclusion presents communication geometry as the determinant of local credit latency, distinct from computation depth, and reports that SpatialPC retains aligned finite-round gradients and matches a backpropagation reference. The appendix collects proofs, derivations, implementation checks, controls, and pseudocode.

9 Conclusion

  • The compiler preserves an N −1 Hamiltonian computation while reducing causal credit latency to Θ(N 1/d), the tight bound for local algorithms in the stated model.SpatialPC realizes the separation with an exact edge-local gradient, while its path-length expansion distinguishes reachability from the effective credit radius.Source: §9 · p. 19
  • At O(√N) round budgets, trained models keep finite-round gradients aligned with settled gradients and match a depth-128 backpropagation reference on MNIST and Fashion-MNIST.The conclusion describes the compiler as defined for every dimension and the analysis as applying to any local rule.Source: §9 · p. 19

Appendix

  • The appendix provides proofs and protocols, derives finite-round APD, checks the implementation against automatic differentiation, and includes controls, sweeps, and pseudocode.It also relates the adjoint equation to augmented-Lagrangian predictive coding.Source: Appendix · p. 23

A.1 Proof of Theorem 4.5

The proof uses the snake-ordered grid traversal to establish local forward progress toward the output. A separate measurement reports the Moore compiler’s reverse eccentricity at implemented sizes, while noting that its general identity remains unproved.

A.1 Proof of Theorem 4.5

  • Theorem 4.5 supplies the step used by Theorem 4.6: from every snake-ordered grid point, a forward edge moves one unit closer to the output.The proof treats the first and last points of the traversal through two inductive statements.Source: §A.1 · p. 23
  • The traversal alternates each slab’s order with its reversal, and the proof uses induction on dimension to identify a unit neighbor later in the order.The base case uses adjacent positions on the one-dimensional traversal.Source: §A.1 · p. 23

A.2 Reverse eccentricity of the Moore output

  • The Moore output’s maximum reverse distance is m + 2 at every implemented size, but the identity is not proved for all k.The measurements use breadth-first search on the reversed graph; proving the identity would require tracking the cut’s position relative to the curve’s recursive structure.Source: §A.2 · p. 23

B Derivation of Finite-Round APD

The appendix derives the finite-round APD recursion from stationarity of a constrained objective, proves a gradient-angle bound, and relates APD’s fixed point to augmented-Lagrangian predictive coding while distinguishing their dynamics.

B Derivation of Finite-Round APD

  • The finite-round objective combines task loss with a feasibility penalty under time-indexed state-transition constraints; stationarity gives the adjoint recursion used by the gradient algorithm.The appendix identifies the feasibility contribution at hT and derives at = J⊤t at+1 for t < T.Source: B Derivation of Finite-Round APD · p. 24

C Proof of the Gradient-Angle Bound

  • The gradient-angle proof establishes cos ∠(x, y) ≥ 1 − ϵ2 when v = x + δ and ∥δ∥ ≤ ϵ∥x∥, with the bound attained at a tangent point.For edge gradients sharing the same nonzero z, the Frobenius-angle cosine equals the state-vector angle cosine.Source: C Proof of the Gradient-Angle Bound · p. 24

D Connection to Augmented-Lagrangian Predictive Coding

  • APD and augmented-Lagrangian predictive coding share the state-stationarity fixed point, but differ in dynamics: APD computes the finite-round objective’s exact gradient in T reverse rounds without relaxation or a feasibility requirement.PC-ALM instead approaches the condition through primal–dual relaxation of states and multipliers.Source: D Connection to Augmented-Lagrangian… · p. 25

E Numerical Verification of the Implementation

The implementation check finds finite-round APD gradients numerically match automatic differentiation across eight configurations. A matched chain control has zero task gradient because its output receives no input information within 32 rounds, making it a qualitative reference rather than an isolated topology comparison.

E Numerical Verification of the Implementation

  • Gradient cosine is 1.0 to displayed precision and relative error is below 2.9 × 10−16 across eight finite-round APD and PyTorch autograd configurations.Stationary APD also reproduces settled backpropagation gradients with relative error below 3.4 × 10−16 for both tested protocols.Source: E Numerical Verification of the… · p. 25, Table 6 · p. 25

F Secondary Experiments

  • The secondary experiments compare the Moore model with chain baselines matched on width, optimizer, and epoch budget, while varying topology.The chain baselines share SpatialPC’s width, optimizer, and epoch budget.Source: F Secondary Experiments · p. 25, §F.1 · p. 25

F.1 Chain control

  • At N = 256 and T = 32, the chain output receives no input information, so its task gradient is zero and reported accuracy equals each test set’s class-0 frequency.The comparison also changes depth-dependent residual scaling, so it is a qualitative reference rather than an isolated topology intervention.Source: §F.1 · p. 25, Table 7 · p. 26

F.2 Activation ablation

The activation ablation reports a trade-off: tanh has slightly lower accuracy but consistently higher gradient cosine than ReLU. The accompanying width sweep compares SpatialPC with depth-128 chain baselines, and the algorithms describe graph construction, forward computation, and APD training.

F.2 Activation ablation

  • Tanh gives slightly lower accuracy and consistently higher gradient cosine than ReLU for both protocols at the reference configuration.The passage relates this pattern to a smaller Jacobian norm and faster path tail.Source: §F.2 · p. 26, Table 8 · p. 26

F.3 External width sweep

  • The one-epoch width sweep compares SpatialPC on the N = 256 Moore graph with depth-128 chain baselines across hidden widths H ∈ {8, 16, 32, 64, 128}.The Moore graph has 3/2N − 2 edges versus N − 1 for the chain, so edge count and topology both differ.Source: §F.3 · p. 26, Table 9 · p. 26

G Algorithms

  • The algorithms construct the Moore DAG, compute settled or T-round partial states, and evaluate SpatialPC gradients with APD on the T-round space-time graph.The compiler cuts a Moore cycle to define a topological order, retaining backbone edges and eligible forward-oriented unit-grid shortcuts.Source: G Algorithms · pp. 27–29
Loading 2610.36139v1…