# COMPASS: Benchmarking Constrained Optimization in LLM Agents

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

## Key facts

- Cited by 9 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 26 of its 33 references that are in the map.
- First posted on arXiv 8 Oct 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, 26 of 26)

- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [MultiWOZ -- A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling](https://mlsanity.com/paper/1810.00278/) (2018)
- [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025)
- [Towards Scalable Multi-domain Conversational Agents: The Schema-Guided Dialogue Dataset](https://mlsanity.com/paper/1909.05855/) (2019)
- [LLMs Get Lost In Multi-Turn Conversation](https://mlsanity.com/paper/2505.06120/) (2025)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [A Simple Language Model for Task-Oriented Dialogue](https://mlsanity.com/paper/2005.00796/) (2020)
- [MINT: Evaluating LLMs in Multi-turn Interaction with Tools and Language Feedback](https://mlsanity.com/paper/2309.10691/) (2023)
- [APIGen-MT: Agentic Pipeline for Multi-Turn Data Generation via Simulated Agent-Human Interplay](https://mlsanity.com/paper/2504.03601/) (2025)
- [StableToolBench: Towards Stable Large-Scale Benchmarking on Tool Learning of Large Language Models](https://mlsanity.com/paper/2403.07714/) (2024)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [LMRL Gym: Benchmarks for Multi-Turn Reinforcement Learning with Language Models](https://mlsanity.com/paper/2311.18232/) (2023)
- [UserBench: An Interactive Gym Environment for User-Centric Agents](https://mlsanity.com/paper/2507.22034/) (2025)
- [Building a Conversational Agent Overnight with Dialogue Self-Play](https://mlsanity.com/paper/1801.04871/) (2018)
- [Aligning LLMs with Individual Preferences via Interaction](https://mlsanity.com/paper/2410.03642/) (2024)
- [ComplexFuncBench: Exploring Multi-Step and Constrained Function Calling under Long-Context Scenario](https://mlsanity.com/paper/2501.10132/) (2025)
- [When2Call: When (not) to Call Tools](https://mlsanity.com/paper/2504.18851/) (2025)
- [Reducing Tool Hallucination via Reliability Alignment](https://mlsanity.com/paper/2412.04141/) (2024)
- [Enhancing Personalized Multi-Turn Dialogue with Curiosity Reward](https://mlsanity.com/paper/2504.03206/) (2025)
- [GenTUS: Simulating User Behaviour and Language in Task-oriented Dialogues with Generative Transformers](https://mlsanity.com/paper/2208.10817/) (2022)
- [TripTailor: A Real-World Benchmark for Personalized Travel Planning](https://mlsanity.com/paper/2508.01432/) (2025)
- [StableToolBench-MirrorAPI: Modeling Tool Environments as Mirrors of 7,000+ Real-World APIs](https://mlsanity.com/paper/2503.20527/) (2025)
- [Flex-TravelPlanner: A Benchmark for Flexible Planning with Language Agents](https://mlsanity.com/paper/2506.04649/) (2025)
- [GroundCocoa: A Benchmark for Evaluating Compositional & Conditional Reasoning in Language Models](https://mlsanity.com/paper/2404.04237/) (2024)

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

- [Toward Personalized LLM-Powered Agents: Foundations, Evaluation, and Future Directions](https://mlsanity.com/paper/2602.22680/) (2026)
- [The Evolution of Tool Use in LLM Agents: From Single-Tool Call to Multi-Tool Orchestration](https://mlsanity.com/paper/2603.22862/) (2026)
- [TRIP-Bench: A Benchmark for Long-Horizon Interactive Agents in Real-World Scenarios](https://mlsanity.com/paper/2602.01675/) (2026)
- [WRIT: Write-Read Intensive Trajectory Synthesis for Multi-Turn User-Facing Agents](https://mlsanity.com/paper/2606.02908/) (2026)
- [AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds](https://mlsanity.com/paper/2608.29397/) (2026)
- [LifePlanner: Evaluating LLM Agents for Geo-spatial Planning with Social Media Data](https://mlsanity.com/paper/2608.25039/) (2026)
- [Tasks over Application Manuals: Revealing Gaps in Long-Horizon Procedural Reasoning for Language Models](https://mlsanity.com/paper/2609.13005/) (2026)
- [Evaluating Open-Weight E-Commerce Agents with Environment-Grounded Verification](https://mlsanity.com/paper/2609.16093/) (2026)
- [Training User Simulators with Latent Intrinsic Feedback](https://mlsanity.com/paper/2610.13617/) (2026)

## Abstract (arXiv)

Human decision-making often involves constrained optimization. As LLM agents are deployed to assist with real-world tasks like travel planning, shopping, and scheduling, they must mirror this capability. We introduce COMPASS, a benchmark that evaluates whether LLM agents can perform constrained optimization in realistic travel planning settings. To success in these tasks, agents must engage in multi-turn conversations with user to gather task information as well as use tools to gather information from the database. Then agents must propose a solution that not only satisfies hard constraints but also optimizes user's utility objective. Evaluating state-of-the-art models, we reveal a significant feasible-optimal gap: while models achieve 70-90% feasibility (constraint satisfaction), they reach only 20-60% optimality (utility optimization). Our analysis shows that tool use is not the bottleneck. Instead, the core limitation is insufficient exploration of the search space, with success strongly correlating with information gathered. Coding agents show a promising approach to mitigate this gap. Together, COMPASS provides a testbed for developing LLM agents that can truly mirror human decision-making by both satisfying constraints and optimizing objectives.