🤖 machine learning

Automated Kernel Discovery Towards Understanding High-dimensional Bayesian Optimization

This paper introduces Kernel Discovery, an LLM-driven evolutionary framework that overcomes the limitations of existing automated kernel design in high-dimensional Bayesian optimization by searching a broader mathematical space without relying on raw observations, achieving superior performance with an average rank of 1.2 out of 17 on benchmarks.

Original authors: Taeyoung Yun, Woocheol Shin, Inhyuck Song, Jaewoo Lee, Jinkyoo Park

Published 2026-05-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Taeyoung Yun, Woocheol Shin, Inhyuck Song, Jaewoo Lee, Jinkyoo Park

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

Imagine you are trying to find the perfect recipe for a cake, but the kitchen has thousands of ingredients (dimensions) instead of just flour and sugar. You can't taste every possible combination because it would take forever. This is the challenge of High-Dimensional Bayesian Optimization (BO): finding the best solution in a massive, complex space with very few tries.

To solve this, scientists use a "smart guesser" called a Gaussian Process (GP). Think of the GP as a chef who builds a mental map of the kitchen based on the cakes you've already tasted. The most important part of this map is the Kernel—a mathematical rule that decides how similar two ingredients (or points in the kitchen) are to each other.

The Problem: The Chef is Stuck

For years, designing these "similarity rules" (kernels) for huge kitchens has been a nightmare.

The Manual Trap: Experts had to hand-craft these rules, which is slow and prone to error.
The "Too Much Info" Trap: Some recent attempts used AI (Large Language Models or LLMs) to help, but they tried to feed the AI all the raw data (thousands of numbers) at once. It's like trying to explain a complex recipe to a chef by shouting a list of 10,000 ingredients at them. The chef gets overwhelmed, forgets the beginning, and can't find the pattern.
The "Cookie-Cutter" Trap: Other AI methods could only mix existing rules in simple ways (adding or multiplying them), like only allowing you to mix flour and sugar but never inventing a new spice.

The Solution: "Kernel Discovery"

The authors of this paper created a new system called Kernel Discovery. They realized that asking an AI to write code directly often results in the AI just renaming variables or rewriting the same math in a different font (like saying "2+2" vs "1+1+2"). It looks different but does the exact same thing.

To fix this, they built a Two-Stage Assembly Line:

The Architect (Stage 1): First, they ask the AI to act as a mathematician. Instead of writing code, the AI proposes a new mathematical shape or formula. It's like the architect drawing a blueprint for a new type of cake pan.
The Builder (Stage 2): Then, a second AI call takes that blueprint and turns it into actual, working computer code.

This separation forces the AI to think about structure rather than just copying syntax. It allows the system to invent completely new types of "similarity rules" that humans might never have thought of.

The "Taste Test" (Selection)

Once the AI invents a new kernel, how do they know it's good?
Usually, systems pick the kernel that fits the current data perfectly. But this is like a chef who memorizes the specific cakes you've already tasted but fails to bake a new one. This is called overfitting.

The authors introduced a new "Taste Test" called LOO-CRPS.

The Analogy: Imagine the chef tastes a cake, then puts it aside and tries to guess what it tasted like without looking at it again. If the chef can still guess correctly, the recipe is robust. If the chef can only guess correctly because they memorized the specific bite, the recipe is bad.
This method penalizes kernels that are too complex or memorized, ensuring the system picks rules that actually generalize to new areas of the search space.

The Results: A New Champion

The team tested this system on five different "kitchens" (benchmarks) with dimensions ranging from 100 to over 6,000.

The Score: Out of 17 different methods (including old-school manual rules and other AI attempts), their method came in 1st place with an average rank of 1.2.
The Discovery: They found that the best kernels often involved geometric warping (bending the space like a rubber sheet) and combining different mathematical ideas in unexpected ways. For example, they found kernels that worked well even though they used "non-stationary" rules (rules that change depending on where you are in the kitchen), which was previously thought to be risky.

Summary

In short, the paper says: "Don't just ask AI to write code based on a wall of data. Instead, ask it to design a mathematical blueprint first, then build it. And don't just pick the rule that fits the past perfectly; pick the one that proves it can guess the future."

This approach allows computers to automatically invent better "maps" for solving incredibly complex, high-dimensional problems without needing a human expert to do the heavy lifting.

Technical Summary: Automated Kernel Discovery Towards Understanding High-dimensional Bayesian Optimization

Problem Statement

High-dimensional Bayesian Optimization (BO) is critical for applications such as hyperparameter tuning, neural architecture search, and biological sequence design. However, BO suffers from the "curse of dimensionality," where large distances between observations make accurate surrogate modeling difficult and lead to over-exploration of search space boundaries.

While recent works suggest that simple kernels (e.g., RBF, Matérn) with properly scaled lengthscale priors or geometric input warpings can perform well, identifying effective priors or transformations still requires extensive manual engineering by domain experts. Existing automated approaches face two primary bottlenecks in high dimensions:

Expressive Bottleneck: Current kernel search methods are restricted to additive and multiplicative compositions of predefined base kernels, limiting the discovery of novel structures suitable for high-dimensional problems.
Interface Bottleneck: Large Language Model (LLM)-based BO methods typically condition on raw observations to guide the search. In high dimensions, the sheer volume of numerical data exceeds LLM context limits and makes pattern extraction infeasible.

