Skip to content

HTAM: Hierarchical Transition-Attended Memory for Operator Optimization

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Agent
Keywords: LLM Agent, GPU Operator Optimization, Hierarchical Memory, Transition Graph, CUDA Kernel Generation

TL;DR

To resolve the granularity mismatch in LLM-based GPU operator optimization—where coarse hints are reusable but non-executable, while fine-grained traces are actionable but inflate search space—HTAM introduces a Hierarchical Transition Graph (HTG) that guides coarse-to-fine kernel evolution via position-aware transition-attended scoring, reaching 98.4% correctness and a 1.978× geometric mean speedup on the full 250-task KernelBench suite.

Background & Motivation

The rapid scaling of large language models (LLMs) and the continuous evolution of specialized accelerator architectures have created an urgent imperative for high-performance GPU operator development. However, authoring optimized GPU kernels remains a heavily specialized, labor-intensive engineering undertaking. Developers must master complex hardware constraints, including multi-level GPU memory hierarchies (global memory, shared memory, registers), domain-specific execution units (such as Tensor Cores), and strict thread mapping and synchronization rules. Although modern code LLMs exhibit remarkable one-shot code synthesis capabilities, automated kernel optimization cannot be treated as a single-turn generation task; the combinatorial nature of hardware-aware design spaces necessitates multi-step iterative exploration and refinement.

During this multi-step evolutionary search, existing methods face a fundamental tension regarding how optimization experience is organized and reused across steps. On the one hand, systems like CudaForge rely on coarse-grained bottleneck diagnoses and high-level textual hints. While these high-level descriptions generalize well across diverse operators and are easy to retrieve, they remain too abstract to prescribe the exact syntax, pointer reinterpretation, or alignment guards required for inline CUDA code generation. On the other hand, approaches like Robust-KBench depend on fine-grained implementation traces. Although rich in concrete edit details, fine-grained representations cause the state-action search space to explode combinatorially, introducing severe syntactic noise into memory retrieval and frequently causing the agent to stagnate in brittle local code perturbations.

To bridge this granularity mismatch, this paper draws inspiration from the workflow of human performance engineers, who systematically diagnose macro-level architectural bottlenecks before applying micro-level code transformations. Core idea: organize optimization experience into a two-level Hierarchical Transition Graph (HTG) decoupling global optimization directions, local strategy cards, and pairwise transition edges, using position-aware attention-inspired transition scoring to guide multi-step coarse-to-fine kernel evolution while shrinking memory complexity from exponential full paths to compact pairwise relations.

Method

Overall Architecture

HTAM models GPU operator optimization as an iterative state-evolution process over \(T\) steps. At each step \(t\), the system first summarizes the current implementation \(c_t\), task context, and compilation/execution feedback into a compact decision state \(s_t\). It then navigates a two-level Hierarchical Transition Graph (HTG) in a top-down manner: first, a global optimization direction \(g_t\) is selected using a deterministic feature-based scoring function that aggregates pairwise transition-edge memories weighted by position-aware attention across recent history; second, candidate local strategies are strictly constrained to the subset of local strategy nodes \(\mathcal{L}(g_t)\) under the chosen global intent, allowing an LLM to evaluate the candidate strategy cards against the code symptoms and produce a concrete edit plan; third, the LLM generates the evolved inline-CUDA kernel \(c_{t+1}\) informed by the selected local card; finally, after hardware compilation and numerical verification on the target GPU, the empirical outcome is written back into node and edge memories via a dual-track architecture separating static priors from runtime evidence.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Initial Operator c0 & Task Context"] --> B["State Summarization<br/>Extract compile/correctness/runtime st"]
    B --> C["Hierarchical Transition Graph Memory<br/>Global VG + Local VGL + Transition EG"]
    C --> D["Global Direction Selection<br/>Position-aware attention over transition edges"]
    D --> E["Local Strategy Selection<br/>LLM scoring constrained to parent global node"]
    E --> F["Inline CUDA Generation & Evaluation<br/>Generate code & benchmark on A100 GPU"]
    F -->|Feedback ot| G["Dynamic Dual-track Memory Update<br/>Update runtime stats on nodes & edges"]
    G -->|t < T| B
    F -->|Best candidate reached| H["Output Optimized Kernel c*"]

Key Designs

1. Hierarchical Transition Graph Memory: Decoupling Global Intents, Local Cards, and Transition Edges

