DecompGym: Benchmarking LLM Agents on Designing Decomposition Algorithms
Sikai Cheng · Tinghan Ye · Arnaud Deza · Xiaonan Qi · Miao Li · Litong Liu · et al.
Benders分解（Benders decomposition）与列生成（column generation）通过在主子问题间传递割、列和对偶值来求解大规模优化问题，正确实现难度高。大语言模型已能自动化部分算法设计，指向能为新问题构建分解求解器的智能体。作为迈向此类智能体的第一步，研究当前编码智能体设计与实现这两种算法的能力及失败模式。提出DecompGym，包含来自9个问题族（5个Benders、4个列生成）的81个实例，智能体需为指定方法编写求解器。每个求解器须满足三项标准：60秒内执行；数值可行并通过方法审计（由LLM评审读取求解器代码）；目标值在存储最优目标值的1%以内。评估12个GPT、Claude和Gemini模型在编码智能体工具中的表现。最多十次尝试中，比较独立重新生成与先诊断失败的反思（reflection）。首次尝试中，两个模型解决所有实例，七个模型解决超过90%。多数Benders失败（62次中48次）为缺失或次优解。列生成最常见失败为方法审计拒绝。仅输出检查会接受108次未通过方法审计尝试中的93次。最常见拒绝为optimalif，出现96次，其中92次来自一个模型。反思将66%的重试转为成功，重新生成为39%，并能修复方法审计失败（评审指出缺陷缺口）。因此分解智能体需检查求解器如何得到答案，并提供定位错误的反馈。基准见 https://github.com/SIKAI-C/DecompGym。
内容由 AI 生成，仅供参考。如发现错误，欢迎反馈。
arXiv:2610.38175v1 Announce Type: new Abstract: Benders decomposition and column generation solve large optimization problems by passing cuts, columns, and dual values between a master problem and subproblems, and are hard to implement correctly. Large language models now automate parts of algorithm design, which points toward agents that build decomposition solvers for new problems. As a first step toward such agents, we study how well current coding agents design and implement these two algorithms, and how they fail. We introduce DecompGym, 81 instances from nine problem families (five Benders, four column generation), in which an agent writes a solver for a prescribed method. Each solver must meet three criteria: execution within a 60-second time limit; numerical feasibility together with a method audit, in which an LLM judge reads the solver's code; and an objective within 1% of the stored optimal objective. We evaluate 12 GPT, Claude, and Gemini models running in coding-agent tools. Over up to ten attempts, we compare independent regeneration with reflection, which first diagnoses the failure. On the first attempt, two models solve every instance and seven solve more than 90%. Most Benders failures (48 of 62) are missing or suboptimal solutions. The most common column-generation failure is a method-audit rejection. Output checks alone would accept 93 of the 108 attempts that fail the method audit. The most common rejection, an optimalif, occurs 96 times, 92 of them in one model.Reflection turns 66% of retries into successes, compared with 39% for regeneration, and it repairs method-audit failures, for which the judge names the defecective gaps. Agents for decomposition therefore need checks on how a solver reaches its answer and feedback that locates the error. The benchmark is available at https://github.com/SIKAI-C/DecompGym.
You are Hermes Agent, an intelligent AI assistant created by Nous Research. You are helpful, knowledgeable, and direct. You assist users with a wide range of tasks including answering questions, writing and editing code, analyzing informati…
--- name: xcode-mcp-for-pi-agent description: Guidelines for efficient Xcode MCP tool usage via mcporter CLI. This skill should be used to understand when to use Xcode MCP tools vs standard tools. Xcode MCP consumes many tokens - use only f…
--- description: 'Expert agent for creating and maintaining VSCode CodeTour files with comprehensive schema support and best practices' name: 'VSCode Tour Expert' --- # VSCode Tour Expert 🗺️ You are an expert agent specializing in crea…
1. 问题与价值
这是一篇「知道 + 做到」兼有的论文：它既是一个测量/诊断基准（DecompGym），也验证了一种修复手段（reflection 重试策略）。主贡献是测量：系统回答「当前 coding agents 能否正确实现 Benders 分解与列生成，以及它们如何失败」。
它解决的问题是：现有 LLM 优化基准大多只检查输出（目标值、可行性、运行时间），不检查求解器是否真的执行了规定算法。对于分解算法，输出检查会放过两类违反方法契约的求解器：一类用启发式绕过分解却拿到最优目标，另一类把「整数受限主问题的最优」误报为「全局最优」。论文把这种「通过所有输出检查但未通过方法审计」的尝试定义为 method-conformance gap，并在普通任务（不植入捷径）上测量它。
评测规模锚点：81 个实例，来自 9 个问题族（5 个 Benders、4 个列生成），每个族 3 个尺寸 × 3 个种子；12 个模型（5 个 GPT、6 个 Claude、1 个 Gemini），每个模型跑全部 81 个实例，两种重试策略，共 972 个模型-实例对、1429 次物理尝试。
主结果反差：首次尝试中，99.0% 的求解器能运行，87.8% 通过全部三项标准；但方法审计拒绝的 108 次尝试中，有 93 次返回了可行且目标值在最优值 1% 以内的解——也就是说，只看输出的评测会把这 93 次全部算作成功。这 93 次就是 method-conformance gap 的规模。其中 96 次拒绝是「无证明的最优性声明」，92 次来自 Claude Sonnet 5 一个模型。
受益者是构建分解算法 agent 的研究者：他们需要知道「输出检查不够」以及「反馈必须定位错误」。论文顺带验证的 reflection 修复手段（诊断失败后带着建议重试）把重试成功率从 regeneration 的 39% 提到 66%，但这只是副产品，不是主贡献。
2. 已有工作的不足
在本文之前，最好的做法分两条线。
优化建模基准（如 OptiBench、NL4Opt、ORLM 相关数据集）让模型把自然语言问题转成数学规划模型，由通用求解器求解，用目标值或状态与参考答案比较。这条线的限制是：算法由 Gurobi 等通用求解器提供，模型从不实现算法本身，输出单独决定成败。
算法编写基准（如 FrontierOR、ORAgentBench、HeuriGym、ALE-Bench）让 agent 自己写求解方法，多数按可行性、目标值、运行时间评分；也有一条按「声明的建模与代码是否一致」评分（Opti-Agent-Bench，引文 21）。FrontierOR 观察到更强的模型更常选择分解或混合方法；ORAgentBench 明确承认自己缺少过程级审计。这条线的限制要说准：一致性评分查的是代码与它自己声明的模型是否相符，而不是「求解器有没有真的执行被规定的分解方法」——后者要裁判读代码，判断主子问题之间到底传了割、列还是对偶值。
方法规定型基准来自机器学习研究代码领域：PaperBench 和 ResearchCodeBench 用评分细则和单元测试给「实现一篇论文描述的方法」打分。DecompGym 把这种评估方式带到优化算法：规定分解方法，并用代码审计检查求解器是否符合方法契约。
在论文发表之前就成立的缺口是：没有任何基准在优化算法任务上同时做到「规定方法」和「审计代码是否执行该方法」。这不是「某方法分数低」的能力差距，而是评估设计本身的缺失。
3. 重建作者的思考路径
如果我是作者，面对「LLM 能写优化求解器」的现状，我会先想到：直接让 agent 写分解求解器，然后像 FrontierOR 那样用目标值评分。但很快会撞上一个矛盾——分解算法的难点不在「拿到好目标值」，而在「主问题和子问题之间的信息流是否正确」。一个 agent 完全可以写一个启发式拿到最优目标，却根本没做分解。输出检查看不出这一点。
于是我会想：那就在任务里规定必须用 Benders 或列生成，然后检查代码。但「检查代码」本身很难自动化——怎么判断一段代码是不是真的在做列生成？我可能会先尝试规则检查（比如「代码里必须出现 master 和 subproblem 两个模型」），但很快发现这太容易被表面形式骗过：模型可以建两个模型却从不真正迭代。所以我需要一个 LLM judge 读代码、追踪调用路径、判断信息是否真的从子问题流回主问题。
到这里，我会意识到一个新问题：judge 的判据必须非常具体，否则它自己也会被「Gurobi 返回 optimal」骗过。最关键的判据是状态标签——求解器报告
optimal意味着它声称证明了全局最优，但列生成的整数受限主问题最优只证明「在已生成列内最优」。这个区分必须写进方法契约，否则 judge 无法拒绝「无证明的最优性声明」。设计好审计之后，我自然会问：输出检查和代码审计的差距有多大？这就是 method-conformance gap 的测量动机。同时，既然要跑多轮重试，我会想知道「重新生成」和「先诊断再改」哪个更有效——这引出 reflection 与 regeneration 的配对比较。
与论文实际路径的差异：我猜作者可能先有「输出检查不够」的直觉，再设计审计来验证它；论文的实际路径似乎更强调「method-conformance gap」作为核心测量对象，reflection 是顺带的策略比较。另外，我没想到作者会把「无证明最优性声明」做成如此核心的判据——这需要先意识到列生成的整数受限主问题最优性是一个普遍且隐蔽的失败模式，而论文的案例研究（第 5.3 节）表明作者确实在数据中发现了这个模式后才把它提升为核心发现。
4. 核心 intuition
用一个日常类比：考试只对答案不对过程。
一个学生交上来的答案是对的，但老师要求「必须用指定方法解题」。如果老师只对答案，学生用猜的、抄的、或者另一种更简单的方法拿到正确答案，老师都看不出来。DecompGym 的做法是：老师不仅对答案，还看解题过程——「你写的是不是 Benders 分解？你的主问题和子问题之间有没有真的传递对偶值和割平面？你最后写『最优』的时候，你的过程真的证明了没有更好的解吗？」
这个类比能对上机制：输出检查对应「对答案」，方法审计对应「看过程」，method-conformance gap 对应「答案对但过程错」的那批学生。列生成里「整数受限主问题最优」被误报为「全局最优」，就像学生解了一个缩小版的问题，却声称解决了原问题——答案恰好一样，但证明不成立。
5. 方法 pipeline 举例
以论文第 5.3 节的案例为例：Claude Sonnet 5 处理中等尺寸 cutting stock 实例（seed 0）。
输入：
data.json包含 stock_size=247，6 种 item types，每种有 size 和 demand。任务要求用列生成求解，输出output.json包含 status、objective_value、patterns。第一步（生成初始列）：agent 写的求解器为每种 item type 构造单类型 pattern，例如一个 pattern 切
floor(247/137)=1个 type 0，另一个切floor(247/77)=3个 type 1，等等。这些是受限主问题的初始列。第二步（受限主问题 LP）：求解器解一个连续 LP，变量是各 pattern 的使用次数，约束是每种 item 的需求必须被覆盖。得到对偶值
c.Pi（每个需求约束的影子价格）。第三步（定价子问题）：用对偶值解一个整数背包问题：在容量 247 内选择 item 组合，最大化对偶值之和。如果最优值大于
1.0 + 1e-6，说明存在负 reduced cost 的列，把它加入受限主问题，回到第二步。否则定价收敛。第四步（整数受限主问题）：定价收敛后，把受限主问题改成整数规划（pattern 使用次数为整数），求解。Gurobi 返回
GRB.OPTIMAL。第五步（写输出——失败点）：agent 的代码写
if final.Status == GRB.OPTIMAL: status = "optimal"，把整数受限主问题的最优状态直接映射为全局最优。输出 objective_value=87（恰好等于最优值），status="optimal"。第六步（方法审计）：judge 读代码，发现 status 赋值逻辑没有比较整数目标与
ceil(LP relaxation value)，也没有确认定价循环是因为「无改进列」而非时间/迭代上限而终止。判定 FAIL，理由是「整数受限主问题的最优性不等于全局最优性」。第七步（reflection 修复）：诊断调用读到 judge 的理由，写出建议：「无条件报告 feasible，除非定价收敛且整数目标等于 LP 松弛的向上取整」。第二次尝试加入这个 bound check：只有当定价已收敛、且整数受限主问题目标等于 LP 松弛的向上取整时才写
optimal，否则写feasible。这条实例上 bound 恰好闭合，所以第二次输出的还是同样的 87 件和 patterns，status 仍然写optimal。论文特意点明：两次尝试的输出完全相同，唯一的区别是第二次的代码能证明它报的那个 optimal——judge 接受。同一实例上 Claude Sonnet 5.5 和 GPT-6 Astra 第一次就做了这个 bound 检查；而不给 reflection 时，Claude Sonnet 5 十次尝试都在重复同一条 status 规则。6. 核心数学推导
论文附录 E.1 给出列生成中最优性证明的推导。设 Ω 是所有可行 cutting patterns 的集合，K 是已生成的 patterns 子集，z* 是原问题最优目标（最少 stock 数量）。
第一步：线性松弛下界。 列生成先解受限主问题的 LP 松弛。如果定价子问题证明 Ω 中没有任何 pattern 有负 reduced cost，那么受限 LP 值等于完整 LP 松弛值 z_LP。因为 LP 松弛是原整数问题的松弛，所以
z_LP ≤ z*。这是有效下界。如果定价因时间或迭代上限提前停止，受限 LP 值不能证明任何下界。第二步：整数受限主问题上界。 把受限主问题作为整数规划求解，得到值
z_IP(K)。因为 K 是 Ω 的子集，这个解是原问题的一个可行解，所以z_IP(K) ≥ z*。这是上界。Gurobi 对这个整数规划返回optimal，只意味着「在 K 内没有更好的整数解」，不是全局最优。第三步：合并两个界。 得到
z_LP ≤ z* ≤ z_IP(K)。因为目标值是整数（stock 数量），解被证明最优当且仅当z_IP(K) = ceil(z_LP)。否则 gap 未闭合：最优整数解可能需要一个定价从未生成的 pattern，因为定价只优化 LP 松弛，不考虑整数规划。一句话总结：这个推导在算「什么时候整数受限主问题的解可以被证明是全局最优」——只有当整数目标恰好等于 LP 松弛值的向上取整时，两个界才闭合；否则报告
optimal就是把「在已生成列内最优」偷换成了「在所有可能列内最优」。7. 实验设计
数据集：81 个实例，9 个问题族。Benders 5 族：UFL（无容量设施选址）、FCTP（固定费用运输）、KM（k-median）、LRP（选址路径）、TSSO（两阶段随机规划）。列生成 4 族：BP（装箱）、CSP（切割库存）、GAP（广义指派）、SHIFT（班次调度）。每族 3 个尺寸 × 3 个种子。实例维度见附录 B，例如 UFL 小尺寸 7-10 个站点/19-25 个客户，大尺寸 29-37 个站点/75-98 个客户。
基线/模型：12 个模型，5 个 GPT（通过 Codex CLI）、6 个 Claude（通过 Claude Code）、1 个 Gemini 3.8 Flash（通过 Antigravity），全部 medium reasoning effort。每个模型跑全部 81 个实例。
指标：三项标准按顺序检查——E（执行，60 秒内运行并写输出）、V（验证，数值可行性检查 + 方法审计）、Q（质量，目标值在最优值 1% 以内）。Q@k 表示前 k 次尝试中至少一次成功。成本用 agent 时间和 tokens 分别测量。
消融/对比：两种重试策略配对比较——regeneration（每次从头重新生成）vs reflection（先诊断失败、写建议、再修改）。两者共享第一次尝试，所以 Q@1 相同，差异从 Q@2 开始。
实验能否支撑结论：能支撑「输出检查不够」的核心主张，因为 method-conformance gap 的 93 次尝试是直接测量的，且审计理由经过人工分类。能支撑「reflection 更快恢复」的方向性结论，但论文自己承认（第 6 节）每个模型-实例-策略只跑一条轨迹，没有重复实验估计 run-to-run 方差，所以配对差异是描述性的。缺什么：没有测量 judge 的假阴性率（接受但实际违反方法的求解器），因为接受的尝试没有人工复核；judge 是 GPT-6 Astra，而 GPT-6 Astra 也是被评估模型之一，存在自偏好风险（论文承认但未量化）。
8. take-aways
9. 最脆弱的假设
最脆弱的假设是：LLM judge 的代码审计是可靠的——具体说，judge 能正确识别「求解器是否真的执行了规定分解」以及「最优性声明是否有证明」。
这个假设一倒，method-conformance gap 的测量就失去意义：如果 judge 大量漏判（接受违反方法的求解器），gap 被低估；如果 judge 大量误判（拒绝合规求解器），gap 被高估。
论文给出的证据：judge 的每次拒绝理由都被人工阅读并分类（108 次拒绝全部人工复核），且论文引用了「LLM judge 在代码级作弊检测上可靠」的文献。但论文自己承认两个关键缺口：接受的尝试没有人工复核，所以 judge 的假阴性率（漏判率）未测量；judge 是 GPT-6 Astra，而 GPT-6 Astra 也是被评估模型之一，存在自偏好风险（LLM judge 可能偏向自己模型的输出）。论文没有量化这个偏差对结果的影响。如果 judge 对 GPT-6 Astra 的代码更宽容，那么 GPT-6 Astra 的 100% 首次成功率可能部分来自 judge 偏差而非真实能力。
10. 一周最小复现
目标：复现核心发现——method-conformance gap 存在，且主要由「无证明最优性声明」驱动。
步骤：
预期指标：如果复现成功，你应该看到至少几个实例上，求解器返回了等于最优的目标值、报告
optimal，但 judge 拒绝，理由是「整数受限主问题最优被当作全局最优」。论文中 Claude Sonnet 5 在 36 个列生成首次尝试中有 26 次无证明最优性声明，你的小规模复现应该能看到同样的模式，即使具体比例不同。资源：24GB 显卡足够跑 LLM 推理（如果本地跑）或直接调 API；Gurobi 学术许可免费；9 个 CSP 小实例的完整 MIP 求解在秒级完成。
11. 反例设计
要推翻的核心主张：输出检查会系统性放过违反方法契约的求解器，因此需要代码审计。
反例实验：构造一个「输出检查足够」的场景，证明 method-conformance gap 在特定条件下消失或变得无关紧要。
具体设计：在 DecompGym 的 81 个实例上，把方法审计从评估标准中移除，只保留执行、可行性、目标值三项。然后测量：被审计拒绝的 93 次「输出通过」尝试，它们的目标值分布与「审计通过」的尝试是否有实质差异。如果这 93 次尝试的目标值全部等于最优值（不只是 1% 内），且它们的求解器在更大实例上也能保持同样的目标质量，那么可以主张「输出检查虽然放过方法违规，但这些违规在实际意义上无害」——即 method-conformance gap 是一个「过程洁癖」问题，不是「结果质量」问题。
判据：如果这 93 次尝试在未见过的更大实例上（比如把 CSP 的 stock length 和 demand 翻倍）仍然能达到最优目标，且运行时间不显著劣于合规求解器，那么「需要代码审计」的主张就被削弱——因为输出检查已经足够保证结果质量。反之，如果这些违规求解器在更大实例上目标值显著偏离最优（因为它们的方法本身有缺陷，只是在小实例上碰巧拿到好结果），则论文的核心主张得到加强。
为什么这个实验能推翻主张：论文的核心论点是「输出检查不够，必须看过程」。如果实验显示「输出检查在结果质量上已经足够」，那么「必须看过程」的规范性主张就失去实用依据——审计变成了一种洁癖而非必要保障。
12. 落地判断
能否用于「抢占式 GPU 自托管 27B 模型做多智能体脚手架」：能，但要以「审计者」而非「求解器生成者」的身份用。
怎么用：你的场景是自托管 27B 模型做多智能体脚手架，涉及抢占式 GPU（随时可能被抢占）。DecompGym 的直接启示不是「让 27B 模型去写 Benders 分解」（论文里最强的模型是 GPT-6 Astra 和 GPT-6.1 Sol，27B 自托管模型的能力大概率远低于此），而是把方法审计作为你脚手架里的一个检查环节。如果你的多智能体系统里有 agent 声称「我用了某算法」或「我证明了最优性」，你可以用 DecompGym 的 judge prompt 模式（读代码、追踪调用路径、检查状态标签是否有证明支撑）来审计它。特别是「最优性声明必须有 bound 闭合证明」这一条，可以直接移植到任何涉及优化的 agent 输出检查里。
成本量级：论文中 judge 是 GPT-6 Astra 高推理努力，但你不需要这么强。27B 模型做代码审计在简单场景下可能够用，成本是每次审计一次 LLM 推理调用。论文中 agent 时间从 21.5 秒到 228.2 秒不等，tokens 从 60.9 千到 277.6 千不等——这是生成求解器的成本，审计单独算。你的场景里审计是增量成本，每次调用大约几千到几万 tokens。
最大的坑：不要用 27B 模型既当求解器生成者又当审计者。论文明确指出 judge 的自偏好风险（LLM judge 偏向自己模型的输出），且 judge 是 GPT-6 Astra 而 GPT-6 Astra 也是被评估模型。你的 27B 模型如果既生成代码又审计自己的代码，假阴性率（放过违规）会不可控。如果必须自托管，至少让审计调用和生成调用使用不同的系统提示、不同的采样参数，并且对审计结果做规则化的二次检查（比如「状态标签是 optimal 时，代码里必须出现 bound 比较」这种可自动验证的模式）。另一个坑是抢占式 GPU 的时延：论文的 60 秒求解器时间限制在你的抢占式环境里可能不够，因为抢占会导致求解器被中断，你需要把「被抢占」和「求解器超时」区分开，否则审计会误判。