Evolution-Based Approaches for Iterative Kernel Refinement #

Section 2.1 placed structured search at the apex of the three axes, width times depth, pruned by fitness. Evolutionary methods are its most developed instance. Rather than the single improving trajectory of sequential refinement (a population of size one), they maintain a population of candidate kernels and improve the population over generations, selecting good candidates, mutating and recombining them, evaluating the offspring, and letting the fittest survive. Most kernel-evolution systems use an LLM as the engine that proposes each mutation, often one of the post-trained models of Section 3, so evolution is a search wrapped around generation rather than an alternative to it. That search is also the setting for the two ideas this subsection builds toward: searching not only over kernel code but over how the problem is decomposed into subproblems, and then using that decomposition to make correctness checking more reliable.

This subsection first abstracts the common evolutionary loop and its two canonical instances, then surveys the kernel-specific systems built on it, and finally turns to a recurring theme in the more recent systems: widening the search from kernel code to the problem’s decomposition. We use MKEvolve [1] as the worked example of that idea.

The evolutionary loop #

Every LLM-driven evolutionary system, whatever the domain, instantiates the same five-part loop over a population \( P_t \) of candidate programs:

The evolutionary loop. A population \( P_t \) of candidate kernels feeds five numbered stages that cycle back into it: select parents, vary them (an LLM proposes offspring, by mutation or crossover), evaluate (compile · check · time), score a fitness (highlighted, the one concrete payoff: correctness-gated speedup \( F(y) = \mathrm{speedup}(y) \) if correct, else \( 0 \) ), and let the fittest survive into the next generation. A refinement trajectory is just the special case \( |P_t| = 1 \) , and the design freedom (◆) lives in three of the stages: selection, the operator, and population structure.

1. Selection. Choose which population members seed the next round (the fittest, a diverse sample, or both).
2. Variation. An LLM turns the selected parents into new candidates, by editing one (mutation) or combining several (crossover). This is where the language model does its work.
3. Evaluation. Run each candidate: compile, check correctness against a reference, and time it.
4. Fitness. Collapse the evaluation into a scalar. For kernels this is almost universally correctness-gated speedup: \( F(y) = \mathrm{speedup}(y) \) if \( y \) is correct, and \( F(y) = 0 \) otherwise, so an incorrect kernel is worthless no matter how fast. This is the same compile-correct-fast signal and anti-cheating discipline that Section 2.3 develops as a verifier, reused here as a selection signal rather than (as in Section 3.2) a policy gradient.
5. Survival. Register the offspring back into the population and decide who stays, closing the loop.

The design freedom lives in steps 1, 2, and 5: how parents are chosen, what the variation operator is, and how the population is structured. The two canonical systems below share this loop but sit at opposite ends of one axis: how much work counts as a single mutation, and correspondingly where the search intelligence lives. AlphaEvolve puts it in the framework wrapped around a simple LLM call; Avo puts it in the operator, which is itself an agent.

AlphaEvolve [2] is the reference LLM-evolution system, and the ancestor most kernel systems cite. Four choices instantiate the loop above:

• Population (a program database). It keeps every program ever evaluated alongside its scores. To build each prompt it draws one parent (the program to improve) plus a few inspiration programs (other high-scoring or notably different attempts, shown to the model as extra ideas to draw on).
• Retention (MAP-Elites + island model). Two rules govern what the database keeps, both to stop the search from collapsing onto a single lineage too early (balancing exploitation, refining the current best, against exploration, trying genuinely different directions). MAP-Elites buckets programs by descriptive features (such as code length or which strategy they use) and keeps the best one per bucket, yielding an archive of diverse champions rather than near-copies of the leader. The island model splits that archive into sub-populations that evolve independently, with occasional migration of a strong program between them, so different islands explore different regions.
• Variation (targeted diffs). An ensemble of Gemini models (a fast, high-volume model plus an occasional higher-quality one) proposes edits emitted as SEARCH/REPLACE diff blocks applied to regions marked by EVOLVE-BLOCK comments, so the model mutates a small, targeted span rather than rewriting the whole program.
• Evaluation (metric cascade). A user-supplied evaluate() function returns a dictionary of scalar metrics, optionally through a cascade of increasingly hard test cases that cheaply kills weak candidates before expensive evaluation.