Existing methods either store flat textual snippets or attempt to record full sequence-level trajectories, which leads to exponential memory growth (\(O(|V_G|^T)\)) and severe data sparsity. HTAM formalizes memory as a Hierarchical Transition Graph \(\mathcal{M} = (V_G, V_{GL}, E_G)\). Global nodes \(V_G\) represent coarse, reusable optimization intents (Memory Access, Data Reuse, Instruction Throughput, Boundary Handling, Parallel Mapping) equipped with static priors (goals, triggers, risks) and dynamic statistics (attempt frequency, success rate, speedup trends). Local nodes \(V_{GL}\) are structured under their respective parent global nodes, serving as expert-curated "strategy cards" (such as aligned vectorized loads or read-only cache promotion under Memory Access) that detail applicable preconditions, concrete code templates, verification rules, and historical positive/negative evidence. Global transition edges \(E_G\) span all ordered pairs \((g_i, g_j) \in V_G \times V_G\), recording the empirical utility and risks of moving between global directions. By bounding the number of transition memories to \(O(|V_G|^2)\), HTAM prevents low-level implementation noise from corrupting macro routing while maintaining actionable local execution guidance.

2. Global Direction Selection: Position-Aware Attention Scoring over Pairwise Transition Edges

Conditioning decisions on full historical prefixes (\(pg_t \to g\)) suffers from extreme sparsity because exact multi-step sequences rarely repeat across operators. Conversely, conditioning only on the immediately preceding step (\(g_{t-1} \to g\)) discards critical context, such as whether memory layout has already been transformed or register pressure has already peaked. HTAM introduces a position-aware attention-weighted scoring rule: given the global prefix \(pg_t = (g_1, \dots, g_{t-1})\), the utility score for candidate global direction \(g \in V_G\) is aggregated from pairwise transition edges:

\[\text{score}_g(g \mid pg_t, s_t) = \sum_{i < t} \alpha_i \phi(g_i, g \mid s_t)\]

where \(\phi(g_i, g \mid s_t) = \mathbf{w}^\top \mathbf{z}(s_t, g_i, g)\) is a deterministic linear evaluation function mapping state-conditioned edge features into scalar utility across performance gains \(\mathbf{z}_{imp}\), execution reliability \(\mathbf{z}_{rel}\), and failure risks \(\mathbf{z}_{risk}\); the position-aware weight \(\alpha_i\) implements exponential recency decay inspired by attention mechanisms:

\[\alpha_i = \exp(-\lambda(|pg_t| - i))\]

This decay assigns greater importance to recent optimization choices while retaining sensitivity to early architectural commitments. The global direction is then sampled via an \(\epsilon\)-greedy Softmax policy. Because this routing is computed deterministically over graph edges, it incurs zero LLM API cost.

3. Local Strategy Selection: Constrained Search Space and Card-Guided Code Generation

Once global intent \(g_t\) is selected, HTAM restricts candidate local strategies strictly to its children \(\mathcal{L}(g_t) = \{l \in V_{GL} : \text{par}(l) = V_G(g_t)\}\), eliminating the noise of searching through the entire strategy space. The LLM evaluates only 3–5 candidate strategy cards against the current code implementation \(c_t\) and decision state \(s_t\), returning a structured decision consisting of the selected card, rationale, and a concrete edit plan:

\[l_t = \arg\max_{l \in \mathcal{L}(g_t)} \text{LLM}(s_t, c_t, V_G(g_t), V_{GL}(l))\]

During subsequent code generation, the chosen strategy card injects precise engineering idioms—such as 16-byte memory alignment guards, scalar fallbacks, and grid-stride loops—into the prompt context. This equips the LLM to synthesize clean, syntactically correct inline CUDA C++ kernels (\(c_{t+1}\)) with PyTorch C++ extension bindings.

4. Dynamic Dual-track Memory Update: Separating Static Priors from Runtime Trajectory Feedback

To prevent memory pollution while enabling continuous adaptation, HTAM equips every node and edge with dual-track memory: read-only static priors and writable runtime feedback. Static priors encode domain knowledge regarding theoretical goals, execution constraints, and typical failure modes. Following kernel compilation and execution at each step, runtime outcomes \(o_t\) (compilation status, numerical error tolerances, execution latency, and bottleneck signals) are parsed and committed back into the graph instance via deterministic update rules. Successful steps append positive evidence to \(V_{GL}(l_t)\) and reinforce \(E_G(g_{t-1}, g_t)\), whereas compilation crashes or performance regressions append negative risk evidence. This update mechanism requires no LLM calls and dynamically refines decision priors both within and across optimization trajectories.

