Stellar Colosseum Uses Dependency Graphs and Falsification Loops to Manage Long-Horizon Mathematical Agents

Stellar Colosseum attempts to address one of the most common failure modes of long-horizon research agents: a model chooses the wrong strategy at the outset, then continues writing dozens of pages based on a faulty premise. The system first has multiple agents generate “strategy cards” that record the core mechanism, required lemmas, evidence, bottlenecks, and unresolved obligations. A readiness gate then determines whether a path is mature enough to proceed. Only after passing the gate is a strategy converted into a graph of proof sections connected by dependency edges. Independent sections can be handled in parallel, and when a verifier finds a problem, its critique needs to be routed back only to the affected sections.

At every stage, the system generates multiple candidates and asks other agents to actively search for counterexamples, circular reasoning, missing assumptions, or misapplied theorems. Candidates and critiques are not resolved through a direct majority vote. Instead, they are merged layer by layer through overlapping randomized sampling trees. In the TCS-Bench configuration described in the paper, the width narrows from 32 to 16, 8, 5, and finally 1, with each aggregation node receiving five inputs. A shared directory preserves known lemmas, failed approaches, literature, and computational observations so that later rounds do not repeat the same mistakes. When the same architecture is adapted to programming problems, the final sections become C++ implementations, and compilation results, public examples, and stress-test results are fed back into the revision loop.

On TCS-Bench, which consists of 300 research-level theorem tasks, Gemini 3.1 Pro and Gemini 3.7 Flash score 54% and 55%, respectively, when used with Colosseum on their own. The team then uses eight Flash critiques to decide which model’s proof to select, reaching 71%, or 213 solved problems. The idealized best-of-two ceiling is 77.3%, indicating that the selector still discards some correct candidates. In a separate experiment on 222 Codeforces problems, the system solves 218 after execution feedback is added, compared with 213 for the baseline without that feedback.

The significance of this work lies in elevating inference-time compute from simply “sampling a few more answers” into an engineering workflow with explicit state, dependencies, and bounded rollback. However, the 71% result combines two models, eight critiques, and reference-assisted grading, so it should not be treated as the accuracy of a single agent. The Codeforces comparison also changes the revision budget at the same time. The paper releases some proof artifacts but does not provide the complete Colosseum harness needed for direct reproduction, a detailed cost breakdown, or per-task trajectories. The next questions to watch are component ablations, formal verification, and whether the system still outperforms a simple best-of-N approach under fixed token and time budgets.