PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Differentiable Logic Gate Networks

Felix Petersen, Christian Borgelt, Hilde Kuehne, Oliver Deussen

arXiv:2210.08277v1cs.LG

TL;DR

Logic gate networks offer fast computation, but their discrete gates are conventionally non-differentiable and cannot be trained with standard gradient descent. This paper uses real-valued logic and continuous relaxation to train gate choices, then discretizes the network; the resulting models achieve very fast inference, including over a million MNIST images per second on one CPU core.

  • Problem

    Logic gate networks use discrete, non-differentiable components, limiting conventional gradient-descent training; gradient-free evolutionary training becomes infeasible for larger models.

    Source: §1 · p. 1

  • Method

    The method uses real-valued logic and a continuous relaxation that learns a gate distribution for each neuron, then selects the most probable gate after training.

    Source: §1 · pp. 1–2

  • Results

    Beyond a million MNIST images per second at >97.5% accuracy is reported on a single CPU core, with inference around two orders of magnitude faster than fully connected ReLU networks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The discretized gate-only networks provide fast inference, with the paper reporting efficiency improvements of one or more orders of magnitude for their accuracy level.

    Source: §1 · p. 2, §7 · p. 10

    Training costs more than performance-comparable conventional neural networks because multiple differentiable operators are evaluated per neuron, although the networks are asymptotically cheaper to train due to sparsity.

    Source: §5 · pp. 6–7

Abstract

from arXiv · show

Recently, research has increasingly focused on developing efficient neural network architectures. In this work, we explore logic gate networks for machine learning tasks by learning combinations of logic gates. These networks comprise logic gates such as "AND" and "XOR", which allow for very fast execution. The difficulty in learning logic gate networks is that they are conventionally non-differentiable and therefore do not allow training with gradient descent. Thus, to allow for effective training, we propose differentiable logic gate networks, an architecture that combines real-valued logics and a continuously parameterized relaxation of the network. The resulting discretized logic gate networks achieve fast inference speeds, e.g., beyond a million images of MNIST per second on a single CPU core.

1 Introduction

The paper targets faster neural-network inference by training logic gate networks, whose discrete gates are conventionally non-differentiable. It relaxes gate choices for gradient-based training, then discretizes the network for fast execution.

1 Introduction

  • Logic gates such as AND and XOR are attractive for efficient computation, but their non-differentiability conventionally prevents gradient-descent training.Evolutionary training is mentioned as an alternative that works for small models but becomes infeasible for larger ones.Source: §1 · p. 1
  • The proposed relaxation learns a probability distribution over logic gates at each neuron, then discretizes the trained network by selecting each neuron's most probable gate.The resulting gate-only network has two inputs per neuron and is intrinsically sparse.Source: §1 · p. 1
  • Unlike binary neural networks, logic gate networks have no weights and learn gate operators while their pseudo-randomly initialized connections remain fixed.The paper describes the 16 possible two-input Boolean functions as encodable in 4 bits per neuron.Source: §1 · pp. 1–2
  • Beyond a million MNIST images per second at >97.5% accuracy is reported on a single CPU core; inference is around two orders of magnitude faster than fully connected ReLU networks.The paper also reports more than 12× the speed of the best binary neural networks and 2–3 orders of magnitude over theoretical sparse-network speed.Source: §1 · p. 2

2 Related Work

Related work spans differentiable logics, continuous relaxations, and methods for learning sparse or operator-based networks. The paper distinguishes its approach by learning gate operators at fixed connections rather than learning connectivity or translating conventional models.

Related work

  • Prior logic-learning work includes memorization with binary lookup tables [14] and translating trained networks into AND-Inverter gate networks [15].The memorization method reports 90% test accuracy on a binary MNIST task; the translated networks are discussed for clinical decision-making.Source: §2 · p. 3
  • The paper places its approach alongside continuous relaxations of discrete structures and differentiable real-valued logics, while distinguishing relaxation of a logic network itself from relaxation of a fixed structure.The related-work discussion also describes fuzzy and infinite-valued logics,,, and Van et al. [13].Source: §2 · pp. 2–3
  • Differentiable logic networks relax which operator is applied at each node while keeping connections predefined, unlike methods that relax connectivity or select inputs to predefined operators.The cited contrasts include differentiable logic machines [24] and Gumbel-Max Equation Learner Networks [25].Source: §2 · p. 3
  • Binary neural networks approximate floating-point operations with binary weights and activations, whereas logic gate networks have no weights and learn logical operations directly.The paper includes binary neural networks as baselines because they achieve high inference speed.Source: §2 · pp. 3–4
  • The paper uses randomly initialized, fixed connections in its sparse-by-definition networks, drawing on prior findings about randomized fixed sparse connections.Sparse-network literature more commonly focuses on selecting connections or distilling sparse models from dense ones.Source: §2 · p. 4

