Search papers, labs, and topics across Lattice.
This paper introduces AlgoSkill, a novel framework that approaches algorithm design as a sequential decision-making process utilizing a library of human-like algorithmic skills. By employing a learned scheduler and a Monte Carlo Tree Search (MCTS) controller, AlgoSkill effectively navigates the complexities of algorithm design through structured skill selection and verification feedback. Experimental results demonstrate that AlgoSkill outperforms traditional LLM methods and other baseline strategies in competitive programming and combinatorial optimization tasks, highlighting the importance of skill-based approaches in automated algorithm design.
AlgoSkill redefines algorithm design by treating it as a skill scheduling problem, outperforming traditional LLM methods in complex programming tasks.
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.
