ALE-Bench: A Benchmark for Automated Optimization with LLM-Based Evolutionary Approaches

20.1 Overview & Motivation

ALE-Bench [arXiv:2506.09050] is a combinatorial optimization benchmark constructed from 40 problems drawn from the AtCoder Heuristic Contest (AHC) series. Developed collaboratively by Sakana AI and AtCoder, it targets a specific evaluation gap: the absence of a standardized, continuous-scoring benchmark for assessing LLM-based agents on open-ended heuristic optimization — problems where provably optimal solutions are computationally intractable and solution quality is measured on a continuous scale rather than binary pass/fail [PAPER §1–3].

20.1.1 The Evaluation Gap

Prior to ALE-Bench, LLM evaluation for optimization-adjacent tasks fell into two categories, neither adequate for heuristic algorithm design [PAPER §3]:

• Exact-solution benchmarks (HumanEval, MBPP, APPS, SWE-bench): Binary pass/fail evaluation on well-specified coding problems. These cannot distinguish a mediocre feasible solution from an exceptional one, and their problem space admits known-optimal algorithms.
• Classical optimization test suites (TSPLIB, CVRPLIB): Single problem-class instances evaluated in isolation, lacking the diversity and iterative-refinement measurement needed for general-purpose optimization agent assessment.

ALE-Bench addresses this by sourcing problems from competitive programming heuristic contests, which provide: (a) calibrated difficulty distributions from 500–1,500+ human participants per problem; (b) diversity across logistics, scheduling, placement, network, simulation, and geometric categories; (c) continuous scoring functions enabling fine-grained quality differentiation; and (d) NP-hard problem instances with search spaces on the order of 10²⁰⁰, reflecting real industrial optimization complexity [PAPER §3–4].

20.1.2 Survey Positioning

Within this survey's taxonomy, ALE-Bench occupies a distinctive niche. Unlike FunSearch (Chapter 11), which evolves single scoring functions within fixed program skeletons, or AlphaEvolve, which targets multi-file algorithm design with massive compute budgets, ALE-Bench provides a standardized evaluation framework — a benchmark rather than a system. Its companion agent (ALE-Agent) demonstrates one approach to the benchmark but is not the benchmark's primary contribution. This distinction is critical for survey readers: ALE-Bench's lasting value lies in its problem suite, scoring infrastructure, and human performance baselines, not in any particular agent architecture [PAPER §1].

20.1.3 Attribution

The collaboration is strategically notable. Takuya Akiba (Sakana AI co-founder) previously created Optuna, one of the most widely used hyperparameter optimization frameworks. Yoichi Iwata from AtCoder brings authoritative knowledge of competitive programming problem design. Kohki Horie holds dual affiliation with Sakana AI and the University of Tokyo [PAPER §2].

20.2 Architecture

20.2.1 Repository Audit

ALE-Bench consists of two distinct components: (1) the benchmark infrastructure — problem statements, test case generators, scoring systems, ranking calculators, and human baselines — which is the primary released artifact; and (2) ALE-Agent, a reference LLM-based agent built on Gemini 2.5 Pro, which is described in the paper but whose full implementation release status requires direct repository verification [PAPER §5–6].

Benchmark Infrastructure Components [PAPER]

Artifact Inventory

20.2.2 Architecture Diagram

20.2.3 Execution Trace

The paper describes a Docker-based execution environment mirroring AtCoder's judge system [PAPER §5]. The exact CLI commands and configuration file paths for the released benchmark require direct repository inspection, which was not performed for this chapter. The following is reconstructed from the paper's description:

# Pseudocode — reconstructed from paper §5 and README description
# Actual CLI commands and config paths require direct repo verification

# Step 1: Obtain benchmark problems and test cases
# (Available via GitHub repo and HuggingFace dataset)

# Step 2: Execute candidate solution in Docker judge environment
# Environment mirrors AtCoder judge:
#   - Language: C++ / Python / Rust (AtCoder-supported)
#   - Time limit: 2-5 seconds per test case (problem-specific)
#   - Memory limit: 256 MB - 1024 MB (problem-specific)
#   - CPU: Single-threaded execution

# Step 3: Score solution using official AtCoder scorer
# Each problem evaluated on 50-200 hidden test instances

# Step 4: Compute percentile ranking against human baselines
# Percentile = (# humans with score ≤ agent_score) / (total humans) × 100

20.3 Core Algorithms

