神经推理模型在填数谜题中实为单次预测,而非迭代搜索。
Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion
- 首通计算即锁定大部分答案,搜索本质是验证而非推演
- 9×9谜题准确率从不足1%提升至96.5%,靠对称增强训练
- 无需重训,测试时对称变换合并可让难题准确率达100%
神经求解器本应逐步推断、分支与修正中间状态,但基于线索丰富的数独任务中,Lattice Deduction Transformer(LDT)仅需一次前向传播,便基本确定整个网格(标准6×6完全锁定,扩展9×9达94-96%),使迭代求解退化为单次预测加精确验证。所有困难实例的失败皆由首次推理中错误删除解所需数值导致,称为首通污染。引入学习分支、最小剩余变量(MRV)、回溯、值排除和共享无用信息(CoLT)虽不改变可解实例范围,但使无效推导减少1,497倍。在固定训练预算下,约束图注意力即可达到完整CoLT精度,而位置表需更长训练才有效,表明其优势在于优化效率而非绝对容量。诊断提示两种有效干预:数字置换增强将9×9准确率从低于1%提升至96.5±0.3(三组训练种子,对称无关划分);测试时对称变换多路结果合并,使三个困难切片准确率从72.8%-78.9%升至100%,无需重训。在从头开始的图着色任务中,单次行为消失,搜索影响准确率。在线索密集补全任务中,类似LDT的系统实为单次摊销预测器,非学习搜索过程:准确率由校准与对称性决定,搜索仅用于清除计算冗余。
原文摘要 · Abstract (English)
Neural solvers are built to deduce, branch, and revise intermediate states. The Lattice Deduction Transformer (LDT) appears to do exactly that. In clue-rich Sudoku, it does not: one forward pass commits essentially the entire grid (every blank cell on standard 6x6, 94-96% on augmented 9x9), turning the iterative solver into a one-shot predictor wrapped in an exact verifier. All hard-slice failures are decided before search begins, when the first pass confidently deletes a value required by the true solution. We call this first-pass poisoning. Adding learned branching, MRV, backtracking, value exclusion, and shared nogoods (CoLT) does not change which Sudoku instances are solved; it cuts repeated invalid derivations 1,497-fold. At the frozen training budget, constraint-graph attention alone matches full-CoLT accuracy, while positional tables recover only under substantially longer training, indicating an optimization and sample-efficiency advantage rather than an absolute capacity difference. The diagnosis predicts two effective interventions. Digit-permutation augmentation raises 9x9 accuracy from below 1% to 96.5 +/- 0.3 across three training seeds on a symmetry-disjoint split. Test-time union over symmetry-transformed passes raises all three hard-slice checkpoints from 72.8-78.9% to 100% without retraining. On from-scratch graph coloring, one-shot behavior disappears and search changes accuracy. In clue-rich completion, LDT-like systems are one-shot amortized predictors rather than learned search procedures: accuracy is determined by calibration and symmetry, while search primarily removes computational waste.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。