Colombo: A Frontier-to-Frontier Autoresearch System for Oracle-Based Optimization
Organizations: Peking University
Abstract
Science advances from frontier to frontier as discoveries reshape what is known and create the basis for further discovery. We present Colombo, a self-organizing AI researcher that drives this renewal, first instantiated in oracle-based optimization. Here, the central question is how efficiently a problem class can be solved through a prescribed information interface and what costs no admissible algorithm can avoid. The gap between achievable guarantees and unavoidable limits defines the frontier recorded in its Complexity Atlas, a living map of frontier settings and the current state of knowledge. Self-Organization turns unresolved gaps into adaptive research programmes, coordinating conjecture formation, mathematical investigation, and replanning as evidence accumulates. Adversarial Co-Ascent develops algorithms and hard families through reciprocal challenge, exposing mechanisms of information use and concealment that guide stronger methods and proofs of unavoidable costs. Independent review and Lean-based formal certification check mathematical claims, while the Long-Term Memory carries supported findings and research experience across settings. To date, Colombo has established optimal or near-optimal rates for more than fifty settings in the Atlas. Colombo thus takes a concrete step toward Autopoietic Science: a scientific process whose validated advances regenerate the conditions of its own progress, continually reshaping how inquiry is organized and what it can discover.
Figures & tables
| Task | Primary oracle type | Total | |||
|---|---|---|---|---|---|
| 0th | 1st | 2nd+ | Special | ||
| Single-Objective Optimization | 10 | 17 | 8 | 1 | 34 |
| Variational Inequalities | 1 | – | 2 | – | 3 |
| Minimax & Saddle-Point | – | 6 | 2 | 1 | 9 |
| Matrix Computation | 1 | – | – | 1 | 2 |
| Online Learning & Bandit | 4 | 1 | – | 1 | 6 |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
| (a) General monotone VIs: tangent residual | |||
| Work | Algorithms | Upper bound | Lower bound |
| Chen et al. (2026d) August 2026 preprint † | Det. | — | |
| Colombo: VI (Sep. 11, 2026) ( Zhang et al., 2026b ) | Det. | — | |
| Colombo: VI (Sep. 11, 2026) ( Zhang et al., 2026b ) | Rand. | — | |
| Zhang et al. (2026m) September 20 preprint | Det. | — | |
| (b) Scalar convex–concave problems: tangent residual and saddle gap | |||
| Work and result | Upper bound | Lower bound |
|---|---|---|
| (a) Baseline smoothness and conditioning | ||
| Kwon et al. (2023) , Cor. 4.2(a) | — | |
| Kwon et al. (2024) -aware oracle; fixed conditioning | — | |
| Chen et al. (2025) , Thm. E.3 | — | |
| Chen et al. (2026a) , Thm. 5.2 † | — | |
| Gu et al. (2026) , Thm. 4.1 September 18 preprint | — | |
Autonomous Research Agents
Autonomous research agents use language models and tools to search literature, design and run experiments, analyze results, and support scientific discovery.
See all 350 papers