Technical Summary: OPT-BENCH

Problem Statement

While Large Language Models (LLMs) have demonstrated remarkable capabilities in reasoning and tool use, their fundamental cognitive faculties—perception, reasoning, and memory—are often evaluated through static, single-pass benchmarks. These evaluations overlook the critical human capability of iterative self-optimization: the ability to continuously refine solutions in response to dynamic environmental feedback. Existing benchmarks primarily measure a model's ability to generate correct responses in one attempt or focus on task completion via tool use, failing to assess whether agents can adapt through intrinsic self-reflection rather than rote memorization or brute-force computation. There is a lack of a unified framework to evaluate how agents navigate complex search spaces by learning from experience, specifically distinguishing between continuous optimization and discrete combinatorial reasoning.

Methodology

OPT-BENCH: The Benchmark

To address this gap, the authors introduce OPT-BENCH, a comprehensive benchmark designed to evaluate self-improvement capabilities in large-scale search spaces. It integrates 30 distinct tasks divided into two contrasting feedback landscapes:

1. Continuous Parametric Optimization (ML Tasks): 20 real-world Machine Learning tasks sourced from Kaggle. These tasks involve continuous search spaces where feedback provides noisy but directional gradients (e.g., improving validation accuracy or reducing MSE).
2. Discrete Combinatorial Reasoning (NP Tasks): 10 classic NP-hard problems (e.g., Hamiltonian Cycle, Traveling Salesman Problem, Graph Coloring). These represent discrete combinatorial spaces characterized by brittle constraints and local optima, where feedback is often binary (Valid/Invalid) or provides specific error traces without directional gradients.

The benchmark establishes rigorous baselines:

• Lower Bound: A "Random Rollout" where the agent generates solutions without historical context (memory-less).
• Upper Bound: Human Expert Baselines, derived from Kaggle Gold Medal solutions for ML tasks and Human-Expert Heuristics (e.g., Simulated Annealing) for NP tasks, representing a reasoning ceiling rather than brute-force optima.

OPT-Agent: The Evaluation Framework

The authors propose OPT-Agent, a framework emulating a human-like cognitive adaptation loop consisting of Perception–Memory–Reasoning. Unlike complex agent architectures relying on engineered prompts or external solvers, OPT-Agent operates through three iterative phases:

1. Drafting (Initialization): The agent generates an initial hypothesis (a Python script for ML, a discrete structure for NP) to kickstart the optimization.
2. Improving (Refinement): Upon finding a valid solution, the agent retrieves historical context (past code/paths, metrics, feedback trends) to perform inductive reasoning (adjusting hyperparameters) or deductive logic (refining discrete structures).
3. Debugging (Correction): When the environment returns a failure signal (runtime error or constraint violation), the agent analyzes error logs to diagnose faults and recover from invalid states.

Experimental Setup

The study evaluates 19 LLMs from 7 model families, ranging from 3B to 235B parameters, including proprietary models (e.g., GPT-4o, Claude-3.5), reasoning models (e.g., o3-mini, Deepseek-V3.1-Thinking), and open-source models. The evaluation metrics include:

• Win Count: The number of tasks where the agent outperforms the memory-less baseline.
• Improvement Rate (IR): The relative performance gain over the baseline.
• Expert Gap (EG): The normalized distance between the agent's final solution and the human expert baseline.
• Buggy Rate: The proportion of invalid solution attempts.

Key Results

1. Scaling Law of Self-Improvement

A strong correlation exists between model scale and self-optimization capability. Larger models are significantly more effective at leveraging historical feedback. For instance, in ML tasks, the 72B parameter model (Qwen2.5-72B) achieves an Expert Gap of 0.45, whereas the 7B model only reaches 0.20. Smaller models often perceive complex error traces as noise due to limited semantic working memory, while larger models exhibit emergent capabilities for multi-step inductive reasoning.

2. Divergence Between Continuous and Discrete Domains

The paper reveals a fundamental divergence in how LLMs handle different search spaces:

• Continuous (ML) Domains: Strong models function effectively as inductive optimizers. They interpret numerical feedback as directional gradients to guide self-optimization. Proprietary models like GPT-4o achieve dominant Win Counts (18/2) over random baselines, confirming that performance gains stem from purposeful, history-driven refinement.
• Discrete (NP) Domains: Environmental feedback yields diminishing returns. Discrete error signals (e.g., "Invalid Cycle") lack directional gradients, making it difficult for models to translate them into structural repairs. Consequently, self-optimization often degenerates into "random search with memory." Even frontier models struggle with incremental refinement in combinatorial spaces, frequently resetting solutions rather than repairing them.

3. The Role of Reasoning Models

Reasoning models (those utilizing Chain-of-Thought) consistently outperform general instruction-tuned models, particularly in NP tasks. For example, Deepseek-V3.1-Thinking achieves a 0.00 buggy rate and the highest Expert Gap (~0.79) in NP tasks. This suggests that CoT reasoning is essential for maintaining global topological consistency and verifying solution validity, a capability often lacking in standard models.

4. Temperature and Exploration

The study finds that optimal temperature settings differ by domain:

• ML: Deterministic decoding ($T=0$) maximizes performance by strictly adhering to directional feedback signals.
• NP: Moderate stochasticity ($T=0.2$) often yields lower buggy rates by helping agents escape local optima in "rugged" landscapes, whereas $T=0$ can cause fixation on invalid structural patterns.

Significance and Claims

The paper claims that OPT-BENCH provides a rigorous setting to assess whether agents can adapt through intrinsic self-reflection rather than rote tool application. The primary contributions are:

1. A New Benchmark: Juxtaposing continuous (ML) and discrete (NP) tasks to evaluate intrinsic self-optimization, moving beyond single-pass correctness.
2. A Cognitive Framework: Introducing OPT-Agent to simulate the human perception-memory-reasoning loop, enabling the assessment of how models leverage historical environmental feedback.
3. Empirical Insights: Revealing that while strong models excel at inductive optimization in continuous spaces, they face fundamental reasoning barriers in discrete combinatorial refinement.

The authors conclude that a significant gap persists between even the strongest LLMs and Human Expert performance. Current "Self-Optimization" appears to be essentially a local search mechanism bounded by the model's inherent reasoning depth. Achieving true autonomous optimization requires global planning and high-level reasoning capabilities that current models have not yet fully mastered, marking a key direction for future AGI research. The paper modestly notes that current results are limited by the 30-task scope and the exclusion of the very latest model releases (e.g., Gemini 3, GPT-5) due to resource constraints.