PaperlayerView exact revision on arXiv

Source-linked AI summary

AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

Zixiang Xu, Jiaan Wang, Fandong Meng

arXiv:2608.29397v1cs.CL

TL;DR

Tool-use benchmarks often test workflow completion without determining whether feasible decisions are globally optimal. AlgoWorlds creates partially observed optimization environments with verified optima and costed information tools, and finds that leading LLMs remain much better at feasibility than exact optimization, even with sufficient information.

  • Problem

    Tool-use benchmarks generally neglect global optimality, although real-world decisions interact through shared constraints and costs so feasible solutions may be substantially suboptimal.

  • Method

    AlgoWorlds transforms formally specified combinatorial optimization problems into partially observed environments with hidden instances, task-specific tools, verified optima, and paired interfaces.

  • Results

    Across the benchmark, leading LLMs usually produce feasible decisions but rarely exact optima; Claude Opus 4.8 achieves the highest exact-optimality score at 38.61%.

  • Takeaways & Limitations

    The challenge extends beyond information acquisition to integrating information, reasoning over global constraints, and verifying the final decision.

  • Takeaways & Limitations

    The results cover seven LLMs and formally generated worlds with unique optima, excluding noisy or ambiguous real-world information and multiple globally optimal solutions.

Abstract

from arXiv · show

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.

1. Introduction

AlgoWorlds addresses a gap in tool-use benchmarks by testing whether agents can convert gathered information into globally optimal decisions, not merely feasible workflow completion. The benchmark evaluates this capability across hidden combinatorial optimization instances and shows that sufficient information still often fails to produce optimal decisions.

  • Motivation: Tool-use benchmarks typically assess appropriate tool selection and task completion, but overlook global optimality in decisions coupled by shared constraints and costs.Feasible solutions in route planning, fleet dispatch, and resource allocation can remain substantially suboptimal.
  • Benchmark: AlgoWorlds evaluates whether LLM agents can turn information acquired through tools into globally optimal decisions.Its decision environments contain hidden problem instances accessed through task-specific tools.
  • Findings: 38.61% is Claude Opus 4.8’s exact-optimality rate, the highest among the seven evaluated LLMs, followed by GPT-5.6 Sol at 38.19%.The result comes from the benchmark’s primary exact-optimality evaluation.
  • Findings: 89.86% of GPT-5.6 Sol trajectories gather sufficient information, yet 58.42% still end without a globally optimal decision.Most such failures produce feasible but suboptimal decisions; one routing example has an objective value 63.3% higher than optimal.
  • Benchmark: 240 algorithmic worlds span ten optimization families and four workload levels, with deterministic instance generation, exact optimum verification, and paired tool interfaces.The paired interfaces expose the same underlying decision problem through structurally different information presentations.
  • Findings: Across seven leading LLMs, agents are often effective at gathering information and producing feasible decisions but remain less reliable at finding global optima.This capability profile is relatively stable across paired interfaces and varies sharply across optimization families.

2. Related Work

Prior benchmarks study tool operation, partially observed interaction, planning, retrieval, and optimization reasoning as related capabilities. AlgoWorlds combines these settings with formal hidden optimization instances and evaluates the final decision against an exact global optimum.

  • Tool use and interactive agents: Tool-use benchmarks evaluate tool selection, valid arguments, state maintenance, and completion of prescribed workflows across APIs, agents, and domains.Examples include API-Bank, ToolLLM, BFCL, ACEBench, Tool Decathlon, TaskBench, and MCP-Bench.
  • Partially observed environments and information seeking: Partially observed environment benchmarks study reasoning and action when information is initially incomplete, including executable web, desktop, and application states.Related work also analyzes trajectories, retrieval, synthesis, and information-seeking behavior.
  • AlgoWorlds: AlgoWorlds exposes well-defined facts from hidden optimization instances and evaluates tool-mediated trajectories by information coverage and final decisions against formal objectives and exact optima.This distinguishes it from benchmarks scored primarily by textual answers or workflow state.
  • Planning with consequential decisions: Planning benchmarks evaluate coherent actions or decisions under constraints and consequences beyond individual steps, including feasible itinerary construction.PlanBench, ACPBench, NATURAL PLAN, TravelPlanner, and DeepPlanning represent this line of work.
  • Algorithmic and optimization reasoning: Algorithmic and optimization reasoning benchmarks test algorithm execution, optimization-model formulation, and automated optimization across textual and mathematical settings.CLRS-Text, NL4Opt, Mamo, OptiBench, and ORLM exemplify these tasks.