ALE-Bench comprises two algorithmic layers: (1) the benchmark evaluation protocol — scoring, aggregation, and ranking — and (2) the ALE-Agent reference system — an iterative code-generation-and-refinement loop. This section treats both, with the benchmark protocol as the primary contribution and the agent as a paper-described companion.

20.3.1 Verification Matrix

20.3.2 Benchmark Scoring and Ranking Protocol

The benchmark's evaluation protocol uses a relative percentile ranking against human baselines from the original AHC contests. This design choice is fundamental: because AHC problems have no known optimal solutions, absolute score metrics are not meaningful across problems. Only relative performance within the human distribution is informative [PAPER §5].

Percentile Computation

[Published formula — paper §5. Notation is the chapter author's formalization of the described mechanism.]

Important caveat on scoring formula specifics: The paper states that the official AtCoder ranking software is used for evaluation. AHC contests use problem-specific scoring functions with diverse normalization schemes — some maximize, some minimize, and some use relative scoring where each participant's score on a test case is normalized against the best score on that case. The paper does not provide a single universal scoring formula applicable to all 40 problems. Each problem's scoring function is defined in its problem statement document. The percentile ranking described above is computed after per-problem score aggregation across test instances, using the same methodology as the original contest [PAPER §5].

20.3.3 Problem Taxonomy and Design

The 40 benchmark problems are categorized into six families [PAPER §4]:

Problem difficulty is characterized not by statement complexity but by the gap between naive and competitive solutions. Each problem has NP-hard combinatorial structure with typical search spaces on the order of 10²⁰⁰ [PAPER §3–4]. The paper illustrates this with the Food Delivery problem (AHC006): selecting 50 orders from 1,000 candidates gives C(1000,50) ≈ 10⁸⁵ combinations, and the joint optimization over selection and routing pushes the effective space further [PAPER §4].

20.3.4 ALE-Agent: Iterative Refinement Loop

ALE-Agent operates an iterative code-generation-and-refinement loop using Gemini 2.5 Pro as the foundation model. Within a 4-hour contest window, the agent performs approximately 100 revision cycles [PAPER §6]:

1. Problem analysis: Parse problem statement, identify optimization objective, classify problem type
2. Initial solution: Generate a baseline greedy or random solution to establish a score floor
3. Iterative refinement: Repeatedly propose code modifications (3–10 candidates per revision), execute, evaluate, accept/reject based on score improvement
4. Strategy switching: When improvements stall, propose fundamentally different algorithmic approaches

# Pseudocode — reconstructed from paper §6 and §8
# This is NOT verified repository code. All identifiers are illustrative.

def ale_agent_loop(problem_statement, time_budget_hours=4):
    """ALE-Agent iterative refinement — paper §6."""
    
    # Phase 1: Initial solution generation
    prompt = construct_prompt(
        problem=problem_statement,
        domain_knowledge=OPTIMIZATION_KNOWLEDGE_BASE,  # SA templates, etc.
        instruction="Generate initial greedy solution"
    )
    current_code = llm_generate(prompt, model="gemini-2.5-pro")
    current_score = execute_and_score(current_code)
    best_code, best_score = current_code, current_score
    
    revision = 0
    while elapsed_time() < time_budget_hours * 3600:
        revision += 1
        
        # Phase 2: Generate K candidate modifications
        K = select_candidate_count()  # typically 3-10
        candidates = []
        for _ in range(K):
            refinement_prompt = construct_refinement_prompt(
                problem=problem_statement,
                current_code=best_code,
                current_score=best_score,
                score_history=get_score_trajectory(),
                strategy_hint=select_strategy(score_trajectory)
            )
            candidate = llm_generate(refinement_prompt, model="gemini-2.5-pro")
            candidates.append(candidate)
        
        # Phase 3: Evaluate candidates with strict gating
        for candidate in candidates:
            if not compiles(candidate):
                continue  # Reject compilation failures
            if not within_limits(candidate):
                continue  # Reject TLE/MLE
            score = execute_and_score(candidate)
            if score > best_score:
                best_code, best_score = candidate, score
        
        # Phase 4: If no improvement, revert and try different approach
        # (implicit in the accept-on-improvement gate)
    
    return best_code, best_score
    # Typical: ~100 revisions, 300-1000 total evaluations

Domain Knowledge Injection [PAPER §7]

A critical component is the injection of optimization algorithm templates into the system prompt. The paper describes a hierarchical prompt structure with system-level context (expert competitive programmer role, algorithm knowledge base), per-problem context (statement, constraints, scoring function, current best code/score), and refinement instructions (suggested improvement area, strategy hints) [PAPER §7].

The knowledge base includes templates for: simulated annealing (temperature schedules, neighborhood design, acceptance criteria), greedy construction (nearest-neighbor, largest-first orderings), local search (2-opt, 3-opt, swap, insert operators), beam search, Monte Carlo methods, and constraint handling (penalty functions, repair operators) [PAPER §7].

Inference-Time Scaling [PAPER §8]

The agent exploits inference-time scaling at two levels: (1) per-revision candidate generation (3–10 variants evaluated, best selected) and (2) cross-revision trajectory exploration (~100 revision cycles with occasional reversion to earlier high-scoring states). The mathematical justification is straightforward [PAPER §8]:

[Standard definition — applied in paper §8 to justify multi-candidate generation.]

20.3.5 Novel Algorithmic Discoveries

The paper reports that ALE-Agent independently discovered two novel algorithmic techniques during benchmark evaluation [PAPER §11]:

Discovery 1: Poisson Distribution Approximation

For problems with scoring functions involving binomial probability computations, the agent replaced exact O(n) summation with a Poisson approximation yielding O(1) evaluation. This enabled approximately 10× more SA iterations within the time budget [PAPER §11].

// Pseudocode — reconstructed from paper §11
// Illustrates the conceptual transformation, not verified agent output

// Before: Exact binomial probability (O(n) per evaluation)
double exact_score(int n, double p) {
    double score = 0.0;
    for (int k = 0; k <= n; k++) {
        score += binomial_pmf(n, k, p) * reward(k);  // O(n) summation
    }
    return score;
}

// After: Poisson approximation discovered by agent (O(1) per evaluation)
double approx_score(int n, double p) {
    double lambda = n * p;  // Poisson parameter
    return expected_reward_poisson(lambda);  // Closed-form
    // Valid when n is large, p is small (standard Poisson limit theorem)
}

Discovery 2: Growth Neighborhood Search Strategy

This novel SA neighborhood operator employs a shrink-and-regrow cycle: the current solution is reduced to a core subset (approximately 60%), then rebuilt using SA-guided incremental construction. The paper reports this single innovation improved ALE-Agent's rank on AHC047 from 82nd to 21st place — a jump from top 8% to top 2% [PAPER §11].

# Pseudocode — reconstructed from paper §11
# This describes the conceptual algorithm, not verified implementation code

def growth_neighborhood_sa(initial_solution, T_start, T_end, time_limit):
    """Growth neighborhood: shrink-and-regrow with SA-guided reconstruction."""
    solution = shrink_to_core(initial_solution, core_fraction=0.6)
    best = initial_solution
    best_score = evaluate(initial_solution)

    while elapsed < time_limit:
        T = temperature_schedule(elapsed, T_start, T_end)

        # Growth phase: add elements with SA-guided selection
        while can_grow(solution):
            candidates = growth_candidates(solution)
            selected = sa_select(candidates, T)  # SA acceptance for each addition
            solution = add_element(solution, selected)

        score = evaluate(solution)
        if score > best_score:
            best, best_score = solution, score

        # Shrink phase: remove low-value elements to enable regrowth
        solution = shrink_to_core(solution, core_fraction=0.6)

    return best

20.3.6 SA Specialization and Dominance

A striking empirical finding is that ALE-Agent converges to simulated annealing as its primary strategy in approximately 85% of problems, regardless of whether SA is optimal for the problem type. This is not hard-coded but emerges from the LLM's training data (which contains extensive competitive programming resources where SA dominates heuristic contests) and the iterative refinement process (which selects for monotonically improving approaches) [PAPER §9].

The paper describes several sophisticated SA implementation techniques generated by the agent [PAPER §9]:

20.4 Key Results

20.4.1 Evaluation Caveats

20.4.2 Headline Results

20.4.3 Comparison Against Baselines

20.4.4 Per-Category Performance

The per-category results reveal a clear pattern: ALE-Agent performs best on problem types where simulated annealing is the dominant human approach (logistics, scheduling, placement), and weakest on simulation-based problems that require fundamentally different paradigms such as MCTS or beam search [PAPER §10].

20.4.5 Ablation Results

Key findings from ablations [PAPER §12]:

1. Iterative refinement is the dominant factor (43.2 pp improvement), confirming that the agent loop architecture — not single-shot LLM quality — drives performance.
2. Score feedback matters substantially (13.2 pp), indicating that the agent's ability to condition on quantitative execution results is critical.
3. Domain knowledge provides meaningful but non-dominant benefit (8.2 pp), suggesting the LLM already possesses significant optimization knowledge from pre-training.
4. Foundation model choice is less important than architecture (3–4 pp difference between Gemini, GPT-4o, Claude 3.5 Sonnet), indicating the agent loop generalizes across models.

20.4.6 Revision Count Scaling

The scaling exhibits clear diminishing returns: the first 10 revisions account for 28 percentile points of improvement (50th → 22nd), while revisions 100–200 add only 1.3 pp. This log-linear relationship suggests that substantial further improvement would require architectural innovations in the agent loop, not simply more iterations [PAPER §12].

20.4.7 Programming Language Effect

The C++ advantage (11.2 pp over Python) is primarily attributable to execution speed: SA performance scales linearly with iteration count, and C++ enables 10–100× more iterations within the same wall-clock budget [PAPER §12]. This finding has practical implications for any LLM-based optimization system: the choice of output language is a critical design variable.

20.5 Implementation & Cost

20.5.1 Computational Requirements

20.5.2 Cost-Performance Curve

The paper notes a super-linear cost structure: the first 30 percentile points (50th → 20th) cost approximately $1–2 per problem, while the last 13 points (20th → 6.8th) cost approximately $15–18 per problem [PAPER §15]. This reflects the fundamental diminishing returns of iterative refinement observed in the revision count scaling analysis (§20.4.6).

20.5.3 Infrastructure for Reproduction

20.6 Reproducibility

20.6.1 Verification Path

The benchmark and the agent have different reproducibility profiles. The benchmark infrastructure (problems, scorer, ranker, human baselines) is designed to be a stable evaluation framework. The agent is a companion system whose reproducibility depends on LLM API access and prompt/configuration availability.

Step-by-Step (Benchmark Only)

1. Clone repository: git clone https://github.com/SakanaAI/ALE-Bench.git
2. Obtain dataset: Available at HuggingFace: SakanaAI/ALE-Bench
3. Set up Docker judge environment: Instructions expected in repository README (not verified)
4. Generate or provide candidate solutions: Any agent or manual approach
5. Execute solutions and score: Using provided scoring infrastructure
6. Compute percentile rankings: Using provided ranking calculator against human baselines
7. Successful reproduction: Percentile rankings for a given solution set should be deterministic given the same test instances and human baselines

20.6.2 Reproducibility Checklist

Assessment: The benchmark infrastructure appears designed for reproducibility — standardized problems, deterministic test generation, official scoring. However, reproducing the ALE-Agent results specifically faces additional barriers: dependence on Gemini 2.5 Pro API (model may be updated or deprecated), unreported seeds/run counts, and unclear release status of prompt templates and domain knowledge base. The benchmark itself is separable from the agent and should be usable with any optimization approach.

20.7 Threats to Validity

20.7.1 Evaluation Protocol Concerns

• Historical baseline staleness: Human baselines are frozen at the time of each original AHC contest. As competitive programming communities improve and potentially adopt AI assistance, the percentile rankings lose calibration over time. A "top 6.8%" result today would represent a different absolute quality level if re-evaluated against future participants.
• Contest format mismatch: ALE-Agent is optimized for 4-hour contests. AHC also includes 2-week long contests where human strategies differ fundamentally (multiple approaches, statistical parameter tuning, collaboration). The benchmark does not capture this format [PAPER §13].
• Single-machine constraint: All solutions run on a single CPU thread, reflecting contest conditions but not modern optimization practice, which commonly uses parallelism, distributed computing, and GPU acceleration [PAPER §18].

20.7.2 Agent-Specific Concerns

• Self-evaluation by developers: Results are reported by the system's creators (Sakana AI / AtCoder). While AHC047 was a live contest (providing some external validation), the broader benchmark results are self-reported.
• Unreported variance: Number of runs, seeds, and variance across runs are not specified in the source material reviewed. A single-run result on a stochastic agent could be misleading.
• Compute budget asymmetry: Comparing ALE-Agent ($5–20/problem in API costs) against unaided human effort in a 4-hour window conflates resource types. Humans bring years of accumulated expertise at zero marginal cost; the agent brings LLM capabilities at monetary cost.
• Model checkpoint drift: LLM APIs are continuously updated. Results obtained with Gemini 2.5 Pro at a specific date may not be reproducible with the same API endpoint months later.

20.7.3 Benchmark Design Concerns

• Domain coverage: 40 problems from competitive programming may not represent industrial optimization challenges (supply chain, financial portfolio, chip design). Generalization to real-world tasks is undemonstrated [PAPER §18].
• Data contamination risk: AHC problem statements and some solutions are publicly available. While the paper argues that these problems require novel algorithm design beyond pattern matching [PAPER §3], the LLM's training data likely includes competitive programming discussions of these specific contests.
• Scoring function diversity: Each AHC problem has a unique scoring function. The percentile aggregation across problems of varying human participation counts and score distributions introduces potential weighting biases. The paper does not describe a normalization scheme for cross-problem aggregation beyond per-problem percentile computation.

20.7.4 Isolation and Security

The paper describes a "sandboxed Docker environment" for solution execution [PAPER §5]. Docker provides process-level isolation but is not a security boundary equivalent to VM-level isolation. For a benchmark evaluating potentially adversarial AI-generated code, the actual security properties of the execution environment matter. The specific Docker configuration (capabilities, network access, resource limits enforcement) was not verified from the repository for this chapter.

20.8 Limitations & Open Questions

20.8.1 Documented Limitations [PAPER §13, §18]

• SA monoculture: ALE-Agent converges to simulated annealing in ~85% of problems, performing poorly on problems requiring beam search, MCTS, dynamic programming, or game-theoretic reasoning. The agent's training data bias toward SA prevents discovery of superior paradigms for non-SA-friendly problems.
• Bug detection failure: Subtle bugs (off-by-one, integer overflow, floating-point accumulation, time-measurement race conditions) reduce scores without producing visible errors. The agent cannot distinguish "algorithmically worse modification" from "modification that introduced a bug." Reported frequency: ~15% of problems affected [PAPER §13].
• Complexity analysis failure: Solutions that pass small sample cases but time out on large hidden instances (~8% of problems). The agent lacks the ability to reason about asymptotic complexity [PAPER §13].
• No meta-learning: Each problem starts from scratch. Experience on one problem does not accelerate performance on subsequent problems [PAPER §18].
• Risk aversion: The accept-on-improvement criterion makes the agent systematically avoid high-variance strategies that may occasionally produce exceptional results [PAPER §13].
• Context window saturation: As solutions grow complex (500+ lines), the agent struggles to maintain coherent modifications across the entire program [PAPER §18].

20.8.2 Failure Mode Statistics [PAPER §13]

20.9 Survey Positioning

20.9.1 Comparison with Related Systems

20.9.2 Evolutionary Framework Correspondence

Where the analogy breaks down: ALE-Agent's single-trajectory approach with greedy accept/reject is closer to a hill-climbing or simulated annealing search than to evolutionary computation. There is no population, no crossover, no diversity maintenance, and no generational structure. The "evolutionary" label in the paper title refers to the iterative refinement paradigm rather than a population-based evolutionary algorithm. This makes ALE-Agent architecturally simpler than systems like FunSearch (which maintains diverse program populations) but also limits its ability to escape local optima through population-level diversity.

20.9.3 Implications for the Field

ALE-Bench establishes several precedents relevant to the broader survey:

1. Iterative refinement as the primary performance driver: The 43.2 pp improvement from iterative refinement (vs. 3–8 pp from model choice or domain knowledge) provides strong evidence that agent architecture matters more than LLM capability for optimization tasks. This aligns with findings from other systems in this survey.
2. LLM-discovered algorithms: The Poisson approximation and growth neighborhood search discoveries suggest that LLM-based optimization agents can produce novel algorithmic techniques, not merely recombine known approaches. However, the frequency and significance of such discoveries relative to human competitive programmers remains unclear.
3. Output language as design variable: The 11.2 pp gap between C++ and Python outputs has practical implications for all LLM-based optimization systems. When iterative algorithms (SA) are the primary paradigm, execution speed directly constrains solution quality.
4. Human-competitive but not superhuman: Top-2% performance on individual problems and top-6.8% on average places ALE-Agent at the expert tier but below world-class competitive programmers (who maintain a 10–30% score advantage). This calibrates expectations for LLM-based optimization in the near term.

20.10 Summary