PaperlayerView exact revision on arXiv

Source-linked AI summary

Coral Discovery: The Division of Cognitive Labor in Autonomous Research

Xinxing Ren, Qianbo Zang, Ziyan Wang, Suman Deb, Qiang Yang, Caelum Forder, Peter Carroll, Gilead Gevero, Jing Liu, Yali Du, Milind Tambe, Zekun Guo

arXiv:2610.33281v1cs.MA

TL;DR

Score-only leaderboards lack an approach-level unit and rate of return for dividing agents’ effort between exploration and exploitation. Coral Discovery adds verifier-assigned direction labels, a board for allocating attention, and per-direction credit. Across nine tasks, it beats MIT CORAL on six, ties on one, and loses on two.

  • Problem

    A score-sorted shared memory identifies the leader but lacks an approach-level unit and rate of return for deciding when agents should deepen an approach or explore another.

    Source: §1 · p. 2

  • Method

    Coral Discovery uses a verifier to label each attempt’s direction and method, while a shared board estimates per-direction returns and advises agents on attention and new directions.

    Source: §1 · pp. 2–3

  • Results

    Coral Discovery beats MIT CORAL on 6 tasks, ties on 1, and falls behind on 2.

    Source: §1 · p. 3, §8 · p. 12

  • Takeaways & Limitations

    Direction labels show that leading scores came from directions a score-only community never entered, which were opened and kept alive until they produced a record.

    Source: §1 · p. 3

    Exploration’s cost was not repaid on LLM-SQL and Txn Sched., where Coral Discovery finished below the 4-agent baseline and the single-agent result, respectively.

    Source: §7 · p. 12

Abstract

from arXiv · show

A research community is only as strong as the way it divides its cognitive labour. The philosopher Philip Kitcher argued that researchers should not all pursue the most promising approach. Credit rules, not a central plan, keep some of them on other lines. We bring this question to autonomous research, where Large Language Model agents improve programs against a deterministic grader. Agents that share only a score follow the leader and converge onto one approach. Coral Discovery gives the community a direction board. A verifier labels every attempt with a direction, the mechanism earning the score, and a method, one change within it. Per direction, the board tracks how much each eval improves the score, adds an exploration bonus for little-tried directions, prices the option of opening a new direction, and suggests how many agents each direction deserves. Credit is earned against a direction's own best, so a lagging direction keeps its agents. Agents finish their lines, then treat the board as advice. We test on nine tasks with the same model and budget, without grader access except for Kernel. Coral Discovery beats the strongest open autonomous multi-agent system on 6 tasks, ties on 1, and loses on 2. Against published numbers, it is best or tied on 4. It improves the reported Kernel result from 1103 to 1095 cycles and passes 1103 at eval 275, under half of the 596 used before. It sets a new Polyominoes state of the art, 91.78 against 87.0. Direction labels show that the leading scores rest on directions a score-only community never entered. Code will be released shortly.

1 Introduction

Research communities must divide effort between established and less-promising approaches, but score-only leaderboards lack an approach-level unit and rate of return. Coral Discovery adds a shared direction board and credit rules to autonomous research agents.

1 Introduction

  • Autonomous evaluator-guided research lets agents propose and evaluate candidates, while fixed evolutionary algorithms decide which parents to select, what to retain, and when to evaluate.Long-running agents instead retrieve, propose, evaluate, and write back through shared memory.Source: §1 · pp. 1–2
  • A verifier labels each attempt with a direction—the score-earning mechanism—and a method, one change within that direction.The verifier classifies the direction from the program diff; direction is the unit for budget allocation and return statistics, while method records work within it.Source: §1 · pp. 2–3
  • The board tracks yield, exploration-adjusted potential, wanted and claimed agents, and the estimated value of opening a new direction, NEW.Credit is measured against each direction’s own best, so records in lagging directions can earn credit equal to records in the leading direction.Source: §1 · pp. 2–3
  • Agents finish their current line before reading the board, then claim a direction and method, edit, run one eval, and write an insight; board advice is nonbinding.Claims face a head-count cap and duplicate check, and unfinished work loops back without consulting the board.Source: §1 · p. 3, Figure 2 · p. 4
  • Coral Discovery beats MIT CORAL on 6 tasks, ties on 1, and falls behind on 2; it is best or tied-best against published results on 4 tasks.The losses are LLM-SQL and Txn Sched.Source: §1 · p. 3
  • Kernel improves from 1103 to 1095 cycles, and Polyominoes reaches 91.78 against the previous 87.0 state of the art.Coral Discovery passes 1103 cycles at eval 275, fewer than half of the 596 evals used before.Source: §1 · p. 3
  • Direction labels show that leading scores came from directions a score-only community never entered, which the authors attribute to claim rules, NEW, per-direction credit, and the inspired-by threshold.Those directions were opened and kept alive until they produced a record.Source: §1 · p. 3

