Select Smarter, Not More: Prompt-Aware Evaluation Scheduling with Submodular Guarantees¶

会议: NeurIPS 2026
arXiv: 2604.11328
OpenReview: https://openreview.net/forum?id=lL7J1xH02I
领域: 优化/理论
关键词: 自动提示词优化, 在线评估调度, 次模优化, 项目反应理论, 自适应测试

一句话总结¶

将自动提示词优化的评估过程形式化为在线自适应考试问题，提出具有单调次模性理论保证的动态调度框架 POES，通过 IRT 区分度、设施选址覆盖度与带切换成本的有界漂移热启动更新，在削减 35%–60% Token 开销的同时显著提升提示词质量。

研究背景与动机¶

大语言模型对输入提示词的用词、格式结构与任务组织方式表现出极高的敏感性。为了减轻人工调优提示词的繁琐负担，基于黑盒编辑、文本梯度与进化搜索的自动提示词优化（Automatic Prompt Optimization, APO）应运而生。在经典的 APO 闭环中，元优化器在每个迭代轮次中生成一批候选提示词，并在下游任务的评测集上打分，筛选出表现最优的候选者作为进一步进化的基准。然而，高质量的优化严重依赖于精准的评估反馈信号，但在完整的训练集（通常包含数百乃至上千个样本）上对每一个候选提示词进行全量推理，其计算与经济成本是不可承受的。

为了平衡优化质量与开销，当前的主流实践通常在每轮优化中抽取一个大小为 $k \ll N$（例如 $k=20$）的小规模样本子集作为临时评测靶标。然而，这个评测子集应该如何演化，成为了制约 APO 性能的关键瓶颈。以 SESS 为代表的静态子集选择方法利用次模函数在优化开始前一次性挑选固定的代表性样本，虽然具备形式化理论保证，却完全脱离了提示词群体的动态演化，无法识别哪些样本能够有效区分当前最优秀的候选者；而以 IPOMP 为代表的动态启发式方法虽然随优化进度调整样本，但缺乏形式化收敛保证，且相邻轮次间样本集的剧烈抖动会导致评估信号极度不平稳，极易误导优化器的搜索轨迹。

本文的切入视角是：APO 的候选评估天然对应着心理测量学中的计算机化自适应考试（Computerized Adaptive Testing, CAT）场景——候选提示词是受测考生，训练样本是考题，调度器的核心使命绝非盲目均摊评测用例，而是在线挑选出最能区分当前头号竞争者的“高鉴别力考题”。核心 idea：将提示词评估调度建模为兼顾 IRT 区分度与设施选址覆盖度的在线次模优化问题，通过带切换成本阈值的热启动局部交换与自适应控制器，在理论上建立 $(1-1/e)$ 贪心近似界与有界漂移保证，以更精简的评估子集换取更具辨识度与稳定性的优化反馈。

方法详解¶

整体框架¶

POES 框架将 APO 的评估调度构建为一个在线组合优化闭环。在每一轮优化中，元优化器生成候选提示词群体，调度器则基于历史累积评测二元胜负矩阵，利用项目反应理论（IRT）实时拟合提示词能力值与样本难度，提取对当前两强候选最具鉴别力的区分度效用；同时结合基于 TF-IDF 相似度的设施选址覆盖度项，共同构成复合优化目标 $G_t(S)$。随后，调度器利用自适应进度控制器调节交换门槛与预算，以前一轮子集为基础执行有界漂移的热启动局部替换，最终输出规模为 $k$ 的当前评估子集用于打分，并将精准反馈回传给优化器。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：候选提示词池与历史评测结果"] --> B["IRT 区分度效用<br/>1PL 模型估计能力与难度，中间态 Fisher 信息最大化"]
    B --> C["设施选址覆盖度<br/>TF-IDF 样本相似度，双曲衰减权重防止表征塌缩"]
    C --> D["进度感知自适应控制器<br/>自动热身判定 + 停滞/提升状态调节交换阈值与预算"]
    D --> E["有界漂移热启动交换<br/>基于增益阈值的单样本替换，维持次模近似与平滑演进"]
    E --> F["输出：当前轮次评估子集 St 并反馈优化器"]

