PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Wesley Shu

arXiv:2609.27855v1cs.AI

TL;DR

AI optimization claims are underspecified when they do not state which candidates were reachable to the optimizing system. The paper introduces RIO to model that region and the evidence needed to support claims about globality. Its benchmark shows that control can restrict, expand, or misdirect reachability, while the benchmark’s finite known-optimum landscapes bound the scope of its evidence.

  • Problem

    AI systems often claim optimization over a formal candidate space without specifying the subset their actual search process can reach.

    Source: §1 · pp. 1–2

  • Method

    RIO models how an AI control system and its budget induce a reachable candidate region and distinguishes evidence about that region from evidence about the full space.

    Source: §1 · p. 2, §3.1 · p. 3

  • Results

    Across the benchmark, control policies restrict, expand, or misdirect reachability, and local or hard-pruned methods show large mean global gaps and high false-globality risk.

    Source: §7.1 · pp. 9–10

  • Takeaways & Limitations

    Optimization reports should distinguish within-reachable performance, reachable-region quality, and evidence relating the reachable region to the full formal space.

    Source: §1 · p. 2, §17 · p. 17

    The benchmark uses finite known-optimum landscapes and does not establish that a particular EP-AI method dominates existing optimizers or that the theory resolves worst-case complexity.

    Source: §18 · p. 17

Abstract

from arXiv · show

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.

1 Introduction

AI optimization claims often describe a best result without specifying the subset of the formal candidate space the system could reach. Reachability-Induced Optimization (RIO) makes that induced region central to defining and evaluating such claims.

1 Introduction

  • AI systems often explore only candidates reachable through their generators, repair operators, verifiers, tools, memory, and compute budgets, rather than the full formal space.The paper argues that this mismatch makes many optimization claims stronger than their evidence supports.Source: §1 · pp. 1–2

1.1 Contributions

  • The contribution is a controlled-system model, claim distinctions and theorem families, a two-gap decomposition, control-value conditions, and a known-optimum benchmark with reproducibility materials.The benchmark record includes 66,150 trials across six landscape families, seven policies, and 270 landscapes.Source: §1.1 · p. 2

2 Positioning within Machine Learning

  • The paper treats the reachable region—not another optimizer—as the reporting object that licenses or invalidates globality claims across AI optimization settings.It connects this issue to verifier-guided reasoning and tool use, where candidates are generated, evaluated, and revised rather than exhaustively enumerated.Source: §2 · p. 3

3 Reachability-Induced Optimization

  • RIO models optimization as a coupled system that determines which candidates can be reached, not solely as an objective function.The system operates through candidate generation and evaluation under finite budget.Source: §3 · p. 3

3.1 Model primitives

  • A RIO instance specifies the formal space, cost, initialization distribution, finite budget, and AI control system that induces transitions over candidates.The control system includes components such as generation, boundary detection, repair, pruning, verification, memory, and action selection.Source: §3.1 · p. 3

3.2 Reachable region and returned candidate

  • The budgeted reachable region comprises candidates with nonzero probability of being visited, while a run’s visited set is only a subset of that region.The model distinguishes the reachable optimum from the exact optimum over the formal space and also defines an effective region using a probability threshold.Source: §3.2 · pp. 4–5

4 Levels of Globality

The paper distinguishes optimization claims by the space over which the returned candidate is best and by what evidence relates that space to the full formal space.

4 Levels of Globality

  • An exact global optimum is best over the full formal space, a constrained global optimum over a specified constraint set, and a reachable global optimum over the region induced by the AI system.Operational stability concerns perturbations within a returned low-cost region; it does not by itself establish global quality.Source: §4 · p. 5
  • False globality is reporting exact global optimality when evidence establishes only optimality over a reachable or sampled subset, local basin, or verifier-dependent region.The distinction keeps a claim’s scope aligned with the region actually supported by the evidence.Source: §4 · p. 5

5 Theoretical Results

The theoretical results separate within-reach optimization from reachability limits and specify when claims can be certified or control can change the reachable set. They also show that control is valuable only under conditions that outweigh its costs and misdirection risks.

