DeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraints

Idea

DeepPlanning 构建 Travel Planning 与 Shopping Planning 两类可验证任务，要求 agent 主动调用 APIs 获取信息、满足单个选择的 local constraints，并同时满足全局时间、空间和预算约束。每个任务运行在独立 offline sandbox 中，最终输出 itinerary 或 shopping cart，通过结构化检查区分部分约束满足与整套计划完全可行。

Research Problem

现有 tool-use benchmark 往往验证单次调用或局部条件，而现实 planning 的困难来自跨步骤依赖：酒店位置影响交通，交通影响时间，coupon 组合改变最便宜的购物方案。传统 planning 测试又常直接给出完整环境信息。论文研究如何同时评估 proactive information acquisition、local reasoning 和 global constrained optimization。

Insight

局部正确率高并不意味着最终 plan 可执行，单个关键约束失败就可能使整套方案无效。论文观察到 constraint-level score 与 case accuracy 的明显差距，说明评测必须保留严格的全局成功条件。Offline sandbox 提供可复现性，但也将结论限制在构造的数据库和 APIs 内；其 code-based scoring 前仍有 LLM parsing 步骤，因此不能称为完全不依赖模型的评估链路。

Method

1. 环境设计：Travel 包含 120 个独立任务及中英文版本，使用真实来源整理的旅行数据和 9 个 APIs；Shopping 包含 120 个英文任务，以合成 product data 和 15 个 APIs 控制属性、优惠与库存复杂度。
2. Task generation：从数据库中的 solution skeleton 出发，逐层注入 personalized constraints 和只有查询环境才能发现的 implicit constraints；调整候选使任务可解且有唯一最优解，再由 LLM 转成自然语言 query。
3. 质量控制与 scoring：人工检查 query 和任务逻辑；Travel 先将 itinerary 解析成固定结构，再用 code 检查 commonsense 与 personalized requirements；Shopping 比较预测 cart 和 ground-truth cart，分别报告 Match Score 与全匹配 Case Accuracy。
4. 评测协议：将模型统一接入 function-calling tools，每任务最多 400 次 tool calls，独立运行四次并平均；进一步分析 reasoning mode、tool calls、interaction turns 与任务复杂度之间的关系，而不只给最终排行榜。