- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces KLineage, a framework for constructing reusable, conditional optimization memory by progressively deoptimizing expert kernels. Accepted simplifications are reconstructed as validated forward transitions and abstracted into SkillCards containing optimization intents, code anchors, implementation carriers, preconditions, risks, and verification evidence. During online optimization, an agent retrieves skills according to the target workload, language, platform, and current optimization state, then applies them under compilation, correctness, and profiling checks.
Critical strengths
- Deoptimizing expert implementations provides a concrete and potentially valuable approach to acquiring optimization knowledge. The paper identifies a practical limitation of kernel-generation agents: knowing an optimization technique does not imply knowing whether the current program state satisfies its prerequisites. Constructing intermediate states through deoptimization, followed by validated forward reconstruction, offers a practical way to expose dependencies that are implicit in the final expert implementation.
- The evaluation includes meaningful transfer evidence beyond reconstruction of the source workloads. The paper explicitly excludes the transfer operators and broader benchmark problems from skill induction. It reports a 1.73× geometric-mean speedup over the no-skill baseline on five H100 transfer targets. On the Ascend benchmark, the number of correctly solved problems increases from 68 to 100, while the number outperforming the reference increases from 22 to 93.
Critical weaknesses
- The comparisons change expert information, knowledge representation, validation, and session organization simultaneously. They therefore demonstrate the effectiveness of the complete system, but do not isolate the benefits of backward deoptimization or explicit preconditions.
- Failed or slower intermediate candidates are expected during search and do not themselves establish a limitation of forward search. Although AdaExplore provides a search-based baseline, superiority over stronger population-based evolutionary search with comparable expert information remains unestablished. Efficiency claims also require considering offline induction costs and differences in caching and search budgets.
Questions for authors
- Isolate the benefits of backward construction and explicit conditions. Using the same expert sources and comparable context budgets, how does KLineage compare with directly summarized SkillCards without deoptimization, and with otherwise identical cards that omit preconditions and conditional scope?
- Does the advantage persist under stronger search and comparable total costs? Compare against population-based evolutionary search given the same expert information, including a broader-budget setting.
- How similar are the held-out benchmark tasks to the expert kernels used for skill induction? While the paper states that evaluation tasks do not contribute to induction, does it analyze overlap in implementation sources, computational structure, or reusable suboperators? A breakdown of transfer gains by source–target similarity would help clarify the scope of generalization.
3 comments
Response (2/2)
Continued: Q3.
Q3. Source–target similarity and the scope of generalization.
Section 4.5 evaluates five held-out transfer operators: KDA, Sparse Attention, Top-P, Fused Add-RMSNorm, and GQA. None of them are used during skill induction, which draws only from GEMM, Conv2d, FMHA, GDN, and Top-K:
| Transfer target | Shared computational basis | Key difference from induction kernels |
|---|---|---|
| KDA | Delta-rule recurrence with GDN | Different state update and gating recurrence |
| Sparse Attention | Attention and softmax with FMHA | Indexed block or token gather instead of dense tiles |
| Top-P | Selection and filtering with Top-K | Cumulative probability threshold and prefix scan |
| Fused Add-RMSNorm | Vectorized reduction patterns | No normalization kernel in the five expert sources |
| GQA | Attention computation with FMHA | Grouped KV-head broadcasting layout |
Although these operators share low-level primitives with the expert kernels, their indexing, dataflow, and synchronization differ substantially. Both without KLineage and with KLineage receive the same five expert kernels in context, isolating the transfer benefit of conditioned skills: 1.73× speedup on H100, and 1.41× speedup on Ascend while also producing a working Sparse Attention kernel where the baseline fails.
To measure similarity on the larger benchmarks, we also inspected the reference programs for all 100 KernelBench Level 2 tasks on NVIDIA and all 100 MultiKernelBench Fusion tasks on Ascend, which use the same 100 operator compositions:
| Computational family | KernelBench Level 2 | MultiKernelBench Fusion | Relation to the 5 expert kernels |
|---|---|---|---|
| GEMM / Linear compositions | 37 | 37 | Same base family as GEMM plus fused epilogues |
| Conv2d compositions | 21 | 21 | Same base family as Conv2d plus fused ops |
| Conv3d compositions | 12 | 12 | 3D convolution; no 3D expert in library |
| ConvTranspose2d compositions | 11 | 11 | Transposed stencil; no ConvTranspose expert |
| ConvTranspose3d compositions | 19 | 19 | 3D transposed convolution; no 3D or transpose expert |
Out of the 100 tasks, 58 combine GEMM or Conv2d with downstream activations, normalizations, reductions, pooling, or residual adds; for instance, task #14 fuses matrix multiplication with scaling and row-wise sum, and task #92 fuses Conv2d with GroupNorm, nonlinearities, residual addition, and LogSumExp. The other 42 tasks are built around Conv3d, ConvTranspose2d, or ConvTranspose3d, which have no matching operator among the five expert kernels. Even so, KLineage produces 100 out of 100 correct kernels on both platforms. Compared with without KLineage, which receives the same five expert sources as few-shot examples, KLineage raises Ascend correctness from 68 to 100 and speedup over PyTorch from 0.63× to 2.09×, and raises NVIDIA speedup over torch.compile from 1.05× to 1.32×. Getting all 42 Conv3d and ConvTranspose tasks right shows that lower-level conditioned skills, such as GM-to-UB ping-pong staging, vectorized aligned transfers, tiling and launch partitioning, and explicit DMA/Vector/Cube synchronization, transfer beyond the source operator families.
Dear Reviewer qX11,
Thank you again for your time and constructive feedback on our submission. As the author–reviewer discussion deadline (Nov 18 AoE) approaches, we wanted to gently check in to see whether our rebuttal and revised manuscript have addressed your concerns and might impact your rating.
Please let us know if any question remains or if there is anything else we can clarify before the discussion period closes. We would greatly appreciate your feedback!
Response (1/2)
Thank you for your valuable comments.
Q1. Isolating backward construction and explicit conditions.
Section 4.3 and Appendix C, Table 9 compare conditioned skills with direct expert-source prompting under a 10 USD budget, where source-prompted agents spent most of their context reasoning through C++ templates and MMA layouts without recovering the full optimization structure. To separate backward deoptimization, explicit preconditions, and conditional retrieval under identical expert information and comparable context budgets, we evaluate five variants on all 100 MultiKernelBench Fusion tasks on Ascend with DeepSeek-V4.1-Flash and Codex (Section 4.6, Table 5). Importantly,
Without KLineageis not a zero-guidance baseline: in both Section 4.5 and Section 4.6, it receives the exact same five expert kernel source files as few-shot examples, without SkillCards.Direct-summary SkillCardssummarize those same expert sources using the identical schema and roundtrip validation without Guided Deoptimization, while the two condition ablations keep full implementation guidance and session setup:0.30×paired speedup vs. full KLineage, whereas all SkillCard variants solve 85 to 100 tasks at0.58×to1.00×.1.00×to0.81×or0.73×.1.00×to0.58×. Guided Deoptimization exposes intermediate code states and ordering dependencies that stay entangled in the final expert code.Q2. Stronger search and comparable total costs.
We compare KLineage with the official OpenEvolve evolutionary search framework on all 100 Ascend MultiKernelBench Fusion tasks using DeepSeek-V4.1-Flash, with population size 5, migration interval 10, and the default five-island setup (Section 4.7, Table 6). For fairness, OpenEvolve receives the exact same five expert kernel sources and hardware descriptions in context under 12 USD and 60 USD total online API budgets across the 100 tasks:
0.29×to0.48×, compared with 87 and 100 correct kernels and1.72×and2.47×speedups for KLineage. This gap mainly reflects that OpenEvolve is built around LLM endpoint calls without a full loop-based agent harness such as Codex, whereas Table 5 in Q1 isolates the gain from KLineage's skills under the same Codex harness. We see integrating techniques like evolution-based search into our system for more efficient online skill reuse as future work.