CORAL: Towards Autonomous Multi-Agent Evolution for Open-Ended Discovery

Motivation

• Open-ended problems lack ground-truth answers, so strong solutions must emerge through iterative proposal, testing, revision, and progress over time.Source: §1 · p. 2

Limitations of Prior Methods

• Fixed evolutionary search leaves parent selection, intermediate testing, and knowledge reuse to externally specified rules rather than the agents themselves.Source: §1 · p. 2

Multi-Agent Paradigms

• Existing multi-agent systems commonly use human-defined roles and communication structures, assuming the best decomposition and interaction topology are known in advance.Source: §1 · p. 3

Contributions

• CORAL establishes new SOTA on 8 of 11 mathematical and systems optimization tasks, with a 2.5× higher improvement rate and 10× fewer evaluations than fixed evolutionary-search baselines.On Kernel Engineering, four co-evolving agents improve the best result from 1,363 to 1,103 cycles, a 20% gain.Source: §1 · p. 3
• CORAL realizes autonomous multi-agent evolution through shared persistent memory, asynchronous organization, and heartbeat-based interventions for long-horizon search.Source: §1 · p. 3

LLM-Driven Evolutionary Search

• Prior LLM-driven evolutionary systems use predefined parent selection, prompting, and mutation pipelines, leaving agents unable to decide what to explore or retain.Source: §2 · p. 3

Autonomous LLM Agents

• Autonomous coding and research agents support open-ended execution, but these systems target one-off task completion rather than sustained goal-driven optimization.Source: §2 · pp. 3–4

Multi-Agent Collaboration

• Existing multi-agent evolutionary systems mainly run stateless evaluation workers, whereas CORAL uses long-lived agents sharing scored attempts, notes, and skills.Source: §2 · p. 4
• Shared knowledge enables CORAL agents to exhibit technique diffusion, spontaneous consensus, and cross-referencing without hardcoded communication protocols.Source: §2 · p. 4

3.1 Preliminaries: Problem Formulation for Open-Ended Discovery

• Each improvement step retrieves context from shared memory, proposes a candidate, evaluates it for score and feedback, and updates persistent memory.Source: §3.1 · p. 4

3.2 From Fixed Search to Autonomous Multi-Agent Evolution

• Autonomous single-agent evolution lets agents decide what to retrieve, when to test or evaluate, and what knowledge to write back; multi-agent evolution runs these agents asynchronously through shared memory.Source: §3.2 · p. 4
• CORAL addresses long-horizon execution challenges with shared persistent memory, asynchronous organization, heartbeat interventions, and safeguards against drift, resource overload, and evaluator misuse.Source: §3.2 · p. 5

3.3 Core Mechanisms of CORAL

• The shared memory is a file-system-like library containing attempts, notes, and reusable skills that agents can retrieve, contribute to, and organize progressively.Source: §3.3 · pp. 5–6
• Agents work asynchronously in isolated workspaces while sharing persistent memory, allowing independent local exploration and indirect coordination through accumulated discoveries.Source: §3.3 · p. 6
• Heartbeat mechanisms prompt reflection during work, consolidate notes into skills after repeated attempts, and redirect search when progress stagnates.Source: §3.3 · p. 6

4.1 Experimental Setup

• The evaluation covers 6 mathematical and 5 systems optimization tasks, plus Kernel Engineering and Polyominoes stress tests, using matched budgets and four independent trials.Single-agent comparisons use Claude Code + Opus 4.6, while multi-agent math and systems experiments also test a fully open-source MiniMax M2.5 + OpenCode stack.Source: §4.1 · pp. 6–7

4.2 Autonomous Evolution Outperforms Fixed Evolutionary Search

• CORAL achieves the best final score on all 11 benchmark tasks and establishes new SOTA on 8, outperforming the strongest baseline, EvoX, on every task.Its improvement rate is 3–10× higher and it typically converges within 5–20 evaluations versus 60–100 for fixed evolutionary search methods.Source: §4.2 · p. 7

4.3 Multi-Agent Evolution Extends the Search Frontier

• Four-agent co-evolution extends the search frontier, producing an 18.3% cycle reduction on Kernel Engineering and a 5.0% score increase on Polyominoes over single-agent CORAL.The gains reflect diverse search trajectories and asynchronous shared persistent memory, not merely additional compute; web-enabled CORAL reaches 89.4 on Polyominoes.Source: §4.3 · p. 7, Table 2 · p. 8

4.4.1 Why Autonomous Evolution Works