A Worked Example

Consider the optimization trajectory of the Swish activation operator (kb_l1_25_swish) from KernelBench Level-1: 1. Baseline State (Step 0): The unoptimized PyTorch eager implementation x * torch.sigmoid(x) executes on an A100 GPU in 18.2 ms (1.00× baseline speedup). 2. First Evolution (Step 1): State summarization identifies redundant DRAM traffic caused by materializing an intermediate sigmoid tensor. HTAM selects global direction g_data_reuse_locality (Data Reuse) and retrieves local card l_g_reuse_light_epilogue_fusion. The LLM synthesizes a single fused scalar CUDA kernel computing \(y_i = x_i / (1 + \exp(-x_i))\), lowering execution time to 9.56 ms (1.904× speedup). 3. Second Evolution (Step 2): Transitioning from Data Reuse to g_memory_access_optimization (Memory Access), the agent retrieves l_g_mem_aligned_vec4_main_tail. The generated code introduces a vectorized float4 main loop guarded by 16-byte memory alignment checks and preserves a scalar fallback loop, dropping latency to 7.77 ms (2.342× speedup). 4. Third Evolution (Step 3): Continuing within Memory Access, the agent selects l_g_mem_ldg_readonly_texture_path. It updates the kernel to utilize __ldg() read-only cache intrinsics and replaces standard library math with the hardware-accelerated fast intrinsic __expf(), achieving a final runtime of 7.76 ms (2.345× overall speedup).

Key Experimental Results

Main Results

Evaluated on the full 250-task KernelBench suite (100 Level-1 single-operator tasks, 100 Level-2 operator-fusion tasks, and 50 Level-3 model-level subgraphs) under the official evaluation protocol on an NVIDIA A100-SXM4-80GB GPU with PyTorch 2.9.1 and CUDA 12.8, HTAM demonstrates superior reliability and speedup compared to controlled baselines:

Method TTS Evo Mem HieDec Correct↑ Fast@1↑ GeoM Spd.↑ L1 Spd.↑ L2 Spd.↑ L3 Spd.↑
DeepSeek-R1 (Direct) × × × × 74.4% 14.8% 0.827× 0.705× 0.926× 0.907×
DeepSeek-V3 × × × × 82.0% 7.2% 0.194× 0.060× 0.314× 0.780×
DeepSeek-V4-Flash × × × × 64.0% 10.0% 0.330× 0.171× 0.375× 0.952×
Gemini-2.5-Flash-Thinking × × × × 86.0% 22.8% 0.355× 0.099× 0.904× 0.699×
Best-of-N Sampling (N=5) ✓ × × × 80.4% 24.8% 0.909× 0.780× 1.030× 0.960×
Feedback-only Refinement ✓ ✓ × × 84.8% 49.2% 1.065× 0.955× 1.180× 1.080×
Flat Memory Retrieval ✓ ✓ ✓ × 89.6% 58.8% 1.464× 1.194× 1.917× 1.284×
KernelBlaster‡ (Reported) ✓ ✓ ✓ × 80.2% 62.8% 1.756× 1.497× 2.592× 1.110×
CudaForge‡ (Reported) ✓ ✓ × × 97.6% 70.8% 1.677× 1.448× 2.104× 1.283×
HTAM (Ours, T=6) ✓ ✓ ✓ ✓ 98.4% 84.0% 1.978× 1.532× 2.598× 1.909×

Ablation Study

On the full 250-task KernelBench suite, ablation experiments isolate the contributions of hierarchical memory organization, prefix-aware transition modeling, and multi-step search depth:

Configuration / Variant Correct↑ GeoM Spd.↑ ΔGeoM Description
HTAM (Full Method, T=6) 98.4% 1.978× 0.000× Complete proposed framework
Hierarchical Organization Ablations
w/o hierarchy structure 89.6% 1.464× -0.514× Removes coarse-to-fine structure; flat memory
w/o local memory 71.6% 0.974× -1.004× Removes strategy cards; global directions only
randomized memory 88.8% 0.812× -1.166× Injects random valid memories to test prompt length
Prefix-Aware Transition Ablations
w/o prefix \(pg_t\) 94.4% 1.683× -0.295× Omits history prefix during global direction scoring
w/o position-aware weight 95.6% 1.787× -0.191× Replaces attention recency decay with uniform average
Evolution Strategy Ablations
w/o updated memory 96.4% 1.842× -0.136× Freezes memory updates during search trajectory
1-step evolution 91.2% 1.428× -0.550× Restricts search to a single optimization step
3-step evolution 95.2% 1.756× -0.222× Restricts search to at most three steps

