# Pseudo-code for LLM-based mutation
def llm_mutate(parent_code: str, problem_description: str,
               mutation_type: str, model: str) -> str:
    """Use LLM to generate a mutated version of parent code."""

    prompt = build_mutation_prompt(
        code=parent_code,
        problem=problem_description,
        mutation=mutation_type,
        best_score=get_population_best(),
        parent_score=get_score(parent_code),
        error_history=get_recent_errors()
    )

    response = call_llm_api(
        model=model,
        messages=[
            {"role": "system", "content": SYSTEM_PROMPT},
            {"role": "user", "content": prompt}
        ],
        temperature=sample_temperature(),  # Varies 0.3-1.0
        max_tokens=8192
    )

    return extract_code(response)

# Model selection based on mutation complexity and budget
def select_model(mutation_type: str, budget_remaining: float) -> str:
    if mutation_type in ["major_refactor", "strategy_change"]:
        if budget_remaining > 0.5:
            return "claude-3-5-sonnet"  # High quality for big changes
        return "gpt-4o"
    elif mutation_type in ["parameter_tune", "local_fix"]:
        return "claude-3-haiku"     # Cheap for small changes
    else:
        return random_choice(["claude-3-5-sonnet", "gpt-4o"])

+========================================================================+
|                    SAKANA AI AHC058 EVOLUTIONARY SYSTEM                 |
+========================================================================+
|                                                                        |
|  +------------------+     +-----------------------+                    |
|  | PROBLEM CONTEXT  |     |   POPULATION STORE    |                    |
|  | - Problem desc   |     |   (Quality-Diversity) |                    |
|  | - Test cases     |     |   +---------------+   |                    |
|  | - Constraints    |     |   | Individual 1  |   |                    |
|  | - Scoring rules  |     |   | - code (C++)  |   |                    |
|  +--------+---------+     |   | - fitness     |   |                    |
|           |               |   | - strategy    |   |                    |
|           v               |   | - lineage     |   |                    |
|  +--------+---------+     |   +---------------+   |                    |
|  | PARENT SELECTION  |<---+   | Individual 2  |   |                    |
|  | - Fitness-prop   |    |   | ...           |   |                    |
|  | - Tournament     |    |   +---------------+   |                    |
|  | - Diversity bonus |    |   | Individual N  |   |                    |
|  +--------+---------+    |   +---------------+   |                    |
|           |               +-----------+-----------+                    |
|           v                           ^                                |
|  +--------+---------+                 |                                |
|  | MUTATION ENGINE   |                | (survivors +                   |
|  | (LLM-Based)       |                |  new offspring)                |
|  |                   |                |                                |
|  | +---------------+ |     +----------+----------+                     |
|  | | Model Select  | |     | SELECTION/SURVIVAL  |                     |
|  | | - Claude 3.5  | |     | - Truncation        |                     |
|  | | - GPT-4o      | |     | - Elitism           |                     |
|  | | - Gemini 1.5  | |     | - Diversity pres.   |                     |
|  | +-------+-------+ |     +----------+----------+                     |
|  |         |         |                ^                                |
|  | +-------v-------+ |                |                                |
|  | | Mutation Type  | |     +----------+----------+                     |
|  | | - Refactor    | |     | EVALUATION ENGINE   |                     |
|  | | - Optimize    | |     | - Compile (g++)     |                     |
|  | | - Bug fix     | |     | - Run on test cases |                     |
|  | | - Strategy    | |     | - Score aggregation |                     |
|  | | - Parameter   | |     | - Timeout handling  |                     |
|  | +-------+-------+ |     +----------+----------+                     |
|  |         |         |                ^                                |
|  | +-------v-------+ |                |                                |
|  | | Prompt Build  | |     +----------+----------+                     |
|  | | + Context     | |     | SANDBOX EXECUTION   |                     |
|  | +-------+-------+ |     | - Compilation       |                     |
|  |         |         |     | - Resource limits   |                     |
|  | +-------v-------+ |     | - Output capture    |                     |
|  | | LLM API Call  | |     +---------------------+                     |
|  | +-------+-------+ |                                                 |
|  |         |         |                                                 |
|  | +-------v-------+ |                                                 |
|  | | Code Extract  +-------> [New C++ Program] -----> Compile & Eval   |
|  | +---------------+ |                                                 |
|  +-------------------+                                                 |
|                                                                        |
|  +------------------------------------------------------------------+  |
|  | ORCHESTRATION LAYER                                               |  |
|  | - Generation loop control  - Budget management                   |  |
|  | - Parallel API dispatch    - Logging and monitoring              |  |
|  | - Error recovery           - Convergence detection               |  |
|  +------------------------------------------------------------------+  |
+========================================================================+

