Abstract
Scheduling complex academic paths requires both logical precision and human-readable explanations. While symbolic solvers provide the former and Large Language Models (LLMs) the latter, neither alone is sufficient for trustworthy, explainable AI. We present TRACE-CS (Trustworthy ReAsoning for Contrastive Explanations in Course Scheduling), a hybrid architecture that integrates the linguistic capabilities of LLMs with the formal rigor of SAT-based symbolic reasoning. Our evaluation demonstrates that TRACE-CS achieves 100% explanation correctness, significantly outperforming standalone LLM baselines.
Introduction
Scheduling is a computationally difficult problem with significant social implications. In academic settings, students often require justifications for scheduling constraints—for instance, why a specific course cannot be taken in a given semester or why a certain prerequisite is blocking their progress. Traditional symbolic methods, while mathematically sound and "provably correct," produce dense logical formulas that are largely unintelligible to non-experts. Conversely, Large Language Models (LLMs) like GPT-4 offer conversational fluency but are prone to logical hallucinations and struggle with the combinatorial complexity of high-stakes planning scenarios.
TRACE-CS bridges this gap by employing a "synergistic" hybrid architecture. By using LLMs as a natural language interface for a symbolic "brain," the system provides explanations that are both linguistically coherent and logically sound.
Methodology
The TRACE-CS architecture is divided into two primary components: the Symbolic Module and the LLM Module. This "LLM-Modulo" framework ensures that the LLM handles the "messy" natural language processing while the symbolic solver handles the strict logical reasoning.
The Symbolic Module
The Symbolic Module serves as the system's logical core. It consists of an Encoder that translates real-world academic constraints—such as prerequisites, credit requirements, and semester availability—into formal logical formulas. These formulas constitute a Knowledge Base (KB). When a user poses a "Why?" question, the Explainer sub-module utilizes a SAT-based solver to identify the exact logical constraints that prevent a specific outcome. Because the explanation is derived directly from the solver's proof, it is guaranteed to be a factual reflection of the underlying constraints.
The LLM Module
The LLM Module, powered by GPT-4, manages the interaction between the user and the symbolic core. The Query Parser translates natural language queries (e.g., "Why can't I take Computer Graphics this semester?") into a symbolic representation ($\phi$) that the logic solver can process.
A critical feature of this module is the User Query Verification step. Before the solver executes, the LLM presents its interpretation of the query to the user for confirmation. This ensures that any "translation" errors are caught early, maintaining the integrity of the reasoning process. Finally, the Explanation Refiner takes the raw logical output from the solver and converts it back into natural English. This is achieved by "stitching" together pre-defined English labels associated with each logical formula in the KB.
Evaluation and Results
The system was evaluated using a proof-of-concept dataset derived from the official computer science course catalog and degree requirements at Washington University in St. Louis. The authors generated 10 distinct schedules and 100 unique "schedule-query pairs" to test the system's accuracy.
The performance of TRACE-CS was compared against GPT-4 in "Zero-shot" and "Few-shot" modes, where the LLM attempted to explain the schedules without symbolic assistance. As shown in the table below, TRACE-CS achieved 100% correctness in its explanations. In contrast, standalone LLMs failed more than half the time, highlighting their inability to handle complex scheduling logic without a symbolic "anchor."
Discussion and Conclusion
The success of TRACE-CS underscores the importance of provable trustworthiness in AI-assisted decision-making. By anchoring natural language explanations in a symbolic solver, the system eliminates the risk of hallucination.
However, several areas for future work remain. The current reliance on manual user verification, while beneficial for accuracy, adds an extra step to the user experience. Additionally, while SAT solvers are robust, scaling to extremely large-scale scheduling problems involving thousands of agents may require more specialized optimization techniques. Future research will also involve user studies with students and academic advisors to measure the qualitative helpfulness and intuitiveness of the generated explanations in real-world academic environments.
Summary updated