Cost Accounting for Reactive Computational Graphs: Exhaustive Sweeps, Sequential Mutation, and the Backward-Locality Gap

Technical Summary: Cost Accounting for Reactive Computational Graphs

Problem Statement
Mechanistic interpretability and robustness analysis rely heavily on "sweep" workloads: exhaustively patching or ablating candidate sites within a neural network's computational graph to measure their causal impact. In standard eager frameworks (e.g., PyTorch) or compiled pipelines (e.g., JAX, torch.compile), these interventions typically trigger a full recomputation of the forward pass (or a re-trace of the program) for every candidate site. This approach ignores partial validity, paying a cost proportional to the entire graph size regardless of how localized the intervention is. While reactive graph engines (like NeuroDSL) maintain persistent graphs where mutations invalidate only the "downstream cone" of the modified node, the aggregate cost of performing an exhaustive sweep or a sequence of persistent mutations on such engines remained unquantified. Specifically, it was unclear how much speedup an exhaustive sweep could achieve over independent full recomputations, how the distribution of computational weight across network depth affects this speedup, and how the cost behaves under sequential versus batched mutation schedules.

Methodology
The paper employs a rigorous combinatorial accounting framework grounded in the structural properties of Directed Acyclic Graphs (DAGs) and the theory of regularly varying sequences (Karamata indices).

1. Theoretical Foundation: The analysis builds upon a "Structural Locality Theorem" (Theorem 1), which proves that in a reactive engine, a mutation at node $s$ invalidates exactly the set of nodes $V^+_s$ (the downstream cone) reachable from $s$.
2. Aggregate Modeling: The authors model the network as a layered DAG with a computational weight profile $w_j$ per layer. They define the "aggregate sweep ratio" $\rho(L)$ as the cost of $S \cdot L$ independent full recomputations divided by the cost of an exhaustive sweep using exact cone recomputation.
3. Asymptotic Analysis: Using Karamata's theorem for regularly varying sequences, the paper derives the limit of $\rho(L)$ as the network depth $L \to \infty$, parameterized by the Karamata index $q$ of the cost distribution.
4. Sequential vs. Batched Analysis: The cost of sequential persistent grafts (where mutations are not undone) is analyzed by tracking the union of invalidation cones. The paper distinguishes between "interleaved" execution (full evaluation between grafts) and "batched" execution (all grafts applied before evaluation).
5. Backward Pass Analysis: The framework is extended to backpropagation by defining the "upstream cone" ($V^-_s$) and analyzing the intersection of forward and backward invalidation sets.
6. Empirical Validation: All theoretical claims are validated against a reference implementation in NeuroDSL (a reactive define-and-run graph engine in Julia). Measurements include wall-clock timing for interpreter overhead and exact integer counts of invalid nodes for combinatorial identities.

Key Contributions

1. Aggregate Sweep Speedup is Not Universal:
   The paper proves that the speedup of an exhaustive sweep over full recomputations is not a constant (e.g., 2) but depends on the network's cost distribution.

   • If computational weight is concentrated near the output (output-heavy, index $q$), the speedup converges to $(q+2)/(q+1)$.
   • If weight is concentrated near the input (input-heavy), the speedup converges to $q+2$.
   • Only in the depth-uniform case ($q=0$) does the speedup converge to exactly 2.
   • Wall-Clock Refinement: When accounting for fixed interpreter overhead (measured as $\beta \approx 0.0054$ ms/node), the practical wall-clock ceiling for uniform graphs drops to $\approx 1.79$, strictly below the combinatorial limit of 2.

2. Exact Cost of Sequential and Batched Mutations:

   • Sequential (Interleaved): For a sequence of $K$ persistent grafts, the total cost is the sum of isolated costs plus an overcount term $\Delta(\pi) \ge 0$. This overcount depends on the insertion order $\pi$ and the number of grafts applied to sites that are downstream of previously grafted sites. The cost is minimized by applying grafts in "shallowest-first" order and maximized by "deepest-first."
   • Batched: If all grafts are applied before any evaluation, the cost is order-independent and sub-additive. It equals the size of the union of all downstream cones plus the fresh nodes, strictly less than the sum of isolated costs if any sites are comparable.

3. The Backward-Locality Gap:
   The paper proves that the locality theorem has an exact mirror for the backward pass (upstream cones). However, on architectures without long skip connections (e.g., standard sequential Transformer stacks), a mutation's upstream cone covers almost the entire graph. Consequently, the aggregate speedup of an exhaustive sweep under backpropagation collapses to 1. This result precisely delimits the utility of reactive locality: it applies fully to inference-time sweeps (activation patching, circuit discovery) but offers no aggregate speedup for training-mode sweeps on sequential architectures.

4. Zero-Tolerance Empirical Validation:
   The paper validates its claims on NeuroDSL with zero tolerance for combinatorial identities and convergence for asymptotic limits:

   • Measured sweep ratios on real graphs converge to the predicted limits for four non-uniform cost profiles.
   • Training-mode ratios collapse to 1 at the predicted rate.
   • All 18 per-graft sequential costs and batched totals match the closed-form predictions exactly across different insertion orders.

Significance and Claims
The paper claims to provide the first exact, closed-form cost accounting for reactive graph workloads, replacing the heuristic assumption that "every intervention costs a full pass" with precise combinatorial identities.

• It establishes that the efficiency of mechanistic interpretability tools (like activation patching) is a function of the network's depth-weight profile, not just the engine's reactivity.
• It clarifies the operational boundary of reactive engines: they provide significant speedups for inference-time causal analysis but do not accelerate exhaustive training-time searches on standard sequential architectures.
• It offers practical guidance for implementation: batching mutations eliminates order-dependent overhead, and compiler layers that remove interpreter overhead ($\beta$) are required to reach the theoretical combinatorial speedup limits.

The authors explicitly state that these results are derived from the properties of the NeuroDSL engine and the specific "downstream cone" invalidation model. They do not claim these results apply to frameworks that do not maintain persistent validity flags or to architectures with long skip connections that violate the layering assumptions of the cost model.