测试大模型在复杂任务中做出全局最优决策的能力。
AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds
- 将组合优化问题转为部分可观测环境，可验证全局最优解
- 7个顶尖大模型最佳表现仅38.61%达成全局最优
- 难点在于信息整合与全局约束推理，非单纯获取信息
工具使用基准通常评估智能体是否能正确使用工具完成工作流并给出有效参数。但在实际决策场景（如路径规划、车队调度）中，仅可行性不足，因个体选择受共享约束和成本影响，可行解仍可能严重次优。这引出更难的问题：智能体能否将工具获取的信息转化为全局最优决策？我们提出AlgoWorlds，将形式化组合优化问题转化为部分可观测决策环境，并具备可验证的全局最优解。每个环境包含仅通过特定信息工具可见的隐藏实例，智能体需提交结构化决策，评估其可行性和最优性。AlgoWorlds涵盖240个环境，覆盖十类组合优化问题和四个工作负载等级。家族特异性确定性程序生成实例，精确算法验证最优解并划分负载等级，两种结构不同的工具接口呈现同一实例。我们评估了七个领先大模型，包括Claude Opus 4.8和GPT-5.6 Sol。实现全局最优依然极具挑战：尽管主流模型多数能生成可行决策，最优秀模型仅在38.61%情况下达到精确最优。即使智能体收集足够信息重建隐藏实例，多数失败仍表现为可行但次优决策。因此，挑战已超越信息获取，延伸至信息整合、全局约束推理与决策验证。项目主页见https://xzx34.github.io/AlgoWorlds/，代码开源于https://github.com/xzx34/AlgoWorlds。
原文摘要 · Abstract (English)
Tool-use benchmarks generally evaluate whether an agent completes a workflow using appropriate tools and valid arguments. However, feasibility alone is insufficient in real-world decision settings such as route planning and fleet dispatch. Individual choices interact through shared constraints and costs, so a feasible solution may still be substantially suboptimal. This raises a harder question: can an agent turn information gathered through tools into a globally optimal decision? We introduce AlgoWorlds, a benchmark that transforms formally specified combinatorial optimization problems into partially observed decision environments with verifiable global optima. Each environment contains a hidden instance observed only through task-specific information tools, after which the agent commits to one structured decision evaluated for feasibility and optimality. AlgoWorlds contains 240 environments covering ten combinatorial optimization families and four workload levels. Family-specific deterministic programs generate the instances, exact algorithms certify their optima and determine workload levels, and two structurally different tool interfaces present each underlying instance. We evaluate seven leading LLMs, including Claude Opus 4.8 and GPT-5.6 Sol. Achieving global optimality remains highly challenging: although leading models produce feasible decisions in most cases, the best-performing model reaches exact optimality in only 38.61% of cases. Even when agents collect sufficient information to reconstruct the hidden instance, most failures end in feasible but suboptimal decisions. The challenge therefore extends beyond information acquisition to information integration, global constraint reasoning, and decision verification. The project homepage is available at https://xzx34.github.io/AlgoWorlds/, and the code is available at https://github.com/xzx34/AlgoWorlds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。