# Flex-TravelPlanner: A Benchmark for Flexible Planning with Language Agents

arXiv: https://arxiv.org/abs/2506.04649 · HTML: https://mlsanity.com/paper/2506.04649/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 5 of its 8 references that are in the map.
- First posted on arXiv 5 Jun 2025.

## Placed in

- 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, 5 of 5)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [LLM-as-an-Interviewer: Beyond Static Testing Through Dynamic LLM Evaluation](https://mlsanity.com/paper/2412.10424/) (2024)

## Built on by (most cited first, 10 of 10)

- [CostBench: Evaluating Multi-Turn Cost-Optimal Planning and Adaptation in Dynamic Environments for LLM Tool-Use Agents](https://mlsanity.com/paper/2511.02734/) (2025)
- [Uncertainty Quantification in LLM Agents: Foundations, Emerging Challenges, and Opportunities](https://mlsanity.com/paper/2602.05073/) (2026)
- [COMPASS: Benchmarking Constrained Optimization in LLM Agents](https://mlsanity.com/paper/2510.07043/) (2025)
- [TripTide: A Benchmark for Adaptive Travel Planning under Disruptions](https://mlsanity.com/paper/2510.21329/) (2025)
- [HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel](https://mlsanity.com/paper/2603.04750/) (2026)
- [TravelEval: A Comprehensive Benchmarking Framework for Evaluating LLM-Powered Travel Planning Agents](https://mlsanity.com/paper/2606.01046/) (2026)
- [Investigating Advanced Reasoning of Large Language Models via Black-Box Environment Interaction](https://mlsanity.com/paper/2508.19035/) (2025)
- [PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models](https://mlsanity.com/paper/2605.20873/) (2026)
- [Replan, Repair, or Edit? A Unified Empirical Evaluation of Travel Agents for Itinerary Revision under Resource Disruptions](https://mlsanity.com/paper/2609.19654/) (2026)
- [Beyond Oracle Communication: Benchmarking Interactive Intent Alignment Under Miscommunication and Evolving User Intent](https://mlsanity.com/paper/2609.38604/) (2026)

## Abstract (arXiv)

Real-world planning problems require constant adaptation to changing requirements and balancing of competing constraints. However, current benchmarks for evaluating LLMs' planning capabilities primarily focus on static, single-turn scenarios. We introduce Flex-TravelPlanner, a benchmark that evaluates language models' ability to reason flexibly in dynamic planning scenarios. Building on the TravelPlanner dataset~citepxie2024travelplanner, we introduce two novel evaluation settings: (1) sequential constraint introduction across multiple turns, and (2) scenarios with explicitly prioritized competing constraints. Our analysis of GPT-4o and Llama 3.1 70B reveals several key findings: models' performance on single-turn tasks poorly predicts their ability to adapt plans across multiple turns; constraint introduction order significantly affects performance; and models struggle with constraint prioritization, often incorrectly favoring newly introduced lower priority preferences over existing higher-priority constraints. These findings highlight the importance of evaluating LLMs in more realistic, dynamic planning scenarios and suggest specific directions for improving model performance on complex planning tasks. The code and dataset for our framework are publicly available at https://github.com/juhyunohh/FlexTravelBench.