2 Related Work

Related work spans evaluator-guided LLM search, autonomous multi-agent systems, and exploration–exploitation methods. Coral Discovery divides a single objective over approaches and uses a shared, verified ledger.

2 Related Work

  • Evaluator-guided LLM research ranges from fixed evolutionary loops to autonomous agents; Coral Discovery adds a community-level layer that allocates evaluations over approaches.Fixed algorithms select parents and retention, whereas autonomous systems hand parts of the loop to agents.Source: §2 · p. 4
  • Unlike multi-agent systems that divide work into subtasks, Coral Discovery divides one objective over directions and replaces negotiation with a shared, verified ledger.AgentRadio reports gains concentrated on decomposable tasks, with interdependent subtasks requiring execution-time coordination.Source: §2 · p. 4
  • Figure 3 separates code lineage from direction membership: borrowing is declared with –inspired-by edges, and direction labels attach to nodes rather than subtrees.A verifier judges direction at each evaluation and records its verdict on the node card.Source: Figure 3 · p. 5
  • The board treats directions as arms, using windowed-mean yield, a UCB-style potential bonus, and NEW as an expansion arm; its reward is each direction’s own new high and its policy is advisory.This contrasts with raw-score rewards and binding choices.Source: §2 · p. 5

3 Method: Coral Discovery

Coral Discovery adds verifier-assigned directions and agent-written methods, a direction board that estimates returns and exploration value, and a round protocol that keeps the board advisory.

3 Method: Coral Discovery

  • Coral Discovery combines direction-and-method labels, the direction board, and the round protocol as its three method components.Agents interact with shared state through coral commands, including board, claim, eval, and insight operations.Source: §3 · p. 5, §3.3 · p. 7

3.1 Directions and Methods

  • A direction is the mechanism by which a program earns its score; a method is one concrete change within that mechanism.The verifier assigns directions from diffs, and direction labels nodes rather than code subtrees.Source: §3.1 · pp. 5–6

3.2 The Direction Board

  • The direction board estimates per-direction returns and exploration value, then suggests agent counts while leaving allocation decisions to agents.Credit rewards records above a threshold that includes the direction’s own best; yield measures mean credit per eval, and potential adds an exploration bonus. NEW estimates whether opening another direction is worthwhile.Source: §3.2 · p. 6

3.3 Protocol

  • The manager runs rounds in two phases: agents finish or diagnose their own line before consulting the board, then claim, edit, evaluate once, and record an insight.Claims are capped at two agents per direction, checked for duplicate methods and mechanisms, and the board remains advisory.Source: §3.3 · p. 7

4 Experimental Setup

The experiments compare Coral Discovery with MIT CORAL baselines across nine tasks under controlled agent, model, and access conditions. Results are reported using repeated runs, evaluation counts, and task-specific evaluation limits.

4.1 Tasks, Baselines and Cited Numbers

  • Nine tasks span five groups; Coral Discovery adds the direction board to four agents and the eval budget, against one-agent or four-agent MIT CORAL baselines.The tasks cover kernel optimisation, combinatorial packing, analysis and combinatorics, LLM inference systems, and data and cloud systems.Source: §4.1 · p. 7

4.2 Experimental Conditions

  • All three methods use Claude Opus 4.6 at medium effort, with no internet or grader access except for Kernel Eng.The grader is withheld because some graders contain scored test data or workloads; the authors report no access attempts in the runs.Source: §4.2 · p. 7