3 Logic Gate Networks

Logic gate networks process binary inputs through two-input logic gates, with the gate choice rather than weights parameterizing each neuron. Multiple outputs per class are summed to produce graded class scores.

3 Logic Gate Networks

  • Each neuron is a two-input binary logic gate, and the network is parameterized by gate choice rather than weights.The gates' outputs feed downstream layers; each neuron has two inputs rather than connections to every neuron in the previous layer.Source: §3 · p. 4
  • Bit-wise logic operations make execution efficient, and the gates are intrinsically nonlinear, so the networks need no activation functions.The networks are sparse because each neuron has only two inputs.Source: §3 · p. 4
  • Multiple neurons per class contribute separate evidence whose summed outputs provide graded predictions instead of only binary class scores.The number of score levels corresponds to the number of neurons per class.Source: §3 · p. 4

4 Differentiable Logic Gate Networks

The section makes logic-gate networks trainable with gradient descent by relaxing binary activations and gates, then uses discretization and implementation choices to support fast inference.

4 Differentiable Logic Gate Networks

  • Probabilistic real-valued logic relaxes binary activations and gate operations, making logic-gate networks differentiable for gradient-based training.The paper uses the probabilistic interpretation of the gate operators.Source: §4 · pp. 4–5
  • Each neuron learns a probability distribution over 16 gate operators and combines their relaxed outputs during training.The operator probabilities are produced by applying softmax to 16 learned values.Source: §4 · p. 5
  • Grouped output neurons support graded classification scores and regression outputs by summing their activations or probabilities.For classification, groups correspond to classes; regression uses an affine transformation to adjust the output range.Source: §4 · p. 5, §4.1 · pp. 5–6

4.1 Training Considerations

  • After training, taking each operator distribution's mode yields Boolean inference, with an MNIST accuracy gap below 0.1%.Training uses randomly initialized connections and neuron parameters; reported models use 4–8 layers and Adam at a constant learning rate of 0.01.Source: §4.1 · p. 5

4.2 Remarks

  • Packing batch Boolean values into larger integer types enables bitwise inference, while logic-gate adders aggregate outputs without writing all outputs to memory.For int64, the method batches 64 data points into an integer.Source: §4.2 · p. 6
  • Reproducible pseudo-random connections reduce storage to 4 bits per neuron, while pruning can trade greater speed for storing connections.The paper also notes that pruning unused neurons or simplifying logical expressions requires storing those connections.Source: §4.2 · p. 6
  • The full 16-operator set performed better than reduced sets; float16 did not degrade training, and Adam improved training over SGD variants for deeper networks.All reported results used float32 training.Source: §4.2 · p. 6

5 Current Limitations and Opportunities

Differentiable logic-gate networks have higher practical training cost than comparable conventional networks, although their asymptotic training cost is lower due to sparsity. The paper points to implementation improvements and small, inference-focused deployments as relevant opportunities.

5 Current Limitations and Opportunities

  • Training costs more in practice than for performance-comparable conventional networks because each neuron evaluates multiple differentiable operators.Most operators in differentiable form require floating-point multiplications; improved implementations could reduce practical cost.Source: §5 · p. 6
  • Despite higher practical cost, differentiable logic-gate networks are asymptotically cheaper to train than conventional networks due to sparsity.Source: §5 · p. 7
  • Convolutional logic-gate networks and components such as residual connections remain future research directions.Source: §5 · p. 7
  • Small architectures may suit edge and embedded settings, where training occurs before deployment; other applications may also have negligible training cost relative to inference.Source: §5 · p. 7

6 Experiments1

The experiments compare accuracy, memory footprint, and inference speed across tabular and image datasets, then inspect the distribution of learned logic gates.

6 Experiments1

  • The experiments assess accuracy, memory footprint, and evaluation speed on MONK, Adult, Breast Cancer, MNIST, and CIFAR-10.The image-recognition benchmarks are MNIST and CIFAR-10.Source: §6 · p. 7

