Research map / Large language models / Agents, code and math
SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SayCanPay, which combines LLM action generation (Say), a trained feasibility model (Can), a trained payoff model (Pay), and beam search over actions to produce plans that are both feasible and cost-effective.
Problem
LLM planners often produce infeasible plans (ignoring affordances/preconditions) or cost-inefficient long plans because they greedily pick the next action without considering long-term goal relevance.
Approach
Frames LM planning as heuristic search: the LM's action probability is multiplied by a learned precondition (Can) score and a learned payoff (Pay) heuristic, and a beam search over whole actions (Beam-Action) selects the plan, rather than greedy token-level decoding.
Key results
- On Ravens Tower of Hanoi with Vicuna, Beam-Action SayCanPay reaches 70% planning success vs 45% for Greedy-Token.
- On BabyAI pickup with Vicuna, Beam-Action SayCan/SayCanPay reach 94% success vs 59% for Greedy-Token.
- Cost-effectiveness: SayCanPay improves over Say by roughly 11-97% with Beam-Action, and over SayCan by roughly 0-33%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Pay scoring to SayCan | SayCan planning · test environments | cost-effectiveness: ≈ 0-33 % for Beam-Action and ≈ 1-150 % for Greedy-Action | Helped |
| Add Pay scoring to Say | Say planning · test environments | cost-effectiveness: ≈ 11-97 % for Beam-Action | Helped |
| Use Beam-Action instead of Greedy-Action | SayCanPay · test environments | planning success: ≈~1-40 % | Helped |
| Use Beam-Action instead of Greedy-Action | SayCanPay · test environments | cost-effectiveness: ≈~0-73 % | Helped |
| Use Beam-Action instead of Greedy-Action | SayCanPay · test-generalize environments | generalization success: ≈~0-89 % | Helped |
| Use a Perfect Say model instead of Vicuna (ablation) | Greedy-Action SayCanPay · Ravens Tower of Hanoi | planning success: 50 -> 92 | Helped |
| Use a Perfect Say model instead of Vicuna (ablation) | Greedy-Action SayCan · Ravens Tower of Hanoi | planning success: 48 -> 88 | Helped |
| Use a Perfect Say model instead of Vicuna (ablation) | Greedy-Action SayCanPay · Ravens Put Blocks in Bowls | planning success: 54 -> 75 | Helped |
| Use a Perfect Say model instead of Vicuna (ablation) | Greedy-Action SayCan · Ravens Put Blocks in Bowls | planning success: 52 -> 70 | Helped |
| Use a Perfect Say model instead of Vicuna (ablation) | Greedy-Action SayCanPay · BabyAI Pickup | planning success: 88 -> 92 | Helped |
| Use a Perfect Say model instead of Vicuna (ablation) | Greedy-Action SayCan · BabyAI Pickup | planning success: 81 -> 90 | Helped |
| Use a Perfect Say model instead of Vicuna (ablation) | Greedy-Action SayCanPay · VirtualHome | planning success: 52 -> 64 | Helped |
Surprising findings
- Generalization to out-of-distribution test splits dropped noticeably for Ravens, suggesting the learned Can/Pay models do not generalize well.
- Flan-T5 and Vicuna showed no consistent advantage of one architecture over the other.
Limitations
- Requires expert trajectories from an oracle planner to train Can and Pay models.
- Can and Pay models generalize poorly to out-of-distribution data (e.g., Ravens).
- Say model failures limit performance; a perfect Say model shows substantial headroom.
Experimental setup
Datasets: Ravens (Tower of Hanoi, Put Blocks in Bowls) BabyAI (Pickup) VirtualHome-Env
Benchmarks: Ravens Tower of Hanoi Ravens Put Blocks in Bowls BabyAI Pickup VirtualHome
Metrics: planning success (# plans out of 100 reaching goal) cost-effectiveness (success with expert plan length) generalization success on test-generalize split relative plan length
Baselines: Greedy-Token Greedy-Action Say Greedy-Action SayCan Beam-Action Say Beam-Action SayCan
Builds on: SayCan Planning LM (Huang et al. 2022 style LM planning) Tree-of-Thoughts approximate planning (POMDP) BERT
Closest papers by meaning
- Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code (NeurIPS 2025 · similarity 0.91)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.90)
- Large Language Models as Planning Domain Generators (Student Abstract) (AAAI 2024 · similarity 0.89)
- Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks (ICML 2025 · similarity 0.89)
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.89)
- Leveraging Environment Interaction for Automated PDDL Translation and Planning with Large Language Models (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.