3. AlgoWorlds

AlgoWorlds is a partially observed decision environment in which agents use costed task-specific tools to reconstruct hidden optimization instances and submit one final decision. The benchmark is deterministically constructed, exactly verified, paired across tool interfaces, and evaluated with final-decision and trajectory metrics.

  • 3.1. Formal Definition: An algorithmic world contains a textual question, hidden optimization instance, task-specific tools, tool costs, and an access budget.The instance determines feasible decisions and objective values, while tools expose information about it.
  • 3.1. Formal Definition: Agents receive the question, tools, cost function, and budget without the hidden instance, then interact through tool calls before committing one final decision.Information calls may repeat within budget; the final-decision tool is zero-cost and invoked once at the trajectory’s end.
  • 3.2. Benchmark Construction: The benchmark covers ten combinatorial optimization families that differ in global constraints, objectives, and exact solution methods.The families include formally specified decision, instance, feasibility, and objective structures.
  • 3.2. Benchmark Construction: Each family uses a deterministic generator, a tailored exact algorithm to find the optimum and workload level, and paired Direct and Mediated interfaces for the same instance.The paired worlds share the instance, question, tool-call costs, and access budget while differing in relational tool structure.
  • 3.3. Data Quality: Every retained instance has a feasible decision and unique global optimum, with independent solver agreement on the optimal decision and objective value.Validation also confirms sufficient information can be acquired within budget, while exhaustive tool use exceeds the budget.
  • 3.4. Evaluation Metrics: Exact optimality, feasibility, and reference utility evaluate final decisions, while information sufficiency and discovery coverage diagnose gathered information.A trajectory can gather enough information yet still end in a non-optimal decision.
  • 3.4. Evaluation Metrics: Information sufficiency records whether a complete sufficient information set was gathered, whereas discovery coverage measures the largest proportion of any sufficient set present.These diagnostics separate information acquisition from final-decision quality.

4. Algorithmic Foundations

AlgoWorlds grounds benchmark workload levels in the primitive operations of exact algorithms rather than raw instance size. Its construction uses coupled combinatorial decisions, certified optima, and algorithm-generated scales to create reproducible difficulty levels.

  • Algorithmic motivations: Shared constraints and objectives couple actions, so independently optimizing each action cannot produce a global optimum.Exact algorithms retain information that later decisions depend on, such as the vehicle-load vector in Fleet Dispatch.
  • Verified optima: Exact algorithms run during benchmark construction to certify each instance’s optimum and quantify agent performance against it.The algorithms are not shown to evaluated agents, which must infer the coupling structure through tool use.
  • Algorithm-grounded workload levels: Workload levels are aligned by the number of primitive operations executed by family-specific exact algorithms, not by raw size or decision-space dimensions.The operation count uses the same primary operations and counting rules across families.
  • Algorithm-grounded workload levels: Levels 1–4 use operation-count bands [2^15, 2^17], [2^19, 2^21], [2^22, 2^24], and [2^24, 2^26], respectively.Adjacent bands are designed to remain clearly separable, with strict within-family increases between Levels 3 and 4.
  • Evaluation summary: Table 2 summarizes performance on all 240 algorithmic worlds using means and sample standard deviations over three trials.Bold entries identify the best performance.

5. Experiments and Analysis

