💬 NLP

PDDL-Mind: Large Language Models are Capable on Belief Reasoning with Reliable State Tracking

The paper introduces PDDL-Mind, a neuro-symbolic framework that enhances Large Language Models' Theory of Mind reasoning by decoupling belief inference from environment state tracking through explicit Planning Domain Definition Language (PDDL) representations, thereby achieving significant accuracy improvements over existing state-of-the-art methods.

Original authors: Wang Bill Zhu, Qiutong Tony Yi, Robin Jia, Jesse Thomason

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wang Bill Zhu, Qiutong Tony Yi, Robin Jia, Jesse Thomason

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: LLMs Are Great Storytellers, But Terrible Note-Takers

Imagine you are watching a complex magic trick or a chaotic sitcom episode. You have a brilliant friend (a Large Language Model, or LLM) who is amazing at explaining why the magician did something or why the character is angry. They understand human psychology perfectly.

But here's the catch: Your friend has terrible short-term memory. As the story gets longer, they start forgetting who is holding the key, which room the cat is in, or who heard the secret conversation. Because they lose track of the basic facts, their brilliant psychological reasoning falls apart. They guess the wrong answer not because they are "stupid," but because they are working with the wrong facts.

The authors of this paper argue that this is exactly what is happening with AI on "Theory of Mind" (ToM) tests. ToM is the ability to understand what others are thinking, knowing, or believing. Current AI fails these tests not because it can't reason, but because it can't reliably keep a mental "scorecard" of the story's events.

The Solution: PDDL-MIND (The "Scriptwriter" Approach)

The team created a new system called PDDL-MIND. Instead of asking the AI to just "read and guess," they force the AI to act like a scriptwriter for a video game.

Here is how it works, using a simple analogy:

1. The Blueprint (The PDDL Domain)

Imagine you are building a house. You don't just tell the builder, "Put up a wall." You give them a strict blueprint with rules: Walls must be 10 feet high; doors must be 3 feet wide.
In the paper, this is the PDDL Domain. It's a pre-written rulebook that defines:

What objects exist (chairs, keys, people).
What actions are possible (move, open, grab, talk).
The strict rules of physics (if you open a box, you can see what's inside; if you close it, you can't).

2. The Translation (Parsing the Story)

The AI reads the messy, natural language story (e.g., "Mary walked into the kitchen and peeked inside the fridge").
Instead of just "reading" it, the AI translates this story into a strict, logical code based on the blueprint.

Story: "Mary walked to the kitchen."
Code: MOVE(Mary, Kitchen)
Story: "Mary opened the fridge."
Code: OPEN(Mary, Fridge)

3. The Fact-Checker (Verification)

This is the secret sauce. Before the AI tries to answer a question, a "Fact-Checker" (a computer program) runs the code.

It asks: "Did Mary actually have the key to the fridge?"
If the story didn't say she had the key, the Fact-Checker says: "ERROR. This action is impossible."
It throws out the mistake and fixes the "state" of the world.

Now, the AI has a perfect, verified timeline of exactly what happened, who saw what, and who knows what.

4. The Final Answer

Finally, the AI looks at this perfect timeline and answers the question: "Does Mary think the cookies are in the jar?"
Because the AI isn't guessing the facts anymore, it can use its natural intelligence to give the correct answer.

Why This Matters: The "Puzzle vs. Math" Analogy

Think of solving a Theory of Mind problem like solving a Jigsaw Puzzle.

Old AI Approach: The AI tries to solve the puzzle by looking at the picture on the box and guessing where the pieces go. It's good at guessing the picture, but it keeps dropping pieces or putting them in the wrong spot.
PDDL-MIND Approach: The AI first sorts every single piece into the correct pile (State Tracking). Once the pieces are sorted perfectly, it easily sees the picture (Reasoning).

The paper proves that sorting the pieces is the hard part, not seeing the picture. Once you fix the sorting (state tracking), the AI suddenly becomes a genius at the puzzle.

The Results: A Massive Win

The researchers tested this on three difficult tests (MMToM-QA, MuMa-ToM, and FanToM).

The Result: PDDL-MIND got 88%+ accuracy, beating the previous best AI by a huge margin (over 5%).
The Efficiency: It did this using fewer computer "calls" than other methods. While other AIs were frantically re-reading the story 27 times to try to remember, PDDL-MIND just read it once, wrote down the facts, and solved it.

The Takeaway

The paper concludes that AI isn't "bad" at understanding human minds. It's just bad at keeping a notebook.

By forcing the AI to translate stories into a strict, logical language (PDDL) and checking that language against the rules, we unlock its true potential. It's like giving a brilliant but forgetful detective a reliable assistant to take notes. Suddenly, the detective can solve the case.

In short: Don't blame the AI's brain; fix its memory. Once the memory is reliable, the reasoning follows.

1. Problem Statement

Large Language Models (LLMs) currently perform significantly below human levels on Theory-of-Mind (ToM) benchmarks, which require inferring agents' beliefs, knowledge, and intentions based on narrative descriptions.

