LLM+AL: Bridging Large Language Models and Action Languages for Complex Reasoning About Actions

Adam Ishay, Joohyung LeeAAAI 2025 · DOI

Abstract

While Large Language Models (LLMs) demonstrate remarkable linguistic capabilities, they frequently falter on complex planning tasks requiring systematic logic and search. This paper introduces LLM+AL, a novel pipeline that leverages LLMs to translate natural language problem descriptions into formal Action Languages ($BC+$). By offloading logical reasoning to a dedicated symbolic reasoner, the system achieves superior performance on intricate planning puzzles and demonstrates high "elaboration tolerance" where standalone models fail.

Introduction

State-of-the-art LLMs like GPT-4 and Claude 3 are proficient at many tasks but struggle with "complex reasoning about actions"—specifically problems involving systematic search or intricate constraints. Two primary hurdles exist:

  1. Memorization vs. Reasoning: LLMs often "solve" classic puzzles by reciting memorized solutions. When variations are introduced (elaboration tolerance), performance collapses.
  2. Language Limitations: Symbolic bridges like PDDL often fail to capture "knowledge-intensive" indirect effects or default behaviors.

LLM+AL addresses these by treating the LLM as a semantic parser and the Action Language ($BC+$) as the logical backbone.

Methodology: The LLM+AL Pipeline

The LLM+AL pipeline consists of four distinct stages designed to bridge the gap between natural language and symbolic logic:

  • Signature Generation: The LLM defines the problem's vocabulary, including objects, types, and constants.
  • Knowledge Generation: The model extracts domain-specific rules and commonsense knowledge (e.g., "moving a vessel changes its location").
  • Rule & Query Generation: Structured knowledge is translated into formal $BC+$ causal laws.
  • Self-Revision: A closed-loop system where the generated code is validated by a $BC+$ reasoner (CPLUS2ASP). Syntax errors or logical inconsistencies are fed back to the LLM for correction.
The LLM+AL pipeline architecture, showing the transition from natural language problem descriptions to formal BC+ rules and the self-revision loop.

Unlike procedural approaches (e.g., generating Python code), LLM+AL is declarative. The LLM describes the rules of the world, while the symbolic reasoner handles the search algorithm automatically.

Evaluation and Results

The researchers evaluated LLM+AL using two primary benchmarks: McCarthy’s MCP Elaborations (17 variations of the Missionaries and Cannibals Puzzle) and various standard puzzles like the Tower of Hanoi and Sudoku.

Superior Accuracy and Elaboration Tolerance

Standalone models like GPT-4, Claude 3 Opus, and Gemini Ultra failed to solve any of the complex MCP variations. Even the reasoning-focused o1-preview solved only 7 out of 17. In contrast, LLM+AL demonstrated significantly higher success rates.

Performance comparison on Missionaries and Cannibals (MCP) elaborations. LLM+AL significantly outperforms standalone models like GPT-4 and o1-preview.

Key Findings

  • Identifying Unsolvability: Standalone LLMs often hallucinate plans for unsolvable problems. LLM+AL uses formal logic to definitively prove when no solution exists.
  • Self-Correction Efficiency: The automated "Self-Revision" step increased the percentage of executable programs from 22.3% to 86.7%.
  • Human-in-the-Loop: For the most complex tasks, LLM+AL reached correct answers with an average of only 3.1 manual corrections, whereas standalone models often failed to improve even after 50 rounds of feedback.

Conclusion

LLM+AL demonstrates that the path to robust AI reasoning lies in combining the linguistic flexibility of LLMs with the rigorous logic of symbolic systems. While the system currently requires occasional human intervention for highly complex elaborations, future work on fine-tuning LLMs for Action Language syntax and expanding to probabilistic reasoning promises to further automate and broaden its applicability in robotics and automated planning.

Summary updated

BibTeX
@inproceedings{ishay2025llm,
  author = {Adam Ishay and Joohyung Lee},
  title = {{LLM+AL: Bridging Large Language Models and Action Languages for Complex Reasoning About Actions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i23.34597},
}
Figure