SkyDiscover Documentation

ADRS (AI-Driven Research for Systems) is an initiative from UC Berkeley that uses AI—including large language models, evolutionary algorithms, and multi-agent architectures—to autonomously design, optimize, and evaluate computer systems.

It treats systems research as a closed-loop optimization problem where candidate algorithms are proposed, evaluated against system-level objectives, and iteratively improved. The benchmarks in this directory define concrete systems tasks with provided evaluators, initial programs, and configurations, which are then evolved using SkyDiscover's evolutionary search loop.

SkyDiscover is designed to be extensible. You can customize the engine by implementing or subclassing the following components:

• Context Builder: Assembles LLM prompts. Extend by subclassing ContextBuilder.
• Solution Generator: Produces candidates via LLM calls. Extend by subclassing LLMInterface.
• Evaluator: Scores candidates and logs metadata. Extend by providing an evaluate.py script.
• Solution Selector: Maintains the solution database and picks parents. Extend by subclassing ProgramDatabase.

SkyDiscover uses a core loop of sample → prompt → LLM → evaluate → add to evolve programs. Algorithms are implemented by plugging into this loop. You can customize the search at two levels of complexity:

1. Level 1: Database only: You implement add() and sample(). This is used when you only need to change how parents are selected or how programs are stored. The default controller handles the execution loop.
2. Level 2: Database + Controller: You implement a custom DiscoveryController. This is used when you need cross-iteration logic, such as reacting to stagnation, implementing island rotation, or applying acceptance gating (filtering results before they are added to the database).

The Circle Packing problem aims to pack exactly 26 non-overlapping circles inside a unit square to maximize the sum of their radii.

Constraints:

• Exactly 26 circles must be packed.
• No circles may overlap.
• Each circle must lie entirely within the unit square.

Scoring:

• The combined_score is calculated as sum_of_radii / 2.635, where 2.635 is the AlphaEvolve B.12 target.
• The evaluator.py is responsible for validating that no overlaps occur and that all circles respect the boundary constraints.

ALE-Bench problems are organized within the ale-bench-lite-problems/ directory. Each problem folder (e.g., ahcXXX/) contains the necessary components for evolution:

• initial_program.cpp: The starting C++ solution.
• evaluator.py: The script that runs the 50 public test cases via the ale_bench package.
• config.yaml: The search configuration (typically set for C++, diff-based evolution, and 100 iterations).

Additionally:

• ale_agent_best/: Contains reference C++ files of the best known solutions.
• private_eval.py: The utility for full private set evaluation and ranking.

The TriMul benchmark evaluates evolved kernels based on two primary criteria:

1. Correctness: The kernel must match the PyTorch reference output within a relative tolerance (rtol) of 0.02 and an absolute tolerance (atol) of 0.02.
2. Performance Score: The score is calculated as SCORE_SCALE / geom_mean_us, where SCORE_SCALE = 3000.0.

A higher score indicates a faster runtime (lower microseconds), meaning the evolution process is successful when the score increases.

SkyDiscover evaluates kernels through a four-step pipeline managed by shared_eval.py:

1. Correctness: Runs TEST_CASES from reference.py and compares output against the reference within a specified tolerance.
2. Warmup: Runs a single case to trigger Triton JIT compilation.
3. Benchmark: Times BENCHMARK_CASES using CUDA events, repeating until the error is < 0.1% or the time budget is exhausted.
4. Score: Calculates the final score.

Scoring Formulas

Most benchmarks use the following formula: combined_score = SCORE_SCALE / geom_mean_us where geom_mean_us is the geometric mean of kernel runtimes in microseconds. SCORE_SCALE is typically 3000.0.

Exception: The vecadd benchmark uses a unique formula: 0.3 * correctness + speedup. Check its specific README for details.

During the evolution phase, programs are scored using 50 public test cases. The combined_score is calculated to ensure a 'higher-is-better' metric regardless of whether the original problem objective was to maximize or minimize a value.

Formula: combined_score = overall_absolute_score * optim_factor / num_public_cases

• optim_factor: +1 for maximization problems, -1 for minimization problems.

Beam Search maintains a fixed-width beam of the most promising programs. At each iteration, a parent is selected from the beam using a specified selection strategy. New programs are added to the beam, which is then pruned back to the configured beam_width based on fitness and optional diversity.

Key mechanics include:

• Pruning: Keeps the top beam_width programs. If beam_diversity_weight is greater than 0, diversity is used as a bonus during pruning.
• Depth Tracking: Beam depth is tracked per program via parent linkage. You can apply an exponential penalty per depth level using beam_depth_penalty to prevent programs from becoming too deep/complex.
• Sampling: The algorithm selects a parent from the beam and considers other context (top programs globally) to generate new candidates.

When setting up a numerical optimization problem for circle packing in a unit square, you must implement the following constraints:

1. Non-overlap Constraint: For every pair of circles $(i, j)$, ensure the distance between centers is at least the sum of their radii: distance(center_i, center_j) >= r_i + r_j
2. Boundary Constraint: Ensure every circle $i$ stays within the unit square $[0, 1] imes [0, 1]$:
   • x_i - r_i >= 0
   • x_i + r_i <= 1
   • y_i - r_i >= 0
   • y_i + r_i <= 1
3. Positive Radii: Use variable bounds rather than inequality constraints to ensure r_i > 0 for all $i$.