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

AI summary

Overview

Research area: LLM agents, tool use, and benchmark design for constraint-based planning (Natural Language Processing / multi-agent planning). Technical level: Intermediate. Scope: The paper introduces TREK, an 800-task travel-planning benchmark with a 212,530-record synthetic knowledge base, a production-style RESTful tool sandbox, and a fully deterministic no-LLM-judge evaluator, used to measure whether 15 LLM agents can produce a single jointly-feasible itinerary.

What This Paper Is About

Travel planning is used here as a stress test for tool-using LLM agents because a usable itinerary is a single artifact that must be correct along many axes at once: every flight, hotel, and attraction must really exist, the days must be physically traversable, the total must fit a budget, and the plan must serve a traveler whose needs are only partly stated. Existing benchmarks tend to reward these properties one at a time and score the final output with soft rubrics or an LLM judge, which the authors argue cannot certify that a plan is executable and are neither reproducible nor auditable. TREK's goal is to make that measurement exact: deterministic scoring, a human-verified gold solution that demonstrably reaches the maximum score, and typed infeasibility as a first-class scored outcome.

Key Contributions

1. A dataset of 800 joint-feasibility travel-planning tasks over a 212,530-record synthetic knowledge base (375 cities, 13 personas), served through a production-style tool sandbox of validated RESTful and semantic-search APIs with structured JSON errors. The 800 tasks split into 533 feasible and 267 provably infeasible instances.
2. A fully deterministic, no-LLM-judge evaluator paired with a human-verified gold reference that demonstrably scores 1.0 on all 800 tasks, making the ceiling bit-reproducible and achievable so that every remaining gap is attributable to the agent rather than scorer strictness.
3. The task-perfect headline metric over nine constraint dimensions, plus typed (route / entity / budget) infeasibility as a first-class scored dimension via the 267 provably-infeasible tasks.
4. A 15-model study establishing the top/median/floor gap and three findings: implicit-need satisfaction as a capability-rising universal bottleneck, spatio-temporal reachability as the planner/non-planner watershed, and reasoning not helping in the one paired comparison the model set permits while accuracy does not track cost.

Main Findings

• Frontier agents largely fail at feasible itinerary synthesis. The strongest agent, GPT-5.6, produces a fully-feasible plan on only 46.2% of the 533 solvable tasks; the median of the 15 agents reaches just 6.6% and the floor is 0.0%.
• The wall is satisfying the traveler, not avoiding hallucination. GPT-5.6 is hallucination-free on 94.9% of tasks (Truthfulness), physically executable on 86.3% (Executability), and refuses impossible requests correctly on 97.0% (Infeasibility), but meets a plan's full set of explicit and implicit needs on only 50.7% of tasks (Satisfaction) — the category that binds the headline.
• Implicit persona needs (D1) are the universal bottleneck. D1 is a top-two failure for all 15 agents, with failure rates from 53.7% to 91.2%. After GPT-5.6 masters every other dimension (next-worst B3 at 13.3%), it still fails implicit-need satisfaction on 53.7% of applicable tasks.
• Spatio-temporal reachability (B3) is the planner/non-planner watershed. B3 failure ranges from 13.3% to 93.8%, the widest spread of any dimension — whether a day's legs are physically traversable cleanly separates planners from non-planners.
• The bottleneck shifts with capability. Weak agents fail everywhere — Nova-Pro and Qwen3-Next-80B miss D0-key on 78.2% and 59.7% of tasks, plus budget, coverage, and scheduling — while the frontier has pushed every other failure mode down substantially.
• Refusal is near-saturated and reported separately. TP-inf reaches 97.0% at the top; the authors report the feasible and infeasible task-perfect rates separately rather than blending them, since blending executable-plan construction with near-saturated refusal detection flatters the number.
• More deliberation did not buy more feasibility. In the one instruct/reasoning pair the model set permits (Kimi-K2.5 at 17.1% versus Kimi-K2-Thinking at 6.6% TP-feas), the reasoning variant underperformed — described by the authors as a cross-version observation, not a perfectly controlled pair.
• Accuracy does not track token spend. GPT-5.6 tops the board at 46k tokens per query, the lowest among the top-scoring agents, while several weak models spend far more — DeepSeek-V3.2 at 270k, Qwen3-Next-80B at 229k, and Nova-2-Lite at 324k — for single-digit or near-zero scores.
• The bar is not a cliff. Requiring ≥0.95 instead of exactly 1.0 on every dimension moves at most one task for any model: 13 of the 15 are unchanged and the other 2 shift by a single task, at most 0.2 percentage points.
• The top score is hard-but-in-band. The authors calibrate against τ-bench, which reports 46.0% airline / 69.2% retail pass, placing TREK's 46.2% among difficult-but-tractable agentic tasks rather than broken ones.
• Gold quality was human-vetted. A panel of 15 annotators (10 PhD researchers, 5 travel-industry practitioners) rated every feasible gold itinerary for realism and executability on a 1–5 scale, with a mean of 4.25/5 (approximately 85%); low-scored or disputed plans were revised before release.

