反应式计算图的成本核算：穷举扫描、顺序变异与反向局部性差距

# 反应式计算图的成本核算：穷举扫描、顺序突变与反向局部性缺口

来源：https://arxiv.org/html/2607.18323 \(2026年7月\)

###### 摘要

对神经网络计算图进行穷举的逐点干预——激活修补扫描、电路发现搜索、系统性消融研究——依次在每个候选位置改变图结构，其成本主要来自每次突变后的重新计算。在反应式图引擎中，失效传播可证明恰好触及突变节点的下游锥体，我们对此类工作负载给出了完整的成本核算。首先，穷举扫描相对于独立全重新计算的总体加速比并非通用常数：若每一层的计算权重随深度以 Karamata 指数 \(q\) 规则变化，当权重集中在输出端时该比值收敛于 \((q+2)/(q+1)\)，当权重集中在输入端时收敛于 \(q+2\)，仅在深度均匀时恢复为 \(2\)；根据实测解释器常数得出的时钟推论预测上限约为 \(1.79\)，严格低于 \(2\)，除非解释器开销被编译消除。其次，我们证明了连续持久突变（插入后永不撤销的序列）的精确成本：交错成本超过孤立成本之和的精确超额 \(\Delta(\pi)\geq 0\) 通过对可比站点对的求和得到，并在插入顺序上具有闭式极值；而*批量化*应用与顺序无关且呈次加性，其成本恰好是各站点下游锥体的并集加上新节点。第三，我们证明了反向传播中正向局部性的精确镜像，并表明它迫使聚合扫描加速比在无长跳接连接的架构上崩塌为 \(1\)——精确界定了加速比完全适用的场景（推理时扫描）。所有恒等式均在 *NeuroDSL*[3] 的参考实现上验证，该实现是 Julia 中的一个反应式定义-运行图引擎：在真实反应式图上测量的扫描比值在四种非均匀成本轮廓下收敛到预测极限 (E4)；训练模式比值以预测速率崩塌为 1 (E5)；所有 18 次逐次嫁接的连续成本、两种顺序极端情况以及顺序无关的批量总和均与闭式精确匹配 (E7)。

## 1 引言

机械可解释性的核心工作方法是*扫描*：依次修补或消融训练好的网络的每个候选站点，测量对指标的影响，恢复基线，然后移至下一个站点。电路发现搜索、因果追踪协议和系统性鲁棒性检查都采用这种形式，其成本主要不在于突变本身——覆盖一个激活值或一个规则是廉价的——而在于每次突变在读取指标之前被迫进行的*重新计算*，再乘以候选站点的数量（随模型大小增长）。其中有多少重新计算是真正必要的，取决于执行模型。Eager 框架如 PyTorch[1] 每次干预都会重新运行完整的前向传播；编译管道（torch.compile、jax.jit[2]）在干预改变已追踪的程序时可能会重新追踪。两者都不维护*部分有效性*的概念：框架无法区分缓存值仍然正确的子图和被干预失效的子图。

而*反应式*图引擎可以做到这一点。*NeuroDSL*[3] 将计算图作为持久 DAG 保存，其中节点拥有自己的缓存值，突变会触发失效波，传播范围被证明仅限于突变节点的下游锥体——即下面定理 1 重新陈述的单突变局部性定理，并在同一引擎的精确网络手术配套研究中得到证明[4]。本文探讨该定理未解决的开放问题：整个*突变工作负载*的成本是多少？我们给出精确答案，涵盖三种场景。

#### 贡献

1. 1. **聚合扫描成本**。对于穷举扫描（每个站点修补并在下一个之前恢复），相对于独立全重新计算的加速比收敛于 \((q+2)/(q+1)\) 或 \(q+2\)，具体取决于网络按深度成本轮廓的 Karamata 指数 \(q\)——仅在深度均匀时才是 2（定理 2）。根据参考引擎上测量的解释器常数算出的时钟推论预测上限约为 \(1.79\)，严格低于组合极限，直到解释器开销被编译消除（推论 1）。
2. 2. **顺序和批量突变成本**。对于*持久*嫁接序列（永不撤销，如生长调度或累积多站点干预），交错成本精确地等于孤立和加上超额 \(\Delta(\pi)\geq 0\)，通过对可比站点对的求和得到，并在插入顺序上具有闭式极值（定理 3、推论 2）；批量应用与顺序无关且呈次加性，其成本恰好是各站点锥体的并集加上新节点（命题 1）。
3. 3. **反向局部性缺口**。反向传播中局部性定理的精确镜像成立（定理 4），并且它迫使聚合扫描加速比在无长跳接连接的架构上崩塌为 1（推论 3）——这是聚合结果的一个边界，而非否定：推理时扫描（本文的动机场景）不受影响。
4. 4. **零容差下的实证验证**（第 7 节）：在四种成本轮廓和两种定向下，真实反应式图上的实测扫描比值收敛到预测极限 (E4)；在具有真实层内宽度的图上，训练模式比值以预测速率崩塌为 1 (E5)；所有 18 次逐次嫁接的连续成本、顺序极值以及顺序无关的批量总和均与闭式精确匹配 (E7)，同时还测量了突变计数下簿记漂移的负结果。

