ItinBench: Benchmarking Planning Across Multiple Cognitive Dimensions with Large Language Models

This paper introduces ItinBench, a new benchmark that evaluates large language models across multiple cognitive dimensions by integrating spatial route optimization with traditional verbal reasoning in travel planning, revealing that current models struggle to maintain consistent performance when handling diverse cognitive tasks simultaneously.

The Gist

Imagine you are hiring a very smart, well-read travel agent to plan a perfect 3-day trip to Philadelphia. You give them a list of very specific requests: "I want a hotel with great service," "I need restaurants with fresh food," and "I want to visit museums that are fun for kids."

In the past, we tested these AI agents (Large Language Models, or LLMs) by asking them simple questions like, "Which museum is open on Sundays?" or "What is the capital of France?" They were great at answering those.

But ItinBench is a new, tougher test. It asks the AI to do two things at once:

1. The "Word Game" (Verbal Reasoning): Understand your complex, picky preferences and find the right places.
2. The "Map Game" (Spatial Reasoning): Figure out how to drive between all those places without wasting time or gas.

Here is a breakdown of what the paper found, using some everyday analogies.

1. The Setup: The "Super-Travel Agent" Test

The researchers built a giant digital database of real restaurants, hotels, and attractions in Philadelphia. They created 500 different "customer requests" (like the one above) and asked various AI models (like GPT-4o, Llama, and Gemini) to generate a full 3-day itinerary.

The twist? The AI had to not just pick the right places, but also optimize the route. It's like asking a chef to not only pick the perfect ingredients for a meal but also to chop, cook, and plate them in the most efficient order so the food doesn't get cold.

2. The Two Skills Being Tested

The paper argues that human intelligence has two distinct gears, and current AIs struggle to shift between them smoothly:

• Verbal Reasoning (The Librarian): This is the AI's ability to read your text, understand "freshness" means "good fish," and find a hotel that matches "good service." It's like a librarian finding the right book based on a vague description.
• Spatial Reasoning (The Navigator): This is the ability to look at a map and realize, "Oh, if I go to the Zoo first, then the Museum, then the Hotel, I'm driving in circles. I should go to the Museum first because it's right next to the Zoo." It's like a GPS that actually thinks about the geometry of the city.

3. The Big Discovery: The "Juggling Act" Failure

The most surprising finding is that when you ask the AI to do both at the same time, it starts to drop the balls.

• The Analogy: Imagine a juggler who is amazing at juggling three red balls (words). If you ask them to juggle three red balls and three blue balls (spatial routes) at the same time, they don't just get slightly worse; they often drop the red balls entirely.
• The Result: When the AI was asked to optimize the route, its ability to follow your specific text preferences (like "I want French food") actually got worse. It got so focused on the map that it forgot your specific tastes.

4. The "Cheat Code" Discovery

The researchers found something interesting about how the AI does the "Map Game."

• The Problem: If you just say, "Plan a route," the AI often fails. It's like asking someone to navigate a city they've never seen just by looking at a list of street names.
• The "Cheat Code": When the researchers gave the AI a pre-made list of "clusters" (e.g., "These 5 places are all in the same neighborhood"), the AI got much better at the route.
• The Takeaway: The AI isn't actually "seeing" the map in its mind like a human does. It's more like a super-fast text processor. It's connecting the dots between words ("Cluster A is near Cluster B") rather than visualizing the geometry. It's solving a word puzzle, not a geometry problem.

5. The Verdict: We Are Not There Yet

The paper concludes that while AI is getting incredibly smart at reading and writing, it still struggles with real-world planning where you have to balance logic, geography, and human preferences simultaneously.

• Current State: If you ask an AI to plan a trip, it might give you a great list of restaurants (Verbal win), but the route it suggests might involve driving 20 extra miles in circles (Spatial loss).
• The Future: To build a true "Travel Agent AI," we need to teach it to stop treating the map as just another list of words and start helping it understand space and distance in a way that feels more like human intuition.

In short: The paper introduces a new gym (ItinBench) where we can see that AI is a great reader but a clumsy navigator. To make them truly useful for real-life planning, we need to help them learn how to juggle both skills without dropping the ball.

Technical Summary

1. Problem Statement

Current benchmarks for Large Language Models (LLMs) primarily evaluate verbal reasoning (linguistic, logical, and mathematical tasks) within controlled, deterministic environments. While LLMs show proficiency in these areas, human-level cognition also heavily relies on spatial reasoning (the ability to visualize relationships, distances, and navigate environments).

Existing travel planning benchmarks often treat route optimization as a secondary task or rely on algorithmic solvers to handle the spatial component, thereby failing to test the LLM's intrinsic ability to perform spatial reasoning concurrently with verbal reasoning. The paper addresses the gap: Do LLMs struggle to maintain high performance when required to simultaneously handle complex verbal constraints (preferences, rules) and spatial constraints (route optimization)?

2. Methodology: ItinBench

The authors introduce ItinBench, a benchmark designed to evaluate LLMs across both verbal and spatial cognitive dimensions simultaneously using trip itinerary planning as the downstream task.