Across AlgoWorlds, LLMs are usually feasible but rarely globally optimal, and sufficient information does not eliminate the decision gap. Performance varies sharply by task family and workload, while paired tool interfaces produce broadly stable outcomes.

  • Main results: 38.61% is the highest exact-optimality rate, achieved by Claude Opus 4.8, despite feasibility reaching 96.25%.GPT-5.6 Sol is similarly feasible at 97.50% but has 38.19% exact optimality.
  • Main results: Information sufficiency exceeds exact optimality for every model, while discovery coverage exceeds 96% for five of seven models.GPT-5.6 Sol reaches 99.10% discovery coverage, indicating that information acquisition alone does not explain the optimality gap.
  • Main results: Only 41.6% of GPT-5.6 Sol’s informative trajectories reach the optimum, while 56.3% end in feasible but suboptimal decisions.Across all seven models, feasible but suboptimal outcomes are the largest category among informative trajectories.
  • Task families: Exact-optimality varies widely across task families: Basket Assembly reaches 100% for four models, while five other tasks remain below 10% for every model.Station Siting spans 0.0%–98.6%, Fleet Dispatch 6.9%–94.4%, and Authorization Planning 0.0%–72.2%.
  • Task families: The contrast between Transit Routing and Basket Assembly suggests that exact-algorithm asymptotic complexity alone does not explain family-level performance differences.LLMs perform significantly better on Basket Assembly even though its exact algorithm includes an exponential factor.
  • Workload levels: At L4 versus L1, reference utility declines by about 8–29% and exact optimality declines by 1.1–7.7% across models.Workload levels are assigned from exact-algorithm primitive operations independently of model trajectories.
  • Tool interfaces: Direct-minus-Mediated exact-optimality differences are positive for all models, ranging from +0.6% to +6.4%, but outcomes are broadly stable across interfaces.Only GPT-5.6 Sol and Claude Sonnet 5 have 95% confidence intervals excluding zero.

6. Limitations

The study’s scope and diagnostic assumptions constrain how broadly its findings should be interpreted. Its evaluation uses a limited model set, formally generated worlds, and predefined sufficient-information sets.

  • The experiments cover seven leading LLMs, so results may reflect biases inherent in those models.
  • The benchmark characterizes LLMs using information tools, while code execution or external optimization solvers might improve performance.
  • Formally generated worlds omit real-world noise, ambiguity, temporal fluctuations, and instances with multiple global optima.
  • Trajectory diagnostics may undercount sufficient information because their predefined information sets do not cover every method for determining the optimum.

7. Conclusion

AlgoWorlds benchmarks whether tool-using LLM agents can convert information about hidden optimization instances into globally optimal decisions. Across the benchmark, leading models often remain feasible but fail to achieve exact optimality.

  • AlgoWorlds evaluates whether LLM agents can turn tool-acquired information into globally optimal decisions.
  • The benchmark contains 120 hidden instances from ten combinatorial optimization families and four workload levels, presented through paired Direct and Mediated interfaces as 240 worlds.
  • 38.61%: Claude Opus 4.8’s exact-optimality score, despite significantly higher feasibility.
  • The findings indicate that sufficient information and task-constraint adherence do not necessarily produce consistent global optimization.

A. A Worked Fleet Dispatch Pair

The worked Fleet Dispatch pair separates hidden instance information, model-visible tools, and final decision evaluation. The benchmark uses paired interfaces, exact optimization procedures, and independent checks to preserve equivalent, verifiable worlds.

  • Fleet Dispatch pair: The worked instance contains 14 jobs and five vehicles, with Direct and Mediated worlds sharing the same underlying information.
  • Fleet Dispatch pair: The agent sees the question, tool schemas, call costs, and access budget, but not the hidden instance or validation records.
  • Fleet Dispatch pair: The hidden instance includes loads, eligible assignments, capacities, route costs, and activation costs; the objective sums route, activation, and decision-independent offset terms.
  • Fleet Dispatch pair: The first five tools reveal instance information, while evaluate_assignment gives one nonterminal candidate-mapping evaluation and submit_assignment records the binding final decision.
  • Formal optimization procedures: Across formal families, global coupling can arise from shared constraints, modular residues, transfers, or relationships linking multiple decisions.
  • Formal optimization procedures: Exact algorithms retain sufficient state information to compute optima, reconstruct decisions, and justify correctness through recurrence or independent verification.
  • Validation: All 240 worlds pass optimal-decision and reference-decision checks, using equality-based exact-optimality verification for integer-valued objectives.

