想象一下，你有一笔有限的资金，用于在迷宫中寻找隐藏的宝藏。你有两种主要策略可供选择：
- “深度思考者”（代理推理）：你雇佣了一位非常聪明且执着的侦探。这位侦探进入迷宫，尝试一条路径，撞墙后感到沮丧，试图调试自己的地图，自言自语，并缓慢地完善其方法。他们可能会解开谜题，但会花费大量时间（和金钱）进行交谈、思考和回溯。
- “飞镖群”（独立采样）：你雇佣了一百个不同的人，而不是只雇佣一名侦探。你给每个人一小笔钱，并告诉他们：“进去，猜测路径，如果卡住了就停止。”你不让他们互相交流或修正错误。你只是向问题抛出大量独立的猜测。
该论文的重大发现：
普林斯顿大学的研究人员在竞争性编程问题（如 Codeforces 上出现的数学和逻辑谜题）上测试了这两种策略。他们发现，策略 2（飞镖群）几乎总是获胜。
即使他们给“深度思考者”大量资金进行深度思考，“飞镖群”仍以更低的成本解决了更多问题。
为什么“深度思考者”在此处会失败？
论文解释说，竞争性编程问题就像自包含的谜题。它们有特定且正确的答案，规则清晰。
- 侦探的陷阱：“深度思考者”（代理）经常陷入循环。它尝试一个解决方案，失败，尝试“调试”它，再次失败，并不断调整同一个想法，却从未意识到整个方法都是错误的。它将预算浪费在无成效的优化上。这就像一个人试图通过反复拧紧同一颗螺丝来修理一块坏掉的手表，而不是意识到他们需要一块新手表。
- 飞镖群的优势：“飞镖群”（k-shot）依赖于探索。因为每个人都是独立猜测，所以飞镖群更有可能在早期就偶然发现那条唯一幸运且正确的路径。它不会浪费时间修正错误；它只是不断尝试新的、全新的想法。
“每次成功的成本”指标
作者不仅关注谁解决了最多的问题，还关注效率。他们提出了一条关于如何分配预算的简单规则：
不要问：“这个方法有多聪明？”
要问：“失败的成本是多少，以及它失败的频率有多高？”
他们从数学上证明，如果你有一笔固定预算，最大化成功几率的最佳方式是找到那种能提供**最低“每美元对数失败可能性”**的方法。
用通俗的话来说：如果一次快速的猜测成本较低且有一定成功几率，你就应该反复进行这种猜测。你不应该为了那些仅略微提高成功几率的漫长复杂过程而额外花费金钱。
核心结论
- 对于软件工程（修复大型代码库中的错误）：“深度思考者”非常出色，因为问题错综复杂，环境复杂，你需要与文件和工具交互才能解决问题。
- 对于竞争性编程（解决逻辑谜题）：“飞镖群”更胜一筹。这些问题就像孤立的数学方程。你不需要侦探去与墙壁对话；你只需要尝试足够多的不同方程，直到有一个奏效。
总之：当你拥有有限预算且面对自包含的谜题时，不要过度思考。与其支付高昂费用进行一次性深度调查，不如向问题抛出大量廉价且独立的猜测。该论文表明，在这种特定情境下，独立尝试的数量往往胜过深度推理的质量。
技术摘要：独立采样何时优于代理推理
问题陈述
本文解决了为大型语言模型（LLMs）解决竞争性编程任务分配固定推理时计算预算的关键挑战。尽管 prior 研究已证明了重复独立采样（例如 k-shot、自一致性）和代理推理（结合工具使用、调试和环境交互的迭代推理）的有效性，但关于其准确率 - 成本权衡仍缺乏系统性的理解。
现有评估通常假设资源无限，或仅报告单一工作点的性能，而未考虑货币成本或模型调用次数。在现实世界的部署中，预算严格受限于成本、延迟或查询数量，目前尚不清楚是将资源投入到具有丰富反馈的单一深度代理轨迹中更优，还是将这些相同资源分配到多个独立的浅层尝试中更优。
方法论
作者在 216 个 Codeforces 问题上进行了严格的实证和理论评估，这些问题涵盖第 1 至第 3 级别，并确保问题发布时间晚于模型的训练时间，以防止数据污染。
评估策略
在匹配约束（货币预算 cmax 和查询次数 kmax）下，比较了三种不同的推理模式：
- k-shot（独立采样）：模型通过单次 API 调用生成 k 个独立解决方案。根据 Codeforces 评测系统的接受情况选择最佳解决方案。
- 代理（单一轨迹）：执行单个 SWE-agent 轨迹，使用完整预算（cmax）。代理可访问终端进行迭代编码、执行和调试，并利用提示缓存来分摊上下文成本。
- Agent-1/3 × 3（预算分割）：将总预算分配给三个独立的 SWE-agent 运行（每个预算为 cmax/3）。这隔离了多次独立初始化的收益与轨迹内优化的收益。
理论框架
为了推广研究结果，作者将问题建模为一个整数规划问题，旨在固定预算 C 下最大化最终成功概率。他们推导出一条成本最优规则：
- 最优策略最小化每美元负对数失败可能性：c−ln(1−p)，其中 p 是成功概率，c 是成本。
- 他们证明，如果单次 API 调用（k-shot）在该指标上的值高于代理运行，则预算应分配给重复的独立调用，而非单一的长代理轨迹。
分析技术
- 轨迹分析：使用 LLM-as-a-judge（GPT-4.1）分析失败的代理运行，对失败模式进行分类。
- 缩放定律：作者估算了 k-shot 和代理运行的成功概率及成本缩放趋势，对代理成本拟合幂律，并分析收敛率。
主要结果
1. 独立采样的优越性
在所有模型系列和难度级别（第 1 至第 3 级别）中，当按货币成本或模型调用次数进行归一化时，k-shot 推理始终优于基于代理的方法。
- 成本效率：对于任何固定的预算阈值，k-shot 解决的严格问题数量多于单一 SWE-agent 运行或预算分割的代理变体。
- 查询效率：即使控制查询数量（忽略成本），代理的表现也落后于 k-shot，这表明低效性不仅仅是由于每次调用的开销或上下文长度更高，而是源于每次调用的有效性较低。
- 鲁棒性：即使在代理框架中启用了提示缓存，性能差距依然存在，排除了上下文长度核算作为造成差异的主要原因。
2. 代理失败模式
轨迹分析显示，代理在竞争性编程环境中经常因特定的结构性弱点而失败：
- 算法效率低下（19.3%）：未能设计高效的算法，导致暴力破解或高复杂度解决方案。
- 迭代循环（7.4%）：在类似的不正确策略中反复循环，仅进行微调而未重新考虑核心方法。
- 调试无效（7.0%）：过度关注外围问题而非战略重新评估。
- 缺乏理论洞察（6.7%）：未能识别必要的数学或组合属性。
3. 缩放趋势
实证缩放分析（图 4）表明：
- k-shot 的成功概率随成本呈指数级收敛至 1，保持每美元负对数失败可能性恒定。
- 代理 的成功概率收敛较慢。由于上下文增长，代理运行的成本随查询数量呈超线性（接近二次方）增长，导致随着预算增加，“每美元负对数失败可能性”显著下降。
- 如果存在最优代理策略，它涉及有限的、短的搜索长度（q∗），超过该长度后，较短搜索的独立重复更具成本效益。
主要贡献
- 系统性比较：跨多个模型和难度级别，对 k-shot、单一代理和预算分割代理进行了细粒度的实证比较，揭示了 k-shot 在准确率 - 成本权衡中占据主导地位。
- 失败模式分析：识别了反复出现的代理弱点（低效迭代、无效调试），解释了其在自包含算法任务中成本效率低下的原因。
- 原则性指标：引入每美元负对数失败可能性（c−ln(1−p)）作为优化成功或失败求解器资源分配的理论依据指标，超越了直观或单点准确率指标。
- 缩放趋势：严格估算缩放定律，显示代理成本呈超线性增长，而独立采样提供线性效率，为在严格约束下偏好 k-shot 提供了数学基础。
意义与主张
本文认为，对于自包含算法任务（如竞争性编程），在现实资源约束下，独立探索（k-shot）比深度代理推理更具成本效益。
- 情境细微差别：作者明确指出，这并不贬低代理在需要复杂导航、文件操作和迭代测试的领域（如 SWE-bench 等软件工程基准）中的价值。相反，研究结果强调推理策略必须与任务结构相匹配。
- 资源分配：该工作提供了一种数学原则化的推理预算分配方法，建议当单次 API 调用比代理运行更具成本效益时，应将资源分配到独立尝试中，而非投入长时间的深思熟虑。
- 评估标准：本文倡导对推理策略进行成本感知的评估，呼吁社区超越单点准确率指标，转向连续的准确率 - 成本轨迹。
作者总结道，虽然代理交互理论上可以提高性能，但在竞争性编程中，迭代优化的开销往往超过其收益，因为“正确”的解决方案路径通常可以通过广泛的独立探索在早期被发现。
每周获取最佳 machine learning 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。