Colombo: A Frontier-to-Frontier Autoresearch System for Oracle-Based Optimization

Haihan Zhang, Wendao Wu, Chenheng Zhang, Chunyuan Zheng, Yanyi Li, Cong Fang, Haoxuan Li, Zhouchen LinarXiv 2026 · arXiv

TL;DR

Colombo is a self-organizing AI research system designed to autonomously navigate the "frontier" of mathematical optimization. By pitting candidate algorithms against adversarial problem instances and verifying its proofs through the Lean formal language, Colombo has already established optimal or near-optimal complexity rates for over 50 distinct research settings, marking a significant step toward fully autonomous, self-regenerating science.

What Problem Does This Paper Address?

In the field of oracle-based optimization, researchers seek to answer a fundamental question: How efficiently can a specific class of problems be solved given a certain type of information (an "oracle")? This involves finding the "upper bound" (the best possible algorithm) and the "lower bound" (the fundamental limit no algorithm can beat). When these two bounds don't match, a "research frontier" exists.

Traditionally, identifying these gaps, formulating conjectures, and proving theorems is a slow, manual process prone to human oversight. While AI has helped solve specific problems (like protein folding), creating a system that can organize its own research agenda, reuse knowledge across different settings, and ensure mathematical correctness remains a major challenge. Colombo aims to bridge this gap by automating the entire lifecycle of a theoretical researcher.

Methods

Colombo operates through a hierarchical, self-organizing architecture that treats research as a recursive process of "frontier renewal."

Figure 1. Frontier-to-frontier renewal. Colombo perceives the current research frontier, formulates problems, consolidates supported knowledge, and regenerates the frontier for subsequent inquiry.

Key components include:

  • The Sensorium & Complexity Atlas: The system maintains a "living map" of optimization settings. It identifies gaps between known upper and lower bounds to prioritize new research directions.
  • The Brain: Acting as a central coordinator, the Brain decomposes high-level research goals into concrete subproblems and manages a fleet of specialized "Cells."
  • Research Cells: These are specialized agents that focus on different tasks: designing new algorithms (upper bounds), constructing "hard" problem instances (lower bounds), or running experiments to test conjectures.
  • Adversarial Co-Ascent: This is the core engine of discovery. Algorithms and hard problem families are developed in a reciprocal "arms race." Algorithms reveal usable information that motivates harder constructions, while hard families expose algorithm limitations that redirect design.
  • Formal Certification: To prevent "hallucinations" common in LLMs, all mathematical claims are translated into Lean, a formal proof language. A machine-checked kernel verifies every step of the proof before it is accepted into the system's long-term memory.
Figure 2. Architecture of Colombo. The Sensorium prepares a selected Setting Profile; the Brain plans and coordinates specialized Cells, integrates their findings, and replans around the remaining complexity gap. Independent review and Lean-based formal certification validate results, which enrich Long-Term Memory, support paper composition, and renew the frontier.

Datasets

Unlike typical ML papers, Colombo does not train on standard image or text datasets. Instead, its "dataset" is the Complexity Atlas, which currently contains 56 research settings across six task classes, including:

  • Single-objective optimization (zeroth, first, and second-order)
  • Variational Inequalities (VIs)
  • Minimax and Saddle-Point problems
  • Stochastic Bilevel Optimization
  • Matrix Computation (e.g., low-rank approximation)

Key Insights and Ideas

  • Autopoietic Science: The authors introduce this concept to describe a scientific process that regenerates the conditions for its own progress. As Colombo closes one gap, it automatically identifies the next adjacent frontier, effectively "reshaping how inquiry is organized."
  • Reciprocal Challenge: The most effective way to find the "truth" of a problem's complexity is to treat it as a game between an algorithm designer and a "nature" that wants to make the problem as hard as possible.
  • Knowledge Reuse: By maintaining a "Long-Term Memory" of proof techniques, hard families, and algorithm components, Colombo can transfer insights from one domain (e.g., smooth convex optimization) to another (e.g., stochastic bilevel optimization).
  • Formal Verification as a Requirement: By integrating Lean-based certification directly into the research loop, the system ensures that its autonomous discoveries are not just plausible, but indisputably correct.

Key Results

Colombo has successfully established optimal or near-optimal rates for over 50 settings, often resolving long-standing open questions:

  • Zeroth-Order Optimization: It closed a 30-year gap regarding the intrinsic dimension cost of exact function-value access in smooth convex optimization.
  • First-Order Nonconvex Gaps: It settled the optimal accuracy exponents for randomized algorithms under fixed finite-order smoothness, matching deterministic upper bounds that were previously thought to be potentially improvable by randomization.
  • Bilevel Optimization: It established sharp accuracy limits for stochastic bilevel problems, settling the accuracy exponent and quantifying the dependence on problem conditioning.
  • Matrix Computation: It supplied missing multiplicative rank dependencies for low-rank approximation algorithms, matching existing upper bounds for various Schatten norms.

Limitations and Future Work

  • Domain Specificity: Currently, Colombo is specialized for oracle-based optimization. While this is a foundational area, extending the system to more empirical fields (like biology or chemistry) would require different types of "oracles" (e.g., robotic labs).
  • Human-in-the-Loop: The system still utilizes a "human approval gate" to select Setting Profiles before the Brain begins its work.
  • LLM Dependency: The system was instantiated with GPT-5.6 Sol; its performance is inherently tied to the reasoning capabilities of the underlying language model.
  • Future Directions: The authors suggest adapting the framework to GPU kernel autotuning and LLM training procedure design, where the "oracle" is the actual hardware performance or validation loss.

Summary updated

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.
BibTeX
@misc{zhang2026colombo,
  author = {Haihan Zhang and Wendao Wu and Chenheng Zhang and Chunyuan Zheng and Yanyi Li and Cong Fang and Haoxuan Li and Zhouchen Lin},
  title = {{Colombo: A Frontier-to-Frontier Autoresearch System for Oracle-Based Optimization}},
  year = {2026},
  eprint = {2611.23080},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.23080},
}
Figure