AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

Zixiang Xu; Jiaan Wang; Fandong Meng

cs.CLAug 29, 2026

AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

Authors: Zixiang Xu, Jiaan Wang, Fandong Meng

Organizations: Weixin AI, Tencent · University of Southern California

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.

Figures & tables

Panel of Figure 1 — Figure 1: Sufficient information does not guarantee global optimality. (a) Exact-optimality rates for the seven evaluated LLMs. (b) In the evaluation of GPT-5.6 Sol, trajectories are initially categorized based on whether they gather sufficient information. Those that meet this criterion are further classified according to their final-decision results. (c) An example evaluation of GPT-5.6 Sol on Transit Routing. The trajectory gathers sufficient information and ends with a feasible, albeit non-optimal, route.

Task family	Decision $y$	Instance data in $\mathcal{I}$	Exact solution method	$\|\mathcal{T}_{\mathrm{info}}\|$
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

Table 1: The ten optimization families in AlgoWorlds .

	Final-decision metrics			Trajectory diagnostics
Model	Exact optimality	Feasibility	Reference utility	Information sufficiency	Discovery coverage
Qwen 3.5 Plus	5.42 $\pm$ 0.42	48.89 $\pm$ 1.73	15.82 $\pm$ 0.87	37.92 $\pm$ 1.25	81.55 $\pm$ 0.42
DeepSeek V4 Pro	16.11 $\pm$ 1.05	83.89 $\pm$ 1.34	28.49 $\pm$ 0.91	79.58 $\pm$ 1.67	97.74 $\pm$ 0.11
GLM 5.2	24.86 $\pm$ 0.64	64.58 $\pm$ 3.15	35.48 $\pm$ 2.67	83.33 $\pm$ 3.82	93.91 $\pm$ 1.49
GPT-5.6 Terra	26.39 $\pm$ 1.34	87.78 $\pm$ 0.87	54.10 $\pm$ 1.95	79.72 $\pm$ 3.13	96.65 $\pm$ 0.25
GPT-5.6 Sol	38.19 $\pm$ 1.34	97.50 $\pm$ 0.00	74.98 $\pm$ 1.77	89.86 $\pm$ 0.64	99.10 $\pm$ 0.13

Table 2: Performance on all 240 algorithmic worlds in AlgoWorlds . Entries are the mean

\pm

sample standard deviation over three trials. Bold marks the best performance.

	Information sufficiency	Three final results in informative trajectories
Model		Globally optimal	Feasible but suboptimal	Other failure
Qwen 3.5 Plus	37.9	3.3	49.9	46.8
DeepSeek V4 Pro	79.6	17.8	69.4	12.8
GLM 5.2	83.3	26.0	40.5	33.5
GPT-5.6 Terra	79.7	29.2	59.8	11.0
GPT-5.6 Sol	89.9	41.6	56.3	2.1

Table 3: Information sufficiency and the final results in informative trajectories.

Task family	Terra	Sol	Qwen	DeepSeek	Opus	Sonnet	GLM
Transit Routing	0.0	1.4	0.0	0.0	0.0	0.0	0.0
Basket Assembly	100.0	100.0	47.2	88.9	100.0	100.0	97.2
Station Siting	83.3	98.6	0.0	8.3	97.2	90.3	58.3
Authorization Planning	18.1	72.2	0.0	4.2	62.5	59.7	19.4
Series Portfolio	0.0	0.0	0.0	0.0	9.7	1.4	0.0
Machine Layout	1.4	1.4	0.0	0.0	4.2	0.0	0.0

Table 4: Performance across task families (in terms of exact optimality). The pale teal color represents the magnitude of the scores, and the bold indicates the row-best value.

	Workload level
Model	L1	L2	L3	L4
GPT-5.6 Terra	27.2 / 68.4	30.6 / 61.0	21.7 / 47.2	26.1 / 39.8
GPT-5.6 Sol	42.2 / 87.8	38.9 / 81.3	35.0 / 69.2	36.7 / 61.7
Qwen 3.5 Plus	4.4 / 20.3	10.0 / 17.1	4.4 / 15.3	2.8 / 10.6
DeepSeek V4 Pro	19.4 / 35.9	18.3 / 27.6	11.7 / 22.3	15.0 / 28.1
Claude Opus 4.8	44.4 / 84.0	41.1 / 76.7	32.2 / 69.8	36.7 / 62.1

