Convolutional Differentiable Logic Gate Networks

Thank you very much for your extensive and positive feedback. We greatly appreciate that you find our result of importance to embedded and real-time machine learning applications. Thank 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.

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.

Thank you for pointing this out. In the following, we present standard deviations (over 10 seeds) for our smaller models.

We 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.

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.

Our 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

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?

Yes, 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. It actually illustrates an important point: the majority of gates in the network are residual gates (A).

typos

Thank you for spotting these typos. We have fixed them, and will do another proof reading for the camera-ready.

I thank the authors for their response and appreciate their effort in addressing my concerns and questions.

With standard deviations being added to the results, and the additional study on learnt distributions over logic gates, I have updated my score of soundness from 3 to 4.

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. Thank you also for appreciating the technical details regarding the realization of the method in hardware, and expressing that you find the realization convincing. Finally, we appreciate that you find our contribution clear, achieving state-of-the-art performance in the context of larger logic neural networks.

Weaknesses:

[...] random connections that applied in [1] are adopted in this work without well being theoretically justified or proposing an alternative way.

We 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.

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.

Thank you for this remark; we will extend the discussion of differentiable logic gates in the camera-ready version, where we have an additional page.

[...] 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.

Yes, the vectors $z$ are optimized by taking the derivative of $z$ on the classification loss. These 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.

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.

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?

Thank 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. In the following, we provide means and standard deviations over 10 seeds for our smaller models:

We will extend the standard deviations to the larger models (takes very long) as well as Fashion-MNIST (we prioritized the other experiments for now).

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.

Question: How do the authors conclude on $z_3=4.905$?

$z_3=4.905$ is the value that leads to 90% probability being assigned to the gate choice 3 ('A'). We have clarified this in the revision. Also, we provide a code sketch for an explicit computation below.

>>> z = torch.zeros(16)
>>> z[3] = 4.905
>>> torch.softmax(z, dim=0)
tensor([0.0067, 0.0067, 0.0067, 0.9000, 0.0067, 0.0067, 0.0067, 0.0067,
        0.0067, 0.0067, 0.0067, 0.0067, 0.0067, 0.0067, 0.0067, 0.0067])

Moreover, 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).

Typos

Thank you for pointing out the typos; we have corrected them, and will proof read everything for the camera-ready as suggested.

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?

We 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.

How do the authors comment on the observation that the proposed method seems to not generalize equally well to smaller architectures?

The proposed method leads to lower accuracies in smaller models (e.x. LogicTreeNet-S of the table 1)

First, we would like to state that we designed each of our models based on model size "L". Thus, 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.

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.

Thank 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.

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. Due to the character limit, we keep our reponses short; please let us know if you would like us to elaborate.

[...] Appendix is vital [...]

Thank 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.

Figure 4 only shows an effect [...]

Fig. 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.

Lines 228-229 [...] line 115. [...]

In line 114-115, we referred to vanilla LGNs, which we will explicitly clarify in the camera-ready. We 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.

In figure 6 [...]

We 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. Blue 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.

SOTA baseline using float weights.

Thanks for the suggestion, we will include SOTA models with float weights into Table 1.

Table 2 lists results for a Xilinx XC7Z020. [...]

For CIFAR-10, as listed in the caption (Tab. 2), the times for M/L/G are based on CPU simulations.

For the MNIST L model, you are correct, based on our initially reported number of gates would not have fit on the FPGA. While 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).

In 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". As Vivado optimizes for 6-LUTs, we could not read out the number of ASIC gates. As 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. Now, it also supports MNIST, and we can report more accurate numbers of ASIC gates for MNIST:

(The actual number of logic gates will still be lower than this number.)

Are any additional resources of the FPGA device being used?

So far, we only utilize Logic Cells and Flip Flops to keep it as close as possible to efficient ASIC designs.

Table 5 [...] "No or pooling". [...]

The 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).

Appendix, Section A.3.3 CPU [...]

The 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.

Thanks for pointing out the typos, we fixed them for the camera-ready.

Questions:

residual initializations

This could indeed be a very interesting direction for future work. We will include a discussion in the revision.

limited to 2-input

Beyond 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.

OR-gates with N >> 2

E.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.

Limitations:

Despite improved training and inference efficiency, experimental results are limited [...] scalability

Thanks for the questions. We are indeed actively working on larger classification tasks for the proposed approach and consider this an important research question. Our current preliminary designs are internally reaching a performance of 48.06% on ImageNet (top-1). We will continue this direction and will hopefully reach even more generalist models in the future.

[...] saturation of accuracy [...] improve with increasing model depth. If there's a reason why you stop early, please mention it in the presentation.

The reason for us to stop rather early was computational training cost. Networks with d=3 are even more expensive to train (~2x compared to d=2). We 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.) Notably, the deeper models are barely more expensive in inference because the deeper models end up with more residual gates.

Inspired 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:

Thank you for responding to our rebuttal, and for asking for the clarifications.

For the final publication, we will publish the full appendix along with the paper, and also include it with the source code.

The rebuttal PDF can be found in the general rebuttal titled “Author Rebuttal by Authors” at the top of this page. It is a single PDF page with 2 figures, which we will include in the final paper / appendix.

For the developed gate-level optimizations, we will include the details in the final appendix.

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. We appreciate that you find our "paper is very well-written". In the following, we address each of your recommendations, questions, and concerns.

Some suggestions on Figure presentation. Figure 1. [...] Figure 2. [...] Figure 3. [...]

Thank you for each of these helpful suggestions. We will incorporate them into Figures 1, 2, and 3, as well as their captions.

Some technical questions need to be better explained. L114-115, why are vanilla LGNs "very computationally expensive to train"? [...]

The 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. In 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. Moreover, 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. Furthermore, the sparsity pattern as introduced by using convolutions is also more favorable for memory accesses.

Beyond 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.

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?

The 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.

The 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.

The 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.

Thus, 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.

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？

To 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. While 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. As FPGAs are effectively slow proxies of ASICs, utilized in hardware design, they are the closest one can get to ASICs without actually manufacturing ASICs.

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.

Indeed, we have not explored CV tasks involving continuous decisions. Continuous 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.