Mert Cemri

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.

Recent work such as AlphaEvolve has shown that combining LLM-driven optimization with evolutionary search can effectively improve programs, prompts, and algorithms across domains. In this paradigm, previously evaluated solutions are reused to guide the model toward new candidate solutions. Crucially, the effectiveness of this evolution process depends on the search strategy: how prior solutions are selected and varied to generate new candidates. However, most existing methods rely on fixed search strategies with predefined knobs (e.g., explore–exploit ratios) that remain static throughout execution. While effective in some settings, these approaches often fail to adapt across tasks, or even within the same task as the search space changes over time. We introduce EvoX, an adaptive evolution method that optimizes its own evolution process. EvoX jointly evolves candidate solutions and the search strategies used to generate them, continuously updating how prior solutions are selected and varied based on progress. This enables the system to dynamically shift between different strategies during the optimization process. Across nearly 200 real-world optimization tasks, EvoX consistently outperforms prior open frameworks, including OpenEvolve, ShinkaEvolve, and GEPA. It achieves the best open-source performance on Frontier-CS (+34\% median over the best AI solutions across 172 problems), matches or surpasses AlphaEvolve and human-designed state-of-the-art solutions on multiple benchmarks, and does so at more than 3$\times$ lower cost on average compared to existing open systems and Claude Code.