Convolutional Differentiable Logic Gate Networks
Authors: Felix Petersen
Hilde Kuehne
Christian Borgelt
Julian Welzel
Stefano Ermon
Venue: NeurIPS 2024 oral (2024)
Keywords: logic
efficient inference
embedded
fpga
logic circuits
lookup tables
differentiable
Primary area: machine_vision

Abstract: With the increasing inference cost of machine learning models, there is a growing interest in models with fast and efficient inference. 
Recently, an approach for learning logic gate networks directly via a differentiable relaxation was proposed. Logic gate networks are faster than conventional neural network approaches because their inference only requires logic gate operators such as NAND, OR, and XOR, which are the underlying building blocks of current hardware and can be efficiently executed. We build on this idea, extending it by deep logic gate tree convolutions, logical OR pooling, and residual initializations. This allows scaling logic gate networks up by over one order of magnitude and utilizing the paradigm of convolution. On CIFAR-10, we achieve an accuracy of 86.29% using only 61 million logic gates, which improves over the SOTA while being 29x smaller.

proposed. Convolutional Differentiable Logic Gate Networks
Felix Petersen Stanford University
Hilde Kuehne Tuebingen Center MIT-IBM Watson Al Lab h. cecianeduun-tuebingeen
InftyLabs Research mail@felise ieeieffelix-ptteren..deee
Christian Borgelt University of Salzburg christian@borgelt.cc .et
Julian Welzel InftyLabs Research
Stefano Ermon
Stanford University ermonêcs. stanford. edu
velzel@inftylabe.coo com
Abstract
With the increasing inference cost of machine learning models, there is growing interest in models with fast and efficient inference. Recently, an approach for learning logic gate networks directly via differentiable relaxation Logic gate networks are faster than conventional neural network approaches be- cause their inference only requires logic gate operators such as NAND, OR, and XOR, which are the underlying building blocks of current hardware and can be efficiently executed. We build this idea, extending it by deep logic gate tree convolutions, logical OR pooling, and residual initializations. This allows scaling logic gate networks up convolution. On CIFAR-10, 10, we achieve an accuracy of 86.29% using only 61 million logic gates, which improves over the SOTA while being 29 smaller.
order of magnitude and utilizing the paradigm
Introduction
90%
Deep learning has led to a variety of new applications, opportunities, and use-cases machine vision. However, this advance- ment has come with considerable compu- tational and energy costs for inference [T]. Therefore, array of methods has been developed for efficient deep learning infer- ence These include binary weight neural networks (BNNs) 2 set of meth- ods for quantizing neural network weights down to binary representations (and some- times also binary activations); quantized low-precision neural networks (3]. su- perset of BNNs and sparse neural net- works [ (6). a set of approaches for prun- ing neural networks and increasing sparsity. These methods have been successfully uti- lized for efficient vision model inference.
Accuracy
Ours
Hirtzlin
Duo
70%
Hubara et
Ghasemoadeh
Rastegari
Winng et
Umuuregu al. Benierine
60%
Gates
Figure Gate count vs. accuracy plot on CIFAR- data set. Our models (*) are substantially above the Pareto-froe of the SOTA basclines. Gate counts are proportional to chip area. Our models more efficient than the SOTA by factors of > 29 Note that the æ-axis (gate count) is log-scale.
The statc-of-ther the-t--rtttttttto (SOTA) method for small architectures, deep differentiable logic gate networks (LGNs) [7] approaches efficient machine learning inference from a different direction: learning an LGN (i.e., a network of logic gates such as NAND and XOR) directly via a differentiable relaxation.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Differentiable LGNs directly learn the combination of logic gates that have to be executed by the hardware. This differs from other approaches (like BNNs) that require translating an abstraction (like matrix multiplication-base basod neural networks) into executable logic for inference, an inductive bias that comes with a considerable computational burden. By optimizing the logic directly on the lowest possible level instead of optimizing an abstraction, differentiable L.NSs lead to very efficient inference on logic gate-based hardware (c.g.. CPU, GPU, FPGA, ASIC). Recently, differentiable LGNs achieved SOTA inference speeds on MNIST 77. (8) However, crucial limitation was the random choice connections, preventing LGNs from learning spatial relations, as they arise in images, which limited performance to accuracy of only 62% on CIFAR- 10 (7). (9]. To address this limitation, we propose to extend differentiable LGNs to convolutions. Specifically, we propose deep logic gate tree convolutions, i.e., kernels comprised of logic gate trees applied in convolutional fashion. Using trees of logic gates, instead of individual gates, increases the expressivity of the architecture while minimizing memory accesses, improving accuracy and accelerating training as well as inference. Further, we adapt pooling operations by representing them with logical or gates (relaxed via the maximum I-conorm), improving the effectiveness of convolutions in LGNs. Additionally, we propose "residual initializations". a novel initialization scheme for differentiable LGNs that enables scaling them up deeper networks by providing differentiable residual connections. These advances lead to an accuracy of 86.29% on CIFAR-10 using only 61 million logic gates, leading to cost reductions by 2 29 compared SOTAs as displayed in Figure
2 Background
Giant Panda
Our work builds on and extends dif- ferentiable logic gate networks [7]. To recap, logic gate networks (LGNs) networks of nodes that are binary logic gates like AND,
Polar Bear
NAND, XOR. L.GNs are also known as binary circuits or logical circuits, and are the format in which any digital hardware is implemented on the lowest pre-transistor abstrac- tion level. The function that an LGN computes depends on the choices of logic gates that form its nodes and how these nodes are connected. Op- timizing an LGN requires choosing the connections and deciding on a gate for each node. A primary chal- lenge when optimizing LGNs is that they are, by default, non-differentiable, preventing gradient descent-basse baseed training, making this problem conventionally a combinatorial problem. However, when applied to machine learning problems, solving the combinatorial problem conventionally becomes infeasible as we require millions of parameters gates. Thus, differentiable relaxation of randomly connected LGNs has been proposed, which allows training LGNs with gradient descent (7]. over- coming the exponential difficulty of optimizing LGNs In the remainder of this section, we cover the structure, relaxation, and training of differentiable L.NNs, which we also illustrate in Figure 2
Figure 2: Architecture of randomly connected LGN, Each node corresponds to one logic gate. During training. the distribution over choices of logic gates (hottom, 16 options) is learned for each node.
Structure L.GNs follow a layered structure with each layer comprising a number of nodes, each comprising one logic gate (3 layers with 4 logic gates each in Fig. 2 As logic gates inherently non-linear, LGNs do not require any activation functions. Further, LGNs do not have any weights nor any biases as they do not rely on matrix multiplications. Due the binary (i.e., two-input) nature of the nodes, LGNs are necessarily sparse and cannot form fully-connected networks. The connectivity between nodes has so far been (fully) randomly selected, which works well for easier tasks but can become problematic if there is inherent structure in the data as, e.g., in images. During training, the connections remain fixed and the learning task comprises the choice of logic gate at each node.
Differentiable Relaxation To learn the choices of logic gates for each node with gradient descent requires the network to be differentiable; however, the LGN is by default not differentiable for two reasons: (i) Because a logic gate computes a discrete function of its (Boolean) inputs, it is not differentiable. (ii) Because the choice of logic gate is not continuous parameter, but discrete

---

decision, it is not differentiable. Petersen et al. (7] propose to differentiably relax each logic gate to real-valued logic via probabilisticc logic (10), I For example, logical and (a, A @2) is relaxed to d1 42 and a logical exclusive or (a1 @ (2) is relaxed to an + 0g - 2 di 02, which corresponds to the output probability when considering two independent Bernoulli variables with coefficients (11, 02- To make the choice of logic gate learnable, Petersen et al. 7 introduce probability distribution over the 16 possible logic gates (8), which is encoded as the softmax of 16 trainable parameters. For trainable parameter vector E Ie and all 16 possible logic gate operations as 9o, 915, the differentiable logic gate as the expectation over its outputs can be computed in closed-form as
15
exp(z1)
fz(a1, a2) = Es-S(x) Ar-B((r)) Arr=Baa))) B(ag) (AI, Ab)
= Σ
t=0 E, exp(2,) 9i(a), a2). (1)
With these two ingredients, logic gate networks become end-to-ent tond differentiable.
Initialization, Training, and Discretization Training differentiable logic gate networks corre- sponds to learning the parameters inducing the probability distributions over possible gates. The parameter vector z for each node has so far been initialized with a standard Gaussian distribution. The connections are randomly initialized and remain fixed during training. For classification tasks, each class associated with composing class score (group sum, right part of Fig. 2) After dividing them by a temperature the class scores are used as logits in softmax cross-entropy loss. Differentiable LGNs perform best when trained with the Adam optimizer [12]. Empirical evidence showed that the softmax distributions typically converge to concrete choices of logic gates. Thus, differentiable LGNs can be discretized to hard LGNss for deployment on hardware by selecting the logic gate with the largest probability. This discretization process incurs only a minimal loss in accuracy compared to the differentiable LGN (7).
of neurons the output layer and active neurons in each set are counted
I Limitations Differentiable LGNs have shown significant limitations wrt. the available architectural components. Previously, they did not provide the option to capture local spatial patterns as they were randomly connected and only operated on flattened inputs (7). Further, they previously performed well only up to a depth of 6 layers 7 Thus, more complex relationships between inputs cannot be modeled. Finally, while they provide SOTA performance, differentiable LGNs are very computationally expensive to train, e.g., a vanilla 5 million gate network required 90 hours on an A6000 GPU (7). In the following, address these limitations by introducing convolutional logic tree layers, logical or pooling, residual initializations, as well as computational considerations for scaling.
3 Convolutional Logic Gate Networks
Convolutional neural networks (CNNs) have ex- perienced tremendous success, being tributor to the current machine learning ascen- dancy starting with their progress on the Ima- geNet classification challenge 2012 [3). Un- derlying CNNs is the discrete convolution of an input tensor A (e.g., an input image or hidden activations) and linear function / kernel W, denoted as * W. CNNs are especially effec- tive in vision tasks due the equivariance of the convolution, which allows the network to generalize edge, texture, and shapes in different locations by sharing the parameters at all place- ments. However, existing differentiable LGN methods do not support convolutions.
con-
(a)
(b)
Figure 3: Conventional convolutional neural networks (a) compared to convolutional logic gate networks (b). The images illustrate the first and second to last kernel placements. The nodes correspond (a), and binary logic gates f1, fa. fa (b), respectively. The weights choices of logic gates are shared hetween kernel placements. For visual simplicity, only single input channel and kernel (output channel) is displayed.
weighted sums
In this work, we propose to convolve activations A with differentiable binary logic gate trees. While we could convolve A with an individual logic gate, we observe that actually convolving A with a (deep) logic gate network or tree leads to substantially better performance as it allows for greater expressivity of the model. Similar to how the inputs to each logie gate are randomly initialized and remain fixed in conventional differentiable LGNs, we randomly construct the connections in
3

---