Methodology in Plain English

The authors build a deterministic three-stage pipeline. First, a build script generates a synthetic knowledge base from fixed seed inputs: 212,530 mutually consistent records — 107,195 flights, 39,396 hotels, 55,814 attractions, and 10,125 car rentals — with 392 airports serving 375 cities. The city-to-airport scaffold uses the public OurAirports reference, while all bookable content such as schedules, prices, amenities, and ratings is synthesized and internally reconciled. The design is deliberate: internal consistency is what lets the team compute an exact ground truth and guarantee a reachable ceiling, which the authors say no scraped, drifting corpus can offer.

Second, tasks are generated with a template-then-populate approach. A pool of pure natural-language templates containing no ordering cues is filled in by a deterministic seeded script that samples valid entities and constraints from the knowledge base, so every named entity, route, and price resolves against the KB by construction. Feasibility labels are not annotated after the fact — they are guaranteed at generation time, because each task's budget is derived from a reference plan priced by the same cost model the scorer bills with. Every row is then re-scored by the authoritative evaluator before shipping, and only rows whose realized label matches the intended label are kept.

Third, each task ships with a gold reference — a feasible itinerary, or for an infeasible task the correctly-typed refusal — that scores 1.0 under the evaluator, validated by the 15-annotator panel.

Agents then act inside a production-style sandbox of five endpoints: four for querying domain resources (flights, hotels, attractions, car rentals) and one for submitting the final plan. Each endpoint enforces strict parameter validation, returns consistent JSON schemas with pagination, and emits structured errors. Query endpoints also return structured facility information and support semantic search, which agents may use to find persona-matching resources — but whether those needs are satisfied is scored deterministically by exact facility set-intersection, never by an LLM judge or embedding threshold.