E.2. Acquisition and Information-Separation Checks

The benchmark formalizes sufficient information as normalized instance facts that reconstruct a hidden instance and recover its verified optimum, then validates acquisition plans, information separation, and paired interfaces.

  • Acquisition and normalization: Sufficient information reconstructs the hidden instance and lets the family-specific algorithm recover its independently verified optimum.Normalized facts are obtained by parsing, joining, removing interface-specific content, and deduplicating tool responses.
  • Acquisition and normalization: Each world has two alternative acquisition plans, and all 480 plans execute successfully and are sufficient.The plans are validation objects rather than prescribed acquisition strategies, and they need not be necessary or minimal.
  • Information separation: Validated plans draw facts from multiple information channels, so decision-relevant information is distributed across the interface.A channel is a validation grouping by information type, not necessarily a single tool, field, record, or response.
  • Information separation: 648 world–channel counterfactual checks pass, with each tested channel capable of changing the optimal decision.The checks do not establish that every fact in a channel is necessary or that the channel is required to reconstruct every instance.
  • Information separation: 1,464 selected-response checks pass, showing that none of the tested responses alone determines the optimum.This finite result does not extend to every possible request, argument, or response, and it is not an information-theoretic lower bound.
  • Paired-interface equivalence: All 120 Direct–Mediated pairs recover the same hidden instance while retaining structurally different relational records before normalization.The paired worlds therefore share feasible decisions, the objective function, and the verified optimum, while model performance need not be identical.

F. Metric Accounting and Secondary Diagnostics

The benchmark separates final-decision quality from trajectory diagnostics and computes reported statistics through trial-first aggregation, with explicit conventions for missing or non-finalized decisions.

  • Conditional outcomes: Information-sufficient trajectories classify final decisions as globally optimal, feasible but suboptimal, or other failure.The other-failure group combines infeasible decisions, absent final decisions, and protocol violations.
  • Conditional outcomes: Conditional percentages are computed within trials and then averaged across trials, and they describe outcomes within the information-sufficient subset rather than causal effects of acquisition.Information sufficiency concerns information contained in tool responses, not whether the agent recognized or correctly used it.
  • Secondary diagnostics: Normalized regret is zero at the optimum and increases with the decision’s gap relative to a fixed suboptimal reference.Among feasible non-exact decisions, median and 90th-percentile regret are computed within each trial before arithmetic averaging across trials.
  • Trajectory diagnostics: Trajectory diagnostics measure information sufficiency and entity grounding rather than treating raw tool use as decision quality.Entity grounding is identifier overlap with model-visible responses and does not establish sufficient information or correct use of costs and constraints.
  • Operational diagnostics: Spend and executed-call summaries describe tool use and expenditure, not an efficiency score.Spend is aggregated as the mean of per-world percentages, with conditional spend averaged only over evaluations meeting the stated condition.

G. Executed-Work Accounting and Calibration

AlgoWorlds calibrates workload using reproducible operation counts from family-specific construction algorithms, while explicitly limiting what those counts represent.

  • Work accounting: Work(ℐ) sums five equally weighted operation categories recorded during each hidden instance’s construction algorithm.Independent verification and later validation checks do not contribute to the work record.
  • Work accounting: The counters measure executed operations, not the full candidate space or a worst-case complexity bound.Counting rules are family-specific; within a family, all hidden instances use the same construction algorithm and accounting rules.
  • Calibration: Workload bands are assigned from recorded operations, while analytic complexity parameters guide family-specific size and structural settings.Calibration is fixed before model evaluation, and model outcomes do not enter the workload assignment.
  • Calibration: 35,646 to 53,964,927 operations span the released instances, a factor of about 1.5 × 10^3.Table 16 reports ranges over three hidden instances at each family–workload-level setting; paired worlds share their instance’s work record.
  • Interpretive scope: The work record is reproducible for this benchmark but depends on the chosen exact algorithm and accounting convention.It does not measure wall-clock time, information-tool use, access cost, or an algorithm-independent lower bound.