logic gate tree kernel function. However, we need to put additional restrictions on the connections for logic gate network kernels. Specifically, we construct each logic gate network kernel as a complete binary tree of depth d with logic gates as nodes and binary input activations as leaves. The output of the logic gate operation then the input to the next higher node, etc. To capture spatial patterns, we select the inputs/ leaves of the tree from the predefined receptive field of the kernel of size 8,, 8w- Based on the depth of the tree, we randomly select as many inputs as necessary. For example, we could construct a binary tree of depth df = 2, which means that we need to randomly select 2d = 4 inputs from our receptive field, e.g., of size 64 x 3 3, which corresponds to 64 input channels with kernel size of 3 x 3. This tree structure allows capture fixed spatial patterns and correlations beyond pair-wise binary inputs. Further, it extends the concept of spatial equivariance to LGNs as such trees can be used as kernel filters, capturing general patterns in different locations. Using trees of logic gates instead of individual logic gates also has the advantage of reducing memory accesses and improving training and inference efficiency. We remark that, eterization of each node is shared between all placements of the kernel (which contrasts convolution from mere local connectivity.) In Figure we illustrate the difference between conventional CNN models and convolutional logic gate networks.
apply convolution, the param-
During training, the network learns which logic gate operation to choose at each node. Thus, each logic tree kernel is parameterized via the choices of each of the 2d - 1 logic gates, which are learnable. For logic kernel of depth 2, we call these logic gates fa. f2- fs (or more formally fax: fra: fzz for
parameter vectors 2 Zg, Zg corresponding to Equation [T]. Given input activations 01 ag, 0g, ag the kernel is expressed as a binary tree of these logic gates:
fa( (1 02), fa(a3, a4) ).
(2)
For an input A of shape m x x w (m input channels; height; width) and connection index tensors CM, CH, Cw each of shape X 4 (n tree kernels / chamnels; 4 imputs per tree), the output is
A' A'K,,, = f3 (F" (A 1..1). C2[k. (..
[C Cn(k:2) [4.2) (3)
12
Cn [k:3:,] Cw (4.33 A [b, Cw
Cw
for l E (1....., n where n is the number of tree kernels, E {1,..., (h 8n + 1 and j E {I...., (w- 8.. + })} where sn x 8w is the receptive field size. Note that, in Equation 3 for each output channel k the logic gates ft. f2. f (or their relaxed form) are chosen and parameterized independently. Per convolution, all placements (indexed via i. of one kernel share their parameters.
After introducing convolutional LGNs,, in the remainder of the section, we introduce our additional components, training strategies, and our architecture.
3.1 Logical Or Pooling
1: pre or propooling
In CNNs, max-pooling is a crucial compo-
Activation Level
60%
2: post or-pooling
nent selecting the largest possible activation over a predefined receptive field, c.g., for
3: no or-pooling
50%
2 x 2, To adopt this for logic, we propose to use the dis-
d,+1,j, . 1++1,f+1) [13)
40%
junetion of the binary activations d. V aij++ V
30%
a++1, V 0:+15+1 via the logical or. Instead of using a probabilistic relaxation of the logical or,
500
1000
1500
2000
2500
3000
Training Steps
we can use the maximum t-conorm relaxation of the logical or (1 (a, b) max(a, b)). By set- ting the stride of the pooling operation to the size of its receptive field, this has a range of crucial computational advantages: (i) it is faster to com- pute than the probabilistic relaxation; (ii) we only need to store the maximum activation and index; (iii) we only need to backpropagate through the maximum activations during training.
Figure 4: Plot of the density of activations for the sec- ond convolutional block of an or-pooling based convo- lutional LGN. It shows that training implicitly enforces that the outputs of the block have the activation level of no no-pooling network (i.e., with pure stride).
Intuitively, using many logical could lead to the outputs of the activations becoming predomi- nantly 1. However, we find that, during training, this is not an issue as using or pooling causes an
CM E {L, (L,.... m pnx4 indicates which out of m input channels is selected; C# E {L,..., s1.} 1nx4 and Cw (I,..., Sw j jndd indicate the selected position inside of the receptive field of size Sh. x Sw.

---

automatic reduction of pre-pooling activations, resolving this potential concern. This phenomenon is shown Figure 4 Here, the average activation of a convolutional block of a logic network with x strided or pooling is illustrated. For random network without pooling, we expect and observe an average activation of 50% (dash-dotted). We observe that the post or pooling activations (solid line) for the initialized models is 66.5%, which follows expectation. The pre or pooling activations (dashed) are initialized at 50%, also following expectations. With training, the post or pooling activations (solid) rapidly converge to the average activations of network without pooling, preventing any problematic saturation activations. We do not introduce any explicit regularization enforcing this behavior, but instead found this to be emerging behavior of training.
3.2 Residual Initialization
The parameters z of existing differentiable LGNs were initialized as random draws from a Gaussian distribution. Unfortunately, after applying softmax, this leads to rather "washed out" probability distributions over choices of logic gates. Accordingly, the expected activations, as computed via Equation [ are also washed out, quickly converging towards 0.5 in deeper networks. This also leads to vanishing gradients in existing differentiable LGNs: With Gaussian initialization, during backpropagation, the gradient norm decays at each logic gate by a factor between 0.1 and 0.2 for an initialized network, exponentially slowing training for deeper networks.
In CNNs. technique for preventing vanishing gradients and preventing loss of information in deep networks are residual connections. Residual connections conventionally add the input to block to the output of this block [14). However, when operating logic, we cannot perform such additions.
To prevent the loss information through washed out activations and reduce vanishing gradients with joint strategy, we propose residual initializations. For this, initialize each logic gate not randomly but instead to be primarily a feedforwarding logic gate. Here, we choose 'A' as a canonical choice and choosing 'B' would be equivalent. In our experiments we found that initializing the probability for the logic gate choice 'A' to around 90% and setting all other gates to 0.67% works well. This corresponds to setting the parameter 23 5 and all other 2; for * 3 in accordance to Eq. [ initializations in Figure [
We illustrate an example of residual initializations compared to the existing Gaussian
Residual initializations
prevent the loss of infor-
(a)
mation as well as vanish-
ing gradients in deeper
networks. During train- (b)
ing, whenever resid- ual connection is not re- quired, the model learns
Figure 5: Gaussian initialization (a)
vs. our residual initialization (b).
to replace the feedforward logic gate choice by an actual operation. Thus. residual initializations are effectively differentiable form of residual connections that does not require any hard-wiring. This also means that this form of residuals does not require additional logic gates for residuals. Residual initializations enable, for the first time, efficient and effective training of LGNs beyond 6 layers.
3.3
Computational Training Considerations
Using trees and pooling allows for substantially improved computational training efficiency and memory requirement reductions. This is because it allows intermediate activations to be used only by the current logic gate tree and because we only need backpropagate through the maximum activations during or pooling. For example, using learnable trees with depth of 2 and or pooling with kernel size and stride of 2 2 corresponds to logic gate tree of depth 2 + learnable + 2 from pooling) with 16 inputs and only single output. For training, it is most efficient discard all intermediate values and only store the output and information of which path through the pooling was selected, and during backward to recompute only this path, thereby reducing memory accesses. The reason for this is that training speed is limited by memory bandwidth and scalability is limited by GPU memory. On average, this strategy reduces memory accesses by 68% and reduces the memory footprint by 90% during training. For using L.GNs hardware designs, trees and pooling improve the locality of operations and routing, which also leads more efficient chip layouts.
(2 levels are
5

---

The residual initializations provide a bias toward the feedforward logic gate in trained LGNs, As feedforward gates only require a wire and no transistors, this further reduces the necessary transistor count for hardware implementations of the LGNs, reducing the required chip area.
We developed efficient fully-fused low-level CUDA kemels, which, for the first time, enable training of convolutional LGNs. The speed of our convolutional layer is up to x faster per logic gate than existing randomly connected LGN implementations (7]. We will make the code publicly available by including it into the difflogic library at github. ccom/Feliin wwwiix/eeeeeeeeeddeeeieeeeee
3.4 Logic Architecture
In the following, we discuss the design of our con- volutional logic gate tree network architectures (LogicTreeNet) for CIFAR-10, which we illus- trate in Figure 6 We follow the pattern of con- ventional convolutional architectures and design the architecture by applying convolutional blocks with pooling at the end of each block. Each block reduces the size by a factor of 2 x 2 and we apply blocks until we reach size of 2 x 2, increasing the number of channels in each stage. Following this, we apply three randomly connected layers and group sum as our classification head. This architecture has an overall logical depth of 23 layers, including 4 convolutional blocks (Conv) with tree depths of = 3. 4 or pooling lay- ers (or-Pool), and 3 randomly connected layers (Rand). 15 of these layers are trainable (Conv blocks and Rand), and the pooling layers remain fixed. The architecture is defined in terms of hy- perparameter k, which controls the width of the network; we consider & E {S - 32, M - 256, B + 512, L 1 024, G + 2 048). In Ap- pendix[A.] we describe LogicTreeNee layer-by- layer and include a LogicTreeNet for MNIST.
Conv: d=3, ch=k, rf=3x3
or-Pool:
ks=2x2, str=2
3:3, 4wk, 3x3
P:2x2,2
C:3, 16*k, 3x3
P:2x2,2
3, 3232,,, 3x3
2x2,
latten
Rand: 128-k-21280-1
Rand: 1280sk->640ek
An additional architecture choice is the connec- tivity for the inputs to a convolutional tree. While we rely on random choices for the inputs, we restrict the choices of channels (CAr) such that each tree observes only 2 (rather than up to 8) input channels. This has the two advantages of enforcing spatial comparisons of values within one channel and is more efficient in hardware circuit designs. When creating hardware designs, for larger models, routing could become prob- lem due to congestion when connections between channels follow arbitrary order. Thus, we re- strict the connections between channels to ensure proper routing: we split the model into k/8 groups, ensuring no cross-connections between the channels of each group. This restriction as well as similar hardware specific routing restrictions can be implemented without affecting the accuracy due to the sparsity of the logic gate network model.
Rand: 640*k-23200k
group sur: 18 classes
Figure 6: LogicTreeNet architecture. The logical ar- chitectures of the layers / blocks are illustrated on a per neuron basis. Circles indicate a logic gate that can be learned while the logical ors remain fixed. During training, for the trainable nodes, we use probabilistic relaxations of logic gates, which we parameterize via a softmax distribution over operators (Eq. ( For the fixed logical ørs, we use the continuous maximum t-conorm relaxation.
3.5 Input Processing
For our smaller CIFAR-10 models (S, M), we use 2 bit precision inputs, and encode them using 3 thresholds as in (7). For our larger CIFAR-10 models (B, L., G), we use 5 bit precision inputs, and process them with low-level feature detectors, in particular, we use edge and curvature detector kernels with thresholds, converting them into binary encodings, which are converted into LGNs and not learned. We note that the gates for the input preprocessing are included in each of the gate counts.

---

4 Related Work
Beyond differentiable LGNs 77. 15]
(covered in Section 2 the related work comprises truth table
networks [6]. 17). binary and quantized neural networks ( 3]. and sparse neural networks 4
Lookup/ Truth Table Networks Lookup table networks (aka. truth table networks) are networks comprised of lookup tables (LUTs) or equivalently (potentially complex) logic gates with n inputs.
There are different approaches for learning or constructing lookup table networks. Chatterjee [T6] constructs truth table networks by "memorizing" training data in an explorative work to consider relations between memorization and generalization. Wang et al. (18), [19] replace the multiplication in BNNs by lookup tables (LUTNet). Benamira et al. [17] transform Heaviside step function activated CNNs into lookup tables by expressing the binary activation of each neuron via a lookup table that implicitly encodes the weight matrix (TTNet). This allows obtaining the binary activation of neuron by "looking up" a value from the truth table at a location encoded via the binary inputs of the layer. Benamira et al. [17] use this as intermediate representation to then convert the truth tables into LGNs via CNF/DNF (conjunctive / disjunctive normal form) conversion. The resulting LGNs allow for efficient and effective formal verification. These resulting LGNs differ from the LGNs considered in this work because they are derived from a conventional CNN and not directly learned, thereby having the inductive bias of the neural network architecture (matmul) and its computational overhead, which is similar to BNNs converted into LGNs. Note that, while TTNets are LGNs, TTNets are not differentiable LGNs there is no differentiable representation of the LGNs involved. Recently, Bacellar et al. 200 extended differentiable LGNs to learning logic gates with more than two inputs.
Binary and Quantized Low- -ow-Precisoon Networks BNNs and quantized neural networks reduce the precision of the weight matrices of a neural network. For example, BNNs typically use the weights -1 and +1, but variations are possible. For quantized neural networks, a popular choice is 8-bit and other options (such as 4-bit (2I) are covered in the literature. This leads to substantially reduced storage requirements of neural networks at the cost of some accuracy. Instead of naively quantizing weights, these approaches typically involve, e.g.. quantization-awant fine-tuning [3]. In addition, for some methods, BNNs and quantized neural networks also reduce the precision of the computations and activations, leading to speedups during inference (2) These approaches typically start with a conventional pre-trained neural network and then convert it into a low-precision representation. BNNs are among the fastest approaches for efficient inference (2).
While BNNs (with binary activations, c.g., Xet (22) are converted into LGNs for inference on hardware (c.g., FPGAs (23). the resulting architectures are fundamentally different from directly trained logic gate networks. BNNs have weight matrices and require multiply-accumulle (MAC) operations to express matrix multiplications. Asymptotically, each MAC requires 8 logic gates while at the same time (with only 2 possible states of the weight) this leads to a smaller expressivity compared to single learned logic gate (with 16 possible states). We include technical discussion in the appendix. While it is disadvantageous for inference, for training, BNNs have the advantage of operating on higher abstraction level, simplifying training and allowing for translation between conventional neural networks and BNNs. We remark that BNNs with binary input activations and binary weight quantization frequently do not use binary output activations [24], which means that only the multiplications within a matrix multiplication are binary. while the remainder of the respective architectures can require floating precision. In contrast to BNNs, differentiable LGNs are not parameterized via weight matrices but instead via the choices of logic gates at each node (7).
Sparse Neural Networks Sparse neural networks are networks that are not densely connected but instead have only selected connections between layers 25 J. (66.. Conceptually, this means multiplying a weight matrix with a binary mask, setting a selection of weights to O. Sparse nets can be utilized for efficient inference the sparsity greatly reduces the number of floating- point operations that have to be executed. For an overview of sparse neural networks, we refer to Hoefler et al. (4).
Due to the binary (i.e., two-input) nature of logic gates, logic gate networks are intrinsically sparse. Thus, LGNs can be seen as sparse networks; however, sparse neural networks are typically not LGNs and typically operate on real values instead of Boolean values. As differentiable LGNs use randomly initialized and fixed connections, is perhaps important to mention that choosing randomly initialized and fixed connections has been shown to also work well for conventional sparse neural networks 55)
7

---

Experiments
5.1
CIFAR-10
We train five sizes of LogicTreeNeets on the CIFAR- 10 data set (9) using the A op- timizer [1]. (33 with a batch size of 128 at a learning rate of 0.02. Additional training de- tails and hyperparameters are in Appendix A.2 report our main results in Table I and Fig- ure Our primary evaluation is with respect to the number of logic gates (bin. ops), which corresponds to the cost in hardware implemen- tations and is proportional to transistor count chip area for ASICs occupancy FPGAs.
Table I: Main results for the CIFAR-10 10 experiments. Our LogicTreeNet models models reduce the required numbers of logic gates by factors 29x compared the state-of- the-art models. Our models are scaled to match accuracies.
Method
Acc.
# Gates
DiffLogic Net (medium) Diff DiffLogic Net (largest)
7
57.39%
0.51 M
62.14%
5.12 M
Conv, TTNet (small)
17
50.10%
0.57 M
Conv. TTNet (large)
17
70.75%
189 M
FINN CNV [3
80.10%
901 M
Comparing our model (M) with 3.08 M gates to the large TTNet model [77], we can ob- serve that, while the accuracies are similar, our model requires only 1.6% of the number of logic gates. Increasing the model size, our model (B) matches the accuracy of FINN (23), while requiring only 16 M gates compared to 901 M gates, a 56x reduction. Considering an even larger variant of our model (L) with 28.9 M gates, we achieve 84.99%. The smallest baseline model that achieves comparable accu- racy (84.95%) LUTNet [19), which requires 44.6x as many logic gates. Finally, consid- ering largest model (G) with 61 M logic gates, we achieve 86.29% test accuracy, We match the accuracy of the XNOR-Net [22]. while this baseline requires 29 as many gates. Indeed, all networks the literature below 4 billion gates perform worse than our 61 million gate network.
LUTNet 19
84.95%
I 290 M
XNOR-Net 22
(NIN)
27
86.28%
1 780 M
RebNet residual)
28
80.59%
2270 M
RebNet residuals)
28
85.94%
2830 M
BinaryNet 29
88.60%
4 090 M
Zhao al.
88.54%
4 4940 M
FBNA CNV
31
88.61%
5 540 M
Hirtzlin et al.
32
91. %
87 400 M
LogicTrreeNet-S NogieTreeNet-M LogicTreeNet-- LogicTreeNNt-LL
60.38%
0.40 M
71.01%
3.08 M
80.17%
16.0 M
84.99%
28.9 M
LogicTreeNut-G
86.29%
61.0
[27
After covering the performance of the trained mod- els, we demonstrate their applicability in hardware designs Xilinx FPGA a proof-of-concept. On CIFAR-10 we limit the hardware development up the base model (B) due labor cost. In Table 2] we report the results. We can observe a very favorable FPGA timing trade-off compared to previous works. Indeed, using our model (B) we achieve 80.17% accuracy, matching the accuracy of the FINN accelerator, but decreasing inference time from 45.6 is 24 ns. In other words, our model achieves 41.6 million FPS, whereas the previously fastest FPGA model achieved 22 thousand FPS (even among all models with 270%). Herein, the limitation preventing us from reaching around 500 million FPS is the transfer speed onto the FPGA. Here, the difference between the smaller models (S & M) and the larger model (B) is that (S & M) receive the input at 2 bit precision whereas (B) receives the input at 5 bit precision. We want to remark that substantially accelerated speeds or reduced power consumption could be achieved by manufacturing custom hardware such ASICs; however, this lies outside the scope of this work and is an interesting future research direction.
Table 2:
Timing results for CIFAR-1O. The time is per image on an FPGA. We use a Xilinx VU13P FPGA. Our times are bottlenecked by the data trans- fer onto the FPGA. 'A' indicates the use of an ASIC.
Method
Acc.
FPGA t.
FINN CNV
80.10%
45.6 jas
RebNet (1 residual)
28
80.59%
167
RebNet (2 residuals)
28
85.94%
333 pas
Zhao et al. 30
88.54%
5.94 ms
FBNA CNV
31
88.61%
1.92 ms
FracBNN (34
80.
356 pa8
TrueNorth 35
83.41%
A: 801
LogicTTreNeet-S
60.38%
ns
LogicTreeNeetM
71.01% %
9 ns
LogicTreeNet-B
80.17%
24
We that all accuracies reported in the main paper are from discretized LGNs, and all gate counts maintain the full convolutional character (i.e., no location-based simplifications). Appendix [A.3] we provide additional gate count details. In Appendix A.4 we include plot comparing the differentiable training mode accuracy to the discretized inference mode accuracy. Further, we refer to Figure for comparison of LogicTreeNet compared to the Pareto-froo of the state-of-the-an

---

5.2 MNIST
We continue our evaluation on MNIST [8. Here,
Table 3: Results of the MNIST experiment. We use Xilinx XC72045 FPGA, the same device as FINN CNV. All other baselines utilize equivalent or more powerful FPGAs.
slightly smaller model ar- chitecture with only (instead of 4) con- volutional blocks due the input size of 28 x 28. Each convolutional block has depth of 3 and, to maintain valid shapes, we use no padding in the first con- volutional block. Each block increases the number of channels by factor of 3. This network architecture is described in greater detail in Appendix AA.ii A..12
Method
Acc. # Gates
FPGA t.
DiffLogic Net (small)
97.69%
48 K 384 K
DiffLogic Net (largest)
98.47%
DWN (0
98.77%
45 ns
TTNet (small)
97. 97.23%
46 K
TTNet [17]
98.02%
360 K
LUTNet T9
98.01 %
5
FINN CNV
23
98.40%
5,28 258 M
641 ns
We display the results for MNIST in Ta- ble[3] Here, our models achieve a range of new SOTAs: compared FINN [3 can observe that our small model already improves the accuracy while simultane- ously decreasing the model size by fac- of 36x, and reducing inference time by factor of 160. Our medium model, with 99. test accuracy improves over BNNs in the literature. When comparing Low- BitNN [36]. non-binary model, our medium model reduces the inference time by a factor of x while still improving accuracy, increasing throughput from 600 FPS to 200 000 000 FPS.
FINN FCN
23
98.86%
LowBitNN
36
99.2 %
152 μrS
FPGA-NHAP [37
97.81% %
4.9 ms
LogicTrreeNe--S NegieTreeNet-M
98.46%
147 K
ns
99.23%
566 K
5 ms
LogicTrreNet-LL
99.35%
1.27
Within the, wwwsssfficatioo-preeeo.tl
regime, comparing to LUTNet 19). we decrease the error from 1.99% to 0.77%, and we note that the larger FPGA that LUTNet uses should enable placing (0.65% error) multiple times, enabling multiple classifications per cycle.
Concluding, our MNIST models are both the most efficient models in the 2 98% regime and at the same time also the highest accuracy FPGA models with an accuracy up to 99.35%.
Variances For small models like the small (S) model for MNIST, which has only 16 kernels in the first layer, variance due to the fixed connectivity can become a significant concern. Thus, for the small models train multiple models simultaneously, and use validation set of 000 images that we hold-out from the training set (not the test set), and based which select the final models. We present the variations before this selection between individual models Table 4 We that with increasing model size, the variance decreases.
Table 4: Variances between in- dividual models MNIST.
Model Individual accs.
S
98.21% + 0.31%
M
99.13% + 0.11%
L
99.29% +: 0.06%
5.3 Ablation Study
To demonstrate the importance of
Table 5: Ablation study on CIFAR-10 wrt. architectural choices.
the provided architectural choices, we conduct an ablation study in T Here, we observe that us- ing trees, residual initializations, as well as pooling are integral convolu-
# train.
layers
# total layers
residual init.
weight decay
2 input channels
Method
Accuracy
to the performance tional LGNs. We also provide ablation wrt. model depth.
LogicTreeNet-LL
84.99%
15
23
Conv. d: 1,1,1,1
80.98%
7
15
Conv. d: 1,1,2,2
82.68%
9
17
Starting with the model depth ab- lation, Table we can observe that the performance improves with increasing model depth. We observe that decreasing the model depth detrimental to perfor- mance. We note that shallower
Conv. d: 2,2,2,
83.32%
11
19
Conv. d: 2,2,3,3
84.13%
13
21
No pooling
81.45%
15
15
X
Gaussian init.
76.18%
15
23
No weight decay 83.94%
15
23
8 input channels
83.53%
15
23

---

models do not directly correspond to reductions in gate counts because, for deeper models, the rates of trivial gate choices like 'A' that are removed during logic synthesis is significantly higher.
Next, we consider the omission of or pool- ing. We can observe that the aceuracy drops by 3.5% when removing or pooling, demon- strating its importance. Setting weight decay
80%
Test Acc.
ww
M
M
70%
to 0 causes small reduction in accuracy by
1%. Allowing each tree use 8 channels as the input, rather than just 2, reduces the ac- curacy (1.4%) because it is better enforce the ability to perform comparisons within one channel at different x, y locations in the ker- nel. However, the more important effect of using only input channels is the resulting improved routing in hardware design layouts.
60%
Residual init. Gaussian init.
50%
100
200
300
400
500
600
700
Epochs
Figure 7: Residual initializations (green) drastically stabi- lize training of the LogieeTreeNe compared Gaussian initialization (orange).
Finally, we ablate the proposed residual initializations. We can observe in the table that the accuracy drops by almost 9% without residual initializations. This means the that the Gaussian initializations are almost unusable for such deep networks. In Figure 7 we display the test accuracy during training and observe that, without our residual initializations, training does not converge and is quite unstable.
We further ablate the effect of residual initialization the distribution of gates in Figure g Here, we can observe that residual initializations not only stabilize training, but also lead to the favorable inductive bias of many gates being 'A', which is automatically reduced during logic simplification.
Gaussian Initialization
0.0
Residual Initialization
0-
0.15
06
1
2
04
3
0.05
02
AAB
-(A B1
A
-IA B1
A B
-(A 8)
81
-8
A B
A
B
-(A A B)-
0.00
-AA B)
-IA B)
5
A B
AV
-(A v B)
IAA B)
B
A-
A B
-MA A B)
000
-AA
Figure 8: Distributions of choices of logic gates in trained MNIST model, comparing Gaussian (left) and
residual (right) initializations. The row number indicates the layer and the column indicates the logic gate.
Conclusion
In this paper, we introduced convolutional differentiable logic gate networks with logic gate tree kernels, integrating a range of concepts from machine vision into differentiable logic gate networks. In particular, we introduced residual initializations, which not only reduces loss of information in deeper networks, but also prevents vanishing gradients, enabling training of deeper LGNs than previously possible. Further, we introduced logical or pooling, which, combined with logic tree kernels, substantially improved training efficiency. Our proposed CIFAR-10 architecture, LogicTreeeNet, decreases model sizes by factors of 2 29x compared to the SOTA while improving accuracy. Further, our inference stack demonstrates that convolutional LGNs can be efficiently executed on hardware. For example, MNIST, our model improves accuracy while achieving 160x faster inference speed, and on CIFAR-10, our model improves inference speed by 1900 over the state-of-the-arr, An interesting direction for future research is applying convolutional differentiable logic gate networks to computer vision tasks with continuous decisions like object localization. We hope that our results motivate the community to adopt convolutional differentiable LGNs, especially for embedded and real-time applications where inference cost and speed matter most.
Acknowledgments and Disclosure of o Funding
This work was supported part by the Federal Agency for Disruptive Innovation SPRIN-D. CB is sup- ported by the Land Salzburg within the WISS 2025 project IDA-Lab (20102-F1901 166-K666 KZP and SE is supported by the ARO (W91 I NNF21-1-00125) the ONR (N00014- 23-1-2159), and the CZ Biohub. We thank the reviewers for their supportive and helpful comments.
10

---

References
[1] R. Desislavov, F. Martinez-Plummen and J. Hemandez--rallo Orallo, "Compute and energy consump- tion trends in deep learning inference," Computing Research Repository (CoRR) in arXiv, 2021.
[2] H. Qin, R. Gong, X. Liu, X. Bai, J. Song, and N. Sebe, "Binary neural networks: A survey," Pattern Recognition, vol. 105, p. 281, 2020.
[3] A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer, "A survey of quantization methods for efficient neural network inference," Computing Research Repository (CoRR) in arXiv, 2021.
[4] T. Hoefler, D. Alistarh, T. Ben-Nun, N. Dryden, and A. Peste, "Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks," The journal of machine learning research (JMLR), 2021.
[5] S. Liu, T. Chen, X. Chen, L. Shen, D. C. Mocanu, 7. Wang, and M. Pechenizkiy, "The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training," in International Conference on Learning Representations (ICIR), 2022.
[6] P. Molchanov, S. Tyree, T. Karras, T. Aila, and J. Kautz, "Pruning convolutional neural networks for resource efficient inference," " in International Conference on Learning Represen-
lations (ICLR), 2017.
[7] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen, "Deep Differentiable Logic Gate Net- works," in Proc. Neural Information Processing Systems (NeurIPS), 2022. [8] Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database," 2010. [Online]. Available:
//cyy/annneccn...mmm/m// lecun. com/ exdb/mmist//
[9] A. Krizhevsky, G. Hinton, et al., "Learning multiple layers of features from tiny images," 2009.
[10] E. van Krieken, Acar, and van Harmelen, "Analyzing differentiable fuzzy logic operators," Computing Research Repository (CoRR) in arXiv, 2020.
[11] G. J. Klir and B. Yuan, Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice Hall,
1997.
[12] D. Kingma and J. Ba, "Adam: A method for stochastic optimization." in International Confer- ence on Learning Representations (ICLR), 2015.
[13] Krizhevsky, Sutskever, and G. Hinton, "ImageNer Classification with Deep Convolutional Neural Networks," in Proc. Neural Information Processing Systems (NeurIPS), 2012.
[14] K. He, X. Zhang, S. Ren, and Sun, "Deep residual learning for image recognition," in Proc. International Conference on Computer Vision and Puttern Recognition (CVPR), 2016.
[15] F. Petersen, "Training a neural network to perform machine learning task," in WIPO (PCT), WO2023143707AL EP2022/051710, 1W112001444, CN202280089954.74 KR KR1020247028676A, etc, 2022.
[16] S. Chatterjee, "Learning and memorization," in International Conference on Machine Learning (ICML), 2018
[17] A. Benamira, T. Guérand, T. Peyrin, T. Yap, and B. Hooi, "A scalable, interpretable, verifi- able differentiable logic gate convolutional neural network architecture from truth tables." " Computing Research Repository (CoRR) in arXiv, 2023.
[18] E. Wang. J. J. Davis, P. Y. K. Cheung, and G. A. Constantinides, "LUTNet: Rethinking inference in FPGA soft logie," in IEEE International Symposium on Field-Pros Poald-Programmable Custom Computing Machines, 2019,
[19] E. Wang, J. J. Davis, P. Y. K. Cheung, and G. A. Constantinides, "LUTNet: Learning FPGA configurations for highly efficient neural network inference," IEEE Transactions on Computers, 2020. to appear.
[20] T. Bacellar, Z. Susskind, M. Breternitz Jr, E. John, L. K. John, Lima, and F. M. França, "Differentiable weightless neural networks," in International Conference on Machine Learning (ICML), 2024.
[21] J. Choi, Z. Wang. S. Venkataramani, P. I.J. Chuang, V. Srinivasan, and K. Gopalakrishnan, "Pact: Parameterized clipping activation for quantized neural networks." Computing Research Repository (CoRR) in arXiv, 2018.

---

[22] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi, "Xnor-net: Imagenet classification using binary convolutional neural networks," in Proc. European Conference on Computer Vision (ECCV), 2016.
[23] Y. Umuroglu, N. J. Fraser, G. Gambardella, M. Blott, P. Leong, M. Jahre, and K. Vissers, "Fimn: A framework for fast, scalable binarized neural network inference," " in Proceedings of the 2017 ACM/SIGDA International Symposium on Field- PeeedProgrammable Gate Arrays, 2017,
pp. 65-74.
[24] A. Santos, J. D. Ferreira, O. Mutlu, and G. Falcao, "Redbit: An end-to-end flexible framework for evaluating the accuracy of quantized cnns," " Computing Research Repository (CoRR) in arXiv, 2023.
[25] S. Liu, Y. Tian, T. Chen, and L. Shen, "Don't be dense: Sparse-to-sparse gan training without sacrificing performance," " International Journal of Computer Vision, 2023.
[26] S. Liu, T. Chen, X. Chen, X. Chen, Q. Xiao, B. Wu, T. Kärkkäinen, M. Pechenizkiy, D. Mocanu, and Z. Wang. "More convnets in the 2020s: Scaling up kernels beyond 51x51 using sparsity." in International Conference on Learning Representations (ICLR), 2023.
[27] J. Yu, PyTorch Implementation of XNOR-Net, Archived in the Internet Archive on 2023/05/11
8:48, 2023. [Online]. Available: hatps://ggihub.... com/ jieeaoyeeeoaitaa -Ntt
[28] F. K. Mohammad Ghasemzadeh Mohammad Samragh, "Rebnet: Residual binarized neural network," in Proceedings of the 26th IEEE International Symposium on Field- Prodd-Programmable Custom Computing Machines, ser. FCCM '1, 2018.
[29] I. Hubara, M. Courbariaux, D. Soudry, R. El- Yaniv, and Y. Bengio, "Binarized neural networks." " in Proc. Neural Information Processing Systems (NeurIPS), 2016.
[30] R. Zhao, W. Song, W. Zhang. T. Xing. J.-H. Lin, M. Srivastava, R. Gupta, and Z. Zhang, "Accelerating Binarized Convolutional Neural Networks with Software-Programmabe FPGAs," Int't I Symp. on Field- PrgeddProgra Gate Arrays (FPGA), Feb. 2017.
[31] P. Guo. H. Ma, R. Chen, P. Li, S. Xie, and D. Wang. "Fbna: A fully binarized neural net- work accelerator," in 2018 28th International Conference on Field Programmable Logic and Applications (FPL), 2018.
[32] T. Hirtzlin, B. Penkovsky, M. Bocquet, J.-O. Klein, J.-M. Portal, and D. Querlioz. "Stochastic computing for hardware implementation of binarized neural networks," IEEE Access, vol. 7, pp. 76 403, 2019.
[33] I. Loshchilov and F. Hutter, "Decoupled Weight Decay Regularization," in International Conference on Learning Representations (ICLR), 2019.
[34] Y. Zhang, J. Pan, X. Liu, H. Chen, D. Chen, and 7. Zhang. "Fracbnn: Accurate and fpga- efficient binary neural networks with fractional activations," " in The 202/ ACM/SIGDA Interna-
tional Symposium on Field-Proge Programmable Gate Arrays, 2021.
[35] S. K. Esser, P. A. Merolla, J. V. Arthur, A. S. Cassidy, R. Appuswamy, A. Andreopoulos, D. J. Berg, J. L. McKinstry, T. Melano, D. R. Barch, et al., "Convolutional networks for fast, energy-efficient neuromorphic computing," Proceedings of the National Academy of Sciences of the United States of America, vol. 113, no. 41, p. 11 441, 2016.
[36] J. Zhan, X. Zhou, and W. Jiang, "Field programmable gate array-based all-layer accelerator with quantization neural networks for sustainable phhsscal systems," Software: Practice and Experience, 2020.
[37] Y. Liu, Y. Chen, W. Yc, and Y. Gui, "FPGA-NHAP: A General FPGA-Based Neuromorphic Hardware Acceleration Platform With High Speed and Low Power," " IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 69, 6. pp. 2553-2566 2022.
[38] Z. Tu, X. Chen, P. Ren, and Y. Wang. "AdaBin: Improving Binary Neural Networks with Adaptive Binary Sets," in Proc. European Conference on Computer Vision (ECCV), 2022.
[39] R. Gong, X. Liu, S. Jiang, T. Li, P. Hu, J. Lin, F, Yu, and J. Yan, "Differentiable soft quantization: Bridging full-precision and low-bit neural networks," " in Proc. International Conference on Computer Vision (ICCV), 2019.
[40] H. Qin, R. Gong, X. Liu, M. Shen, Z. Wei, F. Yu, and J. Song, "Forward and Backward Infor- mation Retention for Accurate Binary Neural Networks." in Proc. International Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
12

---

[41] H. Qiu, H. Ma, Z. Zhang, Y. Gao, Y. Zheng, A. Fu, P. Zhou, D. Abbott, and S. F. Al-Sarawi, "Rbnn: Memory-efficient reconfigurable deep binary neural network with ip protection for internet of things," IEEF Transactions Computer-Aided Design of Integrated Circuits and Systems, 2022.
[42] S. Zhou, Y. Wu, Z. Ni, X. Zhou, H. Wen, and Y. Zou. "DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients," Computing Research Reposi- tory (CoRR) in arXiv, 2016.
[43] M. Shen, X. Liu, R. Gong, and K. Han, "Balanced binary neural networks with gated resid- ual," in ICASSP 2020-2020 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), 2020.
[44] A. Paszke, S. Gross, F. Massa, et al., "Pytorch: An imperative style, high- performance deep learning library." " in Proc. Neural Information Processing Systems (NeurIPS), 2019.
13

---

A Implementation Details
A.1 Model Architecture Details
In this section, we discuss the convolutional LGN architectures in detail.
A.1.1 CIFAR-10 Architecture
In the following, we describe the model for CIFAR-10 from Figure 6 blayer by layer:
convolutional block with kernels with receptive field of size 3 and depth d i.e., each kernel is a logic gate tree with seven logic gates, mapping 8 inputs to one output.
An or pooling layer with kernel size 2 x and stride 2. [shape after layer: k x 16 x 16] convolutional block with 4*k kermels with receptive field of size 3 and depth
An or pooling layer with kernel size 2 and stride 2. [shape after layer: 4+k 8 8]
convolutional block with 16*k kernels with receptive field of size 3 x and depth
3.
An pooling layer with kernel size 2 x 2 and stride 2. [shape after layer: 16*k x 4 x 4]
A convolutional block with 32+k kernels with receptive field of size 3 x 3 and depth d = 3.
An or pooling layer with kernel size 2 x and stride 2. [shape after layer: 32*k x x 2]
Flattening the hidden state. [shape after flattening: 128*k]
Regular differentiable logic layer 128*k + 1280*k (+)
Regular differentialle logic layer 1280*k + 640*k (+)
Regular differentiable logic layer 640*k - 320*k (+)
GroupSum with 10 classes 320*k + 10.
(All convolutional blocks are zero-padded with padding of size 1 to maintain respective shapes.)
(+); For the size CIFAR models, we use 2x as many gates in the final layers.
An additional implementation detail is that we can implement the last 3 layers in fused fashion, using single convolutional block/layer with depth d = and only single kernel application, which is functionally equivalent and faster due to our fused kernels that are available for convolution.
A.1.2 MNIST Architecture
The architecture for MNIST- data has to account for the smaller input sizes (28 28). Thus, we use only 3 instead of 4 convolutional blocks for this architecture.
A convolutional block with k kernels with receptive field of size x 5 and tree depth d = 3, without padding.
An pooling layer with kernel size 2 x and stride 2. [shape after layer: k 12 x 12]
A convolutional block with 3+k kernels with receptive field of size 3 x 3 and depth d = 3.
An or pooling layer with kernel size 2 x 2 and stride 2. [shape after layer: 3+k X 6 x 6]
convolutional block with 9*k kernels with receptive field size 3 x and depth 3.
An or pooling layer with kernel size 2 x and stride 2. [shape after layer: 9+k x 3 x 3]
Flattening the hidden state. [shape after flattening: 81*k]
Regular differentiable logic layer 81 - 1280* (+)
Regular differentiable logic layer 1280*k + 640*k (+)
Regular differentiable logic layer 640*k - 320+k (+),
GroupSum with 10 classes 320+k ++ 10.
(+); For the S & M size MNIST models, use 2x many gates in the final layers.
14

---

A.2 Training Details
In Table 6 we summarize the hyperparameters for each model architecture configuration. We observe that the hyperparameter that depends the most the data set is the learning rate 1). The temperature and thus the range of attainable outputs Rat/e/T has a minor dependence on the data set. We use weight decay only for the CIFAR-10 models as it does not yield advantages for the smaller MNIST models. We note that convergence, when training with weight decay, is generally slightly slower but leads to slightly better models. Models trained with weight decay tend to have more gates.
Table 6: Hyperparameters for each model and data set: softmax temperatures т, learning rates weight decays B, and batch sizes bs. For reference show the relationship last layer per class nez/e. The range of attainable class scores is [0, nzt/e/T).
include the number of output neurons in the
Data set
CIFAR-10
10
MNIST
Model identifier
M
B
I.
G
S
M
I.
Model scale
k
256
512
1224
2560
256
Temperature
T
20
40
280
340
450
6.5
28
35
Learning rate
?
0.02
0.02
0.02
0.02
0.02
0.01
0.01
0.01
Weight decay
0.002
0.002
0.002
0.002
0.001
0
0
0
Batch size
be
128
128
128
128
128
512
256
128
Output gate factor
ox
1
2
1
2
2
1
input bits
5
Outputs/class
Tesffe net/e/T
8K
32K
64K
80K
1K
4K
8K
Max score
51
205
117
193
182
158
146
234
For the loss, we use different softmax temperatures depending on the model size. We observe two important relationships for choosing 7: (i) r depends on the number of output neurons (larger number of output neurons + larger 7) and (ii) T depends on how certain the model will be after training on the respective dataset, i.c., for hard task with low accuracy, while, for an easier task with higher accuracy, we should choose a smaller The reason for this that entrroy requires smaller logit variances if the model is less certain and requires larger logit variances if prediction is certain. A good rule of thumb during scaling is that the optimal temperature proportional the square-root of the number of output gates (T* x (Mtff))
should choose larger т,
For the CIFAR-10 B, L, and G models, we use neural network teacher, supervising the class scores. When using a teacher on the class score level, good rule of thumb is to increase the softmax temperature by factor of /2.
For CIFAR- 10, we split the training data into 45 000 training images and 5 000 validation images, and evaluate every 2 000 steps select the best model. For MNIST, we split the training data into 50 000 training images and 10000 validation images, and evaluate every 000 steps to select the best model.
A.2.1 Memory Access Advantages through Fused Trees and Pooling
Using logic gate trees as convolutional kernels with pooling allows for substantial speedup during training. For this, we fuse the entire The reason behind this two-fold, illustrated for the case of depth d = and 2 x pooling: (i) 2 applications of the 7 Iearnable logic gates comprising the tree. Then, we apply the maximum t-conorm to pool the 4 outputs of the 4 tree applications
well pooling into single CUDA kernel operation.
after reading the necessary 32 inputs, we perform
single output value. Here, we do not need read the intermediate results from memory but can instead keep them in registers. This prevents 28 additional memory read operations. (ii) as each set of tree applications only has single output after pooling, is sufficient write only this individual output (as well as the index of the pooling operation) to memory, saving 28 memory write operations, which are expensive. Further, this also reduces the memory footprint training by factor of around 10x. This procedure requires recomputing selected intermediate values within each block during the backward pass; however, the memory access savings offset this small additional computational cost.
15

---

A.2.2 Computational Requirements
The typical training time per epoch for the model on single NVIDIA RTX 4090 GPU is 30 seconds. Noteworthy is that d' kemnels typically bottlenecked by CUDA compute cores, whereas d and d = kernels are bottlenecked by memory bandwidth. While we explored (when fused) are very expensive (> 10x) due register pressure. Generally, but with very limited exploration, simply going from d = 3 to d = 4 did not improve performance / gate. 4 kernels can also be expressed, without fusing, using logic gate tree layers; however, with this the memory consumption during training increases (+s 10x) which becomes a bottleneck.
4 kernels, they
A.3 Inference Details
For efficient hardware implementations, routing is an important consideration and the ability to place the LGN without conges- tion is paramount, Due to the sparsity of differentiable logic gate networks, limiting the choice of connections gree does not negatively affect accuracy. Accordingly, we select connections such that the model could be split into k/8 separated models that are only recombined at the stage of output gates after accumulation, akin to using grouped convolutions with a con- stant number of groups throughout the network. This prevents congestions without reducing the accuracy. Additional routing re- strictions can straighfforwardly be implemented in differentiable LGNs without incurring performance penalties.
0
reasonable de-
XOYZ
We illustrate the placement of our MNIST model (M) on Xilinx XC77045 FPGA in Figure
We developed scalable logic synthesis tools that simplify the logic gate networks after training. For example, for our large MNIST model (L), during training, the main network has 3 216 128 gates. After training, in the discrete LGN, many of these gates trivial (e.g.. 'A' or constant) or not connected, and also further simplifications are possible. After logic synthesis, the number of logic gates 697 758. Herein, the full convolutional nature of the network maintained (and gates that have zero padded input are still counted as full gates.) For the group sum operation,
KOYO
Figure 9: MNIST model (M).
tree adder that asymptotically uses 7 gates per output, and with is, such, included the gate counts in the paper.
A.4 Train Test
Test Accuracy and Discretization Error
In Figure 10 we plot the training and test accuracies for training convolutional LGN on CIFAR-10 99. Here, we can ob- serve that the discretization error, i.e., the difference between the inference (hard)
1.00
0.95
mode accuracy and the differentiable train- ing mode accuracy is very small during late training. During early training, the discretization error is more substantial be- cause the method first learns "smooth" differentiable LGN (with high levels of uncertainty in the individual logic gate choices), which later converges to dis- crete choices for each logic gate. The discretization step chooses the logic gate with the highest probability for inference mode. Accordingly, during early training, the discretization causes larger changes, negatively affecting accuracy, while dur-
0.90
Accuracy
0.85
0.80
(inference mode)
0.75
Test Acc. (inference mode)
Test Acc. (differentlable train mode)
0.70
200
400
600
800
1000
Figure 10: CIFAR-10 training and test accuracy plot. The discretization eтror, i.c., the difference between the inference (hard) mode accuracy and the differentiable training mode accuracy very small during late training.
16

---

ing late training, the discretization barely causes any changes and therefore does not considerably affect accuracy. We note that there is no noticeable overfitting behavior.
A.5 Ablation of the Residual Initialization Hyperparameter Z3
In Figure I1. we ablate the choice of 23, which the hyperparameter that indicates how strongly the residual initialization is applied. We illustrate the ablation for MNIST model. The model per- forms well, when 23 2 2 (23 1.5 is included but
0.990
0.988
reaches only 13%.) While 23 = 5 is not the optimal choice for this particular model and training length, we have observed that, for larger models as well as for longer trainings, larger 23 tends to be favorable. For example, on CIFAR-10, with the greater model depth, 23 of 2 is too small and prevents training, so we generally recommend using 23
0.986
Figure 11: Test accuracy of an MNIST model with different choices of zs for the residual initialization, steps of 0.5, Averaged over seeds.
B
Additional BMAC and BNN Discussions
B.1 BMACs in Logic
When translating BNN into an LGN for inference on FPGAs, BNNs require BMACs (multiply- accumulate), which often expressed via an XNOR (-(a @ b)) for the multiplication and bitcount operation for the accumulation. In the case n input bits, the necessary n MAC can be expressed using (n)
logic gates: n. logic gates are necessary for the XNORs and R 7n logic gates for the accumulating bitcount. Further, this process adds a delay of (log n) to the logic circuit. This means that BMAC is not one logical operation but instead typically requires around binary logical operations (not accounting for additional thresholding or potentially batch- normalization operations).
B.2 Floats in BNNs
BNNs typically use 1-bit input activation and 1-bit weight quantization, but output activation quantization [24). This means that only the multiplications within a matrix multiplication are binary, while the remainder of the respective architectures is typically non-binary (24). As in some residual BNN approaches (38)-44), [43, the residuals are not quantized, they require an additional FL.OP (or integer operation) overhead between the layers; due to the cost of FL.PPs in logic gates (> 1000 binary OPs), effective deployment on a logic level has not been demonstrated for these unquantized residual approaches. Quantizing the residuals typically comes substantial accuracy penalty as demonstrated, e.g., by Ghasemzadeh et al. (28). Thus, as these networks use full-precision residuals, a fair comparison is not possible. Still, float-residual BNN approaches have important implications for speeding up GPU inference if (i) large matrix multiplications are necessary and (ii) the savings during the binary matrix multiplication itself outweigh the costs of converting between bit-wise representations and floats/integer representations; however, float-residual BNNs are not suitable for efficient logic gate based inference in hardware, e.g., on FPGAS or ASICs.
C List of Assets
CIFAR-10 9 [different open licenses]
MNIST
8
[CC [icense]
PyTorch
44
[BSD 3-Clause License]
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: github.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yss]
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:://// httparppp.....pp.......cccccaata
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
18

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
19


Reviews:
[{"review_id": "HUHvDhlKOc", "reviewer": "Reviewer_BM74", "summary": "This paper introduced a convolutional logic gate network (LGN), which works effectively on high-dimensional spatial images. Inspired by LGN and convolutional neural nets (CNNs), the authors proposed (1) Logic Gate Tree as convolutional kernels (2) Logical OR as the pooling layer, and (3) residual initialization (instead of Gaussian random init). Besides, the authors also developed an engineering strategy to speed up the training, using low-level CUDA kernels, which is well admired. The authors have shown impressive results, in terms of performance and efficiency, on CIFAR10 and MINIST datasets.", "questions": "See weakenss.", "limitations": "The authors could provide a paragraph discussing their potential limitation to solving more complex CV tasks involving continuous decisions. E.g., regressing boundaries of bounding boxes (Object Detection/Tracking), localization and mapping (SLAM), generative CV, etc.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Several novel ideas (technical contributions) exist in this paper. I especially admire the idea of primarily using a feedforward logic gate during initialization, which prevents both loss of information and vanishing gradients. The motivation and intuition are very clear in L208-215.\n- The authors have demonstrated their design using insightful experiments. For example, when introducing logic OR as pooling, the authors discussed that training can implicitly prevent saturation of activations using experiments, which is very interesting.\n- The experimental performance is impressive.\n- The engineering strategy and CUDA implementation (and open-source) would benefit the community and future research a lot.\n- The paper is very well-written. Though I'm not an expert in this domain, it is easy to understand the storyline, technical details, related works, and intuition.", "weaknesses": "- Some suggestions on Figure presentation.\n  - Figure 1. Also consider showing the speed advantage, as today's high-performance edge devices (Nvidia Xavier, Orin, etc) can accommodate large-weight networks and the weights of other works are already relatively small. Reporting that you can run inference the CIFAR-10 image in ~0.7 $\\mu s$ on an FPGA chip would be very impressive even without looking into your paper. Besides, what is \"Pareto-curve\" (in the caption)? I didn't see it shown in the figure.\n  - Figure 2. Maybe change the input into some \"flattened inputs\" (L112) to better show that vanilla LGNs are not designed to process images.\n  - Figure 3. Maybe re-arrange the figure and get some space for the details of your structure. Better to also show how your network process \"channels\", as currently it is not clear from the figure. I also suggest adding some annotations, e.g., in the figure, adding the same notations like \"depth d=2\", the green squares are the selected Cm Ch Ck, in the caption also mention your NN can share weights like CNN in different spatial regions. Polishing this figure can help the reader understand the processing details quicker than understanding Eqn. (3).\n- Some technical questions need to be better explained.\n  - L114-115, why are vanilla LGNs \"very computationally expensive to train\"? Is it because they didn't implement CUDA kernels?\n  - I noticed that in the design of the network, the authors chose a relatively small depth but large channels (2 vs 40,400,2000+). Is there any intuitive reason to do so? How many layers (depth) does vanilla LGN have?\n  - The authors have implemented CUDA kernel, but in the speed comparison (Table 2), the results are from Xilinx FPGA (I guess only has CPU). Why didn't the authors implement experiments on GPU? Is it for fair comparison w/ others? Maybe I missed something, but on CPU, what's the advantage of implementing CUDA kernel？", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your positive feedback, and for appreciating the feedforward gates during initialization, our ablation studies, our experimental performance, as well as our engineering and CUDA implementations. \nWe appreciate that you find our \"paper is very well-written\".\nIn the following, we address each of your recommendations, questions, and concerns.\n\n> Some suggestions on Figure presentation. Figure 1. [...] Figure 2. [...] Figure 3. [...]\n\nThank you for each of these helpful suggestions. We will incorporate them into Figures 1, 2, and 3, as well as their captions.\n\n> Some technical questions need to be better explained.\n> L114-115, why are vanilla LGNs \"very computationally expensive to train\"? [...]\n\nThe primary reason for vanilla LGNs to be very computationally expensive to train is that they are bottlenecked by memory and cache read and write accesses during training.\nIn contrast, by utilizing the proposed convolutional structure, the parameter sharing enables loading fewer parameters into a cache that is shared between different cores of the GPU, requiring reading only once.\nMoreover, by fusing the tree structure, and not storing any intermediate results in memory, expensive global memory writes are drastically minimized. If $d=2$ and we have a maxpool of $2\\times 2$ fused to it, then 15 logic gates are executed during forward, and only a single output activation has to be stored. While this requires recomputation of intermediate results during backward, only one out of four paths through the pooling needs to be backpropagated through, and the choice of this path requires storing only 2 bits. This, combined, leads to a much higher utilization of the memory bandwidth, while at the same time reducing memory access requirements, and drastically improving the utilization of actual compute units in the GPU.\nFurthermore, the sparsity pattern as introduced by using convolutions is also more favorable for memory accesses.\n\nBeyond this, we have made contributions to faster training of vanilla LGNs, and, e.g., reduced memory access from reading 18 floats down to reading 6 floats by precomputing coefficients in a simplification of Eq. (1). In particular, Eq. (1) can be rewritten as $u_0 \\cdot a_1 + u_1 \\cdot a_2 + u_2 \\cdot a_1 \\cdot a_2 + u_3 \\cdot 1$ for a certain set of $u_0, u_1, u_2, u_3$, which we precompute in a separate kernel, and thus only have to compute once for the entire batch. This constitutes another fundamental speedup that applies to both vanilla LGNs and convolutional LGNs, reducing both memory and compute requirements.\n\n> I noticed that in the design of the network, the authors chose a relatively small depth but large channels (2 vs 40,400,2000+). Is there any intuitive reason to do so? How many layers (depth) does vanilla LGN have?\n\nThe intuitive reason for the large number of channels compared to the depth is that the network is very sparse and only uses logic, and thus the expressivity of each channel is smaller (compared to a conventional CNN).  Thus the model requires more channels in order to attain high overall expressivity.\n\nThe depth of 2 that you mention refers to the depth of each convolutional block. With 4 convolutional blocks and 2 randomly connected layers for the head, the total trainable depth of our model is 10 layers. Including the or-pooling, we have a total of 18 layers.\n\nThe best performance with vanilla LGNs is achieved with 4-6 layers. [7] reported trying up to 8 layers, and from our own experiments we can confirm that vanilla LGNs with 8 or more layers converge extremely slowly and to lower accuracies. The best vanilla LGN MNIST model uses 6 layers and the best vanilla LGN CIFAR-10 model uses 5 layers. The best vanilla LGN for CIFAR-10 requires 1,024,000 neurons per layer.\n\nThus, our CIFAR-10 model has 2x the trainable depth and 3.6x the total depth compared to the vanilla LGN, while having substantially fewer channels.\n\n\n> The authors have implemented CUDA kernel, but in the speed comparison (Table 2), the results are from Xilinx FPGA (I guess only has CPU). Why didn't the authors implement experiments on GPU? Is it for fair comparison w/ others? Maybe I missed something, but on CPU, what's the advantage of implementing CUDA kernel？\n\nTo clarify, while all training is performed on GPU (as it requires float operations), the inference is performed on FPGAs or CPUs as it only requires bitwise logical operations.\nWhile we could have also run inference on GPU, GPUs are highly optimized for float operations and rather neglect bitwise logics; further, for GPUs the speed of transferring input data would be the bottleneck.\nAs FPGAs are effectively slow proxies of ASICs, utilized in hardware design, they are the closest one can get to ASICs without actually manufacturing ASICs.\n\n> The authors could provide a paragraph discussing their potential limitation to solving more complex CV tasks involving continuous decisions. E.g., regressing boundaries of bounding boxes (Object Detection/Tracking), localization and mapping (SLAM), generative CV, etc.\n\nIndeed, we have not explored CV tasks involving continuous decisions.\nContinuous decisions, as the ones listed, are a great direction for future work, and we have included a paragraph in the camera-ready to highlight this.", "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": "", "extra_scores": {}}, {"review_id": "BIt2nch0mN", "reviewer": "Reviewer_zmod", "summary": "The presented work is a significant extension to \"Deep Differentiable Logic Gate Networks\" previously presented at NeurIPS 2022 [7]. Additional contributions are the support for convolutions including logic gate trees / or-pooling and residual initializations. All additions together allow to train logic gate networks that are deeper, achieving SOTA accuracies and beyond while using remarkably fewer resources during inference and training as well. The authors promise to also make the code publicly available.", "questions": "Reflecting on lines 216-226: the reviewers personal view of residual connections is similar to the authors' and can be summarized as means to preserve (mutual) information throughout the network. Although residual initializations seem pivotal to training of LGNs, they could potentially also help float-based NN trainings without the need to add residual connections. If the authors share that view it would be great to add a discussion on this to the presentation.\n\nWhy is the choice of gates being limited to 2-input variations? Especially in the context of convolutions and pooling, wouldn't it make sense to also allow for N-input OR-gates with N >> 2? It would also allow for reducing depth and signal propagation delays.", "limitations": "Despite improved training and inference efficiency, experimental results are limited to very small classification tasks. A single bigger task would prove scalability (or not).\n\nLines 416-417. The chosen model sizes (S,M,L,G) do not prove saturation of accuracy (except maybe for MNIST), but you even mention that they improve with increasing model depth. If there's a reason why you stop early, please mention it in the presentation.", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Improving efficiency of (small scale) neural networks substantially. Lowest latency of all SOTA baseline results, the majority of them being much slower with even worse accuracy.", "weaknesses": "There are a few issues with the clarity of the presentation. Upfront it should be mentioned that the Appendix is vital to understand many details (architectures, choice of parameters, memory usage, memory access, etc.) and should certainly be published as well. It was only supplementary material as part of the review.\n\nFigure 4 only shows an effect, but does not explain why pre or-pooling is superior to the other 2 and the text does neither.\n\nLines 228-229 seem to contradict the statement made in line 115. Does the training time mentioned in line 115 mark a baseline? If yes, then please state that and put it in relation to the \"substantially improved computational training efficiency\" lateron.\n\nIn figure 6 (and from the associated text) it is not clear which 10 of the 18 subnetworks are trained. Is it possible to mark those? Are the blue networks the connection index tensors? A few more detailing remarks would help to understand the figure better.\n\nTable 1 does not include a SOTA baseline using float weights. Even if that is a bit out-of-scope, it would help to put accuracies vs. number of bits (e.g. 32 (for FP32) * N parameters) in perspective.\n\nTable 2 lists results for a Xilinx XC7Z020. If not mistaken, the upper limit for the number of configurable gates is ~1.3M. How does the execution of models M/L/G that all exceed that number by far actually work? Same for the MNIST model L in Table 3. Are any additional resources of the FPGA device being used? A breakdown would be very useful.\n\nTable 5 contains a line for \"No or pooling\". It is unclear why it lists the number of total layers to be 10 and not 14. Please explain.\n\nAppendix, Section A.3.3 CPU Inference Times: the CPU in use is not being mentioned. Is this a desktop/workstation CPU or the ARM-based CPU of the Xilinx XC7C020?\n\nTypos:\n\nline 441: \"This means the that the...\" -> \"This means that the...\"\n\nAppendix, line 6: \"... from Figure ??...\" -> please cite the correct figure, my guess is #6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for providing such extensive and positive feedback, and for appreciating our substantial efficiency improvements, and achieving the lowest latency of all SOTA baseline results.\nDue to the character limit, we keep our reponses short; please let us know if you would like us to elaborate.\n\n> [...] Appendix is vital [...]\n\nThank you for this remark. For the camera-ready, papers have an additional page, so we can fit a few more details in the main paper and improve the clarity. Yes, we will publish the appendix as well. \n\n> Figure 4 only shows an effect [...]\n\nFig. 4 indeed only shows the effect that the model automatically regularizes itself to have an activation level of around 50%. (Ideally, act. levels are ~50% to maintain high information content.) \"pre or-pooling\" refers to the activation level before the or-pooling operation and \"post or-pooling\" refers to the activation level after the or-pooling operation (both from the same model). \"no or-pooling\" refers to a modified architecture without or-pooling. We clarified the notation and explanation for the revision.\n\n> Lines 228-229 [...] line 115. [...]\n\nIn line 114-115, we referred to vanilla LGNs, which we will explicitly clarify in the camera-ready.\nWe provide overall training speeds in the supplementary, and offer to add a direct comparisons between existing vanilla LGN, our vanilla LGN, and our convolutional LGN training speeds for the revision.\n\n> In figure 6 [...]\n\nWe apologize for the ambiguity. The layers that are trained are the \"Conv\" (/\"C\") and the \"Rand\" layers; each of the \"Conv\" blocks in the figure contains 2 layers of logic.\nBlue illustrate the input + hidden states; the index tensors are encoded within the green \"Conv\" and \"Rand\" blocks. We will explain and mark it in the revision.\n\n> SOTA baseline using float weights.\n\nThanks for the suggestion, we will include SOTA models with float weights into Table 1.\n\n> Table 2 lists results for a Xilinx XC7Z020. [...]\n\nFor CIFAR-10, as listed in the caption (Tab. 2), the times for M/L/G are based on CPU simulations.\n\nFor the MNIST L model, you are correct, based on our initially reported number of gates would not have fit on the FPGA.\nWhile we were able to fit the model on the FPGA, at the time of writing, we could only accurately compute the number of gates for the CIFAR-10 model, and used an upper bound for the numbers of gates for MNIST (we used the total number of gates during training).\n\nIn the rebuttal PDF (Fig. 1) we illustrate that a majority of gates is actually a trivial feedforward \"A\", which can be optimized away. Additional simplifications are also possible, e.g., \"True and B\" -> \"B\".\nAs Vivado optimizes for 6-LUTs, we could not read out the number of ASIC gates.\nAs there were no open-source libraries for logic gate network simplification that scale to our model, we developed our own stack, which at the time of writing only supported CIFAR. \nNow, it also supports MNIST, and we can report more accurate numbers of ASIC gates for MNIST:\n\n| MNIST | # Gates (prev.) | # Gates (new) |\n|--|--|--|\n| LTNet-S | 296 K | 197 K |\n| LTNet-L | 4.74 M | 671 K | \n\n(The actual number of logic gates will still be lower than this number.)\n\n> Are any additional resources of the FPGA device being used?\n\nSo far, we only utilize Logic Cells and Flip Flops to keep it as close as possible to efficient ASIC designs.\n\n> Table 5 [...] \"No or pooling\". [...]\n\nThe or pooling pools 2x2 inputs, and thus requires 2 levels (layers) of 2-input logic, which can be reduced to a single level on certain hardware (see below).\n\n> Appendix, Section A.3.3 CPU [...]\n\nThe CPU in Appendix A.3.3 is an AMD Ryzen 5 7600X (consumer desktop) CPU, and we utilize only a single thread of the CPU.\n\nThanks for pointing out the typos, we fixed them for the camera-ready.\n\n**Questions:**\n\n> residual initializations\n\nThis could indeed be a very interesting direction for future work. We will include a discussion in the revision.\n\n> limited to 2-input \n\nBeyond what we discussed in the paper, we actually considered, implemented, and evaluated 4-input and 6-input gates in the convolutional kernels. We observed that the 2-input tree formulation leads to more favorable learning dynamics, as well as a better trade-off between numbers of gates and accuracy, which is why we stuck with 2-input gates.\n\n> OR-gates with N >> 2\n\nE.g., for OR-pooling, yes, these can be implemented, e.g., with a 4-input OR gate. Which specific hardware implementations wrt. chip area, delays etc. are best depends on the particular ASIC manufacturing process. For our models, we count the 4-input OR gate as 3 gates to have a conservative estimate that applies independently of the hardware.\n\n**Limitations:**\n\n> Despite improved training and inference efficiency, experimental results are limited [...] scalability\n\nThanks for the questions. We are indeed actively working on larger classification tasks for the proposed approach and consider this an important research question.\nOur current preliminary designs are internally reaching a performance of 48.06% on ImageNet (top-1).\nWe will continue this direction and will hopefully reach even more generalist models in the future. \n\n> [...] saturation of accuracy [...] improve with increasing model depth. If there's a reason why you stop early, please mention it in the presentation.\n\nThe reason for us to stop rather early was computational training cost.\nNetworks with d=3 are even more expensive to train (~2x compared to d=2).\nWe had let it continue to train the d=3,3,3,3 model after submission and it reached 85.46% (vs. 85.22% in Tab.5.)\nNotably, the deeper models are barely more expensive in inference because the deeper models end up with more residual gates.\n\nInspired by your comment, we extended the MNIST model to a larger and deeper model with d=3, and now achieve 99.24%, which improves the accuracy over all baselines:\n\n| MNIST | Acc. | # Gates |\n|--|--|--|\n| LTNet-XLD3 | 99.24±0.06% | 1.82 M |", "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": "", "extra_scores": {}}, {"review_id": "9b2sXIt8Am", "reviewer": "Reviewer_2J2u", "summary": "In this work the authors propose a convolutional-like architecture along with two novel mechanisms oriented to differentiable logic gate neural networks, making the training and inference of such networks possible in more intense tasks in context of logic gate neural networks. More specifically, the authors augment the current state-of-the-art capabilities of Differentiable Logic Gate Networks by introducing a convolutional architecture and training approach that is based on logic gates and along with the proposed “logical or pooling” and “residual initialization” achieving higher accuracies in various dataset with lower number of gates, reducing significantly the inference time. The authors claim that the proposed method unlocks the capabilities of differentiable logic gate networks providing a comprehensive review on works that target efficient inference, discussing the benefits of adopting the proposed architecture on application that requires efficient and low cost inference.", "questions": "How many additional trainable parameters are introduced during training in contrast to the traditional CNNs and which of them are discarded during the inference?\n\nHow do the authors comment on the observation that the proposed method seems to not generalize equally well to smaller architectures?\n\nHow do the authors conclude on $z_3 = 4.905$?\n\nI would like to stress the consistency of the proposed method in different training runs due to the fact that it is based on the random selection of inputs of the receptive field. Is the robustness of training preserved and what are their experimental observations?", "limitations": "Some technical details in the training process are not clear.\n\nSome empirical decisions made on paper are not well justified neither experimentally nor theoretically.\n\nThe proposed method leads to lower accuracies in smaller models (e.x. LogicTreeNet-S of the table 1)\n\nTaking into account that they promote logic gate choice A, it would be very interesting if the authors report the per layer distribution of logic gates after the training. This could be interesting also in contrast to Gaussian initialization.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well organized providing a comprehensive review on methods that target efficient inference, discussing in depth the benefits of logic gate networks. The technical details, arguments and experimental results provided in the paper regarding the realization of the method in hardware are convincing.\n\nThe authors provide some experimental results in actual hardware demonstrating the effectiveness of the proposed method in terms of efficiency. \n\nThe authors provide interesting ablation studies to support experimentally some of the designing decisions. \n\nThe motivation is solid and easy to understand. Additionally, the contribution is clear, achieving state-of-the-art performance in the context of larger logic neural networks.", "weaknesses": "In many cases the work seems incremental in reference to [1], without, however, overcoming or justifying some theoretical lacks that are spotted in this previous work. More specifically, the random connections that applied in [1] are adopted in this work without well being theoretically justified or proposing an alternative way.   \n\nIn addition to that, I find myself referring occasionally to [1] in order to understand some technical details. For example, the differentiable logic gates are presented only schematically in the paper. \n\nFrom a technical point of view, I find it difficult to conceptualize the computational graph that is built during the training. Do the authors introduce a projection layer, parameterized by vectors z, for each channel of the kernel on the available gates? To this end, is the z vector optimized taking the partial derivative of z on the classification loss? Introducing some details on the optimization process will be useful.\n\nThe random selection of inputs on the receptive fields raises concerns regarding the consistency of the training process, with the paper not providing error bars regarding different training runs. Although the authors discuss the reasons for attaching higher probability to the logic gate choice A (or B), they do not discuss how they conclude on $z_3 = 4.905$. Such empirical decisions potentially hinders the generalization ability of the proposed method.\n\nA proof reading is required. There are some minor typos in the paper and in the appendix. (e.x. Paper-L293 “LGNs differ from the LGNs”, missing reference in L6 of the appendix. \n\n[1] Petersen, Felix, et al. \"Deep differentiable logic gate networks.\" Advances in Neural Information Processing Systems 35 (2022): 2006-2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful and positive feedback, and for appreciating that our \"paper is well organized\", provides a comprehensive review on methods that target efficient inference, our in-depth discussion of the benefits of logic gate networks.\nThank you also for appreciating the technical details regarding the realization of the method in hardware, and expressing that you find the realization convincing.\nFinally, we appreciate that you find our contribution clear, achieving state-of-the-art performance in the context of larger logic neural networks.\n\n**Weaknesses:**\n\n> [...] random connections that applied in [1] are adopted in this work without well being theoretically justified or proposing an alternative way.\n\nWe would like to clarify that, while our connections still have some level of randomness, they are substantially more structured. In particular, the convolutional layers are binary trees, so there is a deterministic structure within the convolutional kernels. Moreover, we restrict the input connections to be from only two channels, which further improved performance. \n\n> In addition to that, I find myself referring occasionally to [1] in order to understand some technical details. For example, the differentiable logic gates are presented only schematically in the paper.\n\nThank you for this remark; we will extend the discussion of differentiable logic gates in the camera-ready version, where we have an additional page.\n\n> [...] computational graph [...] Do the authors introduce a projection layer, parameterized by vectors z, for each channel of the kernel on the available gates? To this end, is the z vector optimized taking the partial derivative of z on the classification loss? Introducing some details on the optimization process will be useful.\n\nYes, the vectors $z$ are optimized by taking the derivative of $z$ on the classification loss. \nThese vectors $z$ are the logits of the probability distributions over choices of logic gates, and can be mapped to those probabilites via softmax (Eq. 1). Accordingly, we do not use a projection layer. We will add clarifications to the camera-ready.\n\n> The random selection of inputs on the receptive fields raises concerns regarding the consistency of the training process, with the paper not providing error bars regarding different training runs.\n> \n> I would like to stress the consistency of the proposed method in different training runs due to the fact that it is based on the random selection of inputs of the receptive field. Is the robustness of training preserved and what are their experimental observations?\n\nThank you for raising this important concern. Yes, consistency between training runs is given, especially for larger models, whereas for the smallest models the stochastic effects can be a bit larger.\nIn the following, we provide means and standard deviations over 10 seeds for our smaller models:\n\n| **CIFAR-10** | Originally reported | With standard deviations |\n|--|--|--|\n| LogicTreeNet-S | 56.71% | 56.55±0.46% |\n| LogicTreeNet-M | 70.65% | 70.72±0.37% |\n\n| **MNIST** | Originally reported | With standard deviations |\n|--|--|--|\n| LogicTreeNet-S    | 98.06% | 98.27±0.25% |\n| LogicTreeNet-L    | 99.11% | 99.10±0.10% |\n| LogicTreeNet-XLD3 | (new)  | 99.24±0.06% |\n\nWe will extend the standard deviations to the larger models (takes very long) as well as Fashion-MNIST (we prioritized the other experiments for now).\n\n> Although the authors discuss the reasons for attaching higher probability to the logic gate choice A (or B), they do not discuss how they conclude on $z_3=4.905$. Such empirical decisions potentially hinders the generalization ability of the proposed method.\n> \n> Question: How do the authors conclude on $z_3=4.905$?\n\n$z_3=4.905$ is the value that leads to 90% probability being assigned to the gate choice 3 ('A').\nWe have clarified this in the revision. Also, we provide a code sketch for an explicit computation below.\n\n```python\n>>> z = torch.zeros(16)\n>>> z[3] = 4.905\n>>> torch.softmax(z, dim=0)\ntensor([0.0067, 0.0067, 0.0067, 0.9000, 0.0067, 0.0067, 0.0067, 0.0067,\n        0.0067, 0.0067, 0.0067, 0.0067, 0.0067, 0.0067, 0.0067, 0.0067])\n```\n\nMoreover, to further address your concern, *we performed an additional ablation study*, where we vary $z_3$ between 1.5 and 7.5, which we provide in the Author Response PDF page with the General Rebuttal (Figure 2).\n\n> Typos\n\nThank you for pointing out the typos; we have corrected them, and will proof read everything for the camera-ready as suggested.  \n\n**Questions:**\n\n> How many additional trainable parameters are introduced during training in contrast to the traditional CNNs and which of them are discarded during the inference?\n\nWe use 16 parameters (vector $z$) for each differentiable logic gate. After training, each gate is discretized to a single parameter, i.e., the choice of logic gate. Finally, during the simplification process, depending on the exact model, 60-80% of the logic gates are removed.\n\n> How do the authors comment on the observation that the proposed method seems to not generalize equally well to smaller architectures?\n> \n> The proposed method leads to lower accuracies in smaller models (e.x. LogicTreeNet-S of the table 1)\n\nFirst, we would like to state that we designed each of our models based on model size \"L\".\nThus, for the smallest model, in order to match the number of logic gates with the baselines, we had to drastically reduce the number of channels down to 40, which was not the optimal model for the small size, but maintained for consistency.\n\n> Taking into account that they promote logic gate choice A, it would be very interesting if the authors report the per layer distribution of logic gates after the training. This could be interesting also in contrast to Gaussian initialization.\n\nThank you for this request. We have added a visualization of the per layer distribution of logic gates after the training to the Author Response PDF page.", "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": "", "extra_scores": {}}, {"review_id": "BhwTcpNS17", "reviewer": "Reviewer_nuqf", "summary": "This paper proposes a novel computational architecture for differentiable logic gate networks (LGNs), a machine learning methodology that aims to learn networks of logic gates for fast, gate-efficient inference on logic gate-based hardware. Specifically, the authors propose extensions to a prior work on differentiable LGNs inspired by the computer vision literature. They propose (i) logic gate tree convolutions which are layers that convolve trees of logic gates with the input, (ii) logical or pooling (inspired by max pooling) layers that compute the disjunction of the receptive field, and (iii) residual initializations that bias the initial distribution over logic gates to be an identity gate of one of the two inputs. The authors also detail various computational techniques to optimize the efficiency of the new architecture in training, simulation and hardware. \n\nExperimental results on computer vision tasks (CIFAR-10, MNIST, Fashion-MNIST) and extensive comparison to SOTA methods demonstrate that the proposed architecture achieves competitive (if not SOTA) accuracy while being either significantly smaller (in terms of gate count) or faster (in terms of inference speed on FPGAs or CPUs). The authors demonstrate through ablation studies that the proposed components and architectural choices are all integral to the achieved performance. Moreover, the authors provide experimental results for insightful studies on the proposed components, such as why logical or pooling doesn’t result in too much network activation, the induced stability of residual initializations, and the effects of gate distribution discretization.", "questions": "- If we take the CIFAR-10 results as an example, another method achieved greater accuracy (91%, Hirtzlin et al.) but requires significantly more gates. What is the current limitation on scaling LogicTreeNets to larger gate counts (beyond 111M)? If, for example, a greater accuracy were desired.\n- Similar to the study conducted by F. Petersen et al., is there any insight to be gleaned from the learnt distribution over logic gates in logic gate tree convolution kernels?\n- Possible typos\n    - Lines 344-345: is a forward slash missing?: “transistor count / chip area”\n    - Line 351: is an M missing?: “55.8M gates”", "limitations": "The authors have adequately addressed limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The proposed methods build upon prior work on differentiable logic gate networks (LGN) and take inspiration from compute vision literature. The contributions are novel and advance the SOTA for fast and efficient inference of machine learning models. The results are of importance to embedded and real-time machine learning applications.\n- Related work is discussed in detail, and experimental results are compared to various prior works.\n- The submission is technically sound, with claims supported by experimental results (see weaknesses for point on statistical significance). The authors demonstrate through ablation studies the utility of each of the proposed architectural components, and discuss tradeoffs, strengths and weaknesses for their techniques.\n- Methods are detailed enough for reproducing the proposed architecture and results.\n- The authors provide substantial insight into methodology choices, making the presentation clear and informative.", "weaknesses": "Lack of statistical significance measures for results. (The main prior work on differentiable LGNs (F. Petersen et al.) provides standard deviations in their appendix). However, the authors provide justification for this within the NeurIPS Paper Checklist.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your extensive and positive feedback.\nWe greatly appreciate that you find our result of importance to embedded and real-time machine learning applications.\nThank you also for your praises wrt. coverage of related work, our technical soundness, our ablation studies, discussions of tradeoffs, detailed descriptions, and the insights into methodology choices that we provide.\n\n**Weaknesses:**\n\n> Lack of statistical significance measures for results. (The main prior work on differentiable LGNs (F. Petersen et al.) provides standard deviations in their appendix). However, the authors provide justification for this within the NeurIPS Paper Checklist.\n\nThank you for pointing this out. In the following, we present standard deviations (over 10 seeds) for our smaller models.\n\n| **CIFAR-10** | Originally reported | With standard deviations |\n|--|--|--|\n| LogicTreeNet-S | 56.71% | 56.55±0.46% |\n| LogicTreeNet-M | 70.65% | 70.72±0.37% |\n\n| **MNIST** | Originally reported | With standard deviations |\n|--|--|--|\n| LogicTreeNet-S    | 98.06% | 98.27±0.25% |\n| LogicTreeNet-L    | 99.11% | 99.10±0.10% |\n\nWe will extend the standard deviations to the larger models (takes very long) as well as Fashion-MNIST (we prioritized the other experiments for now) for the camera-ready.\n\n**Questions:**\n\n> If we take the CIFAR-10 results as an example, another method achieved greater accuracy (91%, Hirtzlin et al.) but requires significantly more gates. What is the current limitation on scaling LogicTreeNets to larger gate counts (beyond 111M)? If, for example, a greater accuracy were desired.\n\nOur primary limitation lies in computational ressources for training, both wrt. VRAM and raw compute. In the future, we hope to train even larger and deeper models\n\n> Similar to the study conducted by F. Petersen et al., is there any insight to be gleaned from the learnt distribution over logic gates in logic gate tree convolution kernels?\n\nYes, we provide a study on the learnt distribution over logic gates in logic gate tree convolution kernels in the Author Response PDF page. We also compare it to the same model but with Gaussian initializations.\nIt actually illustrates an important point: the majority of gates in the network are residual gates (A).\n\n> typos\n\nThank you for spotting these typos. \nWe have fixed them, and will do another proof reading for the camera-ready.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all reviewers for their time and valuable comments, which have helped us improve our paper.
We respond to each of your questions and concerns individually below.
Moreover, we would like to highlight the following additions:

* We are now providing standard deviations for our smaller models, and have started training additional seeds for our larger model, which we will include in the camera-ready.
* Inspired by Reviewer zmod's comments, we have trained a larger and deeper model on MNIST, achieving 99.24±0.06% that requires only 1.82 M gates, achieving the best accuracy for logic gate and binary networks overall.
* In the author response PDF, we provide an illustration of the learned distributions over logic gates, comparing residual and Gaussian initializations.
* Finally, we added an ablation study wrt. $z_3$.

Meta-review: The paper introduces a significant improvement in training Logical Gate Network with application to image data. The work introduces convolutional logical gates networks, pooling and residual connectivity operations, and shows that they can be trained to achieve impressive performance.

All reviewers appreciated the novelty and contribution, provided very enthusiastic reviews and endorsed the paper, after some discussion with the authors. I therefore recommend that this paper should be accepted.
Decision: Accept (oral)