Table 5: Performance across workload levels (in terms of exact optimality / reference utility).

	Exact-optimality comparison				Matched outcomes
Model	Direct	Mediated	$\Delta_{\mathrm{D-M}}$	95% paired bootstrap interval	Direct wins	Mediated wins	Ties
GPT-5.6 Terra	27.2	25.6	+1.7	$[-1.9,+5.3]$	19	13	328
GPT-5.6 Sol	40.6	35.8	+4.7	$[+1.4,+8.3]$	25	8	327
Qwen 3.5 Plus	6.1	4.7	+1.4	$[-0.8,+3.9]$	11	6	343
DeepSeek V4 Pro	16.4	15.8	+0.6	$[-1.9,+3.1]$	15	13	332
Claude Opus 4.8	39.2	38.1	+1.1	$[-1.7,+3.9]$	17	13	330

Table 6: Matched Direct–Mediated exact-optimality results. Direct and Mediated are mean rates (%) across three trials, and

\Delta_{\mathrm{D-M}}

is their difference in percentage points. Direct wins, Mediated wins, and ties count the 360 matched instance–trial pairs for each model. The intervals are 95% paired bootstrap confidence intervals for

\Delta_{\mathrm{D-M}}

; complete statistical details appear in Section I.4 .

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Tool	Arguments	Returned information or effect	$f_{c}(t)$
read_fleet_policy	None	Vehicle capacities and the complete vehicle and job rosters	2
read_job	One job	Its load and eligible vehicles, without route costs	1
read_vehicle_contract	One vehicle	Its fixed activation cost, without capacity or assigned jobs	4
read_route_row	One vehicle	Interface-specific route records associated with that vehicle	3
read_dispatch_window	Start job and length 2 or 3	Loads, eligible vehicles, and interface-specific route records for consecutive jobs	14
evaluate_assignment	One complete mapping	Feasibility and, when feasible, its objective value	5

Appendix

Table 7: The available tools in the worked Fleet Dispatch pair. The first five reveal instance information. evaluate_assignment provides nonterminal feedback and may be used once, whereas submit_assignment records the binding final decision.

Task family	Principal scale-bearing quantities	Structure producing global coupling
Transit Routing	Numbers of stages, candidate legs, and lines	Residue condition and directed transfer costs between consecutive lines
Basket Assembly	Item-group and ticket-catalog sizes	Ticket–item incidence and exact-cover overlap
Station Siting	Numbers of zones and demand relations	Shared site-count constraint and bounded-span pairwise demand terms
Authorization Planning	Numbers of stages, packages, and authorized transitions	Authorized transitions, handoffs, and the global clearance residue
Series Portfolio	Numbers of titles, lots, and factors	Overlapping bounded factor scopes
Machine Layout	Numbers of machines and slots	Permutation feasibility and pairwise flow terms

Appendix

Table 8: Scale-bearing quantities and global-coupling structures represented by the ten formal problem families. The entries summarize semantic roles in the formal instances rather than a complete list of generator arguments; the exact algorithms and their complexity parameters are specified in Appendices B and G .

Construction artifact	Template action	Paired-world relation and agent visibility
Hidden instance $\mathcal{I}$	Supplies the constraints, objective terms, and case-specific values	Shared by the paired worlds and not provided directly to the agent.
Textual question $q$	Instantiates the family task statement and the public identifiers needed to describe and submit a decision	Identical in the paired worlds and provided to the agent.
Private interface records	Maps the fields of $\mathcal{I}$ into the relational records queried by an interface’s tools	Organized differently in the Direct and Mediated worlds; selected records appear only through executed tool responses.
Information tools $\mathcal{T}_{\mathrm{info}}$	Defines the callable operations, argument schemas, and record queries	The agent receives the tool schemas and the responses to executed calls, but not the complete private record collection.
Cost function $f_{c}$ and budget $b$	Assigns per-call costs and the total amount available for one trajectory	Identical in the paired worlds and provided to the agent.
Final-decision tool $t_{\mathrm{dec}}$	Defines the family’s structured decision format and records the submitted decision	Identical in the paired worlds; its schema is provided to the agent, and an executed call commits the final decision.

Appendix

Table 9: Components used or instantiated by a family-specific world-construction template. Paired worlds share the decision problem and agent-facing task conditions while using different private relational organizations for the instance information.

