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

Janardhan Kulkarni

cs.SEMar 23, 2026

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

Authors: Janardhan Kulkarni

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 writeups and audited implementations. It also found improved algorithms in some settings, explained principled barriers in others, and uncovered a subtle proof bug in prior published work. More broadly, our results suggest a new paradigm in which LLM systems generate research-paper-quality algorithmic artifacts tailored to each dataset and deployment setting. They also point to a proof-first code-synthesis paradigm, in which code is developed alongside a structured natural-language proof intermediate representation and kept aligned with it throughout synthesis.

Figures & tables

Figure 2: Algorithmist ’s architecture: multi-agent workflow for structured NLP proof and audited code.

Figure 3: Proof or mathematical analysis helps prune costly downstream experiments.

Paper Section	File	Function
Def. C.2 : BW calibration	privacy.py	calibrate_sigma()
Eq. ( 6 ): Spillover threshold	privacy.py	compute_rho1()
Sec. C.2 : $k$ -gram threshold	privacy.py	compute_rho_kgram()
Lemma C.5 : Weighted histogram	algorithm.py	build_histogram()
Def. C.8 : FIP pruning	algorithm.py	fip_prune()
Def. C.10 : HT threshold	algorithm.py	compute_tau()

Table 7: Mapping from paper sections to implementation.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

$\varepsilon$	$\Delta_{0}$	$\rho_{\mathrm{PG}}$	$\rho_{\mathrm{zero}}$	Surcharge	Relative
1.0	10	16.56	16.25	0.32	1.9%
1.0	100	17.97	17.87	0.10	0.6%
3.0	10	6.44	6.11	0.32	5.0%
3.0	100	6.82	6.72	0.10	1.5%
5.0	10	4.50	3.94	0.56	12.5%
5.0	100	4.50	4.33	0.17	3.8%

Appendix

Table 1: Policy Gaussian threshold and the zero-mass benchmark.

$\varepsilon$	$\Delta_{0}$	$\|S\|$ (Policy Gaussian)	$\|S\|$ (benchmark)	Gap (%)
1.0	10	400	403	0.7%
1.0	100	417	420	0.7%
3.0	10	1091	1104	1.2%
3.0	100	1193	1218	2.1%
5.0	10	1625	1670	2.8%
5.0	100	1931	1977	2.4%

Appendix

Table 2: Output size: Policy Gaussian vs. the zero-mass benchmark. Zipf data,

20{,}000

users.

$\varepsilon=4.0$
	Synthetic			Real
Algorithm	Zipf	Clustered	Heavy-tail	Reddit
DPNE baseline	12,876	8,871	13,136	37,161
AFP-DPNE	18,220	10,322	16,916	68,498
Improvement	+41.5%	+16.4%	+28.8%	+84.3%
$\varepsilon=1.0$

Appendix

Table 3: Total

n

-grams extracted (levels 1–6). All numbers are from seed 42.

	Total	Genuine	Spurious	Spur. %
DPNE baseline	37,161	36,951	210	0.6%
AFP-DPNE	68,498	62,548	5,950	8.7%

Appendix

