mlsanityData to 14 Oct 2026

Robust Asynchronous Planning via Auto-Formalization

arXiv 2606.00981 ↗First posted 31 May 2026cs.CLcited by 0

Not on the map. Why?

Abstract (arXiv)

LLMs can plan by generating schedules directly as a Planner, or by translating a task into a formal specification for a solver as a Formalizer. Most real-world tasks are asynchronous, with non-uniform durations, concurrency, and execution-time changes, yet existing benchmarks hardly cover them. We unify asynchronous planning under one formulation and release three benchmarks spanning task-graph scale, grounded state and resource constraints, and execution-time events. Surprisingly, PDDL2.1, the formalism built for temporal planning, is the weakest pipeline. On AsyncPlan-XXL it averages 30.8% plan accuracy, against 81.7% for the Planner and 94.0% for a CP-SAT Formalizer. The gap widens with scale, and at 100 actions the three pipelines reach 9.0%, 44.5%, and 82.5%, respectively. The formalism is not to blame. Compiled from the same model-extracted intermediate representation, PDDL2.1 and CP-SAT reach nearly identical accuracy (81.6% vs. 81.5%), and gold task graphs reach 100% for both. What remains is a bottleneck shared by every pipeline: recovering the task graph from language. Execution-time events further degrade every pipeline, yet updating only event-induced constraints reaches 81.6% versus 41.6% for full regeneration. Robust asynchronous planning thus hinges not on the expressiveness of the target formalism but on how reliably a model can write and edit it, and a well-chosen interface can let a weaker model match a stronger one.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 29 of its 53 references that are in the map. First posted on arXiv 31 May 2026.

Builds on

29 of 53 references.

References · 29

  1. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  2. 2023LLM+P: Empowering Large Language Models with Optimal Planning Proficiencycited by 501
  3. 2018VirtualHome: Simulating Household Activities via Programscited by 415
  4. 2022PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Changecited by 382
  5. 2025The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexitycited by 302
  6. 2023Can Language Models Solve Graph Problems in Natural Language?cited by 252
  7. 2023Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planningcited by 207
  8. 2018WikiHow: A Large Scale Text Summarization Datasetcited by 204
  9. 2023AdaPlanner: Adaptive Planning from Feedback with Language Modelscited by 196
  10. 2023Generalized Planning in PDDL Domains with Pretrained Large Language Modelscited by 139
  11. 2024Lean Workbook: A large-scale Lean problem set formalized from natural language math problemscited by 122
  12. 2024Chain of Thoughtlessness? An Analysis of CoT in Planningcited by 103
17 more
  1. 2024LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBenchcited by 94
  2. 2025PlanGenLLMs: A Modern Survey of LLM Planning Capabilitiescited by 83
  3. 2023Plug in the Safety Chip: Enforcing Constraints for LLM-driven Robot Agentscited by 69
  4. 2020Reasoning about Goals, Steps, and Temporal Ordering with WikiHowcited by 66
  5. 2025LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Modelscited by 38
  6. 2024Graph-enhanced Large Language Models in Asynchronous Plan Reasoningcited by 37
  7. 2023Learning adaptive planning representations with natural language guidancecited by 36
  8. 2024Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programmingcited by 35
  9. 2024Planetarium: A Rigorous Benchmark for Translating Text to Structured Planning Languagescited by 33
  10. 2020Flatland-RL : Multi-Agent Reinforcement Learning on Trainscited by 32
  11. 2025Robotouille: An Asynchronous Planning Benchmark for LLM Agentscited by 32
  12. 2025Text2World: Benchmarking Large Language Models for Symbolic World Model Generationcited by 26
  13. 2024On the Limit of Language Models as Planning Formalizerscited by 18
  14. 2025Plan-over-Graph: Towards Parallelable LLM Agent Schedulecited by 14
  15. 2024CaStL: Constraints as Specifications through LLM Translation for Long-Horizon Task and Motion Planningcited by 10
  16. 2025Executable Counterfactuals: Improving LLMs' Causal Reasoning Through Codecited by 10
  17. 2025Language Model as Planner and Formalizer under Constraintscited by 3

Built on by

Not cited yet.