Task family	Independent verification algorithm
Transit Routing	Represents the computation as exhaustive relaxation over the dense stage–line–residue graph rather than as the construction run’s ordered predecessor scan.
Basket Assembly	Uses a forward-mask recurrence over the tripartite coverage state rather than the first-uncovered-item recurrence.
Station Siting	Uses a top-down recurrence with the generic at-most- $H$ capacity semantics rather than the construction run’s saturation reduction.
Authorization Planning	Uses a reverse suffix recurrence rather than the forward prefix recurrence.
Series Portfolio	Scans from right to left and closes each factor at its leftmost position rather than scanning left to right and closing it at its rightmost position.
Machine Layout	Builds the layout from the first slot by choosing the next machine rather than choosing the final machine of each prefix.

Appendix

Table 10: Independent verification algorithms used to validate the optima produced by the ten construction algorithms.

Task family	Info. groups	Sufficient set size	Call count	Call cost	Budget / exhaustive	Algorithmic work
Transit Routing	3	1,755–6,963	59–147	226–634	524–884 / 637–1,558	50,737–47,619,285
Basket Assembly	2	262–640	38–180	172–764	260–780 / 1,020–2,554	35,646–39,098,995
Station Siting	2	284–326	172–234	558–774	577–779 / 915–1,293	55,391–34,318,974
Authorization Planning	3	2,633–7,781	17–73	99–291	120–296 / 729–1,257	43,747–35,313,268
Series Portfolio	2	381–1,458	24–141	196–924	1,228–1,924 / 1,491–5,658	54,587–34,402,415
Machine Layout	3	444–1,300	10–42	93–370	129–377 / 963–3,166	111,668–46,226,237

Appendix

Table 11: Information and access scale by task family. Sufficient-information-set size, call count, and call cost range over 48 world–call-list combinations (two validated call lists for each of 24 worlds); call cost excludes the candidate-feedback reserve. Budget and exhaustive-catalog cost are separate world-level ranges. Algorithmic work ranges over the 12 underlying hidden instances, whose paired worlds inherit the same value defined in Equation 6 .

Validated property	Validation unit	Count	Pass criterion
Fixed construction membership	Hidden instance	120	Each predetermined family–level–index coordinate yields its reproducible instance.
Optimum agreement and uniqueness	Hidden instance	120	The construction and independent verification algorithms agree on the optimal decision and value and confirm a unique optimum.
Decision checking	Algorithmic world	240	The checker accepts the verified optimal decision and reproduces its objective value.
Reference decision	Algorithmic world	240	The reference is feasible and has $\Delta_{w}^{\mathrm{ref}}>0$ .
Sufficient information acquisition	Acquisition plan	480	The responses reconstruct $\mathcal{I}$ , recover its verified optimum, span multiple information channels, and fit within budget with the candidate-evaluation reserve and within the information-call cap.
Full-catalog budget	Algorithmic world	240	Issuing every request in the finite fact-revealing catalog exceeds $b$ .

Appendix

Table 12: Offline validation in AlgoWorlds . Every listed unit passes its row’s criterion. Counts use the validation unit shown in each row.

Quantity	Per-evaluation value	Within-trial summary
Exact optimality	$E_{w}(y)\in\{0,1\}$ ; one only for a feasible decision at the verified optimum.	Percentage with value one.
Feasibility	$F_{w}(y)\in\{0,1\}$ ; one when the family-specific checker accepts the submitted decision.	Percentage with value one.
Reference utility	$U_{w}(y)\in[0,100]$ , defined in Equation 4 .	Arithmetic mean on its $0$ – $100$ scale.
Information sufficiency	$C_{w}(\tau)\in\{0,1\}$ ; one when the information-tool responses contain at least one sufficient information set in full.	Percentage with value one.
Discovery coverage	$D_{w}(\tau)\in[0,1]$ ; the largest fraction of any sufficient information set contained in those responses.	Arithmetic mean multiplied by 100.

Appendix

Table 13: Per-evaluation values and within-trial aggregation for the three final-decision metrics and two trajectory diagnostics.

