🤖 AI

Prior Knowledge or Search? A Study of LLM Agents in Hardware-Aware Code Optimization

This study demonstrates that LLM agents in hardware-aware code optimization rely primarily on pretrained priors rather than iterative feedback or agentic structures, as evidenced by their greedy behavior in black-box settings, inability to adapt to unseen kernel sizes, and performance degradation when operating with low-density intermediate representations.

Original authors: Dmitry Redko (Applied AI Institute), Albert Fazlyev (AI Talent Hub, ITMO University), Konstantin Sozykin (Applied AI Institute), Maria Ivanova (YSDA, Applied AI Institute), Evgeny Burnaev (Applied AI

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dmitry Redko (Applied AI Institute), Albert Fazlyev (AI Talent Hub, ITMO University), Konstantin Sozykin (Applied AI Institute), Maria Ivanova (YSDA, Applied AI Institute), Evgeny Burnaev (Applied AI Institute), Egor Shvetsov (Applied AI Institute)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Smart" Chef vs. The "Search" Chef

Imagine you are trying to find the perfect recipe for a cake. You have two different chefs working for you:

Chef A (The Black-Box Optimizer): This chef has never baked a cake before. They have a notebook where they write down every attempt, taste the result, and use math to decide exactly where to tweak the recipe next. They are purely logical and adaptive.
Chef B (The LLM Agent): This chef is a world-famous expert who has read millions of cookbooks. They know how to bake a cake without needing a notebook. However, they don't "learn" new things while you are talking to them; they just remember what they read in their books and try to fit your current request into those memories.

This paper asks a simple question: When trying to solve a hard problem, is it better to rely on the chef's massive memory (Prior Knowledge) or their ability to search and adapt based on feedback (Search)?

The researchers tested this by asking these chefs to write computer code (specifically, code that makes graphics cards run faster). Here is what they found.

Finding 1: The "Greedy" Chef

The Experiment: They asked the chefs to find the lowest point in a foggy valley (a classic math problem).
The Result: The LLM Chef (Chef B) acted like a greedy hiker. Once they found a spot that felt slightly lower than where they started, they stopped looking around. They just took small steps downhill from that one spot, convinced it was the bottom. They rarely wandered off to explore other parts of the valley.
The Analogy: Imagine you are looking for a lost key in a dark room. A smart search algorithm would sweep the whole room systematically. The LLM Chef, however, finds a spot that might be the key, and then just pokes around that specific spot for hours, ignoring the rest of the room.
The Takeaway: LLMs are terrible at exploring new territory. They are great at refining what they already know, but they get stuck easily.

Finding 2: The "One-Size-Fits-All" Hat

The Experiment: They asked the chefs to write code for different sizes of data (like a small photo vs. a huge 4K video). They explicitly told the chef, "This is for a tiny photo!"
The Result: The LLM Chef ignored the size instruction. They wrote the exact same code for the tiny photo as they did for the huge video. It was as if the instruction "make it small" was invisible to them.
The Analogy: Imagine a tailor who has made millions of suits. You ask them to make a suit for a 5-year-old child. Even though you tell them, "This is for a child," the tailor pulls out their standard adult pattern and makes a giant suit anyway. They are so used to making adult suits (their "prior knowledge") that they can't imagine making a child's suit, even when you tell them to.
The Takeaway: The LLM's memory is so strong that it overrides your specific instructions. It defaults to what it has seen most often, regardless of the actual problem size.

Finding 3: The "Language Barrier" Feedback Loop

The Experiment: They set up a system where the chef writes code, a computer tests it, and then gives feedback like, "This crashed," or "This is too slow." The chef then tries again.
The Result:

Scenario A (CUDA - Common Language): The chef was asked to write code in CUDA, a language they have read millions of times in their training data. With every piece of feedback, the chef got better and better. The code improved steadily.
Scenario B (TVM IR - Rare Language): The chef was asked to write code in TVM IR, a language they have rarely seen (like finding a needle in a haystack). With every piece of feedback, the chef actually got worse. The more they tried to fix it based on feedback, the more broken the code became.
The Analogy:
CUDA: You are talking to a native speaker. When they make a mistake and you correct them, they understand immediately and fix it.
TVM IR: You are talking to someone who barely knows the language. When they make a mistake and you correct them, they get confused, misinterpret your correction, and make a bigger mistake. They don't have enough "prior knowledge" of the language to understand the feedback.
The Takeaway: Feedback only works if the AI already knows the language well. If the AI is unfamiliar with the topic, feedback confuses it and makes things worse.

The Final Verdict

The paper concludes that LLMs are not "search engines" or "problem solvers" in the way we hope. They are pattern matchers.

They rely heavily on what they have already memorized (their "prior").
They are bad at exploring new ground on their own.
They cannot learn from feedback if the feedback is about something they haven't seen before.

The Solution?
If you want an AI to optimize code or solve hard problems, you can't just let it "chat" and try again. You need to wrap it in a system that forces it to explore (like a search algorithm) or retrieve specific examples it hasn't seen before. You cannot rely on the AI's "agentic" ability to figure it out on its own.

In short: The AI is a brilliant librarian who knows every book in the library by heart, but if you ask it to write a book about a topic that isn't in the library, it will just hallucinate a story based on books that are there, even if you tell it to be different. It needs a human (or a search tool) to guide it when the library runs out of answers.

Technical Summary: Prior Knowledge or Search? A Study of LLM Agents in Hardware-Aware Code Optimization

Problem Statement

Large Language Models (LLMs) are increasingly deployed as autonomous discovery systems that operate via a "propose-evaluate-revise" loop, mimicking black-box optimization (BBO). While successful in domains like extremal combinatorics and scientific equation discovery, it remains unclear which components of these agents contribute most to performance and when exploration fails. Specifically, it is difficult to determine whether LLM agents succeed due to their ability to adapt via context conditioning (feedback) or because they rely heavily on pretrained priors. This paper investigates the breakdown points of LLM-based discovery by contrasting them with classical BBO methods and analyzing their behavior under varying prior densities and distribution shifts.

Methodology

The authors conduct three controlled experiments to isolate the effects of prior knowledge versus feedback mechanisms:

Pure Black-Box Optimization (BBO):
- Setup: LLMs (gpt-oss-120b, DeepSeek-V3.2) are tasked with minimizing unknown functions (synthetic, physical dynamical systems, and BBOB benchmarks) without access to code priors.
- Baselines: Compared against CMA-ES, a hybrid Centaur system (CMA-ES + LLM), and LLM-enhanced Monte Carlo Tree Search (MCTS).
- Metrics: Evaluated on convergence speed (best step), exploration breadth (coverage), and trajectory consistency (normalized trajectory length).
- Analysis: The study probes whether LLMs explore or merely refine locally by examining their decision-making after the initial random sampling phase.
Zero-Shot Kernel Generation (Shape Conditioning):
- Setup: LLMs generate GPU kernels (Softmax, Matmul, Convolution) for varying input tensor sizes.
- Variables: The study manipulates the explicitness of size instructions (implicit vs. explicit prompts) and sampling temperatures ( $T \in \{0.1, 0.5, 0.8\}$ ).
- Goal: To determine if LLMs can adapt hardware-level parameters (tiling, block size) to specific input dimensions or if they collapse to a fixed prior.
Iterative Feedback-Loop Optimization:
- Setup: LLMs optimize kernels through iterative feedback loops involving compilation errors and performance profiling.
- Variables:
  - Representation Language: Contrasting CUDA (high density in pretraining data) with TVM Intermediate Representation (IR) (low density, ~100x less frequent).
  - Size Regime: Benchmark-native sizes vs. small-input sizes (distribution shift).
- Baselines: Compared against TVM MetaSchedule (a prior-free BBO approach) and torch.compile.
- Agents: Two pipelines were tested: a "Sampling Agent" (parallel generation with aggregated feedback) and a "Feedback Loop" (sequential refinement with an advisor/diagnoser).

Key Contributions and Findings

1. LLMs as Greedy Optimizers in Pure BBO

In pure black-box optimization tasks where no strong code prior exists, LLMs behave as greedy local refiners rather than explorers.

Behavior: LLMs anchor their proposals to the best solution seen so far, attempting to mimic gradient descent even when no gradients exist. They fail to explore the search space effectively in higher dimensions (e.g., BBOB-5D), losing to CMA-ES and hybrid Centaur systems.
Evidence: Trajectory analysis shows low coverage and high directional consistency (linear paths), indicating a lack of global exploration. Chain-of-thought analysis confirms models justify local perturbations using gradient-like heuristics.
Implication: LLMs require explicit orchestration (e.g., MCTS or hybrid state updates) to escape local optima; they do not naturally perform broad exploration.

2. Prior Collapse in Kernel Generation

In zero-shot kernel generation, LLMs exhibit prior collapse, producing size-agnostic solutions regardless of explicit input dimensions.

Observation: Whether prompted with explicit size instructions or not, models converge to the same fixed set of kernel parameters (e.g., block size, tile size) across all input sizes and temperatures.
Consequence: This leads to significant performance degradation under distribution shift. For small input sizes, the fraction of accelerated kernels drops from 59% to 31% for LLMs, whereas the prior-free TVM MetaSchedule improves from 41% to 69%.
Conclusion: The pretrained prior overrides prompt conditioning; the model cannot map requested shapes to specialized hardware configurations if those specific mappings are not strongly represented in its training data.

3. Representation-Dependent Feedback Loops

The efficacy of iterative feedback is strictly determined by the density of the prior over the target language.

CUDA (Dense Prior): Feedback loops improve performance monotonically. The model's strong prior over CUDA allows it to effectively incorporate compiler errors and profiling data to refine solutions.
TVM IR (Sparse Prior): Feedback loops cause performance to degrade. Because the prior over TVM IR is weak, the model cannot interpret feedback to generate valid schedules, leading to a decline in both compilation success and speedup over iterations.
Size Shift: Under small-input distribution shifts, the LLM agent loses to TVM MetaSchedule. The LLM's size-specific biases (calibrated to benchmark-native shapes) become misleading, while MetaSchedule adapts freely.

Significance and Claims

The paper argues that the central variable in agentic optimization is not the existence of feedback, but whether the feedback can be absorbed by the model's prior.

Prior vs. Search: LLMs are strong prior exploiters but weak open-ended searchers. They excel when the target solution space is densely covered by their pretraining data (e.g., standard CUDA kernels) but degrade when the task requires genuine exploration or operates in low-density domains (e.g., TVM IR, small input sizes).
Design Implications: Robust optimization pipelines should be adaptive:
- Use LLM refinement where prior coverage is dense.
- Rely on task-adaptive search (like BBO) when distribution shifts occur or priors are sparse.
- Hybrid approaches that combine LLM-guided proposals with structured search or retrieval are necessary to compensate for the limitations of context-only adaptation.

The authors conclude that current agentic pipelines often fail to attribute performance to specific factors because they conflate context manipulation with search. By isolating these factors, the study exposes fundamental failure modes: greedy local search in the absence of priors, and the inability to condition on novel constraints when the prior is sparse.