Introduction
In Constraint Programming (CP), defining the rules or constraints of a problem is often more challenging than finding a solution. For non-experts, formalizing these constraints is a significant barrier. Constraint Acquisition (CA) systems attempt to bridge this gap by asking users to classify examples as valid (positive) or invalid (negative). However, traditional active learning systems like QUACQ face two major hurdles: the "Bias Problem," requiring a predefined list of all possible constraints, and "Low Information Density," where simple binary feedback necessitates a high volume of queries.
Methodology
To address these limitations, the authors propose LLMACQ, a system that integrates Large Language Models (LLMs) to process natural language explanations for invalid solutions. LLMACQ is built upon ACQNOGOODS, a schema that learns "nogoods" (forbidden value combinations) instead of full formal constraints, thereby eliminating the need for an explicit bias.
The core of LLMACQ is a fine-tuned BERT model designed for Multi-Task Learning. When a user rejects an example with a natural language explanation (e.g., "The sum of x4 and x5 must be 40"), the model performs two simultaneous tasks: Relation Identification (determining the constraint type) and Parameter Identification (identifying the specific variables and constants involved).
If the LLM successfully identifies the constraint, the system learns it immediately, significantly reducing the search space. A robust fallback mechanism ensures the system remains functional even if the LLM fails to interpret the feedback.
Experimental Setup
LLMACQ was evaluated against the state-of-the-art QUACQ2 system using classic logic benchmarks: Purdey, Zebra, Sudoku, and Kakuro (versions Kakuro1 and Kakuro93). The BERT component was trained on a synthetic dataset of 200 sentences per relation, generated using ChatGPT-4 templates.
Results and Discussion
The experimental results demonstrate a substantial improvement in efficiency. On the Sudoku benchmark, LLMACQ reduced the number of queries from 6,948 (QUACQ2) to just 101.4. Furthermore, LLMACQ successfully solved complex Kakuro instances in under 90 seconds, whereas QUACQ2 timed out due to the astronomical size of the required bias.
The fine-tuned BERT model achieved 91% accuracy in identifying relations and parameters, validating the feasibility of using natural language as a high-density information source for constraint acquisition.
Conclusion
LLMACQ represents a significant advancement in constraint acquisition by leveraging the semantic power of LLMs. By transforming natural language feedback into formal constraints, it bypasses the combinatorial explosion of traditional methods. Future work may explore more advanced generative LLMs to handle even more complex, multi-sentence user feedback and further refine the system's robustness.
Summary updated