BibTeX download is not available in the pre-proceeding
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 succeed in these tasks, agents must engage in multi-turn conversations with users to gather task information and use tools to retrieve information from a database. Agents must then propose a solution that not only satisfies hard constraints but also optimizes the user's utility objective. By 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 the amount of information gathered. Coding agents offer a promising approach to mitigating 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.