Source-linked AI summary
Learning Symbolic Constraint Representations from Examples: A Neuro-Symbolic Approach
Nassim Belmecheri, Arnaud Gotlieb, Nadjib Lazaar, Helge Spieker
TL;DR
Constraint acquisition can require costly interaction with human oracles, and the paper asks whether Transformers can learn constraint structure from examples. It pairs a neural oracle with a symbolic learner in an automated acquisition framework. FastCA/TO3 achieves the strongest reported pairings, while scalability to extremely large domains remains to be assessed.
Problem
Active constraint acquisition depends on oracles that may face thousands of queries and multi-second delays, motivating the question of whether Transformers can learn constraint structure from examples.
Source: §1 · p. 2Method
The framework trains neural Transformer oracles on labeled examples and pairs their feedback with the FastCA symbolic learner in a closed loop.
Source: §1 · p. 2, §6 · p. 12Results
FastCA/TO3 consistently achieves the highest performance, often reaching 100% across all metrics, including on sparse-solution problems.
Source: §5.3 · p. 9Takeaways & Limitations
Pairing neural guidance with FastCA’s exhaustive search yields a robust automated acquisition framework resilient to incorrectly classified examples that destabilize sequential learners.
Source: §6 · p. 12Scalability to extremely large-scale domains remains to be assessed, particularly where exhaustive search is used.
Source: §6 · p. 12
Abstract
from arXiv · showhide
Learning user-defined concepts as constraint networks has been extensively studied in the constraint acquisition (CA) literature. However, existing approaches typically rely on intensive interactions with a human oracle, making the learning process costly in terms of time and number of queries. In this paper, we propose a neuro-symbolic framework for automatic CA that significantly reduces user involvement by introducing neural Oracle Transformer models which learn to emulate user responses and to generalize conceptual knowledge. Trained on previously available examples, the learned oracle interacts with a dedicated CA engine, FastCA, which systematically refines the oracle's responses into a sound, consistent, and interpretable constraint network. This neuro-symbolic interaction enables the recovery of structured symbolic models from data without prior domain knowledge. Our results demonstrate that this neuro-symbolic interplay effectively aligns data-driven pattern recognition with symbolic reasoning, offering a robust approach to automating model construction in combinatorial domains.
1 Introduction
Constraint programming represents combinatorial problems with variables, domains, and constraints, but constructing those models remains time-consuming and expertise-intensive. The paper asks whether Transformers can learn constraint structure from examples and proposes neural oracles in a closed-loop system with a symbolic learner.
1 Introduction
- Constraint programming models combinatorial problems such as scheduling and planning with variables, domains, and constraints, while knowledge modeling remains a bottleneck.Choosing constraints requires domain expertise, time, and iterative refinement; constraint acquisition seeks to learn networks from labeled examples or oracle interaction.Source: §1 · p. 1
- Human oracles limit active constraint acquisition because they cannot reliably handle thousands of queries or multi-second delays.Prior strategies include reducing queries, parallelizing users, or automating the oracle where executable programs provide ground truth.Source: §1 · p. 2
- The paper asks whether Transformers can learn the abstractions, generalizations, and structural regularities humans use to model problems as constraints.Source: §1 · p. 2
- Neural oracles learn constraint structure from labeled examples and provide feedback to a symbolic learner in a closed-loop system.The authors report high accuracy in reconstructing constraint networks and robust generalization across unseen problem instances.Source: §1 · p. 2
2 Preliminaries
The preliminaries set out the learner, its vocabulary and candidate constraints, and how assignments and concepts relate to constraint networks. They also introduce local concepts and the oracle that can validate them.
2 Preliminaries
- A CA-learner acquires constraints from data using a vocabulary (X, D), where X is a finite variable set and D a finite domain, to form a network (X, D, C).Each constraint has a variable scope and relation; violating tuples complement the relation over the scope’s domain.Source: §2 · p. 2
- Full assignments give values to all n variables, while partial assignments give values to k variables; a full assignment satisfying every constraint is a solution.C entails C′ when sol(C) ⊆ sol(C′), and the networks are equivalent when their solution sets are equal.Source: §2 · p. 2
- The constraint language Γ specifies allowed relation types, while bias B is the finite set of candidate constraints considered for inclusion.For bounded arity k, |B| ≤ n^k t; for binary networks, |B| is bounded by n^2 t.Source: §2 · p. 3
- A general concept is a Boolean function over assignments, represented by a constraint network when its positive assignments equal that network’s solutions.Concept decomposition partitions a general concept into local concepts on subsets of variables, with each candidate constraint corresponding to a local concept.Source: §2 · p. 3
- An oracle knows the target concept’s local concepts and can answer validity questions without expressing them as constraints; local structure learning depends on a source that can validate those concepts.Source: §2 · p. 3
3 Transformer-Based Oracle
T-Oracle learns from labeled full and partial assignments to support autonomous constraint acquisition. Its Transformer architecture combines assignment and variable-position information with learned dependency signals, and its variants differ in the training assignments they use.
3.1 Architecture of T-Oracle
- Dual embeddings combine each assignment value, with 0 denoting unassigned, and variable position before Transformer layers, separating value from structural identity.Source: §3.1 · p. 4
- Cross-variable attention learns global variable dependencies, while value-level interactions flag assigned-value pairs as noteworthy when their interaction score is high.Source: §3.1 · pp. 4–5
- The model averages dependencies among assigned variables into S, then uses S and a learnable threshold to modulate the Transformer’s initial probability and suppress output at high S.Source: §3.1 · p. 5
3.2 Variants of the T-Oracle
- TO1 uses only full assignments, TO2 mixes full and partial assignments, and TO3 uses constraint-scope partial assignments and assumes partial knowledge of target constraints.Balanced positive and negative full-assignment examples can be infeasible, limiting TO1’s practicality; TO2 is designed to generalize from incomplete information.Source: §3.2 · p. 5
4 FastCA: A Time-Efficient CA Learner
FastCA is designed to reduce acquisition time and inter-query latency when queries to automated or neural oracles are inexpensive. It returns a network with the target’s solution set, with query complexity bounded by the bias size.
Description
- At each iteration, FastCA tests a constraint using a partial assignment and either removes it or invokes FindC to identify a valid constraint and eliminate candidates.In normalized CSPs, FindC identifies the target constraint with at most one query; an iteration uses at most two queries while removing one or two constraints.Source: §4 · p. 6
Theoretical Analysis
- FastCA terminates because each iteration removes at least one constraint from the finite bias, in at most |B| iterations.Source: §4 · p. 7
- FastCA returns a learned network L whose solution set equals that of the target network T.Source: §4 · p. 7
- O(nkt) queries suffice for bounded-arity k, reducing to O(n2t) for binary networks; FastCA also runs in time linear in the bias size.Source: §4 · p. 7
- FastCA remains stable with imperfect oracle feedback, although false positives can diminish recall and false negatives can retain redundant constraints and affect precision.Source: §4 · p. 7
5 Experiments
The experiments evaluate FastCA, three T-Oracle variants, and their pairings across varied combinatorial benchmarks. FastCA has the lowest average query time, while scope-aware TO3 paired with FastCA delivers the strongest reported acquisition performance.
5.1 Benchmark Problems
- The benchmarks span classical puzzles, random constraint networks, scheduling, and timetabling problems.The experiments also include Sudoku, JobShop, Murder, Zebra, ExamTT, and NurseR benchmarks.Source: §5 · p. 7, §5.1 · p. 8
5.2 Experimental Protocol
- Oracle training uses an 80/20 random train/test split; TO3 samples balanced positive and negative tuples per target constraint, with the sampling proportion θ ranging from 20% to 80%.Per-constraint balancing prevents rare relation types from being dominated by frequent ones.Source: §5.2 · p. 8
5.3 Results
- FastCA issues more queries than competing learners but achieves the lowest average query time and competitive total acquisition times; GrowAcq has the best overall query-count/runtime trade-off.The comparison reports query count, average query time, and total acquisition time.Source: §5.3 · p. 9, Table 1 · p. 10
- TO1 achieves perfect recall across benchmarks, while scope-aligned TO3 is stable, performs strongly on sparse-solution problems, and consistently outperforms TO2.TO2 performs worse on structurally complex and sparse-solution problems such as JobShop and Zebra.Source: §5.3 · p. 9, Table 2 · p. 10
- FastCA paired with TO3 achieves the highest performance, often reaching 100% across accuracy, recall, and precision, including on sparse-solution problems.FastCA/TO1 precision collapses to 0 across benchmarks; TO1 was trained only on complete assignments and cannot reliably judge partial assignments generated during acquisition.Source: §5.3 · pp. 9–10, Table 3 · p. 11
- TO3 exceeds 95% accuracy on binary constraints and often exceeds 98% on ternary and quaternary constraints.The evaluation samples balanced positive and negative tuples from integer domains of size 100.Source: §5.3 · pp. 11–12, Table 4 · p. 12
6 Conclusion
The paper presents an automated constraint acquisition framework combining a Transformer-based oracle with the FastCA symbolic learner. It identifies large-scale exhaustive search as a remaining scalability question.
6 Conclusion
- The framework integrates a Transformer-based oracle, T-Oracle, with the FastCA symbolic learner for automated constraint acquisition.The conclusion describes this as the first integration of these components.Source: §6 · p. 12
- TO3, trained on localized constraint-level data, captures latent combinatorial-problem semantics and guides FastCA’s exhaustive search.The conclusion says this pairing is resilient to incorrectly classified examples that can destabilize sequential learners.Source: §6 · p. 12
- The framework supports interpretable, data-driven model construction without a human oracle, but its scalability to extremely large domains remains to be assessed.Exhaustive search may become computationally expensive at that scale.Source: §6 · p. 12