Synthetic Neurosymbolic Task Generation with Controlled Constraint Complexity

Mykhailo Buleshnyi, Zsolt Zombori, Michael Benedikt

This paper introduces NeSySy, an open-source synthetic benchmark generator designed to stress-test neurosymbolic (NeSy) AI systems. By leveraging industrial-strength logic solvers, NeSySy allows researchers to generate datasets with precisely tuned logical complexity, providing a much-needed "micro-benchmarking" tool for a field that has historically relied on fixed or overly simplistic datasets.

TL;DR

NeSySy is a synthetic task generator that uses SAT/SMT solvers to create neurosymbolic benchmarks with controllable logical complexity. It enables researchers to systematically evaluate how neural networks interact with symbolic constraints, revealing that expressive unconstrained models can often learn logical structures directly from data as effectively as specialized constraint-enforcement layers.

What Problem Does This Paper Address?

Neurosymbolic AI aims to marry the perception of neural networks with the reasoning of symbolic logic. However, the field’s progress is hampered by a lack of diverse, scalable benchmarks. Existing datasets usually fall into two traps:

  1. Manual Curation: Real-world datasets like Road-R have fixed, relatively simple constraints (e.g., "an object cannot be both a car and a pedestrian").
  2. Oversimplification: Synthetic benchmarks like MNISTadd (summing handwritten digits) are often too easy, as the underlying task reduces to independent classification.

There is no standard way to "turn the knob" on logical difficulty—such as increasing the number of constraints or making them dependent on the input—to see where current NeSy models break. NeSySy fills this gap by providing fine-grained control over constraint structure, tightness, and data alignment.

Methods

NeSySy follows a three-step pipeline to generate a task:

  1. Constraint Generation: It generates a "propositional skeleton" (using CNFgen) and can substitute atoms with linear real-arithmetic inequalities. It uses the Z3 SMT solver to certify that these constraints are satisfiable for all possible inputs.
  2. Generator Mapping: A neural network is trained to act as a "generator," mapping inputs to a diverse range of outputs that roughly follow the desired logic.
  3. Dataset Alignment (The "Repair" Step): To ensure every sample in the final dataset is 100% consistent with the logic, NeSySy uses constrained optimizers (RC2 for MaxSAT or Z3 for OMT). If a generated sample violates a constraint, the solver "repairs" it by finding the nearest valid output (e.g., flipping the fewest bits for Boolean tasks).

The system supports two primary NeSy scenarios: Learning with Constraints (where logic restricts admissible predictions) and Learning from Distant Supervision (where the model must learn latent variables from high-level query answers).

Datasets

NeSySy is a generator rather than a static dataset. However, the authors evaluate it against established benchmarks and use it to create various challenges:

  • Comparison Benchmarks: Road-R, MNISTadd, and Rsbench.
  • Generated Tasks: The authors generated thousands of tasks varying the clause-to-variable ratio (cvr), the number of input-dependent regions, and the alignment strategy (filtering vs. fixing).

Key Insights and Ideas

  • The "Phase Transition" of Difficulty: For Boolean tasks, the hardest problems occur at an intermediate constraint density (cvr ≈ 2). If constraints are too sparse, the model ignores them; if they are too dense, the "feasible" space becomes so small that the task becomes trivial.
  • Fixing is Harder than Filtering: When generating data, "fixing" (repairing) inconsistent samples creates a much harder learning task than "filtering" (discarding them). Fixing pushes data points to the boundaries of the feasible region, forcing the model to learn more complex decision boundaries.
  • Expressivity vs. Enforcement: One of the most surprising findings is that a standard, expressive sequential model (BaseSeq) often outperforms specialized "constraint-aware" layers (like CCN+ or DRL). This suggests that given enough capacity, neural networks can learn to respect logical structure implicitly from data.
  • Solver-Based Repair Wins: At inference time, using an exact solver to "fix" a neural network's prediction (BaseSolver) consistently outperformed heuristic differentiable correction layers.

Key Results

  • Accuracy Gains: On Boolean tasks, the BaseSeq model achieved the highest accuracy gains (up to +7.48% over a standard baseline) while maintaining near-zero constraint violations.
  • Distant Supervision: In scenarios with latent variables, DeepProbLog significantly outperformed pure neural baselines, particularly when the neural components had low capacity or the constraints were highly informative.
  • Scalability: While some differentiable layers (like BaseDRL) failed to scale beyond simple constraints, the solver-based repair approach handled all tested configurations.

Limitations and Future Work

  • Data Types: NeSySy currently supports Boolean and real-valued variables but lacks support for integer data types (e.g., Presburger arithmetic).
  • Multi-Input Constraints: The system generates constraints for individual samples. It does not yet support constraints that relate multiple inputs, which are essential for tasks involving fairness or temporal/sequential data.
  • Theoretical Gap: While the authors identified clear empirical trends in task difficulty, they note that a formal theory linking these syntactic parameters to machine learning complexity (like VC dimension) is still missing.

Summary updated

Abstract

We introduce NeSySy, a synthetic generator for neurosymbolic learning tasks that jointly produces logical constraints and consistent datasets. Unlike existing benchmarks, NeSySy provides fine-grained control over key properties such as constraint structure, tightness, input dependence, and data generation and alignment strategies. In particular, it allows the use of rich constraints over infinite domains, and uses solvers to ensure that the constraints are meaningful and that generated samples satisfy the constraints. We design NeSySy to support both learning with declarative constraints and learning from distant supervision. Across a range of constraint families, we provide evidence that its parameters induce systematic and largely independent effects on task difficulty. Using NeSySy, we study constraint-aware learning methods, identifying regimes where explicit constraint enforcement is beneficial and where expressive unconstrained models can instead learn constraint structure directly from data. Our results establish NeSySy as a controlled testbed for analysing the interaction between learning and logical structure. NeSySy is built around a pipeline that incorporates solvers. Satisfiability checkers (CNFgen and Z3) generate and certify constraints. Constrained optimizers (RC2 for MaxSAT, Z3 for OMT) compute optimal repairs that guarantee every generated sample is consistent.
BibTeX
@misc{buleshnyi2026synthetic,
  author = {Mykhailo Buleshnyi and Zsolt Zombori and Michael Benedikt},
  title = {{Synthetic Neurosymbolic Task Generation with Controlled Constraint Complexity}},
  year = {2026},
  eprint = {2611.19597},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19597},
}
Figure