arXiv:2607.18323cs.LGcs.AI2026-07

揭示神经网络计算图遍历的代价规律,为高效调试提供理论依据。

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

  • 基于反应式图引擎,精确计算逐点修改的重构开销。
  • 全量重计算下速度提升上限约1.79,远低于理想值2。
  • 反向传播时局部性失效,导致加速比降为1,适用于无长连接架构。

对神经网络计算图进行逐点干预(如激活修补、电路发现、系统消融)时,每次修改后需重新计算,成本主要来自重计算。针对一种能精确追踪被修改节点下游影响范围的反应式图引擎,本文给出了此类工作负载的完整代价分析:首先,在权重随深度呈Karamata指数q分布的情况下,遍历搜索的总提速比收敛于 (q+2)/(q+1)(输出附近)或 q+2(输入附近),仅在深度均匀时恢复至2,实测墙钟时间上限约为1.79,除非解释器开销被消除;其次,证明了持久性连续修改序列的代价:交错执行代价高于独立求和,其超额部分可精确表达为可比节点对的总和,不同插入顺序有闭式极值,而批量应用则与顺序无关且满足次可加性,代价等于各节点影响锥的并集加上新增节点数;最后,证明了反向传播下的“反向局部性”完全坍缩,使得聚合加速比降为1,尤其在无长跳连的架构中成立。所有结论均在Julia实现的NeuroDSL引擎上验证:四种成本配置下的扫描比趋近理论极限;训练模式下加速比按预测速率归零;18个逐节点修改的代价及批量总代价在三种插入顺序下均与闭式解完全吻合,容忍度为0。

原文摘要 · Abstract (English)

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.

计算图代价分析神经网络反向传播

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。