Algorithmic Algorithm Improvement with LLMs using Particle-Based Monte Carlo Methods

Kurzfassung

Large language models have recently become promising components in systems for automated code generation, optimisation, and scientific discovery. In the context of algorithmic algorithm improvement, this suggests a shift in perspective in which algorithms are represented as executable programs and improved directly through software-based search, rather than only being manually designed and then implemented. This thesis studies such evaluator-grounded algorithm improvement following the line of work established by FunSearch and AlphaEvolve, while investigating a particle-based search mechanism inspired by Monte Carlo methods.

Instead of maintaining a program database or archive, candidate programs are organised as particles in a tree of program states. At each step, an LLM proposes code edits, the resulting candidates are evaluated using task-defined metrics such as correctness and runtime speedup, and future search effort is allocated by resampling particles according to their scores. We implement this approach as a lightweight prototype and evaluate it on selected AlgoTune tasks.

The experiments compare different open-weight models and analyse several aspects of the search procedure, including particle temperature, search-tree shape, optional LLM-based debugging, lookahead, and stochastic variability. The results show that particle-based resampling can produce measured speedup improvements on several tasks and can therefore serve as a plausible mechanism for LLM-guided algorithmic code improvement. At the same time, performance is strongly task-dependent, sensitive to evaluation noise and parameter choices, and not yet systematically compared against established evolutionary code-search frameworks. The thesis therefore presents particle-based search as a promising variant of evaluator-grounded algorithm improvement, while identifying robustness, scalability, qualitative code analysis, and comparative evaluation as important directions for future work.