LLM-Guided Evolutionary Program Synthesis for Quasi-Monte Carlo Design¶
会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=6L8fgclOTS
代码: https://github.com/hockeyguy123/openevolve-star-discrepancy
领域: 代码智能 / LLM 科学发现 / 拟蒙特卡洛
关键词: 程序合成, 进化搜索, 低偏差点集, 星偏差, Sobol 序列, AlphaEvolve
一句话总结¶
把两个困扰数十年的拟蒙特卡洛（QMC）设计问题——构造低星偏差有限点集、挑选 Sobol' 方向数——重新表述为"程序合成"任务，用一个 LLM 充当智能变异算子的进化循环来搜索生成代码，不做任何针对性训练就重现了已知最优解、并在多个有限规模和高维金融定价场景上刷新了人类手工设计的最好成绩。
研究背景与动机¶
领域现状：高维数值积分是科学计算的基石，标准蒙特卡洛受限于中心极限定理只有 \(O(N^{-1/2})\) 的收敛率，而 QMC 用确定性的高均匀点集替换伪随机采样，靠 Koksma–Hlawka 不等式 \(\left|\int_{[0,1]^d} f\,du - \frac{1}{N}\sum_i f(x_i)\right| \le V(f)\cdot D_N^*(P)\) 把误差界压低——点集的星偏差 \(D_N^*\) 越小，积分越准。
现有痛点：怎么造出星偏差最小的点集是个组合复杂度极高的问题，数学规划只在 2D 的 \(N\le21\)、3D 的 \(N\le8\) 范围内证明了最优，更大的 \(N\) 基本是开放的。无限序列那边，Sobol' 序列的质量高度依赖一组叫"方向数"的整数参数，Joe–Kuo (2008) 通过海量计算搜索给出了一套通用基准，但它优化的是二维投影的 t-value，未必对具体下游积分任务最优。
核心矛盾：传统数论构造（Halton/Sobol'）保证渐近均匀但在有限 \(N\) 下并非最优；基于优化的方法（数学规划、GNN 的 MPMC）能直接优化坐标却只能对固定的 \((N,d)\) 一次性求解，换个规模就要从头重算，且不易随机化、难扩展到高维。
本文目标：验证 LLM 驱动的进化程序搜索能不能成为计算数学中"发现"的新范式——既能在已知最优处复现经典设计，又能在有限结构起作用的地方改进它。
核心 idea：把数学对象的构造当成代码进化问题 —— 不直接优化坐标，而是让 LLM 当变异算子去改写"生成点集/方向数的 Python 程序"，用偏差/MSE 作为适应度反馈来驱动选择，复用开源的 OpenEvolve（AlphaEvolve 的开源实现）做调度。
方法详解¶
整体框架¶
方法建立在 OpenEvolve 之上，把搜索表述为对"一群能生成数学构造的程序"的进化搜索：每个个体是一段 Python 代码，LLM（Gemini 2.0 Flash，温度 0.7、top-p 0.95，全程不训练不微调）作为变异算子改写核心函数，适应度函数返回一个标量分数。整套循环按"初始化 → 评估 → 选择与提示 → 变异生成 → 入群迭代"五步滚动，种群规模 60、分成四个岛环形迁移、约 2000 次 LLM 调用一轮。
flowchart LR
A[初始种群<br/>经典构造种子] --> B[执行程序<br/>得到候选点集/方向数]
B --> C[适应度评估<br/>1/(1+D*) 或 1/(1+MSE)]
C --> D[选择高分父代<br/>+岛屿/精英归档]
D --> E[构造提示<br/>父代源码+分数+灵感程序]
E --> F[LLM 变异<br/>改写生成代码]
F --> B1. 把构造与调参都编码成"会跑出数字的程序"：两个看似不同的问题被统一进同一框架。点集问题里，程序是一个 construct_star() 函数，直接返回 \(N\times d\) 的坐标数组；Sobol' 问题里，程序是一个返回字典列表的函数，每个字典装一个维度的 Sobol' 参数 \((s, a, m_i)\)。关键在于适应度始终是"跑一段短脚本就能算出来的廉价确定量"——点集用 \(\frac{1}{1+D_N^*}\)，方向数用 \(\frac{1}{1+\text{MSE}}\)，因此不需要 RL 训练，光靠程序空间里的搜索加数值信号就能推动进化。星偏差 \(D_N^*\) 按坐标诱导网格扫描极值锚盒精确计算，复杂度 \(O(N^{d/2+1})\)。
2. 两阶段策略平衡"广探索"与"精打磨"：点集发现刻意分两步走。Phase I 直接构造让 LLM 写"显式生成 \(N\) 点集"的代码，2D 从一个平移 Fibonacci 格点起步、3D 从打乱的 Sobol' 序列起步，鼓励模型遍历各种构造性启发式；跑够迭代后切到 Phase II 迭代优化，提示 LLM 改写出"用 scipy.optimize.minimize 之类数值例程精修初始猜测"的代码，把搜索从"找显式公式"转成"直接优化坐标"。\(N=16\) 的例子很说明问题：初始 Fibonacci 格点偏差 0.0962，Phase I 经 243 次迭代微调最优平移降到 0.0924，Phase II 用"抖动 Fibonacci 初值 + 带随机重启的 SLSQP"进一步压到 0.0744，距已知最优 0.0739 仅差 0.68%。
3. 用岛屿模型 + 精英归档维持多样性、鼓励交叉：种群被切成四个岛排成环形拓扑（每岛 15 个程序），每 25 次迭代做一次迁移——各岛一个精英顺时针送出、替换目标岛最差个体；此外维护一个全局精英归档同时供父代选择和构造 LLM 上下文。变异时以 0.7 概率从精英归档采父代、0.3 概率从岛内采，提示里还会塞进其他高分"灵感程序"的代码鼓励交叉。这套结构让进化比反复 one-shot 提示更稳：\(N=100\) 上对 16 个种子，进化搜索（两种 LLM 都行）方差远小于纯提示基线。
4. 把"为什么 LLM 不是只在调 SLSQP"做成对照实验：一个自然质疑是 Phase II 是不是纯粹靠 scipy 做坐标局部优化、LLM 没贡献。作者直接用 SLSQP 在 Sobol' 点集、Fibonacci 格点、最佳 Phase I 集上跑同样目标和迭代预算做基线——这些基线确实大幅改进各自种子，但 LLM 进化出的 Phase II 程序在 24 个测试 \(N\) 中的 22 个仍取得更低偏差，相对纯 SLSQP 最多再降 15%，说明增益来自 LLM 发现的非平凡初始化和重启策略，而非 SLSQP 本身。
实验关键数据¶
主实验表格¶
2D 星偏差对比（部分 \(N\)，越低越好，加粗为最优）
| \(N\) | Fibonacci | MPMC | LLM | Clément（\(N\le20\) 证明最优） |
|---|---|---|---|---|
| 16 | 0.1486 | 0.0768 | 0.0745 | 0.0739 |
| 20 | 0.1188 | 0.0640 | 0.0611 | 0.0604 |
| 40 | 0.0638 | N/A | 0.0331 | 0.0332 |
| 50 | 0.0531 | N/A | 0.0278 | 0.0280 |
| 60 | 0.0442 | 0.0273 | 0.0234 | 0.0244 |
| 100 | 0.0275 | 0.0188 | 0.0150 | 0.0193 |
\(N\le10\) 完全复现已知最优；\(N\ge40\) 起反超此前文献最好值，\(N=100\) 把 0.0188 改进到 0.0150。3D 上 \(N=1,2,3,5,6,7\) 匹配已知最优，并对 \(N>8\) 给出超出证明范围的新最好基准；2D 一路造到 \(N=1020\) 都比已报道值更低。
Sobol' 方向数 → Asian 期权 rQMC MSE（32 维，对比 Joe–Kuo，部分场景）
| \(N\) | Sobol(JK) | LLM | p-value | 场景 |
|---|---|---|---|---|
| 8192 | 4.52e-05 | 4.10e-05 | 7.0e-06 | 训练样例 |
| 8192 | 1.17e-04 | 1.07e-04 | 1.0e-06 | Out-of-Money |
| 8192 | 5.66e-04 | 5.32e-04 | 0.0156 | 高波动率 |
| 1024 | 0.00146 | 0.00131 | 3.5e-08 | At-the-Money |
LLM 只改了维度 4、5、6 的参数（其余 32 维全保留 Joe–Kuo），在 \(N\ge512\) 时按单边 Wilcoxon 符号秩检验 + FDR 校正显著降低 MSE；对比 LatNetBuilder 数字网，六种 Asian 型 payoff 在 \(N\le1024\) 上常以 2–10 倍优势更低。
消融实验表格¶
| 消融维度 | 设置 | 结论 |
|---|---|---|
| 初始化来源 | Joe–Kuo 暖启动 vs 随机方向数初始化 | 随机初始化在多数 \(N\) 上仍劣于 Joe–Kuo，说明搜索是在强领域先验上精修而非从零求解 |
| LLM 规模 | Gemini Flash vs Flash-Lite | 两者在 \(N\gtrsim2048\) 上对 Joe–Kuo 取得相近 MSE 降幅 |
| 进化 vs 提示 | 完整进化 vs one-shot / 多轮提示 | 进化在 16 个种子上偏差更低、方差远更小 |
| Phase II vs 纯优化 | LLM 进化 vs 直接 SLSQP 基线 | 24 个 \(N\) 中 22 个 LLM 更优，最多再降 15% |
关键发现¶
- 泛化性：进化出的方向数迁移到 Lookback、Basket、Bermudan 等多种高维 exotic 期权（\(N\ge512\)）依旧显著更优，唯一例外是高度不连续的 Barrier 期权——评出这是"问题相关的 Sobol' 设计"，平滑路径依赖积分受益、强不连续积分无效甚至略损。
- 计算成本：单个 Sobol' 实验约 2000 次 LLM 调用、约 \(1.6\times10^{10}\) 次 32 维 QMC 采样与 payoff 评估，CPU 工作站约 96 小时；但属一次性离线成本，得到的方向数可跨任务反复复用。
亮点与洞察¶
- 统一表述的优雅：把"造点集"和"调 Sobol' 参数"两个数论老问题都收进同一个"程序合成 + 进化"框架，差别仅在程序输出和适应度，方法论上极简。
- 相比直接坐标优化的结构性优势：输出的是定义整条 Sobol' 序列的方向数而非固定 \((N,d)\) 的坐标，天然支持任意 \(N\) 可扩展、渐进式积分（加点复用旧计算）、标准随机化（Owen 打乱得无偏估计）和高维适用，这些是 MPMC/数学规划这类固定点集方法结构上缺失的能力。
- 诚实的对照设计：专门做 SLSQP-only 基线和随机初始化消融，把"LLM 到底贡献了什么"量化清楚——结论是"在强先验上做非平凡精修"，没有夸大 LLM 从零发现的能力。
局限与展望¶
- 每问题仅一次进化运行：受算力限制，每个问题只跑了一轮进化，虽用配对符号秩检验量化显著性并报告全部种子，但作者自认这是统计上的局限。
- 不连续积分无改进：进化方向数只对平滑、低-中变差的路径依赖积分有效，对 Barrier 这类强不连续 payoff 不帮忙甚至略有损害。
- 方法论上无新算子：贡献是经验与概念性的——证明通用 LLM 程序搜索近乎开箱即用就能复现并微改长期研究的 QMC 构造，并未引入新的进化算子。
- 展望：探索更优提示技巧、进化超参优化，以及"元模型"方法——给定任意维度 \(d\) 或点数 \(N\) 直接生成最优方向数/点集。
相关工作与启发¶
- 经典构造与优化：Halton/Hammersley/Sobol' 数论序列、Clément 等的数学规划（证明最优但仅小实例）、遗传算法/阈值接受等启发式，以及 Rusch 等用 GNN 直接优化坐标的 MPMC——本文与 MPMC 的根本差异在于"程序合成"而非"坐标优化"。
- Sobol' 参数优化：Joe–Kuo (2008) 的标准方向数、面向图形学投影性质的改进、以及 LatNetBuilder 对格规则/数字网的通用搜索。
- LLM 科学发现：直接受 AlphaEvolve（LLM + 进化做算法发现，已攻下矩阵乘法、开放数学猜想）启发，用 OpenEvolve 实现；并讨论了 ShinkaEvolve 等更工程化的后续系统——但因本文适应度是廉价确定量，朴素的 OpenEvolve 已够用。
- 启发：当一个搜索问题的"解可以写成短程序、且评估廉价确定"时，"让 LLM 进化代码 + 数值适应度"可能是比专门训练模型更省事、更可迁移的发现范式；同时"暖启动于强人类先验再精修"往往比从零搜索更稳。
评分¶
- 新颖性: ⭐⭐⭐⭐ — 不在算法层创新（沿用 AlphaEvolve/OpenEvolve），但首次把 LLM 程序合成系统性用到 QMC 设计、并统一两个经典问题，视角新颖。
- 实验充分度: ⭐⭐⭐⭐ — 2D/3D 点集 + 六类 Asian 场景 + 多种 exotic 期权泛化 + SLSQP/随机初始化/模型规模/进化 vs 提示多组消融，配对显著性检验扎实；扣分在每问题仅一次进化运行。
- 写作质量: ⭐⭐⭐⭐ — 背景、方法、对照实验逻辑清晰，对"LLM 究竟贡献什么"的讨论尤其诚实。
- 价值: ⭐⭐⭐⭐ — 刷新多个有限-\(N\) 星偏差基准、给出可复用且可随机化的改进 Sobol' 方向数，对高维数值积分实务有直接价值，也为"LLM 进化做计算数学发现"提供了有说服力的案例。