• Local verification improves attempts most on compiled-code tasks: local testing occurs in 61% of Transaction attempts and 57% of Kernel Engineering attempts, versus 0% on Prism.Local execution often catches compilation failures before external evaluation, whereas hidden or non-reproducible evaluations limit its use.Source: §4.4.1 · pp. 8–9

4.4.2 Why Multi-Agent Organization Helps

• Cross-agent transfer is highly effective: Kernel Engineering attempts using another agent’s commit improve at 17% versus 9% overall, while Polyominoes transfers knowledge across 87% of rounds.The tasks use complementary transfer modes, with more code transfer on Kernel Engineering and more notes and skills transfer on Polyominoes; agent strategy vocabularies are also more than half unique.Source: §4.4.2 · p. 9

4.4.3 Ablations

• Ablations show that disabling knowledge artifacts degrades all three stress-test tasks, including an 18.6% Kernel Engineering regression from 1350 to 1601 cycles.Co-evolution also outperforms the best of four independent single-agent runs on all three tasks, showing gains beyond additional compute.Source: §4.4.3 · pp. 9–10

• Four agents discover solutions that no single agent finds, even when the single agent receives four times the compute.Multi-agent evolution pushes the frontier beyond single-agent autonomy.Source: §5 · p. 10
• CORAL replaces rigid evolutionary heuristics with autonomous control over retrieval, proposal, evaluation, and knowledge accumulation.Agents coordinate through shared persistent memory.Source: §5 · p. 10
• CORAL achieves substantially stronger performance across mathematical, algorithmic, and systems optimization tasks than fixed evolutionary-search baselines.Source: §5 · p. 10

• LLMs supported minor writing tasks and instantiated CORAL agents, but the authors developed the research and conducted the experiments, analyses, and evaluations.No LLM was used to generate research ideas, experimental results, figures, or evaluations.Source: LLM Usage Disclosure · p. 14

• Frontier foundation-model requirements make full deployment on local devices difficult.The authors propose training customized small models for CORAL.Source: A Limitations and Future Directions · p. 14
• Identical initialization and shared information currently limit bootstrapped heterogeneity across agents.Future variants could assign distinct personalities, roles, or private information to encourage behavioral diversity.Source: A Limitations and Future Directions · p. 14
• CORAL assumes a reasonably well-specified evaluator, although many open-ended problems have incomplete, difficult, or ambiguous evaluation.Possible future directions include evaluator refinement, learned critics, or human-agent negotiation over progress.Source: A Limitations and Future Directions · p. 14

B.1 New State-of-the-Art on Polyominoes Packing

• Polyominoes packing requires tightly packing all polyominoes into a grid to minimize unused area and is the hardest of 172 Frontier-CS problems.Figure 3 visualizes the packing solutions.Source: §B.1 · p. 14
• 89.4% coverage with four Claude Opus 4.6 agents surpasses the previous SOTA of 87%.A single-attempt Claude Opus 4.6 baseline achieves 56.0% coverage.Source: §B.1 · p. 14

B.2 Trajectory Statistics for Autonomous Self-Evolution

• Trajectory statistics measure improvement, local testing, prior-attempt inspection, knowledge creation, and knowledge access using rule-based filtering and LLM classification.Standard-task statistics aggregate four runs to reduce potential statistical bias.Source: §B.2 · p. 14
• Figure 3 compares a 56.0% single-attempt polyominoes baseline with an 89.4% CORAL solution that surpasses the previous 87% best-known score.The comparison uses Claude Opus 4.6 via Claude Code with web search access.Source: Figure 3 · p. 15
• Local verification and knowledge reuse are associated with successful improvement, with benefits depending on task characteristics.Tasks supporting cheap, reliable testing favor verification, while tasks with reusable intermediate insights show more knowledge creation and access.Source: §B.2 · pp. 14–15
• Table 4 summarizes trajectory statistics for standard tasks and two advanced benchmarks.The table provides the aggregate view underlying comparisons of verification and knowledge behaviors.Source: Table 4 · p. 15

C Additional Implementation Details

• CORAL organizes configuration, agent management, grading, workspace setup, shared memory, and core data types into six architecture modules.Configuration feeds the agent system and grader loader; workspaces link to shared hub state, and graders return ScoreBundle objects.Source: Figure 4 · p. 16

C.1.1 Agent Instruction Prompt (CORAL.md)

• Agents follow a plan–edit–evaluate–iterate workflow, inspect prior attempts and shared notes, and record reusable notes or skills after evaluations.The multi-agent prompt gives agents independent worktrees but shared visibility into attempts, notes, and skills; the single-agent variant emphasizes persistence and mandatory skill creation.Source: §C.1.1 · p. 17