Scoring covers nine correctness dimensions in four categories. Constraint Satisfaction includes D0-key (every explicitly requested element plus itinerary completeness), D1 (implicit persona needs), D2 (all destination cities booked, reported as D2-single / D2-multi), and D3 (budget, with an exponential overspend penalty of β=4, so a 25% overspend scores 0.37 and a 50% overspend scores 0.14). Truthfulness is D0-src, a zero-tolerance binary check that every named entity resolves to a real KB record. Executability includes B2 (fraction of attraction visits within opening hours) and B3 (same-day travel-time feasibility, using the same canonical travel-time model exposed to the agent's compute_travel_time tool). Infeasibility Handling is D4, all-or-nothing: 1.0 only for a refusal naming the correct typed cause, which the evaluator re-derives independently rather than trusting a stored label.

Each correctness category is scored all-or-nothing on a task, and the four categories are aggregated with a geometric mean rather than an arithmetic one, so no category can hide behind the others. Efficiency is kept as a separate cost axis, comparing tool-call counts to a task-derived oracle minimum and applying an exponential token-overrun penalty, because a correct itinerary produced expensively is still correct.

The experiments run 15 agents from ten vendors through Amazon Bedrock under one Bedrock-native function-calling harness (four search tools plus submit_plan, capped at 15 billable calls at temperature 0), with a free compute_travel_time helper so no agent is graded on a rule it could not query. GPT-5.6 is the one frontier closed model in the set, and the authors note the Claude family was geo-blocked from their run location — an availability constraint, not a design choice.

Why This Matters

Impact on research. The paper argues that the bottleneck in agent evaluation is measurement itself: no soft or LLM-judged score can certify that a returned plan is executable end to end, and satisfying five feasibility properties separately says nothing about satisfying them jointly in one artifact. By pairing a judge-free deterministic evaluator with a gold that demonstrably attains 1.0 on all nine dimensions, TREK makes any agent-to-ceiling gap attributable to the agent rather than the scorer. It also treats typed infeasibility and implicit-need satisfaction as scored, first-class behaviors rather than descriptive categories, and isolates "feasible itinerary synthesis" as a named capability.

Real-world applications:

• Consumer trip-planning assistants that must return one bookable itinerary rather than plausible-sounding prose.
• Corporate travel and expense tooling, where budget validity and bookable-entity truthfulness are hard requirements.
• Accessibility-aware travel services, since personas such as "disabled traveler" and "elderly travelers" are explicitly modeled as implicit needs to be satisfied.
• Agent-platform evaluation, where the deterministic evaluator offers bit-reproducible, free-to-rerun regression testing for tool-calling model upgrades.

Industry relevance. The agent harness mirrors production conditions — validated REST endpoints, structured JSON errors, pagination, semantic search, a billable tool-call cap, and a separate efficiency axis measured against a task-derived oracle minimum. The finding that accuracy does not track token spend is directly relevant to cost planning for deployed tool-using agents, and the finding that implicit-need satisfaction is unsolved even at the frontier identifies where product reliability currently breaks.

Future Directions

• Closing the implicit-need gap. D1 is the last wall even for the strongest agent, failing on 53.7% of applicable tasks; the paper leaves open what modeling or harness change would move it.
• Planning-grounded architectures. B3's spread from 13.3% to 93.8% failure separates planners from non-planners, raising the question of whether solver-backed or neuro-symbolic backends (which the related work reports lift TravelPlanner scores) would transfer to joint feasibility.
• Reasoning versus controllability, properly controlled. The paper's reasoning-versus-instruct observation rests on a single pair (Kimi-K2.5 versus Kimi-K2-Thinking) and is explicitly labeled cross-version rather than a controlled ablation; a controlled comparison under strict tool schemas remains open.
• Extending coverage. The evaluated agent set excludes the Claude family because of geo-blocking, and the paper reports no wall-clock compute measure (wall-clock is described as a usage-cost proxy, not clean compute), leaving both model coverage and compute measurement as gaps to address.

Target Audience

Researchers and engineers working on LLM agents and tool use; benchmark and evaluation designers interested in deterministic, auditable, judge-free scoring; practitioners building travel or booking assistants; and readers following the debate over whether linguistic plausibility is a valid proxy for formal executability. The paper is written at an intermediate level — accessible to readers familiar with LLM agents and API-based tool calling, with the heavier formalization (task formulation, full evaluator formulas, and domain schemas) placed in appendices.

Authors’ abstract

Travel planning is a demanding stress test for tool-using LLM agents: a usable itinerary is a single artifact that must be right along many axes at once - every flight, hotel, and attraction must exist and be bookable, the days must be physically traversable, the total must clear a budget, and the plan must serve a traveler whose needs are only partly stated. Existing agent benchmarks reward these properties one at a time and grade the final output with soft or LLM-judged rubrics, which cannot certify that a returned plan is executable and are neither reproducible nor auditable. We introduce TREK (Travel Reasoning and Evaluation Kit), a benchmark for feasible itinerary synthesis: producing a single plan that is jointly constraint-correct, hallucination-free, spatio-temporally executable, budget-valid, and responsive to the traveler's unstated persona needs. TREK comprises 800 multi-constraint tasks - 533 feasible and 267 provably infeasible with typed route/entity/budget causes - over a synthetic, internally consistent knowledge base of 212,530 records across 375 cities and 13 personas, served through a production-style tool sandbox of validated RESTful APIs. Every task is scored by a fully deterministic, rule-based evaluator with no LLM judge and ships a human-verified gold reference that scores a perfect 1.0 under that same evaluator, so the ceiling is demonstrably achievable and every remaining gap is an agent limitation rather than scorer strictness. Evaluating 15 LLM agents across nine constraint dimensions, we find that even the strongest (GPT-5.6) produces a fully-feasible plan on only 46.2% of solvable tasks, with a median of 6.6% and a floor of 0.0%; satisfying travelers' unstated needs emerges as the universal bottleneck, unsolved even at the frontier. We release the dataset, tool sandbox, deterministic evaluator, and agent code as a fully reproducible benchmark.