The Debate: There is no consensus on the root cause of these failures. Two competing hypotheses exist:
1. Reasoning Limitation: Models fail at high-level inference (deducing beliefs from states).
2. State Tracking Limitation: Models fail to maintain accurate, consistent representations of the world state as events accumulate.
The Gap: Existing methods often treat narratives as unstructured text or rely on implicit, heuristic state tracking, leading to hallucinations and inconsistencies. The authors argue that the primary bottleneck is unreliable implicit state tracking, not a lack of reasoning capability.

2. Methodology: PDDL-MIND

The authors propose PDDL-MIND, a neuro-symbolic framework that decouples environment state evolution from belief inference. It leverages the Planning Domain Definition Language (PDDL) to provide explicit, logically consistent state representations.

Core Workflow

Predefined Domain Definition:
- A fixed PDDL domain file is established containing 7 general action types (move, open, close, grab, drop, ask, tell).
- It defines four object types: agent, loc (location), obj (object), and utterance.
- Crucial predicates include seen (tracking visual observation) and heard (tracking auditory information), alongside standard state predicates like at and in.
State and Action Extraction (LLM-Parsed):
- Initialization: An LLM parses the narrative's initial environment description into a PDDL Problem File, defining the initial state ( $s_0$ ) and objects.
- Action Sequence Generation: The LLM translates the narrative events into a sequence of candidate PDDL actions.
- Verification & Filtering: This is the core innovation. The system validates each candidate action against the predefined domain:
  - It checks if the current state satisfies the action's preconditions.
  - If valid, it executes the action to generate the next state ( $s_i$ ) using the action's effects.
  - If invalid (e.g., an agent trying to open a container they cannot reach), the action is discarded.
- This process yields a verified sequence of world states that are logically consistent with the narrative.
ToM Inference:
- The LLM is provided with the verified state sequence and the ToM question.
- The model performs Chain-of-Thought (CoT) reasoning based only on these explicit, verified states to infer beliefs or intentions.

3. Key Contributions

Disentanglement of Tracking and Reasoning: The paper provides empirical evidence that LLMs possess strong ToM reasoning capabilities but are hindered by unreliable state tracking. By externalizing state tracking to a symbolic verifier, reasoning performance improves drastically.
Neuro-Symbolic Framework: PDDL-MIND bridges natural language and symbolic logic, using LLMs for parsing and symbolic solvers for verification.
Unified Event-State Abstraction: The authors propose a structural abstraction where both physical actions and conversational updates are treated as events with preconditions and effects, unifying single-agent and multi-agent scenarios under a single PDDL formulation.
Cost Efficiency: The method requires only 3 LLM calls per example (Parse, Verify/Extract, Reason), whereas previous state-of-the-art methods (like AutoToM) require an average of 17–35 calls.

4. Experimental Results

The framework was evaluated on three major ToM benchmarks: MMToM-QA, MuMa-ToM, and FanToM.

Performance Gains:
- MMToM-QA: PDDL-MIND (GPT-4o) achieved 88.3% accuracy, outperforming the previous SOTA (AutoToM at 83.0%) by 5.3%.
- MuMa-ToM: Achieved 88.8% accuracy, surpassing AutoToM (81.4%) by 7.4%.
- FanToM: Achieved 80.0% accuracy.
State Tracking Quality: Manual inspection of 40 verified sequences (20 per benchmark) revealed a 90% correctness rate, confirming that the symbolic verification effectively filters out hallucinations.
Error Analysis:
- Remaining errors (~12%) were split between parsing errors (33% of failures, where the LLM misidentified the action) and reasoning failures (67% of failures, where the LLM failed to infer correctly even with perfect states).
- This suggests that with perfect state tracking, the theoretical error rate could drop to ~8%, reinforcing the hypothesis that state tracking is the dominant bottleneck.
Efficiency: PDDL-MIND is significantly more cost-effective, requiring ~10x fewer LLM calls than iterative methods like AutoToM.

5. Significance and Implications

Redefining ToM Benchmarks: The paper argues that current benchmarks often conflate state tracking with reasoning. Future benchmarks should treat accurate, verifiable state tracking as a prerequisite for meaningful ToM assessment.
Architectural Insight: The results challenge the "reasoning deficit" narrative for LLMs. Instead, they suggest that LLMs are capable of complex reasoning if the "noise" of state maintenance is offloaded to a reliable, explicit mechanism.
Future Directions:
- Benchmark Design: Future benchmarks should introduce structural biases (e.g., varying the algorithm associated with a verb across contexts) to prevent models from relying solely on symbolic state tracking without true semantic understanding.
- World Knowledge: While PDDL-MIND excels at closed-world symbolic tasks, it highlights the need for benchmarks that require integrating long-tail world knowledge (e.g., cultural norms, biological facts) that cannot be fully enumerated in a PDDL domain file.
Limitations: The current approach is text-only and relies on a predefined domain, making it brittle for models that struggle with parsing or for scenarios requiring multimodal (visual/spatial) perception.

In conclusion, PDDL-MIND demonstrates that equipping LLMs with a reliable, explicit state-tracking mechanism via PDDL unlocks their latent Theory-of-Mind reasoning capabilities, achieving state-of-the-art performance with significantly reduced computational cost.