C.1.2 Heartbeat Prompts

• Heartbeat prompts trigger reflection, knowledge consolidation, or strategic pivots during long-running search.Consolidation synthesizes notes and promotes validated techniques; pivot prompts diagnose plateaus, inspect strong attempts, and test fundamentally different approaches.Source: §C.1.2 · pp. 17–18

C.2 APIs and System Interfaces

• The CLI evaluation pipeline commits agent changes, loads a hidden grader, records scores and statuses, stores attempt records, checkpoints shared memory, and increments a global counter.The grader runs in a child process with a configurable hard timeout and returns a ScoreBundle.Source: §C.2 · pp. 18–19

C.3 User Interface

• The dashboard provides live leaderboard trajectories, agent logs, shared-note and skill browsing, health status, evaluation counts, and run switching.A Starlette backend serves REST endpoints and polls the shared directory every two seconds through Server-Sent Events.Source: §C.3 · p. 19, Figure 5 · p. 20

C.4 Shared Persistent Memory

• Shared memory is a centralized filesystem exposed through symbolic links, while unique attempt files and filenames avoid explicit locking and observed file conflicts.Each agent’s isolated worktree links to shared notes, skills, attempts, and heartbeat configuration.Source: §C.4 · p. 21, Figure 6 · p. 23

C.5 Heartbeat Mechanism

• Heartbeat monitoring polls attempts, fires interval or plateau triggers, interrupts and resumes agents with evaluation context, and preserves protected reflection and consolidation actions.Agents may customize heartbeat configurations, but protected actions cannot be deleted.Source: §C.5 · pp. 22–23, Table 7 · p. 22

C.6 Multi-Agent Coordination

• Multi-agent coordination uses isolated git worktrees, lifecycle management, session persistence, and automatic restart of unexpectedly terminated agents.The manager creates worktrees and symlinks, delivers heartbeats, resumes valid sessions, and starts fresh orientation prompts for invalid sessions.Source: §C.6 · p. 23

D.2 Task Configurations

• The evaluation spans mathematical optimization, systems optimization, and stress-test problems using multiple grading approaches.The suite includes six mathematical tasks, five systems tasks, Kernel Engineering, and Polyominoes.Source: §D.2 · p. 25

D.3 Evaluator Corrections

• Table 8 summarizes the evaluator bug fixes applied to the ADRS benchmark evaluators.The documented corrections are presented as reproducibility measures for correct scoring.Source: Table 8 · p. 26, §D.3 · p. 26
• Evaluator corrections ensure failures and invalid solutions affect scores rather than being silently skipped or rewarded.The fixes address PRISM failed placements, invalid transaction schedules, dropped EPLB experts, redundant averaging, and LLM-SQL mixed-type handling.Source: §D.3 · p. 26

E.1 Setup Details

• Experiments run on Linux CPU instances, including Kernel Engineering and Polyominoes because their evaluation uses simulation rather than GPU computation.Mathematical and systems tasks likewise do not require GPU acceleration.Source: §E.1 · p. 26
• Experiments use Claude Opus 4.6 for CORAL and baselines, with MiniMax M2.5 for open-source generalization experiments; internet access is configuration-dependent.The baselines are OpenEvolve, ShinkaEvolve, and EvoX.Source: §E.1 · pp. 26–27
• All baselines receive identical seed programs, evaluators, and wall-clock budgets.Mathematical and systems suites follow the SkyDiscover protocol.Source: §E.1 · p. 27
• Mathematical and systems experiments use three-hour budgets averaged over four runs, while stress tests stop after 100 non-improving evaluations or two hours.Multi-agent experiments use four agents with matched wall-clock time, and Bo4 approximates fourfold single-agent compute.Source: §E.1 · p. 27
• Default experiments use max turns=200 and identically initialized multi-agent agents without role specialization.These settings apply unless otherwise noted.Source: §E.1 · p. 27

E.2 Cost and Efficiency

• Typical three-hour single-agent runs cost approximately $30–60, while four-agent runs cost approximately 3–4× more.Context caching reduces repeated context-window costs within a session.Source: §E.2 · p. 27
• CORAL’s improvement rate is substantially higher while agents typically use fewer evaluation calls than structured baselines within the same wall-clock budget.The comparison indicates more efficient use of each evaluation call.Source: §E.2 · p. 27
• Infrastructure overhead is negligible relative to LLM API calls and grader execution.The monitoring loop polls every five seconds and heartbeat rendering is instantaneous.Source: §E.2 · p. 27