5.1 Gap decomposition

  • The framework separates error from failing to optimize within the reachable region from the structural cost of that region itself.A large first term points to better search or scoring; a large second term points to exploration, tools, representations, initialization, or boundary crossing.Source: §5.1 · p. 6

5.2 Reachable optimality and exact globality

  • Reachable optimality does not establish exact global optimality; exactness requires full coverage, sufficient optimization within the reachable set, or a valid bound on the unreachable complement.A returned reachable optimum is globally optimal if its cost is no greater than a valid lower bound on every unreachable candidate’s cost.Source: §5.2 · p. 6

5.3 Control effects on reachability

  • Pruning can shrink reachable space, escape can expand it when prior transitions are preserved, and stability within an attractor does not imply global optimality.Each result concerns reachability or quality relative to regions outside the pruned set or stable attractor.Source: §5.3 · pp. 6–7

5.4 Control value and signal thresholds

  • Boundary-aware control has positive expected value only when expected pruning, repair or mutation, and verifier gains exceed detection, overhead, and misdirection costs.The control-value inequality is E[GP + GR + GV] > E[CD + CO + CM].Source: §5.4 · p. 7
  • Controlled escape requires a sufficiently informative signal to justify escape benefits against incorrect-escape and execution costs, while more compute after absorption need not expand reachability.An absorbing attractor confines subsequent visits to that attractor under the stated condition.Source: §5.4 · p. 7

6 Benchmark Design

The benchmark uses finite landscapes with known optima to measure how different policies affect reachability and false-globality. It records outcomes and search behavior across multiple landscape families, policies, and runs.

6 Benchmark Design

  • Exact enumeration of the finite candidate space provides the true optimum for each landscape, allowing false globality to be measured directly under different induced reachable regions.The benchmark is controlled by design so exact and reachable globality can be compared.Source: §6 · p. 8

6.1 Candidate space and landscapes

  • The landscapes use basin, barrier, and ripple components, with candidate space size |X| = 101 and construction controlling whether the optimum lies inside the initially reachable basin.These design choices enable exact global-optimum computation and vary the relation between the starting region and the optimum.Source: §6.1 · p. 8

6.2 Landscape families

  • Six landscape families test useful or harmful boundary crossing, competing basins, misleading or weak feedback, and variable barrier locations and values.The families are bridge_good, bridge_bad, multi_basin, deceptive_no_signal, sparse_signal, and shifting_barrier.Source: §6.2 · p. 8

6.3 Control policies

  • The benchmark includes local, pruning, reckless-escape, gated-escape, and oracle-probe policies; the gated policy probes after stagnation and crosses only when estimated improvement passes a gate.It otherwise remains in the known reachable basin and returns its best candidate at budget exhaustion.Source: §6.3 · p. 9

6.4 Metrics and scale

  • The study records best cost, global-optimality gap, exact-global success, true-basin reach, false-globality risk, probes, and boundary crossings across 66,150 trials.The record covers six families, seven methods, 45 landscapes per family, 35 runs per landscape-method, and a search budget of 45 per run.Source: §6.4 · p. 9

7 Benchmark Results

Across the benchmark, policy determines whether reachability is restricted, expanded, or misdirected; family and signal conditions qualify those overall comparisons. False-globality risk is concentrated in methods trapped within their reachable regions.

7.1 Overall results

  • Policies that cross boundaries or sample broadly reach better basins more often, while local and hard-pruned methods show mean global gaps near 3.2; no policy dominates everywhere.Reckless escape has the lowest mean global gap and highest exact-global rate, while gated escape depends on signal reliability.Source: §7.1 · pp. 9–10, Table 2 · p. 9

7.2 Family-level exact-global rates

  • In bridge_bad, local and hard-pruned policies do well, but in bridge_good the same policies fail when they cannot reach the true basin.The same optimization behavior can therefore be effective or ineffective depending on whether the reachable region contains the global basin.Source: §7.2 · p. 10, Table 3 · p. 10

7.3 Signal quality and gated escape

  • Higher signal-quality bins generally improve exact-global rate for gated escape, with the strongest rate in the high-signal region, though the pattern is not monotone in every bin.Family composition and landscape difficulty also vary across bins.Source: §7.3 · pp. 10–11, Table 4 · p. 11

