Paper deep dive
Cost Accounting for Reactive Computational Graphs: Exhaustive Sweeps, Sequential Mutation, and the Backward-Locality Gap
Abdallah Khemais
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 7/22/2026, 2:16:10 AM
Summary
This paper provides a rigorous cost accounting for reactive computational graphs, specifically analyzing the efficiency of exhaustive sweeps, sequential mutations, and backpropagation. It proves that the speedup of exhaustive sweeps over independent recomputations depends on the Karamata index of the network's depth-weight profile, converging to (q+2)/(q+1) or q+2. It also derives exact formulas for the cost of sequential and batched persistent mutations, showing that interleaved costs include an overcount based on comparable site pairs, while batched costs are sub-additive. Finally, it demonstrates that the backward pass locality causes sweep speedup to collapse to 1 in architectures without long skip connections. These theoretical results are validated on the NeuroDSL reactive graph engine in Julia.
Entities (7)
Relation Signals (6)
NeuroDSL → implements → Reactive Graph Invalidation
confidence 95% · NeuroDSL keeps the computational graph as a persistent DAG... a mutation triggers an invalidation wave provably confined to the mutated node’s downstream cone
Backward Pass → causesspeedupcollapse → 1
confidence 90% · it forces the aggregate sweep speedup to collapse to 1 under backpropagation on architectures without long skip connections
Sequential Mutation → hascostformula → Isolated Sum + Overcount
confidence 90% · the interleaved cost exceeds the isolated sum by an exact overcount summed over comparable site pairs
Batched Grafting → hascostproperty → Sub-additive
confidence 90% · batched application is order-independent and sub-additive, costing exactly the union of the sites’ cones plus the fresh nodes
Exhaustive Sweep → hasspeeduplimit → (q+2)/(q+1)
confidence 90% · the aggregate speedup of an exhaustive sweep... converges to (q+2)/(q+1) when weight concentrates near the output
PyTorch → lacksfeature → Partial Validity
confidence 85% · Neither maintains a notion of partial validity: the framework cannot distinguish the subgraph whose cached values are still correct
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Exhaustive site-by-site interventions on a neural network's computational graph -- activation-patching sweeps, circuit-discovery searches, systematic ablation studies -- mutate the graph at every candidate site, and their cost is dominated by recomputation after each mutation. On a reactive graph engine whose invalidation provably touches exactly the downstream cone of a mutated node, we give a complete cost accounting for such workloads. First, the aggregate speedup of an exhaustive sweep over independent full recomputations is not a universal constant: if per-layer weight varies regularly with depth at Karamata index q, the ratio converges to (q+2)/(q+1) when weight concentrates near the output and to q+2 near the input, recovering 2 only in the depth-uniform case; a wall-clock corollary predicts a ceiling of about 1.79, below 2, until interpreter overhead is compiled away. Second, we prove the exact cost of a sequence of persistent mutations, never undone between insertions: the interleaved cost exceeds the isolated sum by an exact overcount summed over comparable site pairs, with closed-form extremes over insertion orders, while batched application is order-independent and sub-additive, costing exactly the union of the sites' cones plus the fresh nodes. Third, we prove the exact mirror of forward locality for the backward pass, showing it collapses the aggregate speedup to 1 under backpropagation on architectures without long skip connections. Every identity is validated on NeuroDSL, a reactive graph engine in Julia: measured sweep ratios converge to the predicted limits under four cost profiles; the training-mode ratio collapses to 1 at the predicted rate; and all 18 per-graft sequential costs and the batched total match the closed forms at zero tolerance across three insertion orders.
Tags
Links
- Source: https://arxiv.org/abs/2607.18323v1
- Canonical: https://arxiv.org/abs/2607.18323v1
Trouble viewing inline? Open PDF directly →
Full Text
41,905 characters extracted from source content.
Expand or collapse full text
Cost Accounting for Reactive Computational Graphs: Exhaustive Sweeps, Sequential Mutation, and the Backward-Locality Gap Abdallah Khemais ISITCOM, University of Sousse (July 2026) Abstract Exhaustive site-by-site interventions on a neural network’s computational graph — activation-patching sweeps, circuit-discovery searches, systematic ablation studies — mutate the graph at every candidate site in turn, and their cost is dominated by recomputation after each mutation. On a reactive graph engine whose invalidation provably touches exactly the downstream cone of a mutated node, we give a complete cost accounting for such workloads. First, the aggregate speedup of an exhaustive sweep over independent full recomputations is not a universal constant: if per-layer computational weight varies regularly with depth with Karamata index q, the ratio converges to (q+2)/(q+1)(q+2)/(q+1) when weight is concentrated near the output and to q+2q+2 when concentrated near the input, recovering 22 only in the depth-uniform case; a wall-clock corollary computed from measured interpreter constants predicts a ceiling of ≈1.79≈ 1.79, strictly below 22, until interpreter overhead is compiled away. Second, we prove the exact cost of a sequence of persistent mutations, never undone between insertions: the interleaved cost exceeds the sum of isolated costs by an exact overcount Δ(π)≥0 (π)≥ 0 summed over comparable site pairs, with closed-form extremes over insertion orders, while batched application is order-independent and sub-additive, costing exactly the union of the sites’ downstream cones plus the fresh nodes. Third, we prove the exact mirror of forward locality for the backward pass and show it forces the aggregate sweep speedup to collapse to 11 under backpropagation on architectures without long skip connections — delimiting precisely the regime (inference-time sweeps) where the speedup applies undiminished. Every identity is validated on the reference implementation in NeuroDSL [3], a reactive define-and-run graph engine in Julia: measured sweep ratios on real graphs converge to the predicted limits under four non-uniform cost profiles (E4); the training-mode ratio collapses to 11 at the predicted rate (E5); and all 1818 per-graft sequential costs and the batched total match the closed forms at zero tolerance across three insertion orders (E7). 1 Introduction The workhorse of mechanistic interpretability is the sweep: patch or ablate each candidate site of a trained network in turn, measure the effect on a metric, restore the baseline, and move to the next site. Circuit-discovery searches, causal-tracing protocols, and systematic robustness checks all share this shape, and their cost is dominated not by the mutation itself — overwriting one activation or one rule is cheap — but by the recomputation each mutation forces before the metric can be read, multiplied by the number of candidate sites, which grows with model size. How much of that recomputation is actually necessary depends on the execution model. Eager frameworks such as PyTorch [1] re-run the full forward pass per intervention; compiled pipelines (torch.compile, jax.jit [2]) may additionally re-trace when the intervention changes the traced program. Neither maintains a notion of partial validity: the framework cannot distinguish the subgraph whose cached values are still correct from the subgraph invalidated by the intervention. A reactive graph engine can. NeuroDSL [3] keeps the computational graph as a persistent DAG in which nodes own their cached values and a mutation triggers an invalidation wave provably confined to the mutated node’s downstream cone — a single-mutation locality theorem restated as Theorem 1 below, and proved in a companion study of exact network surgery on the same engine [4]. This paper asks the question that theorem leaves open: what does an entire workload of mutations cost? We answer it exactly, in three regimes. Contributions. 1. Aggregate sweep cost. For an exhaustive sweep that patches every site and restores each before the next, the speedup over independent full recomputations converges to (q+2)/(q+1)(q+2)/(q+1) or q+2q+2 in the Karamata index q of the network’s cost-by-depth profile — 22 only in the depth-uniform case (Theorem 2). A wall-clock corollary, computed from interpreter constants measured on the reference engine, predicts a ceiling of ≈1.79≈ 1.79, strictly below the combinatorial limit, until interpreter overhead is compiled away (Corollary 1). 2. Sequential and batched mutation cost. For a sequence of persistent grafts (never undone, as a growth schedule or a cumulative multi-site intervention performs), the interleaved cost is exactly the isolated sum plus an overcount Δ(π)≥0 (π)≥ 0 summed over comparable site pairs, with closed-form extremes over insertion orders (Theorem 3, Corollary 2); batched application is order-independent and sub-additive, costing exactly the union of the cones plus the fresh nodes (Proposition 1). 3. The backward-locality gap. The exact mirror of the locality theorem holds for the backward pass (Theorem 4), and it forces the aggregate sweep speedup to collapse to 11 under backpropagation on architectures without long skip connections (Corollary 3) — a boundary of the aggregate result, not a retraction of it: inference-time sweeps, the case that motivates this paper, are unaffected. 4. Empirical validation at zero tolerance where the claims are exact (Section 7): measured sweep ratios on real reactive graphs converge to the predicted limits under four cost profiles and both orientations (E4); the training-mode ratio collapses to 11 on a graph with genuine intra-layer width (E5); and all 1818 per-graft sequential costs, both order extremes, and the order-independent batched total match the closed forms exactly (E7), alongside a measured negative result on bookkeeping drift with mutation count. 2 Related Work Dynamic graph engines. PyTorch [1] is define-by-run; JAX [2] traces pure functions. Neither maintains a persistent reactive graph across steps: validity of cached computation is not a first-class notion, so an intervention pays a full forward pass (or a re-trace) regardless of how little of the graph it actually affects. NeuroDSL’s design [3] is closer to incremental computation systems, applied to differentiable programs; this paper quantifies exactly what that buys, and does not buy, for sweep-shaped workloads. Interventional sweeps. Activation patching, causal tracing, and automated circuit discovery all iterate a patch–measure–restore loop over candidate sites; their published cost analyses count forward passes, implicitly assuming each intervention costs a full recomputation. The accounting here replaces that assumption with exact combinatorial identities for engines that recompute only what a mutation invalidates. Exact surgery. The companion study of exact network surgery on the same engine [4] proves the single-mutation locality theorem (restated as Theorem 1) together with functional-exactness guarantees for grafted residual blocks; the present paper takes the single-mutation statement as its starting point and derives the workload-level asymptotics. 3 Preliminaries Definition 1 (Computational graph). A computational graph is a tuple =(,ℰ,op,θ)G=(V,E,op,θ) where (,ℰ)(V,E) is a finite DAG, op(v)op(v) assigns to each non-input node an operator, and θ(v)θ(v) its (possibly empty) parameter set. Distinguished subsets in⊂V_in (sources) and a node voutv_out (output) induce, by composition along the topological order, a function F:→F_G:X . Definition 2 (Grafting). Let e=(u,w)∈ℰe=(u,w) be an edge of G and ℋH a computational graph with a single input and a single output, realizing a function FℋF_H. The grafting (,e,ℋ)S(G,e,H) produces ′G by removing e and adding edges (u,in(ℋ))(u,in(H)) and (out(ℋ),w)(out(H),w), i.e., the value flowing along e now passes through ℋH. Defining insertion on an edge (rather than "at a node") removes any ambiguity about which consumers of u are rerouted: exactly those along e. Two mutation primitives cover every workload in this paper: a graft adds h=|(ℋ)|h=|V(H)| fresh computable nodes at a site, and a patch redefines the rule of an existing node in place (e.g., replacing an activation by a stored or corrupted value) and is later restored by redefining the rule back — two mutations at the same site, each triggering the same invalidation. In a reactive engine, every node carries a validity flag; a mutation at a node s invalidates its dependents, and the next demand-driven evaluation (demand!) recomputes exactly the invalid region. We formalize the invalidation procedure as Algorithm 1 and restate the locality theorem this paper’s accounting is built on; the NeuroDSL routine _invalidate_downstream! implements this algorithm (implementation conformance is an engineering claim, verified by the test suite, not part of the proof). Algorithm 1 Invalidate(,s)(G,s) — reactive invalidation from a seed node s 1:Q←[s]Q←[s]; seen←sseen←\s\ 2:while Q not empty do 3: v←pop(Q)v (Q) 4: for each w with (v,w)∈ℰ(v,w) do 5: if w∉seenw then 6: valid(w)←valid(w) ; seen←seen∪wseen ∪\w\; push(Q,w)push(Q,w) 7: end if 8: end for 9:end while Definition 3 (Downstream cone). For s∈s , let s+=v∈∣there is a path of length≥1 from s to v.V_s^+=\\,v is a path of length≥ 1 from s to v\,\. By convention s∉s+s _s^+ unless s lies on a cycle, which the DAG property excludes; when the mutation is a graft, the seed s=out(ℋ)s=out(H) is a freshly created node, which is born unvalued and needs no invalidation. Theorem 1 (Structural locality). On a DAG, Algorithm 1 terminates and the set of nodes it marks invalid is exactly s+V_s^+. Its complexity is O(|s+|+|ℰs+|)O(|V_s^+|+|E_s^+|), where ℰs+E_s^+ is the set of edges internal to the cone. Proof. Termination. Each node enters seenseen at most once and is pushed at most once; V is finite. Soundness (marked ⇒ in cone). We show by induction on the order of marking that every node marked invalid lies in s+V_s^+. The first nodes marked are the immediate successors of s, which are in s+V_s^+ via paths of length 11. Inductively, a node w is marked only when popped from the queue along an edge (v,w)(v,w) with v previously marked or v=sv=s; by the induction hypothesis there is a path s↝vs v (possibly empty if v=sv=s), which extended by (v,w)(v,w) gives a path of length ≥1≥ 1 from s to w. Hence w∈s+w _s^+. Completeness (in cone ⇒ marked). Let w∈s+w _s^+ and let s=v0→v1→…→vk=ws=v_0→ v_1→…→ v_k=w, k≥1k≥ 1, be a witnessing path. By induction on i: v0=s∈seenv_0=s and is processed; if viv_i is processed, then when it is popped, its successor vi+1v_i+1 is either already in seenseen (hence was marked and pushed earlier) or is marked and pushed now. Either way vi+1v_i+1 is marked and eventually processed. Thus vk=wv_k=w is marked. Preservation. A node v∉s+v _s^+ is never marked by soundness, so valid(v)valid(v) is untouched: its cached value survives the mutation. Complexity. Each node in the cone is popped once and each internal edge scanned once. ∎ Theorem 1 bounds the cost of a single mutation by its downstream cone. Everything that follows is the accounting for workloads built out of many such mutations. 4 Aggregate Cost of an Exhaustive Sweep A caller that tests every candidate site exhaustively – an ablation sweep, a circuit-discovery search, or a systematic robustness check – pays the sum of the per-site cone costs across every site, and it is natural to ask how this aggregate compares to the cost of testing each site by an independent full recomputation. The answer depends on exactly one number: how computational weight is distributed across depth. Definition 4 (Layered cost model). A layered DAG of depth L assigns to each layer j∈1,…,Lj∈\1,…,L\ a computational weight wj>0w_j>0 (e.g. its node count) and hosts S candidate sites per layer, each site’s downstream cone coinciding, up to an O(1)O(1) per-site remainder that vanishes in the ratios below, with the suffix ∑j>iwj _j>iw_j of the layer i it belongs to. Write N(L)=∑j=1LwjN(L)= _j=1^Lw_j for the total weight and ρ(L)=SL⋅N(L)S∑i=1L∑j>iwjρ(L)\;=\; SL· N(L)S _i=1^L _j>iw_j for the ratio of SLSL independent full recomputations to the aggregate cost of exhaustively patching every site, each restored via Theorem 1’s exact cone. Theorem 2 (Aggregate sweep ratio). Suppose wj∼ℓ(j)jqw_j (j)\,j^q as j→∞j→∞ for some q≥0q≥ 0 and some ℓ slowly varying at infinity (Karamata: ℓ(cx)/ℓ(x)→1 (cx)/ (x)→ 1 for every c>0c>0). Then ρ(L)⟶q+2q+1(L→∞).ρ(L)\; \; q+2q+1 (L→∞). If instead the weight profile is reversed, wj∼ℓ(L+1−j)(L+1−j)qw_j (L+1-j)\,(L+1-j)^q (layers near the input carry the heavier weight), the limit is ρ(L)⟶q+2.ρ(L)\; \;q+2. In particular q=0q=0 (uniform per-layer weight, wj≡Mw_j≡ M) gives ρ(L)→2ρ(L)→ 2 under either profile. Proof. Write S(n)=∑j=1nwjS(n)= _j=1^nw_j; by Karamata’s theorem for regularly varying sequences, S(n)∼nwn/(q+1)S(n) n\,w_n/(q+1). For the output-heavy profile, at i=tLi=tL for fixed t∈(0,1)t∈(0,1), wi∼ℓ(L)(tL)qw_i (L)(tL)^q and ∑j>iwj=N(L)−S(i)∼LwLq+1(1−tq+1). _j>iw_j\;=\;N(L)-S(i)\; \; L\,w_Lq+1 (1-t^q+1 ). Riemann-summing over i=1,…,Li=1,…,L (i.e., over t∈(0,1)t∈(0,1)), ∑i=1L∑j>iwj∼L⋅LwLq+1∫01(1−tq+1)t=L2wLq+1⋅q+1q+2=L2wLq+2, _i=1^L _j>iw_j\; \;L· L\,w_Lq+1 _0^1(1-t^q+1)\,dt\;=\; L^2w_Lq+1· q+1q+2\;=\; L^2w_Lq+2, and since N(L)=S(L)∼LwL/(q+1)N(L)=S(L) Lw_L/(q+1), substitution gives ρ(L)∼[L⋅LwL/(q+1)]/[L2wL/(q+2)]=(q+2)/(q+1)ρ(L) [L· Lw_L/(q+1)]/[L^2w_L/(q+2)]=(q+2)/(q+1). The reversed profile follows by the index substitution j↦L+1−j L+1-j, i↦L−i L-i, which turns the same computation into ∑j>iwj↦S(L−i)∼(L−i)wL−i/(q+1) _j>iw_j S(L-i) (L-i)w_L-i/(q+1) against the same N(L)N(L), giving the mirror-image Riemann integral ∫01tq+1t⋅(q+1)=(q+1)/(q+2) _0^1t^q+1dt·(q+1)=(q+1)/(q+2) of the denominator’s leading coefficient and hence ρ(L)→q+2ρ(L)→ q+2. ∎ Remark 1 (Why 22 is not universal). The ratio 22 is the mean of a linear ramp: a site drawn uniformly over depth has, in expectation, half the total weight downstream of it, and in general ρ=1/[U]ρ=1/E[U] for U the (normalized) downstream-weight fraction of a uniformly drawn site. Theorem 2 shows 22 is the q=0q=0 instance of a one-parameter family: back-loading cost toward the output (q>0q>0, output-heavy) lowers the limit toward 11, while front-loading it toward the input raises the limit without bound as q grows. The aggregate ratio is a direct, computable readout of where computation is concentrated in the network, not a universal constant of reactive invalidation. Corollary 1 (Wall-clock refinement). Under the uniform profile (q=0q=0), suppose each recomputation additionally pays a fixed overhead proportional to total graph size, βN(L)β N(L) – the O(||)O(|V|) topological-order walk of the demand-driven evaluator, measured on the reference implementation at a=0.042a=0.042 ms per cone node with an intercept of 2.242.24 ms on a 412412-node model, i.e. β≈0.0054β≈ 0.0054 ms/node (Section 7) – on top of the a|i+|a\,|V_i^+| cost Theorem 1 guarantees. Then the wall-clock aggregate ratio converges to ρwallclock(L)⟶a+βa/2+β≈ 1.79, _wallclock(L)\; \; a+βa/2+β\;≈\;1.79, strictly below the unit-cost limit of 22, since β is paid once per site regardless of cone size and contributes equally to numerator and denominator, while the a-term alone retains the 1/21/2 averaging of Theorem 2. Proof. With cost(i)=aM(L−i)+βMLcost(i)=a\,M(L-i)+β ML per site and K=SLK=SL sites, the numerator (naive) is K(a+β)MLK(a+β)ML and the denominator is a⋅SML(L−1)2+KβML∼SML2(a/2+β)a· SM L(L-1)2+Kβ ML SML^2(a/2+β) to leading order; the ratio of leading terms is (a+β)/(a/2+β)(a+β)/(a/2+β). ∎ Remark 2. This is a testable refinement, not a restatement: it predicts that any exhaustive, depth-uniform sweep on this engine converges to an aggregate speedup strictly below 22 in wall-clock time – ≈1.79≈ 1.79 at the constants above – until the interpreter overhead β is eliminated by a compilation layer (Section 8), at which point the pure combinatorial limit of Theorem 2 is recovered. 5 Sequential Mutation Cost: Interleaved and Batched Grafting Theorem 1 bounds a single graft; Section 4 bounds an exhaustive sweep of patches that are each undone before the next is tried. A growth schedule – and equally a cumulative multi-site intervention that leaves each patch in place – does neither: it applies a sequence of grafts to the same graph, none of them undone, each possibly landing inside a cone already disturbed by an earlier one. This section asks what that sequence costs, in two regimes – interleaved (a full demand! between grafts, as a loop that logs a metric after each mutation would do) and batched (all grafts applied before the next demand!, exactly the cost profile of a multi-site patch set applied at once) – and shows both are governed exactly by Theorem 1 applied recursively, with no new axiom required. Lemma 1 (Cone trace invariance under grafting). Let ′=(,e,ℋ)G =S(G,e,H) with e=(u,w)e=(u,w) and ℋH built from fresh nodes, connected from in(ℋ)in(H) to out(ℋ)out(H) and wired into ′G only via (u,in(ℋ))(u,in(H)) and (out(ℋ),w)(out(H),w). Then for any node f∈()∖uf (G) \u\: (i) f+(′)∩()=f+()V_f^+(G ) (G)=V_f^+(G), i.e. reachability among original nodes is unchanged; (i) the h computable nodes of ℋH belong to f+(′)V_f^+(G ) iff u∈f+()∪fu _f^+(G)∪\f\, i.e. iff f’s downstream cone in G already contained u (equivalently: e lies downstream of f). Proof. Any path between original nodes that used e in G rewrites in ′G as u→in(ℋ)↝out(ℋ)→wu (H) (H)→ w, and conversely any path in ′G between original nodes that enters ℋH must do so at in(ℋ)in(H) (its only in-edge from an original node) and leave at out(ℋ)out(H) (its only out-edge to one), since ℋH’s internal wiring never touches original nodes; replacing that segment with e recovers a path in G. This proves (i). For (i), a node of ℋH is reachable from f in ′G iff some path from f reaches u (then continues u→in(ℋ)↝⋅u (H) ·), which happens iff u∈f+()∪fu _f^+(G)∪\f\. ∎ Theorem 3 (Exact interleaved cost). Let u1,…,uKu_1,…,u_K be distinct nodes of 0G_0 (no two related by ancestry through each other’s own graft, i.e. each uku_k survives as a node through every graft not performed at uku_k itself), grafted in the order π (a permutation of 1,…,K1,…,K) with block sizes h1,…,hKh_1,…,h_K, each graft followed by a full demand! before the next is applied. The recomputation cost of the k-th graft (in π-order) is exactly costπ(k)=|uπ(k)+(0)|+hπ(k)+∑j<kuπ(j)∈uπ(k)+(0)hπ(j),cost_π(k)\;=\; |V_u_π(k)^+(G_0) |\;+\;h_π(k)\;+\!\! _ subarraycj<k\\ u_π(j)\,∈\,V_u_π(k)^+(G_0) subarray\!\!h_π(j), and therefore Cseq(π)=Ciso+Δ(π)C_seq(π)=C_iso+ (π) where Ciso=∑k(|uk+(0)|+hk)C_iso= _k (|V_u_k^+(G_0)|+h_k ) is the cost of K grafts on independent copies of 0G_0, and Δ(π)=∑(j,k):π applies j before kuj∈uk+(0)hj≥ 0, (π)\;=\!\! _ subarrayc(j,k)\,:\,π applies j before k\\ u_j\,∈\,V_u_k^+(G_0) subarray\!\!h_j\;\;≥\;0, with equality iff π never grafts a site while a strictly upstream site’s graft is still outstanding. Proof. By induction on k. At the first graft, 0G_0’s own cone uπ(1)+(0)V_u_π(1)^+(G_0) is recomputed by Theorem 1, plus the hπ(1)h_π(1) fresh nodes of ℋπ(1)H_π(1) (unvalued, hence "recomputed" trivially): this is the k=1k=1 case with an empty sum. Assume the formula holds through graft k−1k-1, giving a fully valid k−1G_k-1. Applying Lemma 1 k−1k-1 times (once per prior graft, each preserving reachability among nodes not part of that graft’s own block) shows uπ(k)+(k−1)V_u_π(k)^+(G_k-1) consists of exactly the original nodes of uπ(k)+(0)V_u_π(k)^+(G_0), together with the fresh block of every prior graft j<kj<k whose site uπ(j)u_π(j) lies in uπ(k)+(0)V_u_π(k)^+(G_0) (Lemma, part (i), applied with f=uπ(k)f=u_π(k)). Theorem 1 recomputes exactly this cone, plus the hπ(k)h_π(k) fresh nodes of the current graft. Summing over k and separating the j=kj=k diagonal terms from the cross terms gives Cseq(π)=Ciso+Δ(π)C_seq(π)=C_iso+ (π); each term of Δ is a size hj≥0h_j≥ 0, so Δ(π)≥0 (π)≥ 0, with equality iff no pair (j,k)(j,k) with j before k has uju_j downstream of uku_k – i.e. π is upstream-first. ∎ Corollary 2 (Order extremes, uniform blocks). If the K sites are totally ordered by depth (a sequential architecture) and hk≡h_k≡ h, then over all K!K! orders: Δmin=0 _ =0 (shallowest-first), Δmax=h(K2) _ =h K2 (deepest-first), and π[Δ(π)]=h(K2)/2E_π[ (π)]=h K2/2 under a uniformly random order (each of the (K2) K2 depth-ordered pairs contributes h independently with probability 1/21/2, by linearity of expectation over the event "the deeper site of the pair is applied first"). Proposition 1 (Batched grafting: sub-additive and order-independent). If all K grafts are applied to 0G_0 before any demand!, the total number of nodes requiring recomputation at the next demand! is exactly Cbatch=|⋃k=1Kuk+(0)|+∑k=1Khk,C_batch\;=\; |\, _k=1^KV_u_k^+(G_0)\, |\;+\; _k=1^Kh_k, independent of the order in which the K grafts were applied, and Cbatch≤CisoC_batch≤ C_iso, strictly whenever some pair of sites is comparable (uj∈uk+(0)u_j _u_k^+(G_0) for some j≠kj≠ k). Proof. Order-independence: redefining an existing node’s rule re-invalidates its cone regardless of what was invalid before (addrule!’s contract, exercised by every graft in this paper), and re-invalidating an already-invalid node is idempotent, so the final valid/invalid partition after K unread grafts depends only on the set of rules redefined, not the order of redefinition. A node needs recomputation iff it is a fresh node of some block (∑khk _kh_k of these, always invalid), or an original node lying in uj+(0)V_u_j^+(G_0) for some j – exactly the union ⋃kuk+(0) _kV_u_k^+(G_0), by definition of the downstream cone (Section 3). No correction term for the sites uku_k themselves is needed: by the same definition, uk∉uk+(0)u_k _u_k^+(G_0) for every k, and uk∈uj+(0)u_k _u_j^+(G_0) for some j≠kj≠ k exactly when uku_k genuinely is an ordinary downstream node of another graft’s site and is therefore correctly recomputed; a site that is not downstream of any other selected site simply never appears in the union at all, with no subtraction required to remove it. Sub-additivity: |⋃kuk+(0)|≤∑k|uk+(0)| | _kV_u_k^+(G_0) |≤ _k|V_u_k^+(G_0)| with equality iff the cones are pairwise disjoint, i.e. no two sites are comparable; hence Cbatch≤CisoC_batch≤ C_iso. ∎ Remark 3 (Composing exactness across a schedule). The companion surgery study [4] proves an identity-morphism theorem for a single function-preserving graft on an arbitrary graph; nothing in its hypotheses refers to the graph’s history. It therefore applies verbatim to every intermediate graph k−1G_k-1 in a sequence, and functional exactness composes by induction across an entire growth schedule – the guarantee a multi-graft schedule implicitly relies on at every step, made explicit here rather than re-derived per instance. Remark 4 (What is proved and what is only measured). Theorem 3 and Proposition 1 are exact combinatorial identities – verified below at zero tolerance, not by convergence. They govern recomputation cost only. A separate, non-combinatorial question – whether the bookkeeping cost of a graft (rewiring consumers, rebuilding the consumers/topological-order caches) drifts with the number of prior mutations at fixed graph size, beyond the size-dependence already captured by the wall-clock Corollary 1’s β term – has no theorem attached and is reported as a measurement only (E7 below). 6 Locality Under Backpropagation: Where the Speedup Evaporates Theorem 1 and its aggregate consequence (Theorem 2) concern forward recomputation: after a mutation at s, only s+V_s^+ must be re-evaluated. Training also propagates a backward pass, and the chain rule ties the gradient of every ancestor of s to the local computation performed at s. This section states the exact mirror of Theorem 1 for this upstream dependency and draws an honest corollary: on the sequential architectures this paper’s cost model targets, the mirror set is almost the whole graph, and the aggregate speedup of Theorem 2 does not transfer to an exhaustive sweep performed under backpropagation. Definition 5 (Upstream cone). For s∈s , let s−=v∈∣there is a path of length≥1 from v to sV_s^-=\v is a path of length≥ 1 from v to s\ – the mirror image of the downstream cone s+V_s^+ of Section 3, obtained by reversing every edge. Theorem 4 (Backward locality). Let ℓ be a distinguished loss node with s∈ℓ−s _ ^- (i.e., s contributes to the loss). Mirroring Algorithm 1 on the graph with every edge reversed, seeded at s, terminates and marks exactly s−V_s^- (termination, soundness, and completeness are the proof of Theorem 1 verbatim, with every edge (u,w)(u,w) read as (w,u)(w,u)). This set is exactly the collection of nodes whose backward pass depends, via the chain rule, on the (possibly mutated) local Jacobian at s: for v∉s−∪sv _s^-∪\s\, ∂ℓ/∂v∂ /∂ v is computed entirely from paths that never traverse s and is therefore unaffected by a mutation there. Proof. Termination, soundness, and completeness of the reversed traversal follow Theorem 1’s proof with the edge direction flipped. For the gradient claim, write ∂ℓ/∂v=∑π:v↝ℓ∏(a,b)∈π∂b/∂a∂ /∂ v= _π:\,v _(a,b)∈π∂ b/∂ a, a sum over directed paths π from v to ℓ ; a term is affected by s’s local computation iff s lies on π. If v∈s−v _s^-, some witnessing path v↝sv s extends through s to ℓ (since s∈ℓ−s _ ^- gives s↝ℓs ), so at least one term of the sum passes through s. If v∉s−∪sv _s^-∪\s\, no path from v reaches s, so no term can. ∎ Corollary 3 (Training-mode locality collapse). In the layered cost model of Definition 4, suppose every node of layer j<ij<i is an ancestor of every node of layer i (resp. j>ij>i a descendant) – true whenever the architecture has no skip connection bypassing an entire layer, as in a stack of Transformer blocks composed purely sequentially. Then a mutation at a site s of local cost ckc_k in layer i touches, under backpropagation, |s−∪s∪s+|=N(L)−wi+ck, |V_s^-∪\s\ _s^+ |\;=\;N(L)-w_i+c_k, the whole graph minus the untouched remainder of s’s own layer, and the aggregate ratio of an exhaustive sweep performed under backpropagation satisfies ρtrain(L)=LN(L)∑i=1L(N(L)−wi+c¯)⟶ 1(L→∞), _train(L)\;=\; L\,N(L) _i=1^L (N(L)-w_i+ c )\; \;1 (L→∞), regardless of the cost profile (wj)(w_j) or its Karamata index – in sharp contrast to Theorem 2. Proof. ∑i=1L(N(L)−wi+c¯)=LN(L)−N(L)+Lc¯ _i=1^L(N(L)-w_i+ c)=LN(L)-N(L)+L c, so ρtrain(L)=LN(L)/(LN(L)−N(L)+Lc¯)=L/(L−1+Lc¯/N(L))→1 _train(L)=LN(L)/(LN(L)-N(L)+L c)=L/(L-1+L c/N(L))→ 1 as L→∞L→∞, since c¯/N(L)→0 c/N(L)→ 0 for any cost profile with N(L)→∞N(L)→∞. ∎ Remark 5. This is not a retraction of Theorems 1 and 2: every measurement in this paper (E4, E5, E7) and the exhaustive patching sweeps that motivate it are performed at inference, with no backward pass through the swept sites – exactly where Theorem 2 applies undiminished. Corollary 3 instead delimits the claim precisely: reactive locality is a property of value propagation, not of gradient propagation, on architectures without long skip connections. Growing a network mid-training – the subject of the companion surgery study [4] – is unaffected in practice, since a growth schedule grafts one site at a time rather than exhaustively sweeping candidates under backpropagation. 7 Experimental Results All measurements use the reference implementation (NeuroDSL, Julia, Float32, CPU). Where a claim is an exact combinatorial identity (E7), the comparison is at zero tolerance on integer invalid counts; where it is an asymptotic limit (E4, E5), convergence across increasing L is reported. The interpreter constants used by Corollary 1 (a=0.042a=0.042 ms per cone node, intercept 2.242.24 ms on a 412-node model, hence β≈0.0054β≈ 0.0054 ms/node) were measured in the companion surgery study’s cost-versus-depth experiment [4] on this same engine and are reused here unchanged. 7.1 E4: The Aggregate Sweep Ratio Under Non-Uniform Cost Profiles (Theorem 2) Theorem 2 is a statement about an abstract layered-cost model; we verify it on a real graph in the reference implementation, not a combinatorial simulation. For each (L,q,profile)(L,q,profile), a sequential graph of L layers is built where layer j contributes wjw_j nodes (a chain of :relu unary ops) with wjw_j set, up to rounding, proportional to jqj^q (output-heavy) or (L−j+1)q(L-j+1)^q (input-heavy) and normalized so total graph size is ≈4000≈ 4000 nodes regardless of q; the graph is evaluated once (so every node is valid), and ρ(L)ρ(L) is computed from the true downstream cone of each layer’s last node, measured by _downstream_nodes – the same routine sweep_patch_sites! uses in the patching-sweep tooling built on this engine, not a re-derivation for this test. Table 1: E4 — measured ρ(L)ρ(L) at L=320L=320 nodes-per-cone-profile, vs. Theorem 2’s prediction. q Predicted (output-heavy) Measured, L=320L=320 Measured (input-heavy) vs. predicted q+2q+2 0.00.0 2.00002.0000 2.00572.0057 2.00572.0057 vs. 2.02.0 0.50.5 1.66671.6667 1.67221.6722 2.50572.5057 vs. 2.52.5 1.01.0 1.50001.5000 1.50641.5064 3.00043.0004 vs. 3.03.0 2.02.0 1.33331.3333 1.34711.3471 3.92473.9247 vs. 4.04.0 Every entry converges toward its predicted limit as L grows across the tested range L∈20,40,80,160,320L∈\20,40,80,160,320\ (not shown in full: the q=1q=1, input-heavy case alone tightens from 3.15853.1585 at L=20L=20 to 3.00043.0004 at L=320L=320), confirming both the asymptotic derivation and that the abstract layered-cost model of Definition 4 is not merely a convenient fiction: a real reactive graph’s measured cones obey it. The uniform case (q=0q=0) recovers 22 from either profile, as it must, and is the special case already exploited for exhaustive activation-patching sweeps built on this same engine. 7.2 E5: Training-Mode Collapse (Corollary 3) A layered graph with genuine intra-layer width is built exactly as in E4, except each layer’s wjw_j branches are computed in parallel from the previous layer (no branch depends on another) and then folded pairwise into a single aggregate before the next layer – so a candidate site’s siblings within its own layer are neither its ancestors nor its descendants, the general case Corollary 3 addresses (unlike a purely sequential single-path graph, where ck=wic_k=w_i and the corollary degenerates to the exact identity ρtrain≡1 _train≡ 1 at every finite L). Measuring ρtrain(L)=|sites|⋅N(L)/∑s|s−∪s∪s+| _train(L)= |sites |· N(L)/ _s|V_s^-∪\s\ _s^+| directly (ancestors by a plain reverse walk over each node’s recorded inputs, descendants by _downstream_nodes) gives, independently of q and of the output-/input-heavy profile: 1.05261.0526 (L=10L=10), 1.02561.0256 (2020), 1.01261.0126 (4040), 1.00621.0062 (8080), 1.00311.0031 (160160) – converging to 11 exactly as Corollary 3 predicts, at a rate insensitive to the cost profile that gave Theorem 2 its rich q-dependence under forward-only recomputation. 7.3 E7: Sequential Mutation Cost (Theorem 3, Proposition 1) On a 400400-node synthetic chain (built and demand!-ed exactly as in E4), K=6K=6 sites are selected at roughly even depth and H=20H=20 fresh nodes are grafted at each. Interleaved regime: for three orders – shallowest-first, deepest-first, and a fixed random permutation – a full demand! is issued before each graft, and the number of nodes marked invalid immediately after each graft is compared to Theorem 3’s closed-form prediction, computed once from 0G_0’s cones before any graft. Batched regime: the same K grafts are applied back-to-back with no intermediate demand!, for the same three orders, and the total invalid count is compared to Proposition 1. Table 2: E7 — per-graft recomputation cost, interleaved regime, three orders (K=6K=6, H=20H=20). Every entry matches Theorem 3 exactly (zero tolerance). Order Measured (per graft) Δ(π) (π) vs. Theorem Shallowest-first 363,306,249,191,134,77363,306,249,191,134,77 0 (predicted: 0) Deepest-first 77,154,231,309,386,46377,154,231,309,386,463 300300 (predicted: H(K2)=300H K2=300) Random (11 seed) 249,191,403,77,154,386249,191,403,77,154,386 140140 Every one of the 1818 per-graft measurements across the three orders matches Theorem 3’s formula exactly, and Δ(π) (π) realizes both extremes of Corollary 2 precisely (0 and H(K2)=300H K2=300). In the batched regime, all three orders give the identical total 463463, matching Proposition 1’s order-independent closed form exactly: the union of the six sites’ original cones is 343343 (the shallowest site’s cone alone, since the other five sites – and their downstream nodes – all lie within it), plus KH=120KH=120 fresh nodes, giving 343+120=463343+120=463 with no correction term, confirming Cbatch=463<Ciso=1320C_batch=463<C_iso=1320, the predicted strict sub-additivity. Two bugs were found and fixed before this number was accepted: an initial version counted leaf nodes (e.g. the graph’s input, which has no rule and whose valid flag is never touched by demand!), producing a constant off-by-one on every interleaved measurement; a second version additionally subtracted one node per selected site from the batched union on the mistaken assumption that every site’s own symbol needed excluding, producing a further off-by-five – resolved by recognizing that Proposition 1’s union already excludes exactly the sites that are not downstream of any other selected site, by the downstream-cone definition itself, with no separate correction needed. Bookkeeping drift with mutation count (measurement, not theorem). 100100 single-node grafts are applied successively to a fresh 400400-node chain (final size 500500), timing only the rewiring step (excluding demand!); a control arm applies 100100 rule-redefinitions without adding a node (graph size fixed at 401401 throughout), isolating any effect of mutation count from the already-established effect of graph size (Corollary 1’s β term). Trimmed-median (10%) cost rises modestly from 0.0330.033 ms (first half, size ≈401≈ 401–451451) to 0.0360.036 ms (second half, size ≈451≈ 451–501501) for the growing chain, consistent with the small size increase; the constant-size control shows no such drift (0.02430.0243 ms in both halves), and grafting is costlier than rule-redefinition alone (0.0350.035 ms vs. 0.0240.024 ms trimmed-median overall) as expected, since it does strictly more work. No history-dependent drift beyond graph size is detected at this scale (100100 mutations, single run) – a negative result reported as such, not a proof of its absence. 8 Limitations The aggregate results concern recomputation counts; wall-clock enters only through the two measured constants of Corollary 1, which are specific to the current interpreter (CPU, Float32) — a compilation layer would change β, and with it the wall-clock ceiling, though not the combinatorial limits. The layered cost model of Definition 4 assumes each site’s downstream cone coincides with a depth suffix up to a vanishing remainder; architectures with long skip connections violate both this and the ancestry hypothesis of Corollary 3, so their sweep ratios are not covered by the closed forms here (the exact per-site formula of Theorem 3 still applies, since it makes no layering assumption). E7’s bookkeeping-drift measurement is a single run of 100100 mutations at one graph-size trajectory; absence of detected drift there is evidence at that scale, not a bound valid at the scale of a real multi-thousand-mutation schedule. Finally, Corollary 3 delimits but does not quantify the intermediate regime of architectures with some long skips, where the sweep ratio under backpropagation lies strictly between 11 and the forward-only limit; characterizing that interpolation is open. 9 Conclusion On a reactive graph engine whose invalidation is provably confined to the downstream cone of a mutation, the cost of an entire sweep-shaped workload is a computable function of where computation is concentrated in the network. The aggregate speedup of an exhaustive site-by-site sweep is (q+2)/(q+1)(q+2)/(q+1) or q+2q+2 in the Karamata index of the cost-by-depth profile — 22 only in the depth-uniform case — with a wall-clock ceiling of ≈1.79≈ 1.79 at the current interpreter’s measured constants; a sequence of persistent mutations costs exactly the isolated sum plus a closed-form order penalty, minimized by upstream-first application and eliminated entirely (along with order dependence) by batching; and under backpropagation the aggregate speedup collapses to 11 on architectures without long skip connections, confining the benefit to inference-time sweeps — precisely the regime of the activation-patching and circuit-discovery workloads that motivate this accounting. Every exact identity is validated at zero tolerance, and every asymptotic limit by measured convergence, on the reference implementation. References [1] Paszke, A., et al. (2019). PyTorch: An Imperative Style, High-Performance Deep Learning Library. NeurIPS. [2] Bradbury, J., et al. (2018). JAX: Composable Transformations of Python+NumPy Programs. http://github.com/google/jax. [3] Khemais, A. (2026). NeuroDSL: A Reactive Computational Graph Framework for Deep Learning in Julia. Preprint. [4] Khemais, A. (2026). Exact Network Surgery: Functional Invariance and Gradient Plasticity in Reactive Computational Graphs. Preprint, submitted concurrently.