Jun 2026· arXiv.org· Vol abs/2606.29999· 1 citation· 36 references
Computer Science
TL;DR
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, which support treating automatic algorithm design as verification-guided skill scheduling rather than one-shot code generation.
Abstract
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.
Algorithm selection for constraint satisfaction problems requires extracting features that capture problem structure. Manually designing feature extractors demands deep domain expertise and quickly becomes a bottleneck when new problem classes appear. We present an automated approach that uses Large Language Models (LLMs) in an agentic check--fix--verify loop to synthesize executable Python scripts that act as interpretable, problem-specific feature extractors. Given a high-level MiniZinc model and an instance, the LLM agent generates code that constructs a typed graph representation and computes structural properties such as graph density, variable clustering, and constraint tightness. We evaluate our approach on three combinatorial problems (vehicle routing, car sequencing, fixed-length error-correcting codes) with a portfolio of five state-of-the-art solvers. The synthesized extractors yield algorithm selectors that consistently outperform both expert-curated mzn2feat features (up to $8.3$ percentage points (pp) test-set accuracy on FLECC) and the best transformer-based trans2feat variants. In the meanwhile, the synthesized feature extractors remain inspectable.
Hai Xia, C. Ansótegui, Stefan Szeider· 0 citations
Combinatorial problems appear in numerous industrial applications. A common approach is to formulate these problems as declarative constraint models that can subsequently be compiled to and solved by a range of back-end solvers. Recent work shows that Large Language Models (LLMs) can produce correct models from natural language, but even a correct model can be expensive to solve because performance remains sensitive to modelling choices. In this work, we investigate whether LLMs can automate performance-oriented model reformulation. Inspired by Automatic Heuristic Design (AHD), we use an evolutionary framework in which an LLM proposes candidate reformulations that are verified and benchmarked against the user-defined baseline model. We compare AHD-adapted search strategies that control which prior attempts, instructions, and measured feedback enter each prompt. Existing retention strategies prioritize recency or performance, but do not explicitly diversify the context. To cover this gap, we introduce Profile-Diverse Retention (PDR), which applies Maximal Marginal Relevance (MMR) to instance-level runtime vectors to retain behaviourally diverse attempts. We systematically evaluate the strategies on eight CSPLib problems using validation-based final model selection. The results show that: (i) iterative reformulation can produce substantial held-out speedups; (ii) strategies that keep the retained context diverse outperform those that retain only recent or the fastest attempts; and (iii) validation-based selection improves the held-out speedup of every strategy.
Kostis Michailidis, Dimos Tsouros, Nguyen Dang et al.· 0 citations
UMCTS is an Uncertainty-aware Monte Carlo Tree Search framework that combines the language understanding capability of large language models with the reliability of well-established solvers and achieves state-of-the-art solution accuracy and improves efficiency by reducing token usage.
Linlin Yu, Xujiang Zhao, Dong Li et al.· Annual Meeting of the Associ...· 0 citations
As LLM technology advances, the space of model families, compute hardware, quantization schemes, parallelization strategies, and specialized optimization kernels continues to expand, sharply increasing the code complexity and maintenance cost of general-purpose inference frameworks. Conventional software engineering uses multiple layers of abstraction to support diverse application scenarios, but these abstractions also increase system complexity and may introduce additional performance overhead. This paper presents metainfer, an'LLM-as-Compiler'approach in which users specify only the runtime constraints of an inference program. An LLM-driven multi-agent collaboration system, coupled with a contract knowledge base, then automatically generates a compact customized inference framework that satisfies these constraints. We evaluate metainfer from three perspectives: the effect of source-code reference, the runtime behavior and performance profile of engines generated under the zero-reference constraint on CKB-covered targets, and knowledge-base evolution for new model and platform scenarios. The results show that metainfer organizes generation constraints, validation feedback, and knowledge consolidation into a continuous closed loop, enabling runnable customized inference solutions to be generated from explicit knowledge. The code is publicly available at https://github.com/MetaInfer/MetaInfer.
Zhenwen Miao, Honglin Wang, Mingheng Mi et al.· 0 citations
Differential compiler testing requires automatically generated programs that are not only diverse and bug-revealing, but also semantically well-defined and reproducible. Rule-based generators provide strong validity guarantees but offer limited control over semantic variation, while large language models (LLMs) can synthesize expressive programs without principled mechanisms for balancing competing testing objectives. This paper proposes LMOEC, a constrained multi-objective evolutionary framework that integrates code language models as semantic genetic operators within an NSGA-II search process. Instead of using the LLM as a one-shot generator, we employ it for population initialization, crossover, and mutation at the program level, enabling semantics-aware recombination while preserving strict admissibility constraints. Compiler test generation is formulated as a multi-objective optimization problem that simultaneously promotes structural diversity, cross-configuration output inconsistency, semantic complexity, and robustness to mutation. A constraint-driven acceptance pipeline enforces syntactic validity, deterministic execution, bounded runtime, and avoidance of undefined behavior before evolutionary selection. By maintaining a Pareto front of non-dominated programs, LMOEC preserves multiple high-value test archetypes reflecting different trade-offs between bug exposure and reproducibility. The framework demonstrates how expressive code models can be systematically embedded into evolutionary multi-objective optimization for reliability-critical software testing.
Lang Hong Nguyet Anh, Ho Viet Duc Luong, Vu Van An· Annual Conference on Genetic...· 0 citations
This work proposes a novel Reinforcement Learning from AI Feedback (RLAIF) framework, finding that specifications can be iteratively refined by leveraging feedback from the LLM's own outputs, creating a self-improving loop.
Jaykithan Y Patel· SIGSOFT FSE Companion· 0 citations