cs.LGFeb 19, 2026

Learning with Boolean threshold functions

Authors: Veit Elser, Manish Krishan Lal

Organizations: Department of Physics, Cornell · Mathematics, Independent Researcher, India

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We develop a method for training neural networks on Boolean data in which the values at all nodes are strictly ±1\pm 1, and the resulting models are typically equivalent to networks whose nonzero weights are also ±1\pm 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\pm 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+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 ( xx ), blue disks are neuron outputs ( yy ), and green lines are weights ( ww ). 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 zz (blue) in the limit of small β\beta when the problem is locally feasible (left) and locally infeasible (right). AA and BB can locally be approximated as affine and are rendered as the red ( AA ) and green ( BB ) 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→66\to 12\to 12\to 12\to 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,5k=3,4,5 .
Figure 11: Generic (left) and transformed (right) data vectors (rows) for the k=5k=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 σ\sigma 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\sigma=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 10610^{6} 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.

Explore similar work

CardsList

  1. A Learning Algorithm for Threshold Boolean Networks with Prescribed Fixed Points

    Aug 18, 2026Gonzalo A. RuzBoolean Function LearningGene Regulatory Network Inference

    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

  2. Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming

    Oct 14, 2026Thomas Pammer, Johannes Fürnkranz, Markus SinnlBoolean Function LearningInterpretable ML

    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

  3. Task-Aware Discretization of Differentiable Logic Gate Networks

    Sep 27, 2026Thore GerlachEfficient Neural Network Inference

    Independent Researcher