This machinery produced concrete, verified discoveries: an algorithm to multiply two \( 4\times 4 \) complex matrices in 48 scalar multiplications (the first improvement over Strassen’s rank-49 scheme in this setting in 56 years), an average 23% speedup on the Pallas kernels used to train Gemini, and a 32% speedup of a FlashAttention kernel optimized at the XLA IR level [2]. The lesson for kernels is that evolutionary search with an executable evaluator in the loop outperforms single-shot generation on real accelerator code.

In these terms, AlphaEvolve’s variation operator is \( \mathrm{Vary}(P_t) = \mathrm{Generate}(\mathrm{Sample}(P_t)) \) : the framework samples the parent and inspirations, and the LLM is called once to return a single diff. All the search logic (population, MAP-Elites, islands) sits in the framework around that one call.

Avo [3] sits at the other end. It makes the operator itself an autonomous agent, \( \mathrm{Vary}(P_t) = \mathrm{Agent}(P_t, K, f) \) , so producing one offspring is now a whole agentic loop rather than a single call: within that step the agent inspects prior implementations, consults a domain knowledge base \( K \) (CUDA guides, PTX ISA docs, hardware specs), reads profiling feedback \( f \) , and runs its own edit-evaluate-diagnose cycle (many LLM calls and tool uses) until it commits a satisfactory candidate. Because the operator now carries the intelligence, Avo can strip the population machinery back to a single lineage on purpose, which isolates and demonstrates that making the operator agentic is what drives the gains. Run this way on attention kernels for NVIDIA B200 GPUs, Avo discovered kernels beating FlashAttention-4 by 5.0% to 10.5% on causal attention and transferred a multi-head attention solution to grouped-query attention in about 30 minutes of additional autonomous search, over a 7-day run that committed 40 kernel versions out of more than 500 explored directions [3]. So the two systems answer the same question, where should the cleverness go, in opposite ways: AlphaEvolve keeps a simple operator and a rich population manager, while Avo keeps a minimal population and a clever, agentic operator.

Search-based systems for kernels #

Between these poles sit the kernel-specific systems, which mostly use beam search, tree search, or a full evolutionary loop, with an LLM as the variation operator and correctness-gated speedup as fitness. These three are not different kinds of thing: they are the same population loop with two knobs set differently, what the variation operator does (mutate one parent, or also recombine several) and how selection prunes (strict top- \( B \) , adaptive with an exploration bonus, or diversity-preserving). This is exactly why KernelEvolve [7] below can express all three as one selection-policy choice \( \pi_{\mathrm{sel}} \) over a shared substrate.

The same population loop with two knobs set differently — the operator (how many parents feed one mutation) and selection (how it prunes). Beam search is a unary operator with strict top- \( B \) survival (keep the best \( B \) , drop the rest). Tree search (MCTS/UCT) keeps the unary operator but spends budget adaptively on the promising subtree (highlighted) while under-tried branches stay alive. Evolutionary adds what neither has: an n-ary operator that recombines several parents (crossover, highlighted) and diversity-preserving selection. Reading left to right, each strategy relaxes a constraint of the one before it.

Reading left to right, each strategy relaxes a constraint of the one before it: beam search is strict top- \( B \) elitism with a unary (mutation-only) operator; tree search keeps the unary operator but replaces the fixed frontier with an adaptive selection policy that spends budget on promising subtrees and adds an explicit exploration term (so it avoids beam’s tendency to fill up with near-copies of one idea); an evolutionary loop adds the two features neither has, an n-ary operator that can recombine several parents (crossover), and diversity-preserving, stochastic selection (MAP-Elites niches or islands, as in AlphaEvolve) instead of pure top- \( B \) .

The most common form of tree search here is Monte Carlo Tree Search (MCTS), the algorithm behind game-playing systems such as AlphaGo. Rather than expanding a fixed frontier, it repeats a four-step cycle: select a path down the existing tree to an under-explored node, expand it with a new candidate (here, a mutated kernel), evaluate that candidate (compile, check, time it for its fitness), and backpropagate the score up to every ancestor, updating their value estimates and visit counts. Which child to descend into at each step is decided by UCT (Upper Confidence bounds applied to Trees), a rule that scores every child and picks the largest:

where \( \bar{v} \) is the child’s mean backpropagated score (favoring it is exploitation: go where kernels already look fast), and the second term is an exploration bonus that grows when a child has been visited few times ( \( n_{\text{child}} \) small relative to the parent’s visit count \( N_{\text{parent}} \) ), so under-tried candidates keep getting a chance; the constant \( c \) sets the balance. This is the “value + exploration bonus” in the diagram, and it is the concrete mechanism by which a promising-but-under-tried kernel can outrank a well-tried leader, preventing the search from tunnel-visioning onto one branch.

This axis is orthogonal to the AlphaEvolve-vs-Avo one above: that concerned what happens inside one operator call (a single LLM call versus a whole agent loop), whereas this concerns how many parents the operator takes and how the population is pruned around it. Any choice on one axis composes with any choice on the other. The systems below differ in target hardware, in the structure imposed on the search, and in what memory persists across rounds.

• Autocomp [4] optimizes low-level tensor-accelerator code with a beam search (width \( B = 6 \) ) driven by a two-phase prompt: a planning phase where the LLM selects exactly one transformation from a concise, editable optimization menu (loop tiling, reordering, double buffering, and so on), then a code phase that applies it. Diversity comes from menu dropout (each menu item is randomly withheld with 70% probability) and from LLM ensembling. It reports 5.6x over the Gemmini vendor library, 1.9x over expert hand-tuned code on AWS Trainium, and 3.8x over an ML cost model on an NVIDIA L40S, and it explicitly rejects crossover (candidate merging) as ill-suited to loop-nest accelerator code, a useful counterpoint to genetic-style recombination [4]. Its plan-then-code split also mirrors the planning/coding decomposition that TritonRL rewards asymmetrically (Section 3.4).

• AccelOpt [5] adds a self-improving optimization memory to a beam search over Trainium NKI kernels. A planner, an executor, and a summarizer cooperate: the summarizer distills each round’s slow-to-fast rewrites (including negative examples) into a bounded queue of reusable strategies that conditions the planner in later rounds. This lifted average throughput from 49% to 61% of hardware peak on Trainium 1 and 45% to 59% on Trainium 2, and, notably, open-source models with search-plus-memory matched Claude Sonnet 4 quality at roughly 26x lower cost [5], a concrete argument that structured search can substitute for raw model strength.

• Astra [6] decomposes optimization by role rather than by code region: separate testing, profiling, planning, and coding agents share a trajectory log over 5 refinement rounds. On production CUDA kernels extracted from the SGLang serving framework it reached 1.32x average speedup, versus 1.08x for an otherwise identical single monolithic agent, showing that role decomposition alone buys accuracy (the monolith even regressed to a slowdown on one kernel when unrepresentative test inputs biased its profiling) [6].

• KernelEvolve [7], deployed at Meta, formalizes the whole family as graph-based tree search defined by a tuple \( (F, \pi_{\mathrm{sel}}, O, \tau) \) : a fitness \( F(v) = t_{\text{pytorch}}/t_{\text{triton}} \) (with \( F = 0 \) for kernels that fail compilation or correctness), a selection policy \( \pi_{\mathrm{sel}} \) instantiable as greedy, MCTS with UCT, or evolutionary crossover/mutation, a single universal operator \( O \) steered by retrieval-augmented prompt synthesis (so one context-adaptive operator replaces fixed draft/debug/improve operators, enabling knowledge injection for proprietary accelerators absent from the training corpus), and a termination rule \( \tau \) .

  This \( (F, \pi_{\mathrm{sel}}, O, \tau) \) view is a useful lens on the whole family: every system fixes a fitness and a correctness gate, then chooses a selection policy and a variation operator. The next idea changes the object the search operates on.

Searching over the decomposition, not just the code #

The systems above, and most LLM kernel generators, treat the kernel as a single monolithic artifact optimized end-to-end. This has two costs. First, it is inefficient: repeatedly re-optimizing an entire kernel wastes improvement effort and tokens, because most useful changes are local and touch only a small part of the computation. Second, monolithic kernels are opaque: a single end-to-end correctness or speedup number cannot say which part is wrong or slow, which makes the result hard for both engineers and LLMs to debug, reuse, or adapt.

