Research map / Large language models / Agents, code and math
LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language
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.
Introduces LexiCon, an extensible natural-language benchmark generator that adds automatically constructed temporal (PDDL3.0) state-trajectory constraints to classical planning domains and verifies LLM plans for optimality.
Problem
LLMs have mostly been evaluated on unconstrained planning, but real deployments require adherence to (safety) constraints on state trajectories; existing constrained NL planning benchmarks are hand-curated, hard to extend, and costly to verify.
Approach
Automatically generate task-aware temporal constraints (Always, Sometime, AtMostOnce, SometimeBefore/After) on top of unconstrained PDDL problems using an optimal plan, guaranteeing feasibility and increased optimal cost, translate them to natural language, and verify LLM plans via compilation (TCORE) and a plan validator.
Key results
- o3 on Blocksworld optimal-plan accuracy drops from 76% (1 constraint) to 0% (10 constraints).
- Reasoning models' thinking-token count correlates with optimal plan cost (Pearson 0.48 to 0.87 across domains).
- LexiCon's generation and verification is roughly one order of magnitude faster than LLM-based planning.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of temporal constraints | LLMs evaluated on LexiCon · Constrained planning across five environments | optimal-plan rate | Hurt |
| Increase constraints from 1 to 10 | OpenAI o3 · Blocksworld | optimal-plan accuracy: 76%, 30%, 26%, 10%, 0 | Hurt |
| Use GPT-4.1 with Chain-of-Thought prompting instead of non-reasoning model alternatives | Constrained planning with one constraint · Across Blocksworld, BabyAI, Logistics, Sokoban, and AlfWorld | optimal-plan rate | Mixed |
| Increase optimal plan length | Reasoning models · LexiCon planning tasks | thinking tokens | Helped |
Surprising findings
- Non-reasoning LLMs failed to produce optimal plans for any problem with more than one constraint.
- R1 often deviates from the requested action format, and Claude 3.7 Sonnet with thinking too, requiring edit-distance mapping of actions.
Limitations
- Simulator lacks parallel episode execution and is slow to generate episodes (1-100 s).
- Only fully observable, state-trajectory constraints; no action or continuous-state constraints or partial observability.
- Evaluation uses a single run per setting with temperature 0.2 or 1 and no error bars.
Experimental setup
Datasets: BabyAI Blocksworld Logistics Sokoban AlfWorld
Benchmarks: LexiCon (BabyAI, Blocksworld, Logistics, Sokoban, AlfWorld constrained problems)
Metrics: optimal plan rate valid plan rate average optimal cost pearson correlation of reasoning tokens with optimal cost execution time
Baselines: GPT-4.1 (chain-of-thought) DeepSeek V3 Claude 3.7 Sonnet (no thinking) Gemini 2.0 Pro
Builds on: PDDL3.0 TCORE compiler SymK planner Chain-of-thought prompting
Closest papers by meaning
- TravelPlanner: A Benchmark for Real-World Planning with Language Agents (ICML 2024 · similarity 0.90)
- LLMs Can Plan Only If We Tell Them (ICLR 2025 · similarity 0.89)
- Large Language Models as Planning Domain Generators (Student Abstract) (AAAI 2024 · similarity 0.89)
- Planning in the Dark: LLM-Symbolic Planning Pipeline Without Experts (AAAI 2025 · similarity 0.89)
- Leveraging Environment Interaction for Automated PDDL Translation and Planning with Large Language Models (NeurIPS 2024 · similarity 0.89)
- PlanU: Large Language Model Reasoning through Planning under Uncertainty (NeurIPS 2025 · similarity 0.88)
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.