Haoping Bai

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.