TL;DR
The paper introduces TravelPlanner, a challenging new benchmark designed to evaluate large language model (LLM) agents on multi-constraint, long-horizon planning tasks using a real-world travel scenario. The evaluation reveals a stark reality check for current AI: even state-of-the-art models like GPT-4 achieve a mere 0.6% success rate when required to search for information and plan simultaneously. This benchmark highlights a massive gap between current language agents and human-level planning capabilities.
What Problem Does This Paper Address?
While LLMs have shown impressive performance in tool use and isolated reasoning tasks, evaluating their ability to plan in complex, unconstrained real-world environments remains difficult. Existing benchmarks often focus on single-objective optimization with fixed ground truths (like Blocksworld) or simple web navigation.
Real-world planning, such as organizing a multi-day vacation, is inherently more difficult. It requires an agent to:
- Manage long horizons: Make dozens of interdependent decisions regarding flights, hotels, restaurants, and attractions.
- Handle multiple constraints: Simultaneously satisfy explicit user preferences (e.g., budget, room type) and implicit commonsense constraints (e.g., not booking a lunch in a city you haven't arrived in yet).
- Proactively collect information: Search through massive, partially observable environments using tools.
To bridge this gap, the authors created TravelPlanner to see if today's language agents can truly operate as robust real-world planners.
Methods
The authors evaluate language agents using two distinct settings:
- Two-Stage Mode (Tool-Use + Planning): The agent is given a natural language query and must proactively use six environment tools to gather information, save relevant data to a digital "Notebook" (simulating working memory), and then compile a final itinerary using a
Plannertool. - Sole-Planning Mode: To isolate planning skills from information retrieval errors, this simplified mode provides the agent with all necessary, pre-filtered information (such as available flights and restaurants) directly in the context window.
The evaluation framework automatically parses the generated itineraries and grades them on three constraint tiers: environment constraints, commonsense constraints (e.g., no repeating attractions, reasonable city routes), and hard constraints (user-specified preferences like budget or cuisine).
Datasets
The paper introduces the TravelPlanner benchmark, which consists of:
- A Sandbox Environment: A static database containing nearly 4 million data records crawled from the internet, including flight statuses, distance matrices, restaurant options, attractions, and accommodations.
- 1,225 Curated Queries: Divided into training (45), validation (180), and test sets (1,000). The queries span three difficulty levels (Easy, Medium, Hard) and three travel durations (3, 5, or 7 days), which dictate the number of cities visited and constraints imposed.
- Human-Annotated Reference Plans: Created by 20 graduate students to ensure that every query has at least one valid, feasible solution.
Key Insights and Ideas
- The "Multitasking Tax" on Cognitive Capacity: LLMs suffer a severe performance drop when forced to collect information and plan at the same time. GPT-4's success rate drops from 4.4% in sole-planning mode to 0.6% in the two-stage mode, suggesting that language agents have a limited "cognitive capacity" when multitasking.
- Micro-Success vs. Macro-Failure: Agents often achieve high micro pass rates (satisfying individual constraints like finding the right cuisine), but fail miserably at macro pass rates (satisfying all constraints holistically). They struggle to maintain a global view of the plan.
- Stubborn Dead Loops: When agents receive negative feedback from the environment (e.g., "No flights found"), they frequently fail to dynamically adjust their strategy. Instead, they get trapped in repetitive loops, executing the exact same invalid action multiple times.
Key Results
The quantitative results paint a sobering picture for autonomous agents:
- Two-Stage Performance: GPT-4-Turbo (using the ReAct framework) was the only model capable of completing any tasks, achieving a 0.6% final pass rate on the test set. Other prominent models, including Gemini Pro, GPT-3.5-Turbo, and Mixtral-8x7B, scored 0%.
- Sole-Planning Performance: Even when handed all the correct data on a silver platter, GPT-4 only managed a 4.4% success rate, proving that multi-constraint satisfaction itself is a major bottleneck.
- Traditional Baselines: A standard rule-based Greedy Search baseline also scored 0%, as it optimized purely for cost and could not navigate the complex web of user and commonsense constraints.
The authors note that agents frequently fail due to argument errors in tool usage, date confusion (e.g., searching for 2023 flights in a 2022 database), and hallucinating fictitious details when they fail to find data.
Limitations and Future Work
The authors acknowledge a few key limitations:
- Static Sandbox: The environment is static to ensure reproducible and unbiased evaluation, meaning it doesn't capture the real-time volatility of live web data.
- Subjective Commonsense: The definition of "commonsense" constraints is based on author consensus, which may vary across different cultures and contexts.
Future Directions: The dismal success rates indicate that standard prompting strategies (like ReAct or Reflexion) are insufficient for complex planning. The authors suggest that future research must focus on developing more sophisticated strategies, such as explicit backtracking mechanisms to recover from dead ends, better working memory management, and training agents via reinforcement learning from environment feedback.
Summary updated