여행 계획은 도구를 사용하는 LLM 에이전트에게 매우 까다로운 스트레스 테스트입니다. 실행 가능한 일정은 여러 축에서 동시에 정확해야 하는 단일 결과물입니다. 즉, 모든 항공편, 호텔, 명소가 실제로 존재하고 예약 가능해야 하며, 날짜 간 이동이 물리적으로 가능해야 하고, 총비용이 예산을 초과하지 않아야 하며, 계획은 요구 사항이 부분적으로만 명시된 여행자의 니즈를 충족해야 합니다. 기존의 에이전트 벤치마크는 이러한 속성들을 한 번에 하나씩 보상하며, 최종 출력을 소프트 루브릭(soft rubrics)이나 LLM이 판단하는 기준으로 채점합니다. 이는 반환된 계획이 실행 가능한지를 인증할 수 없으며, 재현성이나 감사 가능성(auditable)도 갖추지 못합니다.

우리는 실행 가능한 일정 합성(feasible itinerary synthesis)을 위한 벤치마크인 TREK (Travel Reasoning and Evaluation Kit)을 소개합니다. 이는 제약 조건이 모두 정확하고(constraint-correct), 환각이 없으며(hallucination-free), 시공간적으로 실행 가능하고(spatio-temporally executable), 예산이 유효하며(budget-valid), 여행자의 명시되지 않은 페르소나 니즈에 부응하는 단일 계획을 생성하는 것을 목표로 합니다. TREK은 800개의 다중 제약 조건 태스크로 구성되어 있습니다. 이 중 533개는 실행 가능하며, 267개는 유형화된 경로/엔티티/예산 원인과 함께 명백히 실행 불가능함이 증명되었습니다. 이 태스크들은 375개 도시와 13개의 페르소나에 걸쳐 212,530개의 레코드로 구성된 합성적이고 내부적으로 일관된 지식 베이스를 기반으로 하며, 검증된 RESTful API를 갖춘 프로덕션 스타일의 도구 샌드박스(tool sandbox)를 통해 제공됩니다.

모든 태스크는 LLM 판정관 없이 완전히 결정론적인 규칙 기반 평가기(rule-based evaluator)에 의해 점수가 매겨지며, 동일한 평가기 하에서 완벽한 1.0점을 받는 인간 검증 골드 레퍼런스(gold reference)를 함께 제공합니다. 따라서 성능의 상한선(ceiling)은 입증 가능하며, 남아있는 모든 격차는 평가자의 엄격함이 아닌 에이전트의 한계임을 보여줍니다. 9가지 제약 차원에서 15개의 LLM 에이전트를 평가한 결과, 가장 강력한 모델(GPT-5.6)조차 해결 가능한 태스크 중 단 46.2%에서만 완전히 실행 가능한 계획을 생성했으며, 중앙값은 6.6%, 최솟값은 0.0%였습니다. 여행자의 명시되지 않은 니즈를 충족하는 것이 보편적인 병목 현상으로 나타났으며, 이는 최첨단(frontier) 모델에서도 해결되지 않은 과제입니다. 우리는 데이터셋, 도구 샌드박스, 결정론적 평가기 및 에이전트 코드를 완전히 재현 가능한 벤치마크로 공개합니다.