7.4 False globality

  • False-globality risk is around 0.77 for reachable_random, local_repair, and hard_prune_ep, which often find good reachable candidates without reaching the true global basin.The paper names this failure mode as misrepresenting the best reachable candidate as globally optimal.Source: §7.4 · p. 11

8 Interpretation for AI Systems

Across AI systems, optimization quality, reachability quality, and control reliability are distinct, and a system's induced reachable region depends on its operational constraints. RIO applies this distinction to learning, prompt search, architectures, agents, and alignment.

8 Interpretation for AI Systems

  • A method can optimize well within its reachable space yet miss better basins, expand reachability with weak control, or rely on conditional control whose performance depends on signal reliability.The paper argues that mature optimization claims must report optimization quality, reachability quality, and control reliability separately.Source: §8 · p. 11

8.1 Reinforcement learning

  • A reinforcement-learning policy may be optimal within the region induced by its parameterization, exploration, reward feedback, and training dynamics without being globally optimal over all policies.The decomposition separates reachability error from optimization error.Source: §8.1 · pp. 11–12

8.2 Prompt optimization

  • Prompt-optimization reports should state the prompt grammar, mutation operators, objective, evaluation budget, and evidence that the reachable prompt region covers the intended search claim.The best prompt found is usually reachable-optimal rather than exact-optimal over all token sequences.Source: §8.2 · p. 12

8.3 Neural architecture search and AutoML

  • A selected neural architecture is best under the induced search process, not necessarily globally best over all possible architectures.Templates, mutation operators, hardware constraints, predictors, early stopping, and budgets induce the operational search space.Source: §8.3 · p. 12

8.4 Agent planning and tool use

  • Agent planning is control-relative because tool failures, invalid actions, memory limits, and repair policies define which action trajectories are reachable.States requiring unavailable tool access or memory across a required horizon may lie outside the practical reachable set.Source: §8.4 · p. 12

8.5 Alignment and verifier optimization

  • Alignment behavior stable under a reward model or verifier need not be exactly aligned across behavioral states, including under hidden objectives, adversarial prompts, or distribution shift.Source: §8.5 · p. 12

9 Why Reachability Is a Learning-System Variable

Reachability is induced by learning-system components such as representation, initialization, exploration, verifier access, tools, memory, and update rules, so systems facing the same formal task can reach different regions. The paper distinguishes reachability error from other sources of error and limits what visited-set performance establishes.

9 Why Reachability Is a Learning-System Variable

  • Two systems facing the same formal candidate space and objective can induce different reachable regions because reachability is produced by the learning system's design and dynamics.Source: §9 · p. 12

9.1 Approximation, estimation, optimization, and reachability

  • RIO adds reachability error to approximation, estimation, and optimization error, separating a reachability gap inside the model class from approximation and search/optimization gaps.The remedies differ: reachability failure calls for changes such as exploration, tools, initialization, transitions, or control, whereas optimization failure calls for better search, scoring, or budget allocation.Source: §9.1 · pp. 12–13

9.2 Reachability and induced support

  • For a stochastic optimizer, the reachable region after budget T is the union of trajectory supports across time; low final loss shows good visited states were found, not that the formal space lacks better ones.Promoting the best visited candidate to reachable or exact global optimality requires evidence of coverage or a certificate relating reachable and formal spaces.Source: §9.2 · p. 13

10 Certificate Taxonomy

The benchmark tests how landscape structure and policy affect global gaps, false-globality risk, and stability. RIO also distinguishes certificate strengths and specifies what the benchmark records to assess these outcomes.

10 Certificate Taxonomy

  • RIO distinguishes five certificates, from best among evaluated candidates to bounds on every unreachable point that can validate exact globality.The taxonomy also includes reachable-set, coverage, and containment certificates; claims should match the strongest certificate supplied.Source: §10 · pp. 13–14, Table 5 · p. 14

11 Mechanism-Level Predictions

  • The benchmark tests predictions that trapped policies can be stable yet globally poor, while escape can expand reachability but become misdirected without reliable signals.Gated exploration has value only when its signal is informative enough to outweigh probing and misdirection costs; broad random search remains a baseline when signals are unreliable.Source: §11 · p. 14