Counter	Executed operation represented
$N_{\mathrm{state}}$	A recurrence, graph, frontier, subset, or mask state visited by the exact algorithm.
$N_{\mathrm{transition}}$	A predecessor, successor, assignment, or other candidate transition examined from a state.
$N_{\mathrm{check}}$	A feasibility, capacity, compatibility, residue, or other constraint condition checked during the computation.
$N_{\mathrm{update}}$	An update to a stored objective or dynamic-programming value.
$N_{\mathrm{reconstruct}}$	A component of the structured optimal decision recovered during reconstruction.

Appendix

Table 14: The five operation categories summed by

\operatorname{Work}(\mathcal{I})

in Equation 6 .

Task family	Complexity parameters	Worst-case running time
Transit Routing	Stages $d$ , legs per stage $k$ , lines $p$ , and residue modulus $M$	$O(p^{2}\log p+dk^{2}M)$
Basket Assembly	Items per group $n$ and examined ticket extensions $\Delta$	$O(2^{3n}\Delta)$
Station Siting	Zones $n$ , counter range $\bar{H}+1$ for $\bar{H}=n-H$ , and frontier width $\omega$	$O(n(\bar{H}+1)2^{\omega}(\omega+1))$
Authorization Planning	Residue modulus $M$ and authorization-graph vertex and edge counts $V,E$	$O(M(V+E))$
Series Portfolio	Titles $n$ , factor span $\omega$ , and factors closing per position $f_{\omega}$	$O(n2^{\omega}(1+f_{\omega}))$
Machine Layout	Machines $n$ and machine-subset states	$O(n2^{n})$

Appendix

Table 15: Complexity parameters and worst-case running times for the family-specific exact algorithms. Workload levels use recorded operations rather than these bounds.

Task family	Level 1	Level 2	Level 3	Level 4
Transit Routing	50,737–54,053	1,132,766–1,201,734	8,922,755–9,191,138	45,715,806–47,619,285
Basket Assembly	35,646–56,392	773,416–1,558,838	6,430,549–7,063,570	32,683,874–39,098,995
Station Siting	55,391–55,424	1,196,297–1,214,030	5,829,214–6,245,492	34,289,268–34,318,974
Authorization Planning	43,747–44,176	994,240–999,048	7,036,179–7,045,627	35,238,569–35,313,268
Series Portfolio	54,587	973,647	6,698,087	34,402,415
Machine Layout	111,668–113,178	1,093,813–1,107,918	10,405,214–10,470,928	46,053,123–46,226,237

Appendix

Table 16: Executed algorithmic-work ranges over the three hidden instances at each family–workload-level setting. A singleton is shown when all three records coincide.

Model	Model ID / API	Thinking / reasoning	Output cap	Temperature
GPT-5.6 Terra	gpt-5.6-terra Responses API	reasoning.effort=max	128K	Omitted
GPT-5.6 Sol	gpt-5.6-sol Responses API	reasoning.effort=max	128K	Omitted
Qwen 3.5 Plus	qwen3.5-plus Chat Completions API	thinking=true; budget=81,920	65,536	0.6
DeepSeek V4 Pro	deepseek-v4-pro-202606 Chat Completions API	thinking=true; reasoning_effort=max	128K	Omitted
Claude Opus 4.8	claude-opus-4-8 Anthropic Messages API	adaptive thinking; effort=max	128K	Omitted
Claude Sonnet 5	claude-sonnet-5 Anthropic Messages API	adaptive thinking; effort=max	128K	Omitted

Appendix

Table 17: Model-specific request settings used in the reported experiments. The output cap is the returned-output token limit applied to each model request, not a trajectory-level token budget, and is distinct from any internal thinking budget. Here, K denotes 1,024 tokens, and Qwen’s listed thinking budget is also measured in tokens. All models use a configuration with thinking or reasoning enabled. Temperature is marked Omitted when no explicit temperature value was supplied in the reported request configuration.

Panel of Figure 2 — Figure 2: Mean exact-optimality and information-sufficiency rates over three trials on the same fixed worlds. Each line connects the two overall rates for one model. The figure does not condition final decisions on information sufficiency within the same evaluation. Across-trial standard deviations appear in Table 2 , and repeated-trial profiles appear in Table 22 .

Model	Globally optimal	Feasible suboptimal	Infeasible	No decision	Protocol violation
GPT-5.6 Terra	63.3	147.3	29.3	0.0	0.0
GPT-5.6 Sol	91.7	142.3	6.0	0.0	0.0
Qwen 3.5 Plus	13.0	104.3	121.7	0.0	1.0
DeepSeek V4 Pro	38.7	162.7	33.7	5.0	0.0
Claude Opus 4.8	92.7	138.3	5.7	3.3	0.0
Claude Sonnet 5	77.7	143.3	17.7	1.3	0.0