## 2 相关工作

#### 动态图引擎

PyTorch[1] 是定义即运行；JAX[2] 追踪纯函数。两者均不跨步骤维护持久反应式图：缓存计算的正确性并非一等概念，因此一次干预需要付出完整前向传播（或重新追踪）的代价，无论实际影响图的多小部分。NeuroDSL 的设计[3] 更接近增量计算系统，应用于可微程序；本文定量评估了这种设计为扫描形工作负载带来的具体收益与局限。

#### 干预式扫描

激活修补、因果追踪和自动化电路发现都迭代执行修补–测量–恢复循环，遍历候选站点；其公布的成本分析通常计数前向传播次数，隐含假设每次干预的成本等于一次完整重新计算。本文的核算用精确组合恒等式替换该假设，适用于只重新计算突变失效部分的引擎。

#### 精确手术

同一引擎上的精确网络手术配套研究[4] 证明了单突变局部性定理（重新陈述为定理 1），并给出嫁接残差块的功能精确性保证；本文以该单突变陈述为起点，推导工作负载级别的渐近行为。

## 3 预备知识

###### 定义 1（计算图）

计算图是一个四元组 \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathrm{op},\theta)\)，其中 \((\mathcal{V},\mathcal{E})\) 是有限 DAG，\(\mathrm{op}(v)\) 为每个非输入节点赋予一个算子，\(\theta(v)\) 为其（可能为空）参数集。区别子集 \(\mathcal{V}_{\mathrm{in}}\subset\mathcal{V}\)（源）和一个节点 \(v_{\mathrm{out}}\)（输出）通过沿拓扑顺序复合，诱导函数 \(F_{\mathcal{G}}:\mathcal{X}\to\mathcal{Y}\)。

###### 定义 2（嫁接）