4.3 Evaluation and Reporting

  • Each configuration ran three times; reporting uses the best run and its eval count, with crashes and timeouts included, plus best@k and task-specific eval caps.Cloudcast counts the first 20 evals; other tasks count the first 100 except Kernel, which is uncapped. Table 2 juxtaposes six published columns with three Opus 4.6 runs.Source: §4.3 · pp. 7–8, Table 2 · p. 8

5 Results

Against the reproduced MIT CORAL system, Coral Discovery wins on six tasks, ties on one, and loses on two; across published results, it is best or tied on four. Its gains over the four-agent baseline often trace to records in directions that baseline never entered.

5.1 Main results

  • 6 wins, 1 tie, and 2 losses: Coral Discovery beats the reproduced MIT CORAL system on six tasks, ties on Cloudcast, and loses on LLM-SQL and Txn Sched.The four clear-margin results are Kernel 1095 vs. 1138, Polyominoes 91.78 vs. 80.55, Signal 0.7904 vs. 0.7718, and Erdős 0.380984 vs. 0.381264.Source: §5.1 · p. 8
  • Best or tied-best on 4 tasks against published numbers, Coral Discovery is sole best on Kernel Eng. and Polyominoes.On Kernel, it improves the reported result from 1103 to 1095 cycles and passes 1103 at eval 275, under half of the prior 596 evals; Polyominoes reaches 91.78 against the cited 87.0.Source: §5.1 · p. 8
  • Figure 4 plots best-so-far curves for the single agent, four-agent baseline, and Coral Discovery across nine tasks, marking final-best evals and values.Cloudcast shows only the first 20 evals, within which all three methods reach 618.Source: Figure 4 · p. 9
  • The head-to-head against the paper’s CORAL column yields 4 wins, 2 ties, and 3 losses, with all three losses to results obtained using web access and grader reading.Signal Proc.’s 0.8229 is not comparable with Discovery’s 0.7904 because the grader contains the test signals; Discovery’s 0.7904 exceeds the cited SOTA of 0.7429.Source: §5.1 · p. 9

5.2 Where the lead comes from

  • The analysis re-labels every submission by verifier-assigned direction and compares Discovery-only directions, its margin over the baseline, and the share of gain from those directions.Table 3 reports direction counts, records, gain shares from own records and lineage, and Discovery-only directions in winning lineages.Source: §5.2 · p. 9, Table 3 · p. 10
  • On 6 of the 7 tasks where Discovery leads the four-agent baseline, its winning lineage includes directions that baseline never entered, and the entire gain comes from records built on them.On Kernel Eng., Polyominoes, and Txn Sched., every record exceeding the baseline’s final best falls in a Discovery-only direction; EPLB’s lead involves no new direction, while LLM-SQL shows an exploration cost.Source: §5.2 · pp. 9–10, Table 3 · p. 10

6 Analysis: Two Why-Questions

The analysis asks why Discovery opens directions the baseline never enters and why its champion direction merges results from other directions. Its board sustains both new openings and local records while exploration and exploitation continue in parallel.

6.1 Why does Discovery open directions the baseline never does?

  • 68 directions opened by Discovery versus 41 by the baseline, with 34 versus 15 opened after the first third; all six tasks’ gains rest on directions the baseline never entered.The 91.78 Polyominoes result comes from sa-shrink-boundary-removal, opened only at eval 33.Source: §6.1 · p. 10

6.2 Why does Discovery’s champion direction merge in more directions?

  • Credit against each direction’s own best lets lagging directions keep yield and agents, while their node cards let others reuse components.Local records short of the global best were 9 vs. 0 on Signal Proc., 4 vs. 0 on Circle-Pack., and 15 vs. 4 on Erdős Over.Source: §6.2 · p. 10
  • Exploration and exploitation proceed simultaneously: last-third HHI was 1.00 vs. 0.66 on Signal Proc., 1.00 vs. 0.36 on Circle-Pack., and 0.82 vs. 0.29 on Erdős Over., baseline versus Discovery.The three champion directions opened in the second half; after Signal Proc.’s champion first set a global record, it received 76% of the remaining 38 evals.Source: §6.2 · pp. 10–11

