AdaExplore: Failure-Driven Adaptation and Diversity-Preserving Search for Efficient Kernel Generation

🕒 Published (v1): 2026-04-17 18:25 UTC · Source: Arxiv · link

Why this paper was selected

Failure-driven adaptation with diversity preservation for LLM kernel generation agents

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AdaExplore is a two-stage LLM agent framework for GPU kernel runtime optimization in Triton, addressing both the high rate of invalid code (feasibility bottleneck) and the non-linear performance landscape (locality bottleneck). It accumulates cross-task failure patterns into a reusable skill memory and organizes candidate kernels as a UCT-guided search tree, achieving 3.12× and 1.72× speedups on KernelBench Level-2 and Level-3 within 100 steps—without fine-tuning.

Problem

LLMs generating low-level GPU kernels (Triton/CUDA) fail for two compounding reasons: (1) the feasibility boundary is sharp—small syntax or memory-access errors cause compilation/runtime failures, and Triton is severely underrepresented in pretraining data; (2) the runtime-performance landscape is non-linear and combinatorial, so local iterative refinement gets stuck in local optima. Existing methods treat each problem instance independently, wasting execution feedback and failing to transfer experience across tasks.

Method

AdaExplore has two sequential components:

Adapt (cross-task skill memory). The agent synthesizes training tasks by recombining operators from operator documentation, seeded from a small held-out set. For each task it generates a kernel, executes it, and summarizes failures into concise constraint rules (e.g., "you cannot generate a Triton pointer type inside a vectorized load"). Rules are aggregated by frequency across tasks; only rules with occurrence \(O \geq 3\) are retained (78 of 174 deduplicated rules from 200 synthetic tasks). This evolving memory is injected into the system prompt for all subsequent generations, including on held-out test tasks and across different base models.

Explore (diversity-preserving tree search). Candidate kernels are nodes in a search tree \(\mathcal{T}\). Each expansion applies one of two actions: small step (localized patch preserving structure) or large step (structural regeneration). Context for a new generation combines a working memory of the recent branch history \(C_{\text{recent}}\) with a pool of representative kernels \(K_{\text{pool}}\), sampled from segment-deduplicated past candidates to avoid near-duplicate bias. Node selection uses a UCT-style rule: $\(\text{UCT}(s, a) = Q(s,a) + c_{\text{explore}}\sqrt{\frac{\ln N(s)}{N(s,a)}}\)$ with an explicit expand option that incentivizes adding new children when the current children are already well-visited. Large steps clear working memory to break out of local refinement chains.

Key Contributions

• Failure-driven cross-task skill memory: extracts recurring validity constraints from execution failures across synthesized tasks, improving single-pass correctness without any model training.
• Diversity-preserving tree search: alternates small/large steps, uses segment-deduplication for representative kernel selection, and UCT-based node selection with explicit expansion term.
• Demonstrates that combining both mechanisms outperforms either alone, and that the cross-task skill memory transfers across base models (GPT-5-mini, GPT-5, Claude-4.6-Opus, Qwen3-Coder-Next) and GPU architectures (L40S, A100, GB200).
• Inference-time scaling: performance improves monotonically with budget (50→100→200 steps).

Results

All multi-pass results use GPT-5-mini as the base model unless noted; profiling on NVIDIA A6000 at 1500 MHz.

• KernelBench Level-2 (50 steps): AdaExplore 2.65× speedup, 71% Fast@1.2, 34% Fast@2 vs. best non-AdaExplore baseline IR w. SM at 2.59×/67%/33%.
• KernelBench Level-2 (100/200 steps): 3.12× / 3.41× speedup; 78%/81% Fast@1.2; 44%/49% Fast@2.
• KernelBench Level-3 (50 steps): AdaExplore 1.55× speedup, 28% Fast@1.2, 16% Fast@2 vs. OpenEvolve w. SM at 1.47×/28%/10%.
• KernelBench Level-3 (100 steps): 1.72× speedup, 32% Fast@1.2, 20% Fast@2.
• Cross-task skill memory ablation (Table 2): GPT-5-mini Pass@1 improves from 22% to 54%; Pass@25 from 76% to 100% on L2.
• FlashInfer-Bench (case study): RMSNorm 7.22× over PyTorch / 1.75× over expert FlashInfer CUDA kernel; GQA paged decode 18.17× over PyTorch.
• Single-pass frontiers without adaptation: GPT-5-mini 0.34×, GPT-5 0.78×, Claude-4.6-Opus 0.76× speedup on L2.

Limitations

• Task synthesis seeds and operator documentation are manually curated; the quality of synthetic tasks depends on the coverage of the documentation.
• Frequency threshold \(O \geq 3\) for memory retention is a fixed heuristic; it may underfit sparse-but-critical failure modes.
• The cross-task skill memory is constructed offline before test-time inference; it does not update dynamically during the search on a new task.
• Compute-intensive, hardware-specialized kernels (e.g., Blackwell-specific instructions for GQA) remain hard to surpass even with extended budgets.
• Level-3 gains are substantially smaller than Level-2, suggesting model-level workloads with higher-level design dependencies are not yet well-handled.
• Results depend heavily on a strong frontier model (GPT-5-mini); performance on weaker models is not fully characterized.

Relevance to Harnesses / Meta-Harnesses

AdaExplore is a direct instance of a meta-harness pattern: it wraps a base LLM agent with an outer adaptation loop that synthesizes tasks, runs the agent, collects execution feedback, distills failure patterns, and updates a persistent skill memory—all without modifying model weights. This cross-task memory construction is structurally identical to the "meta-level accumulator" seen in harness frameworks that orchestrate multiple agent runs to build shared knowledge. The two-stage pipeline (offline Adapt → online Explore) mirrors the meta-harness separation between a knowledge-building phase and a deployment phase, and the monotonic inference-time scaling behavior demonstrates that harness-level orchestration (not just model capability) is a primary lever for performance. For researchers tracking meta-harnesses, this paper provides a concrete, reproducible instantiation of failure-driven memory construction as a first-class harness component.