- 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
-
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.
-
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
-
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.
-
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
-
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?
-
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?
-
Could the authors more clearly highlight the distinctive features of AlgoWorlds and its additional contributions compared with existing optimization benchmarks?
-
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.