6.1 Why does Discovery open directions the baseline never does?

  • Figure 5 compares re-labelled directions opened by each method across the full run and its first, middle, and last thirds.Blue-grey denotes the four-agent baseline and rose denotes Coral Discovery.Source: Figure 5 · p. 11

6.2 Why does Discovery’s champion direction merge in more directions?

  • Figure 6 depicts local records and continuing exploration alongside exploitation for the baseline and Coral Discovery.Blue-grey denotes the four-agent baseline and rose denotes Coral Discovery.Source: Figure 6 · p. 11

7 Limitations: Exploration Has a Cost

Exploration’s cost is visible on LLM-SQL and Txn Sched., where Coral Discovery finished below a comparator. The cases suggest that spreading effort can miss the best direction or lose to a single agent’s accumulated work within one direction.

7 Limitations: Exploration Has a Cost

  • On LLM-SQL, Coral Discovery finished below the 4-agent baseline, and on Txn Sched. it finished below the single agent.On LLM-SQL, its champion direction remained below the baseline’s best; on Txn Sched., its 4566 at eval 71 remained below the single agent’s 4608 at eval 33.Source: §7 · p. 12
  • On LLM-SQL, Coral Discovery opened 7 directions versus the baseline’s 2, but 15% of its evals went to directions that never produced a record.Its champion tree-row-greedy-col used 72 evals for 18 records and still stayed below the baseline’s lexsort-greedy-prefix, which produced 17 records over 99 evals.Source: §7 · p. 12
  • Opening more directions raises the chance of finding headroom, but within a fixed budget it does not ensure the direction with headroom is opened.On LLM-SQL, the single agent found backward-tail-reopt, a direction Coral Discovery never found.Source: §7 · p. 12
  • On Txn Sched., all three methods ended in one champion direction, and the single agent won within a direction it shared with the others.The authors conjecture that one agent may benefit when an outcome depends on method work within one direction, because it retains the whole line’s process history.Source: §7 · p. 12

8 Conclusion

Coral Discovery structures how autonomous research agents divide their effort through a verifier, direction board, and round protocol. On nine MIT CORAL tasks, it outperformed the reproduced system on six, while direction labels showed that leading scores came from directions the baseline never entered.

8 Conclusion

  • A verifier files each attempt under a direction, a board estimates each direction’s return and prices opening another, and agents finish their line before treating the board as advice.The board’s role is advisory; agents make the decision after completing their own line.Source: §8 · p. 12
  • Coral Discovery outperformed the reproduced MIT CORAL system on 6 of 9 tasks, improved Kernel Eng. from 1103 to 1095 cycles, and set a Polyominoes state of the art at 91.78 versus 87.0.It passed 1103 cycles at eval 275, fewer than half of the 596 evals MIT CORAL used.Source: §8 · p. 12
  • The leading scores came from directions the baseline never entered, while spreading effort sometimes missed headroom or failed to beat a single agent polishing one direction.The paper attributes the opening and persistence of these directions to the combined claim rule, NEW arm, and per-direction credit.Source: §8 · p. 13

A Command Set

Coral Discovery’s agent-facing commands provide access to shared state through coral commands, with a board, direction history, claims, insights, and tree views. The command set also replaces several MIT CORAL operations with functions aligned to the new protocol.

A Command Set

  • Agents use coral commands to access shared state because native git is disabled in their workspaces.Table 5 covers the complete agent-facing command set relative to MIT CORAL.Source: A Command Set · p. 17, Table 5 · p. 17
  • coral board shows direction statistics, the NEW row, agent claims, and the global best, while coral direction lists a direction’s attempts, credit, and insights.coral claim assigns an agent to a direction or opens a provisional one with –new.Source: A Command Set · p. 17
  • The command set adds five commands, extends coral eval, inherits four commands unchanged, and withdraws four MIT CORAL commands in this mode.The leaderboard is replaced by board, direction, and tree show; shared notes by method and insight on node cards; and revert by checkout.Source: Table 5 · p. 17, A Command Set · p. 17

Related papers

Loading 2610.33281v1…