[2603.22363] Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale

Computer Science > Software Engineering arXiv:2603.22363 (cs) [Submitted on 23 Mar 2026] Title:Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale Authors:Janardhan Kulkarni View a PDF of the paper titled Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale, by Janardhan Kulkarni View PDF HTML (experimental) Abstract:Designing algorithms with provable guarantees that also work well in practice remains difficult, requiring both mathematical reasoning and careful implementation. Existing approaches that bridge worst-case theory and empirical performance, such as beyond-worst-case analysis and data-driven algorithm selection, typically assume prior distributional knowledge or restrict attention to a fixed pool of algorithms. Recent progress in LLMs suggests a new possibility: provable algorithm synthesis on the fly. To study this, we built Algorithmist, an autonomous researcher agent on top of GitHub Copilot that runs a multi-agent research-and-review loop, with separate stages for idea generation, algorithm and proof development, proof-guided implementation, and review of proofs, code, and their alignment. We evaluate Algorithmist on research-level tasks in private data analysis and clustering. When asked to design practical methods that jointly satisfy privacy, approximation, and interpretability requirements, it produced provably sound and empirically effective algorithms, together with research-style write...