Research map / Learning theory and algorithms / Combinatorial and search optimization
Conversational Modeling for Constraint Satisfaction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
A blue-sky position paper arguing that automated constraint programmers should hold richer conversations with domain experts (volunteering, soliciting, refining, and using natural language), beyond yes/no oracle queries.
Problem
Constraint acquisition systems treat the domain expert as a yes/no oracle, which makes problem specification burdensome; the conversation between constraint programmer and domain expert is largely unautomated.
Approach
Proposes shifting the research emphasis to what the domain expert can proactively provide: volunteering constraints or justifications, soliciting richer contributions via prompts, refining imperfect models through dialogue, and bridging NLP and chatbots with constraint acquisition.
Key results
- No experiments are reported; the paper illustrates with an anecdotal ChatGPT 3.5 exchange in which the chatbot mis-generalizes a constraint about odd and even row numbers.
Surprising findings
- ChatGPT 3.5 produced an incorrect claim that row 2 is odd, and only corrected it after being challenged.
Limitations
- No empirical evaluation; directions remain abstract with anecdotal illustrations.
- Evaluating conversational modeling is harder than with automated oracles because simulating domain experts is difficult.
- Chatbot-based training data for constraint conversations is not available online and would need to be recorded.
Experimental setup
Builds on: QUACQ GENACQ MGEQCA SEQACQ
Closest papers by meaning
- Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025 · similarity 0.82)
- Logic.py: Bridging the Gap between LLMs and Constraint Solvers (NeurIPS 2025 · similarity 0.82)
- On the Modelling of Constraints with Tractable Logical Operators (AAAI 2025 · similarity 0.81)
- QuestBench: Can LLMs ask the right question to acquire information in reasoning tasks? (NeurIPS 2025 · similarity 0.80)
- What Are the Rules? Discovering Constraints from Data (AAAI 2024 · similarity 0.80)
- Learning to Learn in Interactive Constraint Acquisition (AAAI 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.