AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

• URL: http://arxiv.org/abs/2608.29397v1
• Date: Sat, 29 Aug 2026 18:37:41 GMT
• Title: AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds
• Abstract summary: Tool-use benchmarks generally evaluate whether an agent completes a workflow using appropriate tools and valid arguments.<n>We introduce AlgoWorlds, a benchmark that transforms formally specified optimization problems into partially observed decision environments.<n>AlgoWorlds contains 240 environments covering ten optimization families and four workload levels.
• Score: 58.529749203758634
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Algorithmic Feature Highlighting for Human-AI Decision-Making [2.7830690575074435]
  We study algorithms that highlight a small subset of case-specific features for human consideration.<n>A central issue is how humans interpret the algorithm's choice of features.<n>We show that optimizing highlighting for sophisticated agents can be computationally intractable.
  arXiv  Detail & Related papers  (2026-04-24T05:23:06Z)
• ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization [0.0]
  We introduce ConstraintBench, a benchmark for evaluating large language models on direct constrained optimization.<n>We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck.<n>No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference.
  arXiv  Detail & Related papers  (2026-02-25T22:54:26Z)
• Surrogate-based Optimization via Clustering for Box-Constrained Problems [0.0]
  This work presents a novel Surrogate-Based Optimization framework based on Clustering, SBOC.<n>At each iteration, it uses a single surrogate model for the entire domain, employs k-means clustering to identify unexplored domain, and exploits a local region around the surrogate optimum.<n>It successfully identified a global minimum for most test functions with substantially lower computational effort than other algorithms.
  arXiv  Detail & Related papers  (2026-01-12T11:29:53Z)
• OptimAI: Optimization from Natural Language Using LLM-Powered AI Agents [8.441638148384389]
  We introduce OptimAI, a framework for solving Optimization problems described in natural language.<n>Our framework is built upon the following key roles: formulator, planner, coder and code critic.<n>Our approach attains 88.1% accuracy on the NLP4LP dataset and 82.3% on the Optibench dataset, reducing error rates by 58% and 52%, respectively, over prior best results.
  arXiv  Detail & Related papers  (2025-04-23T17:45:05Z)
• Non-Convex Bilevel Optimization with Time-Varying Objective Functions [57.299128109226025]
  We propose an online bilevel optimization where the functions can be time-varying and the agent continuously updates the decisions with online data. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions.
  arXiv  Detail & Related papers  (2023-08-07T06:27:57Z)
• A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions [18.570591025615453]
  This paper develops a multimodal BO framework to find a set of local/global solutions for expensive-to-evaluate multimodal objective functions. We analytically derive the joint distribution of the objective function and its first-order derivatives. We introduce variants of the well-known BO acquisition functions to the multimodal setting and demonstrate the performance of the proposed framework.
  arXiv  Detail & Related papers  (2022-10-13T00:10:13Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.