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

• URL: http://arxiv.org/abs/2607.18323v1
• Date: Sat, 18 Jul 2026 00:53:22 GMT
• Title: Cost Accounting for Reactive Computational Graphs: Exhaustive Sweeps, Sequential Mutation, and the Backward-Locality Gap
• Abstract summary: We show how Julia handles interventions on a neural network's computational graph.<n>We prove the exact cost of a sequence of persistent mutations, never undone between insertions.<n>We also show how batched application is order-independent and sub-additive.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Efficient Quantum Simulation of Variable-Coefficient Transport with Continuous Source Injection [0.49259062564301753]
  We present an algorithm for a forced variable-coefficient advection-diffusion equation in flow-inspired skew-symmetric form.<n>A centered skew-symmetric discretization makes the advection operator strictly skew-Hermitian for arbitrary velocity profiles.<n>We show that the per-step ancilla failure probability is proportional to the instantaneous dissipation rate, making postselection cost self-regulating over a fifty-fold viscosity range.
  arXiv  Detail & Related papers  (2026-08-27T21:00:39Z)
• Simplex Relaxation for Discrete Diffusion [58.33696160279345]
  We introduce Simplax, an exact Dirichlet--categorical augmentation that couples each corrupted categorical state with an auxiliary simplex-valued variable.<n>Simplax improves the generative perplexity--entropy tradeoff on unconditional OpenWebText generation.
  arXiv  Detail & Related papers  (2026-08-11T07:58:17Z)
• The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems [1.0742675209112622]
  We formalize nuisance adaptation via a slice-normalized minimax ratio.<n>We also define the cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection.
  arXiv  Detail & Related papers  (2026-08-09T17:19:11Z)
• The Equilibrium Is the Initialization: Lazy Identity Collapse in Physics-Structured Deep Equilibrium Reasoning [0.0]
  Deep equilibrium models promise input-adaptive implicit computation.<n>We report a cautionary study of a port-Hamiltonian DEQ with learned reasoning tasks.<n>We show that the standard zeroing ablation is confounded and gives wildly seed-dependent answers.
  arXiv  Detail & Related papers  (2026-07-13T05:45:35Z)
• What Does a Discrete Diffusion Model Learn? [71.03603607324338]
  discrete diffusion model learns: a denoiser, a score ratio, or a bridge plug-in predictor.<n>We start with a rigorous derivation of the continuous-time Markov chain (CTMC) ELBO for any noising process.<n>Every identity is verified numerically, without approximation, on an exactly solvable model.
  arXiv  Detail & Related papers  (2026-07-06T17:56:11Z)
• Active Quantum Kernel Acquisition for Gaussian Process Regression [30.032230630492155]
  Recent work on quantum kernel classification has shown that allocating shots non-uniformly across kernel entries can reduce the shot budget required to reach a target accuracy.<n>We extend this idea to Gaussian process (GP) regression, a setting whose downstream quantities (full-spectrum posterior variance, log-determinant, marginal likelihood) couple to kernel error more tightly than the sign-only outputs of classification.<n>We derive three closed-form pair-level sensitivities predictive coupling $|_i_j|$, leave-one-out residual, and marginal-likelihood gradient and plug them into a Neyman-style minimum
  arXiv  Detail & Related papers  (2026-06-27T09:40:20Z)
• Stochastic Estimation of the Layer-wise Hessian Trace for Monitoring Neural-network Training [45.88028371034407]
  We present a parameter estimator of the trace of the diagonal blocks of the Hessian matrix of the empirical risk of a neural network.<n>The procedure combines the Hutchinson trace estimator with a single Hessian-vector product over the whole parameter vector.<n>We show that correctness under weight sharing requires the layer-wise Hessian to be assembled before the second differentiation.
  arXiv  Detail & Related papers  (2026-05-25T10:24:32Z)
• Self-Attention as a Covariance Readout: A Unified View of In-Context Learning and Repetition [8.250374560598495]
  Large language models (LLMs) exhibit two behaviours: in-context learning (ICL) and repetitive generation.<n>In both, the model behaves as though it had summarised the context into a population-level statistic and discarded token-level detail.<n>We ask whether this summarisation and forgetting' can be derived from the attention mechanism itself, and answer in the affirmative.
  arXiv  Detail & Related papers  (2026-05-11T12:33:15Z)
• Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
  We study mean estimation of a random vector $X$ in a distributed parameter-server-worker setup.<n>Key challenges are adversarial measurements and asynchrony.<n>Results provide a unified finite-time characterization of robustness, identifiability, and statistical efficiency in distributed linear estimation with adversarial workers.
  arXiv  Detail & Related papers  (2026-04-07T11:45:55Z)
• Hardware-Agnostic Modeling of Quantum Side-Channel Leakage via Conditional Dynamics and Learning from Full Correlation Data [0.0]
  We study a sequential side-channel model in which an adversarial probe qubit interacts with a target qubit during a hidden gate sequence.<n>Repeating the same hidden sequence for $N$ shots yields an empirical full-correlation record.<n>Experiments over broad coupling and noise grids show that strict sequence recovery concentrates near the predicted coupling band.
  arXiv  Detail & Related papers  (2026-02-17T19:33:23Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• Clustered Switchback Designs for Experimentation Under Spatio-temporal Interference [44.644520116360106]
  We estimate the global average treatment effect (GATE), the difference between average outcomes having exposed all units at all times to treatment or to control.<n>We propose a clustered switchback design, where units are grouped into clusters and time steps are grouped into blocks.<n>We show that for graphs that admit good clustering, a truncated Horvitz-Thompson estimator achieves a $tilde O(1/NT)$ mean squared error (MSE)<n>Our results simultaneously generalize the results from citethu2022switchback,ugander2013graph and citetleung2022rate
  arXiv  Detail & Related papers  (2023-12-25T01:00:58Z)
• Optimization of Time-Dependent Decoherence Rates and Coherent Control for a Qutrit System [77.34726150561087]
  Incoherent control makes the decoherence rates depending on time in a specific controlled manner. We consider the problem of maximizing the Hilbert-Schmidt overlap between the system's final state $rho(T)$ and a given target state $rho_rm target.
  arXiv  Detail & Related papers  (2023-08-08T01:28:50Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.