TRACE-cs: Trustworthy Reasoning for Contrastive Explanations in Course Scheduling Problems

Stylianos Loukas Vasileiou, William Yeoh

Abstract

We present TRACE-cs, a novel hybrid system that combines symbolic reasoning with large language models (LLMs) to address contrastive queries in scheduling problems. TRACE-cs leverages SAT solving techniques to encode scheduling constraints and generate explanations for user queries, while utilizing an LLM to process the user queries into logical clauses as well as refine the explanations generated by the symbolic solver to natural language sentences. By integrating these components, our approach demonstrates the potential of combining symbolic methods with LLMs to create explainable AI agents with correctness guarantees.

Introduction

Automated scheduling systems, such as those used for university course planning, are often opaque to the end-user. When a system rejects a specific course selection, users require a clear and accurate explanation of the underlying constraints. Existing approaches typically fall into two categories: symbolic logic systems, which are mathematically sound but produce technical, unreadable output; and Large Language Models (LLMs), which offer natural language fluency but are prone to "hallucinations" and logical inconsistencies in complex constraint-satisfaction tasks. TRACE-cs (Trustworthy ReAsoning for Contrastive Explanations in Course Scheduling) addresses this gap by providing a neuro-symbolic framework that is both logically rigorous and human-accessible.

Methodology

The TRACE-cs architecture bifurcates the reasoning process into two distinct modules: a Symbolic Module for logical computation and an LLM Module for natural language interface.

The TRACE-cs architecture combines a Symbolic Module for constraint solving with an LLM Module for natural language processing.

Symbolic Module

The Symbolic Module serves as the core reasoning engine. It utilizes an Encoder to transform university degree requirements and course prerequisites into Boolean logic, formulated as a Satisfiability (SAT) problem. When a conflict is identified, an Explainer applies formal algorithms to extract the minimal set of constraints responsible for the conflict, ensuring the explanation is grounded in the system's hard rules.

LLM Module

The LLM Module (utilizing GPT-4.1) manages user interaction. A Query Parser translates natural language queries into logical clauses. To ensure reliability, a User Verification step requires the user to confirm the parsed query before execution, preventing errors in interpretation. Finally, an Explanation Refiner converts the raw logical output from the Symbolic Module into a coherent, natural language explanation.

Experimental Setup

The system was evaluated using a dataset derived from a real-world university course catalog for a Computer Science degree, encompassing over 200 courses and complex prerequisite chains. The evaluation set consisted of 550 contrastive queries of varying complexity levels (1, 2, 4, and 6), representing the number of courses involved in the query.

Results and Discussion

TRACE-cs was benchmarked against a pure LLM baseline (GPT-4.1) provided with the full set of scheduling rules in its prompt.

Performance comparison between TRACE-cs and a pure LLM baseline across different complexity levels.

As shown in the results, TRACE-cs achieved 100% accuracy across all complexity levels, whereas the pure LLM's accuracy declined significantly as query complexity increased, averaging only 54.1%. Furthermore, TRACE-cs produced more concise explanations, averaging 81.8 words compared to the baseline's 159.4 words. While TRACE-cs exhibited higher latency (14.7 seconds vs 4.3 seconds), this "correctness tax" is a necessary trade-off for ensuring the reliability of explanations in high-stakes academic planning.

Conclusion

TRACE-cs demonstrates that the integration of symbolic solvers with LLMs can overcome the limitations of pure neural approaches in reasoning tasks. By delegating logic to a SAT solver and language processing to an LLM, the system provides explanations that are both provably correct and easy to understand. Future work will focus on optimizing latency and evaluating the system's utility with real-world student cohorts across diverse scheduling domains.

Summary updated

Abstract

We present TRACE-cs, a novel hybrid system that combines symbolic reasoning with large language models (LLMs) to address contrastive queries in scheduling problems. TRACE-cs leverages SAT solving techniques to encode scheduling constraints and generate explanations for user queries, while utilizing an LLM to process the user queries into logical clauses as well as refine the explanations generated by the symbolic solver to natural language sentences. By integrating these components, our approach demonstrates the potential of combining symbolic methods with LLMs to create explainable AI agents with correctness guarantees.
BibTeX
@inproceedings{vasileiou2025trace,
  author = {Stylianos Loukas Vasileiou and William Yeoh},
  title = {{TRACE-cs: Trustworthy Reasoning for Contrastive Explanations in Course Scheduling Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i28.35374},
}
Figure