关键设计¶

1. IRT 区分度效用：自适应锁定顶尖候选的决策边界 针对静态评估无法感知提示词能力迁移、盲目随机抽样缺乏辨识度的痛点，POES 引入一参数逻辑斯蒂项目反应理论模型（1PL / Rasch Model），将提示词 $p$ 在样本 $i$ 上的做对概率建模为 $\Pr(y_{p,i}=1) = \sigma(\theta_p - b_i)$，其中 $\theta_p$ 为提示词潜在能力，$b_i$ 为样本难度参数。在优化第 $t$ 轮，系统重点关注综合能力最高的前两名提示词候选 $p_t^{(1)}$ 与 $p_t^{(2)}$，并将样本 $i$ 的区分度效用定义为两候选预测分布间的对称 KL 散度： $$u_t(i) = D_{\mathrm{KL}}^{\mathrm{sym}}\bigl(\sigma(\theta_{p_t^{(1)}} - b_i),\, \sigma(\theta_{p_t^{(2)}} - b_i)\bigr)$$ 理论分析表明，该效用展开后一阶项直接正比于候选能力中点 $\bar{\theta}_t$ 处的 Fisher 信息量：$u_t(i) = (\Delta \theta_t)^2 \cdot \mathcal{I}(\bar{\theta}_t; b_i) + O((\Delta \theta_t)^4)$。这表明挑选高 $u_t(i)$ 样本正是在最大化顶尖候选决策边界的信息增益。相较于带样本区分度参数的 2PL 模型，1PL 模型参数量紧凑，使用热启动 L-BFGS 单轮求解耗时低于 100ms，在早中期观测稀疏时能有效避免过拟合。

2. 设施选址覆盖度：双曲衰减防止子集表征坍缩 若仅仅依据区分度效用挑选样本，评估子集容易迅速向顶尖两强恰好出现分歧的特定狭隘题型聚拢（例如两个提示词仅在日期推理上分歧，调度器便会清一色选入日期题目，完全遗漏数学运算或逻辑推理），从而导致选出的提示词泛化能力受损。为此，POES 引入设施选址（Facility Location）多样性覆盖函数： $$C_t(S) = \sum_{j \in V} \max_{i \in S} s(i, j)$$ 其中 $s(i, j) = \max(0, \cos(\mathbf{v}_i, \mathbf{v}_j))$ 为样本输入与参考答案拼接后的 TF-IDF 余弦相似度，无需依赖外部重型嵌入模型。在复合目标 $G_t(S) = \sum_{i \in S} u_t(i) + \lambda_t C_t(S)$ 中，平衡系数 $\lambda_t$ 遵循双曲衰减策略：$\lambda_t = \lambda_0 / (1 + \alpha n_t)$。双曲衰减比指数衰减更为平缓，确保在 IRT 参数尚处于探索学习的前中期提供充足的代表性支撑，待提示词群体逐步收敛后再平滑过渡到高区分度细筛。