Table 4: Genuine vs. spurious breakdown (Reddit,

\varepsilon=4

Variant	Total	vs. full AFP
AFP-DPNE (FIP + HT)	18,220	—
w/o FIP ( $m=\infty$ )	17,914	$-1.7\%$
w/o HT ( $\gamma=0$ )	12,876	$-29.3\%$
DPNE baseline	12,876	$-29.3\%$

Appendix

Table 5: Ablation study on Zipf (

\varepsilon=4

\Delta_{0}=100

, seed 42).

$\varepsilon$	Correct/Total	Fraction	$p$ -value	Verdict
1.0	161/300	0.537	1.000	✓ PASS
4.0	160/300	0.533	1.000	✓ PASS
8.0	160/300	0.533	1.000	✓ PASS
Broken (no noise)	100/100	1.000	0.168	see text

Appendix

Table 6: Privacy audit (Zipf 10K users,

\delta=e^{-10}

m=200

canaries, 3 runs aggregated).

Experiment	Setting	Observation
Cost ratios	Six configurations with $k\in\{2,3,4\}$ , $\|\mathcal{G}\|\in\{8,10,12\}$ , $\varepsilon\in\{0.5,1,2\}$ , and $300$ – $500$ random seeds each	Mean observed explainability ratios lie between $1.1341$ and $1.2728$ , while the corresponding theoretical factors are $2.0$ , $2.5$ , and $2.8333$ ; the largest observed ratio in these runs is $2.2655$ .
Scaling	Exact exponential-mechanism runs for $(k,\|\mathcal{G}\|)$ ranging from $(2,10)$ to $(6,18)$	Average wall-clock time rises from $0.0035$ s for $\binom{10}{2}=45$ subsets to $2.8905$ s for $\binom{18}{6}=18564$ subsets, illustrating the expected combinatorial bottleneck of exhaustive finite-domain selection.
Privacy–utility	Fixed $(k,\|\mathcal{G}\|)=(3,10)$ with $200$ seeds per privacy level and $\varepsilon$ ranging from $0.1$ to $10$	As $\varepsilon$ increases from $0.1$ to $10$ , the mean selection cost drops from $1025.4$ to $600.1$ and the exact additive tax drops from $11575.0$ to $115.7$ , matching the expected $1/\varepsilon$ trend.

Appendix

Table 8: Synthetic one-dimensional sanity checks from the companion artifact’s experimental suite. These numbers come directly from the committed experiment results file and are included only to illustrate the small-scale behavior of the finite-domain

k

-median pipeline.

Automated Algorithm Discovery

Automated algorithm discovery develops methods that generate and test executable algorithms for optimization, science, software, and machine learning.

See all 170 papers

Mar 3, 2026

Rethinking Code Similarity for Automated Algorithm Design with LLMs

The rise of Large Language Model-based Automated Algorithm Design (LLM-AAD) has transformed algorithm development by autonomously generating code implementations of expert-level algorithms. Unlike traditional expert-driven algorithm development, in the LLM-AAD paradigm, the main design principle behind an algorithm is often implicitly embedded in the generated code. Therefore, assessing algorithmic similarity directly from code, distinguishing genuine algorithmic innovation from mere syntactic variation, becomes essential. While various code similarity metrics exist, they fail to capture algorithmic similarity, as they focus on surface-level syntax or output equivalence rather than the underlying algorithmic logic. We propose BehaveSim, a novel method to measure algorithmic similarity through the lens of problem-solving behavior as a sequence of intermediate solutions produced during execution, dubbed as problem-solving trajectories (PSTrajs). By quantifying the alignment between PSTrajs using dynamic time warping (DTW), BehaveSim distinguishes algorithms with divergent logic despite syntactic or output-level similarities. We demonstrate its utility in two key applications: (i) Enhancing LLM-AAD: Integrating BehaveSim into existing LLM-AAD frameworks (e.g., FunSearch, EoH) promotes behavioral diversity, significantly improving performance on three AAD tasks. (ii) Algorithm analysis: BehaveSim clusters generated algorithms by behavior, enabling systematic analysis of problem-solving strategies--a crucial tool for the growing ecosystem of AI-generated algorithms. Data and code of this work are open-sourced at https://github.com/RayZhhh/behavesim.

Rui Zhang, Zhichao Lu

Department of Computer Science, City University of Hong Kong

Automated Algorithm Discovery

Ask PDF

Oct 1, 2026

Are you Synthesizing or Recalling? Evaluating LLMs on Algorithmic Code Retrieval

Large language models (LLMs) have demonstrated strong performance in code generation, where success depends on both recalling relevant algorithmic knowledge and reasoning about how to apply it. However, existing LLM pipelines are opaque, with no explicit separation between these two components. We argue that for well-known algorithms whose canonical implementations are widely accessible in pretraining corpora, code generation is better measured as parametric code retrieval: reproducing a named algorithm from internalised knowledge rather than synthesizing a novel one. We introduce AlgoREval, a benchmark of 599 problems spanning classical 77 algorithms across 14 domains, 7 programming languages, and 4 graph-input representations to evaluate this capability in isolation, and assess 15 models (7B--34B parameters) in a zero-shot setting. We find substantial variation in retrieval accuracy across languages and input representations, even for widely documented algorithms and show that prompt augmentation with retrieved code snippets or structured algorithmic hints improve accuracy on complex algorithms, while SFT achieves broader language gains and GRPO achieves larger per-language gains on specific languages. Together, our results establish parametric code retrieval as a distinct, measurable capability and caution against deploying AI-generated algorithmic code without systematic validation.\footnote{Code and dataset are available at https://github.com/Nickil21/AlgoREval

Nickil Maveli, Antonio Vergari, Shay B. Cohen

School of Informatics, University of Edinburgh 10 Crichton Street, Edinburgh, EH8 9AB

Code Generation Evaluation Code Generation Benchmarks

Ask PDF

Jun 29, 2026

AlgoSkill: Learning to Design Algorithms by Scheduling Human-Like Skills

Designing an algorithm from a natural-language problem statement requires identifying the problem structure, reading constraints, choosing a suitable paradigm, checking correctness, and refining complexity. Existing large language model (LLM) methods often rely on direct generation or generic self-refinement, leaving these steps implicit. We propose AlgoSkill, which models algorithm design as sequential decision-making over a typed library of algorithmic skills, including abstraction, constraint analysis, state design, data-structure selection, proof checking, counterexample construction, and complexity refinement. A learned scheduler proposes skills from the current design state, while a Monte Carlo Tree Search (MCTS) controller explores skill sequences using verification feedback from compilation, testing, stress testing, and complexity analysis. Experiments on competitive programming and combinatorial optimization benchmarks show that AlgoSkill improves over direct LLM generation, chain-of-thought prompting, self-refinement, and MCTS without typed skills. Ablations show that typed skills, verification-based repair, and search-based scheduling each contribute to performance. These results support treating automatic algorithm design as verification-guided skill scheduling rather than one-shot code generation.

Xinyuan Song, Zekun Cai, Liang Zhao

Emory University, Atlanta, GA, USA · The University of Tokyo, Tokyo, Japan · LocationMind, Tokyo, Japan

Automated Algorithm Discovery LLM-Based Program Synthesis Algorithmic Reasoning

Ask PDF

Abstract

Automated Algorithm Discovery

Explore similar work

Rethinking Code Similarity for Automated Algorithm Design with LLMs

Are you Synthesizing or Recalling? Evaluating LLMs on Algorithmic Code Retrieval

AlgoSkill: Learning to Design Algorithms by Scheduling Human-Like Skills