The response is to decompose the problem: split the model into subproblems, solve each as its own subkernel, and compose the results into an end-to-end implementation. KernelFalcon [14] established this recipe for LLM kernel generation, fusing a PyTorch model into a typed JSON compute-graph of subgraphs, generating each subkernel with a pool of parallel workers under execution-based verification, and stitching the verified pieces back together with the LLM. MKEvolve [1] builds directly on that decompose-generate-compose lineage but makes two changes: it treats the decomposition itself as a first-class object that is evolved rather than fixed once, and it makes composition and verification programmatic rather than model-driven. A kernel is represented not as one file but as a codebase: a set of files, each implementing a subproblem derived from the original PyTorch module, plus a single top-level module that orchestrates the subkernels into a functionally identical implementation. The search then runs at two levels at once: over the subkernel implementations, and over the decomposition topology (how many subproblems there are and where the boundaries fall). Three choices instantiate the loop above:

MKEvolve on the KernelBench L3 Conv-ViT task (Figure 1 of [1]): the decomposition topology and the end-to-end speedup co-evolve. A failing subproblem (the Transformer Encoder, \( 4 \) ) splits into Self-Attention ( \( 4a \) ) and Feed-forward ( \( 4b \) ), which are later fused into a Transformer Block ( \( 4c \) ); the dashed E2E curve tracks that structural change, rising from failure toward `torch.compile` parity.

• Two-level search. An inner beam search optimizes each subkernel (reward = speedup over torch.compile, incorrect kernels get 0), while every few iterations an outer step reshapes the topology, splitting a failing subproblem in two or fusing subproblems into a larger one, and the LLM budget is steered toward the slow or incorrect pieces rather than spread evenly.
• Programmatic composition. Verified subkernels are plugged into the end-to-end kernel by a deterministic orchestrator, not stitched by the model, so the composed program is correct-by-construction from its parts. This is what makes subkernels swappable (adapt to a related model by replacing one subkernel) and failures traceable (a wrong output localizes to a specific subkernel). Subkernels are held to the anti-cheating and strict-correctness standard of Section 2.3, reusing the TritonRL cheating detector [8] and the KernelBench evaluation pipeline [9].
• Reliable verification. Decomposition also makes correctness checking easier. Correctness is decided by comparing the output against a reference within a tolerance, and a single end-to-end tolerance must be both loose enough not to reject correct kernels and tight enough to catch bugs. In low precision (BF16, FP16) no such value may exist, because a correct low-precision kernel’s own rounding error can be larger than the error a real bug introduces: if a correct kernel deviates by up to \( 10^{-2} \) while a subtle bug perturbs the output by only \( 10^{-3} \) , any tolerance loose enough to admit the correct kernel also admits the buggy one. Checking each sub-operator’s intermediate tensor against its own calibrated tolerance sidesteps this: the bug is caught at the stage where it occurs, before a later operator can dampen its error into the end-to-end noise floor, which is why decomposed checking catches subtle BF16 bugs (unsafe softmax, off-by-one masks) that the end-to-end check misses [1]. That per-operator bounds compose into an end-to-end guarantee follows from classical smoothness and rounding-error analysis [10, 11, 12].

The lesson mirrors AlphaEvolve and Avo: evolutionary search with an executable evaluator beats single-shot generation, and here searching over the decomposition rather than a monolithic artifact yields kernels that are more token-efficient, interpretable, and transferable. The two changes over KernelFalcon are exactly the axes above: KernelFalcon stitches subkernels with LLM-driven composition validated by LLM-generated tests and halts at the first correct subkernel, whereas MKEvolve composes programmatically, verifies with a strict non-LLM pipeline (the TritonRL cheating detector [8] and KernelBench harness [9]), and keeps evolving the topology instead of stopping at first-correct [1]. On KernelBench L2/L3 (Claude Opus 4.5 and GPT-OSS 120B), MKEvolve improves both correctness and speedup over parallel-sampling and beam-search baselines while using 15% to 35% fewer LLM tokens, and it reaches 10.7x to 44.3x speedups over torch.compile on FlashInfer-Bench inference kernels [1, 13].

Takeaways #

• Evolution wraps a search around LLM kernel generation: a population, a variation operator (a diff, an agent loop, or a plan-then-code step), and a correctness-gated speedup fitness that reuses the verifier and anti-cheating machinery of Section 2.3. Beam and tree search, with persistent memory (AccelOpt) or a universal RAG-steered operator (KernelEvolve), are the common instances.
• The variation operator can be as small as a targeted diff (AlphaEvolve) or as large as an autonomous refinement agent (Avo); the trade-off is diversity and control versus per-mutation cost.
• A recurring recent theme is to widen the search from kernel code to the decomposition itself (subproblem topology plus subkernel implementations), which MKEvolve illustrates: a modular codebase is more token-efficient, interpretable, transferable, and reliably verifiable (via per-operator calibrated tolerances) than a monolithic kernel, provided composition and verification stay programmatic rather than model-driven.

References #

1. J. Yoo, R. Saha, S. Zhu, T. Yu, W. Tang, and Y. Park. MKEvolve: A Modular Multi-Agent Framework for Kernel Code Generation. arXiv:2607.20501, 2026 (ICML 2026 Workshop on Compositional Learning). arxiv.org/abs/2607.20501
2. A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, et al. AlphaEvolve: A Coding Agent for Scientific and Algorithmic Discovery. arXiv:2506.13131, 2025. arxiv.org/abs/2506.13131
3. T. Chen, Z. Ye, B. Xu, T. Liu, A. Hassani, T. Chen, R. Krashinsky, M.-Y. Liu, V. Grover, L. Ceze, and H. Shi, et al. Avo: Agentic Variation Operators for Autonomous Evolutionary Search. arXiv:2603.24517, 2026. arxiv.org/abs/2603.24517
4. C. Hong, S. Bhatia, A. Cheung, and Y. S. Shao. Autocomp: A Powerful and Portable Code Optimizer for Tensor Accelerators. arXiv:2505.18574, 2025. arxiv.org/abs/2505.18574
5. G. Zhang, S. Zhu, A. Wei, Z. Song, A. Nie, Z. Jia, N. Vijaykumar, Y. Wang, and K. Olukotun. AccelOpt: A Self-Improving LLM Agentic System for AI Accelerator Kernel Optimization. arXiv:2511.15915, 2025. arxiv.org/abs/2511.15915
6. A. Wei, T. Sun, Y. Seenichamy, H. Song, A. Ouyang, A. Mirhoseini, K. Wang, and A. Aiken. Astra: A Multi-Agent System for GPU Kernel Performance Optimization. arXiv:2509.07506, 2025. arxiv.org/abs/2509.07506
7. G. Liao, H. Qin, Y. Wang, A. Golden, M. Kuchnik, et al. KernelEvolve: Scaling Agentic Kernel Coding for Heterogeneous AI Accelerators at Meta. arXiv:2512.23236, 2026. arxiv.org/abs/2512.23236
8. J. Woo, S. Zhu, A. Nie, Z. Jia, Y. Wang, and Y. Park. TritonRL: Training LLMs to Think and Code Triton Without Cheating. arXiv:2510.17891, 2025. arxiv.org/abs/2510.17891
9. A. Ouyang, S. Guo, S. Arora, A. L. Zhang, W. Hu, C. Ré, and A. Mirhoseini. KernelBench: Can LLMs Write Efficient GPU Kernels? ICML 2025. openreview.net/forum?id=yeoN1iQT1x
10. H. Kim, G. Papamakarios, and A. Mnih. The Lipschitz Constant of Self-Attention. arXiv:2006.04710, 2021. arxiv.org/abs/2006.04710
11. V. Castin, P. Ablin, and G. Peyré. How Smooth Is Attention? arXiv:2312.14820, 2024. arxiv.org/abs/2312.14820
12. N. J. Higham and T. Mary. Sharper Probabilistic Backward Error Analysis for Basic Linear Algebra Kernels with Random Data. SIAM Journal on Scientific Computing, 42(5):A3427-A3446, 2020. doi.org/10.1137/20M1314355
13. S. Xing, Y. Zhai, A. Jiang, Y. Dong, Y. Wu, Z. Ye, C. Ruan, Y. Huang, Y. Zhang, L. Yin, et al. FlashInfer-Bench: Building the Virtuous Cycle for AI-driven LLM Systems. arXiv:2601.00227, 2026. arxiv.org/abs/2601.00227
14. L. Wang, S. Chen, B. Maher, J. Isaacson, L. Fang, W. Chi, J. Liu, A. Hammond, Z. Fisches, M. Saroufim, W. Hunt, R. Li, J. Kahn, E. El-Haraty, and A. Mathews. KernelFalcon: Autonomous GPU Kernel Generation via Deep Agents. PyTorch Blog, 2025. pytorch.org/blog/kernelfalcon-autonomous-gpu-kernel-generation-via-deep-agents