用网格结构特征提前预测解题成功，准确率达88.5%。
Structural Grid Descriptors Predict Within-Task Solver Success on ARC-AGI
- 提取中间状态的网格结构特征，判断解题能否成功
- 50%进度时特征区分成功率，平均准确率88.5%
- 适用于不同解法架构，可大幅节省计算资源
我们探究符号化ARC-AGI求解器在任务中的中间网格状态的结构特性是否能预测其成功与否，以条件互信息I(X;Y|task) > 0为框架。在覆盖400个任务、28种配置、两套不同架构求解器（束搜索与随机深度优先搜索）的44,800次运行中，于50%轨迹完成时手工设计的网格描述符可有效区分同一任务内的成功与失败运行（平均任务内最佳特征AUC=0.885，p<0.001，经任务内标签置换检验）。最具预测性的内容集中在一个网格复杂度轴上。该结果在不同求解器间具有泛化能力：在一个求解器上选出的特征在另一求解器上预测成功，AUC达0.747–0.762，四种转移方向均显著（p<0.001，控制泄漏）。在预注册的41个可靠任务集上，冻结特征n_components_final达到AUC=0.765（95%置信区间[0.717, 0.810]，p<0.001），在任务聚类重采样与跨求解器任务合并下仍稳健。信号不受求解器容量影响（配置残差后AUC分别为0.927和0.896，p<0.001），且与得分轨迹关联极弱（R²≈0）。在50%处提前终止可使束搜索计算减少33.6%，保留98.9%的解题数；退化轨迹检测使SDFS计算减少65.3%且无解题丢失。此外，在400个评估任务中的229个，DSL原始操作库无法从输入网格生成有效转换，出现0步崩溃，此现象与搜索预算无关，且束搜索全数失败，表明这是DSL覆盖范围不足所致而非搜索预算问题。
原文摘要 · Abstract (English)
We ask whether structural properties of intermediate grid states predict whether a symbolic ARC-AGI solver will succeed, framed as a test of conditional mutual information I(X;Y|task) > 0. Across 44,800 runs spanning two architecturally distinct solvers (beam search and Stochastic DFS), 400 ARC tasks, 28 configurations per solver, and both training and evaluation splits, hand-crafted grid descriptors measured at 50% trajectory completion discriminate successful from failed runs within the same task (mean within-task best-feature AUC = 0.885, p < 0.001 under within-task label permutation). Most predictive content lies along a single grid-complexity axis. The result generalizes across solver architectures: a feature selected on one solver predicts success on the other with AUC 0.747-0.762 in all four transfer directions (p < 0.001, leakage controlled). On a pre-registered held-out set of 41 reliable tasks, the frozen feature n_components_final achieves AUC = 0.765 (95% CI [0.717, 0.810], p < 0.001), robust under task-clustered bootstrap resampling and cross-solver task collapsing. The signal is not explained by solver capacity (configuration-residualized AUC = 0.927 and 0.896 for beam search and SDFS, p < 0.001) and is only weakly coupled to score trajectories (R^2 approximately 0). Early stopping at 50% completion reduces beam-search compute by 33.6% while retaining 98.9% of solves; degenerate-trajectory detection reduces SDFS compute by 65.3% with no solve loss. Finally, on 229 of 400 evaluation tasks the DSL primitive library produces no valid transition from the input grid. This 0-step collapse is invariant to search budget and universally failed by beam search, indicating a DSL coverage limitation rather than a search-budget effect.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。