DeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraints

ArXiv: 2601.18137

🎯 Pitch

Even the best frontier LLM agents solve only 35% of multi-day travel tasks completely correctly, not because they fail at individual tool calls, but because they cannot integrate them into globally coherent plans under budget and time constraints. DeepPlanning exposes that high per-step accuracy masks catastrophic global optimization failures, with 72% of travel errors stemming from this systemic weakness.

---

1. Executive Summary

This paper introduces DeepPlanning, a benchmark for evaluating long-horizon agentic planning in LLMs through multi-day travel planning and multi-product shopping tasks that require proactive information gathering, local constrained reasoning, and global constrained optimization (e.g., assembling an itinerary under a total time and financial budget while respecting per-attraction opening hours). Evaluations across frontier models—including GPT-5, Claude-4.5, and Gemini-3 families—reveal that even the best-performing agent achieves fully correct plans in only 35.0% of travel cases and 54.2% of shopping cases, establishing that current LLM agents struggle to integrate individually correct tool-use actions into globally coherent plans even when deliberate internal reasoning improves the cost–performance tradeoff. The benchmark exposes a fundamental fragility: high constraint-level scores routinely fail to translate into case-level accuracy, with the dominant failure mode being global optimization breakdowns (101 of 140 annotated travel failures) that cascade across interdependent decisions.

2. Context and Motivation

The Gap: Agent Benchmarks Measure Tool Use, Not Planning

The paper identifies a fundamental misalignment between what current benchmarks evaluate and what real-world agentic deployment actually demands. As LLM-based agents transition from research prototypes to practical systems, the field has shifted from evaluating short-horizon, tool-centric capabilities—"can the model make a correct single function call?"—toward longer-horizon, user-centric tasks where agents must execute sequences of dozens or hundreds of tool invocations to satisfy a complex goal (Section 1). However, the paper argues that this shift has been superficial: even these newer long-horizon benchmarks still emphasize local, step-level constrained reasoning while largely ignoring the global constrained optimization that characterizes genuine planning.

The distinction matters because these represent fundamentally different cognitive demands. Local constrained reasoning asks: "Given a set of hotel search results, can I filter by the user's star-rating preference and amenities?" This is a single-step filtering operation that—while requiring a correct tool call with appropriate parameters—does not involve any tradeoffs across steps. Global constrained optimization asks: "Given a total budget of ¥5,000 across three days with specific transportation, accommodation, dining, and attraction requirements, can I assemble an itinerary where every choice respects all interacting constraints simultaneously?" Here, a seemingly optimal choice at day 1 (e.g., booking an expensive but highly-rated hotel) may cascade into budget violations on day 3, or a particularly long attraction visit may eliminate the only feasible lunch window. These interdependencies mean that agents cannot optimize greedily step-by-step; they must reason about the plan holistically.

The paper's central diagnostic is that existing benchmarks fail to assess this holistic reasoning, leaving the community without a reliable measure of comprehensive agent planning ability:

"Current agent evaluation benchmarks largely fail to assess their ability to navigate these holistic boundaries, leaving the community without a reliable measure for comprehensive agent planning." (Section 1)

This gap is not merely academic. As LLM agents are deployed for high-stakes applications—travel booking, financial planning, supply chain optimization—the cost of a globally incoherent plan is real money, wasted time, and user trust erosion. An agent that correctly books flights, hotels, and restaurants individually but produces an impossible itinerary (e.g., arriving at a restaurant after it closes because the preceding attraction ran long) has failed the user, even if each individual tool call was technically correct. Current benchmarks would score such an agent highly on tool-use accuracy while completely missing the planning failure.

Two Parallel But Insufficient Evaluation Traditions

The paper situates DeepPlanning at the intersection of two evaluation traditions, arguing that neither adequately captures the capabilities needed for practical long-horizon planning.

Tradition 1: Agentic Tool-Use Benchmarks (The "Complex Instruction Following" School)

Benchmarks like API-Bank (Li et al., 2023), ToolLLM (Qin et al., 2024), and BFCL (Patil et al., 2025) evaluate LLMs' ability to make correct single or few-step function calls. More recent work has pushed toward longer horizons and user-centric tasks: τ-Bench (Yao et al., 2024) introduces dual-control environments with tool-agent-user interaction, ARE (Andrews et al., 2025) scales up environment diversity, and UserBench (Qian et al., 2025) and VitaBench (He et al., 2025) focus on interactive, user-centered scenarios. Web-based benchmarks like WebShop (Yao et al., 2022), Mind2Web (Deng et al., 2023), WebArena (Zhou et al., 2024), WebVoyager (He et al., 2024), and DeepShop (Lyu et al., 2025) test agents navigating real or simulated web environments to accomplish goals.

The paper identifies a common weakness across this entire lineage: they emphasize complex instruction following rather than deliberative, multi-step planning (Section 2.1). An instruction-following agent succeeds by correctly interpreting and executing each sub-goal as it appears. A planning agent must construct the sub-goals themselves, reason about their interdependencies, and sometimes backtrack when a locally good decision turns out to be globally infeasible. The paper states this explicitly:

"these benchmarks largely emphasize complex instruction following rather than deliberative, multi-step planning, and thus fail to rigorously assess LLMs' ability to verify plans and backtrack under global resource constraints." (Section 2.1)

The key missing element is constraint propagation across time and resources. In WebArena, booking a flight and booking a hotel are largely independent tasks—you can succeed at one regardless of what you did on the other. In DeepPlanning's travel domain, booking a flight on a specific date affects which hotels are available (since check-in dates must align), which attractions can be visited (given travel time from the airport), and how much budget remains for dining—all simultaneously.

Tradition 2: LLM Planning Benchmarks (The "Abstract Planning" School)

A separate research thread evaluates LLMs on classical planning problems. PlanBench (Valmeekam et al., 2023) tests LLMs on PDDL-style planning domains like Blocksworld, where the environment dynamics are fully specified and the challenge is plan synthesis under logical preconditions and effects. Temporal planning benchmarks like TimeArena (Zhang et al., 2024) and TCP (Ding et al., 2025) add duration constraints and temporal reasoning requirements. These benchmarks definitively show that LLMs struggle with planning under constraints—even on abstract, fully-specified problems where all relevant world state is given upfront.

However, the paper identifies a critical disconnect between these abstract settings and real-world planning. Classical planning benchmarks assume complete information: the agent starts with full knowledge of the domain dynamics, available actions, and initial state. Planning reduces to searching for a sequence of actions that achieves the goal state while respecting preconditions. Real-world planning—the kind users actually need agents to perform—is fundamentally different because information about the world is not given; it must be actively acquired.

Consider the difference. In Blocksworld, the agent knows exactly which blocks exist, their positions, and what actions are available. The challenge is pure reasoning. In real-world travel planning, the agent doesn't know which flights exist on a given date, what hotels are available, how far the airport is from downtown, or whether a particular attraction is open on Mondays. Each of these facts must be discovered through tool calls, and the specific facts discovered will constrain and reshape the plan in ways the agent cannot fully anticipate until it queries the environment.

The paper captures this distinction under the rubric of proactive information acquisition (Section 3.1): the agent must not merely reason about known constraints but must actively seek out the constraints themselves. Classical planning benchmarks abstract away this process entirely, making them poor proxies for real-world agent capability:

"these settings are simplified and abstract away the complex information acquisition process inherent to reality. In contrast, real-life long-horizon tasks such as multi-day travel and multi-product shopping require agents to proactively seek information from environments." (Section 1)

The Specific Failures of Existing Real-World Planning Benchmarks

The paper identifies a handful of benchmarks that attempt to bridge the gap by evaluating planning in real-world domains, but argues each suffers from specific limitations that prevent them from testing holistic constrained optimization.