Appendix

Table 18: Mean counts by final-decision category per 240-world trial, averaged across the three trials. The five categories partition the evaluation records before rounding. Protocol violations remain separate from infeasible structured decisions and absent final decisions.

Model	Reference utility	Median regret	90th percentile regret	Globally optimal	Better than reference	Reference or worse	Infeasible, absent, or protocol violation
GPT-5.6 Terra	54.10 $\pm$ 1.95	0.526	1.582	63.3	91.3	56.0	29.3
GPT-5.6 Sol	74.98 $\pm$ 1.77	0.214	1.000	91.7	119.3	23.0	6.0
Qwen 3.5 Plus	15.82 $\pm$ 0.87	1.000	4.277	13.0	30.7	73.7	122.7
DeepSeek V4 Pro	28.49 $\pm$ 0.91	1.000	2.582	38.7	55.7	107.0	38.7
Claude Opus 4.8	73.14 $\pm$ 11.81	0.354	1.000	92.7	107.0	31.3	9.0
Claude Sonnet 5	67.20 $\pm$ 9.53	0.357	0.973	77.7	118.7	24.7	19.0

Appendix

Table 19: Reference-normalized decision quality. Utility is the mean

\pm

sample standard deviation across three trial-level means; regret entries average the trial-specific quantiles among feasible non-exact decisions; and outcome columns are mean counts per 240-world trial. Better than reference means normalized regret strictly between zero and one, whereas reference or worse means normalized regret at least one. The four outcome columns partition each trial before rounding; the final column combines infeasible, absent, and protocol-violation outcomes.

	Conditioning count	Final-decision outcomes
Model	Information sufficiency	Globally optimal	Feasible suboptimal	Infeasible	No decision	Protocol violation
GPT-5.6 Terra	191.3	56.0	114.3	21.0	0.0	0.0
GPT-5.6 Sol	215.7	89.7	121.3	4.7	0.0	0.0
Qwen 3.5 Plus	91.0	3.0	45.3	42.3	0.0	0.3
DeepSeek V4 Pro	191.0	34.0	132.7	21.3	3.0	0.0
Claude Opus 4.8	195.7	71.7	116.3	4.3	3.3	0.0

Appendix

Table 20: Mean counts by final-decision category among evaluations satisfying information sufficiency. Each count is computed within a 240-world trial and then averaged across three trials, so the five decision columns sum to the information-sufficiency count in each row up to rounding.

	Reference utility / discovery coverage
Task family	Terra	Sol	Qwen	DeepSeek	Opus	Sonnet	GLM
Transit Routing	40.0/90.6	77.1/98.4	0.5/55.2	3.6/98.2	53.5/98.2	19.8/99.7	1.3/98.6
Basket Assembly	100.0/99.3	100.0/99.5	59.0/80.9	91.6/98.7	100.0/89.6	100.0/95.7	98.5/94.8
Station Siting	88.8/94.9	99.9/100.0	2.5/48.7	10.0/99.1	98.8/95.6	92.1/96.3	59.5/97.9
Authorization Planning	18.9/96.9	75.6/100.0	0.0/99.2	4.2/99.2	65.0/100.0	65.7/100.0	19.4/98.6
Series Portfolio	20.8/96.9	34.5/100.0	0.2/68.2	1.2/100.0	48.9/100.0	49.6/98.3	7.4/98.6

Appendix

Table 21: Task-level reference utility and discovery coverage. Within each trial, each task-family slice contains 24 worlds. Each cell reports the mean across the three trial-level reference-utility means, followed by the mean across the three trial-level discovery-coverage percentages. Reference utility is on its

[0,100]

scale, whereas discovery coverage is a percentage. These are marginal task-level summaries of decision quality and the information contained in the recorded tool responses.

	Trial exact-optimality rate			Trials attaining exact optimality per world				Pairwise agreement
