mlsanityData to 14 Oct 2026

Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools

arXiv 2404.11891 ↗First posted 18 Apr 2024cs.AI cs.CL cs.HCcited by 47

Not on the map. Why?

Abstract (arXiv)

Large Language Models (LLMs) struggle to directly generate correct plans for complex multi-constraint planning problems, even with self-verification and self-critique. For example, a U.S. domestic travel planning benchmark TravelPlanner was proposed in Xie et al. (2024), where the best LLM OpenAI o1-preview can only find viable travel plans with a 10% success rate given all needed information. In this work, we tackle this by proposing an LLM-based planning framework that formalizes and solves complex multi-constraint planning problems as constrained satisfiability problems, which are further consumed by sound and complete satisfiability solvers. We start with TravelPlanner as the primary use case and show that our framework achieves a success rate of 93.9% and is effective with diverse paraphrased prompts. More importantly, our framework has strong zero-shot generalizability, successfully handling unseen constraints in our newly created unseen international travel dataset and generalizing well to new fundamentally different domains. Moreover, when user input queries are infeasible, our framework can identify the unsatisfiable core, provide failure reasons, and offers personalized modification suggestions. We show that our framework can modify and solve for an average of 81.6% and 91.7% unsatisfiable queries from two datasets and prove with ablations that all key components of our framework are effective and necessary. Project page: https://sites.google.com/view/llm-rwplanning.

Key facts. Cited by 47 papers in the map (data through 14 Oct 2026). Builds on 26 of its 67 references that are in the map. First posted on arXiv 18 Apr 2024.

Builds on

26 of 67 references.

References · 26

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2022Training language models to follow instructions with human feedbackcited by 15,971
  4. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  5. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  6. 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
  7. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,182
  8. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,442
  9. 2023ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIscited by 1,947
  10. 2022Code as Policies: Language Model Programs for Embodied Controlcited by 1,210
  11. 2022Inner Monologue: Embodied Reasoning through Planning with Language Modelscited by 1,081
  12. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,075
14 more
  1. 2022Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agentscited by 1,035
  2. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 886
  3. 2023Reasoning with Language Model is Planning with World Modelcited by 861
  4. 2023Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolutioncited by 551
  5. 2023LLM+P: Empowering Large Language Models with Optimal Planning Proficiencycited by 501
  6. 2024Understanding the planning of LLM agents: A surveycited by 421
  7. 2024TravelPlanner: A Benchmark for Real-World Planning with Language Agentscited by 392
  8. 2023Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedbackcited by 353
  9. 2023PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimizationcited by 233
  10. 2023Large Language Models as Commonsense Knowledge for Large-Scale Task Planningcited by 231
  11. 2023Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planningcited by 207
  12. 2024LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworkscited by 179
  13. 2024EASYTOOL: Enhancing LLM-based Agents with Concise Tool Instructioncited by 154
  14. 2023AutoTAMP: Autoregressive Task and Motion Planning with LLMs as Translators and Checkerscited by 113

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 20; 2026: 23.

47 papers.

Sort:

By area:

  1. 2024ToolACE: Winning the Points of LLM Function Callingcited by 216
  2. 2025Evolving Deeper LLM Thinkingcited by 58
  3. 2024Steering Large Language Models between Code Execution and Textual Reasoningcited by 24
  4. 2025TripCraft: A Benchmark for Spatio-Temporally Fine Grained Travel Planningcited by 21
  5. 2024Trust the PRoC3S: Solving Long-Horizon Robotics Problems with LLMs and Constraint Satisfactioncited by 19
  6. 2024TRIP-PAL: Travel Planning with Guarantees by Combining Large Language Models and Automated Plannerscited by 17
  7. 2025Is Your LLM-Based Multi-Agent a Reliable Real-World Planner? Exploring Fraud Detection in Travel Planningcited by 15
  8. 2025R1-Code-Interpreter: LLMs Reason with Code via Supervised and Multi-stage Reinforcement Learningcited by 15
  9. 2025Teaching LLMs to Plan: Logical Chain-of-Thought Instruction Tuning for Symbolic Planningcited by 15
  10. 2025ConstraintLLM: A Neuro-Symbolic Framework for Industrial-Level Constraint Programmingcited by 10
  11. 2025Verification-Aware Planning for Multi-Agent Systemscited by 10
  12. 2025ToolForge: A Data Synthesis Pipeline for Multi-Hop Search without Real-World APIscited by 10
