Active Constraint Acquisition Using Large Language Models

Abstract

Background: In Constraint Programming, constraint acquisition is the subfield that addresses the issue of modelling problems as sets of constraints, so that they can be solved by a constraint solver. This is a way to dramatically extend the use of Constraint Programming technology. Most active constraint acquisition systems suffer from two weaknesses. They require the explicit generation of the set of potential constraints (the bias), whose size can be prohibitive for practical use of these systems, and the answers to queries contain little information. Objectives: We introduce AcqNogoods, an active learning schema that does not require the construction of a bias. We then propose LlmAcq, an active learning system that incorporates a Large Language Model (LLM) component in the AcqNogoods schema. LlmAcq interprets the user’s answers given in natural language, leading to more informative communication. Methods: LlmAcq was instantiated with (i) a fine-tuned LLM encoder and (ii) a prompt-engineered LLM decoder. We evaluated both variants on classical logic-puzzle benchmarks (Purdey, Zebra, Sudoku, Kakuro). For greater realism, we also collected written feedback from 12 human subjects and used these data to design a pseudo-real experiment. Results: Across all benchmarks, LlmAcq dramatically decreases the number of queries, while learning constraints of arbitrary arity without the need of an explicit bias. The version of LlmAcq using a decoder LLM shows better accuracy and an interesting abstraction capability that allows it to learn several constraints from a single user’s answer. Conclusions: Our results suggest that combining natural-language feedback with bias-free learning is a promising step toward more user-friendly Constraint Programming modeling.