Abstract

Tool-use benchmarks generally evaluate whether an agent completes a workflow using appropriate tools and valid arguments. However, feasibility alone is insufficient in 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. AlgoWorlds evaluates whether LLM agents can turn information acquired through tools into globally optimal decisions. It transforms formally specified combinatorial optimization problems into partially observed decision environments with verifiable global optima. Each environment contains a hidden optimization instance that the agent observes only through sequential calls to task-specific information tools. The agent may then commit at most one structured decision, which an independent family-specific checker evaluates for feasibility and objective value; exact optimality is determined against a separately verified optimum. Family-specific deterministic programs generate 120 hidden instances, while exact algorithms certify their global optima and determine their workload levels. Each instance is exposed through paired Direct and Mediated interfaces that preserve the same decision problem under different information presentations, yielding 240 algorithmic worlds across ten optimization families and four workload levels. Independent offline checks confirm the optima and paired-interface equivalence. Across seven leading LLMs, the best-performing model reaches exact optimality in only 38.61% of cases. Even when recorded trajectories contain 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.

Exact-optimality rates for seven evaluated LLMs; GPT-5.6 Sol evaluations divided by information sufficiency, with the sufficient subset broken down by final-decision outcome; and a Transit Routing case where a feasible 24-leg route has 9.6% lower travel time but 241.5% higher transfer cost than the certified optimum, producing an objective 63.3% higher. — Sufficient information does not guarantee global optimality.View full-size figureScroll horizontally to inspect the figure.

Results

Exact optimality, the primary metric, remains low for every evaluated model: mean rates range from 5.42% for Qwen 3.5 Plus to 38.61% for Claude Opus 4.8, with GPT-5.6 Sol close behind at 38.19%. By contrast, Opus and Sol produce feasible decisions in 96.25% and 97.50% of evaluations, respectively. Information sufficiency and discovery coverage are also higher than exact optimality for every model.

Observed exact-optimality rates vary substantially across optimization families. Every model records lower exact optimality and reference utility at L4 than at L1, although the intermediate levels are not uniformly monotonic. Workload indexes the executed work of the offline exact methods; it is not a deterministic ranking of LLM difficulty.

Sufficient information does not guarantee global optimality

For GPT-5.6 Sol, 647 evaluations have trajectories satisfying information sufficiency. Of these, 41.6% reach the global optimum, 56.3% end in a feasible but suboptimal decision, and 2.2% are infeasible. Information sufficiency means that joint normalization of the recorded fact-revealing responses recovers at least one verified sufficient fact set in full; it does not establish that the agent recognized, reconstructed, or correctly used that information.

Globally optimal: 41.6%
Feasible but suboptimal: 56.3%
Infeasible: 2.2%

Overall Performance

Models are ranked by mean exact optimality across three trials on the same set of 240 algorithmic worlds. Values are the mean ± sample standard deviation of the trial-level summaries.

Model	Final-decision metrics			Trajectory diagnostics
Model	Exact optimality	Feasibility	Reference utility	Information sufficiency	Discovery coverage
AnthropicClaude Opus 4.8	38.61 ± 4.65	96.25 ± 2.89	73.14 ± 11.81	81.53 ± 8.74	97.33 ± 1.45
OpenAIGPT-5.6 Sol	38.19 ± 1.34	97.50 ± 0.00	74.98 ± 1.77	89.86 ± 0.64	99.10 ± 0.13
AnthropicClaude Sonnet 5	32.36 ± 3.85	92.08 ± 0.83	67.20 ± 9.53	86.39 ± 7.36	98.59 ± 1.08
OpenAIGPT-5.6 Terra	26.39 ± 1.34	87.78 ± 0.87	54.10 ± 1.95	79.72 ± 3.13	96.65 ± 0.25
Z.aiGLM 5.2	24.86 ± 0.64	64.58 ± 3.15	35.48 ± 2.67	83.33 ± 3.82	93.91 ± 1.49
DeepSeekDeepSeek V4 Pro	16.11 ± 1.05	83.89 ± 1.34	28.49 ± 0.91	79.58 ± 1.67	97.74 ± 0.11
QwenQwen 3.5 Plus	5.42 ± 0.42	48.89 ± 1.73	15.82 ± 0.87	37.92 ± 1.25	81.55 ± 0.42

Exact optimality, feasibility, information sufficiency, and discovery coverage are percentages; reference utility is reported as 100 × U. Bold marks the highest mean in each metric and does not imply statistical significance.

Benchmark Details