Model	T1	T2	T3	0/3	1/3	2/3	3/3
GPT-5.6 Terra	27.9	25.4	25.8	164	8	22	46	91.7
GPT-5.6 Sol	39.2	38.8	36.7	135	16	8	81	93.3
Qwen 3.5 Plus	5.8	5.4	5.0	218	9	9	4	95.0
DeepSeek V4 Pro	17.1	16.2	15.0	187	14	15	24	91.9
Claude Opus 4.8	33.3	40.4	42.1	127	18	25	70	88.1

Appendix

Table 22: Repeated-execution profiles on the same fixed worlds in AlgoWorlds . T1–T3 are exact-optimality rates in percent. Columns 0/3 through 3/3 count worlds on which the model attains exact optimality in that many trials. For each pair of trials, pairwise agreement is the percentage of the 240 fixed worlds whose binary exact-optimality statuses agree; the table reports the mean over the three trial pairs. The four frequency counts sum to 240 worlds, and together with pairwise agreement describe binary exact-optimality repeatability on this fixed suite, not agreement in objective value or submitted decision.

	Trajectory-level summaries			Tool use	Conditional and termination summaries
Model	Discovery	Grounding	Sufficiency	Calls	Exact given sufficiency	Info.-call cap	Budget cap
GPT-5.6 Terra	96.65	100.00	79.72	54.9	29.24	0.0	0.0
GPT-5.6 Sol	99.10	100.00	89.86	57.4	41.57	0.0	0.0
Qwen 3.5 Plus	81.55	97.91	37.92	34.6	3.31	0.0	0.0
DeepSeek V4 Pro	97.74	97.27	79.58	69.0	17.82	2.0	0.7
Claude Opus 4.8	97.33	98.60	81.53	58.2	36.33	3.3	0.0

Appendix

Table 23: Trajectory-level, tool-use, conditional, and termination summaries. Discovery coverage and information sufficiency are the two trajectory diagnostics defined in Section 3.4 ; entity grounding is a secondary diagnostic defined in Appendix F . Each numerical entry is the mean of the three trial-level summaries. These three quantities and conditional exact optimality are percentages. Calls are mean executed information-tool calls per evaluation; information-call- and budget-cap terminations are mean counts per 240-world trial.

	Overall acquisition			Conditional spend
Model	Calls	Spend	Spend / budget	Given information sufficiency	Given exact optimality
GPT-5.6 Terra	54.9	335.4	68.1%	360.1	367.3
GPT-5.6 Sol	57.4	448.2	80.6%	464.0	323.8
Qwen 3.5 Plus	34.6	291.9	66.5%	273.4	311.7
DeepSeek V4 Pro	69.0	424.5	83.0%	455.1	335.4
Claude Opus 4.8	58.2	367.6	73.3%	353.7	328.9

Appendix

Table 24: Descriptive acquisition accounting. Calls and spend follow Equation 49 : they include candidate-evaluation calls when executed and exclude the final-decision tool and calls rejected before execution. Calls, spend, and spend relative to budget are computed per evaluation, averaged within each trial, and then averaged across three trials. Spend and both conditional-spend columns are in benchmark cost units; spend/budget is instead the mean of the per-world percentages. Conditional columns are likewise computed within each trial for evaluations satisfying information sufficiency or exact optimality and then averaged across the three trials; they are not efficiency scores or estimates of a spending effect.

Field	Recorded trajectory
Archetype	Tool responses do not contain a sufficient information set in full
World	Station Siting, Mediated, L2, instance 1; DeepSeek V4 Pro, trial 2
Recorded calls	read zone window (8); read zone (3); read demand (11)
Final result	No final decision; discovery coverage 35.0%.
Archetype	Sufficient information, infeasible
World	Evidence-Joined Routing, Mediated, L1, instance 2; GPT-5.6 Terra, trial 1

Appendix

Table 25: Three examples drawn from recorded trajectories. The recorded-call rows give a compact inventory of tool names and counts in first-use order, include the final-decision submission when one occurs, and exclude private reasoning text. They do not reproduce the full call sequence and are not the

N_{\mathrm{call}}

diagnostic, which excludes

t_{\mathrm{dec}}

. The examples illustrate distinct information-availability and final-decision outcomes; corresponding aggregate results appear in Tables 2 , 3 , 19 and 23 . They are illustrative examples rather than estimates of outcome prevalence.

AI Agent Benchmarks

AI agent benchmarks measure how reliably autonomous systems plan, use tools, interact, and complete tasks across controlled and real-world settings.

