TLDR: A new benchmark called ASPBench evaluates Large Language Models (LLMs) on Answer Set Programming (ASP) tasks. It finds that while LLMs perform moderately on simpler tasks like entailment and verification, they significantly struggle with complex answer set computation, especially for real-world problems and programs with intricate logical structures. The study highlights LLMs’ limitations in robust logical reasoning for non-monotonic problems and suggests a need for hybrid approaches.
Answer Set Programming (ASP) is a powerful method for solving complex problems, especially those involving situations where conclusions might change as new information becomes available. Think of it as a way to model scenarios where you need to make decisions based on incomplete or evolving knowledge, like planning or diagnostics. Recently, large language models (LLMs) have shown impressive abilities in various logical reasoning tasks, leading researchers to wonder if they could also tackle ASP problems.
However, existing evaluations of LLMs in ASP have often been too simplistic. They typically use very basic ASP programs, don’t handle common features like negation or multiple possible solutions, and lack tasks specifically designed to test true ASP solving capabilities. To address this gap, researchers introduced ASPBench, a new and comprehensive benchmark.
ASPBench is designed to rigorously test how well LLMs can solve ASP problems. It includes three distinct tasks:
ASP Entailment (ASE)
This task asks LLMs to determine if a specific statement is true, false, or unknown given an ASP program that has only one unique solution. It’s like asking, “Is this particular fact derivable from the rules?”
Answer Set Verification (ASV)
Here, LLMs are given an ASP program and a candidate solution (a set of facts). Their job is to verify if this candidate set is indeed a correct and valid solution (an “answer set”) for the program. This task often involves programs that can have multiple possible solutions.
Also Read:
- Navigating the Maze: How Language Models Handle Spatial Challenges
- Unmasking LLM Agent Hallucinations: A New Benchmark for Interactive Environments
Answer Set Computation (ASC)
This is the most challenging task. LLMs are given an ASP program and must compute and return one of its correct answer sets. This requires the model to generate a complete and coherent solution from scratch.
The researchers conducted extensive evaluations on ASPBench using 14 state-of-the-art LLMs, including models like deepseek-r1, o4-mini, and gemini-2.5-flash-thinking. The findings revealed significant insights into the current limitations of LLMs in ASP solving.
Overall, LLMs performed relatively well on the simpler tasks of ASP Entailment and Answer Set Verification. However, they struggled significantly with Answer Set Computation, which is considered the core of ASP solving. For instance, the average success rate for ASC on synthetic data was only 23.2%, dropping further to a mere 8.6% on real-world ASP programs. This highlights the difficulty LLMs face in generating complete and precise multi-step logical reasoning.
Interestingly, LLMs specifically optimized for reasoning tasks showed notable improvements compared to general-purpose LLMs, but even these advanced models still have a considerable gap before they can be reliably used for practical ASP applications. The study also found that LLMs generally performed better when given textual descriptions of the problems for classification tasks (ASE and ASV), while symbolic inputs were slightly better for the computation task (ASC).
The way predicates (the building blocks of ASP statements) were named also influenced performance. LLMs reasoned more effectively with predicates that had some semantic meaning (like “flying” or “bird”) rather than simple identifiers like “P1” or “P2”. This suggests that providing some context, even if random, helps LLMs anchor their reasoning.
A significant performance drop was observed when LLMs tackled real-world ASP problems compared to synthetic ones. Real-world problems, despite sometimes having fewer rules, possess more complex logical structures, including constraints and iterative rules. This indicates that current LLMs are largely unable to solve highly complex ASP problems encountered in practical scenarios.
A fine-grained analysis revealed further limitations. In ASP Entailment, LLMs often preferred to output “unknown” rather than risking a wrong “true” or “false” answer, indicating a risk-averse bias. For Answer Set Verification, they struggled with judging the overall completeness of a candidate solution, even if local parts seemed consistent. In Answer Set Computation, their performance was sensitive to the number of possible solutions, dropping sharply when programs had three or more answer sets.
The study also explored the impact of “thinking time” and model size. Longer reasoning chains (more “completion tokens”) generally led to higher performance, suggesting that giving models more time to process and generate thoughts can be beneficial. Larger models, while performing better, were also more “token-efficient,” meaning they achieved better results without necessarily generating much longer outputs.
Finally, the syntactic structure of the ASP programs played a crucial role. LLMs performed significantly better on simpler programs (e.g., “Positive,” “Stratified,” or “Head-Cycle-Free” programs) and struggled dramatically when these structural constraints were violated. This points to a fundamental weakness in LLMs’ ability to handle complex iterative and fixed-point reasoning, which is essential for many ASP problems.
In conclusion, while large language models show some promise in basic Answer Set Programming tasks, they currently lack the robust logical reasoning capabilities needed for complex practical applications. The findings from ASPBench highlight the need for new approaches, possibly integrating symbolic logic with neural networks, to enhance LLMs’ ASP solving abilities. You can find more details and the dataset at the project’s GitHub repository.
