测试大模型在复杂调度任务中的可靠性,发现约束交互是主要瓶颈。
R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling
- 构建可扩展的基准测试框架,逐步增加调度约束难度。
- 模型在多重约束交互下性能急剧下降,而非图深度导致失败。
- 适合评估大模型在真实场景(如数据中心迁移)中的推理能力。
在资本项目、制造、物流和IT基础设施迁移等大规模规划中,资源、时间和操作约束下的高效调度至关重要。然而,大语言模型(LLMs)在高约束环境下推理的可靠性尚未充分评估。为此,我们提出R-ConstraintBench,一个可扩展的评估框架,用于测试模型在资源受限项目调度问题(RCPSP,NP完全类)上的表现,通过线性增长约束来提升难度。该框架先在有向无环图(DAG)中逐步增加非冗余前序约束,随后引入停机时间、时间窗口和互斥约束。以数据中心迁移为例,对多个LLMs进行可行性与错误分析,识别出性能退化阈值及最易引发失败的约束类型。实证显示,强模型在仅含前序约束的DAG上接近理论上限,但当停机时间、时间窗口与互斥约束共同作用时,可行性性能急剧崩溃,表明约束交互是核心瓶颈,而非图深度。此外,合成数据上的良好表现无法保证在实际场景中的泛化能力,凸显当前模型通用性有限。
原文摘要 · Abstract (English)
Effective scheduling under tight resource, timing, and operational constraints underpins large-scale planning across sectors such as capital projects, manufacturing, logistics, and IT fleet transitions. However, the reliability of large language models (LLMs) when reasoning under high-constraint regimes is insufficiently characterized. To address this gap, we present R-ConstraintBench, a scalable framework that evaluates models on Resource-Constrained Project Scheduling Problems (RCPSP), an NP-Complete feasibility class, while difficulty increases via linear growth in constraints. R-ConstraintBench incrementally increases non-redundant precedence constraints in Directed Acyclic Graphs (DAGs) and then introduces downtime, temporal windows, and disjunctive constraints. As an illustrative example, we instantiate the benchmark in a data center migration setting and evaluate multiple LLMs using feasibility and error analysis, identifying degradation thresholds and constraint types most associated with failure. Empirically, strong models are near-ceiling on precedence-only DAGs, but feasibility performance collapses when downtime, temporal windows, and disjunctive constraints interact, implicating constraint interaction, not graph depth, as the principal bottleneck. Performance on clean synthetic ramps also does not guarantee transfer to domain-grounded scenarios, underscoring limited generalization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。