# ALE-Agent (`ale_agent`)

> Domain-guided tabu best-first search with broad sibling expansion and multi-turn implementation refinement.

## Overview

ALE-Agent is the algorithm-engineering scaffold introduced with ALE-Bench. It treats every scored program as a search state, expands the most promising unexpanded state, and generates 30 independent refinement branches from it. Each branch gets three implementation turns with fresh evaluator feedback; only the strongest version from those turns returns to the best-first frontier. Expanded parents are tabu and are never selected for expansion again.

The first turn in each branch separates planning from implementation. It samples one of the four domain prompts published in the paper supplement—complexity/speed, simulated-annealing state, simulated-annealing neighborhood, or beam search—asks for a strategy, then asks the model to implement it. Later turns receive the current code, its evaluation feedback, the historically best code and feedback, and the branch strategy.

This is a paper-specification port. The public ALE-Bench repository contains the benchmark and generic self-refinement harness, but not the experimental ALE-Agent source. The implementation here follows the main paper and supplement rather than claiming source-level parity with unreleased code.

Galapagos tasks require an initial genome, so the selected task's bundled baseline is the root state;
the paper instead describes a conceptual root whose first children are generated from the problem
statement alone. For deterministic sequential execution, the historically best state is frozen when
a 30-sibling cohort starts, preventing an earlier scheduled sibling from leaking into a later one's
prompt as though the originally concurrent requests had observed each other.

## Algorithm

1. Rank frontier states lexicographically by accepted-case ratio and task score. The bundled ALE-Bench task adapter currently exposes the all-50-cases `judge_accepted` signal; tasks that expose a finer `acceptance_ratio` are used directly.
2. Pop the highest-priority state and mark it expanded (tabu).
3. Create `ale_children_per_parent=30` sibling branches.
4. For each branch, sample a domain guide and run `ale_refinement_turns=3` evaluated implementation turns.
5. Put the best version from each branch on the frontier; retain every evaluated version in the archive for historical-best context.
6. Repeat until the explicit Galapagos iteration budget is exhausted or no unexpanded frontier state remains.

Galapagos schedules sibling branches sequentially. This preserves the paper's search tree and deterministic replay, but not the wall-clock latency reduction obtained by dispatching the 30 model calls concurrently in the original experiments.

## Components

| Slot | Implementation | Role |
|---|---|---|
| Population | `ALEAgentPopulation` | Keep-all archive ranked by acceptance ratio, then score. |
| SelectionPolicy | `ALEAgentSelectionPolicy` | Tabu best-first parent selection, 30 sibling branches, and three-turn branch state. |
| PromptBuilder | `ALEAgentPromptBuilder` | Current/best feedback plus one of four published algorithm-engineering guides. |
| Proposer | `ALEAgentProposer` | Strategy call on turn one, then complete-program implementation/refinement. |
| Evaluator | task-supplied | The selected task's evaluator; bundled AHC tasks run ALE-Bench's 50 public cases. |
| Memory | `ALEAgentMemory` | Rolling trajectory summary used by the Base and Method 1 ablations. |

## Configuration and ablations

The bundled preset is the paper's full **Base + Method 1&2** structure:

- `selection_policy.ale_children_per_parent: 30`
- `selection_policy.ale_refinement_turns: 3`
- `prompt_builder.ale_domain_guidance: true`
- `prompt_builder.ale_include_history: false` (the paper omits history in the full breadth setting to protect diversity)
- `general.mutation_approach: full_rewrite`

The paper's ablations can be selected with ordinary overrides:

```bash
# Base: one sequential child, one implementation turn, no domain guide.
galapagos run --scaffold ale_agent --task ahc039 \
  --set selection_policy.ale_children_per_parent=1 \
  --set selection_policy.ale_refinement_turns=1 \
  --set prompt_builder.ale_domain_guidance=false \
  --set prompt_builder.ale_include_history=true

# Base + Method 1: domain guidance and three turns, still a single path.
galapagos run --scaffold ale_agent --task ahc039 \
  --set selection_policy.ale_children_per_parent=1 \
  --set selection_policy.ale_refinement_turns=3 \
  --set prompt_builder.ale_domain_guidance=true \
  --set prompt_builder.ale_include_history=true
```

The original experiment used Gemini 2.5 Pro and a per-problem wall-clock limit of four hours or the original contest duration, whichever was shorter. Galapagos uses an explicit iteration budget; the preset's 1,000 iterations reflects the paper's reported approximate generation scale, so pass `--general.max_iterations 100` (or less) for a smoke run.

## Source

- *ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineering*, NeurIPS 2025, arXiv:2506.09050.
- Reference benchmark repository: `SakanaAI/ALE-Bench` (Apache-2.0).