An algorithmic world combines a textual decision problem, a hidden optimization instance, and a suite of task-specific tools with per-call costs and a total access budget. The agent receives the question, tool schemas, per-call costs, and access budget—but not the hidden instance—and may submit at most one terminal structured decision.

AlgoWorlds contains 120 hidden instances across ten formally specified combinatorial optimization families and four algorithm-grounded workload levels. Each instance is presented through paired Direct and Mediated interfaces that preserve the question, tool-call costs, access budget, and final-decision format while changing the relational organization of the returned information.

Benchmark Structure

Hidden instances: 120
Algorithmic worlds: 240
Optimization families: 10
Algorithm-grounded workload levels: 4
Paired interfaces per instance: 2
Terminal structured decision: ≤1

Data Quality

Before model evaluation, every world is checked for scoring validity, in-budget information access, and paired-interface equivalence.

hidden instances with independently confirmed unique optima: 120
algorithmic worlds passing scoring checks: 240
validated in-budget acquisition plans: 480
channel-level counterfactual checks: 648
response-level counterfactual checks: 1,464
equivalent Direct–Mediated pairs: 120

Benchmark Construction

For each optimization family, construction proceeds in three stages.

01
Deterministic instance generation
A human-written deterministic generator produces each hidden instance from explicit size and structural parameters.
02
Exact solution and workload calibration
A family-specific exact algorithm solves each instance and records the executed work used to assign one of four shared workload levels.
03
Tool-mediated world construction
The same hidden instance is exposed through paired Direct and Mediated interfaces with fixed call costs and an access budget.

Optimization Families

Each family defines its decision space, hidden instance data, exact solution method, and suite of information tools. Tool counts exclude the final-decision tool.

Task family	Decision	Instance data	Exact solution method	Information tools
Transit Routing	One route leg per stage	Stage-specific legs, travel times, line labels, directed transfer costs, and residues	Residue and last-line dynamic program	6
Basket Assembly	A ticket set forming an exact cover	Requirements, ticket-item incidence, and prices	First-uncovered-item bitmask dynamic program	5
Station Siting	One site per zone	Shared capacity, site costs, and bounded-span pairwise demand rewards	Resource-aware band-frontier dynamic program	4
Authorization Planning	A package sequence	Authorization relations, policy adjustments, handoffs, and clearance residue	Product-state dynamic program	6
Series Portfolio	One lot per title	Lot values, scopes, and overlapping signed factors	Bounded-span factor dynamic program	6
Machine Layout	A machine-to-slot permutation	Machine flows, a unit-spaced slot order, and placement adjustments	Cut-identity subset dynamic program	8
Sequential Matching	An ordered perfect matching	Compatibility, pair costs, and directed handoffs	Used-set and last-match dynamic program	6
Fleet Dispatch	A job-to-vehicle assignment	Job loads, eligible vehicle-job pairs, capacities, route costs, and activation costs	Mixed-radix capacity dynamic program	6
Evidence-Joined Routing	A layered source-to-target path	Layered graph with source and target, quantities, exceptions, tariffs, and residues	Expanded-state shortest path	6
Migration Portfolio	One package per component group and an activated domain set	Package costs, support domains, activation costs, and signed interactions	Activated-domain mask enumeration	8

What Each World Requires

These capabilities are jointly required; AlgoWorlds evaluates the resulting trajectory and decision without attributing an individual failure to any single stage.

01
Information acquisitionSelect sequential information calls under positive per-call costs and a fixed access budget.
02
Cross-tool integrationJoin entities, relations, constraints, and objective terms distributed across returned records.
03
Coupled optimizationCompare complete decisions whose components interact through shared constraints and aggregate costs.
04
Final verificationCheck feasibility and objective value before committing a terminal structured decision, which can be submitted at most once.

Evaluation Metrics

Three final-decision metrics score the submitted decision, while two trajectory diagnostics characterize the decision information recoverable from fact-revealing tool responses. The diagnostics do not establish that the agent recognized, reconstructed, or correctly used that information.

Aspect	Metric	Definition
Final decision	Exact optimality	Binary; the decision is feasible and attains the verified global optimum. This is the primary metric.
Final decision	Feasibility	Binary; the family-specific checker accepts the submitted structured decision as feasible.
Final decision	Reference utility	A feasible decision receives U in [0,1]; results report 100 × U, so the global optimum is 100 and the fixed suboptimal reference decision is 0.
Trajectory	Information sufficiency	Binary; joint normalization of the fact-revealing tool responses recovers at least one verified sufficient fact set in full.
Trajectory	Discovery coverage	The largest fraction, in [0,1], of any verified sufficient fact set recovered through joint normalization of the fact-revealing tool responses.