SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling

• URL: http://arxiv.org/abs/2608.00991v1
• Date: Sun, 02 Aug 2026 04:41:20 GMT
• Title: SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling
• Abstract summary: SCHEDBench is a benchmark for evaluating scheduling constraint faithfulness under surface-form variation.<n>It spans 1,132 instances across job-shop scheduling problems, single and multi-mode resource-constrained project scheduling problems, nurse rostering/scheduling, and curriculum timetabling problems.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces SCHEDBench, a natural-language benchmark for evaluating combinatorial scheduling constraint faithfulness under surface-form variation. Grounded in canonical scheduling instances and solver-derived feasibility and optimality, SCHEDBench assesses whether large language models (LLMs) generate schedules with the same constraint-feasible behavior across varied natural-language (NL) surface forms. SCHEDBench spans 1,132 instances across job-shop scheduling problems (JSP), single and multi-mode resource-constrained project scheduling problems (RCPSP), nurse rostering/scheduling, and curriculum timetabling problems of varying difficulty. Instances are templated into natural language problems using domain-specific templates, themed entities, lexical-syntactic template rephrasing, and constraint-level surface-form variation, with reference solutions verified for feasibility and objective optimality. Across thirteen frontier and open-weight LLMs, we find that models are not reliably invariant to semantically equivalent renderings of the same scheduling problem. Surface-form variation reduces feasibility and induces above-noise shifts in per-instance hard-constraint violations on matched instances. Among the tested isolated axes, constraint reordering yields the clearest above-noise sensitivity.

Related papers

• DScheLLM: Enabling Dynamic Scheduling through a Fine-Tuned Dual-System Large language Model [2.9367859148626945]
  This paper proposes DScheLLM, a dynamic scheduling approach that leverages fine-tuned large language models within a dual-system (fast-slow) reasoning architecture.<n>A unified large language model-based framework is constructed to handle dynamic events, where training datasets for both fast and slow reasoning modes are generated.<n> Experimental evaluations on standard job shop scheduling benchmarks demonstrate that the fast-thinking mode can efficiently generate high-quality schedules.
  arXiv  Detail & Related papers  (2026-01-14T03:02:22Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering [64.62317305868264]
  We present textbfKBQA-R1, a framework that shifts the paradigm from text imitation to interaction optimization via Reinforcement Learning.<n>Treating KBQA as a multi-turn decision process, our model learns to navigate the knowledge base using a list of actions.<n>Experiments on WebQSP, GrailQA, and GraphQuestions demonstrate that KBQA-R1 achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-12-10T17:45:42Z)
• When Words Change the Model: Sensitivity of LLMs for Constraint Programming Modelling [1.052782170493037]
  Large language models show impressive results in automatically generating models for classical benchmarks.<n>Many standard CP problems are likely included in the training data of these models.<n>We show that while LLMs can produce syntactically valid and semantically plausible models, their performance drops sharply under contextual and linguistic variation.
  arXiv  Detail & Related papers  (2025-11-18T10:40:32Z)
• FACTS: Table Summarization via Offline Template Generation with Agentic Workflows [11.885086835801523]
  FACTS produces offline templates, which can be rendered into natural language summaries and are reusable across multiple tables.<n>It enables fast summarization through reusable offline templates, accurate outputs with executablesql queries, and privacy compliance by sending only table schemas to LLMs.
  arXiv  Detail & Related papers  (2025-10-15T10:24:49Z)
• CP-Bench: Evaluating Large Language Models for Constraint Modelling [6.250460397062786]
  Constraint programming (CP) is widely used to solve problems, but its core process, namely constraint modelling, requires significant expertise and is considered to be a bottleneck for wider adoption.<n>Recent studies have explored using Large Language Models (LLMs) to transform problem descriptions into executable constraint models.<n>Existing evaluation datasets for constraint modelling are often limited to small, homogeneous, or domain-specific instances, which do not capture the diversity of real-world scenarios.<n>This work addresses this gap by introducing CP-Bench, a novel benchmark that includes a diverse set of well-known problems sourced from the CP community, structured
  arXiv  Detail & Related papers  (2025-06-06T12:56:02Z)
• LLM-Symbolic Integration for Robust Temporal Tabular Reasoning [69.27153114778748]
  We introduce TempTabQA-C, a synthetic dataset designed for systematic and controlled evaluations.<n>This structured approach allows Large Language Models (LLMs) to generate and executesql queries, enhancing generalization and mitigating biases.
  arXiv  Detail & Related papers  (2025-06-06T05:14:04Z)
• Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo [90.78001821963008]
  A wide range of LM applications require generating text that conforms to syntactic or semantic constraints.<n>We develop an architecture for controlled LM generation based on sequential Monte Carlo (SMC)<n>Our system builds on the framework of Lew et al. (2023) and integrates with its language model probabilistic programming language.
  arXiv  Detail & Related papers  (2025-04-17T17:49:40Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• Matchmaker: Self-Improving Large Language Model Programs for Schema Matching [60.23571456538149]
  We propose a compositional language model program for schema matching, comprised of candidate generation, refinement and confidence scoring. Matchmaker self-improves in a zero-shot manner without the need for labeled demonstrations. Empirically, we demonstrate on real-world medical schema matching benchmarks that Matchmaker outperforms previous ML-based approaches.
  arXiv  Detail & Related papers  (2024-10-31T16:34:03Z)
• Automated Conversion of Static to Dynamic Scheduler via Natural Language [3.4748713192043876]
  We propose a Retrieval-Augmented Generation (RAG) based LLM model to automate the process of implementing constraints for Dynamic Scheduling (RAGDyS) Our framework aims to minimize technical complexities related to mathematical modelling and computational workload for end-users.
  arXiv  Detail & Related papers  (2024-05-08T04:07:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.