35 more
  1. 2025TripTide: A Benchmark for Adaptive Travel Planning under Disruptionscited by 8
  2. 2025Self-Guided Function Calling in Large Language Models via Stepwise Experience Recallcited by 7
  3. 2025Planner-R1: Reward Shaping Enables Efficient Agentic RL with Smaller LLMscited by 7
  4. 2025Wide-Horizon Thinking and Simulation-Based Evaluation for Real-World LLM Planning with Multifaceted Constraintscited by 6
  5. 2026GroupTravelBench: Benchmarking LLM Agents on Multi-Person Travel Planningcited by 5
  6. 2026TAPE: Tool-Guided Adaptive Planning and Constrained Execution in Language Model Agentscited by 4
  7. 2026TourPlanner: A Competitive Consensus Framework with Constraint-Gated Reinforcement Learning for Travel Planningcited by 3
  8. 2026WorldTravel: A Realistic Multimodal Travel-Planning Benchmark with Tightly Coupled Constraintscited by 3
  9. 2026VASO: Formally Verifiable Self-Evolving Skills for Physical AI Agentscited by 3
  10. 2026Beyond the Leaderboard: A Synthesis of Tool-Use, Planning, and Reasoning Failures in Large Language Model Agentscited by 3
  11. 2025Urban Computing in the Era of Large Language Modelscited by 2
  12. 2025Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scalingcited by 2
  13. 2025Agent-Testing Agent: A Meta-Agent for Automated Testing and Evaluation of Conversational AI Agentscited by 2
  14. 2025ATA: A Neuro-Symbolic Approach to Implement Autonomous and Trustworthy Agentscited by 2
  15. 2026VeriTrans: Fine-Tuned LLM-Assisted NL-to-PL Translation via a Deterministic Neuro-Symbolic Pipelinecited by 2
  16. 2026TREK: A Travel Reasoning and Evaluation Kit for LLM Agents in Complex Trip Planningcited by 2
  17. 2025TripScore: Aligning LLMs for Real-World Travel Planning via Expert-Calibrated Rewardcited by 1
  18. 2025TriFlow: A Progressive Multi-Agent Framework for Intelligent Trip Planningcited by 1
  19. 2026AWARE-US: Preference-Aware Infeasibility Resolution in Tool-Calling Agentscited by 1
  20. 2026Decoupled Travel Planning with Behavior Forestcited by 1
  21. 2026Priming, Path-dependence, and Plasticity: Understanding the molding of user-LLM interaction and its implications from (many) chat logs in the wildcited by 1
  22. 2026MaxSAT-Based Feedback for Guiding Vision-Language Models in Sudokucited by 1
  23. 2026Replan, Repair, or Edit? A Unified Empirical Evaluation of Travel Agents for Itinerary Revision under Resource Disruptionscited by 1
  24. 2025Formal Reasoning for Intelligent QA Systems: A Case Study in the Educational Domaincited by 0
  25. 2025IMAGINE: Integrating Multi-Agent System into One Model for Complex Reasoning and Planningcited by 0
  26. 2026Heuristic Search as Language-Guided Program Optimizationcited by 0
  27. 2026Nidus: Externalized Reasoning for AI-Assisted Engineeringcited by 0
  28. 2026Revisiting the Travel Planning Capabilities of Large Language Modelscited by 0
  29. 2026Reliable Reasoning with Large Language Models via Preference-Based Maximum Satisfiabilitycited by 0
  30. 2026SafeRun: Enabling Determinism in LLM Planning for Runningcited by 0
  31. 2026Training the Orchestrator: A Supervised Approach to End-to-End PDDL Planning with LLM Agentscited by 0
  32. 2026CARL: Constraint-Aware Reinforcement Learning for Planning with LLMscited by 0
  33. 2026Embark Now: User Demand Oriented Framework for Multi-day Urban Travel Itinerary Planningcited by 0
  34. 2026Behavior2Trip: Towards Personalized Travel Planning via User Behavior Trajectorycited by 0
  35. 2026Grounded Evaluation and Repair for NL-to-PDDL Problem Generationcited by 0