Generation Loop:

  [Population] --select--> [Parents] --mutate(LLM)--> [Offspring Code]
       ^                                                      |
       |                                                      v
       |                                              [Compile (g++)]
       |                                                      |
       |                                              [Pass?]--No--> discard
       |                                                |Yes
       |                                                v
       |                                        [Run on test cases]
       |                                                |
       |                                                v
       |                                        [Compute fitness]
       |                                                |
       |                                                v
       +--------[Survival selection]<---------[Scored offspring]

## System prompt (parameter tuning)
"""
You are an expert competitive programmer. You are given a C++ solution
for an optimization problem. Your task is to ONLY adjust numerical
constants, thresholds, and parameters to improve the score.

DO NOT change the algorithm structure. ONLY modify:
- Temperature schedules (initial temp, cooling rate)
- Iteration counts and loop bounds
- Scoring weights and penalties
- Threshold values for decisions

Return the complete modified C++ code.
"""

## User prompt
"""
Problem: {problem_description}

Current solution (score: {current_score}, best known: {best_score}):
```cpp
{parent_code}

#### Example: Strategy Change Mutation

#### Crossover Operator

{parent_a}

{parent_b}

### 10.2 Parent Selection and Sampling Strategies

Parent selection determines which individuals from the population are chosen to be mutated. The system uses a multi-strategy approach:

#### Fitness-Proportionate Selection


$$
P(select individual i) = f(i)^α / Σj f(j)^α
where f(i) is the fitness of individual i and α is a selection pressure parameter (typically 1.0-2.0)
$$

# Normalize to [0, 1] range
fitnesses = (fitnesses - fitnesses.min()) / (fitnesses.max() - fitnesses.min() + 1e-8)

# Apply selection pressure
weights = fitnesses ** alpha
probabilities = weights / weights.sum()

return np.random.choice(population, p=probabilities)

#### Tournament Selection

#### Diversity-Aware Selection

# Combined score: fitness + diversity bonus
combined = (1 - diversity_weight) * fitnesses + diversity_weight * diversities
probabilities = combined / combined.sum()

return np.random.choice(population, p=probabilities)

### 10.3 Population Management and Architecture

The population is structured as a **quality-diversity (QD) archive** rather than a simple flat list. This ensures the system maintains a diverse collection of high-quality solutions.

#### Population Structure

def __init__(self, max_per_niche=5, niche_categories=None):
    self.niches = {}   # strategy_type -> list of individuals
    self.max_per_niche = max_per_niche
    self.elite_buffer = []  # Top K overall
    self.hall_of_fame = {}  # Best ever per niche

def add(self, individual):
    """Add individual to archive, maintaining quality within niche."""
    niche = individual.strategy_tag

    if niche not in self.niches:
        self.niches[niche] = []

    self.niches[niche].append(individual)
    self.niches[niche].sort(key=lambda x: x.fitness, reverse=True)

    # Keep only top K per niche
    if len(self.niches[niche]) > self.max_per_niche:
        self.niches[niche] = self.niches[niche][:self.max_per_niche]

    # Update hall of fame
    if niche not in self.hall_of_fame or individual.fitness > self.hall_of_fame[niche].fitness:
        self.hall_of_fame[niche] = individual

    # Update elite buffer
    self._update_elite(individual)

def get_population(self):
    """Return all individuals across all niches."""
    return [ind for niche in self.niches.values() for ind in niche]

def population_size(self):
    return sum(len(n) for n in self.niches.values())

#### Population Parameters

| Parameter | Typical Value | Purpose |
| --- | --- | --- |
| Max population size | 30-50 | Total across all niches |
| Max per niche | 5-10 | Quality within strategy type |
| Elite buffer size | 5 | Global best preservation |
| Offspring per generation | 5-20 | Exploration-exploitation tradeoff |
| Elitism count | 1-3 | Best individuals guaranteed survival |

### 10.4 Solution Diversity and Novelty Mechanisms

Maintaining diversity is critical to avoid premature convergence. The system employs multiple mechanisms:

#### Strategy Tagging

Each program is tagged with its algorithmic strategy type. The LLM is asked to classify the approach:

{code}

#### Behavioral Descriptors

Solutions are characterized by behavioral features computed from their execution:

# Score distribution across test cases
scores = [run_and_score(program, tc) for tc in test_cases]
features['mean_score'] = np.mean(scores)
features['score_variance'] = np.var(scores)
features['min_score'] = np.min(scores)

# Runtime characteristics
features['avg_runtime'] = np.mean(runtimes)
features['memory_usage'] = peak_memory

# Code structural features
features['code_length'] = len(program.code.split('\n'))
features['num_functions'] = count_functions(program.code)

return np.array(list(features.values()))

#### Novelty Search Component


$$
novelty(x) = (1/k) * Σi=1..k dist(behavior(x), behavior(nni))
        where nni are the k nearest neighbors in behavioral space
$$

#### Multi-Model Diversity

Using multiple LLMs inherently generates diverse mutations because each model has different coding styles, preferences for data structures, and optimization intuitions.

### 10.5 LLM Orchestration and Model Selection

#### Model Selection Strategy

MODELS = {
    "claude-3-5-sonnet": {"quality": 0.95, "cost_per_1k": 0.009, "speed": "medium"},
    "gpt-4o": {"quality": 0.90, "cost_per_1k": 0.010, "speed": "medium"},
    "claude-3-haiku": {"quality": 0.70, "cost_per_1k": 0.001, "speed": "fast"},
    "gemini-1.5-pro": {"quality": 0.88, "cost_per_1k": 0.007, "speed": "medium"},
}

def select_model(self, mutation_type, budget_fraction_remaining):
    """Select optimal model for this mutation."""

    # High-impact mutations get best models
    if mutation_type in ["strategy_change", "major_refactor", "crossover"]:
        if budget_fraction_remaining > 0.3:
            return "claude-3-5-sonnet"
        return "gpt-4o"

    # Simple mutations use cheap models
    if mutation_type in ["parameter_tune", "bug_fix"]:
        return "claude-3-haiku"

    # Default: rotate for diversity
    return random.choice(["claude-3-5-sonnet", "gpt-4o"])

async def batch_mutate(self, parents, mutation_types):
    """Run multiple mutations in parallel across models."""
    tasks = []
    for parent, mut_type in zip(parents, mutation_types):
        model = self.select_model(mut_type, self.budget_remaining)
        tasks.append(self.async_mutate(parent, mut_type, model))

    results = await asyncio.gather(*tasks, return_exceptions=True)
    return [r for r in results if not isinstance(r, Exception)]

#### Temperature Scheduling

The LLM temperature is varied strategically:

base_temps = {
    "parameter_tune": 0.3,
    "local_fix": 0.4,
    "algorithm_refine": 0.6,
    "strategy_change": 0.9,
    "major_refactor": 0.8,
    "crossover": 0.7,
}

base = base_temps.get(mutation_type, 0.6)

# Cool down as evolution progresses (exploit more, explore less)
temp = base * (1.0 - 0.3 * progress)

return max(0.2, min(1.0, temp))

### 10.6 Search Strategies and Tree Exploration

The evolutionary search can be viewed as exploring a tree of program transformations. Several strategies govern this exploration:

#### Lineage Tree

#### Exploration vs Exploitation Balance


$$
mutation_type ~ Categorical(p_explore(gen), p_exploit(gen))



        p_explore(gen) = p_explore_init * decay^gen + p_explore_min



        p_exploit(gen) = 1 - p_explore(gen)
        Exploration probability decays over generations, shifting focus from strategy discovery to refinement
$$

# Exploration mutations (large changes)
explore_prob = max(0.1, 0.5 * (1.0 - progress))

if random.random() < explore_prob:
    # Exploration: large-magnitude mutations
    return random.choice(["strategy_change", "major_refactor", "crossover"])
else:
    # Exploitation: refine existing solutions
    return random.choices(
        ["parameter_tune", "local_fix", "algorithm_refine"],
        weights=[0.4, 0.3, 0.3]
    )[0]

### 10.7 Evaluation and Fitness Assessment

#### Evaluation Pipeline

    # Step 1: Compilation
    compile_result = self.compile_cpp(code, flags=["-O2", "-std=c++17"])
    if not compile_result.success:
        return EvalResult(
            fitness=0,
            status="COMPILE_ERROR",
            error=compile_result.stderr
        )

    # Step 2: Run on each test case
    scores = []
    runtimes = []
    for tc in test_cases:
        result = self.run_sandboxed(
            binary=compile_result.binary,
            input_data=tc.input,
            time_limit=5.0,     # seconds
            memory_limit=1024   # MB
        )

        if result.status == "OK":
            score = self.compute_score(result.output, tc.expected, tc.params)
            scores.append(score)
            runtimes.append(result.runtime)
        elif result.status == "TLE":
            scores.append(0)  # Time limit exceeded
        elif result.status == "RE":
            scores.append(0)  # Runtime error

    # Step 3: Aggregate fitness
    if len(scores) == 0:
        fitness = 0
    else:
        # Weighted: penalize variance, reward consistency
        fitness = np.mean(scores) - 0.1 * np.std(scores)

    return EvalResult(
        fitness=fitness,
        status="OK",
        scores=scores,
        runtimes=runtimes
    )

#### Fitness Aggregation


$$
fitness(p) = (1/N) * Σi=1..N score(p, test_i) - λ * std({score(p, test_i)})
        Mean score across test cases with a penalty for inconsistency (λ ~ 0.1)
$$

#### Fast Evaluation (Subset Sampling)

To reduce evaluation cost, the system uses a two-stage evaluation:

# Stage 1: Quick eval on small subset
quick_tests = random.sample(all_tests, k=5)
quick_fitness = evaluate(candidate, quick_tests)

# Only fully evaluate promising candidates
if quick_fitness > elite_threshold * 0.8:
    # Stage 2: Full evaluation
    full_fitness = evaluate(candidate, all_tests)
    return full_fitness

return quick_fitness  # Not worth full eval

### 10.8 Prompt Engineering and Co-Evolution

#### Prompt Template Structure

Prompts are constructed from multiple components:

    # 1. System context
    sections.append(self.system_prompt(mutation_type))

    # 2. Problem description (always included)
    sections.append(f"## Problem\n{self.problem_description}")

    # 3. Parent code
    sections.append(f"## Current Solution (Score: {parent.fitness})\n```cpp\n{parent.code}\n```")

    # 4. Performance context
    sections.append(f"## Performance\n"
        f"- Best known score: {population_context['best_score']}\n"
        f"- This solution's score: {parent.fitness}\n"
        f"- Per-test scores: {parent.per_test_scores}\n"
        f"- Runtime: {parent.avg_runtime}ms")

    # 5. Error history (if applicable)
    if parent.recent_errors:
        sections.append(f"## Recent Errors\n{parent.recent_errors}")

    # 6. Mutation-specific instructions
    sections.append(self.mutation_instructions(mutation_type))

    # 7. Output format
    sections.append("## Output\nReturn the COMPLETE modified C++ code in a ```cpp code block.")

    return "\n\n".join(sections)

#### Prompt Co-Evolution

The system can evolve its own prompts over time. Prompts that lead to successful mutations (fitness-improving offspring) are reinforced:

def record_outcome(self, prompt_id, fitness_improvement):
    """Track which prompts lead to improvements."""
    if prompt_id not in self.prompt_scores:
        self.prompt_scores[prompt_id] = []
    self.prompt_scores[prompt_id].append(fitness_improvement > 0)

def select_prompt_template(self, mutation_type):
    """Select prompt template weighted by historical success."""
    variants = self.prompt_variants[mutation_type]
    success_rates = [
        np.mean(self.prompt_scores.get(v.id, [0.5]))
        for v in variants
    ]
    # Softmax selection
    probs = softmax(np.array(success_rates) * 3.0)
    return np.random.choice(variants, p=probs)

### 10.9 Cost Control and Budget Management

def get_generation_budget(self) -> float:
    """Budget for current generation."""
    remaining = self.total_budget - self.spent
    remaining_gens = self.total_generations - self.current_generation

    # Reserve more budget for later (refinement phase)
    if self.current_generation < self.total_generations * 0.3:
        # Early: explore freely but don't overspend
        return remaining / remaining_gens * 0.8
    else:
        # Later: steady spend
        return remaining / remaining_gens

def should_use_cheap_model(self) -> bool:
    """Switch to cheaper models when budget is low."""
    fraction_remaining = (self.total_budget - self.spent) / self.total_budget
    fraction_time_remaining = 1 - self.current_generation / self.total_generations

    # If spending faster than time progresses, use cheaper models
    return fraction_remaining < fraction_time_remaining * 0.8

def record_cost(self, cost: float):
    self.spent += cost

### 10.10 Meta-Level and Self-Improvement Techniques

The system incorporates several meta-learning mechanisms:

#### Adaptive Mutation Rate Scheduling

The distribution over mutation types is adapted based on which types have been most successful recently:

def record(self, mutation_type, improved: bool):
    self.history[mutation_type].append(improved)

def get_probabilities(self):
    """Compute mutation type probabilities from recent success."""
    success_rates = {}
    for t in self.types:
        recent = self.history[t][-self.window:]
        if len(recent) > 0:
            success_rates[t] = np.mean(recent) + 0.1  # smoothing
        else:
            success_rates[t] = 0.5  # uninformed prior

    total = sum(success_rates.values())
    return {t: v/total for t, v in success_rates.items()}

#### Feedback-Driven Prompting

Error messages and execution failures are fed back into subsequent prompts, enabling the system to learn from its mistakes within a single evolutionary run:

#### Population Statistics as Meta-Information

The system tracks and uses aggregate statistics about the evolutionary run to inform its decisions:

- Fitness improvement rate (stagnation detection)
- Compilation success rate per mutation type
- Average fitness improvement per model
- Diversity metrics over time

## 11. Programming Language

### System Implementation

The evolutionary framework itself is implemented in **Python**, leveraging:

- `asyncio` for concurrent LLM API calls
- `subprocess` for compilation and execution sandboxing
- `numpy` for fitness calculations and selection
- Standard HTTP libraries for API communication (httpx/aiohttp)

### Generated Code Language

The evolved solutions are written in **C++17**, the dominant language for AtCoder competitive programming:

- Compiled with `g++ -O2 -std=c++17`
- Utilizes STL containers, algorithms, and data structures
- Solutions typically 100-500 lines
- Includes competitive programming idioms (fast I/O, macros, etc.)

while (elapsed() < TIME_LIMIT) {
    State neighbor = generate_neighbor(current);
    int delta = neighbor.score - current.score;
    if (delta > 0 || exp(delta / temp) > rng()) {
        current = neighbor;
        if (current.score > best.score)
            best = current;
    }
    temp *= COOL_RATE;
}
return best;

## 12. Memory Management

### Context Window Management

LLM context windows are a critical resource. The system manages them carefully:

| Context Component | Approximate Tokens | Management Strategy |
| --- | --- | --- |
| System prompt | 200-500 | Static, always included |
| Problem description | 500-2000 | Compressed summary for smaller contexts |
| Parent code | 500-3000 | Full code always included |
| Performance context | 200-500 | Summarized scores and timing |
| Error history | 0-500 | Only recent/relevant errors |
| Mutation instructions | 200-800 | Mutation-type specific |
| **Total per call** | **1600-7300** |  |

### History and Caching

- **Compilation cache:** Identical source code is not recompiled; hash-based lookup
- **Evaluation cache:** If an identical program was already evaluated, reuse the score
- **Lineage history:** Full parent-child relationships stored for analysis but not included in prompts (too large)
- **Error deduplication:** Repeated identical errors are collapsed in feedback

def get_or_eval(self, code, evaluator, test_cases):
    code_hash = hashlib.sha256(code.encode()).hexdigest()
    if code_hash in self.cache:
        return self.cache[code_hash]
    result = evaluator.evaluate(code, test_cases)
    self.cache[code_hash] = result
    return result