设 \(e=(u,w)\in\mathcal{E}\) 是 \(\mathcal{G}\) 的一条边，\(\mathcal{H}\) 是一个具有单输入单输出的计算图，实现函数 \(F_{\mathcal{H}}\)。嫁接操作 \(\mathcal{S}(\mathcal{G},e,\mathcal{H})\) 通过移除 \(e\) 并添加边 \((u,\mathrm{in}(\mathcal{H}))\) 和 \((\mathrm{out}(\mathcal{H}),w)\) 产生新图 \(\mathcal{G}'\)，即原本沿 \(e\) 流动的值现在经过 \(\mathcal{H}\)。在*边*上定义插入（而非“在节点上”）消除了关于 \(u\) 的哪些消费者被重路由的歧义：恰好是沿 \(e\) 的那些。两个突变原语涵盖了本文所有工作负载：*嫁接*在站点添加 \(h=|\mathcal{V}(\mathcal{H})|\) 个新的可计算节点；*修补*就地重定义已有节点的规则（例如，将激活值替换为存储的或损坏的值），稍后通过将规则重定义回来*恢复*——同一站点的两次突变，每次都触发相同的失效过程。

在反应式引擎中，每个节点都携带一个有效性标志；对节点 \(s\) 的突变使其依赖者失效，之后按需驱动求值（demand!）精确重新计算失效区域。我们将失效过程形式化为算法 1，并重新陈述本文核算所依赖的局部性定理；NeuroDSL 例程 `_invalidate_downstream!` 实现了该算法（实现一致性是工程声明，由测试套件验证，不属于证明部分）。

**算法 1** Invalidate\((\mathcal{G},s)\)——从种子节点 \(s\) 开始的反应式失效
1: \(Q\leftarrow[s]\); \(\mathrm{seen}\leftarrow\{s\}\)
2: **while** \(Q\) 非空 **do**
3:   \(v\leftarrow\mathrm{pop}(Q)\)
4:   **for each** \(w\) 使得 \((v,w)\in\mathcal{E}\) **do**
5:     **if** \(w\notin\mathrm{seen}\) **then**
6:       \(\mathrm{valid}(w)\leftarrow\mathbf{false}\); \(\mathrm{seen}\leftarrow\mathrm{seen}\cup\{w\}\); \(\mathrm{push}(Q,w)\)
7:     **end if**
8:   **end for**
9: **end while**

###### 定义 3（下游锥体）

对于 \(s\in\mathcal{V}\)，令 \(\mathcal{V}_{s}^{+}= \{\, v\in\mathcal{V}\mid \text{存在从 }s\text{ 到 }v\text{ 的长度 }\geq 1\text{ 的路径}\,\}\)。按惯例 \(s\notin\mathcal{V}_{s}^{+}\)，除非 \(s\) 位于环上，而 DAG 性质排除了这种情况；当突变是嫁接时，种子 \(s=\mathrm{out}(\mathcal{H})\) 是新创建的节点，出生即无效，无需失效。

###### 定理 1（结构局部性）

在 DAG 上，算法 1 终止，并且它标记为无效的节点集合恰好是 \(\mathcal{V}_{s}^{+}\)。其复杂度为 \(O(|\mathcal{V}_{s}^{+}|+|\mathcal{E}_{s}^{+}|)\)，其中 \(\mathcal{E}_{s}^{+}\) 是锥体内部的边集。

###### 证明

*终止性*：每个节点至多进入一次 \(\mathrm{seen}\) 并至多被入队一次；\(\mathcal{V}\) 是有限的。

*可靠性*（标记 ⇒ 在锥体内）：通过对标记顺序进行归纳，证明每个标记为无效的节点位于 \(\mathcal{V}_{s}^{+}\) 中。首先被标记的节点是 \(s\) 的直接后继，它们通过长度为 1 的路径在 \(\mathcal{V}_{s}^{+}\) 中。归纳地，一个节点 \(w\) 仅当沿边 \((v,w)\) 从队列弹出时被标记，且 \(v\) 先前被标记或 \(v=s\)；由归纳假设存在路径 \(s\rightsquigarrow v\)（若 \(v=s\) 则为空），扩展 \((v,w)\) 得到从 \(s\) 到 \(w\) 的长度 \(\geq 1\) 的路径。因此 \(w\in\mathcal{V}_{s}^{+}\)。

*完备性*（在锥体内 ⇒ 被标记）：设 \(w\in\mathcal{V}_{s}^{+}\)，且设 \(s=v_0\to v_1\to\dots\to v_k=w, k\geq 1\) 是一条见证路径。对 \(i\) 归纳：\(v_0=s\in\mathrm{seen}\) 并被处理；若 \(v_i\) 被处理，则当其弹出时，其后继 \(v_{i+1}\) 要么已在 \(\mathrm{seen}\) 中（因此先前被标记并入队），要么现在被标记并入队。无论哪种情况 \(v_{i+1}\) 被标记并最终被处理。因此 \(v_k=w\) 被标记。

*保持性*：由可靠性，不在 \(\mathcal{V}_{s}^{+}\) 中的节点永不被标记，因此 \(\mathrm{valid}(v)\) 不受影响：其缓存值在突变后仍存活。

*复杂度*：锥体中每个节点弹出一次，每条内部边扫描一次。

∎

定理 1 将*单次*突变的成本限定在其下游锥体。接下来的所有内容是对由多个此类突变构成的工作负载进行核算。

## 4 穷举扫描的聚合成本

测试每个候选站点的调用者（消融扫描、电路发现搜索或系统性鲁棒性检查）需支付每个站点锥体成本之和，很自然地要问：这个总成本与通过独立全重新计算测试每个站点的成本相比如何？答案取决于一个数字：计算权重在深度上的分布。

###### 定义 4（分层成本模型）

深度为 \(L\) 的*分层 DAG* 为每一层 \(j\in\{1,\dots,L\}\) 赋予计算权重 \(w_j>0\)（例如节点数），每层有 \(S\) 个候选站点，每个站点的下游锥体（在下面比值中忽略每个站点的 \(O(1)\) 余项）近似等于其所属层 \(i\) 的后缀 \(\sum_{j>i} w_j\)。记 \(N(L)=\sum_{j=1}^L w_j\) 为总权重，\(\rho(L)=\frac{SL\cdot N(L)}{S\sum_{i=1}^L\sum_{j>i} w_j}\) 为 \(SL\) 次独立全重新计算相对于通过定理 1 精确锥体穷举修补每个站点聚合成本的比值。

###### 定理 2（聚合扫描比值）

假设当 \(j\to\infty\) 时 \(w_j\sim \ell(j)\, j^q\)，其中 \(q\geq 0\)，\(\ell\) 在无穷远处缓慢变化（Karamata：对所有 \(c>0\) 有 \(\ell(cx)/\ell(x)\to 1\)）。则
\[
\rho(L) \longrightarrow \frac{q+2}{q+1} \quad (L\to\infty).
\]
若权重轮廓相反：\(w_j\sim \ell(L+1-j)\,(L+1-j)^q\)（*输入*附近的层权重更大），则极限为
\[
\rho(L) \longrightarrow q+2.
\]
特别地，\(q=0\)（每层均匀权重，\(w_j\equiv M\)）在两种轮廓下均给出 \(\rho(L)\to 2\)。

###### 证明

记 \(S(n)=\sum_{j=1}^n w_j\)；由规则变化序列的 Karamata 定理，\(S(n)\sim n w_n/(q+1)\)...