# TREK: A Travel Reasoning and Evaluation Kit for LLM Agents in Complex Trip Planning arXiv: https://arxiv.org/abs/2607.26977 · HTML: https://mlsanity.com/paper/2607.26977/ ## Key facts - Cited by 2 papers in the map (data through 14 Oct 2026). - Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning. - Builds on 45 of its 114 references that are in the map. - First posted on arXiv 29 Jul 2026. ## Placed in - LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/) - LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/) ## Builds on (most cited first, 30 of 45) - [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022) - [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023) - [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025) - [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023) - [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023) - [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023) - [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024) - [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025) - [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023) - [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024) - [OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments](https://mlsanity.com/paper/2404.07972/) (2024) - [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023) - [Large Language Models are not Fair Evaluators](https://mlsanity.com/paper/2305.17926/) (2023) - [GLM-5: from Vibe Coding to Agentic Engineering](https://mlsanity.com/paper/2602.15763/) (2026) - [Kimi K2.5: Visual Agentic Intelligence](https://mlsanity.com/paper/2602.02276/) (2026) - [LaMP: When Large Language Models Meet Personalization](https://mlsanity.com/paper/2304.11406/) (2023) - [Justice or Prejudice? Quantifying Biases in LLM-as-a-Judge](https://mlsanity.com/paper/2410.02736/) (2024) - [JudgeBench: A Benchmark for Evaluating LLM-based Judges](https://mlsanity.com/paper/2410.12784/) (2024) - [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023) - [Judging the Judges: A Systematic Study of Position Bias in LLM-as-a-Judge](https://mlsanity.com/paper/2406.07791/) (2024) - [Self-Preference Bias in LLM-as-a-Judge](https://mlsanity.com/paper/2410.21819/) (2024) - [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024) - [Large Language Models are Inconsistent and Biased Evaluators](https://mlsanity.com/paper/2405.01724/) (2024) - [Do LLMs Recognize Your Preferences? Evaluating Personalized Preference Following in LLMs](https://mlsanity.com/paper/2502.09597/) (2025) - [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024) - [Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools](https://mlsanity.com/paper/2404.11891/) (2024) - [The Amazon Nova Family of Models: Technical Report and Model Card](https://mlsanity.com/paper/2506.12103/) (2025) - [Robust Planning with LLM-Modulo Framework: Case Study in Travel Planning](https://mlsanity.com/paper/2405.20625/) (2024) - [TripTailor: A Real-World Benchmark for Personalized Travel Planning](https://mlsanity.com/paper/2508.01432/) (2025) - [To the Globe (TTG): Towards Language-Driven Guaranteed Travel Planning](https://mlsanity.com/paper/2410.16456/) (2024) ## Built on by (most cited first, 2 of 2) - [Replan, Repair, or Edit? A Unified Empirical Evaluation of Travel Agents for Itinerary Revision under Resource Disruptions](https://mlsanity.com/paper/2609.19654/) (2026) - [BANGLAPLAN: A Benchmark for Constraint-Based Planning and Decision-Making in Bangla](https://mlsanity.com/paper/2610.19704/) (2026) ## Abstract (arXiv) 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.