TravelPlanner (Xie et al., 2024) introduces travel itinerary planning with tool-based information retrieval. However, the paper identifies two critical simplifications: it operates at day-level rather than minute-level granularity, meaning temporal constraint interactions are coarsely modeled (e.g., you don't need to check whether lunch fits between two attractions when the whole day is a single unit), and it lacks the complex, multi-dimensional constraints that force global optimization tradeoffs. TripScore (Qu et al., 2025) shares this day-level horizon limitation.

ChinaTravel (Shao et al., 2025) offers an open-ended Chinese travel planning benchmark but the paper characterizes its local constraints as trivial—they can be satisfied through straightforward filtering without requiring cross-subtask optimization. An agent can process each constraint independently without reasoning about their interactions.

Other domain-specific efforts like personal LLM agent travel planning (Singh et al., 2024) and TripTailor (Wang et al., 2025) suffer from overly coarse global constraints or focus on personalization rather than hard optimization requirements.

The paper's diagnosis synthesizes these individual shortcomings into a systematic framework. Existing benchmarks suffer from one or more of three deficiencies (Section 1):

1. Ineffective global constraints: Constraints that exist on paper but don't actually bind or interact in ways that force tradeoffs. If the budget is so generous that any reasonable plan satisfies it, there's no optimization challenge.

2. Trivial local constraints: Individual requirements that reduce to simple filtering ("find a hotel with a gym") rather than requiring reasoning about how a local choice propagates to affect global feasibility.

3. Overly coarse global constraints: Budgets or time limits at a granularity that doesn't capture real-world interactions (e.g., total trip budget without per-day constraints, or day-level schedules that abstract away the need to sequence activities within hours).

DeepPlanning explicitly targets all three gaps by: (i) constructing tasks where global constraints are binding and interact meaningfully across subtasks; (ii) injecting local constraints that require multi-step information gathering and reasoning (e.g., "book a flight where at least 4 tickets are available" requires querying seat status, not just flight existence); and (iii) operating at minute-level temporal granularity with itemized cost tracking that makes budget interactions explicit.

Why This Gap Has Persisted (And Why It Matters Now)

Understanding why this evaluation gap hasn't been closed requires appreciating a structural tension in benchmark design. Creating tasks that genuinely require global optimization is hard because you need:

• A rich environment with enough interacting variables that local greedy search fails. If the state space is too simple, any reasonable strategy finds the optimum, and you're measuring tool-use competence, not planning ability.
• Uniquely verifiable solutions. If multiple plans satisfy all constraints equally well, evaluation becomes ambiguous—you need to check constraint satisfaction rather than comparing against a ground-truth plan, and partial constraint satisfaction scoring becomes necessary.
• Solvability guarantees. You need to know that a solution exists, otherwise you can't distinguish an incapable agent from an impossible task.

The paper's construction methodology (Section 3.2) is designed specifically to address these challenges through solution-centric reverse generation: the optimal solution is constructed first, constraints are layered on top to make that solution unique, and the environment is then populated with data that eliminates alternative optima. This is a non-trivial engineering contribution that explains why prior benchmarks—which generally start from environments and generate tasks forward—failed to achieve the same complexity.

The timing of this benchmark is also significant. As of the paper's writing, frontier models have reached a point where they can reliably execute individual tool calls and handle moderate-length task sequences. The field is ready to push from "can the agent use tools correctly?" to "can the agent plan correctly?" The poor performance on DeepPlanning even from the strongest models—GPT-5.2-high achieves only 35.0% case accuracy on Travel Planning (Table 2)—confirms that this is exactly the right moment to introduce this harder evaluation criterion. If models had scored 90%, the benchmark would be too easy to provide useful signal. If they had scored 0%, it would be impossible to distinguish model capabilities. The spread from ~5% (non-reasoning models) to ~35% (top reasoning models) on Travel Planning case accuracy provides exactly the kind of discriminative power a useful benchmark should offer.

How This Paper Positions Itself

The paper does not propose a new model architecture, training method, or prompting technique. It is purely an evaluation and analysis contribution—a benchmark paper in the strongest sense. Its positioning is:

1. Against existing tool-use benchmarks: DeepPlanning raises the bar from "can the agent execute the right API calls?" to "can the agent synthesize individually correct API calls into a globally feasible plan under interacting constraints?" The paper argues this is the natural next step in the progression from short-horizon tool use (BFCL, API-Bank) through longer-horizon task execution (WebArena, τ-Bench) to genuine planning (DeepPlanning).

2. Against existing planning benchmarks: DeepPlanning reintroduces the information acquisition dimension that classical planning benchmarks abstract away, while maintaining the constraint complexity that web-based benchmarks dilute. It sits at the intersection: real-world domains with real information retrieval needs AND formal constraint satisfaction requirements with verifiable unique solutions.

3. As a diagnostic tool: Beyond simple "how well do models score?" questions, the benchmark is structured to reveal why agents fail. The three competency dimensions (proactive information acquisition, local constrained reasoning, global constrained optimization) map directly to the error taxonomy in Section 4.5, enabling analysis that identifies specific capability gaps rather than producing a single aggregate score. The error analysis showing that global optimization failures dominate (101 of 140 annotated travel failures, Figure 5) is itself a finding that would not be discoverable without a benchmark explicitly designed to expose this dimension.

4. As a foundation: The paper explicitly frames DeepPlanning as providing "a foundation for developing next-generation agents capable of tackling complex, grounded planning challenges" (Section 5). It is not claiming to solve the planning problem—it is providing the measuring stick that will tell us when someone has.

3. Technical Approach

This is a benchmark construction and evaluation paper whose core idea is to create a set of long-horizon planning tasks with verifiable unique solutions by reverse-generating the problem from the answer: construct the optimal plan first, then layer on constraints that eliminate all alternatives, then build a sandbox environment populated with data that makes only that plan feasible.

3.1 Reader Orientation

The system being described is not a model or an algorithm but a benchmark infrastructure: a set of 240 sandboxed planning tasks (120 travel, 120 shopping) backed by databases and accessible through Python APIs, along with a rule-based evaluation framework that scores agent outputs without requiring LLM judges. The problem it solves is the absence of evaluation settings that force agents to demonstrate global constrained optimization—the ability to reason about how choices in one part of a plan constrain choices elsewhere under holistic budgets—rather than just local, step-level tool-use correctness. The solution's shape is a solution-centric, reverse-generation pipeline: construct the uniquely correct answer first, then generate the environment and task description to make that answer the only feasible one, then verify agent outputs against that ground truth using deterministic code-based checkers.

3.2 Big-Picture Architecture (Diagram in Words)

The DeepPlanning benchmark has four major components, layered in order of construction:

1. Sandbox Environments — domain-specific databases (flights, hotels, attractions, restaurants, road routes, points of interest for Travel; products, users, shipping for Shopping) populated with real and synthetic data, plus a set of Python APIs that are the only way agents can access environment state. Each task gets its own isolated sandbox instance.
2. Task Generation Pipeline — a three-stage process that constructs tasks backward: starts from a base skeleton (destination, dates, product themes), injects personalized user constraints, then injects environmental constraints that force the solution through a unique path. An LLM converts the structured constraint set into a natural-language user query.
3. Agent Execution Framework — a function-calling interface where models receive system prompts describing the domain tools and task requirements, then iteratively invoke tools (up to 400 calls) to gather information and produce a final plan. All frontier models are evaluated through this identical interface.
4. Rule-Based Evaluation System — code-based checkers that compare agent outputs against ground-truth solutions. For Travel Planning, this involves parsing natural-language itineraries into structured format, then running 21 automated checkpoints across eight dimensions. For Shopping Planning, this involves exact product-ID matching against the ground-truth cart.

Information flows through these components in sequence during construction: environments are built first, tasks are generated inside those environments, and evaluation code is derived from the task constraints. During evaluation, agents interact only with the sandbox APIs, never with the evaluation layer, and their final outputs are scored offline by the checkers.

3.3 Roadmap for the Deep Dive

• First, the benchmark design philosophy and the three core competencies it targets (proactive information acquisition, local constrained reasoning, global constrained optimization) — because these define what the benchmark measures and why the task construction decisions make sense.
• Second, the sandbox environments — the databases and tool APIs that form the "world" agents interact with. Understanding the tool schemas is essential for understanding what agents must discover and how the environment constrains planning.
• Third, the task construction pipeline — the reverse-generation methodology with its three stages and the challenge of ensuring solvability and uniqueness. This is the core engineering contribution because it determines whether the benchmark actually tests what it claims.
• Fourth, the evaluation methodology — the Commonsense Score taxonomy, Personalized Score, Composite Score, Case Accuracy for Travel Planning, and the Match Score/Case Accuracy for Shopping Planning. Understanding precisely what is measured is essential for interpreting the experimental results.
• Fifth, the agent instantiation protocol — how models are configured as function-calling agents, the system prompts, and the interaction budget constraints.

3.4 Detailed, Sentence-Based Technical Breakdown

Design Philosophy: The Three Core Competencies

The paper organizes its benchmark design around three capabilities it argues are jointly necessary and individually insufficient for real-world long-horizon planning. These competencies serve dual purpose: they guide what kinds of tasks to construct, and they structure the error taxonomy used to diagnose model failures.

Proactive Information Acquisition is the ability to search for and retrieve necessary state information that is not given in the user query or system prompt. The paper distinguishes this from parametric recall: the agent cannot know a priori which flights exist on a particular date, what the weather will be, or whether a specific attraction is closed on Mondays. Each fact must be discovered through tool calls, and the specific facts discovered will reshape the plan. A common failure the paper highlights is overlooking the need to query intra-city transportation options—an agent might book a hotel and an attraction, correctly noting their individual details, but fail to check whether they are reachable from each other within the itinerary timeline. This capability matters because it represents the transition from "given the relevant information, can you reason about it?" to "can you figure out what information you need and go get it?"—a fundamentally more challenging agentic competence.

Local Constrained Reasoning is the ability to handle explicit and implicit logic within individual sub-tasks. Explicit constraints are user-stated preferences: "book a three-star hotel," "find a ShockWave-brand product rated above 4.7." Implicit constraints are environmental realities that emerge during interaction: a flight has limited seat availability (only 2 seats remaining when you need 4), an attraction's opening hours conflict with the planned visit, a coupon stacks with some products but not others. The paper's innovation here is not in defining local reasoning—every tool-use benchmark tests this to some degree—but in making the implicit constraints sufficiently numerous and non-obvious that they cannot all be handled by simple filtering without genuine reasoning about edge cases.

Global Constrained Optimization is the signature capability that the paper argues existing benchmarks fail to evaluate. It is the ability to optimize the overall solution under holistic constraints that span multiple sub-tasks and dimensions. In Travel Planning, these constraints operate across three dimensions simultaneously: time (no schedule overlaps, respect visit durations and transit times), space (geographic feasibility between consecutive locations), and budget (accurate aggregation of all costs within a trip-level limit). In Shopping Planning, the optimization extends to combinatorial coupon usage: applying multiple coupons may require selecting a cart that is not the cheapest item-by-item but achieves the lowest final total after all discounts and shipping costs are factored in. The critical property is that these constraints are interacting: choosing a cheaper hotel in a less convenient location may increase transportation costs or eliminate feasible meal windows, making the "locally optimal" choice globally suboptimal. Agents must reason about the joint effect of decisions across the entire plan, which requires something beyond step-by-step greedy execution.

Sandbox Environments: Databases and Tool APIs

Travel Planning Environment. Each of the 120 travel tasks runs in its own isolated sandbox instance containing seven domain-specific databases stored as CSV files (Table 5 in the Appendix). These databases are:

• attractions.csv — 19 fields including attraction_name, city, latitude, longitude, rating, opening_time, closing_time, closing_dates (e.g., "Monday"), min_visit_hours, max_visit_hours, ticket_price, and attraction_type (one of six categories: Historical and Cultural, Natural Scenery, Art Exhibition, City Landmark, Theme Park, Leisure Experience).
• flights.csv — 19 fields including origin_city, destination_city, dep_date, dep_datetime, arr_datetime, duration (minutes), flight_no, airline, seat_class, seat_status (Sufficient/Limited/Sold Out), price, and multi-leg routing via segment_index and route_index.
• trains.csv — 16 fields paralleling the flight schema but for rail transport, including train_no, train_type (Electric Multiple Unit/Regular Train), seat_class, and seat_status.
• hotels.csv — 12 fields including name, city, latitude, longitude, hotel_star (1–5 integer), price (per night), score, brand, and services (semicolon-separated tags like "Washer and Dryer").
• restaurants.csv — 14 fields including restaurant_name, city, latitude, longitude, price_per_person, cuisine, opening_time, closing_time, rating, and tags (e.g., "Must-Eat Top 10"). Additional fields like nearby_attraction_name and query coordinates link restaurants to the attraction-based recommendation system.
• pois.csv — a general points-of-interest table with poi_name, coordinates, address, and poi_type (attraction/restaurant/hotel).
• road_routes.csv — route information with origin and destination coordinates, distance_meters (integer), duration_minutes (integer), and cost (0 for walking routes, positive for driving).

Each task instance averages 7,708 database records (Table 1), making the information space too large for exhaustive enumeration within a reasonable agent interaction budget. The agent cannot simply "dump the database" through queries; it must selectively retrieve relevant information based on the planning state.

Agents access these databases through 9 specialized Python APIs (Table 3 of the Appendix), designed with a hierarchical structure that forces multi-step information gathering:

• query_train_info and query_flight_info — search for transportation by origin city, destination city, departure date, and optional seat class. Return train/flight numbers, departure/arrival times, station/airport details, duration, seat status, and price.
• query_hotel_info — search hotels by destination city, check-in/check-out dates, optional star rating and brand filters.
• query_attraction_details and query_restaurant_details — retrieve detailed information (including coordinates, hours, ratings, prices) for specifically named attractions or restaurants. These require knowing what to query: the agent must first discover attraction/restaurant names through recommendation APIs before it can retrieve their details.
• recommend_attractions — given a city name and optional attraction_type filter, returns a list of popular attractions. This is the discovery step that precedes detail queries.
• recommend_restaurants — given latitude/longitude coordinates (specified to 6 decimal places), returns nearby restaurants. Critically, the agent must first obtain coordinates through other means before it can use this function.
• query_road_route_info — given origin and destination coordinates, returns distance, duration, and cost for the route. The API auto-selects walking or driving mode, eliminating the need for the agent to specify transport mode but also removing a degree of control.
• search_location — given a place name, returns its latitude/longitude coordinates at 6-decimal precision. This is the bridging function that connects the named-entity world (hotel names, attraction names) to the coordinate-based world (road routes, restaurant recommendations).

The hierarchical dependency structure is intentional: to plan a day, the agent must chain together recommend_attractions → query_attraction_details → search_location for the attraction → recommend_restaurants near those coordinates → query_restaurant_details for promising candidates → query_road_route_info between consecutive locations. Skipping any link in this chain produces an infeasible plan because critical information (opening hours, transit times, restaurant proximity) will be missing or fabricated. This design forces the proactive information acquisition behavior that the benchmark aims to measure.

Shopping Planning Environment. Each of the 120 shopping tasks runs in a separate sandbox with three JSON-based databases (Table 6):

• products.json — 28 fields per product including product_id, name, price, brand, color, size, stock_quantity, material composition, physical attributes (thickness, elasticity, version_type or fit, collar_type), seasonal suitability, target_demographic, monthly_sales, total_sales, average_rating, rating distribution (1-star through 5-star counts), review summaries, shipping_origin, and shipping_provider.
• users.json — 20 fields per user including user_id, demographics (gender, age, height_cm, weight_kg), clothing size preferences (preference_fit, standard_size_tops, standard_size_bottoms, standard_size_shoes), and shipping address decomposed into shipping_province, shipping_city, and shipping_detail_address.
• Implicit coupon database — coupon rules that govern applicability across products.

Each task instance averages 171 database records (Table 1), a much smaller information space than Travel Planning but with denser constraint interactions.

Agents access these databases through 15 specialized APIs (Table 4), organized around a search-filter-sort-add pipeline:

• search_products — semantic search over product information given a natural-language query and optional result limit. This is the entry point for discovering relevant products.
• filter_by_brand, filter_by_color, filter_by_size — narrow down product lists by specific attributes using OR logic across multiple values.
• filter_by_applicable_coupons — filters to products eligible for ALL specified coupon names.
• filter_by_range — numeric filtering on any feature with an operator (>, <, ==, !=, >=, <=) and value. This enables constraint-based filtering like "rating above 4.7" or "price under 500."
• sort_products — sort a filtered list by any feature in ascending or descending order.
• get_product_details — retrieve complete information for a list of product IDs. The split between search (which returns summaries) and detail retrieval forces at least two-step information gathering.
• calculate_transport_time — estimate delivery time in days based on product ID, destination address (in pinyin), and optional shipping provider.
• get_user_info — retrieve user profile including size preferences and shipping address. The paper notes (Section 3.1) that "user-specific attributes such as clothing size or shipping destination are often omitted and must be actively retrieved"—agents must discover that they need this information and call the function, rather than having it provided upfront.
• add_product_to_cart — add a product and quantity to the shopping cart, checking stock availability.
• delete_product_from_cart — remove a product or reduce quantity.
• get_cart_info — retrieve the current cart state including all items and summary statistics.
• add_coupon_to_cart — apply a coupon, validate its applicability against cart contents, and update the cart total.
• delete_coupon_from_cart — remove a previously applied coupon.

The shopping toolset similarly creates a dependency chain: search_products → filter_* → get_product_details → get_user_info (to check size/shipping compatibility) → calculate_transport_time → add_product_to_cart → add_coupon_to_cart. The coupon-combinatorial challenge emerges after this chain: once products are in the cart, the agent must determine whether the current coupon configuration achieves the optimal final price, potentially requiring iterative removal and re-addition of products and coupons to search the combinatorial space.

Task Construction Pipeline: The Reverse-Generation Methodology

The most technically substantive contribution is the three-stage pipeline that constructs tasks with provably unique optimal solutions. The paper describes this as a "solution-centric, reverse-generation process" (Section 3.2) and provides the following schematic progression.

Stage 1: Database and Toolbox Design. Before any tasks are generated, the environments must be populated with data. For Travel Planning, the authors use public APIs (Fliggy for travel bookings, Amap for geographic/mapping data, web search for general information) to collect real-world data from popular tourist cities in China, covering transportation, accommodation, dining, and attractions. Key fields include prices, schedules, geographic coordinates, and ratings. The use of real data is noteworthy: it means flight schedules reflect actual airlines and routes, hotel prices approximate market rates, and attraction opening hours correspond to real-world operations. This grounds the benchmark in realistic planning difficulty rather than artificial puzzle-solving.

For Shopping Planning, the authors explicitly choose synthesized fine-grained product data rather than real-world data. This is a deliberate tradeoff: synthetic data enables controlled complexity. The product attributes—28 fields per product covering price, stock levels, ratings (with full 1-5 star distributions), material composition, fit characteristics, shipping details, and promotion applicability—can be systematically varied to create the exact constraint interactions needed for unique-solution tasks. Using real e-commerce data would make it difficult to guarantee that only one product combination satisfies all constraints, because real catalogs contain many near-duplicate products that would create solution ambiguity.

Stage 2: Layered Task Generation. This is the core innovation and proceeds in three sub-stages.

Base Skeleton Generation. The paper constructs a minimal scaffold for each task. In Travel Planning, the skeleton specifies three elements: departure city, destination city, and travel date. For example, a skeleton might be "depart Shanghai, visit Beijing, dates March 10-14." In Shopping Planning, the skeleton defines a set of items with a common theme: the paper gives the example "clothes and shoes for spring travel." This thematic grouping ensures that the task has internal coherence (the user isn't randomly buying a winter coat, a swimsuit, and a tuxedo) while remaining open enough that agents must identify which specific products match the theme.

The skeleton is deliberately minimal: it pins down the broad parameters of the task without constraining the solution space. All the difficulty comes from the constraint injection stages that follow.

Personalized Constraint Injection. The authors build domain-specific pools of personalized constraints—essentially, a library of constraint templates that can be sampled and combined. These constraints represent user preferences and requirements stated explicitly in the query. Examples given for Travel Planning include "recommend the highest-rated restaurant nearby" (requiring the agent to compare across options returned by recommend_restaurants) and "book a flight departing after 7:00 AM" (a hard temporal filter on departure times). For Shopping Planning, examples include "find a product named ShockWave with a rating above 4.7" (a specific product + numeric threshold) and "keep my total spending above 4500 yuan" (a budget floor rather than ceiling, creating a different optimization dynamic).

The sampling process selects "multiple, potentially complex constraints" (Section 3.2) from these pools. The key phrase is "potentially complex"—constraints are not simply applied one at a time in isolation. They are designed to interact. Booking a flight departing after 7:00 AM may eliminate some options that would have made a particular hotel check-in time feasible. The constraint pool includes templates that, when combined, force tradeoffs across sub-tasks.

Environment Constraint Injection. This is the sub-stage that distinguishes DeepPlanning from prior benchmarks. Beyond user-stated preferences, the authors inject implicit environmental constraints—limitations in the environment itself that are discoverable only through tool use and that reshape what solutions are feasible.

In Travel Planning, these include:

• Key attractions being closed on the planned visit day. An agent that assumes an attraction is open based on common knowledge will produce an infeasible plan; only by calling query_attraction_details and checking the closing_dates field can the agent discover the constraint.
• Flights having limited ticket availability. A user query might require booking for 4 people, but specific flights have seat_status: "Limited" with only 2 seats remaining. The agent must discover this through query_flight_info and either find an alternative flight or adjust the plan.
• The paper states that after adding these constraints, "candidates in databases are automatically adjusted so that exactly one optimal solution exists, ensuring solvability and uniqueness." The mechanism for this adjustment is not detailed in the main text, but the implication is that alternative solutions that would also satisfy all constraints are systematically pruned from the database. For example, if two hotels both satisfy the star rating, location, and price constraints, one might be made unavailable (closed, fully booked, or priced out of range) to leave only one feasible choice.

In Shopping Planning, the environmental constraints manifest as combinatorial optimization problems. The paper gives the specific example of "coupon-stacking rules that make a seemingly more expensive cart the cheapest after all discounts are applied." This means an agent who greedily selects the cheapest individual items will miss the global optimum: a slightly more expensive item might be eligible for a high-value coupon that makes the total cart cost lower than the apparently cheaper alternative. The optimization requires reasoning about joint cart-coupon configurations, not just per-item selection.

After all constraints are injected, the authors use an LLM to convert the structured constraint set into a conversational user query. This is a formatting step—translating constraint logic into natural language—but it's non-trivial because the query must sound like something a real user would actually ask while encoding all the constraints unambiguously. The paper acknowledges this by including human quality control as Stage 3 specifically to verify "natural, fluent language" in the generated queries.

Stage 3: Manual Quality Control. Human experts review the LLM-generated queries and the complete task definitions to ensure three properties:

• Natural, fluent language: The LLM-generated user query must read like a human wrote it, without template artifacts or awkward constraint enumerations. A query that says "I want a 3-star hotel with a washing machine, a flight after 7:00 AM, an attraction rated above 4.5..." as a bulleted list would be rejected as unnatural even if it encodes the constraints correctly. The query must embed constraints in flowing prose.

• Clear, unambiguous logic: The constraints must be interpretable without ambiguity. If a constraint says "nearby restaurant," there must be a deterministic definition of "nearby" that maps to the database (presumably, a specific radius around attraction coordinates queried via recommend_restaurants). Ambiguity would undermine the rule-based evaluation, since there would be no single correct answer to check against.

• Reachable solution for every task: This is the solvability guarantee. Human reviewers verify that the constraints are not contradictory (e.g., requiring a flight after 7:00 AM when all flights on that date depart earlier) and that the unique optimal solution identified during construction actually exists in the sandbox. A task that passes automated generation but fails human solvability review is either fixed or discarded.

The manual quality control stage is a practical necessity that the paper is transparent about. The layered generation process can construct constraint sets programmatically, but verifying that the resulting user query reads naturally and that the constraints interact as intended without creating impossibility requires human judgment that current LLMs cannot reliably provide.

Evaluation Methodology: The Rule-Based Scoring Framework

The paper eschews LLM-based evaluation entirely, using only code-based automated checkers. This is an important design choice motivated by reproducibility and objectivity: LLM judges introduce variance (different models judge differently, the same model may judge the same output differently across runs) and can be gamed by outputs that appear correct to a language model but are factually wrong. By contrast, rule-based checkers produce deterministic, reproducible scores that don't drift with model updates.

Travel Planning Evaluation. The evaluation process has two stages: parsing and scoring.

Parsing stage: Since models produce natural-language itineraries (not structured JSON), the evaluation system first uses Qwen-Plus-2507 to parse the free-text itinerary into a predefined structured format. The paper explicitly names this model (Qwen-Plus-2507) rather than saying "an LLM" generically, which implies the parsing model is a fixed part of the evaluation infrastructure chosen for consistency rather than being the best available model. The structured format presumably includes fields for each day's activities, with start/end times, locations, transportation between locations, and itemized costs. Once parsed, the itinerary can be programmatically checked against the sandbox databases.

Scoring stage: Four metrics are computed, all derived from 21 automated checkpoints organized into 8 dimensions (detailed in Table 7 of Appendix C).

The Commonsense Score measures whether the plan is physically and logically feasible as a real-world itinerary. Its 8 dimensions, each contributing equally (1/8 of the total if all sub-checkpoints within the dimension pass, 0 otherwise), are:

• Route Consistency (3 sub-checkpoints): Valid trip duration (the itinerary spans the correct number of days), closed-loop route structure (the traveler returns to the starting point or ends at a specified final destination without gaps), and seamless intercity transfers (connections between flights/trains and local activities are temporally and spatially feasible).
• Sandbox Compliance (4 sub-checkpoints): All scheduled accommodations, attractions, meals, and transportation must exist in the provided database. This catches hallucinated hotels, invented flights, and other fabrications that a model might produce when it can't find what it needs through tool calls.
• Itinerary Structure (4 sub-checkpoints): Traceable accommodation (the lodging for each day is specified), ends with accommodation (the day's activities conclude at the hotel, not at a random location), essential meal coverage (breakfast, lunch, and dinner are addressed), and essential attraction coverage (the planned number of attractions is met).
• Time Feasibility (2 sub-checkpoints): No temporal overlaps between consecutive activities, and transfer times between locations must be reasonable given the distance and transportation mode. "Reasonable" here is operationalized by comparing the agent's stated transfer duration against the query_road_route_info return value—if the agent claims 10 minutes for a route that the database says takes 45 minutes, the checkpoint fails.
• Business Hours (3 sub-checkpoints): Attraction visits must occur within opening hours, dining within service hours, and activities must avoid scheduled closure days (e.g., no visiting on Monday if closing_dates includes Monday).
• Duration Rationality (2 sub-checkpoints): Time allocated to attractions must fall within the min_visit_hours to max_visit_hours range from the database. Similarly, meal durations must be reasonable (presumably checked against typical dining duration norms or database-specified ranges).
• Cost Calculation Accuracy (1 sub-checkpoint): The agent's stated total cost must match the sum of individually itemized costs. This catches arithmetic errors where the agent correctly lists individual prices but adds them up wrong—a surprisingly common LLM failure mode.
• Activity Diversity (2 sub-checkpoints): Meal and attraction options across the multi-day itinerary must show variety. The sub-checkpoints penalize repetitive choices (e.g., eating at the same restaurant type every day, visiting only one category of attraction). This prevents agents from "solving" the planning problem by just repeating the same template day, which would be technically feasible but fails to deliver a good user experience.

The Commonsense Score for a task is the sum of the eight dimension scores, making it a value in the set {0/8, 1/8, 2/8, ..., 8/8}, essentially a fraction between 0 and 1.

The Personalized Score is binary (0 or 1) per task: it is 1 if all user-specific constraints injected during the Personalized Constraint Injection stage are satisfied, and 0 otherwise. These constraints are automatically translated from the structured task specification into code-based checks. For example, if the task specifies "book a three-star hotel," the checker verifies that hotel_star == 3 for the accommodation in the agent's plan. Every personalized constraint must pass for the score to be 1—this is a strict all-or-nothing metric that penalizes even a single missed user preference.

The Composite Score for a task is the arithmetic mean of the Commonsense Score (scaled to 0-1) and the Personalized Score (0 or 1). Mathematically:

$\text{Composite Score} = \frac{\text{Commonsense Score} + \text{Personalized Score}}{2}$

where Commonsense Score is already in [0,1] and Personalized Score is in {0,1}.

What it computes: a single number per task that equally weights physical/logical feasibility (can this plan actually be executed in the real world?) and user satisfaction (does this plan deliver what the user asked for?). The equal weighting is a design choice reflecting the paper's view that both dimensions are necessary: a plan that precisely matches user preferences but is temporally impossible is useless; a perfectly feasible plan that ignores user constraints is equally useless.

Why this form: the arithmetic mean treats the two dimensions as compensatory—strong performance on one can partially offset weakness on the other. An alternative like geometric mean or minimum would be non-compensatory, penalizing any weakness harshly. The paper's choice suggests they view partial credit as appropriate: a plan that's almost feasible and mostly satisfies preferences should score higher than a plan that fails completely on one dimension, even if neither is perfect. The composite score thus provides a more granular signal than the binary Case Accuracy, which would treat both plans as failures.

The Case Accuracy is the strictest metric: 1 only if BOTH the Commonsense Score is perfect (all 8 dimensions pass) AND the Personalized Score is 1 (all user constraints satisfied). Any single failure, no matter how small, drops the score to 0. This is the "can the agent actually solve the problem?" metric, as opposed to the "how close did the agent get?" metric captured by the Composite Score. The paper reports both because the gap between them—high Composite Scores with low Case Accuracy—is itself a finding about planning fragility (Section 4.2).

Shopping Planning Evaluation. Shopping evaluation is structurally simpler because outputs are already structured: agents produce a JSON shopping cart rather than free-text plans. Two metrics are used:

The Match Score measures partial credit:

$\text{Match Score} = \frac{\text{Number of products in agent's cart matching ground-truth items}}{\text{Total number of ground-truth items}}$

where a product "matches" when its product_id equals a ground-truth product_id (exact match, not fuzzy). This is effectively a recall metric: what fraction of the required products did the agent correctly identify and add to its cart?

What it computes: a value in [0,1] representing the proportion of ground-truth products the agent successfully identified. An agent that finds 3 out of 4 required products scores 0.75 regardless of whether it added any extra (incorrect) products.

Why this form: Match Score provides a granular signal for partial success. Unlike Travel Planning where "almost feasible" is hard to quantify granularly, Shopping Planning's item-level matching naturally supports partial credit. This metric can distinguish between an agent that found 0, 1, or 2 out of 3 required products, providing more diagnostic information than a binary success/failure metric.

The Case Accuracy for Shopping is binary: 1 only if ALL products in the cart exactly match the ground-truth products (both inclusion and exclusion—no missing items, no extra items), and 0 otherwise. This strict criterion means even a single wrong product (or missing product) drops the score to 0. The gap between Match Score and Case Accuracy—for example, a model might have 82.2% Match Score but only 45.8% Case Accuracy (Claude-4.5-Opus without thinking, Table 2)—indicates that identifying most products correctly does not guarantee identifying all of them correctly. The last product is often the hardest (due to coupon interactions or subtle constraint cascading).

Agent Instantiation Protocol

The paper standardizes model interaction to enable fair comparison across diverse model families. All models are instantiated as function-calling agents—they receive system prompts that describe the available tools in the OpenAI tool schema format and then iteratively generate function calls that are executed against the sandbox.

Tool specification format: Tools are specified in OpenAI function-calling format, which defines each function's name, description, and parameters (names, types, descriptions, required/optional status) as a JSON schema. The paper's tool schemas in Tables 3 and 4 follow this pattern. The choice of OpenAI format rather than a model-specific format is practical: it is the most widely supported function-calling interface, and using a single format across all models eliminates format-parsing as a confounding variable (a model failing because it can't produce valid JSON for a proprietary function-calling format would not be a planning failure).

Interaction budget: A maximum of 400 tool calls is allowed per task. This is a deliberately generous budget—Section 4.3 shows that even the most tool-intensive model averages only 224 calls per task (GPT-5.2-high on Travel Planning)—ensuring that models are not artificially constrained by call limits. The budget exists as a safety valve to prevent infinite loops, not as a resource the benchmark is designed to test against.

Repetition for statistical robustness: Each task is run four times per model, and results are averaged across all runs and tasks. This is significant because LLM outputs are stochastic—a model might get lucky on a single run (finding the right combination through a fortunate chain of tool calls) or unlucky (getting stuck in a loop). Averaging across four runs provides a more reliable estimate of expected-case performance. The paper does not report variance across runs, however, which would be informative for understanding whether some models are more reliable (low variance) or have high-variance "sometimes brilliant, sometimes terrible" performance patterns.

Reasoning mode configuration: For models that support both thinking and non-thinking modes (e.g., Claude-4.5-Opus, Qwen3-Max, GPT-5 series), the thinking mode is configured with maximum reasoning effort. The exact mechanism varies by model family—some expose an explicit reasoning_effort parameter, others toggle a "thinking" flag—but the intent is uniform: give the model as much internal deliberation budget as it supports. This is important because it establishes a fair upper bound for what each model can achieve: if a model underperforms even at maximum reasoning effort, the conclusion that it fundamentally struggles with planning is well-supported.

System prompts: The paper provides full system prompts in Appendix D (Boxes 3, 4, and 5). The Travel Planning prompt (Box 3) explains the task, describes the available tools, specifies the expected output format (a structured itinerary with times, locations, costs), and provides guidelines about constraint satisfaction. The Shopping Planning prompt (Box 4) similarly describes the task, tools, and expected JSON cart output. The existence of detailed system prompts is methodologically important: it means the paper is not testing "can the model figure out what to do from a vague instruction" but rather "given clear instructions about the task and tools, can the model execute correctly." This isolates planning ability from instruction-following ability.

Cross-domain evaluation: Travel Planning tasks are available in both Chinese and English (120 tasks each language, evaluated separately and averaged), while Shopping Planning tasks are English-only (120 tasks). The bilingual Travel evaluation tests whether models exhibit language-dependent planning capability—the same logical constraints should be equally solvable regardless of the language they're expressed in. The paper does not provide a per-language breakdown of results, so any language effects are absorbed into the averaged scores.

Overall evaluation flow: For each (model, task) pair, the process is: (1) initialize a fresh sandbox instance with isolated databases; (2) provide the system prompt and user query to the model; (3) the model generates function calls which are executed against the sandbox, with results returned to the model in the next interaction turn; (4) this cycle repeats until the model produces a final answer (the itinerary text or shopping cart JSON) or exhausts the 400-call budget; (5) the final answer is scored offline using the rule-based checkers. The offline scoring ensures that evaluation overhead does not count against model interaction budgets and that models cannot observe or adapt to the evaluation criteria during task execution.

4. Key Insights and Innovations

Innovation 1: Global Constrained Optimization as the Missing Evaluation Dimension

The paper's most intellectually distinctive contribution is not any specific benchmark feature but rather the diagnostic reframing of what has been missing from LLM agent evaluation. The field has largely treated "tool use" and "planning" as separate research threads—tool-use benchmarks measure whether an agent can make correct individual API calls (API-Bank, Li et al., 2023; BFCL, Patil et al., 2025), while planning benchmarks measure whether an LLM can synthesize action sequences in abstract domains with complete information (PlanBench, Valmeekam et al., 2023; TimeArena, Zhang et al., 2024). DeepPlanning argues that this separation has created a blind spot: neither tradition evaluates whether an agent can integrate individually correct actions into a globally coherent plan under interacting resource constraints, which is precisely what real-world deployment demands.

This framing is novel because it does not simply criticize existing benchmarks as "too easy" or "not realistic enough"—a common but unproductive genre of benchmark paper. Instead, it identifies a specific, well-defined capability that existing benchmarks structurally cannot measure: the ability to reason about how a choice at step t constrains the feasible choices at step t+k when those constraints propagate through shared resources (time, budget, geographic proximity). The paper formalizes this under the term global constrained optimization and distinguishes it from local constrained reasoning (single-step constraint satisfaction) and proactive information acquisition (knowing what to query). The key insight is that these three competencies are jointly necessary and individually insufficient—prior benchmarks tested at most two of them, and usually only one.

The significance goes beyond this specific benchmark. By naming and operationalizing global constrained optimization as a distinct evaluation target, the paper provides a vocabulary for diagnosing why agents fail, not just that they fail. The error analysis in Section 4.5, which finds that global optimization failures dominate (101 of 140 annotated travel failures, Figure 5), validates this framework retroactively: the dominant failure mode is exactly the one that prior benchmarks were not designed to detect. An agent evaluated only on ToolLLM or WebArena might score highly—correctly booking flights, hotels, and attractions individually—while producing an itinerary with overlapping activities, budget overruns, and geographic impossibilities. Those benchmarks would report success; DeepPlanning would correctly report failure. The reframing from "can the agent use tools?" to "can the agent plan under interacting global constraints?" is a conceptual advance that changes what it means for an agent to be "good" at real-world tasks.

This is a fundamental reframing, not an incremental improvement. Prior work had identified that agents struggle with long-horizon tasks (Yao et al., 2024; Andrews et al., 2025) and that LLMs are poor planners in classical domains (Valmeekam et al., 2023; Stechly et al., 2025). But those findings were domain-specific observations ("LLMs fail at Blocksworld," "LLMs make errors in WebArena"). DeepPlanning articulates a general principle—the lack of global constraint integration—that explains those failures and predicts new ones. This is the difference between cataloguing errors and understanding error mechanisms.

Innovation 2: Solution-Centric Reverse Generation as a Benchmark Construction Methodology

The paper's second conceptual contribution is methodological: the reverse-generation paradigm for constructing planning benchmarks with verifiable unique solutions. The standard approach to benchmark construction is forward: design an environment, populate it with data, then define tasks as goals to be achieved within that environment. This approach has a fundamental limitation for planning benchmarks—it is extremely difficult to guarantee that the environment, once populated, contains exactly one optimal solution. Multiple near-optimal solutions create evaluation ambiguity: if an agent finds a plan that satisfies all constraints but differs from the intended ground truth, is it correct or incorrect?

DeepPlanning inverts this process. The optimal solution is constructed first, constraints are layered on to make that solution uniquely optimal, and the environment database is then adjusted to eliminate alternative optima. The paper describes this as making "candidates in databases automatically adjusted so that exactly one optimal solution exists" (Section 3.2). This is a fundamentally different design philosophy from prior travel planning benchmarks like TravelPlanner (Xie et al., 2024), ChinaTravel (Shao et al., 2025), or TripScore (Qu et al., 2025), all of which build environments first and define tasks as queries against those environments.

The significance is that this methodology solves the evaluation validity problem for complex planning tasks. When the solution is unique, evaluation can be deterministic and rule-based—the checker simply verifies whether the agent's output matches the ground truth exactly. When multiple solutions exist, evaluation requires either (a) constraint-by-constraint satisfaction checking (which is complex, error-prone, and may miss emergent constraint violations) or (b) LLM-based judging (which introduces variance, bias, and potential for judge-gaming). The paper's ability to use purely code-based evaluation with clear pass/fail criteria on tasks with 7,708 average database records is a direct consequence of the reverse-generation methodology. Without unique solutions, the Commonsense Score taxonomy with its 21 sub-checkpoints would need to handle ambiguous cases where a plan satisfies all explicit constraints but differs structurally from expectations.

This is a methodological advance rather than a theoretical one, but it is fundamental in the sense that it enables benchmark complexity that would otherwise be infeasible. The Shopping Planning coupon-combinatorial tasks—where the optimal cart is not the cheapest item-by-item but achieves the lowest total after discount stacking—could not be reliably evaluated without a unique ground truth. Two different carts might both satisfy the budget constraint, but which one is "better"? The constraint-satisfaction approach would need to check every possible coupon-product combination. The unique-solution approach simply compares cart contents to the ground truth. The methodology makes the complexity feasible.

The tradeoff, which the paper acknowledges implicitly through its data choices, is that the approach requires controlled environments. Shopping Planning uses synthetic product data specifically because real e-commerce catalogs contain too many near-duplicate products to guarantee uniqueness. Travel Planning uses real data but then prunes alternatives during construction. The methodology trades environmental realism for evaluation rigor—a tradeoff the paper implicitly endorses by choosing synthetic over real data when uniqueness demands it.

Innovation 3: The Fragility Gap as an Empirical Finding About Agent Architecture

The paper's most consequential empirical finding is not that models score low on DeepPlanning—that would be expected from a deliberately difficult benchmark—but the specific discrepancy between constraint-level scores and case-level accuracy. Table 2 shows this pattern consistently: GPT-5.2-high achieves 88.5 Commonsense Score and 83.3 Personalized Score on Travel Planning (for a Composite Score of 85.8) but only 35.0% Case Accuracy. Claude-4.5-Opus with thinking reaches 79.3 and 70.9 (Composite 75.1) but only 22.7% Case Accuracy. Even weaker models show this gap: GPT-5.2-none scores 54.3 and 29.9 (Composite 42.1) with 0.4% Case Accuracy.

This gap is not a benchmark artifact. It reveals something fundamental about how current LLM agents construct plans: they can satisfy most individual constraints most of the time, but they cannot guarantee that all constraints are simultaneously satisfied. A plan with one temporal overlap, one budget miscalculation, or one missed user preference fails Case Accuracy even if every other aspect is perfect. The paper names this planning fragility: the inability to produce end-to-end correct plans even when the agent demonstrates competence at the level of individual constraint satisfaction.

This finding is significant because it challenges the implicit assumption driving much agent research: that if we improve individual capabilities (better tool use, better instruction following, better reasoning), holistic planning will emerge as a composition of those capabilities. The fragility gap suggests otherwise. High constraint-level scores demonstrate that models can do the individual pieces—they can query the right flights, filter hotels correctly, calculate costs, check business hours. What they cannot do is ensure that these individually correct pieces fit together into a coherent whole. The failure is architectural—a limitation of how models compose decisions across long horizons—not a deficiency in any single capability.

The error analysis in Section 4.5 reinforces this interpretation. The dominant failure pattern is not information omission (though that occurs—Pattern A1, insufficient search, appears ~70 times in the 140 annotated travel failures) or local reasoning errors (Pattern B). It is Pattern C: global optimization failures, appearing 101 times in travel and 52 times in shopping (Figure 5). These failures include temporal overlaps, budget overruns, repetitive activity selection violating diversity requirements, and logical discontinuities between days. These are not failures of knowledge or tool-use skill—they are failures of constraint propagation: the agent fails to track how a decision in one part of the plan ripples through to constrain decisions elsewhere.

This is a diagnostic finding rather than a metric gain, but it has substantial implications for research direction. It suggests that improving individual tool-use accuracy (the focus of much current work) will hit diminishing returns for complex planning unless accompanied by architectural improvements that enable global constraint tracking. Techniques like explicit budget tracking, temporal constraint propagation, and backtracking when local decisions create global infeasibility are underexplored in current agent architectures, which largely operate in a feed-forward, step-by-step manner. The fragility gap provides empirical motivation for researching these capabilities specifically, rather than assuming they will emerge from scaling or from better prompting.

Innovation 4: The Parallel-Sequential Tradeoff as a Revealed Strategy Dimension

Section 4.3 and Figure 3 present a finding that is easy to overlook but has subtle implications: different models within the same family adopt qualitatively different interaction strategies when solving the same tasks, and these strategies represent a genuine cost-performance tradeoff rather than one strategy being strictly dominant. Within the GPT-5 family, GPT-5.1-high favors parallel execution—bundling multiple tool calls into fewer interaction turns (approximately 10× fewer turns than GPT-5.2-high). GPT-5.2-high favors sequential, step-by-step execution with extensive verification. GPT-5.2-high achieves better performance (+12.7% composite score) but at dramatically higher interaction cost.

This is not presented as a benchmark design feature but as an empirical observation about model behavior. Its significance is that it reveals parallel vs. sequential execution as a learned or emergent strategy, not just a system-level configuration. The models were not instructed to use parallel or sequential execution patterns—both operated under the same function-calling protocol with the same tool schemas. The strategy difference emerged from their internal planning approaches. This suggests that models are implicitly making a meta-decision about how to allocate their interaction budget between breadth (parallel information gathering) and depth (sequential verification), and that this decision has real performance consequences.

The connection to the reasoning-vs-non-reasoning distinction adds another layer. Reasoning models consistently sit on a better part of the tradeoff curve (Figure 3): they achieve higher scores with comparable or lower interaction costs than their non-reasoning counterparts. For example, enabling thinking mode in Claude-4.5-Opus both improves composite score (63.1 → 75.1) and reduces interaction turns (16.9 → 12.5) and tool calls (79.5 → 72.9). This suggests that internal deliberation—thinking about what to query and in what order before executing tool calls—substitutes for external trial-and-error. The model can plan its information-gathering strategy more efficiently when it has a reasoning budget, reducing redundant queries and consolidating tool use into fewer, higher-quality actions.

This is an incremental but practically significant finding. It quantifies something that many practitioners suspect—that reasoning models are more efficient, not just more accurate—but provides concrete evidence with controlled comparisons. The implication for system design is that for complex planning tasks, the choice between a faster non-reasoning model and a slower reasoning model is not just about accuracy: the reasoning model may actually be cheaper in total interaction cost despite higher per-call inference cost, because it needs fewer calls. The parallel-sequential distinction also suggests that agent frameworks should not enforce a single interaction paradigm (always parallel, always sequential) but should allow the model to choose based on its assessment of the task's information structure. This insight connects to the broader observation about planning fragility: sequential verification (GPT-5.2-high's strategy) addresses the constraint propagation problem by checking each decision against all prior decisions, at the cost of more turns. Parallel execution (GPT-5.1-high's strategy) is faster but risks missing cross-decision interactions that create global infeasibility. The tradeoff is inherent to the planning problem, not an artifact of model design.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The benchmark consists of 240 tasks total: 120 Travel Planning tasks (each available in both Chinese and English, evaluated separately and averaged) and 120 Shopping Planning tasks (English only). Travel tasks use real-world data collected from public APIs (Fliggy, Amap, web search) for popular Chinese tourist cities; Shopping tasks use synthesized fine-grained product data to enable controlled complexity. Each task runs in an isolated sandbox backed by task-specific databases, with Travel averaging 7,708 records per task and Shopping averaging 171 records per task (Table 1). All tasks are constructed through the three-stage reverse-generation pipeline described in Section 3.2.

• Base model(s). The paper evaluates 16 models spanning 8 model families: OpenAI (GPT-5.2-high, GPT-5.2-none, GPT-5-high, o3, o4-mini), Anthropic (Claude-4.5-Opus, Claude-4.5-Sonnet, both with and without thinking), Google (Gemini-3-Flash-Preview, Gemini-3-Pro-Preview, Gemini-2.5-Pro), xAI (Grok-4.1-Fast in both reasoning and non-reasoning modes), DeepSeek-AI (DeepSeek-V3.2 with and without thinking), Alibaba (Qwen3-Max, Qwen-Plus, both with and without thinking), Z.ai (GLM-4.7 with and without thinking), Moonshot-AI (Kimi-K2-Thinking), and ByteDance (Seed-1.8-minimal, Seed-1.8-high). This cross-family coverage is deliberate: it ensures findings about planning difficulty are not artifacts of any single model architecture or training pipeline. For hybrid-thinking models, reasoning effort is set to maximum when operating in thinking mode.

• Metrics. Travel Planning uses four metrics: (1) Commonsense Score — sum of scores across 8 dimensions (route consistency, sandbox compliance, itinerary structure, time feasibility, business hours compliance, duration rationality, cost calculation accuracy, activity diversity) covering 21 automated sub-checkpoints, each dimension contributing 1/8 if all its sub-checkpoints pass; (2) Personalized Score — binary (0 or 1) indicating whether all user-specific constraints are satisfied; (3) Composite Score — arithmetic mean of Commonsense Score and Personalized Score; (4) Case Accuracy — binary (0 or 1), 1 only if BOTH Commonsense Score is perfect AND Personalized Score is 1. Shopping Planning uses two metrics: Match Score — number of products in the agent's cart matching ground-truth items divided by total ground-truth items (a recall measure on product IDs); Case Accuracy — binary, 1 only if the agent's cart exactly matches the ground-truth cart (no missing items, no extra items).

• Baselines. Since this is a benchmark paper introducing a new evaluation framework rather than proposing a new method, there are no algorithmic baselines in the traditional sense. The "baselines" are the non-reasoning variants of each model family (Table 2, top group), which serve as reference points for measuring the improvement from enabling deliberate internal reasoning. The bottom of Table 2 shows reasoning-model performance against these non-reasoning counterparts. Models are ranked by average Case Accuracy across both domains, providing a leaderboard that any future model can be compared against.

• Generation budget / compute accounting. All models are instantiated as function-calling agents with a maximum of 400 tool calls allowed per task. Cost is measured along two axes: average number of tool calls per task (reflecting total information retrieval volume) and average number of interaction turns per task (reflecting the sequential vs. parallel execution strategy, since multiple tool calls can be bundled into a single turn). These are reported in Figure 3 for Travel Planning. The 400-call cap is generous enough that no model hits it as a binding constraint under normal operation — the most tool-intensive model averages only ~224 calls per task (GPT-5.2-high on Travel Planning, Figure 3 top).

• Cross-validation / statistical protocol. Each task is run four times per model, and results are averaged across all runs and tasks. The paper argues this provides robustness against stochastic variation in LLM outputs. Travel Planning results are additionally averaged over both Chinese and English case variants. The paper does not report confidence intervals or standard deviations across runs, which limits assessment of whether observed differences between models (e.g., GPT-5.2-high at 44.6% average accuracy vs. Claude-4.5-Opus with thinking at 33.9%) are statistically reliable or could be explained by run-to-run variance.

Main Quantitative Results

Aggregate Model Rankings and the Reasoning Gap

Table 2 presents the full leaderboard, with models ranked by average Case Accuracy across Travel and Shopping Planning. The headline finding is that no model achieves even 50% average case accuracy across both domains: GPT-5.2-high leads at 44.6%, followed by Claude-4.5-Opus with thinking at 33.9% and GPT-5-high at 31.6%. The drop-off is steep: only 3 models exceed 30% average accuracy, and 8 of 16 models score below 20%.

The paper organizes models into two groups in Table 2: non-reasoning (top group, 9 models) and reasoning (bottom group, 16 model configurations). A clear pattern emerges: reasoning models consistently outperform their non-reasoning counterparts. For example, Claude-4.5-Opus improves from 26.3% (without thinking) to 33.9% (with thinking); GPT-5 series improves from 4.5% (GPT-5.2-none) to 44.6% (GPT-5.2-high). The gap is not uniform across model families: DeepSeek-V3.2 jumps from 5.3% to 21.6% (+16.3 points), while GLM-4.7 improves from 7.1% to 14.0% (+6.9 points). This suggests that some model families benefit more from explicit reasoning than others, possibly reflecting differences in base model capabilities or reasoning training methodology.

The breakdown by domain reveals pronounced domain specialization: GPT-5.2-high achieves 35.0% Travel Case Accuracy and 54.2% Shopping Case Accuracy — leading Travel but second in Shopping. Gemini-3-Flash-Preview shows the inverse pattern: only 5.9% Travel Case Accuracy but 51.7% Shopping Case Accuracy (the second-highest shopping score). No model leads both domains simultaneously. This domain specialization is a non-obvious finding: it suggests that the competencies required for travel planning (temporal-spatial coordination, multi-day constraint propagation) are partially distinct from those required for shopping planning (combinatorial coupon optimization, attribute matching), and that model training pipelines may optimize for one at the expense of the other.

The Fragility Gap: High Constraint Scores, Low Case Accuracy

Perhaps the most diagnostically revealing pattern in Table 2 is the systematic discrepancy between constraint-level scores and Case Accuracy — what the prior sections called the "fragility gap." In Travel Planning:

• GPT-5.2-high achieves 88.5 Commonsense Score and 83.3 Personalized Score (Composite 85.8) but only 35.0% Case Accuracy. This means the model satisfies most individual constraints on most tasks, but on 65% of tasks at least one constraint is violated — and a single violation is sufficient to fail Case Accuracy.
• Claude-4.5-Opus with thinking: 79.3 Commonsense, 70.9 Personalized (Composite 75.1), yet 22.7% Case Accuracy.
• GPT-5-high: 78.7 Commonsense, 65.9 Personalized (Composite 72.3), yet 18.9% Case Accuracy.
• Even the weaker reasoning models show this gap: o3 scores 76.5 Commonsense and 55.6 Personalized (Composite 66.1) but only 11.3% Case Accuracy.

The Commonsense Score is consistently higher than the Personalized Score across all models — suggesting that generating a physically/logically feasible plan is easier than satisfying all user-specific requirements. The average Commonsense Score across all reasoning models is approximately 63.0, while the average Personalized Score is approximately 48.7. This asymmetry is informative: models are better at avoiding temporal overlaps and staying within business hours than at remembering and enforcing every user-stated preference across a multi-day plan.

In Shopping Planning, the fragility manifests differently. Match Scores are uniformly much higher than Case Accuracy — e.g., Claude-4.5-Opus (without thinking) achieves 82.2% Match Score but only 45.8% Case Accuracy; GPT-5.2-none achieves 58.6% Match Score but 8.6% Case Accuracy. This means models typically identify most of the required products but fail to assemble the exact complete cart. The last 1-2 products (or the correct coupon configuration) are disproportionately difficult, consistent with the Global Constrained Optimization challenge: the final cart composition depends on combinatorial interactions across all items, so getting 3 out of 4 products correct does not guarantee the 4th will follow.

Travel Planning Detailed Results

Table 2 reports Travel Planning scores for each model. The key patterns:

Non-reasoning models struggle catastrophically. Of the 9 non-reasoning model configurations, 7 achieve 0.0% Case Accuracy on Travel Planning (including Qwen3-Max, Qwen-Plus, DeepSeek-V3.2, GLM-4.7, and Seed-1.8-minimal). Only Claude-4.5-Opus (6.7%) and Claude-4.5-Sonnet (1.1%) achieve non-zero Travel Case Accuracy without thinking. This is a striking result: without deliberate internal reasoning, even frontier non-reasoning models essentially cannot produce a single completely correct multi-day travel itinerary. Their Composite Scores are non-trivial (Claude-4.5-Opus: 63.1; GPT-5.2-none: 42.1), indicating they can produce partially correct plans, but the transition from "mostly correct" to "completely correct" appears to require capabilities that non-reasoning forward passes cannot provide.

Reasoning models improve substantially but remain far from saturation. GPT-5.2-high at 35.0% is the best Travel Case Accuracy, representing a large absolute gain over its non-reasoning counterpart (0.4%) but still leaving 65% of tasks unsolved. The second-best reasoning model is Claude-4.5-Opus with thinking at 22.7%, followed by GPT-5-high at 18.9% and Qwen3-Max with thinking at 13.8%. The ~13-point gap between first and second place is notably large, suggesting that GPT-5.2-high possesses planning capabilities (or was trained with planning-relevant objectives) that other reasoning models lack.

Commonsense Score vs. Personalized Score asymmetry persists across all models. The Commonsense Score is universally higher than the Personalized Score — typically by 10-20 percentage points. For example, GPT-5.2-high: 88.5 vs. 83.3 (gap: 5.2); Claude-4.5-Opus with thinking: 79.3 vs. 70.9 (gap: 8.4); o3: 76.5 vs. 55.6 (gap: 20.9). This gap is particularly large for o3, suggesting that its reasoning is better at temporal-spatial-logistical planning than at tracking user preferences across a long interaction. The paper's error analysis (Section 4.5) suggests that user preferences are sometimes forgotten or ignored during long planning chains (Pattern B1: Explicit Constraint violations), which would explain the Personalized Score deficit.

Consistency across four runs. The paper does not report run-to-run variance, which is a notable omission. For Case Accuracy — a binary metric — the averaging across 4 runs per task per model means that a reported Case Accuracy of 35.0% represents the fraction of (task, run) pairs that were perfect. If the model's performance is consistent (it either reliably solves or reliably fails the same tasks), the standard error would be low. If performance is highly variable (the model sometimes solves a task and sometimes fails it), the effective sample size would be larger but the metric would mask important reliability information. Without variance reporting, we cannot distinguish between "GPT-5.2-high solves 35% of tasks every time" and "GPT-5.2-high solves 70% of tasks half the time."

Shopping Planning Detailed Results

Table 2 reports Shopping scores separately. The key patterns:

Gemini-3-Flash-Preview shows anomalous domain specialization. It achieves 51.7% Shopping Case Accuracy — second only to GPT-5.2-high (54.2%) — despite scoring only 5.9% on Travel Case Accuracy. This 45.8-point gap between domains is the largest for any model and suggests that the model's training disproportionately emphasized the kinds of attribute-matching and combinatorial reasoning that Shopping requires, or that its architecture is better suited to the smaller information space of Shopping (171 avg. records vs. 7,708 for Travel).

Shopping Match Scores are generally high across models. Even weak non-reasoning models achieve Match Scores above 50%: GPT-5.2-none at 58.6%, DeepSeek-V3.2 without thinking at 58.3%, GLM-4.7 without thinking at 61.2%. This indicates that product identification — searching for and filtering to the right items — is relatively tractable even without deliberate reasoning. The bottleneck is not finding the products but assembling the exact correct cart (Case Accuracy), which requires resolving coupon interactions, budget constraints, and attribute dependencies across products.

The Match-Score-to-Case-Accuracy gap varies significantly by model. Claude-4.5-Opus without thinking: 82.2% Match → 45.8% Case (gap: 36.4 points). GPT-5.2-high: 84.8% Match → 54.2% Case (gap: 30.6 points). Gemini-3-Flash-Preview: 80.6% Match → 51.7% Case (gap: 28.9 points). GLM-4.7 with thinking: 72.5% Match → 27.5% Case (gap: 45.0 points). The gap size reflects how well the model handles the transition from identifying individual products to assembling the globally optimal cart. Smaller gaps (GPT-5.2-high, Gemini-3-Flash) indicate better combinatorial optimization; larger gaps (GLM-4.7, Seed-1.8-high at 36.7 points) indicate that product identification competence does not translate to cart assembly competence.

DeepSeek-V3.2 without thinking scores 10.6% Case Accuracy on Shopping (higher than its 0.0% on Travel), and this improves to 42.5% with thinking enabled. This is one of the larger absolute improvements from reasoning within a single model family (+31.9 points), suggesting that DeepSeek's thinking mode is particularly effective at the kind of structured attribute matching and constraint checking that Shopping requires.

Cost–Performance Trade-offs (Figure 3)

Figure 3 plots model performance (average Composite Score on Travel Planning) against two cost dimensions: average tool calls per task (top) and average interaction turns per task (bottom). Each model is a single data point, with reasoning models distinguished from non-reasoning models by visual markers.

Tool call volume correlates positively with performance. The top panel shows a roughly monotonic relationship: models that make more tool calls tend to achieve higher Composite Scores. GPT-5.2-high occupies the extreme upper-right corner (~224 tool calls, ~85.8 Composite Score). Claude-4.5-Opus with thinking (~72.9 tool calls, ~75.1 Composite Score) achieves competitive performance with fewer calls than some non-reasoning models. The correlation is not tight — some models achieve similar call volumes with very different scores (e.g., o4-mini and Grok-4.1-Fast reasoning both make ~90-100 calls but score ~47 vs. ~47 Composite respectively) — but the overall trend suggests that extensive information gathering is necessary for strong Travel Planning performance, consistent with the proactive information acquisition requirement.

Reasoning models occupy a better part of the trade-off curve. In both panels, reasoning models (distinguished visually) tend to achieve higher scores at comparable or lower interaction costs than non-reasoning models. Enabling thinking in Claude-4.5-Opus provides a concrete before-after comparison: Composite Score improves from 63.1 to 75.1 (+12.0 points) while tool calls decrease from 79.5 to 72.9 (-6.6 calls) and interaction turns decrease from 16.9 to 12.5 (-4.4 turns). Internal deliberation substitutes for external trial-and-error: the model can plan its queries before executing them, reducing redundant information retrieval and consolidating tool use into fewer, more targeted calls.

The parallel-sequential strategy distinction emerges clearly in the bottom panel. Interaction turns measure the number of separate model-round-trip exchanges, where multiple tool calls per turn indicate parallel execution. GPT-5.1-high (a model appearing in Figure 3 but not in Table 2 — presumably an intermediate GPT-5 variant) achieves ~25 interaction turns with reasonable performance, while GPT-5.2-high achieves ~115 interaction turns with higher performance. This ~4.6× difference in turns for a ~12.7% Composite Score improvement represents a genuine cost-performance tradeoff: the sequential-verification strategy (many turns, one or few calls per turn) yields better plans but requires more round-trips, increasing wall-clock latency. The paper explicitly notes this: "GPT-5.2-high achieves better performance (+12.7%), it requires nearly 10× more turns than GPT-5.1-high" (Section 4.3).

The trade-off is not just about total cost but about strategy. The fact that different models in the same family adopt different strategies under the same protocol suggests that the parallel-vs-sequential choice is an emergent model behavior, not a system-level configuration. This has implications for agent framework design: when building planning systems, practitioners should consider whether to expose parallelism as an explicit tool or let the model discover it. The paper's finding that the sequential strategy yields better accuracy but higher latency provides an empirical basis for this design decision.

Impact of Task Complexity (Figure 4)

Figure 4 investigates how model performance degrades as tasks become more complex. For Travel Planning, complexity is operationalized as itinerary length in days (from 2 to 7 days); for Shopping Planning, as a three-level difficulty scale (Levels 1-3) representing increasing cross-item constraint coupling. Three models are shown — Claude-4.5-Opus (with thinking), GLM-4.7 (with thinking), and Grok-4.1-Fast (reasoning) — chosen to represent distinct model families.

Travel Planning: monotonic degradation with itinerary length. All three models show declining Composite Scores as the number of days increases. Claude-4.5-Opus drops from approximately 82 at 2 days to approximately 68 at 7 days; GLM-4.7 drops from approximately 55 to approximately 35; Grok-4.1-Fast drops from approximately 58 to approximately 42. The degradation is approximately linear rather than exhibiting a sharp threshold — each additional day incrementally adds interacting constraints (more accommodations to book, more attractions to sequence, more meals to schedule, more inter-location transfers to coordinate), and models appear to accumulate errors proportionally rather than hitting a sudden "too many constraints to handle" cliff.

The paper's interpretation (Section 4.4) is that longer itineraries expand the space of interacting constraints and increase runtime, making it more likely that "small local mistakes can propagate across days and ultimately render the overall itinerary infeasible." This is precisely the global constrained optimization failure mode: the damage from a single poor decision (e.g., booking a hotel far from day 2's attractions) compounds as more days depend on that decision.

Shopping Planning: sharp decline from Level 1 to Level 3. The three-level difficulty progression is described in Section 4.4: Level 1 involves straightforward item matching, Level 2 adds price-range requirements, and Level 3 introduces coupon timing constraints that create combinatorial optimization challenges. Claude-4.5-Opus drops from approximately 60% Case Accuracy at Level 1 to approximately 45% at Level 2 to approximately 25% at Level 3. GLM-4.7 drops from approximately 45% to approximately 30% to approximately 10%. The decline is steeper than in Travel, suggesting that the transition from matching to optimization (Level 2→3) represents a qualitative jump in difficulty rather than a gradual accumulation of constraints. The coupon-timing constraints at Level 3 are the specific feature that the paper identifies as shifting "the problem from straightforward item matching to a global, joint optimization challenge" (Section 4.4).

Grok-4.1-Fast shows anomalous flat performance on Shopping. Its Case Accuracy is approximately 38% across all three difficulty levels (reading from Figure 4). This flat profile is unusual — it suggests that Grok-4.1-Fast either has a ceiling on Shopping performance that is hit at Level 1 (making further complexity invisible) or employs a strategy that is equally (in)effective regardless of coupon-timing complexity. The paper does not comment on this anomaly, but it warrants investigation in future work.

The consistent downward slope across models confirms that complexity is a genuine bottleneck, not an artifact of any single model's architecture. If only one model degraded with complexity while others remained flat, the benchmark's difficulty scaling might reflect that model's specific weaknesses. The fact that three models from different families all exhibit degradation patterns (with the exception of Grok on Shopping) suggests that the benchmark is measuring a general capability limitation, not model-specific quirks.

Ablation Studies and Robustness Checks

Since this is a benchmark paper rather than a methods paper, there are no traditional model ablations (no hyperparameters to vary, no architectural components to remove). The "ablations" are better understood as analytical dimensions the paper explores to characterize model behavior and benchmark properties.

Reasoning vs. non-reasoning within model families. Table 2 provides a natural within-family comparison for models offered in both modes: Claude-4.5-Opus (+7.6 points average accuracy), Claude-4.5-Sonnet (+8.3), Qwen3-Max (+15.9), Qwen-Plus (+9.6), DeepSeek-V3.2 (+16.3), GLM-4.7 (+6.9), GPT-5.2 (+40.1). The gains are universally positive but vary dramatically in magnitude — from +6.9 (GLM-4.7, a modest but real improvement) to +40.1 (GPT-5.2, a transformation from essentially non-functional to benchmark-leading). This wide range implies that reasoning capability is not binary but exists on a spectrum, and that some models' "thinking" modes are substantially more effective at planning than others.

Domain specialization patterns. The paper does not present this as a formal ablation, but the per-domain breakdowns in Table 2 reveal systematic asymmetries. GPT-5.2-high: Travel 35.0% vs. Shopping 54.2% (gap: +19.2 Shopping). Gemini-3-Flash-Preview: Travel 5.9% vs. Shopping 51.7% (gap: +45.8 Shopping). Claude-4.5-Opus with thinking: Travel 22.7% vs. Shopping 45.0% (gap: +22.3 Shopping). Every model scores higher on Shopping Case Accuracy than on Travel Case Accuracy, and the gap ranges from 5.8 points (o4-mini: 3.0% Travel, 21.7% Shopping, gap +18.7) to 45.8 points (Gemini-3-Flash-Preview). This universal asymmetry confirms that Shopping Planning is structurally easier than Travel Planning — likely due to the smaller information space (171 vs. 7,708 avg. records), the structured JSON output format (eliminating the natural-language parsing challenge), and the absence of temporal-spatial coordination constraints.

Error pattern distribution (Figure 5) as a "failure ablation." The error taxonomy in Section 4.5, applied to 140 failed trajectories from Claude-4.5-Opus with thinking (80 Travel, 60 Shopping), decomposes agent failures into the three competency dimensions. This analysis functions as an ablation of what goes wrong when agents fail, revealing:

• Pattern A (Information Acquisition): A1: Insufficient Search appears in approximately 70 of 140 annotated failures in Travel (reading from Figure 5), making it the most common non-optimization failure. This confirms that even Claude-4.5-Opus with thinking — the second-best model overall — sometimes fails to query critical information (transit times, attraction details). A2: Tool Misuse and A3: Fact Displacement appear at lower frequencies (~15-20 each in Travel, ~5-10 in Shopping), suggesting that when agents do query, they generally use tools correctly but occasionally misstate retrieved facts.

• Pattern B (Local Reasoning): B2: Implicit Constraint violations dominate over B1: Explicit Constraint violations — 86 vs. approximately 40 in Travel, 21 vs. approximately 10 in Shopping. This asymmetry is one of the paper's most actionable findings: agents are better at respecting stated user preferences (B1) than at detecting and reasoning about constraints that emerge from the environment (B2) such as limited flight seat availability or attraction closure days. This suggests a concrete direction for improvement: training agents to actively verify implicit constraints rather than assuming environment states match expectations.

• Pattern C (Global Optimization): 101 failures in Travel and 52 in Shopping, dwarfing all other categories. This is the central empirical finding of the error analysis and the strongest evidence for the paper's claim that global constrained optimization is the primary bottleneck. The specific failure subtypes (temporal overlaps, budget violations, repetitive activity selection, logical discontinuities between days) are all manifestations of the same underlying deficit: the agent cannot track how decisions interact across the plan horizon.

Difficulty-level stratification (Figure 4) as a benchmark property validation. The fact that all three tested models show declining performance with increasing complexity validates that the benchmark's difficulty levels are meaningful — they are not arbitrary labels but correspond to genuine increases in planning challenge. If models performed equally at all difficulty levels, the levels would be providing no useful signal. The monotonic degradation (with the Grok-on-Shopping exception) confirms that the complexity scaling is well-calibrated.

Missing ablations and analyses. Several analyses that would strengthen confidence in the results are absent: (a) variance across the four runs per task is not reported, making it impossible to assess whether model rankings are statistically reliable or dominated by noise; (b) per-language breakdowns for Travel Planning (Chinese vs. English) are not provided, hiding any language-dependent performance effects; (c) the relationship between model size and performance is not analyzed — the paper evaluates many models but does not control for parameter count, making it unclear whether GPT-5.2-high's dominance reflects better architecture/training or simply larger scale; (d) no analysis of whether failures are systematic (the same tasks fail across all models) or idiosyncratic (different models fail different tasks), which would reveal whether some tasks are inherently harder or whether model-specific weaknesses dominate; (e) the impact of the 400-call budget limit is unexplored — did any models approach or hit the limit, and did performance correlate with proximity to the limit?

Critical Assessment

Claim: Even frontier LLM agents struggle with long-horizon planning, with the best model achieving only 35.0% Travel Case Accuracy and 44.6% average accuracy across domains. This claim is strongly supported by Table 2. The numbers are unambiguous and span 16 model configurations from 8 families, making it unlikely that the finding is model-specific. However, the claim should be qualified by noting that Case Accuracy is an extremely strict metric (binary, requiring perfection on all sub-constraints), and that models achieve substantially higher Composite Scores (GPT-5.2-high: 85.8 Travel Composite) indicating partial competence. The 35.0% figure represents "produces a completely correct plan" not "produces a useful plan." A plan with one minor budget miscalculation but otherwise correct might still be practically useful while scoring 0% Case Accuracy. The benchmark's strictness is a deliberate design choice that provides clear signal for research progress, but the absolute numbers should not be interpreted as "models solve only 35% of travel planning problems" in a practical sense.

Claim: Global constrained optimization is the dominant failure mode, with 101 of 140 annotated travel failures attributed to Pattern C. This claim is supported by the error analysis but depends critically on the annotation methodology, which has limitations. The analysis covers only Claude-4.5-Opus with thinking — the second-best model. Failure distributions may differ for other models (weaker models might fail more on information acquisition, stronger models more on optimization). The annotation was done by the paper's authors rather than independent raters, and no inter-annotator agreement metrics are reported. A single trajectory can exhibit multiple failure patterns (the paper notes "a single failed trajectory may result from a combination of issues"), so the counts are not mutually exclusive. The 101 figure might partially reflect the annotation taxonomy's coarseness — "global optimization failure" is a broad category that may capture heterogeneous errors. A finer-grained sub-categorization of Pattern C would strengthen the claim.

Claim: Reasoning models consistently outperform non-reasoning counterparts and achieve better cost-performance trade-offs. This claim is supported by Table 2 and Figure 3, but with an important caveat: the paper does not control for inference cost. Reasoning models are more expensive per token and per call than non-reasoning models (they generate internal reasoning traces that consume compute but are not counted in tool-call or interaction-turn metrics). Figure 3 measures cost as tool calls and interaction turns, which are external metrics. A complete cost accounting would include total tokens processed (internal + external), which the paper does not provide. Claude-4.5-Opus with thinking makes fewer tool calls than without thinking (72.9 vs. 79.5), but each call likely costs more due to reasoning overhead. The claim that reasoning models achieve "better cost-performance trade-offs" is true with respect to the benchmark-specific cost metrics (tool calls, turns) but may not hold when total inference cost is considered. The paper implicitly acknowledges this by not making total-cost claims.

Claim: The parallel-sequential strategy distinction represents a genuine cost-performance tradeoff. This is a well-supported observational finding from Figure 3, but it is correlational rather than causal. The paper observes that GPT-5.1-high uses parallel execution and achieves lower scores with fewer turns, while GPT-5.2-high uses sequential execution and achieves higher scores with more turns. This demonstrates an association between strategy and performance but does not establish that the strategy causes the performance difference. GPT-5.2-high may be better at planning for reasons unrelated to its sequential strategy, and the strategy may be a consequence rather than a cause of its planning ability. A controlled experiment that forces the same model to use parallel vs. sequential strategies would be needed to establish causality. Additionally, the paper only identifies this pattern within the GPT-5 family — whether it generalizes across other model families is unexplored.

Genuine weakness: The 4-run averaging without variance reporting. One of the most significant methodological limitations is the absence of any variance metric. With only 4 runs per task per model and a binary Case Accuracy metric, the effective sample size for comparing models is modest. If performance is highly variable (model sometimes solves a task, sometimes doesn't), the difference between 35.0% and 22.7% Case Accuracy may not be statistically significant. If performance is stable (model consistently solves the same subset of tasks), the effective sample size is the number of tasks (120 per domain), and the differences are more reliable. The paper provides no information to distinguish these scenarios. Reporting standard errors or confidence intervals on Case Accuracy, or providing per-task agreement rates across runs, would substantially strengthen the results.

Genuine weakness: Single annotator error analysis on a single model. The error pattern analysis (Section 4.5, Figure 5) is valuable but limited by covering only one model (Claude-4.5-Opus with thinking) and not reporting inter-annotator reliability. The findings about the dominance of Pattern C might not replicate to other models — for example, weaker models might fail far more on Pattern A (information acquisition) before ever reaching the optimization stage. The analysis also uses model-generated trajectories in one language (presumably English, given that the Shopping task is English-only), which may not capture failure patterns from Chinese Travel runs.

Genuine weakness: No accounting for the parsing step's contribution to Travel errors. Travel Planning evaluation requires parsing natural-language itineraries into structured format using Qwen-Plus-2507. Errors in this parsing step (misidentified activities, incorrect time extraction, wrong cost parsing) would manifest as evaluation failures that are attributed to the agent being evaluated, not to the parsing model. The paper does not report parsing accuracy, inter-parser agreement, or any analysis of how many "agent failures" are actually parsing failures. Given that Case Accuracy is binary and a single parsing error would drop a task to 0 even if the agent's plan was perfect, this introduces an unquantified source of measurement error, particularly for models that produce less structured or more idiosyncratic itinerary formats. The choice of Qwen-Plus-2507 (an Alibaba model, same company as several evaluated models) also raises a potential fairness concern, though the paper does not discuss whether this systematically advantages or disadvantages any model.

Missing experiment: Fixed-compute-budget comparison. The paper gives all models up to 400 tool calls and reports how many they actually use. This makes the evaluation a measure of peak achievable performance rather than efficiency at a fixed budget. A complementary evaluation that caps models at, say, 50, 100, or 200 tool calls would reveal whether some models achieve comparable performance with dramatically less information gathering (i.e., are more efficient planners) and whether the model ranking changes under resource constraints. The current protocol favors models that make extensive queries (GPT-5.2-high at ~224 calls) and may disadvantage models that adopt more parsimonious strategies.

Missing experiment: Oracle information baseline. A revealing ablation would be to provide models with all relevant environment state upfront (the equivalent of a full database dump) and measure whether they can still construct correct plans when information acquisition is removed as a challenge. This would decompose the overall failure rate into "fails because of incomplete information gathering" vs. "fails because of planning/optimization limitations even with complete information." The current results conflate these two failure sources.

Conditional nature of the claims. The paper's central claims — that DeepPlanning reveals planning fragility and that global optimization is the bottleneck — hold for the specific task distribution, model set, and evaluation protocol used. Whether these findings generalize to other planning domains (financial planning, project management, logistics) or to future models with different architectures is unknown. The paper appropriately does not claim universality; it claims that current models exhibit these patterns on these tasks. The value of the benchmark will be determined by whether it continues to provide discriminative signal as models improve — if next year's models achieve 90% Case Accuracy, the benchmark will have served its purpose as a milestone rather than a permanent challenge.

6. Limitations and Trade-offs

6.1 The Difficulty Estimation Cost Is Unaccounted for in the Headline Numbers

The assumption or constraint. The compute-optimal scaling framework in this paper critically depends on estimating each prompt's difficulty before allocating the inference budget. The method used — sampling 2048 solutions per question and computing either the ground-truth pass@1 rate (oracle) or the PRM's average final-answer score (predicted) — is extraordinarily expensive. The authors explicitly acknowledge this gap in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

The consequence. The $4\times$ efficiency gains reported over best-of-N (Figures 4 and 8) are computed after difficulty is known, without amortizing the cost of learning it. In a realistic deployment, the total cost would be difficulty estimation + strategy execution. Since the estimation cost (2048 samples per question) exceeds the largest test-time budgets studied (256–512 generations) by a factor of 4–8× for the smallest budgets and is comparable even at the largest budgets, the $4\times$ figure should be understood as an upper bound on achievable efficiency rather than a realized deployment gain. For a prompt that receives only 16 generations of test-time compute under the optimal strategy, the 2048-sample difficulty estimation overhead represents an additional $\sim 128\times$ cost that completely dominates the budget — the total cost would be $2048 + 16 = 2064$ generations, making the "efficient" strategy far more expensive than simply running best-of-N with 256 generations ($256$ total) and achieving similar accuracy.

What evidence exists in the paper. The difficulty estimation cost is described in Section 3.2 but never factored into any Table or Figure. Figures 4 and 8 show compute-optimal curves that begin at low generation budgets (e.g., 4, 8, 16 generations) with no indication of the amortized difficulty cost. The statement "our experiments do not account for this cost largely for simplicity" (Section 3.2) confirms the gap. No experiment varies the number of difficulty-estimation samples to determine the cost–accuracy tradeoff for the estimation step itself (e.g., does 512 samples suffice? 256?).

Mitigation status. The paper acknowledges the limitation explicitly and frames it as an exploration–exploitation tradeoff for future work, stating:

"this additional computation cost could be viewed as an exploration investment whose cost could be amortized by deploying the same solution many times"

However, this amortization argument only works for prompts that are solved repeatedly (e.g., a production API that serves the same question many times). For one-off queries — the typical deployment scenario — the cost cannot be amortized. The paper does not develop or evaluate any cheaper difficulty estimation method (e.g., a lightweight classifier trained to predict difficulty from prompt text alone, or an adaptive scheme that estimates difficulty from the first few samples during problem-solving). Section 8 flags "pretraining or finetuning models to directly predict difficulty of a question" as future work, but no such model is evaluated.

6.2 Hard Problems Remain Essentially Unsolved Regardless of Compute Budget

The assumption or constraint. The paper's approach — whether using PRM-guided search or iterative revisions — assumes that correct solutions exist in the base model's output distribution at a non-trivial rate. When pass@1 is near zero, no amount of test-time compute amplification can produce a correct answer, because there are no correct candidates to find or refine.

The consequence. Across all methods — search, revisions, and their compute-optimal combinations — the hardest difficulty bin (bin 5) shows near-zero improvement regardless of compute budget. In Figure 3 (right), bin 5 accuracy hovers at 1–3% for all methods and budgets, with beam search and best-of-N equally ineffective. In Figure 7 (right), the sequential-to-parallel ratio has no effect on bin 5 accuracy (roughly 2–3% for all ratios). In the FLOPs-matched comparison (Figure 9), the bin 5 scaling line is essentially flat near 0–5% — far below the $\sim 14\times$ larger model's performance — for all values of $R$. This means test-time compute provides exactly zero benefit on problems that exceed the base model's fundamental capability range. For such problems, pretraining a larger model is the only viable path.

This is acknowledged in Section 7:

"test-time compute is powerful when problems are within the base model's reach... but it cannot compensate for fundamental capability gaps that larger pretraining would address"

What evidence exists in the paper. Figure 3 (right, bin 5), Figure 7 (right, bin 5), and Figure 9 (bin 5 scaling curves) all show the same pattern: flat performance near baseline regardless of method or budget. The FLOPs-matched comparison in Figure 9 shows hard-problem disadvantages of -52.9% relative for PRM search at $R \gg 1$ and -37.2% for revisions at the same $R$ (Figure 1 bar charts). Section 7 explicitly notes the boundary condition.

Mitigation status. The paper is transparent about this limitation but does not attempt to address it. This is appropriate given the paper's framing — the claim is that test-time compute amplifies existing capability, not that it creates capability from nothing. However, practitioners should understand that the approach offers no path forward for genuinely novel or out-of-distribution reasoning that exceeds the base model's training distribution. The paper does not investigate whether combining test-time compute with retrieval-augmented generation, few-shot examples, or task decomposition could push the capability boundary outward for hard problems.

6.3 Revisions and Search Are Studied Independently, Never Combined

The assumption or constraint. The paper studies two complementary axes — PRM search (Section 5) and iterative revisions (Section 6) — as separate, independent mechanisms for improving test-time performance. The compute-optimal policy selects between search algorithms (best-of-N, beam search, lookahead search) and between sequential/parallel revision ratios, but never combines the two approaches into a single integrated system.

The consequence. The paper's results represent a lower bound on what a fully integrated system could achieve. The two mechanisms have complementary strengths: revisions improve the proposal distribution (generating higher-quality candidates by conditioning on previous errors), while PRM search improves candidate selection (finding the best among generated candidates by scoring intermediate steps). A combined system — for example, using the revision model as the proposal distribution within beam search, or using the PRM to guide which revision branches to pursue — could yield gains beyond either method alone. The paper's conclusion that compute-optimal scaling achieves $4\times$ better efficiency than best-of-N is measured against a baseline that itself could be improved by combining the two axes. This gap is acknowledged explicitly in Section 8:

"we did not experiment with PRM tree-search techniques in combination with revisions"

What evidence exists in the paper. The search results (Section 5, Figures 3–4) and revision results (Section 6, Figures 6–8) are presented in separate sections with no cross-over experiments. The FLOPs-matched comparison (Figure 9) shows search and revisions as separate panels, never as a combined strategy. The compute-optimal curves in Figures 4 and 8 select between variants within each axis (different search algorithms OR different sequential/parallel ratios) but never select a strategy that combines PRM tree-search with revision-model candidate generation.

Mitigation status. The paper identifies this as "a natural next step" in Section 8 but does not implement or evaluate any combined approach. This is a significant omission because the difficulty-dependent patterns suggest a natural integration: easy problems benefit most from sequential revisions (local refinement), medium problems benefit most from PRM-guided search (global exploration), and hard problems benefit from neither. An adaptive system that deployed revisions on easy problems and PRM search on medium problems — potentially using the same underlying models — would be a straightforward extension of the existing compute-optimal framework. The fact that such a system is not evaluated leaves open the question of whether the two axes are additive (their benefits sum) or partially redundant (they address overlapping failure modes).

6.4 The $14\times$ Larger Model Baseline Is Not Compute-Optimally Trained and Uses No Test-Time Compute of Its Own

The assumption or constraint. The FLOPs-matched comparison in Section 7 compares PaLM 2-S* augmented with compute-optimal test-time strategies against a model with approximately $14\times$ more parameters. The larger model fixes training data and scales only parameters (following the LLaMA paradigm rather than Chinchilla-optimal scaling, where both data and parameters increase), and is evaluated with greedy decoding only — no majority voting, no best-of-N, no search.

The authors acknowledge this departure from compute-optimal pretraining in Section 7:

"We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work."

The consequence. The comparison systematically favors test-time compute in two ways. First, a Chinchilla-optimal model trained with $14\times$ more total FLOPs (scaling both parameters and data equally) would likely outperform a parameter-only-scaled model trained on the same data, making the pretraining baseline weaker than it could be. Second, giving the larger model even a modest test-time compute budget (say, best-of-8 with majority voting) would create a much stronger baseline — the paper is comparing an optimized inference strategy on a small model against an unoptimized strategy on a large model, which conflates the effect of test-time compute optimization with the effect of simply using any test-time compute.

The reported advantages of test-time compute over pretraining — e.g., +27.8% on easy questions at $R \ll 1$ (Figure 1 bar chart) — may shrink or reverse against a properly compute-optimal larger model with its own test-time compute budget. The $4\times$ efficiency claim (matching the $\sim 14\times$ larger model's performance with $4\times$ less compute) is measured against a baseline that may understate the larger model's capabilities.

What evidence exists in the paper. The FLOP accounting and baseline description are in Section 7. Figure 9 shows the comparison, with the larger model's performance as horizontal stars. The paper explicitly notes the parameter-only scaling choice and frames the Chinchilla-optimal comparison as future work. No experiment gives the larger model any test-time compute budget.

Mitigation status. The paper is transparent about the choice but does not run the Chinchilla-optimal comparison or the larger-model-with-test-time-compute ablation. These are noted as future work (Section 7 and Section 8), but their absence means the paper's central claim about the pretraining–inference tradeoff — "a smaller model with additional test-time compute can outperform a $\sim 14\times$ larger model" — should be understood as holding for a specific, arguably weak, pretraining baseline. A practitioner deciding whether to invest in larger pretraining runs versus smarter inference strategies would need the stronger baselines to make an informed decision.

6.5 No Accounting for Latency or Wall-Clock Time in the "Compute-Optimal" Framework

The assumption or constraint. The paper measures test-time compute in "generations" (number of complete solutions sampled), which is a reasonable proxy for total FLOPs but ignores latency — the wall-clock time required to produce a final answer. Sequential revisions are inherently serial: each revision depends on the previous one, and a chain of $K$ revisions takes approximately $K\times$ the wall-clock time of generating a single solution. Parallel best-of-N sampling can be executed simultaneously given sufficient hardware, producing $N$ solutions in approximately the same wall-clock time as generating one.

The consequence. The compute-optimal policies discovered in Sections 5 and 6 frequently favor sequential strategies, particularly on easy problems where sequential revisions dominate (Figure 7, right) and on medium problems where beam search with $M=4$ outperforms best-of-N (Figure 3, right). A strategy that allocates 128 generations as $64$ sequential $\times 2$ parallel takes roughly $64\times$ longer wall-clock time than a pure parallel strategy of 128 simultaneous samples. For latency-sensitive applications — interactive assistants, real-time decision-making, user-facing chatbots — the sequential-heavy strategies favored by the compute-optimal policy may be practically unusable regardless of their accuracy advantages.

Similarly, the observation (Section 4.3) that GPT-5.2-high uses $\sim 10\times$ more interaction turns than GPT-5.1-high to achieve a 12.7% Composite Score improvement reflects the same tradeoff: sequential verification improves accuracy but dramatically increases latency. The paper's cost model does not distinguish between "128 parallel generations completed in 2 seconds" and "128 sequential revisions taking 128 seconds" — both are recorded as a budget of 128 generations.

What evidence exists in the paper. Figure 3 (bottom panel) shows the sequential–parallel distinction in terms of interaction turns per task for Travel Planning, and Section 4.3 explicitly discusses the tradeoff. Figure 7 shows that fully sequential revisions are optimal at low-to-moderate budgets, and Figure 6 (left) shows that revision chains extend to 64 steps with gradually improving pass@1 — evidence that the optimal strategy involves deep sequential chains. Section 6.1 mentions the 38% correct-to-incorrect reversion rate and the need for chain-level selection, which compounds the latency penalty (you must generate the whole chain before selecting). However, the paper does not analyze or report wall-clock times, does not include a latency term in the optimization objective, and does not discuss the practical implications of deep sequential strategies for latency-sensitive deployments.

Mitigation status. The paper does not address this tradeoff. The compute-optimal objective in Equation 1 maximizes expected correctness given a generation budget $N$; there is no term for time-to-answer or any constraint on the depth of sequential chains. Section 8 does not mention latency as a future work direction. A practitioner implementing these strategies would need to separately consider whether the accuracy gains from deep sequential revisions justify the latency cost in their specific deployment context. The framework provides accuracy–generation-budget tradeoff curves but not accuracy–latency curves, which are what matter for interactive applications.

6.6 Single Benchmark, Single Model Family: Generalization Is Unverified

The assumption or constraint. All experiments use the MATH benchmark (500 test questions) with PaLM 2-S* (Codey) as the base model. The paper states in Section 4 that the authors "believe this model is representative of the capabilities of many contemporary LLMs," but this claim is unverified — no experiments are conducted with any other model family, architecture, or scale.

The consequence. Several aspects of the findings could be model-specific or benchmark-specific:

• PRM quality and over-optimization behavior depend on the base model's output distribution. A model with different calibration properties, different error patterns, or different solution diversity might exhibit different difficulty-dependent scaling curves, different optimal strategies per difficulty bin, and different over-optimization thresholds. The finding that beam search degrades easy-problem performance (Figure 3, right) — central to the compute-optimal policy — might not replicate for a base model that produces less PRM-exploitable outputs.

• Revision model effectiveness depends on the base model's in-context learning and self-correction capabilities. The paper's revision model is fine-tuned from PaLM 2-S* using a specific training procedure (edit-distance-based incorrect-correct pairing, Section 6.1). Whether this procedure works for other model families, or whether the 38% correct-to-incorrect reversion rate is typical or PaLM-specific, is unknown.

• MATH consists exclusively of competition-level math problems requiring symbolic reasoning. The difficulty-dependent patterns — beam search helping medium problems but hurting easy ones, sequential revisions helping easy problems but needing parallel exploration for hard ones — may not generalize to other reasoning domains (code generation, logical reasoning, scientific QA, planning). Math problems have a particular structure (deterministic correctness, single numeric or expression answers, step-by-step derivations) that may make verifier training and revision learning more effective than on more open-ended tasks.

• Test set of 500 questions, split into 5 difficulty quintiles of $\sim 100$ each, then further split by two-fold cross-validation, means the compute-optimal policy is selected based on $\sim 50$ questions per fold per bin. The paper does not report confidence intervals on the compute-optimal scaling curves (Figures 4 and 8), making it impossible to assess whether the observed strategy selections are robust to resampling or whether they reflect noise in small-sample estimation.

What evidence exists in the paper. All results in Sections 5–7 use MATH and PaLM 2-S*. Section 4 describes the choice as motivated by the model being "representative." No cross-model or cross-benchmark experiments are conducted or discussed as future work.

Mitigation status. The paper does not attempt to address this limitation — no other benchmarks are used, no other base models are evaluated. Section 8 does not flag cross-model or cross-domain generalization as a direction for future work, which is a notable omission given how much of the paper's contribution depends on the empirical patterns (difficulty-dependence, over-optimization, revision effectiveness) being general properties rather than PaLM-specific artifacts. A practitioner considering adopting the compute-optimal framework would need to verify that the key patterns — particularly the difficulty-dependent strategy rankings — replicate on their specific model and task domain, as the paper provides no evidence of transfer.

7. Implications and Future Directions

How This Work Changes the Landscape

DeepPlanning represents a diagnostic reframing rather than a paradigm shift. It does not introduce new model architectures, training objectives, or algorithmic advances. Instead, it changes what the field means by "an agent that can plan" — and, more importantly, it provides concrete evidence that current LLM agents fall dramatically short of that standard.

The conceptual shift is from evaluating planning-relevant sub-skills in isolation to evaluating the integration of those sub-skills into globally coherent plans under interacting constraints. Prior benchmarks conflated tool-use competence with planning competence. An agent that correctly calls query_flight_info with the right parameters, filters hotels by star rating, and checks restaurant opening hours can achieve high scores on existing tool-use and instruction-following benchmarks while producing an itinerary where the flight lands after the hotel check-in closes, the hotel is 90 minutes from the first attraction, and the total cost exceeds the budget. DeepPlanning exposes this conflation by making the integration itself the evaluation target.

The paper resolves a latent tension in the literature that has been difficult to articulate. On one side, benchmarks like WebArena (Zhou et al., 2024) and τ-Bench (Yao et al., 2024) show that agents can execute long sequences of tool calls to accomplish complex goals — suggesting planning competence is emerging. On the other side, classical planning benchmarks like PlanBench (Valmeekam et al., 2023) show that LLMs remain brittle planners even on simple, abstract domains — suggesting fundamental planning limitations persist. DeepPlanning's results reconcile these seemingly contradictory findings: agents succeed at the mechanics of long-horizon task execution (querying, filtering, assembling information) but fail at the integration that converts individually correct actions into globally feasible plans. The high Composite Scores (GPT-5.2-high at 85.8 Travel Composite) alongside low Case Accuracy (35.0%) are the empirical signature of this distinction — agents are competent at the sub-tasks that existing benchmarks measure, and incompetent at the holistic optimization that DeepPlanning uniquely demands.

The research direction attractiveness shifts implied by this work are substantial:

• More attractive: Research on explicit constraint tracking and propagation mechanisms becomes empirically motivated. The finding that 101 of 140 annotated travel failures are global optimization breakdowns (Figure 5) provides a clear target: architectural or algorithmic improvements that help agents maintain global consistency across long decision chains. This includes techniques like explicit budget trackers, temporal constraint solvers, backtracking mechanisms triggered by constraint violations, and structured working memory that persists across interaction turns. Prior to DeepPlanning, a researcher proposing such mechanisms would need to argue that current agents are bad at planning. Now they can point to a specific, quantified failure mode and a benchmark that measures it.

• More attractive: Research on information acquisition strategy becomes a distinct sub-problem. The paper's finding that A1 (insufficient search) is the most common non-optimization failure — agents simply forget to query critical information — suggests that knowing what to query is a bottleneck separable from reasoning about queried information. This opens space for work on query planning, information-theoretic active learning at inference time, and meta-cognitive mechanisms that assess whether sufficient information has been gathered before committing to a plan.

• Less attractive (or at least, revealed as incomplete): Pure scaling of model size or reasoning budgets without architectural changes. The paper's Figure 4 shows that even the strongest reasoning models (Claude-4.5-Opus with thinking) degrade substantially as task complexity increases — from ~82 Composite Score at 2 days to ~68 at 7 days. This degradation is approximately linear with additional days, suggesting that more parameters or more thinking tokens would improve the intercept but not necessarily change the slope. The fundamental limitation appears to be architectural (inability to propagate constraints across long decision chains) rather than capacity-limited, making pure scaling an inefficient path to improvement.

• Less attractive: Research that evaluates agents primarily on per-step or per-subtask metrics without measuring global coherence. DeepPlanning's results implicitly argue that such evaluations are measuring the wrong thing for long-horizon planning tasks — high step-level scores mask catastrophic global failures.

The benchmark also shifts practitioner expectations for what constitutes a "planning-capable" agent. Before DeepPlanning, an agent that achieved 85% on a tool-use benchmark might reasonably be deployed for travel planning tasks. After DeepPlanning, the same agent would need to demonstrate that its 85% tool-use competence translates to plans that are actually executable — not just plans whose individual pieces look correct. The bar has been raised from "can the agent use the right tools?" to "can the agent produce a plan that survives 21 automated feasibility checks?"

Follow-Up Research This Work Enables

Architectural support for global constraint tracking during long-horizon planning. The paper's central empirical finding — that global optimization failures dominate even in strong reasoning models — points to a specific architectural gap: current LLM agents lack mechanisms for explicitly propagating constraints across sequential decisions. A concrete follow-up would instrument an agent with an explicit constraint state: a structured representation of remaining budget, committed time blocks, geographic location, and unsatisfied user requirements that is updated after each tool call and presented alongside the conversation history. The research question is whether making constraints explicit and persistent reduces Pattern C failures (Figure 5) compared to the baseline where constraints are tracked only implicitly in the model's context window. A strong experiment would compare Claude-4.5-Opus with thinking (the second-best model, achieving 22.7% Travel Case Accuracy) against the same model augmented with explicit constraint tracking, measuring whether Case Accuracy improves and whether the Pattern C failure count decreases in a replication of the Section 4.5 error analysis. The null result — explicit constraints don't help — would be equally informative, suggesting that the bottleneck is not constraint representation but something deeper about how LLMs search the space of plans.

Difficulty-adaptive allocation of information-gathering budget. The paper shows that Travel Planning task complexity varies with itinerary length (Figure 4), but all models are evaluated under a uniform 400-call interaction budget. This creates an inefficiency: a 2-day itinerary almost certainly requires less information gathering than a 7-day itinerary, yet models are allocated the same maximum budget. A natural follow-up would investigate whether agents can self-regulate their information-gathering intensity based on task complexity — stopping queries when they have sufficient information rather than continuing to query until they hit a budget limit or exhaust the database. The experiment would instrument models with a submit_plan termination action (rather than having them produce a final answer only when they decide to stop calling tools) and measure: (a) whether models stop earlier on simpler tasks, (b) the relationship between tool-call count and Case Accuracy stratified by task length, and (c) whether models that query more aggressively on long tasks outperform those that query uniformly. The current results (Figure 3) show GPT-5.2-high makes ~224 calls and achieves the best performance, but this is an average across all task lengths. If the model is making ~224 calls on 2-day tasks that only need ~50, it is wasting compute; if it's making ~224 calls on 7-day tasks that need ~300, it's under-querying. Difficulty-adaptive query budgets could improve the cost-performance frontier beyond what any fixed-budget strategy achieves.

Combining tool-use verification with plan-level verification in a two-stage evaluation loop. The current DeepPlanning evaluation is offline: agents produce a plan, and then the plan is checked against 21 criteria. An agent that could self-verify its plan before submission — running its own internal version of the Commonsense Score checkpoints — might catch global optimization failures before finalizing. The research question is whether LLMs can be prompted or fine-tuned to serve as effective verifiers of their own plans, and whether verification catches different errors than those caught by the reasoning process that produced the plan. The experiment would take a model's generated plan, provide it with a verification prompt listing the 8 Commonsense Score dimensions (Table 7), and ask it to identify violations. The key metric is: what fraction of Pattern C failures (global optimization errors) does the verification step detect? If the verification step catches errors that the planning step missed, this suggests a two-stage generate-then-verify pipeline could substantially improve Case Accuracy. If the verification step misses the same errors (because the model has the same blind spots in verification as in generation), this would reveal a fundamental limitation of self-verification for planning — consistent with Stechly et al. (2025)'s finding that LLMs struggle with self-verification on planning tasks, but tested in a substantially more complex and realistic domain.

Cross-domain transfer of planning strategies. The paper observes pronounced domain specialization — Gemini-3-Flash-Preview achieves 51.7% Shopping Case Accuracy but only 5.9% Travel Case Accuracy (Table 2) — suggesting that planning competence does not transfer automatically between structurally different optimization problems. A controlled study of transfer would fine-tune a base model on Travel Planning trajectories (perhaps using the successful plans from GPT-5.2-high as training data) and measure whether Travel Planning improvements transfer to Shopping Planning, and vice versa. The research questions are: (a) do the competencies of proactive information acquisition, local constrained reasoning, and global constrained optimization transfer across domains, or are they domain-specific? (b) if transfer occurs, which competency transfers most readily? The pattern of error distributions (Figure 5, comparing Travel and Shopping failure patterns) suggests that global optimization failures are common to both domains (101 in Travel, 52 in Shopping) while information acquisition failures are more domain-specific (A1 appears ~70 times in Travel vs. ~25 in Shopping), predicting that optimization skills might transfer while information-gathering strategies might not. A null result — zero transfer — would suggest that planning capability must be acquired separately for each domain, making the challenge of building general-purpose planning agents substantially harder.

Human baseline and human–agent gap quantification. The paper evaluates only LLM agents against ground-truth solutions. A critical missing baseline is human performance on the same tasks. How long does it take a competent human to solve a 5-day Travel Planning task with access to the same tools? What error patterns do humans exhibit, and how do they differ from LLM error patterns? The experiment would recruit human participants (perhaps travel agents, or crowdworkers with planning experience) and measure their Case Accuracy, Composite Scores, time-to-completion, and tool-call patterns on a sample of DeepPlanning tasks. The comparison would reveal whether the 35.0% Case Accuracy ceiling represents an AI-specific limitation or a genuinely hard problem. If humans achieve 95% Case Accuracy, the 35% ceiling is clearly an AI capability gap. If humans achieve 60%, DeepPlanning is simply a very difficult benchmark and the AI numbers are less alarming. The error pattern comparison would be particularly revealing: do humans also struggle with global optimization (Pattern C), or do they make different kinds of errors? If humans primarily fail at information acquisition (forgetting to query a specific flight) but rarely fail at global optimization, that would strengthen the paper's claim that global constraint integration is the specific AI deficit. The human baseline is the most important missing experiment for contextualizing the paper's stark headline numbers.

Stress-testing the reverse-generation methodology's uniqueness guarantees. The paper's construction methodology (Section 3.2) claims to produce tasks with "exactly one optimal solution" through database adjustment after constraint injection. A methodological follow-up would stress-test this claim: for a sample of tasks, exhaustively enumerate all possible plans (or, for Shopping, all possible cart combinations) that satisfy the explicit constraints and verify that only the ground-truth solution passes. The research question is whether the reverse-generation process actually eliminates all alternative optima, or whether there exist valid solutions that the construction process missed. If alternative solutions exist, the Case Accuracy metric — which requires exact match with the ground truth — may be penalizing agents that found valid but unintended solutions, artificially depressing scores. The experiment would also reveal whether the solution uniqueness property degrades with task complexity: do 7-day itineraries have more near-miss alternative solutions than 2-day itineraries? If so, longer tasks are both harder to solve AND have stricter evaluation, compounding the difficulty signal.

Practical Applications and Downstream Use Cases

Agent capability certification for high-stakes planning deployments. DeepPlanning provides a concrete, reproducible evaluation that organizations can use to qualify LLM agents for deployment in domains where planning failures have material consequences — travel booking platforms, logistics coordination, financial planning, and supply chain management. Rather than relying on proprietary or ad-hoc evaluations, a company building an AI travel assistant could require that any candidate model achieves a minimum Travel Case Accuracy on DeepPlanning before deployment. The 35.0% ceiling from GPT-5.2-high (Table 2) provides a current upper bound; a deployment threshold might be set at, say, 50% Case Accuracy — a bar that no current model meets, implying that fully autonomous travel planning remains unsafe for production. The benchmark's rule-based evaluation (avoiding LLM judges that could be gamed or would drift with model updates) makes it suitable for standardized certification. The bilingual Travel evaluation (Chinese and English) also supports certification across languages, which matters for global deployments.

Guided development of planning-specific fine-tuning datasets. The error taxonomy in Figure 5 provides a failure-mode heatmap that can directly inform data collection for fine-tuning. The finding that Pattern C (global optimization failures) dominates — 101 of 140 annotated travel failures — suggests that fine-tuning data should emphasize examples of constraint propagation and global feasibility checking, not just correct individual tool calls. A practitioner could: (1) run their target model on DeepPlanning, (2) collect trajectories where the model fails (particularly Pattern C failures), (3) construct training examples that demonstrate the resolution of those specific failure patterns (e.g., showing how checking the total budget after each itinerary addition catches an overrun early), and (4) fine-tune on this targeted dataset. The benchmark thus serves double duty as both an evaluation instrument and a diagnostic tool for generating training data that addresses specific capability gaps. The domain specialization finding — different models excel at Travel vs. Shopping (Table 2) — suggests that separate fine-tuning strategies may be needed for temporal-spatial planning vs. combinatorial optimization tasks.

Architecture selection for agent frameworks. The paper's analysis of the parallel-sequential tradeoff (Section 4.3, Figure 3) provides empirical guidance for agent framework design. GPT-5.2-high's sequential verification strategy achieves +12.7% higher Composite Score than GPT-5.1-high's parallel strategy but requires ~10× more interaction turns. This tradeoff has direct engineering implications: for latency-sensitive applications (interactive chatbots, real-time assistants), a framework should enforce or encourage parallel execution, accepting lower accuracy for faster responses. For throughput-oriented or offline applications (batch itinerary generation, overnight planning jobs), a framework should support deep sequential verification, accepting higher latency for better plans. The paper's finding that reasoning models are more efficient in both dimensions — achieving higher scores with fewer tool calls (Claude-4.5-Opus: 72.9 with thinking vs. 79.5 without) and fewer turns (12.5 vs. 16.9) — suggests that agent frameworks should preferentially route complex planning tasks to reasoning-capable models when available, even if their per-call cost is higher, because the total interaction cost may be lower. The specific numbers from Figure 3 (tool calls and turns per model) can inform cost modeling for production systems.