精读笔记

Problem Setting

《Benchmarking Bilevel Derivative-Free Optimization Algorithms》（arXiv preprint / 2026）实际处理的是 BL-DFO 的评测可信度，而不是求解器设计。问题的关键不是“如何求 bilevel problem”，而是“如何知道一个算法报告的好解是否真是 bilevel admissible”。

在 BL-DFO 中，upper-level 每提出一个 x，都要依赖 lower-level solver 生成 response y。若 lower-level 是 DFO、heuristic、local search 或 inexact oracle，则 y 很可能不是全局或足够精确的 lower-level minimizer。传统 benchmark 往往直接拿算法日志里的 F(x,y) 做比较，这等价于信任每个 y 都是 follower rational response。这个假设在 bilevel setting 中是核心漏洞。

真正的矛盾是：BL-DFO 的性能看起来取决于 upper-level search，但评测有效性首先取决于 lower-level optimality 是否成立。一个不充分的 lower-level solver 可能产生对 upper-level 非常有利但 follower 不会选择的 y，从而在 profile 中虚假领先。以前方法卡在把 single-level DFO 的 evaluation-count profiles 直接搬到 bilevel setting：它们既不挑战 admissibility，也不正确统计两层计算成本。

Motivation

作者的核心观察很尖锐：在 bilevel benchmark 中，lower-level solver 越差，有时反而越可能让算法看起来更好。因为它可能停在一个 lower-level suboptimal 的 y，而这个 y 对 upper-level objective F 很优。若 benchmark 不检查 y 是否 rational，这种点就会被当成候选最优解，导致评测偏向错误方向。

已有 BL-DFO 文献缺的是两个东西。第一，缺少独立于被测算法的 admissibility challenge；多数工作默认 lower-level response 是 exact 或足够好，即使实际是 inexact/local。第二，缺少统一的 bilevel cost metric；有的只数 upper-level evaluations，有的只数 lower-level evaluations，有的简单相加并默认两层成本相同。这些选择都会改变算法排序。

所以论文的动机不是提出更强 solver，而是修正 evaluation protocol：先确保比较对象至少没有被明显 lower-level suboptimality 污染，再用更接近真实开销的预算轴比较。

Core Idea

核心思想可以概括为：benchmark 不应信任 BL-DFO solver 自己声称的 admissibility，而应引入一个 post-hoc referee，对日志中的候选点做反证式审计。给定算法产生的点 (x,y)，referee 固定 x，重新求 lower-level problem；如果找到另一个可行的 ŷ 使 f(x,ŷ) < f(x,y) - εobj，则原点不可能是 ε-lower-level optimal，应从 benchmark 数据中删除。

这个设计的本质变化是把 bilevel benchmark 的信息流从“solver 输出 → profile”改为“solver 输出 → admissibility filter → profile”。它引入的 inductive bias 是：宁可低估算法表现，也不要奖励下层非理性点。注意 referee 不证明一个点是 admissible，它只寻找证据撤销 admissibility；这是现实 DFO setting 下更可操作的方向。

第二个核心思想是 cost reparameterization：将 upper-level 与 lower-level evaluations 用缩放因子 λ 聚合成 N = λNUL + NLL 或等价形式。这样 profiles 的横轴不再是任意单层 evaluation，而是带有相对成本假设的 total effort。它不解决 bilevel 求解，但让 benchmark 的资源度量更接近实际部署。

Method

1. Inexact admissibility formalization：作者把 feasibility、rationality、admissibility 扩展到 ε setting。它解决的是实际 lower-level solver 很少 exact 的问题；没有这个定义，referee 会过度惩罚所有近似解。核心变化是 benchmark 的 validity criterion 从 exact bilevel condition 变成可调容忍度下的 ε-admissibility。

2. Refereeing procedure：对 claimed ε-admissible point 固定 x，重新优化 lower-level；若找到 lower-level objective 更优且满足约束的 response，则撤销该点。它解决的是 solver log 不可信的问题。机制上，这是一个 falsification test，不是 certification test。

3. 三种审计粒度：End-Point 只查最终点，成本低但 myopic；Complete 查全部日志，最接近完整清洗但代价高；Reverse 从末尾往前查，试图在最终有效解与审计成本之间折中。这里真正有价值的是 Reverse 的 benchmark 工程取舍：对 profiles/accuracy 关注最终可用点时，不必全量检查轨迹。

4. Scaled computational effort：用 λ 聚合两层 evaluations，并在 data profile 中按 (nx+1)(ny+1) 预算单位归一化。它解决的是单层 evaluation count 扭曲成本的问题。核心变化是让 BL-DFO profile 的横轴显式表达“我认为 upper/lower evaluation 相对多贵”。

Key Insight / Why It Works

这篇最有价值的 insight 是：bilevel benchmark 的首要误差源不是 profile 形式，而是 admissibility contamination。只要日志中混入大量 lower-level suboptimal points，任何 performance profile / data profile 都会精确地比较错误对象。referee 有效的原因不是它更会求解 bilevel，而是它改变了 benchmark 的默认信任关系：算法不能再靠 lower-level failure 获得虚假 upper-level gain。

