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.