NATURAL PLAN: Benchmarking LLMs on Natural Language Planning

Recent advances in large language models (LLMs) such as GPT-4 and Gemini have demonstrated impressive capabilities in natural language understanding and reasoning. However, their application in complex planning tasks—requiring multi-step reasoning, constraint satisfaction, and tool use—remains limited. Traditional planning approaches rely on formal languages like PDDL and specialized algorithms, which are not directly applicable to natural language scenarios. Prior efforts to evaluate LLMs' planning abilities often used synthetic datasets or template-based prompts, lacking realism. With the advent of API and tool integration, researchers aim to bridge the gap between language understanding and real-world task execution. Yet, a comprehensive benchmark that tests models on realistic, multi-faceted planning tasks grounded in actual data is still lacking, hindering systematic progress.

Despite progress, current LLMs struggle with multi-constraint, multi-step planning in natural language, especially when tasks involve numerous entities, locations, or time constraints. Existing benchmarks do not reflect real-world complexity, limiting their utility. The core challenge lies in models' inability to effectively leverage contextual information, incorporate tool outputs, and generalize across scenarios. This results in low success rates and poor robustness, impeding deployment in practical applications such as travel planning, scheduling, and logistics. Developing a benchmark that captures these complexities is crucial to evaluate and improve models' reasoning and tool-use capabilities.

The primary innovation is the creation of NATURAL PLAN, a benchmark that combines natural language instructions with real API outputs, simulating real-world planning scenarios. It includes three tasks—Trip Planning, Meeting Scheduling, and Calendar Management—each constructed with real constraints and tool data. The benchmark emphasizes multi-task evaluation, long-context learning, and ablation studies on self-correction and generalization. This approach enables assessment of models’ reasoning, tool integration, and scalability in realistic environments. The use of real API data distinguishes it from prior synthetic datasets, making it more applicable to practical AI deployment. Additionally, the benchmark explores the potential of extensive context windows, up to 355K tokens, to enhance planning performance.

• �� Data Construction: Generate tasks by sampling real cities, people, and constraints; query Google APIs for connectivity, schedules, and travel info. • Prompt Design: Use 5-shot examples within each task, embedding API outputs as context. • Model Evaluation: Parse model outputs, compare with gold plans, compute exact match scores. • Complexity Analysis: Vary number of cities, people, days to assess performance degradation. • Ablation Studies: Test effects of self-correction, long-context, and few-shot generalization. • Long-Context Experiments: Increase context size up to 355K tokens, evaluate performance gains. • Performance Metrics: Success rate, accuracy, and robustness across scenarios.

The experiments involve testing GPT-4, GPT-3.5, GPT-4o, and Gemini 1.5 models on the constructed benchmark. Few-shot prompts are used, with variations in task complexity by adjusting the number of cities, attendees, and days. The models are also evaluated with extended context sizes, up to 800 shots, to analyze long-context benefits. Ablation experiments assess the impact of self-correction and generalization strategies. Results are statistically analyzed to compare success rates across different scenarios, emphasizing the performance drop with increased complexity and the potential of long-context modeling to mitigate these issues.

Models exhibit significant performance drops as task complexity increases: success rates fall below 5% with 10 cities in Trip Planning. Gemini 1.5 Pro outperforms others in long-context settings, reaching over 40% success with 355K tokens. Self-correction strategies generally degrade performance, especially for stronger models like GPT-4. The results highlight that current models are far from human-level planning, particularly in multi-constraint, multi-step scenarios. Long-context capabilities show promise, but overall, the benchmark exposes substantial gaps in reasoning, generalization, and robustness that need addressing for real-world deployment.

This benchmark can guide development of AI assistants, automated scheduling tools, and travel planning systems that require understanding complex constraints and multi-step reasoning. It emphasizes the importance of tool integration and long-term context management, crucial for real-world applications. The insights gained can inform the design of more robust, scalable models capable of handling diverse, dynamic environments, ultimately advancing AI's role in everyday decision-making and operational tasks.

Models perform poorly under high complexity, indicating limited reasoning and memory capacity. Self-correction may cause overconfidence, reducing overall accuracy. Reliance on external APIs introduces variability and potential instability, affecting reproducibility. The benchmark, while realistic, still simplifies some real-world uncertainties, such as API failures or incomplete data. Future work should address these issues by improving model robustness, scalability, and interpretability, and expanding datasets to cover more diverse scenarios.