Deep Differentiable Logic Gate Networks
Authors: Felix Petersen
Christian Borgelt
Hilde Kuehne
Oliver Deussen
Venue: NeurIPS 2022 Accept (2022)
Keywords: logic gate
logic operator
differentiable
relaxation
continuous
fast inference

Abstract: 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.

Deep Differentiable Logic Gate Networks
Felix Petersen
Christian Borgelt
Stanford University
University of Salzburg
University of Konstanz
christian@borgell net
meiilfellix-peersen.dee
Hilde Kuehne
Oliver Deussen
University of Frankfurt
University of Konstanz oliver dwussen@uni. kn
MIT-IBM Watson Al Lab
Tuehne@uni-frankfurr.
Abstract
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 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 continuously parameterized relaxation of the network. The resulting discretized logic gate networks achieve fast inference speeds, e.g., beyond million images of MNIST per second on a single CPU core.
Introduction
With the success of neural networks, there has also always been strong interest in research and industry in making the respective computations as fast and efficient as possible, especially at inference time. Various techniques have been proposed solve this problem, including reduced computational precision []. 2] binary (3) and sparse [4] neural nets. In this work, we want to train a different kind
of architecture, which is well known in the domain of computer architectures: logic (gate) networks.
The problem in training networks of discrete components like logic gates, is that they are non- differentiable and therefore, conventionally, cannot be optimized via standard methods such as gradient descent [5]. One approach for this would be gradient-free optimization methods such as evolutionary training 6 71. which works for small models, but becomes infeasible for larger ones.
In this work, we propose an approach for gradient training of logic gate networks (aka. arith- metic/ / algebraic circuits [8]. (9). Logic gate networks are based on binary logic gates, such as "and" and "xor" (see T.. For training logic gate networks, we continuously relax them differentiable logic gate networks, which allows efficiently training them with gradient descent. For this, we use real-valued logic and learn which logic gate to use at each neuron. Specifically, for each neuron, we learn probability distribution over logic gates. After training, the resulting network is discretized to (hard) logic gate network by choosing the logic gate with the highest probability. As the (hard) logic gate network comprises logic gates only, it can be executed very fast. Additionally, as the logic gates are binary, every neuron logic gate has only 2 inputs, and the networks are extremely sparse.
Logic gate networks are not binary neural networks: binary neural networks are form of low precision (wrt. weights and/or activations) neural networks, as they reduce weights and/or activations to binary precision. Binary neural networks are usually dense and typically rely on weights trained in
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

3% and
2%
72% xor
9%
1% false
nand
true
Panda
Gibbon
Figure Overview the proposed differentiable logic gate networks: pixels the image are converted into Boolean valued inputs, which are processed by a layer of neurons such that each neuron receives two inputs. The connectivity of neurons remains fixed after an initial beeudo-radoo initialization. Each neuron is continuously parameterized by distribution over logical operators. During training, this distribution is learned for each neuron, and, during inference, the most likely operator used for cach neuron. There are multiple outputs per class, which are aggregated by bit-counting, which yiclds the class scores. The number of neurons in the visualization is greatly reduced for visual simplicity.
the continuous domain and are discretized afterwards. In contrast to binary neural networks, logic gate networks do not have weights, are intrinsically sparse as they have only 2 inputs to each neuron, and are not form of low precision (wrt. weights and/or activations) neural networks.
They also differ from current sparse neural network approaches, as our goal to learn which logic gate operators are present at each neuron, while the (weightless) connections between neurons brandomlyy initialized and remain fixed. The network is, thus, parameterized by the choice of the logic gate operator binary function for each neuron. As there total of 16 functions of signature f: {0, 1 x 1] - {0, 1}. the information which operation a neuron executes can be encoded in just bits. The objective is learn which of those operations optimal for each neuron. Specifically, for each neuron, we learn a probability distribution over possible logic gates, which we parameterize via softmax. We find that this approach allows learning logic gate networks very effectively via gradient descent.
Logic gate networks allow for very fast classification, with speeds beyond million images per second on a single CPU core (for MNIST at > 97.5% accuracy). The computational cost of layer with n neurons ((n) with very small constants (as only logic gates of Booleans are required), while, in comparison, a fully connected layer (with m imput neurons) requires ( mm) computations with significantly larger constants (as requires floating-point arithmetic). While the training can be more expensive than for regular neural networks (however, just by a constant and asymptotically less expensive), to our knowledge, the proposed method is the fastest available architecture inference time. Overall, our method accelerates inference speed (in comparison to fully connected ReLU neural networks) by around two orders of magnitude. In the experiments, we scale the training of logic gate networks up to 5 million parameters, which can be considered relatively small in comparison to other architectures. In comparison to the fastest neural networks at 98.4% on MNIST, our method is more than 12x faster than the best binary neural networks and 2 3 orders of magnitude faster than the theoretical speed of sparse neural networks.
Related Work
In this section, we discuss related work on learning logic gate networks, methods with methodological or conceptual similarity, as well as other machine learning methods that are fast and that we compare ourselves to with respect to inference cost and speed.
Differentiable Logies and Triangular Norms Differentiable logics (aka. real-valued logics, or inluue logic) are well-known in the fields of fuzzy logics [10] and probabilistic metric spaces [TT.. [2]. In Supplementary Material D we give examples for T-norms and T-conorms.
additional reference for differentiable real-valued logics is Van et al. 13

---

Learning Logic Gate Networks Chatterjee [14] explored "memorization", a method for memoriz- ing binary classification data sets with network of binary lookup tables. The motivation for this is to explore principles of learning and memorization, as well as their trade-off and generalization capabilities. He constructs the networks of lookup tables by counting conditional frequencies of data points. We mention this work here because binary logic gates may be seen as the special case of 2-input lookup tables. That is, his method has some similarities to our resulting networks. However, he memorizes the data set, while this leads to some generalization, this generalization is limited. In his experiments, he considers the binary classification task of distinguishing the combined classes '0'-"4' from the combined classes "5'-'9" of MNIST and achieves test accuracy of 90%. Brudermueller et al. [15] propose a method where they train a neural network on a classification task and then translate it, first into random forests, and then into networks of Inverteerter logic gates, i.e., networks based only on "and" and "not" logical gates. They evaluate their approach on the "gastrointestinal bleeding" and "veterans aging cohort study" data sets and argue for the verifiability and interpretability of small logical networks in patient care and clinical decision-making.
Continuous Relaxations A popular approach for making discrete structures differentiable is continuous relaxation [16]. [17] In this work, we also use continuous relaxations; however, instead of relaxing a fixed discrete structure (e.g., an algorithm) [66 [3], we continuously relax discrete structure (a logic gate network) to optimize it.
Relaxed Connectivity in Networks In this work, we relax which logic operator is applied at each node, while the connections are predefined. Zimmer et al. (24) propose differentiable logic machines for inductive logic programming. For this, they propose logic modules, which contain one level of logic and for which they predefine that the first half of operators are fuzzy "and"s and the second half are fuzzy "or"s. They relax which nodes are the inputs to the "and"s and "or"s of their logic modules. Similarly, Chen (25) proposes Gumbel-Max Equation Learner Networks, where he predefines a set of
arithmetic operations in each layer and learns via Gumbel-Softmax (26). (27 which outputs of the previous layer should be used as inputs of a respective arithmetic operation. He uses this to learn
symbolic expressions from data. While these works relax which nodes are connected to which nodes,
this is fixed in our work, and we relax which operator is at which node.
Evolutionary Learning of Networks Mocanu et al. (28) propose training neural networks with sparse evolutionary training inspired by network science. Their method evolves an initial sparse topology of two consecutive layers of neurons into scale-free topology. On MNIST, they achieve (with 89 797 parameters) an accuracy of 78%. Gaier et al. (29) propose learning networks of operators such as ReLU, sin, inverse, absolute, step, and tanh using evolutionary strategies. Specifically, they use the population-based neuroevolution algorithm NEAT. They achieve learning those floating-point lunction-basel networks and achieve an accuracy of 94. 4% on MNIST with a total of 1 849 connections.
Learning of Decision Trees Zantedeschi et al. (30) propose to learn decision trees by quadratically relaxing the decision trees from mixed-integer programs that learn the discrete parameters of the tree (input traversal and node pruning). This allows them to differentiate in order to simultaneously learn the continuous parameters of splitting decisions. Logic gate-based trees are conceptually vastly different from decision trees: decision trees rely on splitting decisions instead of logical operations, and the tree structure of decision trees and logic gate-based trees are in the opposite directions [31]. Logic gate-based trees begin with a number of inputs (leafs) and apply logic gates to aggregate them to binary value (root). Decision trees begin at the root and apply splitting decisions (for which they consider an external input) to decide between children, such that they end up at a leaf node corresponding to value.
Binary Neural Networks Binary neural networks (BNNs) 3 are conceptually very different from logic gate networks. For binary neural networks, "binary" refers to representing activations and weights of a neural network with binary states (e.g., (-1,+13). This allows approximating the expensive matrix multiplication by faster XNOR and bitcount (popcount) operations. The logical operations involved in BNNs are not learned but instead predefined to approximate operations, and, as such, a regular weight-based neural network. This is not the case for logic gate networks, where we learn the logie operations, we do not approximate weight-basee neural networks, and do not have weights. While BNNs are defined via their weights and not via their logic operations,
moating-poin
3

---

logic gate networks do not have weights and are purely defined via their logic operations. We include BNNs baselines our experiments because they achieve the best inference speed.
neural networks where only selected subset of connections is present, i.e., instead of Cully-connected layers, the layers are sparse. In the literature of sparse neural networks, usually, the task is to distill sparse neural network from dense neural network and the choice of connections is important. However, there has also been work suggesting high effectiveness of using randomized and fixed sparse connections [32]. For logic gate networks, which are sparse by definition, we follow these findings and use randomly initialized and fixed connections.
Sparse Neural Networks Sparse neural networks
Logic Gate Networks
Logic gate networks are networks similar to neural networks where each neuron is represented by binary logic gate like 'and', 'nand', and 'nor' and accordingly has only two inputs (instead of all neurons in the previous layer as it is the case in fully-connected neural networks). Given binary vector as input, pairs of Boolean values are selected, binary logic gates are applied to them, and their output is then used as input for layers further downstream. Logic gate networks do not use weights. Instead, they are parameterized via the choice logic gate each neuron. contrast to fully connected neural networks, binary logic gate networks are sparse because each neuron has only 2 instead of n inputs, where n is the number neurons per layer. In logic gate networks, we do not need activation functions as they are intrinsically non-linear.
While it is possible make a prediction simply with single binary output or binary outputs for k classes, this is not ideal. This is because in the crisp case, we only get Os or 1s and no graded prediction, which would be necessary for a "greatest activation" classification scheme. By using multiple neurons per class and aggregating them by summation, even the crisp case allows for grading, with as many levels as there are neurons per class. Each of these neurons captures a different piece of evidence for a class, and this allows for more finely graded predictions. Figure Tillustrates small logic gate network. In the illustration, each node corresponds to a single logic operator. Note that the distribution over operators (red) is part of the differentiable relaxation discussed in the next section.
As logic gate networks build bit-wise logic operations only, their execution is very efficient.
Differentiable Logic Gate Networks
Training binary logic gate networks is hard because they are not differentiable, and thus no gradient descent-based training is conventionally possible. Thus, we propose relaxing logic gate networks to differentiable logic gate networks to allow for gradient-basee based training.
Table I: List of all real-valued binary logic ops.
To make binary logic networks differentiable, we leverage the fol- lowing relaxation. First, instead of hard binary activations / values a [0,1), we relax all values to probabilistic activations a E [0, 1]. Second, replace the logic gates by comput- ing the expected value of the activation given probabilities of independent inputs aj and ag- For example, the probability that two indepen- dent events with probabilities a, and az both occur is the probabilistic T-norm and T-conorm; we
Differentiable Logics
Operator
real-valued
00
01
10
11
False
0
0
0
AA
B
A
0
1
-(A +
B)
A
A-AB
AB
0
0
A
0
-(A +
B)
AB
1
0
B
1
A B
A B 2AB
AVB
A+ AB
(AVB)
(A+ B- AB)
0
These operators correspond
(A@B)
1
(A+ BA+B-2AR 2AB)
10
-B
0
report the full set of relaxations corresponding to probabilistic interpretation T (In
A
1 BB
0
12
-A
1-A
1
addition, we report alternative relaxations cor-
A
AB
1
responding to alternative interpretations in Ta- bles 10 and 11 in Supplementary Material D.)
14
(AAB)
1-AB
1
0
True
1

---

Accordingly, we define the activation of neuron with the ith operator as
a' = f((01, 02).
where St is the ith real-valued operator corresponding to Table Tand #1, d2 are the inputs to the neuron. There are also alternative real-valued logics like the Hamacher T-(co)norm, the relativistic Einstein sum, and the Eukasiewicz norm. While, in this work, we use the probabilistic interpretation, we review array of possible T-norms and T-conorms that could also be used in SM D.
Differentiable Choice of Operator While real-valued logics allow differentiation, they do not allow training the operators not continuously parameterized and thus (under hard binary inputs) the activations in the network will always be a E {0, 13. Thus, we propose to represent the choice of which logic gate is present each neuron by categorical probability distribution. For this, we parameterize each neuron with 16 floats (i.e., uo E RR16, which, by softmax, map to the probability simplex (i.e., a categorical probability distribution such that all entries sum up to 1 and it has only non-negative values). That is, e / /22 e e) and thus p lies in the probability simplex p A During training, evaluate for each neuron all 16 relaxed binary logic gates and use the categorical probability distribution to compute their weighted average. Thus, we define the activation a' of differentiable logic gate neuron
15 Σ P f((a), 02)
15
e
d'
ESer e f((a).
Aggregation of Output Neurons Now, we may have output neurons ai 02,...g ... On [0, 1]. but we may want the logic gate network to only predict ls < values of a larger range than [0, 1]. Further, we may want be able to produce graded outputs. Thus, we can aggregate the outputs as
(++1)-n/k
Ú:
Σ
/
(3)
j=in/k+1
where 7 is a normalization temperature and 33 is an optional offset.
4.1 Training Considerations
Training For learning, randomly initialize the connections and the parameterization of each neuron. For the initial parameterization of each neuron, we draw elements of w independently from a standard normal distribution. In all reported experiments, layer (except for the input) and between and 8 layers, which we call straight network. We train all models with the Adam optimizer (33 at constant learning rate of 0.01.
use the same number of neurons in each
Discretization After training, during inference, we discretize the probability distributions by only taking their mode (i.e., their most likely value), and thus the network can be computed with Boolean values, which makes inference very fast. In practice, we observe that most neurons converge to one logic gate operation; therefore, the discretization step introduces only small error, e.g., for MNIST, the gap is smaller than 0.1%. We note that all reported results are accuracies after discretization.
Classification In the application of a classification learning setting with k classes (e.g., 10) and output neurons (e.g., 1 000), we group the output into k groups of size n (e.g., 100). Then, we count the number of which corresponds can be retrieved via the arg max of the class scores. During differentiable training, we sum up the probabilities of the outputs in each group instead of counting the 1s, and we can train the model using softmax cross-entropy classification loss. For reference on choosing the hyperparameter T, see Supplementary Material 1. the offset / is not relevant for the classification setting, as arg max shift-invariant A heuristic for choosing is that when increasing when increasing n by factor of 10, should be decreased by factor of about 2 to /10.
the classification score such that the predicted class
have to reduce 7. Empirically,
Regression For regression learning, let us assume that we need to predict a k-dimensional output vector. Here, and 3 play the role of an affine transformation to transform the range of possible
5

---

predictions from 0 to n/k & to an application specific and more suitable range. Here, the optional bias is important, e.g., we want to predict values outside the range of [0. n/.]/// In some cases, is desirable to cover the entire range of real numbers, which may be achieved using logit transform logit(#;) = o - (x) = log I-z in combination with 7 = n//k: A / During differentiable training, we sum up the probabilities of the outputs in each group instead of counting the 1s, and we can train the model, e.g., using an MSE loss.
4.2 Remarks
Boolean Vectorization via Larger Data Types One important computational detail for inference time is that we do not use Boolean data types but instead use larger data types such as, e.g., int64 for a batch size of 64, and thus perform bit-wise logics on larger batches which significantly improves speed on current hardware. For int64, batch 64 data points such that the vth Boolean value of the jth data point is the jth bit in the ith int64 integer. Thus, it is possible to compute on average around 250 binary logic gates on each core in each CPU clock cycle (i.e.. per Hz) on a typical desktop / notebook computer. This is the case because modern CPUs execute many instructions per clock cycle even on a single core, and additionally (for Booleans) allow single-instruction multiple-data (SIMD) by batching bits from multiple data points into one integer (e.g., int64). Using advanced vector extensions (AVX), even larger speedups would be possible. On GPU, this computational speedup also available in addition to typical GPU parallelization.
Aggregation of Output Neurons via Binary Adders In addition, during inference, we aggregate the output neurons directly using logic gate nets that make up respective adders, as writing all outputs to memory would constitute bottleneck and aggregating them using logic gate networks is fast, Specifically, we construct adders that can add exactly one bit to binary number from logic gates.
Memory Considerations Since we pseudo-randomly initialize the connections in binary logic gate networks, i.e., which are the two inputs for each neuron, we do not need to store the connections as they can be reproduced from single seed. Thus, it suffices to store the 4-bit information which of the 16 logic gate operators is used for each neuron. Thus, the memory footprint of logic gate networks drastically reduced in comparison neural networks, binary neural networks, and sparse neural networks.
Pruning the Model An additional speedup for the inference of logic gate networks is available by pruning neurons that are not used, or by simplifying logical expressions. However, this requires storing the connections, posing a (minor) trade-off between memory and speed.
Subset of Operators We investigated reducing the set of operators; however, we found that, in all settings, the more expressive full set of 16 operators performed better. Nevertheless, smaller set of operators could be a good trade-off for reducing the model size.
We also investigated training with half precision (float16). In our experiments, half precision (in comparison to full precision) did not degrade training performance; nevertheless, all reported results were trained with full precision (float32).
Half Precision
Optimizer For training differentiable logic gate networks, we the Adam optimizer (33] because it includes a normalization of the gradients with respect to their magnitude over past steps. We found that this greatly improves training compared other optimizers like which can become ineffective for training deeper logic gate networks.
SGD SGD with momentum,
5 Current Limitations and Opportunities
Expensive Training A limitation of differentiable logic gate networks is their relatively higher training cost compared to (performance-wist) comparable conventional neural networks. The higher training cost is because multiple differentiable operators need to be evaluated for each neuron, and in their real-valued differentiable form, most of these operators require floating-point value multiplica- tions. However, the practical computational cost can be reduced through improved implementations.

---

We note that, asymptotically, differentiable logic gate networks are cheaper to train compared to conventional neural networks due to their sparsity.
Convolutions and Other Architectures Convolutional logic gate networks and other architectural components such as residual connections are interesting and important directions for future research.
Edge Computing and Embedded Machine Learning We would like to emphasize that the current limitations to rather small architectures (compared to large deep learning architectures) does not need be a limitation: For example, edge computing and embedded machine learning [34)- [37]. models are already limited to tiny architectures because they run, e.g.. on mobile CPUs, microcontrollers, or loT devices. these cases, training cost not a concern because is done before deployment.
We also note that there are many other applications in industry where the training cost is negligible in comparison the inference cost.
Experiments
To empirically validate our method, we perform an array of experiments. We start with the three MONK data sets and continue to the Adult Census and Breast Cancer data sets. For each experiment, we compare our method to other methods in terms of model memory footprint, evaluation speed, and accuracy. To demonstrate that our method also performs well on image recognition, we benchmark on the MNIST as well as the CIFAR-10 10 data sets. We benchmark speeds and computational complexity of our method in comparison to baselines, which we díscuss in detail in Section B.
6.1 MONK's Problems
Table 2: Results on the MONK data sets. The inference times are per data point for CPU thread. Averaged over 10 runs. For Diff Logic Nets, # Parameters and Space vary between the MONK data sets use different architectures.
The MONK's problems
40) are 3 classic machine learning tasks that have been used to benchmark learning algorithms. They consist of 3 binary classi- fication tasks data set with 6 attributes with 4 possible values each. Corre- spondingly, the data points binary
Method
MONK-1
MONK-2
MONK-3
Decision Tree Learner (ID3)
38
98.6%
67.9%
94.4%
Decision Tree Learner (C4.5)
39
100%
70.4%
100%
Rule Learner (CN2) 31
100%
69.0%
89.1%
Logistic Regression
71.1%
61.4%
97.0%
Neural Network
100%
100%
93.5%
Diff Logic Net (ours)
100%
90.9%
97.7%
Parameters
Inf. Time
Space
can be encoded vectors of size 17. In Ta- ble [ we show the perfor- mance of our method, a reg- ular neural network, and few of the original learning methods that have been benchmarked. We give the prediction speed for single CPU thread, the number of parameters, and storage requirements.
Decision Tree Learner
Rs 30
49ns
RJ 60B
Logistic Regression
20
68ns
80B
Neural Network Diff Logic Net (ours)
162
152ns
648B
144 72
72
18ns
72B
36B
36B
On all three data sets, our method per- forms better than logistic regression and on MONK-3 (which is the data set with label noise) our method even outperforms the much larger neural network. For hy- perparameter details, see Supplementary Material A.I.
Table Results the Adult and Breast Cancer data sets averaged over 10 runs.
Adult
Acc.
Param.
Infer. Time
Space
Decision Tree Learner
79.5%
As 50
86ns
Rs 130B
Logistic Regression
84.8%
234
63ns
936B
Neural Network 84.9%
3810
635ns
15KB
Dift Logic Net (ours)
84.8%
1280
5.
640B
6.2
Adult and Breast Cancer
Breast Cancer
Acc.
Param.
Infer. Time
Space
For our second set of experiments, we con- sider the Adult Census (41) and the Breast Cancer data set [42]. We find that our method performs very similar to neural 'The source code will be publicly available github.com/Felix http:/eelixPetteree//ddiftoogooo
Decision Tree Learner
71.9%
100
82ns
230B
Logistic Regression
72.9%
34ns
416B
Neural Network
75.3%
434
130ns
1.4KB
Diff Logic Net (ours)
76.1%
640
2.8ns
320B
7

---

networks and logistic regression on the Adult data set while achieving a much faster inference speed. On the Breast Cancer data set, our method achieves the best performance while still being the fastest model. We present the results in Table 3
6.3 MNIST
For our comparison to the fastest neural networks, we start by considering MNIST [43] The methods we compare ourselves to are also discussed in further detail in the baselines section. In comparison to the fastest method achieving at least 98.4% on MNIST, which is FINN by Umuroglu et al. [44) (identified by Qin al. (3), our logic network achieves better performance, while requiring less than 10% of the number of binary operations. That is, our model is objectively more than 10x cheaper to evaluate. When comparing real times, for NVIDIA A6000 GPU, our model is 12x faster than the model by Umuroglu et al. [44) on their specialized FPGA hardware, even though our model only achieves 7% utilization of the GPU. For the other BNNs, OPs have not been reported, but their inference speed is also substantially slower than FINN. When compared to the smallest sparse neural network, our model requires substantially fewer operations than each of the of baselines. Sparse function networks [29). which have been learned evolutionarily, achieve an accuracy of 94.2%. We provide an additional discussion of the results displayed in the Table 4 in Supplementary Material B.
Table 4: Results for MNIST, all of results averaged over 10 runs. Times (T.) are inference times per image, the GPU an NVIDIA A6000, and the CPU is single thread at 2.5 GHz. For our experiments, i.c., the top block, we use binarized MNIST.
MNIST
Acc.
Puram.
Space
T. [CPU]
T. [GPU]
OPs
FLOPs
Linear Regression
91.6%
4010
16KB
3us
2.4ns
(4M)
4K
Neural Network (smalf)
97.92%
282
462KB
14ps
12.4ns
(236M)
236K
Neural Network
98.40%
22 609
86MB
2.2ms
819ns
(45G)
45M
Diff Logic Net (small)
97 6969%
400
23KB
625ns
6.3ns
48K
Diff Logic Net
98.47%
38400 000
188KB
7
(50ns)
384K
Binary Neural Networks
T. [FPGA]
FINN 44
98.40%
(96
641ns
5.28M
BinaryFye Eye
45
98.40%
50yss
ReBNet 46
98.29%
3js
LowBitNN
47
99.2%
152ps
Sparse Neural Networks
Sparsity
Var. Dropout (8
98.08%
4000
98.5%
(8M)
SK
Lo regularization
49
98.6%
2/3
(200M)
200K
SET-MLP 28
98.74%
89 797
96.8%
(180M)
180K
Sparse Function Net (29
94.2%
3 1849
2K
6.4 CIFAR-10
In addition MNIST, we also benchmark our method on CIFAR-10 50) For CIFAR-10. 10, we reduce the color-channel resolution of the CIFAR-10 images and employ a binary embedding: For color-channel resolution of (the first three rows of Table (5). we use three binary values with the three thresholds 0.25, 0.5, and 0.75. For color-channel resolution of 32 (the large models, i.e., the last three rows of the top block of Table we use 31 binary values with thresholds (i/32) We do not apply data augmentation / dropout for our experiments, which could additionally improve performance. For all basclines, we copied the reported accuracies from the original source, and thus those results are with data augmentation and the original color-channel resolution, and may include dropout (51) as well as other techniques such as student-teache learning with a convolutional teacher [52)
The results are displayed in Table We find that our method outperforms neural networks in the first setting (color-channel resolution of 4) by a small margin, while requiring less than 0.1% of the memory footprint and (with larger model) by a large margin while requiring less than 1% of the memory footprint. In comparison to the best fully-connected neural network baselines, which are trained with various tricks such as student-teacher learning and retain the full color-channel resolution, our model does not achieve the same performance, while it is also much smaller and has
8

---

access to fewer data. With 1 million parameters, the student-teacher model [52] has footprint that is about 64% larger than the footprint of our largest model (largex4), and achieves an accuracy which is only 3.7% better than ours. It is important to note that this models requires 2 million floating-point operations, while our model requires 5 million bit-wise logic operations (before pruning/opimizzaion)) On foattarithmmtii hardware-acceleratee integrated circuits (as current GPUs and many CPUs), the 2 million floating-poin operations are around x slower than million bit-wise logic operations. On general purpose hardware (i.e., without float acceleration) the speed difference would be one order of magnitude larger, i.e., 000x.
More competitive with respect to speed are sparse neural networks. In the final block of Table 5 we report the sparsest models for CIFAR- 10. Note that two of the methods resulted performances below 50%, and even those methods which achieve around 75% accuracy require significantly more expensive inference. ProbMask (3) with its 140 KFI.OPs per image means that the model (depending on hardware) 1 orders of magnitude more expensive than our largest model. Also, note that two out of three ResNet32 based sparsification methods achieve only around 37% accuracy.
The results in parentheses are estimated because compilation to binaries did not finish / for GPU the largest models could also be compiled due to compiler limitations. This can be resolved if desired with moderate implementation effort, e.g., compiling the model directly to PTX (CUDA Assembly) without compiling via gee and nvcc. The actual problem is that the compilers used by the implementation have compile time that is quadratic in the number of lines of code statements.
We provide additional discussion of the results displayed in Table 5 in SM B.
Table 5: Results on CIFAR-10. Times (T.) are inference times per image, the GPU an NVIDIA A6000, and the CPU is a single thread at 2.5 GHz, For our experiments, i.c., the top block, we use color celnnel resolution of 4 for the first 3 lines and color-channel resolution of 32 for the large models. The other baselines provided with the full resolution of 256 color-channel values. The numbers parentheses are extrapolated estimated.
CIFAR-10
Acc.
# Param
Space
T. [CPU]
T. [GPU]
OPs
FLOPs
Neural Network (color-ch. res. 4)
50.79%
6M
48MB
1.2ms
370ns
(25G)
25M
Diff Logic Net (small)
51.27%
48K
24KB
1.3pss
19ns
48K
Diff Logic Net (medium)
57.39%
512K
250KB
7.3ps
29ns
512K
Diff Logic Net (large)
60.78%
1.28M
625KB
(18us)
(73ns)
1,28M
Diff Logic Net 22
61.41%
2.56M
1.22MB
(37
(145ns)
2.56M
Diff Logic Net 44
62.14%
5.12M
2.44MB
(73js)
(290ns)
5.12M
Best Molly-Connected Baselines (color-ch. res. 256)
Regularized SReLU NN 28
68. 68%70%
20.3M
77MB
1.9ms
565ns
(40G)
40M
Student-Teacher NN
52
65.8%
IM
4MB
1 112ps
243ns
(2G)
2M
Student-Teade NN
5
74.3%
31.6M
121MB
2.9ms
960ns
(63G)
63M
Sparse Neural Networks
Sparsity
PBW (ResNet32) [44
38.64%
99.9%
(140M)
(140K)
ML (ResNet32)
55
36.09%
99.9%
(1 (140M)
(140K)
ProbMask (ee32)
53
76.87%
99.9%
(140M)
(140K)
SET-MLP 28
74.84%
279K
4.7MB
98.6%
(558M)
558K
6.5 Distribution of Logic Gates
To gain additional insight into learned logic gate networks, we consider histograms of operators present in each layer trained model. Specifically, we consider a 4 layer CIFAR- 10 model with 12 000 neurons per layer in Figure 2
We observe that, generally, the constant "operator is learned be used only very infrequently as it does not actually provide value to the model. Especially interesting is that it does not occur at all in the last layer. the first layer, we observe stronger presence of 'and', 'nand', 'or', and 'nor'. In the second and third layers, there are more 'A', 'B', -" '-A', , and '-B's, which can be seen as residual direct connection. This enables the network to model lower-order dependencies more efficiently by expressing it with fewer layers than the predefined number of layers. In the last layer, the most frequent operations are 'xor' and 'xnor', which can create conditional dependencies of activations of the previous layers. Interestingly, however, implications (e.g.. A + B) are only infrequently used.

---

Layer
1000
Layer
800
1000
500
400
250
200
1200
1500
800
1000
400
250
nan Impstes 01
A
Aor
nolA vox 81
Dimplie
roDAL
Aimplees
renA ratA and Bi
Andd
no0A inniitt B
non imottes Al
Ax00
or
nottA vor Bi
rotBi
iimplees
rosAl
Aimpiia B
nati and
Figure 2: Distribution of logic gates in a trained four layer logic network.
7 Conclusion
In this work, we presented novel approach to train logic gate networks, which allows us to effectively train extremely efficient neural networks that- for their level of accuracy- are one more orders of magnitude more efficient than the state-of-the-art. For this, we leveraged real-valued logics and continuous relaxations via softmax. will release source code of this work to the community to foster future research on learning logic gate networks.
Acknowledgments and Disclosure of Funding
This work was supported by the MIT-IBM Watson AI Lab, the DFG in the Cluster Excellence EXC 2117 "Centre for the Advanced Study of Collective Behaviour" (Project-ID 390829875), and the Land Salzburg within the WISS 2025 project IDA-Lab 11100-FF99116666 and 20204-W185/225/197- 2019).
References
[1] J. Choi, Z. Wang. S. Venkataramani, P. I.-J. Chuang, V. Srinivasan, and K. Gopalakrish- nan, "Pact: Parameterized clipping activation for quantized neural networks," arXiv preprint arXiv:1805. 011880500085, 2018.
[2] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan, "Deep learning with limited numerical precision," in International Conference on Machine Learning (ICML), 2015.
[3] H. Qin, R. Gong, X. Liu, X. Bai, J. Song, and N. Sebe, "Binary neural networks: A survey." Pattern Recognition, vol. 105, p. 107 281, 2020.
[4] T. Hoefler, D. Alistarh, T. Ben-Nun, N. Dryden, and A. Peste, "Sparsity deep learning: Pruning and growth for efficient inference and training in neural networks." arXiv preprint arXiv:2102.0 00554, 2021.
[5] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, "Learning representations by back- propagating errors," Nature, vol. 323, no. 6088, pp. 533-536, 1986.
[6] Telikani, A. Tahmassebi, W. Banzhaf, and A. H. Gandomi, "Evolutionary machine learning:
A survey," ACM Computing Surveys (CSUR), 2021.
[7] J. Rapin and O. Teytaud, Nevergrad A gradient-free optimization platform, https: / GitHub. com/ wwt.ccoo///aaeeee FacebookResearch Neechheeeeerrad 2018.
[8] A. Darwiche and P. Marquis, "A knowledge compilation map." Journal of Artificial Intelligence
Research, 2002.
[9] S. Arora and B. Barak, Computational Complexity: a Modern Approach. Cambridge University Press, 2009.
10

---

[10] G. J. Klir and B. Yuan, Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice Hall,
1997.
[11] K. Menger, "Statistical metrics," Proceedings of the National Academy of Sciences of the United States of America, vol. 28, no. 12, p. 535, 1942.
[12] E. P. Klement, R. Mesiar, and E. Pap. Triangular Norms. Springer Science & Business Media, 2013.
[13] E. van Krieken, E. Acar, and F. van Harmelen, "Analyzing differentiable fuzzy logic operators." arXiv preprint arXiv:2002. 06100, 2020.
[14] S. Chatterjee, "Learning and memorization," in International Conference on Machine Learning (ICML), 2018.
[15] T. Brudermueller,
Shung, A. Stanley, J. Stegmaier, and S. Krishnaswamy, "Making logic learnable with neural networks," arXiv preprint arXiv:2002.03847 2020.
[16] M. Cuturi, O. Teboul, and J.-P. Vert, "Differentiable ranking and sorting using optimal trans- port," in Proc. Neural Information Processing Systems (NIPS), 2019.
[17] F. Petersen, "Learning with Differentiable Algorithms," 2022.
[18] F. Petersen, B. Goldluecke, C. Borgelt, and O. Deussen, "GenDR: A Generalized Differentiable Renderer," in Proc. International Conference on Computer Vision and Pattern Recognition
(CVPR), 2022.
[19] F. Petersen, C. Borgelt, H. Kuchne, and O. Deussen, "Monotonic Differentiable Sorting Networks," in International Conference on Learning Representations (ICLR), 2022.
[20] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach, "Learning with Dif- ferentiable Perturbed Optimizers." in Proc. Neural Information Processing Systems (NIPS), 2020.
[21] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen, "Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision," International Conference on Machine Learning (ICML), 2021.
[22] M. Cuturi and M. Blondel, "Soft-DTW: A Differentiable Loss Function for Time-Series," in International Conference on Machine Learning (ICML), 2017.
[23] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen, "Learning with Algorithmic Supervision via Continuous Relaxations," " Proc. Neural Information Processing Systems (NIPS), 2021.
[24] M. Zimmer, X. Feng, C. Glanois, et al., "Differentiable logic machines," arXiv preprint
arXiv:2102.111
2021.
[25] G. Chen, "Learning symbolic expressions via gumbel-max equation learner network," arXiv preprint arXiv:2012.06921 2020.
[26] Maddison, A. Mnih, and Y. W. Teh, "The concrete distribution: A continuous relaxation of discrete random variables," " in International Conference on Learning Representations (ICLR), 2017.
[27] E. Jang, S. Gu, and B. Poole, "Categorical reparameterization with gumbel-softmax " 2017
[28] D. C. Mocanu, E. Mocanu, Stone, P. H. Nguyen, M. Gibescu, and A. Liotta. "Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science," " Nature communications, vol. 9, no. 1, pp. 1-12, 2018.
[29] A. Gaier and D. Ha, "Weight agnostic neural networks," in Proc. Neural Information Processing Systems (NIPS), 2019.
[30] V. Zantedeschi, M. Kusner, and V. Niculae. "Learning binary decision trees by argmin differ- entiation," in International Conference on Machine Learning (ICML), 2021.
[31] P. Clark and T. Niblett, "The en2 induction algorithm,"" Muchine learning, vol. 3, no. 4, pp. 261- 283, 1989.
[32] S. Liu, T. Chen, X. Chen, et al., "The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training," in International Conference Learning Representations (ICLR), 2022.
[33] D. Kingma and J. Ba, "Adam: A method for stochastic optimization," in International Confer-
ence on Learning Representations (ICLR), 2015.
[34] M. S. Murshed, C. Murphy, D. Hou, N. Khan, G. Ananthanarayanan, and F. Hussain, "Machine learning at the network edge: A survey." ACM Computing Surveys (CSUR), 2021.
11

---

[35] T. S. Ajani, A. L. Imoize, and A. A. Atayero. "An overview of machine learning within embedded and mobile opeiiiaioss and upplications," Sensors, vol. 21, no. 13, 2021. Lee, and L. M. Ang. "Embedded intelligence on fpga: Survey, applications and challenges." Electronics, vol. 10, no. 8. p. 895, 2021.
[36] K. P. Seng,
[37] S. Branco, A. G. Ferreira, and J. Cabral, "Machine learning in resource-scarce embedded systems, fpgas, and end-devices: A survey," Electronics, vol. 8, no. 11, p. 1289, 2019.
[38] J. R. Quinlan, "Induction of decision trees," Machine learning, vol. 1, no. 1, pp. 81-106, 1986.
[39] S. L. Salzberg, C4. 5: Programs for machine learning by j. ross quinlan. morgan kaufmann publishers, inc.. 1993, 1994.
[40] S. B. Thrun, J. W. Bala, E. Bloedorn, et al., "The monk's problems: A performance comparison of different learning algorithms," Tech. Rep., 1991.
[41] R. Kohavi and B. Becker, "Uci machine learning repository: Adult data set," Avaliable: https:/arrchiee.i wtt.hiiiieiiii.u.. ics.
bet.:uurinnn-ddaauusse/uuul 1996.
[42] M. Zwitter and M. Soklic, Uci machine learning repository breast cancer dataset, 1988.
[43] Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database," 2010. [Online].
Available: http: http:://aan... 1ecun.
[44] Y. Umuroglu, N. J. Fraser, G. Gambardella, et al., "Finn: A framework for fast, scalable binarized neural network inference," " in Proceedings of the 2017 ACM/SIGDA International Symposium on Feeld-Programmahhe
Gate Arrays, 2017, pp. 65-74.
[45] P. Jokic, S. Emery, and I.. Benini, "Binaryeye: A 20 kfps streaming camera system on fpga with real-time on-device image recognition using binary neural networks," " in 2018 IEEE 13th International Symposium on Industrial Embedded Systems (SIES), IEEE, 2018, pp. 1-7.
[46] F. K. Mohammad Ghasemzadeh Mohammad Samragh, "Rebnet: Residual binarized neural network," in Proceedings of the 26th IEEE International Symposium on PeildPrograamable Custom Computing Machines, ser FCCM 18, 2018.
[47] J. Zhan, X. Zhou, and W. Jiang. "Field programmable gate array-based all-layer accelerator with quantization neural networks for sustainable cyber-physical systems," Software: Practice and Experience, 2020.
[48] D. Molchanov, A. Ashukha, and D. Vetrov, "Variational dropout sparsifies deep neural net- works," in International Conference on Machine Learning, PMLR, 2017, pp. 2498-2507.
[49] C. Louizos, M. Welling, and D. P. Kingma, "Learning sparse neural networks through Lo regularization," in International Conference on Learning Representations (ICLR), 2018.
[50] A. Krizhevsky, G. Hinton, et al., "Learning multiple layers of features from tiny images," 2009.
[51] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, "Dropout: A simple way to prevent neural networks from overfitting," The journal of machine learning research, vol. 15, no. I, pp. 1929-1958, 2014.
[52] G. Urban, J. J. Geras, S. F. Kahou, et al., "Do deep convolutional nets really need to be deep and convolutional?" In International Conference on Learning Representations (ICLR), 2018. [53] X. Zhou, W. Zhang, H. Xu, and T. Zhang, "Effective sparsification of neural networks with global sparsity constraint," in Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2021, pp. 3599-3608,
[54] S. Han, H. Mao, and W. Dally, "Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding," in International Conference on Learning Representations (ICLR), 2016.
[55] W. Zeng and R. Urtasun, MLPrune: Multi-layer pruning for automated neural network com-
pression, 2019.
[56] A. Paszke. S. Gross, F. Massa, et al., "Pytorch: learning library," in Proc. Neural Information Processing Systems (NIPS), 2019.
An imperative style, high-performance deep
[57] J.-F. Têtu, L.-C. Trudeau, M. Van Beirendonck, A. Balatsoukas- StiiiaanstStiinnn......m and P. Giard, "A standalone fpsa-based miner for lyra2rev2 cryptocuurrencies." IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 67. no. 4. pp. 1194-1206, 2020.
[58] C. Kolivas, Cgminer, /tttps://tttt t/uithbb..tttt..../ ctt. http:/oooliaas/smmmmmn. cgminer 2012.
[59]
S. A. Khan, A. Agarwala, and D. Shahani, "Implementation of advance oscilloscope triggering scheme on fpga," " in 2005 IEEE Instrumentationand Measurement Technology Conference
Proceedings, IEEE, vol. 1, 2005, pp. 407-411.
12

---

[60] I. Shani, L. Shaughnessy. J. Rzasa, et al., "Dynamies of analog logic-gate networks for machine learning," Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 29, no. 12, p. 123 130, 2019.
[61] S. Lym, E. Choukse, S. Zangeneh, W. Wen, S. Sanghavi, and M. Erez, "Prunetrain: Fast neural network training by dynamic sparse model reconfiguration" in Proceedings of the International Conference for High Performance Computing, Networking. Storage and Analysis, 2019.
[62] D. Blalock, G. Ortiz, Frankle, and Guttag, "What is the state of neural network pruning?" In Proceedings of the 3rd MLSys Conference, Austin, TX, USA, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them?
[Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [Yes] The source code for this Petersen/difflogic
work will be made publicly available at atggthuu..cmm/aae httpta/oooommmess-eeeeeee/riiigi
(b) Did you specify all the training details (e.g., data splits, byperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're
using/curating?? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals. applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "ivfTmjq4giQ", "reviewer": "Reviewer_eqXk", "summary": "This paper introduces a new approach for fast-inference, low memory neural networks: logic gate networks. An output neuron is connected sparsely to only two neurons from the input layer, and training learns one of sixteen possible boolean functions on the two binary inputs. Training is done with real relaxations of the logic functions and averaging over all 16 functions, while testing uses the most common function. Using logic gates enables extremely efficient inference execution on CPU. The authors show logic gate networks perform comparably to alternatives on several small datasets.", "questions": "Questions and suggestions:\n- Line 195 I believe it should be \"increasing n by a factor of 10, tau should be decreased...\" not increasing tau.\n- The paragraph in section 4.2 \"aggregation of output neurons via binary adders\" does not make any sense to me.\n- I find the remark on lines 242-244 about being developed from scratch inappropriate for a paper. I would rewrite to discuss the possibility of future papers considering convolutions and other connectivity patterns without the excuse. And perhaps you should add a sentence explaining how the work is implemented (pytorch?)\n- Higher training cost is mentioned for logic gate networks limitation in section 5. But how much higher is the cost? Quantifying this, even if the number might be improved down the line, seems like an important and useful benchmark to have.\n- If you say practical cost of training can be reduced through improved implementations, then you should explain what stands to be improved and how much improvement we might gain. \n- \"Thus, our model is objectively more than 10x cheaper to evaluate\" — I do not like this sentence. Whether a net is cheaper to evaluate depends on factors other than the number of binary operations. \n", "limitations": "Limitations:\n- the limitations section is not very good. The statements are qualitative when it would be very easy to make them quantitative. Furthermore, there are more interesting things that could be said about future extensions. Most of the limitations section sounds like making excuses in case the reader is not impressed with the current work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- To my knowledge, this is a new idea. Using logic gates is a smart goal for achieving ultra-fast NN inference, and the authors seem to use the correct general approach to training such networks.\n- Related work is well-cited, and the authors do a good job contextualizing to the space of similar techniques (sparse NNs/pruning, binarized NN's)\n- Claims are fairly well supported. \n- Submission is mostly well-written, with some exceptions.\n- Significance: the results are not game-changing **yet**, but I find the goal of logic-gate networks to be an exciting direction and the work the authors achieve in pursuit of this direction.\n- In all experiments, the approach presented has the fastest inference time. \n\nWeaknesses:\n- Overall writing quality could be better. Many details are not described well:\n- The network architecture is poorly explained in section 3. The description is informal and at a high level of detail. The pieces don't really come together until the end of section 4; for example, the sparse net topology of 2 inputs per neuron is not fully explained with the random connectivity in line 221. \n- There is no architecture figure. While not 100% necessary, I think this would be a helpful aid to understanding the architecture, especially how the connective topology is organized.\n- Many training and architectural design choices are not motivated well. Often there are reasonable alternative choices, which should be ruled out, or better yet experimented against to see which is best! For example, there could be alternate ways of making the choice of logic gate differentiable (smoothly interpolate between logic ops?), or you could try structured connectivity patterns rather than random connectivity patterns. Or you could try expanding the set of operators rather than reducing. Four inputs instead of two?\n- The paper has a lot of unpleasant language that seems to be making a lot of effort to apologize for poor results \"if we had more time down the line, we could implement more connectivity types\", or \"practical computation cost can be reduced through improved implementations\" and the like. Ignoring the quality of results, such statements do not belong in a paper in my opinion.\n- Many of the baseline comparison architectures do not seem justified well. Why does the breast cancer dataset neural network have 3810 parameters? Why does the Diff logic net have 1280 parameters? \n- It would be extremely valuable to have a comparison of training time for Diff Logic Nets and the baselines, even if some baselines' training time can't be given or can only be estimated. Even if DLN are much slower to train (that's okay!), this should be shown!\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Yb1DQd0pho", "reviewer": "Reviewer_2qAj", "summary": "The authors proposed the Logic Gate Network - a neural network with neurons represented by binary logic gates. The network is parameterized by the choice of logic gates chosen from 16 logic operations. During training, the inputs to the neurons are relaxed from binary to probabilities to allow for differentiability. To allow for differentiability of the logic operations, each neuron has a weight vector of dimension 16, which when taken the softmax forms a categorical distribution. The activation of the neuron is the weighted sum of the distribution with their corresponding real-valued logic operation. At test time, the trained network is binarized to allow for fast inference. The authors evaluated their method on a set of classification tasks including MONK, Adult and breast cancer dataset, MNIST and CIFAR-10. Results show that compared to fully connected networks, the logic gate network is able to speed up inference time by 1-2 orders of magnitude and reduce the space consumption by roughly the same amount while moderately sacrificing accuracy in some tasks.", "questions": "- \"after training, the network is binarized by choosing the logic gate with highest probability\", this is not the same network that is being trained on, even though the binary network provides a speed up at inference, will the accuracy be higher with the \"soft\" version?\n\n- \"there is a total of 16 functions of signature\" - can it be more than 16? if so will it improve performance?\n\n- no comparison with CNN on image classification tasks, though this is for fair comparison with a fully connected logic net, can the authors comment how a CNN version of the logic net will perform?\n\n- \"CIFAR-10 reduced grayscale resolution and employ binary embedding\",  why is this needed?\n\n- The sparse neural network rows in Tables 4 and 5 are a bit confusing, they don't have inference times but instead sparsity metrics, which the diff logic net do not provide, not sure what the comparison here is.", "limitations": "The authors provided a reasonable set of limitations in Section 5. One of my concerns is that the input and output of the proposed logic network are Booleans, how would colored images be represented? Moreover, would regression tasks be out of the question for this type of network?", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The authors made good progress in enabling binarized logic network to work reasonably well in small to midsize classification problems while significantly reducing the memory footprint and speeding up the inference process. I particularly enjoyed Sections 4.1 and 4.2 where the authors discussed practical considerations and tricks they have tried to improve the performance. This type of work has much practical value to the edge deployment of neural network models.\n\nWeaknesses\n- elucidation of the position of the proposed architecture within the deep learning literature can be improved. functionality-wise, do the authors see the logic gated network able to achieve most of what other networks can down the road, or by design it would occupy a different functional space (for example efficient inference on the edge with reduced accuracy)?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "By-RPt_OTsR", "reviewer": "Reviewer_BrUk", "summary": "This paper proposes the differentiable logic gate networks. The logic gate networks parameterize the logical operations by proposing a logic gate neuron that consists of 16 binary logic operations. The differentiable learning is done by 1) using soft logic operations and 2) introducing attention parameters over the 16 operations. The proposed model is evaluated on standard classification tasks, which seems to suggest that the model is faster in inference time.", "questions": "I recommend the authors re-writing the paper and address the following concerns:\n- What is the motivation of this work? \n- What are the benefits of using this network compared to other neural-symbolic models?\n- How are the layers connected? Is there any theoretical or empirical justification to this design?\n\nI also recommend re-designing the experiments:\n- Include training time when comparing with other baselines.\n- Include empirical analysis on certain parts of the proposed network. For example, shifts in the feature space, and classification via grouping.\n", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\nOverall, the proposed method isn't intellectually novel. The idea of using soft logic and attention mechanism to learn a logic system in a differentiable way has been a common practice in the literature, and similar and more sophisticated designs for the same problems have been proposed and studied extensively in many prior works [1-5].  With that being said, this paper clearly misses a big part of the literature. For those cited work, the paper does a poor job in connecting them to the proposed method, either due to the comparison is missing (e.g., L95) or the comparison is unconvincing and confusing:\n- \"while this leads to some generalization, this generalization is limited\"\n- \"While these works relax which nodes are connected to which nodes,85this is fixed in our work, and we relax which operator is at which node\"\n\n\n### Quality\nI find some of the proposed designs difficult to understand and can be fundamentally flawed:\n- Judging from Figure 1 and section 4,  it looks like the neuron accepts only two inputs from the previous layer, but it is unclear how they are picked. This can be problematic compared to the standard fully connected layer because not all logical combinations are included in the model space. Consider this a simple setting with 3 binary inputs (a, b, c) and two neurons f1 and f2 that connect to (a, b) and (b, c) respectively. Then it is impossible to represent any operations between (a, c). To consider all combinations, one needs n^2 number of neurons at each layer.\n- L187, the classification is performed by simply grouping adjacent neurons and counting. My concern is that this implicitly makes the output dependent on the position of the neurons. For the image classification task, this means the network is not translational invariant as opposed to CNNs, because a small shift in the original image is going to lead to different results.\n\n\n\n### Clarity\nThe writing needs an overhaul. This paper is prone to confusing statements, constant grammatical errors and informal presentations.  \n\nThe English writing should be improved:\n- \"as well as other machine learning methods that are fast and that we compare ourselves to with respect to inference cost and speed\"\n- Mixed usages of normal and italic \"which\" in L77-86\n\nThe wording should be improved; some of the contents are rather colloquial:\n- \"He does this to explore principles of learning and memorization\" -> \"The proposed method explores the  principles of learning and memorization\"\n\n\n### Significance\nThe proposed method is only evaluated on existing tasks and struggles to match with the performance of other baselines. The only merit seems to be that the proposed network excels in inference speed. However, this comes with serious limitations: \n- As mentioned by the author at L235, the network is expensive to train. However, it's unclear how expensive the training actually is because only inference time is compared in the experiments. To fairly compare with other baselines, it is necessary to include the training time.\n- The network likely oversimplifies the layer connections and can be flawed in representing certain logical combinations.\n\nThat said, there is no substantial contribution in this work.\n\n[1] Serafini, Luciano, and Artur d'Avila Garcez. \"Logic tensor networks: Deep learning and logical reasoning from data and knowledge.\" arXiv preprint arXiv:1606.04422 (2016).\n\n[2] Dong, Honghua, et al. \"Neural logic machines.\" arXiv preprint arXiv:1904.11694 (2019).\n\n[3] Shi, Shaoyun, et al. \"Neural logic reasoning.\" Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.\n\n[4] Shanahan, Murray, et al. \"An explicitly relational neural network architecture.\" International Conference on Machine Learning. PMLR, 2020.\n\n[5] Yang, Yuan, and Le Song. \"Learn to explain efficiently via neural logic inductive learning.\" arXiv preprint arXiv:1910.02481 (2019).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1uzSZP5OJfD", "reviewer": "Reviewer_r8L3", "summary": "This paper proposes deep logic networks that can train with backpropagation and inference with binary values. The logic networks comprise logical gates arranged in layers, randomly selected connections between gates, and an output layer that sums the outputs from groups of gates to adapt cross-entropy loss or squared error loss. The types of gates are treated as parameters of the model and are optimized by Adam. The experiments show this network can perform classification tasks on MONK, Adult Census, Breast Cancer, MNIST, and CIFAR10, achieving good accuracy.", "questions": "1. Line 195: the first tau should be n?\n2. Line 334: What is PTX?\n3. What's the training time of each Diff Logic Net in Table 5?\n", "limitations": "The paper discussed 3 aspects of limitations in section 5.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and easy to follow. To my best knowledge, the proposed Differentiable Logic Gate Networks is a highly novel idea. The model learns the type of gates instead of the weight matrix/connections. This training paradigm differs significantly from the standard DNN and other logic models. More interestingly, the Diff Logic Net uses randomly selected connections between gates, and the random connections are fixed during the training. This simple idea works surprisingly well and is probably the key reason it can learn the gate type in a scalable way. The experiments compare with a set of prior compact models and show the advantage of the Diff Logic Net in terms of accuracy, the number of operations, and actual inference time. I especially appreciate the results on CIFAR10 to demonstrate the scalability of this new breed of models. This work may significantly impact edge-device AI in both software and hardware aspects.\n\nThe success of Diff Logic Net looks too good to be true; therefore, discussing its limitation is highly appreciated. I saw it in Section 5 and consider the current section 5 reasonably informative. I believe the community will appreciate it more if section 5 is expanded further. One idea for exploring the current limitation is to examine its architectural robustness against several factors. For example:\n1. Depth versus accuracy\n2. If the input dimension is very high, would the random connection still work with a reasonable model width?\n3. The variance of accuracy with different random connections\n\nNote the above bullets are suggestions and I do not consider these are weaknesses of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept