acceptodds
Under review as a conference paper at ICLR 2027

Structure Before Tuning: Two-Stage Search for LLM-Generated GPU Kernels

Abstract

GPU kernels form the computational foundation of modern artificial intelligence systems, and their execution efficiency directly affects training and inference latency, throughput, and deployment cost. Large language models can generate kernel code and iteratively optimize it using compilation and runtime feedback, offering a new way to reduce the cost of manual tuning. However, LLM-generated kernels often fall short of the desired performance: reaching a high-performance implementation typically consumes substantial model tokens and evaluation budget, and the resulting optimization is unstable. Existing methods commonly search over complete kernel programs through a unified generate–compile–benchmark–revise loop that alternates between structural decisions and local implementation tuning. Structural decisions determine how computation is decomposed and coordinated, whereas local optimization refines implementation details within a given structure. When the search moves to a new structure, local refinements made for the previous structure often cannot be reused, reducing the value of the budget already spent and potentially causing candidates to be compared or discarded before they are sufficiently optimized. We introduce , a two-stage framework that decouples structural search from local optimization. In the first stage, an agent selects and composes actions from a predefined structural action library to construct abstract structural blueprints, which are then instantiated as executable domain-specific-language (DSL) implementations to explore alternative computation organizations. After structural exploration, promising structures are selected based on the search outcomes, and each retained structure becomes an independent starting point for the second stage. For each structure, an agent independently performs local implementation search under its corresponding structural contract. By exploring structures first and then optimizing each retained structure within its own trajectory, avoids repeatedly switching between structural search and local tuning and enables different structures to be compared after a controlled degree of implementation refinement. On FlashInfer-Bench and Sol-ExecBench kernel workloads running on NVIDIA A800 and H100 GPUs, we compare with mixed search, structure-only search, and local-only optimization. Insert final experimental results.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
GPU Kernel Optimization, Large Language Models, Agentic Code Generation, Triton, Structural Search, Local Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_iVVZOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes StruTune, a two-stage framework for LLM-based GPU kernel generation and optimization. The key idea is to decouple structural search from local implementation optimization. In the first stage, the system generates and evaluates multiple structural plans without executing code. In the second stage, it implements the selected plans and independently optimizes each structure under a fixed structural contract. Experiments on selected operators demonstrate promising performance improvements over several existing kernel optimization agents on A800 and H100 GPUs.

Critical strengths
  1. The paper identifies an interesting practical problem: existing LLM-based kernel optimization agents may overcommit to an initial implementation structure and spend excessive effort on local refinements.

  2. The separation between structural exploration and local optimization is intuitive and potentially useful. The reported results across benchmarks and GPU architectures are promising.

Critical weaknesses
  1. Limited discussion of novelty relative to existing planning-based kernel optimization agents.

The central idea of separating planning from implementation and iteratively refining optimization strategies has been explored in prior work. In particular, AccelOPT (MLSys 2026, also missing citation) uses a Planner–Executor–Summarizer architecture, where the Planner proposes multiple optimization plans, the Executor realizes them, and profiling results are summarized into reusable optimization experiences that guide subsequent planning iterations. AccelOPT additionally uses beam search to maintain multiple candidate implementations and demonstrates the discovery of both local and nontrivial global optimizations. Another paper is https://arxiv.org/pdf/2606.26758 EGG, you may also want to clarify the distinction clearly. In general, "planning" then "implementation" in the area of coding has been widely explored before. I am a bit hesitant about the novelty here.

While StruTune explicitly distinguishes structural decisions from local implementation decisions and optimizes selected structures independently, it is unclear to me whether this represents a fundamental algorithmic advantage over existing iterative planning and search frameworks, rather than a different organization and presentation of the search process.

I would appreciate a more detailed discussion of the conceptual and algorithmic differences from AccelOPT and related approaches such as K-Search and QiMeng-Kernel. In particular, what structural transformations can StruTune systematically explore that existing planning-based agents cannot? Is the main contribution the explicit structural representation, the execution-free structural evaluation, or the independent allocation of optimization budgets? Can the authors provide empirical evidence isolating the advantage of these design choices?

  1. The current experiments do not sufficiently isolate the algorithmic advantage of structural search.

The ablation study seems too simple. It does not control for the same API budget.

Questions for authors

Please see the Critical Weaknesses section.

Also, a potentially distinguishing component of StruTune is its ability to evaluate and rank structural plans before generating or executing kernels. Does the ranking really make sense without actually executing the kernels? Some plans may seem bad at first glance, but a good kernel may still come out of such a plan.

Do you think about this structural lock-in problem as a model capability issue? If so, any way to mitigate it it via training?

4 comments
AuthorsOpenReview ↗

Rebuttal - Part 1

We thank the reviewer for recognizing the practical importance of structural lock-in and the potential usefulness of separating structural exploration from local optimization. We also appreciate the constructive suggestions on novelty, budget-controlled comparisons, pre-execution ranking, and training-based mitigation. We hope the following clarifications and additional results address these concerns.

W1: Limited discussion of novelty relative to existing planning-based kernel optimization agents

We appreciate the reviewer’s suggestions on contribution clarity and related work. Our novelty lies in identifying structural lock-in and addressing it by separating structural search from local optimization. Existing methods tend to continue local refinement within an already implemented structure, with limited exploration of structural alternatives. So our distinction from “planning before implementation” is the separation of structural and local decision spaces, rather than simply assigning planning and coding to different steps.

(1) Clarifying AccelOpt's local and global optimizations. AccelOpt's local–global distinction differs from ours. Its local examples apply algebraic simplification and instruction substitution, while its global example introduces recomputation and reorganizes loops to reduce spilling and intermediate storage usage. These illustrated transformations fall within our local implementation optimization categories L2 and L5, and thus do not change the structure as we define it.

(2) Differences from related work. AccelOpt, K-Search, and QiMeng-Kernel interleave structural and local implementation decisions. EGG separates algorithmic design from hardware tuning, but defines and selects candidates differently from StruTune. We summarize this in R_Table 1.

R_Table 1: Differences in planning and search organization between StruTune and related methods.

MethodPlanning mechanism and contentDifference from StruTune
AccelOptProposes edits to beam candidates, retains implementations by measured latency, and reuses optimization experience.Mixes structural and local changes within iterative code search.
K-SearchMaintains optimization intents and updates their priorities using execution feedback.Searches structural and local edits within the same evolving implementation space.
QiMeng-KernelMacro Thinking selects an optimization type and code region; Micro Coding implements each action.Separates action planning from coding, while interleaving structural and local decisions.
EGGRefines algorithmic seeds, selects one by measured performance, then tunes parallel mapping, tiling, and memory.Selects algorithms before parallel mapping; StruTune jointly searches A/G/P and independently tunes multiple selected structures.

We will add the missing AccelOpt and EGG citation, clarify these distinctions in Section 2 of our paper, and revise the contribution statement in the introduction.

(3) What structural transformations can StruTune systematically explore that existing planning-based agents cannot?

StruTune does not introduce structural transformations that existing agents cannot generate; it makes their exploration an explicit search stage. For DSA, these alternatives include fused online attention, partitioned attention with stable merging, and materialized-logit attention. Existing agents may discover them while modifying an implementation, whereas StruTune compares structural alternatives before code generation and independently optimizes the selected structures, reducing dependence on the initial implementation.

(4) Main contribution and empirical evidence. Our main contribution is the two-stage framework that separates structural search from local optimization. The explicit structural representation, execution-free evaluation, and independent optimization budgets work together to implement this separation, rather than constituting three standalone contributions. Our response to W2 provides detailed ablation results and analyzes the roles of structural search, local optimization, and workload dispatch under the same local optimization budget.

We will add the missing AccelOpt and EGG citation, expand these comparisons in Section 2 of our paper.

AuthorsOpenReview ↗

Rebuttal - Part 2

W2: Ablation with the same API budget

The current experiments do not sufficiently isolate the algorithmic advantage of structural search. The ablation study seems too simple. It does not control for the same API budget.

We appreciate the reviewer’s suggestion to better control the optimization budget and isolate the contribution of each component. Structural search and our local optimizer each improve performance, independently of dispatch. We redesigned the ablation on 10 FlashInfer-Bench operators on H100 to isolate these contributions.

Budget control. Every configuration uses two parallel trajectories with 10 local optimization rounds each. Ours Structural Plan initializes them from the top two of five scored structures; PyTorch Reference initializes them from reference code. Stage II uses either our action library (Ours Local Optimization) or direct LLM refinement (Direct LLM), keeping the number of trajectories and local rounds fixed.

Component contributions.

  • Structural search improves initialization. With our local optimizer and dispatch disabled, structural initialization increases GM speedup from 1.21× to 1.92×, maintaining 100% correctness.
  • Our local optimizer improves refinement. Starting from the same structural plans, our action library achieves 1.92× versus 1.42× with direct LLM refinement, both with 100% correctness.
  • Dispatch adds no benefit in this run. The candidates showed no consistent complementary performance across workloads, so the dispatch-enabled configuration retained the single-structure result of 1.92×.

R_Table 2: Ablation with the same API budget on FlashInfer-Bench on H100. GM speedup is relative to the FlashInfer expert library

#Stage I: Ours structural planStage I: PyTorch ReferenceStage II: Ours Local OptimizationStage II: Direct LLMDispatchCorrect (%)GM speedup
1—✓—✓—80.001.61×
2—✓✓——100.001.21×
3✓——✓—100.001.42×
4✓—✓——100.001.92×
5✓—✓—✓100.001.92×

We will include the revised ablation and its budget-accounting details in Section 5.3 and Appendix E of our paper.

Q1: Effectiveness of Pre-execution Structural Scoring

Also, a potentially distinguishing component of StruTune is its ability to evaluate and rank structural plans before generating or executing kernels. Does the ranking really make sense without actually executing the kernels? Some plans may seem bad at first glance, but a good kernel may still come out of such a plan.

This is really an excellent question. Pre-execution scoring effectively identifies structures with high performance potential, even when their initial implementations are slow. To evaluate this, we implemented five structures for each of the 10 FlashInfer-Bench operators on H100 and optimized each for 10 rounds without dispatch.

Pre-execution structural scoring effectively identifies promising structures. We implemented all five candidates for each of the 10 FlashInfer-Bench operators on H100 and optimized each for 10 rounds without dispatch. The top two by score include the best-performing final structure for every operator (R_Figure 1), demonstrating the effectiveness of ranking structures before execution.

R_Figure 1: Structural scores versus final performance on 10 FlashInfer-Bench operators R_Figure 1 (https://anonymous.4open.science/r/ICLR_2027_Rebuttal-C98D/R_Figure_1.png)

Structural scoring also identifies potential that initial performance comparisons can miss. For DSA, the highest-scored structure, S₁, initially achieves approximately 5× speedup, below S₂’s 11×, but reaches approximately 38× after optimization, compared with S₂’s 20× (R_Figure 2). Thus, selecting by initial performance would favor S₂, while structural scoring correctly prioritizes S₁’s greater optimization potential.

R_Figure 2: Structural scores versus initial and optimized speedups for five DSA structures on H100. R_Figure 2 (https://anonymous.4open.science/r/ICLR_2027_Rebuttal-C98D/R_Figure_3.png)

We will include these analyses in Section 5.3 and Appendix E of our paper.

AuthorsOpenReview ↗

Rebuttal -Part 3

Q2: Model Capabilities and Trajectory Training for Mitigating Structural Lock-in

Do you think about this structural lock-in problem as a model capability issue? If so, any way to mitigate it it via training?

This is a practically important question. Structural lock-in may partly reflect a model capability limitation, and targeted trajectory training could help mitigate it.

(1) Recognizing a slow kernel does not necessarily mean identifying a structural bottleneck. A model may detect poor performance without determining whether it stems from structural design or implementation choices. One possible reason is limited training data that explicitly connects performance bottlenecks to structural causes and demonstrates how to address them.

(2) Training on bottleneck diagnosis and structural changes could improve this capability. Such trajectories should show how to identify a performance bottleneck, link it to structural design, and modify the structure, followed by correctness and performance evaluation. This supervision could help models learn both when structural changes are necessary and how to make them effectively.

We will discuss this model capability issue and training direction in Section 6 of our paper.

Thank you again for your valuable suggestions. As the rebuttal deadline approaches, we have revised the organization of our responses to clarify our main contribution and its relationship to prior work. We added a concise comparison with AccelOpt, K-Search, QiMeng-Kernel, and EGG, and made the supporting component ablations and pre-execution scoring results more prominent. We also clarified how trajectory training could help mitigate structural lock-in.

We would appreciate your feedback on whether the revised explanations and evidence address your concerns about novelty and experimental support. If further clarification would be helpful, we would be happy to provide it during the remaining discussion period.

Thank you again for your time and consideration.

Reviewer_FeEPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

StruTune argues that current kernel agents often commit to one high-level implementation structure too early and spend most of their budget tuning parameters within that structure. It separates search into two stages: first, generate and rank abstract structural plans; then, realize the top-ranked plans and optimize each one independently under a fixed structure contract. The paper evaluates this approach on 29 selected operators from FlashInfer-Bench and SOL-ExecBench, using A800 and H100 GPUs. The reported results are strong: StruTune reaches 100% task success on both platforms and improves aggregate speedups over the compared agent baselines. The main empirical claim is that explicitly exploring alternative structures before local tuning yields both better kernels and lower token use.

Critical strengths

The paper raises a meaningful issue in agentic kernel optimization. The distinction between high-level computation structure and low-level tuning choices is useful, and the DSA trace analysis gives a concrete example of why repeatedly editing one incumbent may be limiting.

The system is described in unusual detail. The paper specifies the structural representation, the local-action taxonomy, contracts, search budgets, prompts, and evaluation protocol. This makes the intended separation between Stage I and Stage II much clearer than in many agent-system papers.

The evaluation is broader than a single benchmark or a single GPU. It includes 29 tasks, two benchmark suites, two NVIDIA architectures, correctness rates, per-task results, and token accounting.

The paper is careful in a few important places. It distinguishes paired comparisons from raw aggregate averages, reports failed tasks instead of assigning them artificial speedups, and explicitly notes limitations of the current structural evaluator.

Critical weaknesses

The central selection mechanism is not validated. Stage I generates five plans but only optimizes the top two according to an LLM-produced structural score. The paper never shows whether this score predicts downstream performance, whether the best final structure is usually ranked in the top two, or whether score-based selection is better than random selection, diversity-based selection, or simply optimizing the first two plans. Figure 4 evaluates all five structures and is normalized by the best of those same five, so it demonstrates that diversity can help, but not that the proposed reviewer successfully identifies promising structures.

The ablation does not isolate the effect of structure-first search. The full method enables workload dispatch, whereas both “structure-only” and “local-only” disable it. Thus, the gain from the full method conflates structural search, independent local optimization, and final dispatch. This is particularly important because dispatch can combine complementary candidates and may account for a substantial part of the reported improvement.

The claimed structure-preservation guarantee is weaker than the presentation suggests. The contract checker validates coder-declared logical fields against the plan, but Appendix A explicitly states that it is not a static proof that the generated Triton code implements those obligations. A local edit could therefore alter the effective computation structure without being detected. This undermines the claim that each Stage II trajectory remains within a fixed structure.

The evidence for “structural lock-in” is limited and partly self-reported. The cross-task structure counts come from agents reviewing their own logs and are not independently verified. The controlled replay is only performed on one DSA task. More importantly, the StruTune replay input includes a fixed two-branch dispatch rule, while the competing inputs are single structures. The reported 37.47x result therefore does not cleanly establish that the underlying structure is better.

The resource comparison is not yet a fair budget comparison. Baselines use very different stopping rules: one-hour limits for some agents, a fixed search budget for K-Search, and up to 400 attempts for Dr. Kernel. StruTune uses five structural candidates and two ten-step local trajectories. Token counts are useful, but the paper does not report end-to-end wall-clock time, API cost, cache effects, or a matched-budget performance curve. The claim of much lower search cost should be made more cautiously.

The method is tuned and dispatched on the same workload suite used for final evaluation. This is reasonable if the deployment workload set is known in advance, but it does not establish generalization to unseen shapes or workload distributions. There is no held-out workload evaluation, and the final dispatch rules are selected using performance on the evaluation suite itself.

The measurement protocol is relatively light for the size of the claims: five timed iterations and one timing trial, with no reported variance across repeated agent runs. The pipeline is stochastic, and FlashInfer input generation is not seeded. The paper needs repeated end-to-end runs or, at minimum, confidence intervals for the main comparisons.

Questions for authors

Across all tasks, how often does the Stage I top-two ranking contain the best structure found after optimizing all five plans? Please compare the reviewer-score policy against random selection, diversity-based selection, and an oracle upper bound.

What is the performance of the full pipeline with dispatch disabled? A clean ablation should separate the contributions of structural search, independent local tuning, and workload dispatch.

How do the authors verify that a generated Triton program still implements the selected structure, rather than merely returning a matching self-declared contract? Can they provide independent code-level annotations or a static verifier for a representative subset?

Can the DSA replay be repeated without the fixed two-branch StruTune dispatch rule, and on several operators beyond DSA? This would clarify whether the observed gain comes from structural quality rather than composition across specialized branches.

Can the authors provide matched-budget comparisons in terms of total tokens, wall-clock search time, and monetary cost? A performance-versus-budget curve would be more informative than comparing methods with different stopping rules.

Are the 29 tasks fixed before method development? Please provide the full selection protocol and evaluate on held-out workloads or shapes that were not used during planning, tuning, or dispatch construction.

How stable are the results across independent runs of StruTune? Please report variation in success rate, speedup, selected structures, and token consumption.

10 comments
AuthorsOpenReview ↗

Rebuttal - Part 1

We appreciate the reviewer’s recognition of the meaningful problem addressed by StruTune, the detailed system specification, and the breadth and care of our evaluation. We also thank the reviewer for the constructive feedback, which has guided additional experiments and a clearer account of our method and its limitations. We hope the following results and clarifications address the reviewer’s remaining concerns.

W1: Central selection mechanism

We thank the reviewer for raising this issue. We added score–downstream performance curves and a selection-policy ablation on the 10 FlashInfer-Bench operators on H100. The results show that the top-two ranking contains the best final structure for all 10 operators, and score-based selection outperforms random selection, diversity-based selection, and selecting the first two plans, supporting the effectiveness of our selection strategy.

(1) Scores reflect downstream performance potential. Higher structure scores generally correspond to higher downstream performance, as shown in R_Figure 1. This positive association supports the scores as an indicator of downstream optimization potential, although the relationship is not strictly monotonic.

R_Figure 1: Structural scores versus downstream performance on 10 FlashInfer-Bench operators on H100.

R_Figure 1 (https://anonymous.4open.science/r/ICLR_2027_Rebuttal-C98D/R_Figure_1.png)

(2) Top-two coverage and comparison with alternative selection strategies. Score-based top-two selection retained the best final structure for all 10 operators and matched the five-candidate oracle, outperforming the evaluated alternatives (R_Table 1). Using the same candidate archive and local optimization results, selecting the first two plans, random selection, and diversity-based selection retained the best structure for 3, 3, and 5 operators, respectively, and achieved 90.21%, 82.43%, and 82.27% of oracle performance. These results support the effectiveness of our score-based selection strategy.

R_Table 1: Comparison of selection strategies on FlashInfer-Bench on H100

Selection strategyDetailsCorrectness rateBest-structure hit ratePerformance relative to the five-candidate oracle
Score-based top-2Select the two structures with the highest weighted scores.100.00%100.00%100.00%
First two plansSelect the first two structures in the original generation order.100.00%30.00%90.21%
Two random candidatesRandomly select two distinct structures using seed 2026.100.00%30.00%82.43%
Two diverse candidatesSelect the pair with the largest mean Jaccard distance across A/G/P structural features.100.00%50.00%82.27%

We will include these score–performance and selection-policy analyses in Section 5.3 and Appendix E of the revised paper.

AuthorsOpenReview ↗

Rebuttal - Part 2

W2: Isolating the effects of structural search, independent local optimization, and workload dispatch

The ablation does not isolate the effect of structure-first search. The full method enables workload dispatch, whereas both “structure-only” and “local-only” disable it. Thus, the gain from the full method conflates structural search, independent local optimization, and final dispatch. This is particularly important because dispatch can combine complementary candidates and may account for a substantial part of the reported improvement.

We thank the reviewer for pointing out this issue. The revised component ablation shows that structural search and local optimization provide complementary benefits, while the main gains persist without dispatch on both A800 and H100 (R_Table 2).

(1) Effect of structural search. Adding structural search to local optimization increases geometric-mean speedup from 1.37× to 3.45× on A800 and from 1.21× to 1.92× on H100 (rows 2 and 3), with dispatch disabled. This demonstrates the benefit of exploring structural alternatives before local optimization.

(2) Effect of local optimization. Combining structural search with local optimization improves geometric-mean speedup over structure-only from 2.41× to 3.45× on A800 and from 1.03× to 1.92× on H100 (rows 1 and 3). These results show that local optimization develops the performance potential of the discovered structures.

(3) Effect of workload dispatch. Dispatch provides an additional geometric-mean gain of approximately 2.4% on A800 and no additional gain in the independent H100 repeat experiment (rows 3 and 4). On A800, DSA was the only operator using dispatch: its speedup increased from 37.19× to 47.17×. Dispatch is enabled only when candidate structures exhibit stable, complementary performance across workloads, a condition that was uncommon in our evaluated runs.

R_Table 2: Ablations of dispatch and other components on FlashInfer-Bench on A800 and H100. GM speedup is relative to the FlashInfer expert library and is computed over successful tasks.

#MethodStructural searchLocal optimizationDispatchA800 Success (%)A800 GM speedupH100 Success (%)H100 GM speedup
1Structure-only✓——100.002.41×100.001.03×
2Local-only—✓—100.001.37×100.001.21×
3StruTune without dispatch✓✓—100.003.45×100.001.92×
4StruTune with dispatch✓✓✓100.003.53×100.001.92×

We will include these component and dispatch ablations in Section 5.3 and Appendix E of the revised paper.

W3: Structure preservation and consistency between declared contracts and generated code

The claimed structure-preservation guarantee is weaker than the presentation suggests. The contract checker validates coder-declared logical fields against the plan, but Appendix A explicitly states that it is not a static proof that the generated Triton code implements those obligations. A local edit could therefore alter the effective computation structure without being detected. This undermines the claim that each Stage II trajectory remains within a fixed structure.

Thank you for highlighting this distinction.

(1) Stage II maintains the selected structure through constraints on local action selection and implementation, together with contract consistency checks. The Local Planner selects an action from the library in Appendix A.5 and specifies how and where to modify the code. These actions target the local implementation configuration while preserving the selected structure. The contract checker additionally checks the coder-declared logical fields against the fixed plan.

(2) To strengthen verification of consistency between declared contracts and generated code, we can extend the Local Reviewer to inspect modifications directly and check whether they follow the local plan and preserve the selected structure. Such inspection would provide additional code-level evidence.

(3) A static proof is particularly challenging because a single fixed set of static rules does not readily recover the A/G/P abstraction from Triton implementations across diverse operator types.

We will clarify these structural constraints and the scope of the contract checker in Section 4.2 and Appendix A.2 of our paper.

AuthorsOpenReview ↗

Rebuttal - Part 3

W4: Independent verification of structure counts and replay without dispatch

The evidence for “structural lock-in” is limited and partly self-reported. The cross-task structure counts come from agents reviewing their own logs and are not independently verified. The controlled replay is only performed on one DSA task. More importantly, the StruTune replay input includes a fixed two-branch dispatch rule, while the competing inputs are single structures. The reported 37.47x result therefore does not cleanly establish that the underlying structure is better.

We appreciate the reviewer’s careful examination of the structural lock-in evidence. We conducted independent verification of the structure counts and added dispatch-free replay experiments for DSA, GDN decode, and GEMM. These results confirm the accuracy of the reported counts and support the performance advantage of the discovered structures without dispatch. We hope this additional evidence addresses the reviewer’s concerns.

(1) Independent verification of structure counts. The results in Table 1 and Figure 2(a) are reliable and have been independently verified by three experts. The structural counts were initially obtained through agent (Codex + gpt-5.6-sol) self-annotation. We then randomly sampled five operators for manual inspection and identified one missed structure in KDA’s DSA run. Following this correction, three experts cross-checked the implementation code and optimization logs for all 29 operators, finding no additional discrepancies and confirming the reported counts. We apologize for the unclear description and will clarify the verification procedure in Appendix D.1.

(2) Structure replay without dispatch. StruTune’s structures achieve higher speedups than the compared structures on all three operators without dispatch (R_Table 3). We repeated replay on H100 for DSA and two additional operators, GDN decode and GEMM, using single-structure inputs under the same refinement protocol. These results support the performance advantage of the discovered structures independently of workload dispatch. We will add the dispatch-free replay results to Appendix D.4.

R_Table 3: Structure replay results without dispatch for three operators on H100. Speedups are relative to the PyTorch reference implementation

OperatorBackendCodexK-SearchKDAStruTune
DSAH100 / Triton31.0829×15.4512×23.2942×42.7526×
GDN decodeH100 / Triton247.7313×243.4155×218.2175×281.8416×
GEMMH100 / Triton0.5174×0.5411×0.4745×0.5541×
Reviewer_7TzaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies LLM-based GPU kernel optimization and diagnoses structural lock-in: agents concentrate refinement on one implementation structure (computation strategy A, kernel graph G, parallelization P) while alternatives are underexplored. Evidence: (1) across 29 tasks on A800, over 87% of solved tasks for Codex/KDA/K-Search/Claude Code report 1-2 structures (Table 1); (2) DSA traces show 100%/91.5%/100% of tokens on one family; (3) a controlled replay where Codex optimizes each extracted structure with a shared budget gives STRUTUNE's skeleton 37.47x vs 28.63x best alternative (+30.88%). The method, STRUTUNE, decouples search: Stage I generates 5 structural plans, reviews validity and scores potential (5-dim rubric) without executing code; Stage II realizes top-2 and tunes each independently for 10 rounds under a fixed structure contract, with optional workload dispatch. On 29 selected operators (722 workloads, FlashInfer-Bench + SOL-ExecBench, A800/H100), it reports 100% correctness on both GPUs, 3.53x/1.81x over FlashInfer expert and 6.51x/5.77x over eager, with 78-95% lower tokens than agent baselines.

Critical strengths

S1: Clear problem framing + controlled evidence for structural lock-in. The S=(A,G,P) vs theta factorization (Sec 3.1, App A.1) makes structure testable, and the DSA replay under a shared optimizer/budget/action library is much stronger than token-share alone. The 30.88% gap on a fixed budget directly motivates the two-stage design.

S2: Strong empirical breadth with efficiency accounting. 29 operators x 2 GPUs, correctness + geometric-mean speedup reported together (correctly excluding failed tasks), paired-subset improvements (Table 27), ablations (structure-only vs local-only vs full), plus per-task token tables (App E.2). Token reduction holding per benchmark-GPU group, not just totals, is a real practical win.

Critical weaknesses

W1: Task selection + generalizability is unclear. 29 selected operators per Sec 5.1 principles, but no sampling frame, no failure cases shown, and only NVIDIA A800/H100 + Triton. The 100% correctness claim is on the evaluated tasks - ACs will read this as selection-sensitive. Needs: how many operators were considered/rejected, and discussion of transfer to other op families/backends.

W2: Structural-coverage evidence relies on agent self-annotation. Sec D.1 admits counts come from agents reviewing their own logs, not independently verified, reconciled only by zeroing unsolved tasks. KDA DSA count is manually corrected. This weakens Table 1/Fig 2(a), the core motivation. Independent code-level annotation on a subset, or inter-annotator agreement, is needed.

Additional concern: Stage-I reviewer is ungrounded - LLM 0-4 scores with fixed weights (0.25/0.25/0.20/0.15/0.15) with no ablation on weights, no correlation of score vs realized speedup, and dispatch effect is conflated in the full-method ablation (Sec 5.3 admits including dispatch in the full method, rather than isolating a dispatch-free effect).

Questions for authors

For Table 1: can you report independent (non-agent) structure labels for at least the DSA case + one more operator, and agreement rate?

What is the correlation between Stage-I R(S) scores and realized F(k)? How sensitive is top-2 selection to the weights and to m=2 vs m=3?

What is the dispatch-only gain? Report full method with dispatch disabled to isolate local-tuning benefit.

6 comments
AuthorsOpenReview ↗

Rebuttal - Part 1

We thank the reviewer for the positive feedback and are glad to hear that our structural lock-in analysis and efficiency reporting were recognized. We hope the following discussions address the reviewer's remaining concerns.

W1: Task selection and generalizability are unclear

We thank the reviewer for pointing out this issue.

(1) Task selection. We selected operators from two widely used benchmarks, FlashInfer-Bench and SOL-ExecBench, covering as many operator categories and computational patterns as possible. Sampling frame: FlashInfer-Bench contains 43 tasks grouped into DSA, GDN, GEMM, GQA Paged, GQA Ragged, MLA Paged, and RMSNorm, with separate prefill and decode variants for GDN, GQA Paged, and MLA Paged. SOL-ExecBench contains 94 L1 tasks (single operations) and 82 L2 tasks (fused operations), categorized into Attention, MoE, Normalization, Embedding/Pos, Linear/Proj, Fused Block, MLP/Activation, GEMM, Conv, SSM/Mamba, and Other. Considering the cost, we initially selected 10 operators from each of FlashInfer-Bench, SOL-ExecBench L1, and SOL-ExecBench L2, prioritizing diverse operator categories and computational patterns while avoiding duplicate operators across benchmarks. Rejected operator: We subsequently excluded SOL-ExecBench L2/057_residual_coupling_flow_block because its 12 successive convolutional layers amplify numerical discrepancies through repeated accumulation, causing mathematically equivalent implementations to exceed the evaluator’s tolerance. The final evaluation therefore comprises 29 operators.

(2) Generalizability. StruTune generalizes across hardware architectures and programming languages. It represents structure through computation strategy, logical kernel graph, and semantic parallelization, separating these decisions from hardware-specific implementation mechanisms and Triton-specific syntax or execution primitives. These structural plans can therefore also be realized in TileLang, which supports tile-based computation. To validate this generalizability, we conducted additional experiments using Triton on B200 and TileLang on H100. Since our original FlashInfer-Bench subset already covers its operator families, we focused on three operators with distinct computational patterns—DSA, GDN decode, and GEMM. The results in R_Table 1 provide empirical support for StruTune’s applicability across hardware architectures and programming languages.

R_Table 1: Results for three operators using Triton on B200 and TileLang on H100. Speedups are relative to the PyTorch reference implementation.

OperatorBackendCodexK-SearchKDAStruTune
DSAB200 / Triton42.21×19.19×25.74×47.95×
GDN decodeB200 / Triton291.78×265.32×255.32×335.34×
GEMMB200 / Triton0.61×0.61×0.57×0.62×
DSAH100 / TileLang2.58×6.99×23.97×62.63×
GDN decodeH100 / TileLang447.53×439.56×432.13×493.08×
GEMMH100 / TileLang0.81×0.65×0.82×0.79×

We hope these clarifications and additional experiments address the reviewer’s concerns. We will document the task selection and exclusion procedure, together with the operator-category breakdown of the selected tasks, in Appendix C, and include the additional hardware and language generalization results in Appendix E.

W2: Structural-coverage evidence relies on agent self-annotation

W2: Structural-coverage evidence relies on agent self-annotation. Sec D.1 admits counts come from agents reviewing their own logs, not independently verified, reconciled only by zeroing unsolved tasks. KDA DSA count is manually corrected. This weakens Table 1/Fig 2(a), the core motivation. Independent code-level annotation on a subset, or inter-annotator agreement, is needed.

We thank the reviewer for raising this significant issue. The results in Table 1 and Figure 2(a) are reliable and have been independently verified by three experts. The structural counts were initially obtained through agent (Codex + gpt-5.6-sol) self-annotation. We then randomly sampled five operators for manual inspection and identified one missed structure in KDA’s DSA run. Following this correction, three experts cross-checked the implementation code and optimization logs for all 29 operators, finding no additional discrepancies and confirming the reported counts. We apologize for the unclear description and will clarify the verification procedure in Appendix D.1.

AuthorsOpenReview ↗

Rebuttal - Part 2

W3: ablation on scoring weights, correlation of score vs realized speedup, and dispatch effect isolation

Additional concern: Stage-I reviewer is ungrounded - LLM 0-4 scores with fixed weights (0.25/0.25/0.20/0.15/0.15) with no ablation on weights, no correlation of score vs realized speedup, and dispatch effect is conflated in the full-method ablation (Sec 5.3 admits including dispatch in the full method, rather than isolating a dispatch-free effect).

We thank the reviewer for raising these concerns. We added a scoring-weight ablation and a score–performance correlation analysis on the 10 FlashInfer-Bench operators on H100, and dispatch-effect isolation experiments on both A800 and H100, hoping these can address the reviewer's concerns.

(1) Ablation on scoring weights. The results show that candidate selection is reasonably robust to weight changes and that our original weights are a reasonable choice. These weights reflect our assessment of the dimensions’ relative importance: computation quality and parallelism (0.25 each), reuse (0.20), and state and coordination efficiency (0.15 each). We compared them with uniform weights and five configurations assigning 80% to one dimension. As shown in R_Table 2, original and uniform weights both achieved 1.920× geometric-mean speedup over the FlashInfer expert reference and retained the best structure for all 10 operators. The single-dimension-heavy configurations achieved 1.740–1.920× and retained the best structure for 8–10 operators.

R_Table 2: Ablation of scoring weights on FlashInfer-Bench on H100. GM speedup is relative to the FlashInfer expert library

Weights configurationWeightsSelection ruleGM speedupBest-structure coverage
Original weights0.25/0.25/0.20/0.15/0.15Top-21.920×10/10
Uniform weights0.20/0.20/0.20/0.20/0.20Top-21.920×10/10
Computation-heavy weights0.80/0.05/0.05/0.05/0.05Top-21.920×10/10
Parallelism-heavy weights0.05/0.80/0.05/0.05/0.05Top-21.917×9/10
Reuse-heavy weights0.05/0.05/0.80/0.05/0.05Top-21.740×9/10
State-efficiency-heavy weights0.05/0.05/0.05/0.80/0.05Top-21.790×8/10
Coordination-efficiency-heavy weights0.05/0.05/0.05/0.05/0.80Top-21.740×9/10

(2) correlation of score vs realized speedup. Scores are positively associated with realized speedup, supporting their use as an indicator of structural optimization potential. We optimized all five candidates per operator for 10 rounds without dispatch. As shown in R_Figure 1, higher scores generally correspond to higher final speedups within an operator, although this relationship is not strictly monotonic and varies across operators.

R_Figure 1: Score versus realized speedup of 10 FlashInfer-Bench operators on H100

R_Figure 1 (https://anonymous.4open.science/r/ICLR_2027_Rebuttal-C98D/R_Figure_1.png)

(3) Dispatch effect isolation. The performance gains persist without dispatch on both A800 and H100 (R_Table 3). On A800, disabling dispatch reduces geometric-mean speedup from 3.53× to 3.45×. DSA was the only operator using dispatch, with its speedup decreasing from 47.17× to 37.19× when dispatch was disabled. In the independent H100 repeat experiment, both settings achieved 1.92× geometric-mean speedup, indicating no additional dispatch benefit. Dispatch is enabled only when candidate structures exhibit stable, complementary performance across workloads; this condition was uncommon in our evaluated runs.

R_Table 3: Ablation isolating the dispatch effect on FlashInfer-Bench on A800 and H100. GM speedup is relative to the FlashInfer expert library on successful tasks

#MethodStructural searchLocal optimizationDispatchA800 Success (%)A800 GM speedupH100 Success (%)H100 GM speedup
1Structure-only✓——100.002.41×100.001.03×
2Local-only—✓—100.001.37×100.001.21×
3StruTune without dispatch✓✓—100.003.45×100.001.92×
4StruTune with dispatch✓✓✓100.003.53×100.001.92×

Following the reviewer’s suggestions, we will incorporate these additional analyses and ablation results into Section 5.3 and Appendix E of the revised paper.

AuthorsOpenReview ↗

Rebuttal - Part 3

Q1: Independent structure labels for DSA, GDN decode and GEMM, and agreement rate across all operators

For Table 1: can you report independent (non-agent) structure labels for at least the DSA case + one more operator, and agreement rate?

We thank the reviewer for this suggestion. We added independent structure labels for DSA, GDN decode, and GEMM and verified agreement between structure counts reported in our paper and expert-verified across all 29 operators.

(1) Independent structure labels. We provide independent structure labels for DSA, GDN decode, and GEMM in R_Table 4. Each label follows S = (A, G, P), with its semantics summarized in R_Table 5. The complete formalized plans are available in our anonymous repository (https://anonymous.4open.science/r/ICLR_2027_Rebuttal-C98D/Structure_Labels.md).

R_Table 4: Structure labels for DSA, GDN decode, and GEMM

OperatorClaude CodeCodexKDAK-Search
DSAD1, D2D3D1, D2D1
GDN decodeR1R1R1R1
GEMMM1M1M1, M2Excluded*

R_Table 5: A/G/P semantics of the structure labels in R_Table 4

LabelA: computation strategyG: logical stagesP: parallelization strategy
D1Fused online sparse attentionOne stage produces output and LSE.Parallelize over tokens and heads; each owner covers all sparse positions.
D2Partitioned attention with stable mergingPartial states (m, l, U) → stable merge.Parallelize over tokens, heads, and position partitions; merge per token/head.
D3Materialized-score attentionScores → normalization and value reduction.Parallelize scores over tokens, heads, and positions; value reduction over tokens, heads, and output coordinates.
R1Fused recurrent update and readoutOne stage produces updated state and output.Parallelize over batches, value heads, and value rows; reduce over all K coordinates.
M1Direct GEMMComplete K contraction → C.Parallelize over output coordinates (m, n); each owner covers all K.
M2Partitioned-K with explicit reductionSeparate partial products → reduction → C.Parallelize partial products over output coordinates and K partitions; reduce partitions per output coordinate.

* K-Search GEMM calls torch.matmul for larger M and is excluded under Table 1’s final-outcome reconciliation rule.

(2) Agreement rate across all operators. The structure counts reported in our paper match the expert-verified counts across all 29 operators (100% agreement). Please refer to our response to W2 for the verification procedure.

We will add the structure labels for these three operators to the appendix. We are glad to provide labels for all evaluated operators if the reviewer considers them necessary.

Q2: Score–performance correlation and selection sensitivity to scoring weights and candidate count

What is the correlation between Stage-I R(S) scores and realized F(k)? How sensitive is top-2 selection to the weights and to m=2 vs m=3?

(1) Score–performance correlation and sensitivity to scoring weights. Higher structural scores generally correspond to higher realized speedups, and candidate selection is reasonably robust to weight changes. Please see our response to W3, points (1)–(2), for the supporting analyses.

(2) Sensitivity to candidate count. Retaining two structures matches the performance of retaining three or four while requiring fewer local optimization trajectories. We compared m=1, 2, 3, and 4 using the same five-candidate archive on the 10 FlashInfer-Bench operators on H100. Each retained structure received 10 local optimization rounds, without dispatch. Increasing m from 1 to 2 improved geometric-mean speedup from 1.913× to 1.920×, while m=3 and m=4 yielded no further improvement; all settings achieved 100% correctness (R_Table 6). These results support m=2 as a practical choice on this evaluated subset.

R_Table 6: Ablation of candidate count on FlashInfer-Bench on H100. GM speedup is relative to the FlashInfer expert library

ConfigurationCandidate countCorrectness rateGM speedup
m=11100.00%1.913×
m=22100.00%1.920×
m=33100.00%1.920×
m=44100.00%1.920×

We will add the candidate-count ablation to Section 5.3 and Appendix E of our paper.

Q3: Dispatch-only gain

What is the dispatch-only gain? Report full method with dispatch disabled to isolate local-tuning benefit.

Dispatch improved performance by approximately 2.4% on A800 and provided no additional gain in the independent H100 repeat experiment. Please see our response to W3, point (3), for details.

Comments on the paper

2 comments
Area_Chair_MefqOpenReview ↗

Reminder: Author–reviewer discussion ends today

Dear Reviewers,

As the author–reviewer discussion period ends today (November 18, AoE), please read the authors’ responses, any relevant manuscript updates, and the other reviewers’ comments, and engage with the authors before the deadline.

In particular, please clarify which of your concerns have been addressed and which remain unresolved, and raise any remaining questions promptly so the authors have an opportunity to respond. Even if your assessment is unchanged, a brief follow-up explaining your reasoning would be helpful.

Thank you for your time and thoughtful reviewing!

Area Chair

Dear Area Chair and Reviewers,

As the discussion period draws to a close, we thank you for your constructive feedback. We have resubmitted a revised version of the rebuttal, in which we reorganized our responses in the hope of addressing your questions more clearly. In response, we added extensive experiments to validate StruTune’s structural selection, isolate its gains from dispatch, assess generalization and stability, and provide matched-budget comparisons. We also independently verified the reported structures and clarified our novelty, evaluation protocol, and planned manuscript revisions. We hope these additions have addressed the main concerns, and we would be happy to clarify any remaining questions.

Thank you again for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.