H. Operational Protocol and Record Integrity

The evaluation protocol fixes the model–world–trial design, tool-access controls, and record-finalization rules so that each scheduled evaluation yields one auditable trajectory record.

  • Evaluation design: Each model is evaluated in three trials over the same 240 worlds, producing 720 scheduled evaluations per model and 5,040 across seven models.The worlds comprise 120 hidden instances presented through Direct and Mediated interfaces, and are reused across models and trials.
  • Interaction protocol: Agents receive the question, tool schemas, tool costs, and access budget but not the hidden instance, verified optimum, or sufficient information sets.Parallel tool calls are disabled, so each response is recorded before the next call.
  • Interaction protocol: Each trajectory allows at most 255 executed information-tool calls and at most one zero-cost final-decision call.Candidate-evaluation calls count toward the information-call cap; rejected calls do not count or incur benchmark cost.
  • Interaction protocol: The agent-facing suite excludes general-purpose code execution and optimization solvers, including the exact algorithms used for construction and validation.Those exact algorithms are therefore not exposed to evaluated agents.
  • Record integrity: A finalized record is created for every scheduled evaluation, including the trajectory and its metrics, even when no final decision is submitted.Provider and network attempts are separate request records and do not enter trajectory outcomes or cap-termination counts.
  • Record integrity: Integrity checks require validated world and experiment identifiers, content digests, and 240 finalized records for every model–trial pair.Empirical tables use only records that pass the stated manifest checks.

I. Supplementary Experimental Results

Supplementary analyses show that feasible-but-suboptimal decisions dominate most models’ outcomes, including among information-sufficient trajectories. Decision quality is therefore distinct from information sufficiency and feasibility.

  • Final-decision outcomes: Feasible but suboptimal decisions are the largest outcome category for six of seven models; Qwen instead has more infeasible decisions.
  • Decision quality: Sol, Opus, Sonnet, and Terra have mean trial-specific median regrets below 1.0 among feasible non-exact decisions.The reported means are 0.214, 0.354, 0.357, and 0.526, respectively.
  • Informative trajectories: Among information-sufficient evaluations, feasible but suboptimal decisions remain the largest final-decision category for all seven models.

I.2. Task-Level Reference Utility and Discovery Coverage

Task-level and diagnostic analyses show that high information discovery can coexist with poor decision quality, while workload increases generally reduce performance. Repeated-trial and interface analyses further qualify these patterns.

  • Task-level quality: 99.2% discovery coverage corresponds to reference utilities of 0.0 for Qwen and 4.2 for DeepSeek in Authorization Planning.Fleet Dispatch contrasts with this pattern: all seven models have discovery coverage of at least 95.8% and reference utility of at least 80.1.
  • Workload-level patterns: All seven models have lower exact optimality and reference utility at L4 than at L1.Reference utility decreases at every successive level for six models; DeepSeek partially recovers at L4 while remaining below its L1 value.
  • Interface analysis: The Direct–Mediated interface comparison is limited to 120 validated matched pairs and does not establish a Direct advantage for other interface designs.Only GPT-5.6 Sol and Claude Sonnet 5 have 95% intervals excluding zero.
  • Repeated trials: Pairwise agreement measures repeatability of binary exact-optimality status, not exact-optimality rate or agreement in submitted decisions and objective values.Qwen has 95.0% pairwise agreement but achieves exact optimality in all three trials on only four worlds.
  • Tool-use diagnostics: High discovery coverage does not establish correct use of returned costs and constraints, because discovery coverage and entity grounding measure information overlap rather than decision quality.GLM’s mean discovery coverage is 93.91% while its mean entity grounding is 70.82%.
Loading 2608.29397v1…