Constraint-Checked LLM Planning for Cluster Recovery
DOI:
https://doi.org/10.54691/6nsbnf76Keywords:
Cluster scheduling, failure recovery, large language models, constraint checking, rescheduling, workflow DAG, decision latency.Abstract
Node failures invalidate the pre-computed schedules of dependency-aware batch workloads, and the recovery decision must be taken while the cluster keeps running. Language models are attractive repair planners because they can weigh heterogeneous objectives expressed in text, but their raw plans are frequently infeasible and their inference latency competes with the recovery itself. This paper presents CC-LLM, a constraint-checked planning architecture in which a small language model proposes repairs and independent components make them safe and timely. CC-LLM (i) scopes the failure with a slack-aware delay analysis over the task graph, (ii) commits every decision that must execute before the expected inference latency to a verified fast incumbent and exposes only the remaining queued decisions to the model, (iii) encodes these decisions as compact decision sheets whose answers are constrained by a JSON Schema, and (iv) checks each proposal for processing-capacity, memory, dependency, node-availability and deadline violations, returning violation certificates that drive conflict-directed revisions before a legalizer and an anytime arbiter select the dispatched plan. On 18 failure scenarios built from real Pegasus executions of six scientific workflows and under an equal 20 s decision budget, CC-LLM with a 0.5B-parameter model on a single CPU core returned a verified feasible plan in every scenario with zero voluntary migrations, achieved the lowest mean repair cost (777 versus 845 for a warm-started CP-SAT solver on the same scope and 1242 for heuristic local repair), shortened recovery time by 18% relative to local repair, and required a mean decision latency of 6.4 s. Unchecked model proposals were feasible in only 44% of the consultations, and certificate feedback reduced conflicting decisions by 67%.
Downloads
References
[1] Verma, A., Pedrosa, L., Korupolu, M., Oppenheimer, D., Tune, E., & Wilkes, J. (2015). Large-scale cluster management at Google with Borg. In Proceedings of the 10th European Conference on Computer Systems (EuroSys).
[2] Coleman, T., Casanova, H., Pottier, L., Kaushik, M., Deelman, E., & Ferreira da Silva, R. (2022). WfCommons: A framework for enabling scientific workflow research and development. Future Generation Computer Systems, 128, 16–27.
[3] Deelman, E., Vahi, K., Juve, G., Rynge, M., Callaghan, S., Maechling, P. J., Mayani, R., Chen, W., Ferreira da Silva, R., Livny, M., & Wenger, K. (2015). Pegasus, a workflow management system for science automation. Future Generation Computer Systems, 46, 17–35.
[4] Schroeder, B., & Gibson, G. A. (2010). A large-scale study of failures in high-performance computing systems. IEEE Transactions on Dependable and Secure Computing, 7(4), 337–350.
[5] Vieira, G. E., Herrmann, J. W., & Lin, E. (2003). Rescheduling manufacturing systems: A framework of strategies, policies, and methods. Journal of Scheduling, 6(1), 39–62.
[6] Herroelen, W., & Leus, R. (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165(2), 289–306.
[7] Topcuoglu, H., Hariri, S., & Wu, M.-Y. (2002). Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3), 260–274.
[8] Sakellariou, R., & Zhao, H. (2004). A low-cost rescheduling policy for efficient mapping of workflows on grid systems. Scientific Programming, 12(4), 253–262.
[9] Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Saldyt, L., & Murthy, A. (2024). Position: LLMs can’t plan, but can help planning in LLM-Modulo frameworks. In Proceedings of the 41st International Conference on Machine Learning (ICML) (Vol. 235, pp. 22895–22907). PMLR.
[10] Valmeekam, K., Marquez, M., Olmo, A., Sreedharan, S., & Kambhampati, S. (2023). PlanBench: An extensible benchmark for evaluating large language models on planning and reasoning about change. In Advances in Neural Information Processing Systems 36 (NeurIPS), Datasets and Benchmarks Track.
[11] Abgaryan, H., Harutyunyan, A., & Cazenave, T. (2024). LLMs can schedule [Preprint]. arXiv. https://arxiv.org/abs/2408.06993
[12] WfCommons Project. (n.d.). WfInstances: Collection of open access production workflow executions [GitHub repository]. https://github.com/wfcommons/WfInstances
[13] Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), 320–333.
[14] Grandl, R., Ananthanarayanan, G., Kandula, S., Rao, S., & Akella, A. (2014). Multi-resource packing for cluster schedulers. In Proceedings of the ACM SIGCOMM.
[15] Mao, H., Schwarzkopf, M., Venkatakrishnan, S. B., Meng, Z., & Alizadeh, M. (2019). Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM SIGCOMM.
[16] Wang, Y., Zou, X., Lu, Z., Wei, K., & Rhee, M. (2026). PRESAGE: Uncertainty-aware predictive elastic scheduling for cloud analytics and GenAI inference. IEEE Access, 14, 146019–146040. https://doi.org/10.1109/ACCESS.2026.3734498
[17] Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., Kohli, P., & Fawzi, A. (2024). Mathematical discoveries from program search with large language models. Nature, 625, 468–475.
[18] Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., & Yao, S. (2023). Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems 36 (NeurIPS).
[19] Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., Gupta, S., Majumder, B. P., Hermann, K., Welleck, S., Yazdanbakhsh, A., & Clark, P. (2023). Self-Refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems 36 (NeurIPS).
[20] Qin, Y., Rhee, M., Teng, D., Zhang, C., & Zi, B. (2026). Neuro-symbolic constraint verification for LLM-driven internet finance transaction execution. Scientific Reports. https://doi.org/10.1038/s41598-026-65233-w
[21] Zhang, H. (2026). A verification-guided multi-agent framework for reliable RTL generation and optimization. Transactions on Computer Science and Intelligent Systems Research, 13, 260–274. https://doi.org/10.62051/r6y8jj34
[22] Geng, S., Josifoski, M., Peyrard, M., & West, R. (2023). Grammar-constrained decoding for structured NLP tasks without finetuning. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
[23] Hui, B., Yang, J., Cui, Z., Yang, J., Liu, D., Zhang, L., Liu, T., Zhang, J., Yu, B., Lu, K., et al. (2024). Qwen2.5-Coder technical report [Preprint]. arXiv. https://arxiv.org/abs/2409.12186
[24] Perron, L., & Furnon, V. (n.d.). OR-Tools (Version 9.15) [Software]. Google. https://developers.google.com/optimization/
[25] goinfer. (n.d.). Single-binary local LLM inference runtime with JSON-Schema-constrained decoding (Version 0.23.0) [GitHub repository]. https://github.com/townsendmerino/goinfer
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Scientific Journal of Intelligent Systems Research
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