从机制归因看，核心贡献是 evaluation validity correction，而不是新的 optimization capability。End-Point、Reverse、Complete 的区别主要是 engineering trade-off；Reverse 被推荐，是因为在实验中接近 Complete 但便宜很多，这更像 practical benchmarking heuristic，而非理论上严格优越。

scaled effort 的贡献也更偏 benchmark calibration。它本质上不是算法创新，而是防止 evaluation axis 选择造成 ranking artifact。文中实验清楚显示，只数 NUL、只数 NLL、加权总成本会给出不同印象。这说明很多已有 BL-DFO 比较可能存在 cost-accounting bias。

需要强调：referee 的能力依赖 test-time compute 和 lower-level re-optimization 覆盖，而不是某种理论认证。它更像 adversarial validation / audit，而不是 proof。若 referee 与被测 solver 共享同类局部失败模式，过滤效果会显著下降。因此方法有效的真正条件是 referee 至少在 lower-level search 上具有足够互补性或更强预算。

Relation To Prior Work

最接近的 prior 不是某个 BL-DFO solver，而是 single-level DFO benchmarking 体系：Dolan-Moré performance profiles、Moré-Wild data profiles，以及 constrained/surrogate-assisted DFO 中的 cost/accuracy profiles。本文属于 benchmark methodology extension，而非 solver family。

和已有 BL-DFO 评测的本质区别有两个。第一，过去的 profiles 默认候选点有效；本文把 admissibility 作为可被挑战的对象。第二，过去 evaluation budget 往往任意选择 upper 或 lower evaluations；本文要求显式聚合两层成本。

看似新的部分中，profile 本身并不新，ε-inexact terminology 也主要是把已知 bilevel 概念适配到 practical setting。实质创新是把 lower-level re-optimization 作为 benchmark preprocessing，并明确指出“差 lower-level solver 可能在 benchmark 中看起来更强”这个 bilevel-specific failure mode。这个判断比具体三种 referee 策略更重要。

Dataset / Evaluation

实验使用 BOLIB 的解析 bilevel problems，并提供 Julia 版 BOLIB.jl。覆盖的是标准 analytical benchmark，而不是真实 expensive blackbox 或 noisy simulation。它适合说明 methodology 的影响，但不应被解读为该 protocol 已经在真实工业 BL-DFO 上充分验证。

evaluation 支持了两个核心 claim：referee 会显著改变算法排序；scaled effort 会改变 data profile 结论。这正是论文要证明的 benchmark sensitivity，而不是某个算法的 superiority。作者避免堆大量数字，主要用 profiles 展示趋势，这和文章定位一致。

局限也明显：BOLIB 问题通常 evaluation cost 较可控、无噪声、解析结构较强。真实黑箱中 referee 的额外成本可能远超原始 optimization；λ 的估计也可能随输入、缓存、并行化、simulation variance 改变。benchmark 是否能跨场景泛化，文中未充分说明。

Limitation

第一，referee 只能 falsify，不能 certify。未被撤销的点不等于 admissible，只是 referee 没找到反例。这一点决定了方法的上限：它提高 benchmark 下界可信度，但不提供严格 bilevel validity。

第二，方法可能把难题转移到 referee。若 lower-level global optimization 本身困难，referee 也只是另一个 heuristic solver。多个 referee 可以提高覆盖，但成本可能超过原始求解，且仍无认证。

第三，referee 设置会引入新偏置。起点选择、预算、停止准则、是否 internal/external、是否与某类算法同源，都会影响撤销率。文中讨论了这些因素，但没有给出原则性选择准则。增益来源有时可能主要来自给 referee 更多 test-time compute，而不是评测框架本身。

第四，λ 的 cost scaling 是必要但主观的。用 CPU time ratio 看似自然，但在 heterogeneous hardware、并行 lower-level solve、昂贵 simulation、随机 evaluation 下并不稳定。若 λ 选得不合理，新的 profile 仍可能偏。

第五，实验没有充分覆盖 noisy/stochastic、high-dimensional、multi-fidelity、real-world expensive bilevel cases。当前结论更像对 analytical BL-DFO benchmark 的方法学警告，而不是完整 deployment protocol。

Takeaway

• 1. BL-DFO benchmark 必须把 admissibility validation 和 optimization log 分离；否则 profile 可能奖励 lower-level failure。
• 2. Referee 最重要的价值是反证式清洗，而不是认证。
• 未来更值得做的是构造多样化、互补性强、成本可控的 referee ensemble，并量化未发现非 admissibility 的风险。
• 3. bilevel evaluation 的横轴必须显式建模 upper/lower cost ratio。

一句话总结

这篇论文是 BL-DFO 方向的 benchmark-correction work：它通过 post-hoc referee 审计 admissibility 和加权统计两层计算成本，把 single-level DFO profiles 改造成更符合 bilevel 结构的评测协议。