Can LLMs Solve ASP Problems? Insights from a Benchmarking Study (Extended Version)

📄 arXiv: 2507.19749v1 📥 PDF

作者: Lin Ren, Guohui Xiao, Guilin Qi, Yishuai Geng, Haohan Xue

分类: cs.AI

发布日期: 2025-07-26

备注: Accepted for publication at the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR 2025). The code is available at https://github.com/HomuraT/ASPBench

🔗 代码/项目: GITHUB

💡 一句话要点

ASPBench：构建ASP基准测试，揭示LLM在解答集编程中的局限性

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 解答集编程 大型语言模型 逻辑推理 基准测试 非单调推理

📋 核心要点

  1. 现有LLM在解答集编程(ASP)方面的评估不足，缺乏全面、支持复杂逻辑结构的基准测试。
  2. 论文构建ASPBench基准，包含ASP蕴含、解答集验证和解答集计算三个任务，用于全面评估LLM的ASP能力。
  3. 实验表明，LLM在简单的ASP任务上表现尚可，但在核心的解答集计算任务上表现不佳，存在明显局限性。

📝 摘要（中文）

本文提出ASPBench，一个全面的解答集编程(ASP)基准测试，旨在评估大型语言模型(LLM)在非单调推理方面的能力。现有对LLM在ASP能力评估通常过于简化，不支持否定、析取或多重解答集，且缺乏专门为ASP求解设计的基准。ASPBench包含三个ASP特定任务：ASP蕴含、解答集验证和解答集计算。对包括deepseek-r1、o4-mini和gemini-2.5-flash-thinking在内的14个先进LLM的广泛评估表明，它们在前两个较简单的任务上表现相对较好，但在作为ASP求解核心的解答集计算方面表现不佳。这些发现揭示了LLM在ASP求解方面的局限性，强调了开发更有效地整合符号推理能力的新方法的需求。代码和数据集可在https://github.com/HomuraT/ASPBench获取。

🔬 方法详解

问题定义：论文旨在解决现有大型语言模型(LLM)在解答集编程(ASP)问题求解能力评估不足的问题。现有评估方法通常使用过于简化的ASP程序，不支持否定、析取或多重解答集，并且缺乏专门为ASP求解设计的基准测试。这使得我们难以准确评估LLM在处理复杂逻辑推理任务时的能力。

核心思路：论文的核心思路是构建一个更全面、更具挑战性的ASP基准测试集，即ASPBench，以更准确地评估LLM在ASP问题求解方面的能力。通过设计包含ASP蕴含、解答集验证和解答集计算等任务，可以更细粒度地分析LLM在不同ASP任务上的表现，从而揭示其优势和局限性。

技术框架：ASPBench基准测试集包含三个主要任务：1) ASP蕴含：判断给定的ASP程序是否蕴含某个逻辑语句；2) 解答集验证：验证给定的解答集是否是ASP程序的有效解答集；3) 解答集计算：计算给定ASP程序的所有解答集。研究人员使用这些任务来评估各种LLM的性能。整体流程包括：定义ASP问题 -> 使用LLM生成答案 -> 评估LLM答案的正确性。

关键创新：该论文的关键创新在于构建了一个专门针对ASP问题求解的基准测试集ASPBench。与以往的简化评估方法不同，ASPBench支持更复杂的ASP程序结构，包括否定、析取和多重解答集。这使得研究人员能够更全面、更准确地评估LLM在处理复杂逻辑推理任务时的能力。

关键设计：ASPBench的设计考虑了ASP问题的不同难度级别，并针对每个任务设计了相应的评估指标。例如，对于解答集计算任务，评估指标包括计算出的解答集的完整性和正确性。此外，ASPBench还提供了多种ASP程序的生成方法，以确保基准测试集的多样性和代表性。具体的参数设置和损失函数取决于所使用的LLM模型，论文主要关注不同LLM在ASPBench上的性能比较，而非特定LLM的微调。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，虽然LLM在ASP蕴含和解答集验证等简单任务上表现尚可，但在解答集计算这一核心任务上表现不佳。例如，即使是最先进的LLM，在处理包含否定和析取的复杂ASP程序时，其解答集计算的准确率也远低于专业的ASP求解器。这突显了LLM在符号推理能力方面的不足。

🎯 应用场景

该研究成果可应用于评估和改进LLM在逻辑推理、知识表示和问题求解方面的能力。通过使用ASPBench基准测试，可以更好地了解LLM在处理复杂逻辑规则和约束时的局限性，从而指导LLM的架构设计和训练策略，使其更有效地应用于智能规划、决策支持和自动化推理等领域。

📄 摘要（原文）

Answer Set Programming (ASP) is a powerful paradigm for non-monotonic reasoning. Recently, large language models (LLMs) have demonstrated promising capabilities in logical reasoning. Despite this potential, current evaluations of LLM capabilities in ASP are often limited. Existing works normally employ overly simplified ASP programs, do not support negation, disjunction, or multiple answer sets. Furthermore, there is a lack of benchmarks that introduce tasks specifically designed for ASP solving. To bridge this gap, we introduce ASPBench, a comprehensive ASP benchmark, including three ASP specific tasks: ASP entailment, answer set verification, and answer set computation. Our extensive evaluations on ASPBench reveal that while 14 state-of-the-art LLMs, including \emph{deepseek-r1}, \emph{o4-mini}, and \emph{gemini-2.5-flash-thinking}, perform relatively well on the first two simpler tasks, they struggle with answer set computation, which is the core of ASP solving. These findings offer insights into the current limitations of LLMs in ASP solving. This highlights the need for new approaches that integrate symbolic reasoning capabilities more effectively. The code and dataset are available at https://github.com/HomuraT/ASPBench.