12 Statistical and Experimental Reporting

  • The benchmark uses known optima and family-conditional estimates to expose effects that aggregate averages can hide, and provides trial-level records for recomputing results.Exhaustive enumeration of X = {0, . . . , 100} makes false globality observable; raw records permit stratification by family and signal-quality bins.Source: §12 · pp. 14–15

13.1 Mean global gap by landscape family

  • Local and hard-pruned methods are nearly optimal in bridge_bad but fail strongly in bridge_good, where crossing is necessary.This contrast separates local optimization quality from reachable-region quality.Source: §13.1 · pp. 15–16, Table 6 · p. 15

13.2 False-globality risk by family

  • False-globality risk is highest when a method is stable inside the wrong basin.The table reports risk by family and method.Source: Table 7 · p. 15, §13.2 · p. 16

13.3 Stability versus globality

  • Near-perfect perturbation stability can coexist with high global gaps because stability certifies persistence within a region, not its optimality over the full space.A local attractor may remain stable while being globally poor.Source: §13.3 · p. 16

14 Failure Modes

RIO identifies failure modes arising from restricted, pruned, or misdirected reachability and offers guidance for evaluating optimization claims. Its benchmark has a finite known-optimum scope and does not establish that a particular EP-AI method dominates existing optimizers.

14 Failure Modes

  • Reachability collapse, overpruning, and misdirected escape can respectively trap search in a small basin, remove better regions, or cross boundaries without improving the result.Other failure modes include proxy-verifier globality, coverage illusion, and stability illusion.Source: §14 · p. 16

15 What Would Falsify or Narrow the Model

  • The model would be narrowed if trapped methods did not concentrate false-globality risk or reachability-expanding policies did not change true-basin reach across barriers.Gated improvements regardless of signal quality would also weaken the proposed control-value mechanism.Source: §15 · p. 16

16 Practical Guidance for Reviewers and Builders

  • Reviewers should identify the formal and reachable spaces, classify the claimed optimum, and check whether a matching certificate supports the claim.The audit also separates within-reachable error from reachability gap and examines how control changes reachability.Source: §16 · p. 17

17 Reporting Standard for Optimization Claims

  • Reports should specify the candidate space, reachable set or sampling process, budget, objective, policy, supporting evidence, and claimed level of optimality.They should also state evidence relating the reachable set to the formal space and expected failure modes under sparse, deceptive, or shifted feedback.Source: §17 · p. 17

18 Limitations

  • The benchmark uses finite known-optimum landscapes and does not prove that a particular EP-AI method dominates existing optimizers.The authors call for applying the reporting standard to realistic optimization settings.Source: §18 · pp. 17–18

19 Reproducibility and Online Appendix

The paper treats optimization as system-dependent: a controller’s reachable set can differ from the formal candidate space, so exact-global claims require additional proof. It supplies benchmark records and reporting materials for examining that distinction.

19 Reproducibility and Online Appendix

  • The reproducibility record covers six landscape families, seven control policies, 45 landscapes per family, 35 runs per landscape-method, and 66,150 trials.The true optimum for each landscape is computed by exhaustive enumeration of the discrete candidate space.Source: §19 · p. 18

20 Conclusion

  • Exact globality depends on the reachable set and control-signal reliability; control can restrict, expand, stabilize, or misdirect search.The conclusion distinguishes reachable optimization from exact-global claims, which require additional proof relating the reachable region to the formal space.Source: §20 · p. 18

A Additional Definitions and Proof Details

  • Reachability ordering compares systems by set inclusion, but a larger reachable set need not improve optimization because it can dilute sampling or increase misdirection.Reachability quality separately reflects how close the reachable set comes to globally optimal candidates.Source: A Additional Definitions and Proof… · p. 19
  • Reachable optimization differs from ordinary constrained optimization because initialization, policy, tools, memory, feedback, and budget induce its feasible region.Changing these system components can change the reachable set.Source: A Additional Definitions and Proof… · p. 19

