arXiv:2601.04675cs.AI2026-01AAAI被引 3

用大模型指导符号求解,让复杂逻辑公式更快找到答案

LLM-Guided Quantified SMT Solving over Uninterpreted Functions

  • 用大模型生成函数定义候选,缩小求解搜索空间
  • 在SMT-COMP测试中解决多个传统工具超时的实例
  • 适合需要高效处理非线性实数公式的符号推理研究者

带有未解释函数的非线性实数算术量化公式给满足模理论(SMT)求解带来根本性挑战。传统量化实例化方法因缺乏对未解释函数约束的语义理解,需在无界解空间中盲目搜索,引导不足。本文提出AquaForte框架,利用大语言模型为未解释函数实例化提供语义引导,通过生成满足约束的函数定义候选,显著压缩求解器的搜索空间与复杂度。该方法先对公式进行约束分离,使用结构化提示从大模型中提取数学推理,并通过自适应实例化将结果与传统SMT算法融合。通过系统验证确保严谨性:大模型生成的实例若为可满足,则原问题可解;若为不可满足,则生成排除子句用于迭代优化。完整性通过回退至增强学习约束的传统求解器保障。在SMT-COMP基准上的实验表明,AquaForte解决了多个当前先进求解器(如Z3、CVC5)超时的实例,尤其在可满足公式上表现突出。本工作证明大模型可为符号推理提供有价值的数学直觉,开创了SMT约束求解的新范式。

原文摘要 · Abstract (English)

Quantified formulas with Uninterpreted Functions (UFs) over non-linear real arithmetic pose fundamental challenges for Satisfiability Modulo Theories (SMT) solving. Traditional quantifier instantiation methods struggle because they lack semantic understanding of UF constraints, forcing them to search through unbounded solution spaces with limited guidance. We present AquaForte, a framework that leverages Large Language Models to provide semantic guidance for UF instantiation by generating instantiated candidates for function definitions that satisfy the constraints, thereby significantly reducing the search space and complexity for solvers. Our approach preprocesses formulas through constraint separation, uses structured prompts to extract mathematical reasoning from LLMs, and integrates the results with traditional SMT algorithms through adaptive instantiation. AquaForte maintains soundness through systematic validation: LLM-guided instantiations yielding SAT solve the original problem, while UNSAT results generate exclusion clauses for iterative refinement. Completeness is preserved by fallback to traditional solvers augmented with learned constraints. Experimental evaluation on SMT-COMP benchmarks demonstrates that AquaForte solves numerous instances where state-of-the-art solvers like Z3 and CVC5 timeout, with particular effectiveness on satisfiable formulas. Our work shows that LLMs can provide valuable mathematical intuition for symbolic reasoning, establishing a new paradigm for SMT constraint solving.

SMT求解大模型符号推理

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