Stellar Colosseum: A Many-Agent Harness for Long-Horizon Mathematical Research

Paper: *Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science* Authors: Honghao Lin, David P. Woodruff, Yuan Deng, Jieming Mao, Song Zuo, Vahab Mirrokni (Google Research & CMU) arXiv: 2609.15983

Stellar Colosseum takes inspiration from the Roman arena: instead of a single gladiator, many LLM agents compete and collaborate as a research team. The goal is not answering a single math question, but conducting research — exploring strategies, decomposing theorems into interdependent lemmas, allocating resources per subproblem, and iterating after failures.

Why Research Is Harder Than Answering

Proving a research-level theorem involves challenges beyond typical reasoning benchmarks:

• Strategic uncertainty: which direction will work is unknown upfront.
• Distributed technical difficulty: bottlenecks across interdependent lemmas.
• Long outputs and error accumulation: proofs can span dozens of pages; symbols and assumptions drift.
• Partial progress from failure: failed attempts may yield counterexamples, restricted versions, or reusable lemmas.

Architecture: Two Layers

Layer 1: Research Workflow

1. Strategy Exploration — parallel candidate strategies, each stating its core mechanism, needed lemmas, expected bottlenecks, and a verifiable test. 2. Readiness Gate — decides whether some route is concrete enough to start proof construction (stable core structure, precise unresolved claims, no architectural bridges pending). 3. Decomposition & Parallel Construction — the chosen strategy becomes a numbered proof skeleton whose dependencies form a DAG; independent sections are solved in parallel. Passed sections are committed; failed sections are re-solved locally without touching finished work. 4. Global Verification — independent reviewers check the full proof for cross-section consistency; defects are localized so fixes are local, not from scratch.

Layer 2: Adversarial In-Stage Reasoning

• Parallel candidate generation with varied representations, temperatures, and prompt perspectives.
• Targeted falsification — adversarial reviewers hunt for counterexamples, invalid inferences, circular reasoning; refutation records stay attached to candidates.
• Tree aggregation — e.g., 128 candidates are merged pairwise-ish via overlapping random sampling (each candidate participates ~2.5 times on average), with constructive intermediate merges. Crucially, objections are never averaged away: a concrete fatal defect vetoes a candidate, unlike voting or ranking.

Shared Memory Across Rounds

• Failed attempts carry their drafts and reviewer feedback into the next round.
• A Knowledge Directory curates reusable knowledge into four categories: theorems/lemmas, failed approaches (with exact failure points), references, and observations.

New Research Results

Colosseum is not just a benchmark system:
• Strong coresets for ℓp subspace approximation (p > 2): improved coreset size from O(k^{p/2}ε^{-p}) to O(k^{p/2}ε^{-2}) for the same sampling rule, by keeping truncation terms in sampling probabilities.
• Sparse least squares: a conditional lower bound (under a randomized exact-volume small-set expansion assumption) showing no fixed sublinear power of the condition number can replace the linear dependence on sparsity.
• Maximum inner product embeddings: nearly closed the exponent gap (1/ε vs 1/ε²) for Chamfer similarity, proving a dimension lower bound of m^{c_δ/ε^{2-2δ}} for single-vector representations.
• Knuth's cyclic problem: a 46-page proof draft for the even case and 75 pages for subsequent constructions.
• Erdős unit distance problem: independently rediscovered (offline, with Gemini 3.1 Pro) the core architecture of a counterexample solution — a number-theoretic approach based on divergence towers and relative unit groups — across 15 rounds, producing a 22-page draft.

Benchmark Results

• TCS-Bench (300 theorem-proving tasks from 2020–2026 FOCS/STOC/SODA papers): 71.0% accuracy, using Gemini 3.1 Pro and Gemini 3.7 Flash with a critic-based selection between two runs.
• Codeforces: 218 of 222 problems solved with the proof-oriented pipeline plus execution feedback (Gemini 3.1 Pro).

Why It Works

1. Diversity beats strength — many varied candidates plus adversarial filtering, rather than one model thinking longest. 2. Failure is valuable — structured knowledge from failures (exact failure points, restricted versions) turns wasted compute into assets. 3. Global view + local repair — DAG decomposition enables fixing defects without restarting the proof. 4. Adversarial verification beats consensus — voting hides shared blind spots; a concrete counterexample outweighs a hundred "looks right" judgments.

Limitations

• No correctness guarantee: outputs are natural-language proofs without formal verification; use is best as a human collaborator.
• Resource cost: tree aggregation with 128 leaves and multi-round verification requires many API calls.
• Depends on base models: no amount of sampling fixes a base model lacking domain intuition.
• No human feedback loop: a single expert hint can beat dozens of automated explorations.

Takeaway

Colosseum reframes AI research as organized teamwork — explorers, skeptics, synthesizers, and memory keepers — amplifying compute to cover strategy spaces humans would need years to explore, so mathematicians can spend creativity and intuition where they matter most.

References

1. Lin, H., Woodruff, D. P., Deng, Y., Mao, J., Zuo, S., & Mirrokni, V. (2026). Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science. *arXiv:2609.15983*.