We develop a method for training neural networks on Boolean data in which the values at all nodes are strictly ±1, and the resulting models are typically equivalent to networks whose nonzero weights are also ±1. The method replaces loss minimization with a nonconvex constraint formulation. Each node implements a Boolean threshold function (BTF), and training is expressed through a divide-and-concur decomposition into two complementary constraints: one enforces local BTF consistency between inputs, weights, and output; the other imposes architectural concurrence, equating neuron outputs with downstream inputs and enforcing weight equality across training-data instantiations of the network. The reflect-reflect-relax (RRR) projection algorithm is used to reconcile these constraints. Each BTF constraint includes a lower bound on the margin. When this bound is sufficiently large, the learned representations are provably sparse and equivalent to networks composed of simple logical gates with ±1 weights. Across a range of tasks -- including multiplier-circuit discovery, binary autoencoding, logic-network inference, and cellular automata learning -- the method achieves exact solutions or strong generalization in regimes where standard gradient-based methods struggle. These results demonstrate that projection-based constraint satisfaction provides a viable and conceptually distinct foundation for learning in discrete neural systems, with implications for interpretability and efficient inference.
Figures & tables
Figure 1: Two 5-layer random logic circuits where each node either copies a value from the layer below (isolated colored lines) or applies a logical gate to them (colored groups). The gates are either 2-input And/Or (left circuit) or 3-input Maj (right circuit). The colors (red/blue) of the highlighted edges indicate whether or not negation is applied. The blue node in the left circuit means this BTF is taking input from the constant node with weight +1 , thereby choosing to implement And .
Figure 2: Evolution of the training and test accuracies when training on 128, 256, 384, and 512 data generated by the random logic networks above. Learning the random And/Or data (left plot) is easier, but 256 data appear to be sufficient to learn both types of data, given sufficient iterations of the algorithm.
Figure 3: Same evolution of learning curves as in Figure 2 but for the gradient-descent method.
Figure 4: Distribution of network weights after training on the two types of random logic data (left: And/Or , right: Maj ). The lower histograms show the weights in just the first layer of each network.
Figure 5: Divide-and-concur variable groupings in BTF networks. Red lines are neuron inputs ( x ), blue disks are neuron outputs ( y ), and green lines are weights ( w ). On the left, the highlighted fan-in shows all the variables in one BTF constraint. On the right, the highlighted fan-out show the concur between neuron outputs and inputs.
Figure 6: Local behavior of the iterate z (blue) in the limit of small β when the problem is locally feasible (left) and locally infeasible (right). A and B can locally be approximated as affine and are rendered as the red ( A ) and green ( B ) rods in this cartoon.
Figure 7: Evolution of the gap (left) and weights (right) during training of a simple binary multiplier circuit. Though the evolution of the weights is chaotic, the values in the solution (when the gap is very small) are quite simple.
Figure 8: A three-layer 2-bit multiplier circuit found using boolearn . There are eight And gates (blue nodes), one Or (red node), and three Not s (red arrows).
Figure 9: The gap for learning the 3-bit multiplication table goes to zero for the 6→12→12→12→6 architecture but remains positive when one layer of hidden nodes is removed.
Figure 10: Evolution of the gaps (left) and training accuracies (right) in the binary autoencoder problem for k=3,4,5 .
Figure 11: Generic (left) and transformed (right) data vectors (rows) for the k=5 binary autoencoder problem.
Figure 12: The gap when training a generator of MNIST 4’s from just 16 1-hot codewords.
Figure 13: The 16 archetype 4’s generated by the 1-hot codeword model when trained on 1024 examples. The images are ranked by frequency, from top-left (highest) to bottom right (lowest).
Figure 14: Down-sampled MNIST digits 1 .
Figure 15: Effect of the σ hyperparameter on the gap when learning to classify MNIST data for various numbers of training items.
Figure 16: Detail of the classification-accuracies corresponding to the training runs in Figure 15 .
Figure 17: The learned MNIST weights for the ten digit classes (in the same order as the samples in Figure 14 ) when training on 2048 items with σ=1 . Blue/red denote positive/negative values.
Figure 18: Minimum value of the gap achieved with increasing iterations for the 5-layer Copy/And/Or circuit data. On the left is shown the evolution with increasing data in the under-constrained case. As shown on the right, the evolution changes character in the over-constrained case.
Figure 19: Evolution of train/test accuracies for learning one step of the rule-30 automaton. The constraint-based results are on the left, gradient-descent with sparsity enhancement is on the right. Both methods used 106 steps/iterations.
Figure 20: By thresholding weights by magnitude, to identify the relevant BTF inputs, one can see rule-30 implemented in various ways.
Figure 21: Same as Figure 19 but for data derived from two steps of rule-30.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 22: Near reproducibility of the evolution of the minimum gap (left) and training accuracy (center) with iterations, in three runs of the RRR training algorithm differing only in the initialization. The right panel compares training and test accuracies. The same 512 data items derived from the circuit in Figure 1 were used in all runs.
Figure 23: Same as Figure 22 but showing the batch-size dependence when training in batch mode. The runs with batch sizes 256, 128 and 64 were allowed 2, 4 and 8 times, respectively, as many iterations as the run in which all 512 data were processed in each iteration. All runs completed in the same amount of time (in our serial implementation) because the smaller batch sizes use less time per iteration.
We present a learning algorithm for inferring threshold Boolean networks (TBNs) with a prescribed set of fixed points. The proposed method employs a custom differentiable loss function that jointly enforces fixed point preservation, penalizes spurious attractors, encourages binary outputs, and promotes sparsity through L1 regularization. Applied to the FOS-GRN model of Arabidopsis thaliana, the approach achieved perfect reconstruction (i.e., all 10 desired fixed points and no spurious ones) in 5 out of 30 independent runs, recovering on average 8.53 ± 0.90 correct fixed points with no spurious attractors. In contrast, standard methods such as the Perceptron and Logistic Regression recovered up to 10 fixed points but introduced between 8 and 31 spurious ones. An additional analysis varying the sparsity coefficient (λ) confirmed that the method's performance and the structural properties of the inferred networks remain robust within a practical range (up to 0.01) of regularization strengths. Overall, the results demonstrate the effectiveness and stability of the proposed algorithm in capturing meaningful network dynamics under prescribed dynamical constraints.
Gonzalo A. Ruz
Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile · Millennium Nucleus for Social Data Science (SODAS), Santiago, Chile · Millennium Nucleus in Data Science for Plant Resilience (PhytoLearning), Santiago, Chile +1
We study the problem of learning accurate and cognitively simple binary classifiers that are directly interpretable as Boolean rules. We propose mixed integer linear programming (MILP) formulations for training sparse disjunctive normal form (DNF) networks, viewed as small networks with a conjunctive hidden layer and a disjunctive output layer. Contrary to previous work that uses MILP for inductive rule learning, we start with a fixed network structure, for which we then find optimal weights. A regularized objective explicitly trades off misclassification costs against sparsity, yielding globally optimized rule sets. Our main technical contribution is an enhanced formulation that substantially reduces the number of integer decision variables and eliminates redundant constraints, while preserving exact Boolean semantics for all feasible solutions. Furthermore, we develop a combined approach based on initialization and dropout to break symmetries in the weights between rules, mitigating redundancy, and encouraging more diverse and stable rule representations. Experiments on synthetic benchmarks and UCI datasets show that the advanced formulation improves computational efficiency and achieves competitive or superior accuracy compared to established interpretable baselines, including SAT-based DNF learning and well-known rule- and tree-based learners. Overall, our approach provides a principled optimization framework for learning compact Boolean rule sets with explicit control over accuracy and sparsity trade-offs.
Thomas Pammer, Johannes Fürnkranz, Markus Sinnl
Institute for Application-Oriented Knowledge Processing (FAW), Johannes Kepler University Linz, Austria · LIT AI Lab, Johannes Kepler University Linz, Austria · Institute of Business Analytics & Technology Transformation/JKU Business School, Johannes Kepler University Linz, Austria
Differentiable logic gate networks (DLGNs) enable gradient-based training of highly efficient Boolean networks by relaxing discrete logic gates during training and discretizing them for inference. Standard approaches make this discretization decision locally, typically through argmax selection and confidence- or entropy-based convergence criteria. We show that local discretization can be task-suboptimal even for globally optimal relaxed solutions, with high gate confidence providing no general guarantee, and derive bounds relating task-aware gate selection to tractable interventions in the relaxed network. Motivated by these results, we study first-order downstream task information for progressive discretization and characterize when this local approximation is reliable. Experiments on convolutional DLGNs reveal a strong locality dependence: first-order scores become unreliable when directly optimized over nonlocal interventions, but accurately assess local argmax decisions for progressive freezing.