Technical Summary: TREK – A Travel Reasoning and Evaluation Kit for LLM Agents in Complex Trip Planning

1. Problem Statement

Travel planning represents a critical stress test for Large Language Model (LLM) agents transitioning from conversational chatbots to production systems that must return executable artifacts. A deployable travel itinerary is a "single object" that must simultaneously satisfy multiple, often conflicting, constraints:

• Existence and Bookability: Every flight, hotel, and attraction must exist and be bookable within the system.
• Spatio-Temporal Executability: The itinerary must be physically traversable (e.g., travel times between locations must be feasible within the day).
• Budget Adherence: The total cost must remain within the user's specified budget.
• Implicit Need Satisfaction: The plan must address unstated traveler personas (e.g., "luxury," "disabled," "foodie") which require specific facilities or amenities not explicitly requested in the prompt.

Existing benchmarks fail to adequately measure this capability. They often reward properties in isolation, rely on "soft" rubrics or LLM judges (which are biased and non-reproducible), and lack a mechanism to certify that a returned plan is truly executable end-to-end. Consequently, it is difficult to distinguish between an agent that has genuinely solved a complex planning problem and one that has produced a hallucinated but linguistically plausible plan.

2. Methodology: The TREK Benchmark

TREK (Travel Reasoning and Evaluation Kit) is introduced as a benchmark designed to measure joint feasibility—the ability to synthesize a single plan that is constraint-correct, hallucination-free, spatio-temporally executable, budget-valid, and responsive to implicit needs.

2.1 Synthetic, Internally Consistent Knowledge Base

To ensure ground truth is computable and reproducible, TREK utilizes a synthetic knowledge base containing 212,530 records across 375 cities. This includes:

• 107,195 flights
• 39,396 hotels
• 55,814 attractions
• 10,125 car rentals
• 13 distinct traveler personas (e.g., "with children," "road trip," "disabled traveler")

The data is generated by deterministic scripts seeded with fixed inputs (using public airport data as a scaffold) to ensure internal consistency. Prices, coordinates, and facilities are mutually coherent, allowing for exact ground-truth calculation. This approach avoids the drift and copyright issues of scraped real-world data while providing a controlled environment for certification.

2.2 Task Formulation

The benchmark comprises 800 multi-constraint tasks:

• 533 Feasible Tasks: Agents must generate a complete itinerary satisfying all constraints.
• 267 Infeasible Tasks: Agents must correctly refuse the request and diagnose the specific cause of infeasibility. These are categorized into three typed causes:
  1. Entity: A specifically named resource does not exist in the knowledge base.
  2. Route: No direct flight exists between required cities.
  3. Budget: The budget is strictly below the achievable cost floor.

Tasks are generated via a "template-then-populate" approach, ensuring that every entity and constraint in a query is resolvable against the knowledge base by construction.

2.3 Production-Style Tool Sandbox

Agents interact with a production-style environment consisting of RESTful APIs with strict parameter validation, semantic-search endpoints, and structured JSON errors. This mimics real-world travel service interfaces, requiring agents to handle tool errors and interpret structured responses rather than relying on free-form function calls.

2.4 Deterministic Evaluation Framework

A core innovation of TREK is its fully deterministic, rule-based evaluator that uses no LLM judge.

• Scoring: Every dimension is an exact computation against the versioned knowledge base.
• Implicit Needs: Satisfaction is scored via deterministic set-intersection of required facilities against booked resources, avoiding embedding-based or learned thresholds.
• Gold Reference: Every task ships with a human-verified gold reference (a feasible itinerary or a correctly typed refusal) that scores a perfect 1.0 under the same evaluator. This establishes a demonstrably achievable ceiling, ensuring that any performance gap is attributable to the agent, not scorer strictness.

2.5 Evaluation Metrics

The primary metric is the Task-Perfect Rate, defined as the fraction of tasks where an agent scores 1.0 on every applicable correctness dimension and passes all hard gates. The evaluation covers nine dimensions across four categories:

1. Constraint Satisfaction: Explicit constraints (D0-key), Implicit needs (D1), City coverage (D2), and Budget (D3).
2. Truthfulness (D0-src): Zero-tolerance check for hallucinations (every entity must resolve to a KB record).
3. Executability: Opening hours compliance (B2) and Spatio-temporal feasibility (B3).
4. Infeasibility Handling (D4): Correctly identifying and typing the cause of infeasibility.

3. Key Results

The authors evaluated 15 LLM agents (including frontier models like GPT-5.6, Kimi-K2, and GLM-5) across the 800 tasks.

• Overall Performance: Even the strongest agent, GPT-5.6, achieved a fully-feasible plan on only 46.2% of solvable tasks. The median performance across all 15 agents was 6.6%, with a floor of 0.0%.
• The Universal Bottleneck (Implicit Needs): The primary failure mode for all agents, including the frontier models, is Implicit Need Satisfaction (D1). While GPT-5.6 achieved high scores in truthfulness (94.9%) and executability (86.3%), it satisfied implicit persona needs on only 50.7% of applicable tasks. This dimension remains the hardest, with failure rates ranging from 53.7% to 91.2% across all models.
• Planner vs. Non-Planner Watershed: Spatio-temporal reachability (B3) serves as a clear divider. Failure rates ranged from 13.3% for the top model to 93.8% for the weakest, indicating that many agents struggle to plan physically traversable itineraries.
• Reasoning vs. Controllability: In the one pair of models permitting a comparison (Kimi-K2 vs. Kimi-K2-Thinking), the reasoning-enhanced variant underperformed (6.6% vs. 17.1% task-perfect rate). This suggests a tension between deliberation and strict adherence to tool schemas.
• Cost vs. Accuracy: There is no correlation between token spend and accuracy. The top-performing agent (GPT-5.6) had the lowest per-query token cost among top scorers, while weaker models spent 5–7 times more tokens for single-digit scores.

4. Significance and Claims

The paper claims that TREK provides the first benchmark capable of certifying joint feasibility with a demonstrably reachable ceiling. Its significance lies in:

1. Moving Beyond Soft Metrics: By eliminating LLM judges and using a deterministic, rule-based scorer against a human-verified gold, TREK offers reproducible and auditable results.
2. Identifying the True Frontier: The study reveals that while agents are becoming proficient at retrieving facts and following explicit instructions, they fundamentally struggle with synthesizing plans that satisfy unstated human needs and ensuring physical executability.
3. Typing Infeasibility: TREK treats the correct refusal of impossible requests as a first-class, scored behavior, distinguishing between "I can't do this" and a specific diagnosis (e.g., "No flight route exists").
4. Realistic Stress Testing: The combination of a production-style API sandbox, strict parameter validation, and multi-constraint optimization exposes limitations in current agents that softer benchmarks miss.

The authors conclude that current LLM agents are not yet dependable for everyday travel planning, as the "universal bottleneck" of satisfying implicit needs remains unsolved even at the frontier. The benchmark is released as a fully reproducible kit including the dataset, tool sandbox, evaluator, and agent code.