arXiv:2607.17047cs.LGcs.AI2026-07

区分模型难易与求解器难易,揭示LLM推理的表面敏感性。

Solver-Hard Is Not Model-Hard: A Hardness-Controlled Diagnostic for LLM Constraint Reasoning

  • 用密度匹配的公式对比求解难易,分离出真实推理难度
  • 模型准确率与冲突数无一致关联,证明其判断不可靠
  • 适合关注大模型约束推理可信度的研究者

大型语言模型(LLM)在评估约束推理时,常在随机-满足相变附近进行,导致密度与求解难度混杂。本文在近似相同子句密度下,测试实例级迁移性能。在尺寸和最大子句宽度匹配的情况下,比较了证明困难的膨胀型Tseitin公式与证明简单的梯形型Tseitin公式、鸽巢锚定问题以及密度不匹配的对照组。理论表明它们的可解性存在差异:以Glucose的平均冲突数为代理指标,两者差距可达51倍,其他五个求解器也保持相同趋势。在三个纳入模型中(每模型243个实例;第四模型因拒绝回答被排除),近似密度下的准确率差距为-32至+20点,总体差距为+1.7点(p=0.74),且正确率与冲突数呈正相关(r=+0.15),方向错误。一种保持证明结构的重标注使一个模型所有簇的准确率下降93点,但另一模型不受影响,暴露模型表面敏感性。预注册扩展显示,考虑公式长度并剔除异常值后,提供商报告的完成令牌消耗并未随代理指标稳定上升。在16k上下文长度下,推理模型对证明简单的匹配公式消耗更多令牌,并在求解最易的非可满足家族耗尽预算;32k上下文长度下,1号簇的差距消失。这些结果说明验证准确性和观察到的令牌消耗之间存在脱节,但不涉及证书求解、精确证明长度或分配效率。

原文摘要 · Abstract (English)

LLM constraint reasoners are often evaluated near the random-SAT phase transition, confounding density and solver hardness. We test instance-level transfer while near-matching clause density. At aligned size bins, with near-matched density and matched maximum clause width, we compare proof-hard expander-Tseitin and proof-easy ladder-Tseitin formulas, pigeonhole anchors, and density-mismatched controls. Theory separates their resolution hardness; a solver-specific Glucose mean-conflict proxy differs by up to $51\times$, and five other solvers preserve the direction. Across three included models (243 instances each; a fourth is excluded for abstention), the near-matched-density accuracy gaps range from $-32$ to $+20$ points, with a pooled gap of $+1.7$ points ($p=0.74$) and a wrong-signed correctness-versus-conflict association ($r=+0.15$). A proof-preserving relabeling lowers accuracy in all five clusters for one model (mean $-93$ points) but not another, exposing model-surface sensitivity. In a preregistered extension, provider-reported completion-token spend does not consistently increase with the proxy after accounting for formula length and censoring. At 16k, the reasoning model spends more on proof-easy matched formulas and exhausts its budget on the solver-easiest UNSAT family; the 32k C1 gap is absent. These scoped dissociations concern verdict accuracy and observed token spend, not certificate solving, exact proof length, or allocation efficiency.

大模型推理约束求解可解释性评测基准

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。