acceptodds
Under review as a conference paper at ICLR 2027

AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

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? In this paper, we introduce AlgoWorlds, a benchmark that transforms formally specified combinatorial optimization problems into partially observed decision environments with global optima. Each environment contains a hidden optimization instance that the agent observes only through sequential calls to task-specific information tools. The agent then commits to one structured decision, which an independent checker evaluates for feasibility, objective value, and optimality. AlgoWorlds contains 240 such environments, covering ten combinatorial optimization families and four workload levels. To make these environments both controllable and auditable, family-specific deterministic programs generate hidden instances, while exact algorithms certify their global optima and determine their workload levels. Each instance is exposed through two structurally different multi-tool interfaces, which preserve the same decision problem under different information presentation. We evaluate seven leading LLMs, including Claude Opus 4.8 and GPT-5.6 Sol, on AlgoWorlds. Results show that achieving global optimality remains highly challenging: although leading models achieve feasibility in most cases, the best-performing model achieves exact optimality in only 38.61% of cases. Further analysis shows that even when the LLM 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.

Primary area:
datasets and benchmarks
Keywords:
large language models, tool use, AI agents, combinatorial optimization, global optimization, decision making, datasets and benchmarks

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_3ethOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces AlgoWorlds, a benchmark covering 10 combinatorial optimization tasks to evaluate whether LLMs can make globally optimal decisions using only information-retrieval tools. It uses independent exact algorithms to verify the feasibility and global optimality of the solutions and evaluates seven LLMs across multiple dimensions. The results show that while LLMs can often gather sufficient information and produce feasible solutions, they still struggle to achieve global optimality. The benchmark provides a reliable evaluation framework, but the experimental setup, reasons for model failures, benchmark scale, and differences from existing work require further clarification and validation.

Critical strengths
  1. The paper develops an interactive benchmark covering 10 combinatorial optimization tasks and uses independent exact algorithms to verify the feasibility and global optimality of model-generated solutions, making the evaluation more objective and reliable.

  2. The paper evaluates models across multiple dimensions, including information acquisition, solution feasibility, and global optimality. It also compares different models, difficulty levels, and tool interfaces, providing a more comprehensive assessment of LLM optimization capabilities.

Critical weaknesses
  1. The benchmark restricts agents to information-access tools and limited candidate feedback, while excluding code execution and optimization solvers. However, real-world combinatorial optimization tasks typically rely on specialized algorithms. This raises concerns about the practical relevance of the experimental setting and what new scientific insights can be gained from evaluating LLMs without computational tools.

  2. The paper evaluates information sufficiency and solution feasibility, but it remains unclear whether LLMs fail to find optimal solutions because they misunderstand the problem and its constraints or struggle with the optimization itself. Additional control experiments would help clarify the reasons for these failures and strengthen the paper's conclusions.

Questions for authors
  1. Given that the benchmark contains 120 hidden instances (10 task families × 4 workload levels × 3 instances), presented through two tool interfaces to form 240 environments, is this scale sufficient to support reliable conclusions? Could the authors further examine how instance selection might affect the reported results?

  2. Based on Tables 2 and 3, Claude Opus 4.8 may achieve a higher optimality rate when the information-sufficiency criterion is not met. Could the authors verify this observation using the original results and provide further analysis across task families and difficulty levels?

  3. Could the authors more clearly highlight the distinctive features of AlgoWorlds and its additional contributions compared with existing optimization benchmarks?

  4. Could the authors include traditional optimization heuristics as additional baselines? Such comparisons would help assess the difficulty of the tasks and put LLM performance into perspective.

Reviewer_zfRtOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces AlgoWorlds, a benchmark designed to evaluate whether LLM agents can gather information through tool interactions and make globally optimal decisions. The benchmark consists of 240 environments derived from 120 instances across 10 combinatorial optimization task families and four difficulty levels. Each instance has a verified global optimum and is presented through two different tool interfaces. Experiments on seven frontier LLMs show that agents often collect sufficient information and produce feasible solutions but struggle to achieve global optimality, with the best model Claude Opus 4.8 reaching only 38.61% exact optimality.

Critical strengths
  1. The benchmark uses independently verified optimal solutions, enabling objective and reproducible evaluation without relying on LLM judges.
  2. It has a good coverage, with multiple combinatorial optimization problems, difficulty levels, and tool interface.
  3. The benchmark also comes with insightful analysis. The experiments highlight a substantial gap between information acquisition, solution feasibility, and global optimality.
Critical weaknesses
  1. I feel this task is not very pratically reasonable. It does not reflect how LLM agents should solve optimization tasks. The benchmark requires LLMs to directly solve structured combinatorial optimization problems without standard computational tools. This weakens the claimed relevance to real-world agentic decision-making. In realistic applications, LLM agents would be more valuable for understanding requirements, gathering information, formulating problems, and invoking standard optimization solvers, or improving the optimization solver. Even a chatting llm today can write code when it encounters an optimization problem.
  2. The paper would be stronger with more meaningful baselines. It only evaluates standalone LLM agents without comparing to optimization solver augmented agents, simple classical optimization heuristics, or LLMs given complete problem information. These baselines are important for understanding why the observed failures arise.
  3. The main conclusion that LLMs frequently produce feasible but suboptimal solutions is relatively unsurprising given the task design.
Questions for authors
  1. Can we add more baselines like agent with an optimization solver tool or llm with full optimization problem instance as an upper bound performance? so we can analyze whether the performance gap comes from information collection or just optimization reasoning?
Reviewer_HHMkOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This article proposes AlgoWorlds, a benchmark for evaluating whether LLM agents can obtain information and make globally optimal decisions through tools. It covers 10 types of combinatorial optimization problems, 120 independent instances, and 240 tool interaction environments, and verifies the optimal solution through precise algorithms. Experiments have found that even if LLM can obtain sufficient information and generate feasible solutions, it often fails to achieve global optimality; The best performing model only achieved an optimal rate of 38.61%.

Critical strengths
  1. The tool extends the evaluation of task completion and feasibility to global optimality, proposing a meaningful evaluation dimension.

  2. Covers ten types of optimization problems and uses independent exact solving algorithms to cross validate the optimal solution, ensuring the reliability and reproducibility of the evaluation results.

  3. Evaluate seven mainstream LLMs and analyze model performance from multiple dimensions such as information acquisition, solution feasibility, optimality, task category, and tool interface.

Critical weaknesses
  1. Lack of key baselines such as heuristic algorithms, LLM+optimization solvers, and LLM+code execution. Due to the deliberate prohibition of using external computing tools in the experiment, it is unclear whether the performance bottleneck comes from the decision-making ability of the agent or its limited computing power.

  2. The paper mainly explains the failure of the model through the gap between information sufficiency and optimal rate, but lacks complete information input, solver assistance, and other control experiments, which cannot fully distinguish between information integration errors and insufficient optimization reasoning ability.

  3. The benchmark only contains 120 independent composite instances, with only 3 instances for each task category and difficulty level. In addition, the difficulty is defined by the number of operations of a specific precise algorithm, and its consistency with the actual inference difficulty of LLM has not been fully demonstrated.

Questions for authors

Please see above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.