Automated Kernel Discovery Towards Understanding High-Dimensional Bayesian Optimization¶
会议: NeurIPS 2026
arXiv: 2605.20249
OpenReview: https://openreview.net/forum?id=s7NsKU2IcH
代码: https://github.com/99yty/KernelDiscovery
领域: 优化/理论
关键词: 高维贝叶斯优化、高斯过程、核函数发现、大语言模型、进化算法
一句话总结¶
本文提出基于大语言模型进化搜索的高维贝叶斯优化核函数发现框架 Kernel Discovery，通过“数学形式提案 + 代码转换”的两阶段生成与留一连续排位概率评分（LOO-CRPS）防过拟合准则，突破预设组合与上下文长度限制，在 5 项高维基准上斩获 1.2 的平均名次并揭示非平稳与几何形变核的有效机理。
研究背景与动机¶
高维黑盒优化在机器学习超参数调优、神经架构搜索、生物分子序列设计以及高自由度机器人连续控制等关键问题中广泛存在。作为求解黑盒优化问题的黄金范式，贝叶斯优化依赖高斯过程代理模型在已观测样本上构建后验分布，并通过最大化采集函数迭代推荐下一批待评测点。然而，当输入维度攀升至数百乃至数千维时，采样点在高维空间中极度稀疏，传统各向同性或各向异性核函数面临严重的维度灾难，极易诱发采集函数向搜索空间边界过探索（boundary-seeking behavior），导致代理模型退化与优化停滞。
早期的高维贝叶斯优化方法主要依赖强结构假设，如加性分解模型、低维活性子空间投影或稀疏轴对齐假设。这些先验在合成函数上表现良好，但在真实的工程与控制问题中往往难以契合。近期多项经验研究表明，在合适的维度缩放长度尺度先验下，基础 RBF 或 Matérn 核能匹敌复杂的专用方法；而 BOCK 的圆柱坐标分解与 SL 的超球面立体投影等输入形变技术更在真实高维基准上大幅超越复杂基线。然而，这类优质核函数与几何变换的设计完全依赖领域专家极其繁重的试错与手工工程，未能形成系统化的自动化探索机制。
大语言模型（LLM）蕴含深厚的先验数学知识与跨领域推理能力，为算法与启发式规则的自动发现提供了新契机。然而，直接将 LLM 引入高维贝叶斯优化核设计面临双重瓶颈：一是表达力瓶颈，既有自动核搜索（如 CAKE）将搜索空间局限在基础核的加法与乘法组合，无法发现新型非线性输入形变与特征映射结构；二是接口与上下文瓶颈，端到端 LLM 优化器或传统核演化方案依赖输入历史观测数值，而在维度高达数百数千、评估达到千步的高维设定下，原始浮点数序列迅速超出上下文窗口，且模型难以从长串密集数字中提取几何规律。本文的核心 idea 是：完全解耦观测数值与结构搜索，通过两阶段（数学符号推导→可执行代码转换）LLM 进化管线探索无约束的有效核空间，并配合留一连续排位概率评分（LOO-CRPS）准则防范过拟合。
方法详解¶
整体框架¶
Kernel Discovery 围绕种群进化与双阶段 LLM 协同展开。算法在初始阶段引入适配高维特性的基础核种群；在每一轮贝叶斯优化中，系统并行执行探索性的“数学发现（Discovery）”与利用性的“组合演化（Composition）”生成候选核。所有候选核在进入种群前必须通过严格的维度无关动态执行与 Cholesky 正定性校验。随后，算法利用当前黑盒观测样本，以对内样本过拟合具有强免疫力的留一连续排位概率评分（LOO-CRPS）为准则，从种群中筛选出最优核函数用于拟合高斯过程、优化采集函数 LogEI 并采样真实目标值。根据目标函数值的真实增益执行淘汰机制，并保留 Top-\(N\) 优势核进入下一轮迭代。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["初始化高维特征核种群 P0<br/>RBF / Matern52 / RQ / BOCK / SL"] --> B["阶段1：两阶段 LLM 核发现与组合<br/>数学公式演绎 -> 形式化代码转换"]
B --> C["阶段2：自动化正定性与维度无关校验<br/>动态张量形状广播 + Cholesky 分解验证"]
C -->|验证通过| D["阶段3：基于 LOO-CRPS 的稳健核选择<br/>解析解单次求逆评估分布校准度"]
D --> E["高斯过程拟合与 LogEI 优化<br/>向目标黑盒提交真实采样点"]
E --> F["阶段4：基于实际增益的种群淘汰与截断<br/>未提升则剔除，保留 Top-N 优质核"]
F -->|未达评估预算| B
F -->|用尽预算| G["输出全局最优解 x*"]关键设计¶
1. 两阶段数学驱动与可执行代码转换机制：攻克代码级功能冗余与接口瓶颈
直接让 LLM 编写核函数 Python 代码时，模型极易产生“表面语法各异、数学实质完全相同”的伪多样性变体（例如将 x - y 替换为 x.sub(y)、重命名内部变量或将相同的指数多项式拆写）。为突破这一表达力困境，本文将核生成解耦为两阶段：第一阶段由推导大模型根据种群中已有核的纯数学表达式生成全新的非线性数学公式 \(m_{\text{new}} \sim \mathcal{M}(\{m_i\}_{i=1}^N; \rho_{\text{disc}})\)， prompt 中注入高维贝叶斯优化专家先验，要求设计能规避边界聚集的高维输入变换与正定核结构；第二阶段由专门的代码生成大模型将数学形式转换为严格符合 GPyTorch 规范的类代码 \(c_{\text{new}} \sim \mathcal{M}(m_{\text{new}}; \rho_{\text{conv}})\)。更关键的是，prompt 仅输入先前的数学符号形式，完全不注入任何原始样本点数值 \((\mathbf{x}, y)\)，从根本上消除了高维海量浮点数据击穿上下文窗口和上下文语义干扰的弊端。
2. 严格的维度无关动态执行与正定性验证器：保障计算图稳健性
由大模型生成的核函数极易在工程细节与数学有效性上出错。算法构建了组合校验器 \(\mathcal{V}(k) = \mathcal{V}_{\text{agn}}(k) \wedge \mathcal{V}_{\text{psd}}(k)\)。在维度无关性检验 \(\mathcal{V}_{\text{agn}}\) 中，代码将在不同批量、不同空间维度以及自协方差矩阵 \((N, D)\) 与长方形交叉协方差矩阵 \((N_1, D) \times (N_2, D)\) 下进行前向执行测试，严防硬编码维度、错误提取主对角线或无法支持广播的实现（如引入恒等矩阵正则项导致的矩形协方差形状不匹配）；在半正定检验 \(\mathcal{V}_{\text{psd}}\) 中，利用随机合成点计算 Gram 矩阵并进行加轻微抖动的 Cholesky 分解，拦截破坏正定性的非线性距离形变或振荡项。此外，在真实数据集上拟合时间超过 60 秒的超慢核也会被超时机制熔断剔除。
3. 基于留一连续排位概率评分的稳健核选择准则：防范高维过拟合
高维小样本场景下，常规的高斯过程边际对数似然（MLL）准则倾向于偏好极度复杂、拟合能力过强的核，从而陷入内样本过拟合并破坏外推预测的置信度校准。本文引入连续排位概率评分（Continuous Ranked Probability Score, CRPS），度量预测分布与真实标量值的全分布误差：
为避免在训练集上重新拟合的开销与内样本偏差，算法结合高斯过程的留一分析（Leave-One-Out）解析恒等式，仅需对协方差矩阵 \(\mathbf{K}_k\) 进行一次求逆，即可求出剔除第 \(i\) 个样本后的后验均值 \(\mu_{-i} = y_i - [\mathbf{K}_k^{-1}\mathbf{y}]_i / [\mathbf{K}_k^{-1}]_{ii}\) 与后验方差 \(\sigma_{-i}^2 = 1 / [\mathbf{K}_k^{-1}]_{ii}\)，进而定义 LOO-CRPS 准则：
在极端超高维基准（如 Humanoid, \(D=6392\)）上，进一步结合 BIC 惩罚构建 \(\text{LOO-CRPS-BIC}\)，有效遏制超参数量爆炸的退化核。
4. 基于实际增益的种群动态淘汰与演化更新：动态环境自适应
在黑盒优化过程中，随着观测数据的不断扩充，先前拟合优秀的核可能不再适用于当前全局或局部曲率。算法设置了淘汰逻辑：新生成的核若在当前轮选出且未能刷新全局最优值 \(y^*\)，则判定失效并立即从种群剔除；初始基础核拥有耐受阈值 \(P=3\) 次失败保护。若种群出现全员淘汰的空集状态，系统将触发自动重置回到 \(\mathcal{P}_0\)。通过每轮对候选池计算 LOO-CRPS 截断保留最优的 \(N\) 个个体，保持种群高质恒定。
完整示例 / 训练策略¶
以 SVM 基准（\(D=388\)）发现的典型优质核 \(k_{\text{discover}}\) 为例，其数学结构展示了跨类别组合机制：
其中 \(k_{\text{tanh-Poly}}\) 对 ARD 缩放后的特征应用有界投影 \(\mathbf{h}_{\tanh}(\mathbf{x}) = \tanh(\sigma (\mathbf{x} \oslash \boldsymbol{\ell}))\)，再计算 2 阶多项式内积 \(\sum_{n=0}^2 w_n (\mathbf{h}_{\tanh}(\mathbf{x})^\top \mathbf{h}_{\tanh}(\mathbf{x}'))^n\)；外层乘积则通过 Matérn-5/2 保证局部二阶连续平滑。优化流程采用批大小 \(q=20\)，初始样本集 \(|\mathcal{D}_0|=20\)（Sobol 序列生成），评测预算 \(T=1000\)（共 50 轮迭代）。每一轮从当前种群并行优化各核超参数并计算 LOO-CRPS，挑选最优核由 L-BFGS-B 执行 4 次随机重启优化 LogEI 采集函数，生成 20 个候选点送入黑盒评测。
实验关键数据¶
主实验¶
在涵盖机器人运动控制、工程结构设计、生物信息学与超参数优化的 5 项高维基准（\(D=100 \sim 6392\)）上，与单核高斯过程（7 种）、传统核搜索方法（3 种）及 LLM 驱动优化器（6 种）共 16 种竞争基线展开 4 个随机种子下的严格横向对比。
| 基准任务 | 空间维度 \(D\) | 指标方向 | 基础核最佳基线 | 搜索/LLM 最佳基线 | 本文方法 (Kernel Discovery) | 优势提升幅度 |
|---|---|---|---|---|---|---|
| Rover | \(D=100\) | 越大越好 (↑) | \(4.096 \pm 0.473\) (SL) | \(4.114 \pm 0.409\) (TROpt) | 4.353 ± 0.319 | 相比次优提升 +0.239 |
| Mopta08 | \(D=124\) | 越小越好 (↓) | \(215.77 \pm 0.57\) (Matérn52) | \(218.76 \pm 1.17\) (CompSearch) | 216.81 ± 0.87 | 显著超越其他所有搜索与LLM基线 |
| Lasso-DNA | \(D=180\) | 越小越好 (↓) | \(0.291 \pm 0.001\) (RBF) | \(0.288 \pm 0.003\) (CompSearch) | 0.286 ± 0.001 | 达成全场最低验证均方误差 |
| SVM | \(D=388\) | 越小越好 (↓) | \(0.061 \pm 0.004\) (RBF) | \(0.067 \pm 0.007\) (CompSearch) | 0.056 ± 0.003 | 错误率降至 0.056（次优为 0.061） |
| Humanoid | \(D=6392\) | 越大越好 (↑) | \(669.52 \pm 50.15\) (BOCK) | \(700.58 \pm 81.55\) (CompSearch) | 762.78 ± 72.39 | 相比最佳基线提升 +62.20 |
| 平均名次 | - | 越低越好 (↓) | 6.1 / 17 (BOCK) | 4.4 / 17 (CompSearch) | 1.2 / 17 | 位列全部 17 种方法榜首 |
消融实验¶
通过对架构各关键设计进行系统性消融，验证两阶段生成、高维基础核初始化、LOO-CRPS 评价准则及提示词引导模块的必要性（实验基于 4 个随机种子）。
| 消融配置 / 机制变体 | SVM (\(D=388\)) 最优误差 (↓) | 候选核验证失败率 (%) | 全基准平均名次 (↓) | 核心设计作用说明 |
|---|---|---|---|---|
| 完整框架 (Kernel Discovery) | 0.056 ± 0.003 | 39.5% | 1.0 / 8 | 采用两阶段生成 + 高维初始化 + LOO-CRPS 准则 |
| 直接代码生成 (Direct Code Gen) | \(0.057 \pm 0.004\) | 高度冗余 | - | 导致功能冗余，缺乏实质多样性，全任务表现落后 |
| 移除高维核初始化 (w/o Init) | \(0.071 \pm 0.011\) | - | 4.9 / 8 | 缺少 BOCK/SL 几何归纳偏置，早期样本效率严重崩塌 |
| 移除发现阶段 (w/o Discovery) | \(0.064 \pm 0.003\) | - | 5.2 / 8 | 仅能做基础核加乘组合，陷入表达力天花板 |
| 替换为 MLL 准则 (w/o Eval) | \(0.057 \pm 0.003\) | - | 4.0 / 8 | 边际对数似然倾向过度复杂的过拟合核 |
| 移除高维优化提示引导 | \(0.068 \pm 0.007\) | 35.7% | - | LLM 丧失避免边界聚集的高维启发设计 |
| 移除半正定约束提示引导 | \(0.064 \pm 0.003\) | 44.9% | - | 产出大量病态核，导致合法候选率显著暴跌 |
关键发现¶
- 两阶段解耦带来质的飞跃：余弦距离功能多样性分析表明，直接在代码空间生成核函数会导致大模型频繁进行变量更名与代数等价重写，而“数学公式推导→代码翻译”使生成核诱导的 Gram 矩阵功能余弦距离大幅增加，并在 5 个基准上全线斩获更优的优化结果。
- 拒绝原始数值上下文的必要性：传统 LLM-BO 方法（如 CAKE）将历史评估数据拼接为上下文，但在高维空间（\(D \ge 100\)）由于 token 膨胀和模式提取受阻，CAKE 的平均排名仅为 9.8，远逊于单核基线；而完全摆脱数值依赖、专注于数学结构的 Kernel Discovery 展现出压倒性优势。
- 意想不到的非平稳与几何形变核潜力：进化出的顶尖核函数普遍组合了非平稳组件（如 \(k_{\text{tanh-Poly}}\)）与多层几何输入形变（如多层 \(\arctan\) 变换与球面映射）。旅行商距离（OTSD）与边界触碰率分析表明，这些新型核在优化过程中与 RBF 同样具备聚集探索特性，完全没有发生高维下致命的边界死锁问题。
亮点与洞察¶
- “数学推导与代码实现解耦”的进化发现模式：让一个 LLM 专注于数学形式的符号创新，另一个 LLM 专注于工程严谨的代码转化。这彻底解决了代码生成模型表面语法花哨、实质数学逻辑同构的共性缺陷。
- 纯结构化推理避开海量数值输入：不向大模型传递历史观测坐标与数值，仅传递高阶数学公式表达。用最精简的上下文换取纯粹的数学归纳能力，绕过了高维输入爆 token 的物理瓶颈。
- 高阶核函数具备出色的跨任务迁移性：在 SVM (\(D=388\)) 单任务上发现的 Matérn 与 tanh-Poly/RQ 复合核，在不重新搜索的前提下直接作为固定核迁移到 Rover、Mopta08、Lasso-DNA 与 Humanoid 任务中，仍取得了超越全部原生基础核的 2.8 平均排名。
局限与展望¶
- 单轮搜索计算时延偏长：尽管采用符号上下文大大减少了 token 消耗，但每一轮迭代均需发起两次大模型 API 调用并进行多核候选评测，单轮迭代耗时约 28 秒（主要耗于 LLM API），不适用于对采样延迟极度敏感的毫秒级系统。
- 候选核拒绝率仍有压缩空间：目前 LLM 生成的核仍有约 30%~40% 因未能通过动态形状广播测试或正定性 Cholesky 校验而被直接丢弃，未来可通过更精细的少样本提示词或形式化约束语法（Grammar-guided decoding）进一步提升有效代码产出率。
- 跨基准联合发现与预训练核库：目前算法针对每个优化目标独立开启进化循环；未来可拓展为跨多任务的终身学习与联合元发现，构建面向高维贝叶斯优化的通用自适应核函数知识库。
相关工作与启发¶
- vs CAKE (Suwandi et al., NeurIPS 2025)：CAKE 将输入历史观测拼接给大模型，且搜索范围严格限制在预设基础核的加法与乘法树；Kernel Discovery 不依赖观测数值上下文，且通过自由形式数学演绎突破预设组合壁垒，发现具备有界投影与多层形变的新核。
- vs BOCK (Oh et al., ICML 2018) & SL (Doumont et al., AISTATS 2026)：BOCK 与 SL 分别人工设计了圆柱极坐标与立体投影核；Kernel Discovery 则通过演化机制自动发现了融合多层 \(\arctan\)、球面映射与非平稳多项式特征的新型复合核，性能显著超越单一人工设计的几何核。
- vs LLaMEA-BO (Li et al., 2025) & FunBO (Aglietti et al., ICML 2025)：既有工作尝试用 LLM 演化全套优化器算法或采集函数，但在高维空间极易失控退化；本文将搜索靶点精准聚焦在承载空间相关性的高斯过程核函数上，保持标准 BO 闭环稳定性，实现了高可靠性的性能增益。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ (创新性提出数学形式推导与代码转换解耦的两阶段核发现范式，成功摆脱数值上下文对 LLM 的干扰)
- 实验充分度: ⭐⭐⭐⭐⭐ (覆盖 5 项高达 6392 维的严苛基准，横向对比 16 种竞争基线并开展了详尽的消融、多样性与核演化分析)
- 写作质量: ⭐⭐⭐⭐⭐ (论文结构严谨，理论与工程实现细节交代清晰，深入探究了高维核函数抑制边界探索的数学成因)
- 价值: ⭐⭐⭐⭐⭐ (对高维黑盒优化与代理模型设计具有重大理论启发，证明了大语言模型在深层数学结构自动发现中的卓越价值)