3. 有界漂移热启动交换：兼顾次模理论界与评估平滑性 如果每轮都从零开始贪心重选子集，会导致前后轮次的评估集合发生剧烈颠簸，致使提示词得分在不同子集间产生非连续波动，破坏元优化器的寻优梯度。POES 以上一轮子集 $S_{t-1}$ 为基准执行热启动更新，每轮允许至多 $B_t$ 次单样本替换（One-for-One Swap），且每次替换必须满足严格的增益阈值条件： $$G_t(S') - G_t(S) > \tau_t$$ 由于线性组合项 $\sum_{i \in S} u_t(i)$ 是模函数（Modular），而设施选址项 $C_t(S)$ 是单调次模函数，因此复合目标 $G_t(S)$ 严格保持单调次模性（Monotone Submodular）。该热启动更新具备严格理论保证：(1) 有界漂移，保证前后子集对称差满足 $|S_t \triangle S_{t-1}| \le 2 B_t$；(2) 单调递增，保证优化值至少提升 $m_t \tau_t$；(3) 局部最优性，在无法满足阈值时自动收敛至 $\tau_t$-局部最优；(4) 近似质量跟踪，在轮间漂移有界时持续维持接近 $(1-1/e)$ 的全局近似质量。

4. 进度感知自适应控制器：动态调节探索与开发平衡 为避免固定静态超参数导致的早熟或低效，POES 配备了进度感知自适应控制器与自动热身（Auto Warmup）模块。在优化前 2–3 轮，由于历史测试数据匮乏导致 IRT 估计方差较大，当区分度极值比 $\max_i u_t(i) / \bar{u}_t$ 未超过退出阈值 $\rho_{\text{exit}} = 1.05$ 时，控制器强制保持随机均匀抽样热身；一旦进入主动调度阶段，控制器实时监测最优提示词得分演进：若连续两轮出现停滞（Stagnation），则衰减阈值 $\tau_t \leftarrow 0.8 \tau_t$ 并增加交换预算 $B_t \leftarrow B_t + 1$，鼓励更激进的子集重构以跳出局部鞍点；若持续取得改进，则增大阈值 $\tau_t \leftarrow 1.2 \tau_t$ 并减小预算 $B_t \leftarrow B_t - 1$，以强化评测环境的稳定性。

损失函数 / 训练策略¶

POES 属于非侵入式的测试时评估与调度算法，不更新 LLM 基础权重。其在线学习核心在于 IRT 潜变量的最大似然估计与动态超参数约束： - IRT 在线拟合目标：每轮通过 L-BFGS 最大化累积二元打分矩阵的对数似然函数： $$\max_{\boldsymbol{\theta}, \mathbf{b}} \sum_{(p, i)} \Bigl[ y_{p,i} \log \sigma(\theta_p - b_i) + (1 - y_{p,i}) \log\bigl(1 - \sigma(\theta_p - b_i)\bigr) \Bigr]$$ - 自适应超参数截断：交换门槛截断在 $\tau_t \in [0.01, 0.30]$，交换预算限制在 $B_t \in [3, 5]$，初始覆盖系数设为 $\lambda_0 = 0.5$。

实验关键数据¶

主实验¶

论文在 36 个评测任务上展开测试，涵盖 BBH（27 项推理任务）、BigBench-IPOMP（5 项任务）以及 4 项数学基准（GSM8K、GSM-Hard、MATH、MultiArith），横跨 3 种优化器（OPRO、EvoPrompt-GA、EvoPrompt-DE）与 2 款推理大模型（Llama-3.1-8B-Instruct、Qwen-2.5-7B-Instruct），元模型统一采用 GPT-OSS-120B。

下表展示了在经典配置 OPRO × Llama-3.1-8B-Instruct 下各类基准的平均准确率（$k=20$）：

方法	BBH (27)	BigBench (5)	MMLU (57)	GSM8K	GSM-Hard	MATH	MultiArith	全局平均
Random	0.809	0.748	0.440	0.853	0.689	0.775	0.933	0.750
SESS (静态次模)	0.817	0.719	0.435	0.728	0.686	0.720	0.850	0.708
IPOMP (动态启发式)	0.833	0.758	0.455	0.907	0.667	0.767	0.892	0.754
Anchor (k-medoids)	0.798	0.709	0.442	0.892	0.727	0.735	0.783	0.727
Prediction (模型预测)	0.815	0.746	0.437	0.907	0.481	0.720	0.942	0.721
POES (本文)	0.893	0.816	0.565	0.890	0.780	0.900	0.983	0.832
相对最佳基准提升	+6.0%	+5.8%	+11.0%	–	+5.3%	+12.5%	+4.1%	+7.8%

消融实验¶

论文在五项横跨多领域的代表性任务上对核心组件进行了详尽的逐项消融：

配置	Dyck Lang.	Navigate	GSM-Hard	MATH	MultiArith	平均分	说明
完整 POES	0.900	0.890	0.754	0.900	0.983	0.885	完整系统
w/o 自动热身 (No-AutoWarmup)	0.900	0.775	0.750	0.775	0.950	0.830	早期噪声估计直接调度致剧烈掉点
w/o 设施选址覆盖度 (No-Coverage)	0.860	0.797	0.693	0.812	0.946	0.822	样本单一化导致泛化覆盖受损
w/o 自适应控制器 (No-Adaptive)	0.750	0.725	0.680	0.694	0.938	0.757	静态超参数退化严重（平均掉 12.8pp）
仅区分度+静态覆盖 (Disc+Cov)	0.790	0.855	0.722	0.739	0.992	0.820	缺乏自适应调整与热身保护

预算效率分析¶

论文对比了不同子集规模 $k$ 下的精度与 Token 消耗（在 Dyck, GSM-Hard, MultiArith, Navigate 四项基准上测试）： - 同等预算表现卓越：在常规预算 $k=20$ 下，POES 以仅高出随机抽样 6% 的计算开销（797K vs. 752K tokens），在 4 项任务上均获得第 1 名，平均准确率达到 0.955（基准方法最高仅为 0.869）。 - 小预算超越大预算：POES 在 $k=20$ 时准确率（0.875）超越自身在 $k=30$ 时的表现（0.857），同时节省 33% 的 Token；而在 $k=10$（仅消耗 478K tokens）时，平均准确率达到 0.804，几乎追平所有基准在 $k=20$ 时的平均水平（0.820，消耗 727K tokens），节省了 34% 的 Token。

关键发现¶

自适应控制贡献最为显著：消融瀑布图表明，从无自适应基线到完整 POES 的 12.8 个百分点增益中，自适应控制器贡献了 6.5 个百分点，自动热身机制贡献了 5.5 个百分点，充分印证了动态进度调节对防止优化停滞的关键作用。
越困难的任务收益越大：任务提升幅度与基准难度呈显著负相关（$r = -0.40, p = 0.016$），在 Navigate（+8.3%）与 Logical Deduction（+5.6%）等提示词敏感型硬任务上优势尤为突出。
热启动稳定性显著优于冷启动：相较于每轮从零开始重新求解次模贪心子集的冷启动，热启动局部交换在 BBH Navigate 与 BigBench Navigate 上分别取得 +9% 与 +11% 的额外提升，实测证明评测子集的平滑演化是防止优化器在噪声中迷航的必要条件。

亮点与洞察¶

将 APO 评估优雅映射为在线自适应考试：摆脱了以往启发式挑选“难样本”或“代表样本”的朴素直觉，用 1PL-IRT 建立提示词-样本交互模型，直接以两强候选决策边界处的 Fisher 信息最大化指导子集选择。
理论完备的带切换成本次模优化：首次在 APO 子集动态演进问题中引入次模性理论体系，不仅推导了单调次模性与 $(1-1/e)$ 贪心界，更证明了热启动单步交换的有界漂移与近似跟踪理论保证。
“更聪明而非更多”的计算收益法则：证明了评估质量的提升对优化轨迹具有杠杆效应，通过科学调度，$k=20$ 的紧凑子集甚至超越了 $k=30–50$ 的大子集效果，为工业级 APO 部署节省高达 35%–60% 的推理成本。

局限与展望¶

理论分析未闭环覆盖端到端收敛：当前理论证明主要作用于调度层自身的次模性、局部最优与漂移界，尚未结合黑盒 LLM 优化器本身的非凸连续/离散动力学给出端到端优化收敛性保证。
打分范式目前局限于二元判定：当前模型基于 1PL 逻辑斯蒂回归，原生支持对/错二元反馈，面对自由文本生成、开放式问答等多维连续打分或成对偏好标注场景，仍需扩展广义等级反应模型（Graded Response Model）。
超大规模训练池拓展：当训练样本池规模扩展至 $N > 1000$ 时，TF-IDF 相似度矩阵构建与全局贪心候选过滤将面临更高的内存与计算开销，需要引入分层检索或核集采样加速。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将 APO 评估调度形式化为带切换成本的在线次模自适应测试问题，视角开创且理论扎实。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖 36 项跨领域任务、3 大主流优化器、2 款开源底座模型，且包含详尽的开销分析、消融实验与超参敏感性测试。
写作质量: ⭐⭐⭐⭐⭐ 动机阐述自然流畅，数学推导完备自洽，图表信息表达清晰严谨。
价值: ⭐⭐⭐⭐⭐ 直接命中自动提示词优化落地的高成本痛点，即插即用且显著降低 35%–60% 的 Token 开销，极具实用推广价值。