IGLM（三）：DILR、随机组合与 Scaling Law 的概率解释
说明：本文中的具体实现、数学整理与写作表述均由 GPT 辅助完成，笔者本人主要负责提出核心想法、研究方向与关键判断。
前两篇主要做了两件事：
- 把“学习就是压缩”具体化为最小计算元素集合；
- 把学习过程写成“从原始元素出发，迭代扩展元素集合”的结构问题。
这一篇终于进入算法本身。
我的要求其实不高：现阶段我并不打算先解决复杂度最优、工程吞吐、启发式搜索这些问题，而是只抓住一个核心点：
如果允许不断堆算力，能不能有一种最简单的算法，使得系统对目标结构的解释单调变好，并最终以非零概率逼近最优路径？
DILR（Dijkstra-Iterative Logic Rewriting）就是围绕这个目标设计出来的。
背景
如果按照上一篇的完全闭包定义
\[E_{t+1}^{\mathrm{full}} = E_t \cup \{ op(g,h) \mid g,h \in E_t,\ op \in \Omega \},\]那么每一轮的候选数量会非常快地爆炸：
\[|E_{t+1}^{\mathrm{full}} \setminus E_t| \le |\Omega|\cdot |E_t|^2.\]这在理论上没问题，但在实际中根本不可能完整枚举。
所以真正可行的做法一定不是“每轮生成所有二元组合”，而是“每轮只采样极少数候选”。问题变成：
- 采样之后，怎样定义当前最优结构？
- 如果后来发现更短路径，怎样更新？
- 这个过程为什么会随着算力增加而越来越接近最优结构？
DILR 的出发点就是这三个问题。
目标函数与状态表示
仍然考虑目标函数
\[f : X \to \{0,1\},\]原始元素集合为
\[\mathcal P = \{x_1,\dots,x_n,0,1\},\]二元运算符集合为
\[\Omega = \{op_1,\dots,op_r\}.\]一个计算元素 $g$ 本身就是从 $X$ 到 ${0,1}$ 的函数，因此可以直接把它当成一个状态。对于有限输入空间，这个状态甚至可以显式表示成真值表。
于是 DILR 的状态空间就是所有可达函数的集合。关键不在于状态多，而在于：
对每个状态，只保留当前已知的最短生成路径。
代价函数
设 $c(g)$ 表示生成元素 $g$ 的当前最优代价。最简单的定义就是“新增中间元素数量”，也就是每次通过一次二元组合产生新元素时，代价加 1。
初始化时，对于原始元素
\[\forall p \in \mathcal P, \quad c(p)=0.\]如果某个新元素由
\[g = op(a,b), \quad a,b \in E_t,\]生成，那么候选代价为
\[\tilde c(g) = c(a)+c(b)+1.\]这里的 $+1$ 表示“引入了一个新的组合元素”。如果后续实现里要考虑共享子结构、哈希合并、图重用，那么代价函数还可以改得更精细，但当前这一版已经足够表达核心思想。
DILR 算法定义
DILR 维护一个映射表
\[M_t : g \mapsto (c_t(g), \pi_t(g)),\]其中：
- $g$ 是某个已经发现的计算元素；
- $c_t(g)$ 是第 $t$ 轮时该元素的当前最优代价；
- $\pi_t(g)$ 是对应的生成路径或父节点信息。
初始化：
\[M_0 = \{ (p, 0, \varnothing) \mid p \in \mathcal P \}.\]第 $t+1$ 轮做一次随机扩展：
- 从当前元素池 $E_t = \mathrm{dom}(M_t)$ 中随机采样两个元素 $a_t, b_t$；
- 从 $\Omega$ 中随机采样一个二元运算符 $op_t$；
- 构造候选元素 \(g_t = op_t(a_t,b_t);\)
- 计算候选代价 \(\tilde c_t = c_t(a_t)+c_t(b_t)+1;\)
- 执行松弛更新：
- 如果 $g_t \notin E_t$，则把 $g_t$ 加入映射表；
- 如果 $g_t \in E_t$ 但 $\tilde c_t < c_t(g_t)$，则用新路径覆盖旧路径；
- 否则丢弃本轮候选。
如果写成伪代码，大概就是：
M = {p: (0, None) for p in primitives}
for t in range(T):
a = sample_state(M)
b = sample_state(M)
op = sample_operator(Omega)
g = op(a, b)
cand = cost[a] + cost[b] + 1
if g not in M or cand < cost[g]:
M[g] = (cand, (op, a, b))
这就是 DILR 的最简形式。
为什么它是“单调递优”的
DILR 最核心的性质很简单，但非常重要。
对于任意元素 $g$，定义第 $t$ 轮时的当前最优代价为 $c_t(g)$。按照松弛规则，有
\[c_{t+1}(g) = \min\big(c_t(g), \tilde c_t(g)\big),\]其中如果本轮没有生成 $g$ 的候选路径，可以视为 $\tilde c_t(g)=+\infty$。
于是立刻得到
\[c_{t+1}(g) \le c_t(g).\]这说明对任何状态，DILR 都不会让当前最优解释变差。特别地，对目标函数 $f$ 来说，如果记
\[C_t(f)=c_t(f),\]那么序列
\[C_0(f), C_1(f), C_2(f), \dots\]是一个单调非增序列。
这就是 DILR 最重要的理论价值：
训练过程不是在一个不透明目标上振荡，而是在结构代价上做单调松弛。
最优路径的概率可达性
单调递优还不够，我们还需要解释为什么“堆算力”真的有意义。
设目标函数 $f$ 的某条最优生成路径为
\[pi^* = (g_1^*, g_2^*, \dots, g_L^*),\]其中：
- 每个 $g_i^*$ 都是通过某个二元运算从更早的元素生成；
- 最后 $g_L^* = f$；
- 这条路径的总代价达到最小值 \(c^*(f)=K_\Omega(f;\mathcal P).\)
现在假设采样策略具有全局支撑，也就是说：
- 对任意当前已发现元素 $a,b$，都有 \(\Pr[(a_t,b_t)=(a,b)] > 0;\)
- 对任意 $op \in \Omega$，都有 \(\Pr[op_t=op] > 0.\)
那么只要最优路径的前缀已经被发现，下一步生成正确后继元素的概率就始终大于 0。
更具体地，设当最优路径前 $i-1$ 个元素都已经进入状态池后，单轮正确生成 $g_i^*$ 的概率下界为 $p_i>0$。那么在 $K$ 次独立有效尝试后，至少命中一次该步骤的概率满足
\[P_i(K) = 1-(1-p_i)^K.\]当 $p_i$ 很小时，有近似
\[P_i(K) \approx 1-e^{-Kp_i}.\]如果进一步把整个路径的关键步骤合并成一个等效事件，记单轮命中“某条把目标代价降到不超过 $c$ 的路径”的概率为 $q_c$，则有
\[\Pr[C_K(f) \le c] = 1-(1-q_c)^K \approx 1-e^{-Kq_c}.\]这个式子已经足够说明一个核心现象：
算力的价值，就是不断放大命中更优结构的累计概率。
如何从这个概率式子得到 Scaling Law
上面的公式还是一般形式，要把它和 scaling law 联系起来，还需要一个关于搜索空间的假设。
最自然的假设是：代价越低的结构越稀有，因此命中代价不超过 $c$ 的改进路径概率会随着 $c$ 下降而快速变小。一个简单模型是
\[q_c \approx B^{-c}, \quad B>1,\]其中 $B$ 可以理解成有效分支因子。这个式子的含义是：
- 想把结构代价再降低一点；
- 需要命中的搜索路径会指数级更稀有。
把它代入前面的累计概率式子：
\[\Pr[C_K(f) \le c] \approx 1-e^{-K B^{-c}}.\]当这个概率达到常数量级，比如 $1-1/e$ 时，有
\[K B^{-c} \approx 1.\]于是得到
\[c \approx \log_B K.\]也就是说，在这种最简单的模型下，随着算力 $K$ 增加，系统能够命中的更优结构代价会按对数规律下降。
如果任务误差 $L(K)$ 单调依赖于当前最优结构代价 $C_K(f)$，那么就自然得到一种 scaling law 解释：
- 算力变多；
- 命中更优路径的概率上升；
- 当前最优结构复杂度下降；
- 宏观误差继续下降。
这和通常从参数量或数据量直接拟合幂律不同。这里的解释更偏结构主义：
Scaling law 不是参数统计本身的规律，而是搜索命中更优结构路径的概率规律。
为什么会出现“涌现”
这个框架下，“涌现”也很容易解释。
如果某个关键中间元素一旦被发现，就能大规模复用，那么在它被命中之前，系统一直表现得像是在记忆碎片；在它被命中之后，整个结构复杂度会突然下降，泛化能力也会突然上升。
也就是说，涌现对应的不是某个神秘能力突然出现，而是：
DILR 首次命中了一个压缩收益极大的关键中间结构。
这个现象在加法器任务里尤其容易出现。比如进位链相关的关键结构一旦被找到，大量原本分散的样本就会被统一解释，表现上就像“突然学会了加法”。
当前版本为什么不急着谈优化
DILR 当然还有很多可以改进的地方：
- 可以设计更聪明的采样策略；
- 可以加启发式距离；
- 可以做分层搜索；
- 可以缓存共享子结构；
- 可以并行化松弛。
但这些都不是当前最重要的事。
我现在更关心的是，把理论主线先说清楚：
- 状态是计算元素；
- 新状态由随机二元组合产生；
- 每个状态始终保留当前最短路径；
- 因此目标代价单调不增；
- 随着迭代次数增加，命中更优路径的累计概率持续上升；
- scaling law 可以由这个概率过程直接解释。
只要这条主线是成立的，后面的优化才有方向。否则先堆一堆技巧，只会把问题重新做回一个黑箱搜索器。
这一篇的结论
DILR 可以看成 IGLM 的第一代核心算法。它不追求现在就高效，而是先追求三件事：
- 定义清楚：元素如何被生成；
- 性质清楚：最优代价如何单调下降；
- 解释清楚：为什么算力增加会带来结构改进。
用公式总结就是：
- 元素生成： \(g_t = op_t(a_t,b_t), \quad a_t,b_t \in E_t,\ op_t \in \Omega;\)
- 代价松弛： \(c_{t+1}(g)=\min(c_t(g), \tilde c_t(g));\)
- 概率命中： \(\Pr[C_K(f) \le c] \approx 1-e^{-Kq_c};\)
- 若 $q_c \approx B^{-c}$，则 \(c \approx \log_B K.\)
到这里，IGLM 这条主线就基本完整了：
- 第一篇定义压缩对象；
- 第二篇定义迭代扩展的学习过程；
- 第三篇给出 DILR 及其对 scaling law 的概率解释。
后面如果继续写，我更想做的是实验篇，直接用加法器或其他离散任务去验证：随着迭代次数增加，目标函数的当前最优结构代价是否真的按预期下降，以及泛化能力是否会在关键结构命中后出现跃迁。