arXiv:2605.28602cs.AIcs.CL2026-05中稿 · the ACM Internatio…被引 2

用配对公式评估大模型的逻辑推理能力,发现传统指标易误导。

Satisfiability Solving with LLMs: A Matched-Pair Evaluation of Reasoning Capability

  • 设计配对公式协议,要求正确区分相似但一可满足一不可满足的实例。
  • 多数模型在变量增多时性能骤降,且难以复现3-SAT的难易转折特征。
  • 适合评估大模型真实推理能力,尤其关注逻辑一致性与跨表示稳定性。

大型语言模型(LLMs)被广泛用于隐含归约为布尔可满足性(SAT)的问题,但其在SAT任务上的推理能力尚不明确。本文系统研究了LLMs在2-SAT和3-SAT任务上的表现,并引入两种经典归约:顶点覆盖(Vertex Cover)与离散三维装箱问题(discrete 3D packing),以检验表示不变的推理能力。首先使用准确率、精确率、召回率、F1分数及SAT相变设置进行评估,发现这些指标具有误导性:许多模型通过过度预测可满足公式获得高分,无法再现经典3-SAT阈值附近的易-难-易特征,且随变量数量增加性能显著下降。为此,提出基于最小差异可满足/不可满足公式的配对协议,结合准确区分率(ADR),要求每对中的两个实例均被正确分类。ADR能有效区分推理型模型与启发式模型,并与解的有效性相关。此外,将CNF转换为顶点覆盖或3-SAT转为离散三维装箱,测试跨表示一致性:大多数模型在超过80%的实例上在不同表示下的决策一致,表明其决策规则具有稳定性。总体而言,结果表明SAT是评估大模型推理能力的保守基准,而基于ADR的配对评估比传统指标更忠实且具表示鲁棒性。

原文摘要 · Abstract (English)

Large language models (LLMs) are increasingly used for tasks that implicitly reduce to Boolean satisfiability (SAT), yet their reasoning ability on SAT remains unclear. We present a systematic study of LLMs on 2-SAT and 3-SAT, together with two canonical reductions, Vertex Cover and discrete 3D packing, to probe representation-invariant reasoning. We first evaluate models using conventional metrics, including accuracy, precision, recall, and F1, as well as the SAT phase-transition setting. We find that these metrics can be misleading: many models obtain high scores by over-predicting satisfiable formulas, fail to reproduce the classical easy-hard-easy signature around the 3-SAT threshold, and degrade sharply as the number of variables grows. To address this problem, we introduce a paired-formula protocol based on minimally different satisfiable and unsatisfiable instances, together with Accurate Differentiation Rate (ADR), which requires both members of each pair to be classified correctly. ADR separates reasoning-oriented models from heuristic ones and correlates with witness validity. Beyond CNF, we test cross-representation consistency by converting CNF to Vertex Cover and 3-SAT to discrete 3D packing. Model decisions on CNF and on the corresponding graph or packing instances agree for most models on more than 80 percent of instances, suggesting stable decision rules across representations. Overall, our results show that SAT is a conservative probe for LLM reasoning, and that paired evaluation with ADR provides a more faithful and representation-robust assessment than conventional metrics.

逻辑推理大模型评估可满足性交叉表示

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