A. Data Construction

• Dataset: Based on the Yelp Dataset, focusing on Philadelphia. It includes 500 restaurants, 105 hotels, and 322 attractions.
• Preprocessing: User reviews are processed to extract specific attributes (e.g., "freshness," "service," "activity-oriented") to create a rule-based reasoning challenge.
• Queries: 500 human-like queries are generated, each containing 6–10 preferences covering trip duration, budget, cuisine, attraction types, and accommodation requirements.

B. Experimental Tasks

The benchmark defines four distinct tasks to isolate and combine reasoning capabilities:

1. Task 1 (Verbal Only): Generate an itinerary using the full dataset with no route optimization request. Tests pure verbal reasoning (preference matching).
2. Task 2 (Verbal + Spatial): Generate an itinerary using the full dataset with an explicit route optimization request. Tests multi-task reasoning without pre-filtered data.
3. Task 3 (Filtered + Spatial): Generate an itinerary using pre-filtered data (matching user preferences) with a route optimization request. Tests spatial reasoning when verbal constraints are removed.
4. Task 4 (Tool Use + Spatial): Uses a ReAct-style framework where the LLM must call tools (e.g., RestaurantSearch, BusinessClusterSearch) to gather information and optimize routes.

C. Evaluation Metrics

The evaluation is split into two domains:

1. Verbal Reasoning Metrics:

• Out of Pool (OOP): Rate of selecting businesses not present in the provided dataset (hallucination).
• Missing Information (MI): Rate of vague or missing recommendations.
• Micro/Macro Preference Matching: Percentage of recommendations satisfying specific user constraints.
• Validated Rate (VR): The proportion of plans that pass all failure checks and preference thresholds.

2. Spatial Reasoning Metrics:

• Average Recommendation Gap (ARG): Deviation from the required number of daily attractions.
• Distance Gap (DG) & Total Distance Gap (Total-DG): The difference in travel distance between the LLM's proposed route and an optimized route calculated by an adapted Traveling Salesman Problem (TSP) algorithm.
• Extra Cluster Jump (ECJ): Measures how often the LLM jumps between distant spatial clusters instead of visiting nearby attractions within the same cluster.

3. Key Contributions

1. Integration of Cognitive Dimensions: ItinBench is the first benchmark to explicitly integrate spatial reasoning (route optimization) into a verbal reasoning task (trip planning), moving beyond single-domain evaluations.
2. Algorithmic Evaluation of Spatial Reasoning: The authors adapted TSP algorithms to quantitatively measure route efficiency and spatial clustering logic, providing a rigorous metric for "spatial" performance rather than relying on subjective human judgment alone.
3. Comprehensive Benchmarking: The framework evaluates a wide range of models, from open-source (Llama 3.1 8B, Mistral Large) to closed-source (Gemini 1.5 Pro, GPT-4o, o1).

4. Key Results

The experiments reveal significant limitations in current LLMs when handling dual-domain tasks:

• Verbal Reasoning Struggles: Even with full data access, the Validated Rate (VR) is extremely low (e.g., ~18% for the best model, o1, in Task 1). Models frequently hallucinate (Out of Pool) or miss constraints. Performance improves significantly (up to 66% VR) only when data is pre-filtered, suggesting LLMs struggle with multi-step constraint satisfaction.
• Spatial Reasoning Trade-offs:
  • When asked to optimize routes without explicit spatial cues (Task 2), models fail to reduce travel distance significantly compared to Task 1.
  • Performance Drop: When forced to handle both verbal and spatial tasks simultaneously, models exhibit a trade-off. For example, OpenAI o1 achieves a low Total-DG (~7-9%) but sees a drop in Verbal Validated Rate compared to when it only handles verbal tasks.
  • Reliance on Textual Cues: Models perform better on spatial tasks only when provided with textual clustering information (e.g., "Cluster 1 contains these hotels"). This suggests LLMs are not performing genuine geometric reasoning but rather semantic text manipulation based on provided cues.
• Tool Use: While models like GPT-4o and Mistral Large achieve high tool delivery rates, they still struggle with fine-grained parameter extraction from complex queries (e.g., distinguishing "good flavor" from "good freshness").

5. Significance and Conclusion

• Real-World Complexity: ItinBench demonstrates that real-world planning requires a synthesis of cognitive domains that current LLMs cannot yet master simultaneously. The "performance trade-off" indicates that optimizing for one dimension (e.g., strict route efficiency) often degrades performance in another (e.g., preference adherence).
• Beyond Semantic Shortcuts: The study highlights that current "spatial reasoning" in LLMs is often a proxy for semantic reasoning (matching text patterns) rather than true spatial cognition (visualizing 2D/3D space).
• Future Directions: The authors argue that future benchmarks must move beyond textual representations of space (e.g., lists of coordinates) to test models on native structured spatial representations (graphs, maps) to truly advance toward Artificial General Intelligence (AGI) capable of complex planning.

In summary, ItinBench provides critical evidence that while LLMs are powerful verbal reasoners, they lack the robust, simultaneous cognitive integration required for complex real-world planning tasks involving spatial constraints.