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

Wesley Shu

cs.AIAug 20, 2026

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

Authors: Wesley Shu

Organizations: The Institute of Energetic Paradigm

Abstract

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.

Figures & tables

Level	Name	Meaning
1	Exact global optimum	Best over full formal space $\mathcal{X}$
2	Constrained global optimum	Best over explicit set $K\subseteq\mathcal{X}$
3	Reachable global optimum	Best over $\mathcal{X}_{R}(\mathcal{A},\mu_{0},T)$
4	Operational global stability	Stable low-cost behavior under perturbation
5	Local attractor	Stable but possibly suboptimal basin
6	False globality	Reachable/local result reported as exact global

Table 1: Levels of globality in AI optimization claims.

Method	Mean gap	Median gap	Exact rate	True basin	False globality	Crosses	Probes
reckless escape	0.120	0.000	0.926	0.944	0.043	7.51	0.00
random full	0.148	0.040	0.366	0.991	0.004	0.00	0.00
oracle probe	0.524	0.177	0.281	0.882	0.096	0.72	7.98
gated escape	0.587	0.168	0.290	0.930	0.075	2.88	7.99
hard prune	3.183	2.943	0.206	0.207	0.770	0.00	0.00
local repair	3.186	2.943	0.205	0.207	0.770	0.00	0.00

Table 2: Overall benchmark results over 66,150 executed trials.

Family	Reckless	Full rnd.	Oracle	Gated	Prune	Local	Reach rnd.
bridge bad	0.994	0.371	0.993	0.989	0.989	0.987	0.629
bridge good	0.972	0.367	0.130	0.121	0.000	0.000	0.000
deceptive no signal	0.898	0.361	0.071	0.111	0.000	0.000	0.000
multi basin	0.892	0.363	0.120	0.170	0.067	0.067	0.041
shifting barrier	0.884	0.363	0.211	0.213	0.156	0.156	0.102
sparse signal	0.917	0.369	0.161	0.135	0.022	0.022	0.014

Table 3: Exact-global rate by family and method.

Signal-quality bin	Mean gap	Exact-global rate
(0.0529, 0.267]	0.792	0.120
(0.267, 0.506]	0.993	0.144
(0.506, 0.765]	0.395	0.267
(0.765, 0.842]	0.417	0.408
(0.842, 0.949]	0.335	0.510

Table 4: Signal-quality bins for the gated escape policy.

Certificate	Required evidence	Supported claim
Visited-set	all evaluated candidates and scores	best visited
Reachable-set	proof over $\mathcal{X}_{R}$	reachable optimum
Coverage	$\mathcal{X}_{R}=\mathcal{X}$	exact global if optimized
Containment	$x^{\star}\in\mathcal{X}_{R}$	exact global if found
Complement	lower bound on $\mathcal{X}\setminus\mathcal{X}_{R}$	exact global if bound dominates

Table 5: Certificate types and the claim they support.

Family	Reckless	Full rnd.	Oracle	Gated	Prune	Local	Reach rnd.
bridge bad	0.003	0.181	0.003	0.005	0.005	0.006	0.041
bridge good	0.078	0.127	0.643	0.576	7.150	7.150	7.184
deceptive no signal	0.199	0.149	0.792	0.704	3.214	3.214	3.254
multi basin	0.143	0.145	0.586	0.505	2.626	2.649	2.636
shifting barrier	0.137	0.156	0.517	0.462	2.529	2.520	2.520
sparse signal	0.160	0.134	0.604	1.267	3.577	3.577	3.616

Table 6: Mean global gap by family and method. Lower is better.

Family	Reckless	Full rnd.	Oracle	Gated	Prune	Local	Reach rnd.
bridge bad	0.000	0.000	0.000	0.000	0.000	0.000	0.009
bridge good	0.011	0.000	0.001	0.000	1.000	1.000	1.000
deceptive no signal	0.069	0.005	0.221	0.121	1.000	1.000	1.000
multi basin	0.057	0.004	0.134	0.075	0.889	0.889	0.890
shifting barrier	0.060	0.010	0.145	0.066	0.778	0.778	0.781
sparse signal	0.064	0.004	0.074	0.187	0.956	0.956	0.959

Table 7: False-globality risk by family and method. Lower is better.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Family	Reckless	Full rnd.	Oracle	Gated	Prune	Local	Reach rnd.
bridge bad	0.994	0.371	0.993	0.989	0.989	0.987	0.629
bridge good	0.972	0.367	0.130	0.121	0.000	0.000	0.000
deceptive no signal	0.898	0.361	0.071	0.111	0.000	0.000	0.000
multi basin	0.892	0.363	0.120	0.170	0.067	0.067	0.041
shifting barrier	0.884	0.363	0.211	0.213	0.156	0.156	0.102
sparse signal	0.917	0.369	0.161	0.135	0.022	0.022	0.014

Appendix

Table 8: Method-level exact-global rates by landscape family (appendix repetition).

Global Optimization

Global optimization seeks the best solution across an entire search space, including nonconvex problems with many local optima.

See all 36 papers

AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds
Aug 29, 2026Zixiang Xu, Jiaan Wang, Fandong MengAI Agent Benchmarks Global Optimization
Weixin AI, Tencent · University of Southern California
The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows
Aug 7, 2026Junbo Li, Boyi Liu, Canwen Xu +5Large Language Model-Guided Optimization LLM Agent Workflow Optimization
The University of Texas at Austin · Snowflake
optimize_anything: A Universal API for Optimizing any Text Parameter
May 19, 2026Lakshya A Agrawal, Donghyun Lee, Shangyin Tan +11Black-Box Optimization Large Language Model-Guided Optimization
UC Berkeley USA · MIT USA

Aug 29, 2026J/K move · Enter open · S save

AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

Zixiang Xu, Jiaan Wang, Fandong Meng

Weixin AI, Tencent · University of Southern California

AI Agent Benchmarks Global Optimization Tool Use Combinatorial Optimization Operations Research Language Modeling

Open paper AskPDF arXiv

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.

Abstract

Global Optimization

Explore similar work

AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows

optimize_anything: A Universal API for Optimizing any Text Parameter