Source-linked AI summary
DeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraints
Yinger Zhang, Shutong Jiang, Renhao Li, Jianhong Tu, Yang Su, Lianghao Deng, Xudong Guo, Chenxu Lv, Junyang Lin
TL;DR
Existing benchmarks underrepresent active information gathering and global constrained optimization in realistic long-horizon tasks. DeepPlanning addresses this with multi-day travel and multi-product shopping evaluations, finding that frontier agents still struggle and that explicit reasoning and parallel tool use are important for better effectiveness–efficiency trade-offs.
Problem
Existing agent benchmarks emphasize local constraints and abstract away the active information acquisition and global optimization required by realistic long-horizon planning.
Method
DeepPlanning benchmarks proactive information acquisition, local constrained reasoning, and global constrained optimization through complex travel and shopping tasks with verifiable evaluation.
Results
Frontier agentic LLMs show fundamental limitations on DeepPlanning, while reliable explicit reasoning patterns and parallel tool use support better effectiveness–efficiency trade-offs.
Takeaways & Limitations
DeepPlanning provides a foundation for evaluating and improving agent reliability on complex, grounded, long-horizon planning challenges.
Takeaways & Limitations
The benchmark is limited to travel and shopping, uses synthesized constrained queries that may shift from real user distributions, and focuses on single-turn planning.
Abstract
from arXiv · showhide
While agent evaluation has shifted toward long-horizon tasks, most benchmarks still emphasize local, step-level reasoning rather than the global constrained optimization (e.g., time and financial budgets) that demands genuine planning ability. Meanwhile, existing LLM planning benchmarks underrepresent the active information gathering and fine-grained local constraints typical of real-world settings. To address this, we introduce DeepPlanning, a challenging benchmark for practical long-horizon agent planning. It features multi-day travel planning and multi-product shopping tasks that require proactive information acquisition, local constrained reasoning, and global constrained optimization. Evaluations on DeepPlanning show that even frontier agentic LLMs struggle with these problems, highlighting the importance of reliable explicit reasoning patterns and parallel tool use for achieving better effectiveness-efficiency trade-offs. Error analysis further points to promising directions for improving agentic LLMs over long planning horizons. We open-source the code and data to support future research.
1 Introduction
DeepPlanning targets a gap in agent evaluation: real-world planning requires active information gathering, local constraint handling, and global optimization across entire solutions. The benchmark evaluates these abilities on travel and shopping tasks, exposing limitations in frontier agents and identifying reasoning and tool-use directions.
- Existing benchmarks emphasize local, step-level constraints but insufficiently test global constraints involving total time, cumulative cost, and cross-subtask dependencies.
- Classical and temporal planning benchmarks abstract away the active information acquisition required by real-world multi-day travel and multi-product shopping.
- DeepPlanning evaluates proactive information acquisition, local constrained reasoning, and global constrained optimization in Travel Planning and Shopping Planning.
- Reliable explicit reasoning patterns and parallel tool use improve effectiveness–efficiency trade-offs, while error analysis identifies omissions and difficulty with implicit environmental constraints.
- The benchmark uses complex travel and shopping tasks with reproducible, easy-to-verify evaluation through offline sandboxes and rule-based checkers.
- Large-scale evaluation exposes fundamental limitations of frontier agentic LLMs in long-horizon planning and motivates more realistic evaluation settings.
2 Related Works
Prior planning benchmarks cover classical, temporal, and real-world tasks, but often simplify horizons, omit complex constraints, or abstract away information acquisition. These limitations motivate a more comprehensive long-horizon planning benchmark.
- Existing benchmarks can also weaken global constraints or make information acquisition and task settings too trivial for thorough evaluation.
- Classical and temporal planning benchmarks show that LLM agents struggle under specific global constraints but simplify the planning setting.
- Recent travel-planning benchmarks use real-world scenarios but often simplify planning horizons or lack complex constraints.
3 DeepPlanning
DeepPlanning evaluates long-horizon agents in offline travel and shopping environments where success requires tool-mediated information acquisition, local reasoning, and global constraint satisfaction. Its tasks are generated with layered constraints and evaluated through automated checks.
- Benchmark Overview: DeepPlanning evaluates Travel Planning and Shopping Planning in self-contained offline sandboxes accessed through Python toolkits.
- Travel Planning: Travel tasks require minute-level multi-day itineraries integrating transportation, accommodation, attractions, and dining under coupled time, location, and budget constraints.
- Core Capabilities: Agents must actively retrieve environmental states, including transportation options, user-specific attributes, attraction availability, and other information not guaranteed by the query.
- Global Constrained Optimization: Global optimization requires feasible timing, transportation, and budget across travel itineraries, while shopping requires cart-level optimization under total-cost and coupon constraints.
- Database and Toolbox Design: Travel environments use public real-world data, whereas shopping environments synthesize fine-grained product data for controlled complexity.
- Task Construction: Tasks are constructed by designing domain databases and APIs, progressively injecting base, personalized, and environmental constraints, then applying manual quality control.
- Task Evaluation: Automated evaluation uses code-based checks, including eight equally weighted commonsense dimensions spanning 21 checkpoints for travel plans.
4 Experiments
DeepPlanning evaluates frontier function-calling agents on travel and shopping tasks requiring long-horizon information gathering, constrained reasoning, and global optimization. Results show fragile case-level planning, benefits from internal reasoning, higher performance with more tool use, and declining performance as complexity increases.
- 4.2 Main Results: Frontier agents often satisfy individual constraints while failing to produce fully correct global plans; the best Travel Planning model reaches only 35.0% case accuracy.A single budget violation or scheduling conflict can invalidate an otherwise high-scoring plan.
- 4.2 Main Results: High Shopping Planning Match Scores frequently fail to translate into high Case Accuracy, revealing difficulty integrating correct actions into executable plans.The gap reflects failures in globally coherent end-to-end planning.
- 4.2 Main Results: Reasoning-enabled models generally outperform non-reasoning counterparts; Gemini-3-Flash-Preview leads Shopping Planning with 60.0% Case Accuracy despite poor Travel Planning performance.The benchmark is generally led by GPT-5 and Claude-4.5 models using maximal reasoning effort.
- 4.3 Cost-Performance Trade-offs: Model performance generally increases with tool-call count, with GPT-5.2-high achieving the best score at roughly 224 tool invocations per task.Travel Planning requires proactive validation of times, transfers, and budgets beyond parametric knowledge.
- 4.3 Cost-Performance Trade-offs: Claude-4.5-Opus thinking mode improves performance while reducing interaction turns from 16.9 to 12.5 and tool calls from 79.5 to 72.9.The authors associate this trade-off with less redundant trial-and-error and more consolidated tool use.
- 4.3 Cost-Performance Trade-offs: GPT-5.2-high achieves +12.7% performance over GPT-5.1-high but requires nearly 10× more turns, contrasting sequential verification with parallel tool execution.GPT-5.1-high bundles multiple calls into one turn, whereas GPT-5.2-high uses a step-by-step workflow.
- 4.4 Impact of Task Complexity: Performance consistently drops as task complexity increases across both domains, with Travel Planning scores declining from 2- to 7-day itineraries.Shopping Planning accuracy declines from Level 1 to Level 3 as cross-item constraints such as price ranges and coupon timing are added.
- 4.5 Error Analysis: Global optimization failures are the most prevalent categorized errors, occurring 101 times in Travel Planning and 52 times in Shopping Planning.The category captures failures to integrate interdependent decisions under overarching constraints.
5 Conclusion
DeepPlanning is introduced as a benchmark for practical long-horizon agent planning in real-world travel and shopping settings. Its evaluation finds that state-of-the-art agents struggle significantly, exposing a gap in planning reliability.
- 5 Conclusion: DeepPlanning evaluates long-horizon LLM agent planning through multi-day travel and complex shopping scenarios with proactive information gathering and multi-level constrained optimization.The benchmark targets real-world planning settings rather than isolated actions.
- 5 Conclusion: State-of-the-art agents struggle significantly on DeepPlanning, revealing a fundamental gap in planning reliability.The benchmark is intended to support development of agents for complex, grounded planning challenges.
Limitations
DeepPlanning remains limited in domain coverage, query realism, and interaction scope. The authors identify broader scenarios, more realistic user-query distributions, and multi-turn interaction as future directions.
- Limitations: DeepPlanning is restricted to travel and shopping domains, limiting its coverage of real-world agent-planning scenarios.The authors propose incorporating a broader range of scenarios.
- Limitations: Synthesized multi-level constraints in user queries may create distribution shift relative to real user queries, despite real-world data in the sandbox databases.This limits direct realism of the query distribution.
- Limitations: The benchmark focuses on single-turn, multi-step planning and does not model multi-turn user-agent interactions.The authors identify multi-turn interaction modeling as future work.
A.1 Travel Planning Output Example
The paper provides example outputs for both benchmark domains: a two-day travel itinerary with a budget and a shopping cart containing selected items and coupons.
- A.1 Travel Planning Output Example: The travel-planning example consists of a two-day itinerary and budget.
- A.1 Travel Planning Output Example: The shopping-planning example consists of a cart containing selected items and coupons.
B Tool Schemas and Database Schema
The travel-planning task uses dedicated tools whose definitions are presented in Table 3.
- Table 3 defines the tools used in the travel planning task.
- These tool definitions specify the interfaces available for travel-planning operations.
- The table serves as a reference for the travel-planning tool layer.
B.2 Database Schema
The database schema section documents the detailed fields used in the travel-planning task and explains their meanings.
- Table 5 lists the detailed database fields used in the travel planning task.
- The schema explains the meanings of the fields in the travel-planning databases.
- The database documentation provides a reference for interpreting travel-planning records.
C Evaluation Details
The evaluation-details materials describe the commonsense scoring criteria and provide system prompts for the travel and shopping tasks, including travel-plan format conversion.
- Scoring criteria: The Travel Planning evaluation uses 21 scoring criteria for its commonsense score.
- System prompts: System prompts are provided for both Travel Planning and Shopping Planning tasks.
- Plan conversion: A separate prompt supports plan format conversion in the Travel Planning domain.
- Example: The materials include an example with a total estimated budget of 2,923RMB.
Box 2: Example for cart checkout
The materials illustrate shopping-cart contents and the prompt-driven requirements for producing tool-grounded, continuous, daily travel plans with exact names and cost details.
- Cart contents: The cart includes running shoes, a performance top, wide-leg trousers, sneakers, slippers, and training leggings.
- Cart checkout: The example cart contains six items with a total price of 9915.9.
- Information collection: Travel plans must be generated only after tools collect necessary information such as flights, routes, and prices.
- Tool grounding: All itinerary attractions, hotels, restaurants, and transportation details must come from their corresponding tool query results.
- Name matching: Names in the itinerary must exactly match the names returned by tools.
- Itinerary format: Daily itineraries require continuous activity times, with waiting or preparation represented as buffer activities.