TREK: 복잡한 여행 계획을 위한 LLM 에이전트의 추론 및 평가 도구

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

여행 계획은 도구를 사용하는 LLM 에이전트에 대한 매우 어려운 과제입니다. 사용 가능한 여행 일정은 하나의 결과물이며, 모든 측면에서 정확해야 합니다. 즉, 모든 항공편, 호텔, 관광 명소가 존재하고 예약 가능해야 하며, 이동 경로는 물리적으로 실현 가능해야 하고, 총 비용은 예산을 초과하지 않아야 하며, 계획은 여행자의 요구 사항을 부분적으로만 충족시켜야 합니다. 기존 에이전트 벤치마크는 이러한 특성을 하나씩 평가하고 최종 결과를 주관적인 기준 또는 LLM 기반의 기준으로 평가하는데, 이는 제공된 계획이 실행 가능한지 보장할 수 없으며 재현 가능하거나 감사 가능하지 않습니다. 우리는 TREK(Travel Reasoning and Evaluation Kit)을 소개합니다. TREK은 실현 가능한 여행 일정 생성에 대한 벤치마크이며, 제약 조건을 동시에 충족하고 환각 현상이 없는 상태로, 공간적 및 시간적으로 실행 가능하며 예산 요건을 만족하고 여행자의 명시되지 않은 요구 사항에도 부합하는 단일 계획을 생성하는 것을 목표로 합니다. TREK은 800개의 다중 제약 조건 작업으로 구성되어 있으며, 이 중 533개는 실현 가능한 반면 267개는 유형화된 경로/엔티티/예산 오류로 인해 확실히 불가능합니다. 이는 375개 도시와 13가지 페르소나를 포함하는 총 212,530개의 레코드로 구성된 자체적으로 일관성이 유지되는 지식 기반을 활용하며, 검증된 RESTful API를 통해 생산 환경의 도구 샌드박스에서 제공됩니다. 각 작업은 LLM 평가 없이 완전히 결정론적인 규칙 기반 평가기를 사용하여 점수가 매겨지며, 인간이 검증한 표준 답안이 함께 제공되어 동일한 평가기에서 완벽한 1.0점을 받도록 설계되었습니다. 따라서 최고 점수를 달성할 수 있으며, 나머지 격차는 평가기의 엄격함보다는 에이전트의 한계로 인한 것입니다. 우리는 9가지 제약 조건 측면에서 15개의 LLM 에이전트를 평가한 결과, 가장 강력한 에이전트(GPT-5.6)조차도 해결 가능한 작업의 46.2%에서만 완전히 실현 가능한 계획을 생성하는 것으로 나타났으며, 중앙값은 6.6%, 최저값은 0.0%였습니다. 여행자의 명시되지 않은 요구 사항을 충족시키는 것은 모든 에이전트에게 공통적인 난제로, 최고 성능의 에이전트에서도 해결되지 않는 경우가 많았습니다. 우리는 데이터셋, 도구 샌드박스, 결정론적 평가기 및 에이전트 코드를 완전히 재현 가능한 벤치마크로 공개합니다.

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.