Methodology: Kernel Discovery

The authors propose Kernel Discovery, an LLM-driven evolutionary framework designed to automate the design of effective Gaussian Process (GP) kernels for high-dimensional BO. The framework operates through an iterative loop involving population initialization, kernel discovery, validation, and selection.

1. Two-Stage Discovery Pipeline

To overcome the limitation of LLMs generating syntactically varied but functionally identical code, the authors adopt a two-stage approach:

Stage 1 (Mathematical Formulation): An LLM is prompted to propose novel mathematical forms of kernels based on a population of existing kernels. Crucially, this stage does not condition on raw observations; instead, it relies on the mathematical reasoning capabilities of the LLM to generate structurally innovative forms. The prompt includes specific guidance on high-dimensional strategies (e.g., input projections, dimensionality scaling) and constraints (e.g., positive semi-definiteness).
Stage 2 (Code Conversion): A second LLM call converts the proposed mathematical form into executable Python code (specifically for the GPyTorch framework).

2. Population Initialization and Evolution

The process begins with an initial population ( $P_0$ ) of kernels known to be effective in high dimensions, including RBF, Matérn52, Rational Quadratic (RQ), BOCK (cylindrical kernels), and SL (spherical linear kernels).

Composition: In addition to the two-stage discovery, the framework includes a composition stage where the LLM combines top-performing kernels via addition or multiplication.
Validation: Newly generated kernels undergo two empirical checks:
- Agnostic Execution ( $V_{agn}$ ): Ensures the code runs correctly across varying input shapes and batch sizes.
- Positive Semi-Definiteness ( $V_{psd}$ ): Verifies that the kernel produces a valid covariance matrix via Cholesky decomposition.
Selection Criterion (LOO-CRPS): To select the best kernel for the next BO iteration without overfitting, the authors introduce the Leave-One-Out Continuous Ranked Probability Score (LOO-CRPS). Unlike the marginal log-likelihood (MLL), which can favor overly complex kernels that overfit current data, LOO-CRPS penalizes overconfident fits by evaluating predictive distributions on held-out data points.

3. Evolutionary Loop

At each iteration, the framework generates new candidates, validates them, and selects the kernel with the lowest LOO-CRPS to fit the GP surrogate. The acquisition function (LogEI) is then maximized to propose the next query point. The population is updated by retaining the top- $N$ kernels with the lowest LOO-CRPS, ensuring the population evolves toward more calibrated and effective surrogate models.

Key Contributions

Novel Framework: Introduction of "Kernel Discovery," the first LLM-driven evolutionary framework that searches a broader kernel space beyond simple additive/multiplicative compositions and avoids conditioning on raw high-dimensional observations.
Two-Stage Decomposition: A methodological insight that separating mathematical formulation from code generation reduces functional redundancy and encourages the discovery of genuinely novel kernel structures.
Robust Selection Metric: The proposal of LOO-CRPS as a selection criterion to mitigate overfitting in the kernel selection process, addressing a known weakness of MLL in automated kernel search.
Empirical Validation: Comprehensive evaluation on five high-dimensional benchmarks (dimensions ranging from 100 to 6,392), demonstrating superior performance over 16 baselines, including base kernels, search-based methods, and other LLM-based BO approaches.

Experimental Results

The method was evaluated on five standard benchmarks: Rover ( $D=100$ ), Mopta08 ( $D=124$ ), Lasso-DNA ( $D=180$ ), SVM ( $D=388$ ), and Humanoid ( $D=6392$ ).

Performance: Kernel Discovery achieved an average rank of 1.2 out of 17 methods across all benchmarks, significantly outperforming the runner-up, Compositional Search (rank 4.4).
Comparison with Baselines:
- It outperformed all fixed base kernels (RBF, Matérn, etc.).
- It significantly surpassed search-based methods like Greedy Search and Compositional Search, highlighting the limitation of restricting the search space to simple compositions.
- It notably outperformed LLM-based baselines like CAKE, ARM, and LMABO. The authors attribute the failure of CAKE to its reliance on raw observations as context, which degrades performance in high dimensions.
Ablation Studies: Removing any component (initialization, discovery stage, or the LOO-CRPS metric) resulted in performance degradation, confirming the necessity of the full pipeline. The two-stage approach was shown to produce more functionally diverse kernels than direct code generation.

Significance and Claims

The paper claims that automating kernel design with a system capable of mathematical reasoning can substantially reduce the barrier of manual engineering in high-dimensional BO.

Beyond Compositions: The study demonstrates that effective kernels for high dimensions are not limited to simple compositions of base kernels. The discovered kernels often involve complex geometric warping (e.g., arctan transformations) and non-stationary components that were not present in the initial population.
Insight into High-Dimensional BO: By analyzing the discovered kernels, the authors provide new insights into what drives effective surrogate modeling. They found that compositions of geometrically warped kernels and non-stationary components (like tanh-polynomials) can lead to improvements, challenging the prevailing intuition that simple kernels with scaled priors are sufficient.
Transferability: The authors show that kernels discovered on one benchmark (e.g., SVM) can transfer effectively to other benchmarks, suggesting that the discovered structures capture generalizable properties of high-dimensional optimization landscapes.

The authors conclude that while their current framework optimizes kernels per benchmark, the results suggest that LLM-driven kernel discovery is a promising strategy for high-dimensional BO, offering a path toward more expressive and automated surrogate modeling.