B Benchmark Tables

  • Table 8 is identified as reporting method-level exact-global rates by landscape family, while the text describes the benchmark tables as diagnostic.The supplied passages give the table’s scope but no cell values.Source: Table 8 · p. 19, B Benchmark Tables · p. 19

C Appendix Inventory

  • The online appendix lists raw trial and landscape files, processed aggregate and stability tables, benchmark and validation code, figures, and checksums.The trial file contains 66,150 executed trials, and the landscape metadata file covers 270 known-optimum landscapes.Source: C Appendix Inventory · pp. 19–20

D Full Benchmark Protocol

The benchmark combines known-optimum landscapes with mechanisms designed to vary reachability and signal quality. Its control analysis treats gains, costs, and signal reliability as conditions on whether control has positive value.

D Full Benchmark Protocol

  • The protocol generates 45 landscapes per family, enumerates each exact optimum, runs seven methods 35 times under budget T = 45, and records outcomes and diagnostics.Results are aggregated by method and family-method condition.Source: D Full Benchmark Protocol · p. 20

D.1 Landscape semantics

  • The six landscape families test basin trapping, unnecessary escape, competing basins, misleading or sparse signals, and shifting barriers.These designs probe reachability limits and feedback sensitivity under different landscape conditions.Source: §D.1 · pp. 20–21

D.2 Method semantics

  • The seven-policy design varies reachability deliberately: local methods restrict it, reckless escape expands it, gated escape depends on a signal threshold, and random_full provides broad sampling.oracle_probe_ep approximates an upper-bound policy with cleaner probe information.Source: §D.2 · p. 21

E.1 Detailed proof of the control-value inequality

  • Control has positive value only when expected gains from pruning, repair or mutation, and verifier information exceed detection, overhead, and misdirection costs.The decomposition is a bookkeeping identity, not evidence that adding control is inherently beneficial.Source: §E.1 · p. 21

E.2 Detailed proof of the signal threshold

  • Gated escape has positive value only when signal reliability exceeds a cost-adjusted threshold balancing beneficial escapes against misleading signals and probe costs.The threshold condition is pB+ > (1 - p)B- + CE.Source: §E.2 · p. 21

E.3 Reachability gap under conservative policies

The section explains how restricted reachability can leave a positive globality gap even under perfect within-region optimization, and connects that risk to claim reporting and benchmark interpretation.

E.3 Reachability gap under conservative policies

  • If a conservative policy stays within an initial basin whose best point is worse than an outside candidate, every reachable optimum has a strictly positive globality gap.Perfect optimization inside the basin cannot close this structural gap; bridge_good instantiates the trap for local and hard-pruned methods.Source: §E.3 · p. 22

E.4 False-globality risk as a conditional probability

  • False-globality risk captures candidates that are good within their final basin or reachable region but are not exact global optima.This error mode can support an unjustified global claim despite plausible local success.Source: §E.4 · p. 22

F Additional Reporting Template

  • The reporting template asks systems to specify their formal space, objective, verifier, generator, transitions, budget, reachability evidence, optimization evidence, failure modes, and certificate.It calls for claims to be supported by visited-set, reachable-set, coverage, containment, or complement evidence.Source: F Additional Reporting Template · pp. 22–23

G Connection to Practical Learning Pipelines

  • Across hyperparameter tuning, prompt search, program repair, planning, and hypothesis generation, the reachable region is shaped by system interfaces and proposal mechanisms.A best reachable candidate need not be the best candidate in the full formal space.Source: G Connection to Practical Learning… · p. 23

H Why This Paper Is Not a Leaderboard Claim

  • The benchmark maps mechanisms rather than declaring a universal policy winner: local methods can be trapped, escape expands reachability, and gates depend on signal quality.Random full search is strong under poor signals, while exact-global success requires broad coverage or reliable reachability expansion.Source: H Why This Paper Is Not a Leaderboard… · p. 23

I Online Appendix Integrity

  • The online appendix pairs raw trial records with integrity checksums and validation scripts that trace aggregate claims back to the records.The authors present this audit path as necessary for a paper about disciplined optimization claims.Source: I Online Appendix Integrity · p. 24
Loading 2609.27855v1…