A Category-Theoretic Approach to Neural-Symbolic Task Planning with Bidirectional Search

Shuhui Qu, Jie Wang, Kincho H. Law2025 · DOI

This paper, recently accepted for EMNLP 2025, presents a sophisticated "best of both worlds" approach to task planning. By combining the creative generative power of Large Language Models (LLMs) with the rigorous mathematical framework of Category Theory, the authors have created a planner that is both flexible and formally guaranteed to follow rules.

TL;DR

The authors introduce a neural-symbolic framework that uses LLMs to decompose tasks and Category Theory to verify them. By treating planning states as mathematical objects and actions as "morphisms," they use "pullbacks" to ensure plans never violate resource or timing constraints, achieving state-of-the-art results with significantly higher efficiency.

What Problem Does This Paper Address?

Task planning—the process of determining a sequence of actions to achieve a goal—is a cornerstone of AI. Historically, we’ve had two choices:

  1. Classical Symbolic Planners: These are mathematically "correct" but incredibly brittle. They require experts to manually write complex logic (PDDL) for every new domain.
  2. LLM-based Planners: These are flexible and understand natural language, but they are "black boxes." They frequently hallucinate, ignore resource limits (e.g., using more butter than available), or violate temporal logic (e.g., trying to bake a cake before mixing the batter).

The challenge is creating a system that retains the LLM's ability to understand the world while enforcing the strict, provable constraints required for real-world applications like robotics or logistics.

Methods

The authors propose a three-stage pipeline:

  1. LLM-Driven Operator Decomposition: An LLM takes a natural language query and breaks it down into structured categorical specifications (resources, operators, and constraints).
  2. Category-Theoretic Verification: This is the core innovation. The planning domain is modeled as a Category.
  3. States are Objects: A state $w$ encapsulates resources, symbolic progress, and time.
  4. Operations are Morphisms: An action is a mapping ($f: w_1 \to w_2$) that must preserve categorical constraints.
  5. Pullbacks for Composition: To ensure two plan fragments can be joined safely, the system uses a mathematical construct called a pullback. If a pullback exists, it proves that the combined plan respects all resource, temporal, and logical boundaries.
  6. Bidirectional Search: Instead of searching only from the start to the goal, the algorithm searches from both ends simultaneously. This is guided by a learned Planning Distance Function that helps the agent "sniff out" the most promising paths, reducing search complexity from $O(b^L)$ to $O(b^{L/2})$.

Datasets

The framework was evaluated on three distinct domains:

  • PlanBench: A standardized Blocksworld benchmark for testing logical dependencies.
  • RecipeNLG: A cooking dataset. The authors augmented this with explicit resource limits (e.g., "max 0.5 cups of sugar") and temporal intervals to test "health-conscious" and time-sensitive planning.
  • Proc2PDDL: A dataset of procedural texts (like manuals) used to test the ability to translate text into formal planning files.

Key Insights and Ideas

  • The "Safety Layer": Category theory acts as a formal safety filter. The LLM proposes actions, but the math disposes. If the LLM suggests an action that violates a resource limit, the categorical framework identifies that no valid morphism exists and prunes that path immediately.
  • Compositionality is Key: Category theory is the "mathematics of composition." By using it, the authors ensure that if step A is valid and step B is valid, their combination is also guaranteed to be valid—a property LLMs struggle with on their own.
  • Efficiency through Geometry: By embedding states into a space where distance represents "plan difficulty," the bidirectional search can find meeting points in the middle of the state space much faster than traditional forward-only search.

Key Results

The proposed method, "Ours," consistently outperformed baselines like LLM+P and LLM-MCTS:

  • Zero Violations: In the RecipeNLG domain, the framework achieved 0% resource violations, whereas even the strongest baselines (LLM+P) still had a 3.4% violation rate.
  • Higher Accuracy: On PlanBench, the method reached a 96.6% completion rate, a 6.6% improvement over the previous state-of-the-art.
  • Action Accuracy: In Proc2PDDL, it improved action-wise accuracy by 9.1%, showing it is better at predicting the specific preconditions and effects of tasks.
  • Scaling: The framework allowed smaller models (like LLaMA-3-13B) to perform nearly as well as much larger models (GPT-4o) by compensating for weaker reasoning with stricter mathematical verification.

Limitations and Future Work

While powerful, the authors note a few hurdles:

  • Temporal Complexity: While the system handles intervals well, extremely complex, overlapping temporal dependencies still pose a challenge.
  • State Space Overhead: In domains with an astronomical number of possible states, the computational cost of maintaining the search graphs can become significant.
  • Domain Knowledge Dependency: The system still relies on the LLM having some baseline understanding of the domain. If the LLM's initial decomposition is completely nonsensical, the categorical verification has nothing to work with.

Future research may focus on automating the "categorical encoding" even further to handle entirely unseen domains without any manual prompt engineering.

Summary updated

Abstract

We introduce a Neural-Symbolic Task Planning framework integrating Large Language Model (LLM) decomposition with categorytheoretic verification for resource-aware, temporally consistent planning.Our approach represents states as objects and valid operations as morphisms in a categorical framework, ensuring constraint satisfaction through mathematical pullbacks.We employ bidirectional search that simultaneously expands from initial and goal states, guided by a learned planning distance function that efficiently prunes infeasible paths.Empirical evaluations across three planning domains demonstrate that our method improves completion rates by up to 6.6% and action accuracy by 9.1%, while eliminating resource violations compared to the existing baselines.These results highlight the synergy between LLM-based operator generation and category-theoretic verification for reliable planning in domains requiring both resourceawareness and temporal consistency.
BibTeX
@misc{qu2025category,
  author = {Shuhui Qu and Jie Wang and Kincho H. Law},
  title = {{A Category-Theoretic Approach to Neural-Symbolic Task Planning with Bidirectional Search}},
  year = {2025},
  doi = {10.18653/v1/2025.findings-emnlp.1157},
}
Figure