AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds
Zixiang Xu, Jiaan Wang and Fandong Meng (WeChat AI) turn combinatorial optimization problems into partially observed tool-use environments with certified global optima, and find leading models reach exact optimality only 38.61% of the time.
Ask this paper
Feasibility is not the bar: Existing tool-use benchmarks ask whether the workflow completed with valid arguments. AlgoWorlds asks whether the gathered information was turned into a globally optimal decision, which is what route planning and fleet dispatch actually require.
240 environments, ten problem families, four workload levels: Instances come from family-specific deterministic programs, exact algorithms certify the optima and set workload levels, and two structurally different tool interfaces present each instance.
Best model at 38.61% exact optimality: Across seven leading LLMs including Claude Opus 4.8 and GPT-5.6 Sol, models produce feasible decisions in most cases but rarely optimal ones.
Failure is integration, not acquisition: Even when agents collect enough information to reconstruct the hidden instance, most failures end in feasible but suboptimal decisions. The bottleneck is global constraint reasoning and decision verification.
Clean separation of concerns: Because the optima are certified, the benchmark can attribute failure to information integration in a way that most agent benchmarks cannot.
Abstract
Tool-use benchmarks generally evaluate whether an agent completes a workflow using appropriate tools and valid arguments. However, feasibility alone is insufficient in real-world decision settings such as route planning and fleet dispatch. Individual choices interact through shared constraints and costs, so a feasible solution may still be substantially suboptimal. This raises a harder question: can an agent turn information gathered through tools into a globally optimal decision? We introduce AlgoWorlds, a benchmark that transforms formally specified combinatorial optimization problems into partially observed decision environments with verifiable global optima. Each environment contains a hidden instance observed only through task-specific information tools, after which the agent commits to one structured decision evaluated for feasibility and optimality. AlgoWorlds contains 240 environments covering ten combinatorial optimization families and four workload levels. Family-specific deterministic programs generate the instances, exact algorithms certify their optima and determine workload levels, and two structurally different tool interfaces present each underlying instance. We evaluate seven leading LLMs, including Claude Opus 4.8 and GPT-5.6 Sol. Achieving global optimality remains highly challenging: although leading models produce feasible decisions in most cases, the best-performing model reaches exact optimality in only 38.61% of cases. Even when agents collect sufficient information to reconstruct the hidden instance, most failures end in feasible but suboptimal decisions. The challenge therefore extends beyond information acquisition to information integration, global constraint reasoning, and decision verification. The project homepage is available at https://xzx34.github.io/AlgoWorlds/, and the code is available at https://github.com/xzx34/AlgoWorlds.