6.1 MONK’s Problems

  • On all three MONK datasets, the method beats logistic regression and, on noisy MONK-3, also outperforms the much larger neural network.Table 2 reports results averaged over 10 runs, with inference time per data point on one CPU thread.Source: §6.1 · p. 7, Table 2 · p. 7

6.2 Adult and Breast Cancer

  • On Adult, the method performs similarly to neural networks and logistic regression while inferring much faster; on Breast Cancer, it achieves the best performance and remains the fastest model.Table 3 reports results averaged over 10 runs.Source: Table 3 · p. 7, §6.2 · p. 8

6.3 MNIST

  • On MNIST, the logic network outperforms FINN, the fastest method achieving at least 98.4% accuracy, while requiring less than 10% of its binary operations and running 12× faster on an A6000 GPU.The comparison is with FINN on specialized FPGA hardware; the logic model uses only 7% of the GPU.Source: §6.3 · p. 8, Table 4 · p. 8

6.4 CIFAR-10

  • On CIFAR-10, the method outperforms neural networks by a small margin with 4-value color channels and by a large margin in a larger model, using less than 0.1% and less than 1% of their memory footprints, respectively.Against the best fully connected baselines, it does not match performance, though it is smaller and uses fewer data; the largest such baseline is only 3.7% more accurate than the largest logic model.Source: §6.4 · p. 8, Table 5 · p. 9
  • On CIFAR-10, the largest logic model uses 5 million bitwise operations, while a student-teacher baseline uses 2 million floating-point operations; the latter is around 100× slower on hardware-accelerated integrated circuits.Sparse baselines around 75% accuracy require substantially more expensive inference, and two ResNet32 sparsification methods achieve only around 37% accuracy.Source: §6.4 · p. 9, Table 5 · p. 9
  • CIFAR-10 results in parentheses are estimated when compilation did not finish or compiler limitations prevented compiling the largest GPU models.The cited compiler implementation has compilation time quadratic in the number of code lines or statements.Source: §6.4 · p. 9, Table 5 · p. 9

6.5 Distribution of Logic Gates

  • In a trained four-layer CIFAR-10 network, middle layers favor direct-connection operators, while the last layer most often uses XOR and XNOR; implications are infrequent.The first layer shows more AND, NAND, OR, and NOR operators; constant 0/1 operators are rare and absent from the last layer.Source: §6.5 · p. 9, Figure 2 · p. 10

7 Conclusion

The paper presents a way to train logic gate networks using real-valued logics and continuous relaxations via softmax, reporting high efficiency for their accuracy and plans to release the code.

7 Conclusion

  • For their level of accuracy, the trained networks are one or more orders of magnitude more efficient than the state-of-the-art.The approach uses real-valued logics and continuous relaxations via softmax.Source: §7 · p. 10
  • Real-valued logics and continuous relaxations via softmax form the proposed approach to training logic gate networks.Source: §7 · p. 10
  • The authors plan to release the source code to foster future research on learning logic gate networks.Source: §7 · p. 10

A Implementation Details

The implementation provides PyTorch-compatible backends and converts trained logic gate networks into optimized C or CUDA binaries for deployment.

A Implementation Details

  • The library supports pure PyTorch and native CUDA backends, with the native CUDA implementation up to 50× faster than pure PyTorch.Both backends are usable in PyTorch; the distinction is the backend.Source: A Implementation Details · p. 14
  • For inference, the library automatically converts trained logic gate networks into optimized C or CUDA binaries callable from Python or other languages supporting shared-object binaries.Source: A Implementation Details · p. 14
  • The authors plan to release a PyTorch-based library with the experiments for reproducibility.Source: A Implementation Details · p. 14

A.1 Model Architectures and Hyperparameters

The experiments use straight architectures and grid-search depth and width; the appendix also describes training settings and optional output aggregation with logic-gate adders.

A.1 Model Architectures and Hyperparameters

  • The architecture search used straight networks, grid-searching 2–10 layers and neurons per layer at a factor-of-two resolution.Tables 6 and 7 list layer and neuron counts for the logic-gate and neural-network architectures.Source: §A.1 · p. 14, Table 6 · p. 14, Table 7 · p. 14
  • Models used Adam and were trained for up to 200 epochs with batch size 100; logic-gate networks used learning rate 0.01 versus 0.001 for neural networks.Source: §A.1 · p. 14
  • Softmax temperature was grid-searched over {1, 1/0.3, 1/0.1, 1/0.03, 1/0.01}, except for Adult, with larger temperatures used when there are more outputs per class.Source: §A.1 · p. 14