See all 1,482 papers

Feb 25, 2026

ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization

Large language models are increasingly applied to operational decision-making where the underlying structure is constrained optimization. Existing benchmarks evaluate whether LLMs can formulate optimization problems as solver code, but leave open a complementary question. Can LLMs directly produce correct solutions to fully specified constrained optimization problems without access to a solver? We introduce ConstraintBench, a benchmark for evaluating LLMs on direct constrained optimization across 10 operations research domains, with all ground-truth solutions verified by the Gurobi solver. Each task presents a natural-language scenario with entities, constraints, and an optimization objective; the model must return a structured solution that a deterministic verifier checks against every constraint and the solver-proven optimum. We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck. The best model achieves only 65.0% feasibility, yet feasible solutions average 89 to 96% of the Gurobi-optimal objective. No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference. Per-domain analysis shows large variation in difficulty, with average feasibility spanning from 85.0% in the facility location domain to 0.8% in the crew assignment domain. Further, systematic failure modes include duration constraint misunderstanding, entity hallucination, and a feasibility-optimality decoupling in facility location and vehicle routing where models achieve high feasibility but 0% optimality. ConstraintBench and all evaluation infrastructure will be publicly released.

Joseph Tso, Preston Schmittou, Quan Huynh +1

Haladir Research Team

Constraint-Guided Reasoning in Language Models Constrained Optimization LLM Reasoning Operations Research

Ask PDF

Aug 20, 2026

Reachable Global Optimization in AI Systems: How Global Is Global?

AI systems increasingly claim to optimize prompts, policies, architectures, plans, tool-use trajectories, reasoning traces, and test-time computation. This paper argues that such claims are underspecified unless they state the region actually reachable by the system that performed the optimization. We introduce Reachability-Induced Optimization (RIO), a model in which a generator, verifier, controller, memory, tools, and budget induce a reachable candidate region. The returned solution is therefore a best visited point, an approximate reachable optimum, or an exact global optimum only when additional certificates relate the reachable region to the full formal space. We prove reachable-optimality, false-globality, gap- decomposition, certificate, escape, pruning, and control-value results. The full benchmark record contains 66,150 executed trials over six known-optimum landscape families, seven control policies, 270 landscapes, and 35 runs per landscape-method. The online appendix includes raw trial records, aggregate tables, figures, benchmark code, validation scripts, and checksums. The results show that control can restrict, expand, or misdirect reachability, and that optimization quality, reachability quality, and control reliability must be reported separately.

Wesley Shu

The Institute of Energetic Paradigm

Global Optimization Reachability Analysis

Ask PDF

Jul 12, 2026

Opti-Agent-Bench: Benchmarking End-to-End Optimization R&D Agents on Real-World Business Problems

LLM-based agents are increasingly deployed to solve optimization problems, yet existing benchmarks evaluate them on pre-structured mathematical formulations that bypass the most critical challenge: translating complex business requirements into correct models and solve efficiently. We introduce Opti-Agent-Bench, an end-to-end benchmark that evaluates Large Language Models (LLMs) across the complete optimization R&D pipeline, from understanding business-language descriptions through mathematical modeling, algorithm selection, and code implementation, to solution report generation. Our design rests on three pillars: (1) businesssemantic authenticity with anti-template traps that defeat pattern matching; (2) modular evaluation with cross-module consistency checking across Problem Understanding, Formal Modeling, Implementation, and Reporting; and (3) the ORAC bi-level validity framework that simultaneously ensures task quality and scoring integrity. Across several industrialscale tasks spanning integer programming, robust optimization, stochastic programming, and non-convex optimization, we expose critical failure modes of current models, including constraint omission, model-code inconsistency, and report-implementation divergence, that remain invisible under conventional single-metric evaluation.

Yongchang Fu, Xinjie Huang, Chengjun Dai +3

Ding Talk, Alibaba Group, Hangzhou, China · Zhejiang University, Hangzhou, China

Large Language Model-Guided Optimization LLM Agent Evaluation AI Agent Benchmarks Natural Language to Optimization Modeling Operations Research

Ask PDF

Abstract

AI Agent Benchmarks

Explore similar work

ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization

Reachable Global Optimization in AI Systems: How Global Is Global?

Opti-Agent-Bench: Benchmarking End-to-End Optimization R&D Agents on Real-World Business Problems