CRAM把数独求解写成能量下降:训练42毫秒解出99.996%的Sudoku-Extreme,比循环模型快千倍
核心概要
一种可训练的能量模型CRAM把推理变成在能量函数上的循环下降,权重直接从已解谜题中学得。在Sudoku-Extreme上它解出99.996%的测试题,在Maze-Unique上解出全部测试迷宫,单张GPU训练分别只需42毫秒和132毫秒,比循环模型至少快1000倍。它同时提示,数独和迷宫这类谜题的高分不足以衡量循环推理方法在更难任务上的可扩展性。
深度剖析
推理可以不再靠反复套用同一组网络层,而是靠最小化一个从数据中学到的能量函数;这个能量模型叫CRAM,在约束类谜题上同时拿到更高准确率和极短训练时间。 此前的循环推理模型把一层或一组层反复施加来产生答案,在数独和迷宫上有效,但训练慢、不稳定,且需要大量参数和浮点运算。 在Sudoku-Extreme上CRAM解出99.996%的测试题,最准的循环基线TRMP为99.87%;在Maze-Unique上CRAM解出100%,TRMP为99.23%。CRAM的拟合时间为42毫秒和132毫秒,而各循环基线的拟合时间从约13分钟到二十余小时不等。
推理过程是让每个格子的候选值信念沿能量梯度反复更新,直到能量降到由训练解拟合出的阈值以下,或没有任何单格改动能再降低能量。 能量写成格与格之间成对代价加每格偏置的均值场自由能形式,是连续Hopfield网络能量到多状态神经元的推广;训练用伪似然目标,直接在标注解上计算,不需要对推理轨迹做反向传播。 在Sudoku-Extreme的每一次训练中,CRAM都学到只在同行、同列或同宫的810个格子对上放置相等的正代价,其余代价为零;在Maze-Unique上,18个学到的代价使搜索每步关掉一个死端格子,即死端填充。
能量给出天然的停止判据,使计算量随谜题难度变化,并且从不在错误棋盘上停下。 循环模型通常另加一个停止网络或按梯度范数判断何时停止,这些规则会在部分谜题上于错误棋盘处停止。 把1万道Sudoku-Extreme测试题按数据集难度分箱后,CRAM的中位计算量从最易箱到最难箱增长22倍;HRM、TRM、EqR、TRMP和EBR的停止规则分别在0.05%到3.54%的已停止谜题上停在错误棋盘,CRAM为0。
启示与展望
演示范围限于Sudoku-Extreme、Maze-Unique、N-Queens和8与10顶点的图着色这四类约束谜题,它们都能被CRAM的成对能量精确表示;所有拟合时间都是单张H200上的实测墙钟时间。对Maze-Hard,原始CRAM一道测试迷宫也解不出,加入一层隐神经元后三次训练各解出1000道测试迷宫中的999道。
高准确率只说明模型学到了答案格子之间的少数成对规则,因此这些基准上的高分不预示在ARC-AGI这类更难任务上的表现。在数据极少的情形下CRAM会收敛到许多错误解,而TRM在最少训练谜题时解出的测试题最多。拟合时间在共享集群上测得,会随节点上的并发任务变化。