A.2 Aggregating Predictions via Logic Gate Network Adders

  • After learning, class output bits can be aggregated into binary numbers with fixed logic-gate adders to reduce memory bandwidth.The aggregation is described as faster than storing unaggregated results in VRAM.Source: §A.2 · p. 15

A.3 Training Times & Standard Deviations

The appendix reports training times for MNIST and CIFAR-10, includes accuracy standard deviations, and introduces further discussion of fast-network baselines.

A.3 Training Times & Standard Deviations

  • Training times are provided for the MNIST and CIFAR-10 models, alongside accuracy standard deviations.Tables 8 and 9 cover training times and standard deviations for MNIST and CIFAR-10, respectively.Source: §A.3 · p. 15, Table 8 · p. 15, Table 9 · p. 15
  • The reported training times use the code version from the original experiments, while a substantially faster implementation is planned for public release.Source: §A.3 · p. 15

B Additional Discussion of Baselines

B.1 Binary Neural Networks

This section surveys binary neural networks and FPGA-based classifiers, highlighting reported MNIST speeds and accuracies across specialized hardware and logic-gate approaches.

B.1 Binary Neural Networks

  • 1,561,000 images per second at 98.4% accuracy is reported for FINN on specialized FPGA hardware.The survey identifies it as the fastest method for classifying MNIST among those discussed.Source: §B.1 · p. 15
  • FPGAs are configurable processors for high-speed execution of predefined logic-gate tasks, including applications with limited complexity.Source: §B.1 · p. 15
  • 330,000 images per second at 98.29% accuracy and 20,000 images per second at 98.4% accuracy are reported for two other FPGA MNIST systems.The first result is attributed to Ghasemzadeh et al.; the second to Jokic et al.Source: §B.1 · p. 15
  • LBNNs reach 99.2% MNIST accuracy at 6,580 images per second, while analog logic-gate networks report accuracies up to 89%.Source: §B.1 · p. 16

B.2 Sparse Neural Networks

The section reviews sparse-network comparisons and design choices, including depth limits, randomized connections, operator-set size, and real-valued logic operators.

B.2 Sparse Neural Networks

  • 98.08% MNIST accuracy is reported at 98.5% sparsity; L0-regularized models report 98.6% accuracy at around 2 · 10^5 FLOPs, or roughly 2/3 sparsity.Source: §B.2 · p. 16
  • 99.9% sparsity corresponds to around 140 kFLOPs for ProbMask’s smallest ResNet32; the authors describe their much smaller models as competitive.This is the only cited work in the passage reporting architectures this sparse.Source: §B.2 · p. 16
  • At 32× theoretical speedup, surveyed CIFAR-10 VGG methods fall below 70% test accuracy; sparse-cost comparisons assume 1,000 binary OPs per sparse float32 FLOP.The passage describes this conversion as a conservative estimate favoring sparse float32 models; practical sparse execution may add 10–100× overhead.Source: §B.2 · p. 16
  • Sparse evolutionary training reports 74.84% CIFAR-10 accuracy with 278,630 parameters and 98.74% MNIST accuracy with 89,797 parameters; its evaluation is estimated to be orders of magnitude more expensive.Source: §B.2 · p. 16

C.1 Depth vs. Accuracy Trade-off

  • Vanishing gradients begin to hinder efficient training at around 8–10 layers, a depth range similar to regular networks without residual connections or batch normalization.Source: §C.1 · p. 16

C.2 On the Effectiveness of Randomized Sparse Connections

  • Random connections are canonical, and selection method does not substantially affect performance unless only neighboring pairs are chosen; hardware-oriented patterns may improve memory access.Fixed connectivity avoids the added complexity of relaxing connectivity during training; heuristic updates after training could in principle improve performance.Source: §C.2 · p. 17

C.3 Ternary and Other Additional Operators

  • Ternary gates yield 256 possible operators; larger operator sets risk vanishing probabilities and require more costly relaxed-operator computations, aggregation, and derivatives.Source: §C.3 · p. 17

D Differentiable Logics: T-Norms and T-Conorms

  • Real-valued T-norms and T-conorms generalize AND and OR; the paper uses the probabilistic pair and excludes the drastic T-conorm for occlusion because it yields no useful gradients.The passage describes T-norms and T-conorms as axiomatic generalizations of conjunction and disjunction.Source: D Differentiable Logics: T-Norms and… · pp. 17–18

Related papers

Loading 2210.08277v1…