Key Findings

  • Local strategy cards represent the decisive bridge to code generation: Removing local strategy memories causes the largest performance degradation (-1.004× ΔGeoM), causing geometric mean speedup to drop below the PyTorch reference (0.974×) and reducing correctness from 98.4% to 71.6%. Abstract high-level concepts alone fail to guide LLMs through complex hardware-level syntax and pointer alignment.
  • Fusion workloads derive the largest acceleration: HTAM attains its highest speedup on Level-2 operator fusion tasks (2.598×), outperforming Level-1 (1.532×) and Level-3 (1.909×). Composite kernels present high memory bandwidth bottlenecks where HTAM excels by sequentially pairing Data Reuse (epilogue fusion) with Memory Access (vectorization and read-only cache promotion).
  • Extreme economic efficiency and cross-benchmark transferability: With DeepSeek-R1, the average online API cost to optimize a kernel over 6 steps is just $0.214 (totaling $53.6 for all 250 tasks), because graph routing and memory updates are computed via deterministic, zero-API rules; in cross-suite transfer on Robust-KBench, initializing HTAM with KernelBench memories boosts cold-start geometric mean speedup from 1.20× to 1.58× (+0.38× gain), with LayerNorm improving by +1.76× and RMSNorm by +1.59×.

Highlights & Insights

  • Compressing Exponential Trajectory Keys into Quadratic Pairwise Graph Edges: Instead of maintaining full optimization paths of size \(O(|V_G|^T)\) that suffer from severe sparsity, HTAM retains a compact \(O(|V_G|^2)\) edge memory while recovering full path sensitivity at inference time via attention-style recency weighting.
  • Decoupled Architecture between Deterministic Graph Routing and LLM Synthesis: Macro-level direction selection is handled by a deterministic feature-based reward function rather than costly LLM generation, reserving model context and reasoning budget strictly for translating micro-level strategy cards into hardware-compliant CUDA implementations.
  • Auditable and Robust Engineering Practices: Strategy cards provide explicit guardrails—such as 16-byte address alignment verification, scalar fallbacks, and boundary masking—which empower the system to achieve an unprecedented 98.4% correctness across diverse operator workloads.

Limitations & Future Work

  • Author-Admitted Limitations: Evaluations were primarily conducted on NVIDIA A100 GPUs within KernelBench and Robust-KBench under fixed search budgets; extensive sweeps across alternative hardware targets (such as AMD ROCm or Apple Metal) and different decoding hyperparameter configurations remain open for future work. Furthermore, verification relies on benchmark test inputs rather than formal verification, leaving open the possibility of latent numerical bugs on out-of-distribution tensor shapes.
  • Observed Constraints: In cross-benchmark transfer on Robust-KBench, the Cross-Entropy task exhibited a minor speedup degradation (-0.10×) when pre-initialized with KernelBench memory, indicating that transferring optimization priors between structurally dissimilar compute graphs can introduce negative inductive bias.
  • Future Directions: Extending the hierarchical transition graph framework to intermediate DSLs such as Triton and TileLang to provide unified cross-platform operator optimization across heterogeneous accelerator backends.
  • vs CudaForge: While CudaForge utilizes hardware performance profiling and natural language hints, it lacks fine-grained strategy cards and transition edge structures; HTAM substantially outperforms it in Fast@1 (84.0% vs 70.8%) and correctness (98.4% vs 97.6%).
  • vs KernelBlaster / Flat Memory: Flat memory banks mix coarse intents and fine code patches in an unconstrained search space, leading to retrieval noise and inefficient exploration; HTAM structures experience into a two-level HTG with transition-aware routing, achieving higher geometric mean speedup (1.978× vs 1.756× / 1.464×) at lower exploration cost.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ (Elegant two-level Hierarchical Transition Graph with attention-style edge aggregation solving the granularity mismatch and path-dependence explosion in LLM operator tuning)
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ (Rigorous evaluation across 250 KernelBench tasks, three extensive ablation groups, multi-backend API evaluations, cross-benchmark Robust-KBench transfer, and detailed token cost accounting)
  • Writing Quality: ⭐⭐⭐⭐⭐ (Clear mathematical formulation, disciplined notation, highly structured presentation, and complete auditable case studies)
  • Value: ⭐⭐⭐⭐⭐ (Provides an effective, reproducible, and economically viable architectural blueprint for autonomous AI system software optimization)