BOLD: Boolean Logic Deep Learning
Authors: Van Minh Nguyen
Cristian Ocampo
Aymen Askri
Louis Leconte
Ba-Hien Tran
Venue: NeurIPS 2024 poster (2024)
Keywords: Boolean neural networks
1-bit training
low precision
Boolean logic
Backpropagation
Primary area: deep_learning_architectures

Abstract: Computational intensiveness of deep learning has motivated low-precision arithmetic designs. However, the current quantized/binarized training approaches are limited by: (1) significant performance loss due to arbitrary approximations of the latent weight gradient through its discretization/binarization function, and (2) training computational intensiveness due to the reliance on full-precision latent weights. 
This paper proposes a novel mathematical principle by introducing the notion of Boolean variation such that neurons made of Boolean weights and/or activations can be trained ---for the first time--- natively in Boolean domain instead of latent-weight gradient descent and real arithmetic. We explore its convergence, conduct extensively experimental benchmarking, and provide consistent complexity evaluation by considering chip architecture, memory hierarchy, dataflow, and arithmetic precision. Our approach achieves baseline full-precision accuracy in ImageNet classification and surpasses state-of-the-art results in semantic segmentation, with notable performance in image super-resolution, and natural language understanding with transformer-based models. Moreover, it significantly reduces energy consumption during both training and inference.

BOLD: Boolean Logic Deep Learning
Van Minh Nguyen'
Cristian Ocampo
Aymen Askri
Louis Leconte
Ba-Hien Tran
Mathematical and Algorithmic Sciences Laboratory, Huawei Paris Research Center, France
vanminh waamiinn.nnuyenhhureee com
Abstract
Computational intensiveness of deep learning has motivated low- cow-precision arith- metic designs. However, the current quantized/binarized training upproaches are limited by: (1) significant performance loss due to arbitrary approximations of the latent weight gradient through its dissretivation/binarizaiii function, and (2) training computational intensiveness due to the reliance full-precision latent weights. This paper proposes a novel mathematical principle by introducing the notion of Boolean variation such that neurons made of Boolean weights and/or activations can be trained -for the first time- natively in Boolean domain instead of latent-weight gradient descent and real arithmetic. We explore its convergence, conduct extensively experimental benchmarking. and provide consistent complex- ity evaluation by considering chip architecture, memory hierarchy, dataflow, and arithmetic precision. Our approach achieves baseline full- mull-precision accuracy in ImageNet classification and surpasses tfateoff-the-ar results in semantic segmen- tation, with notable performance in image super-resolution, and natural language understanding with transformer-bon based models. Moreover, significantly reduces energy consumption during both training and inference.
Introduction
Deep learning [59] has become the de facto solution a wide range of tasks. However, running deep learning models for inference demands significant computational resources, yet it is just the tip of the iceberg. Training deep models even much more intense. The extensive literature on this issue can be summarized into four approaches addressing different sources of complexity. These include: (I) model compression, pruning [38, 20, 109] and network design [94, 44, 96] for large model dimensions; (2) arithmetic approximation [58, 94, 15] for intensive multiplication; (3) quantization
techniques like post-training [106, 34J, quantization-awar training [37, 114, 51]. and quantized
training reduce precision [16, 93]; and (4) hardware design [18, 87, 105, 101, 35, 112] to overcome computing bottleneck by moving computation closer to or in memory.
Aside from hardware and dataflow design, deep learning designs have primarily focused on the number of compute operations (OPS), such as FLOPS or BOPS, as complexity measure [33, 83] rather than the consumed energy memory, and particularly in inference tasks. However, it has been demonstrated that OPS alone are inadequate and even detrimental as a measure of system complexity. Instead, energy consumption provides a more consistent and efficient metric for computing hardware
*Van Minh developed the mathematical principle, designed and implemented the Boolean deep learning framework first in C++ and later in Porch,, validated the concept the MNIST and CIFAR-10 benchmarks. led aspects the project. Cristian evaluated the design using computer vision benchmarks. Aymen analyzed and evaluated the computational complexity. Louis proposed the incorporation plasticity effects in the Boolean optimizer and developed the convergence analysis. Ba Hien contributed to the design and evaluation of Boolean attention mechanisms and enhanced the quality of the paper's presentation.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

[94, 95, 108, 92]. Data movement, especially, dominates energy consumption and is closely linked to system architecture, memory hierarchy, and dataflow [57, 89, 110, 19]. Therefore, efforts aimed solely at reducing OPs are inefficient.
Quantization-wware training, notably binarized neural networks (BNNS) [24, 47], have garnered significant investigation [see, c.g. 83, 34, and references therein]. BNNS typically binarize weights and activations, forming principal computation blocks in binary. They learn binary weights, Wain. through full-precision (FP) latent weights, Wrp. leading to no memory or computation savings during training. For example, binarized linear layer is operated as a W Xbin. where s is the output and a is a FP scaling factor, Whin sign( WTp)), and Xbin = sign(xx (Xtp) J the binarized inputs. The weights are updated via common gradient descent backpropagation, i.e. Wbin = sign( Wep 1) Bw.,) with a learning rate 17, and FP gradient signal gw., Gradient approximation of binarized variables often employs a differentiable proxy of the binarization function sign, commonly the identity proxy. Various approaches treat BNN training as a constrained optimization problem 17, 65], exploring methods to derive binary weights from real-valued latent ones. BNNS commonly suffers notable accuracy drops due to reduced network capacity and the use of proxy FP optimizers [61] instead of operating directly in binary domain [83, 77, 36.. Recent works mitigate this by incorporating multiple FP components in the network, retaining only a few binary dataflows [68]. Thus, while binarization aids in reducing inference complexity, it increases network training complexity and memory usage.
In contrast to binarizing FP models like BNNS, designing native binary models not relying on FP latent weight has been explored. For example, Expectation Backpropagation [91], although operating on full-precision training. was proposed for this purpose. Statistical moysis--nsspired [8, 9] and Belief Propagation [10] algorithms utilize integer latent weights, mainly applied to single perceptrons, with unclear applicability to deep models. Evolutionary algorithms [75, 50] are also an alternative but encounter performance and scalability challenges.
No scalable and efficient algorithm currently exists for natively training deep models in binary. The challenge of significantly reducing the training complexity while maintaining high performance of deep learning models remains open.
Summary:
Contributions. For the aforementioned challenge, we propose a novel framework Boolean Logic Deep Learning (B@LD)- - which relies on Boolean notions to define models and training:
We introduce the notion of variation to the Boolean logic and develop new mathematical framework of function variation (see $ 3.2). One of the noticeable properties is that Boolean variation has the chain rule (see Theorem 321 similar the continuous gradient.
Based on the proposed framework, we develop a novel Boolean backpropagation and optimization method allowing for a deep model to support native Boolean components operated solely with Boolean logic and trained directly in Boolean domain, eliminating the need for gradient descent and FP latent weights (see $ 3.3). This drastically cuts down memory footprint and energy consumption during both training and inference (see, e.g., Fig. 1).
We provide a theoretical analysis of the convergence of our training algorithm (see Theorem 3.17).
We conduct an extensive experimental campaign using modern network architectures such as convolutional neural networks (CNNS) and Transformers [100] on wide range of challenging tasks including image classification, segmentation, super-resolution and natural language understanding (see 4). We rigorously evaluate analytically the complexity of B@LD and BNNs. We demonstrate the superior performance of our method in terms of both accuracy and complexity compared to the state-of-the-art (see, e.g., Table 4, Table 5, Table 7).
2 Are Current Binarized Neural Networks Really Efficient?
Our work is closely related with the line of research on binarized neural networks (BNNs). The concept of BNNS traces back to early efforts to reduce the complexity of deep learning models. BINARYCONNECT [24] is one of the pioneering works that introduced the idea of binarizing FP weights during training, effectively reducing memory footprint and computational cost. Similarly, BINARYNET [47], XNOR-NET [86] extended this approach to binarize both weights and activations, further enhancing the efficiency of neural network inference. However, these early BNNs struggled with maintaining accuracy comparable to their full- full-precision counterparts. To address this issue,

---

Table 1: A summary of SOTA BNNS compared to our method. The notation indicates the nonex- istence of a specific requirement (column) within a given method (row). The colors denoting the methods shall be used consistently throughout the paper.
Bitwidth (Weight-Att)
Specialized Architucture
Mandatory
Mulli-stae
Weight
Training Arithmetic
Method
FP Componenis
Training
Updates
Backprop
OO BINARYNET [47]
1-1
K
X
HP betent-wiights
Gradient
HP
BINARYCONNECT [24]
1-32
X
FP weightweights
Gradient
FP
XNOR-NET [86]
leight-weightss
Gradient
HP
(0) RI-REALNET [60]
beien--wiights
Gradient
HP
( REAL.2HNARY [73]
1-1
FP Intent-weights
Gradient
FP
REACTNET [68]
1-1
HP beight-weights
Gradient
HP
[1]]
Intent-weight
Gradient
HP
BNEXT [36]
1-1
FI' leieht-weights
Gradient EP
(8) POKEBNN [117]
1-1
HP letent-weights
Gradiem
HP
BOLD [Ours]
1-1
X
Native Boolean weights
Logic
Logic
significant advances have been made on BNNS [see, e.g., 83, 85, and references therein], which can be categorized into three main aspects.
! Binarization strategy. The binarization strategy aims to efficiently convert real-valued data such as activations and weights into binary form {-1,1}. The sign function is commonly used for this purpose, sometimes with additional constraints such as clipping bounds in state-of-ther ofttt----ee-rrt (SOTA) methods like POKEBNN [117] or BNEXT [36]. REACTNET [68] introduces rsign as more general alternative to the sign function, addressing potential shifts in the distribution of activations and weights. Another approach [99] explores the use of other two real values instead of strict binary
to enhance the representational capability of BNNS.
2 Optimization and training strategy. BNN optimization relies totally on latent- training, necessitating a differentiable proxy for the backpropagation, Moreover, latent-weight based training methods have store binary and real parameters during training and often requires multiple sequential training stages, where one starts with training a FP model and only later enables binarization [36, 117, 107]. This further increases the training costs. Furthermore, knowledge distillation (KD) has emerged as method to narrow the performance gap by transferring knowledge from a full-precision teacher model to a binary model [68, 107, 117, 60]. While a single teacher model can sufficiently improve the accuracy of the student model, recent advancements like multi-KD with multiple teachers, such as BNEXT [36], have achieved unprecedented performance. However, the KD approach often treats network binarization as an add-on to full-precision models. In addition, this training approach relies on specialized teachers for specific tasks, limiting adaptability on new data. Lastly, [103, 41] proposed some heuristics and improvements to the classic BNN latent-weight based optimizer.
k Architecture design. Architecture design in BNNS commonly utilizes RESNET [69, 68, 11, 36] and MOBILENET [68, 36] layouts. These methodologies often rely on heavily modified basic blocks, including additional shortcuts, automatic channel scaling via squeeze- and-excitation (SE) [117]. block duplication with concatenation in
94
Accuracy (%) (-)
BILD WITH BATCH-NORM
92-
the channel domain [68. 36]. Recent approaches introduce initial modules to enhance input adaptation for binary dataflow [107] or replace convolutions with lighter woint-wise convolutions [66].
BOLD W/O BATCH
90-
KNOR
BINARYNET
Another related line of research involves logic gate networks (LGNs) [79]. In L.NS,, each neuron functions as binary logic gate and, con- sequently, has only two inputs. Unlike traditional neural networks, LGNS do not utilize weights; instead, they are parameterized by se- lecting a specific logic gate for each neuron, which can be learned. Compared to the standard neural networks or our proposed method, LGNS are sparse because each neuron receives only two inputs rather than multiple inputs. Recently, [5] expanded on LGNS by incorporating flexible and differentiable lookup tables. While these advancements show promises, adapting them modern neural network architectures such as CNN Transformers is challenging. Furthermore, these approaches have not been validated on large-scale datasets like IMAGENET on tasks that require high precision, such image segmentation or super-resolution, as demonstrated in our work.
100
Energy Consum. w.t.t FP (%) (+)
Our method against notable BNNS on CIFAR 10 us- ing VGG-SMALL. The energy is analytically evaluated consider- ing hypothetical V100 equiva- lence with native 1-bit support; of $ 4 for details.
Figure 1:
3

---

Summary. Table 1 shows key characteristics of SOTA BNN methods. These methods will be considered in our experiments. Notice that all these techniques indeed have to involve operations on FP latent weights during training, whereas our proposed method works directly on native Boolean weights. In addition, most of BNN methods incorporate FP data and modules as mandatory components. As result, existing BNNs consume much more training energy compared to our B@LD method. An example is shown in Fig. I, where we consider the VGG-SMALL architecture [24, 90] on CIFARIO dataset. In 4 we will consider much larger datasets and networks more challenging tasks. We can see that our method achieves 36x and more than 15x energy reduction compared to the FP baseline and BINARYNET, respectively, while yielding better accuracy than BNNS. Furthermore, BNNS are commonly tied to specialized network architecture and have to employ costly multi- or KD training. Meanwhile, our Boolean framework is completely orthogonal to these BNN methods. is generic and applicable for a wide range of network architectures, and its training procedure purely relies Boolean logic from scratch. Nevertheless, use Boolean components in our proposed framework as is flexible and can be extended to architectures comprised of mix of Boolean and FP modules. This feature further improves the superior performance of our method as can be seen in Fig. I, where we integrate batch normalization (BN) [49] into our Boolean model, and we will demonstrate extensively in our experiments.
stress that it is not obligatory to
Proposed Method
3.1 Neuron Design
Boolean Neuron. For the sake of simplicity, we consider linear layer for presenting the design. Let Wo, (Wi...., Wm). and (.1..... [m be the bias, weights, and inputs of neuron of input size m 2 1. In the core use case of our interest, these variables are all Boolean numbers. Let L be logic gate such AND, OR, XOR, XNOR. The neuron's pre-activation output given follows:
Wi +
where the summation is understood as the counting of TRUES.
Mixed Boolean-Real Neuron. To allow for flexible use and co-existence of this Boolean design with real-valued parts of a deep model, two cases of mixe data are considered including Boolean weights with real-valued inputs, and real-valued weights with Boolean inputs. These two cases can be addressed by the following extension of Boolean logic to mixed-type data. To this end, we first introduce the essential notations and definitions. Specifically, we denote IB = FT, equipped with the Boolean logic. Here, T and indicate TRUE and FALSE, respectively.
Definition 3.1 (Three- logic). Define M def BU (0} with logic connectives defined according those of Boolean logic as follows. First, the negation is: -T F. -F T, and -0)-0- 0. Second, let L be a logic connective, denote by LM and La when it is in MI and in B, respectively, then Lv(a, b) = (a, b) for a,
and Laz , b)
otherwise.
Notation 3.2. Denote by L logic set (e.g., BB or M), IR the real set, Z the set of integers, N numeric set (e.g., R or Z). and ID a certain set of or N.
Definition 3.3. For x E N, its logic value denoted by Flogic is given as Dlogic = T r O, < O, and Flogic 0 x O.
Flogle = F
Definition 3.4. The magnitude of variable denoted (ar), is defined as its usual absolute value if x E N. And for x E L: |x| = 0 if x = 0, and xx| = otherwise.
Definition 3.5 (Mixed-type logic). For logic connective of L and variables a, b, operation L(a,,) b) is defined such that |c| = [a||b] and Clogie = L(Allggee blogie).
Using Definition 3.5, neuron formulation Eq. directly applics to the mixed Boolean-reat neurons.
Forward Activation. It is clear that there can only be one unique family of binary activation functions, which is the threshold function. Let be scalar, which can be fixed or learned, the forward Boolean activation is given as: y = if 2 T and y F otherwise where 8 is the preactivation. The backpropagation throughout this activation will be described in Appendix C.3.

---

3.2 Mathematical Foundation
In this section we describe the mathematical foundation for our method to train Boolean weights directly in the Boolean domain without relying on FP latent weights. Due to the space limitation, essential notions necessary for presenting the main results are presented here while a comprehensive treatment is provided in Appendix A.
Definition 3.6. Order relations '<' ">' in are defined as follows: < T, and T Definition 3.7. For a, B, the variation from a to b, denoted ò(a + b), is defined as: ō(a +
T if a, def O if a, and def if
Throughout the paper, (3, T) denotes the set of all functions from source 3 to image T. Definition 3.8. For f F(BB, DD, Vor T. write 6f -x) ((f(z) f(-x)). The variation of f w.r.t. 2, denoted (z), is defined as: f'(x) xnor(ó(x -f) -
Remark 3.9. The usual notation of continuous derivative f' is intentionally adopted here for Boolean variation for convenience and notation unification. Its underlying meaning, i.e., continuous derivative or Boolean variation, can be understood directly from the context where function is defined.
Intuitively, the variation f w.r.t. x is T if f varies in the same direction with x. Example 3. 10. Let a E IB, f(x) = xor(1, a) for x E IB, the variation of f w.r.t. x can be derived by establishing truth table (see Table in Appendix A. from which we obtain f'(x) a.
For f E N), its derivative, also known in terms of finite differences, has been defined in the literature as fz) = f(x + 1) - fx). see e.g. [52]. With the logic variation as introduced above, can make this definition more generic follows.
Definition 3.11. For f FD), the variation of f w.rt. a E Z is defined f'(x) del of(r x + 1), where 5f is in the sense of the variation defined in D.
Theorem 3.12. The following properties hold:
1. For 1 F(BB --]])(===-(00 =
2. For F(B. (f)
3. For f.g E F(B,N ((() Ve
4, LB 9 D: (go ()( xnor (f())) ff E.
4. For B
5. For TB 4 B, if 1 (2)) < and ( 1), then: (g f) mmr(g'(((z)),ff
The proof is provided in Appendix A.1. These results are extended to the multivariate case in straightforward manner. For instance, for multivariate Boolean functions
follows.
Definition 3.13. For x (II,..., Inn ) B", denote x-4 (I1,.... ... Ii-1, ITa Pit1.... .......,,,,,,............. for n 2 1 and 1 & S n. For f E F(B", B), the (partial) variation of f w.r.t. Ei denoted (x(x) or (x)) is defined as: f(() (x))/(xx def xnor(ō(a; + -I;,, 8 fx +x.)).
Proposition 3.14. Let f E F(B", B),
and E FBB, B). For sism
(go f)( (for(g fx)),, Vx B"
(2)
Example 3.15. From Example 3.10, we have 6xor(1, fz (1) we have: (xnor(x,a)) 4)/6x = a since xnor(z, a) = -xor(x,o)) a). Example 3.16. Apply Theorem 3.12 12-)3) to s from Eq. 1: 5s/5w; = SL(w,, xx)/ /8w; and 8s/52; = (L(,; //x4 Then, for L = xnor example, we have: ds/ōw; n, and 8s/5x; Wt.
for a, E B. Using Theorem 3.12-
3.3 BackPropagation
With the notions introduced 3.2, we can write signals involved in the backpropagation process as shown in Fig. 2. Therein, layer is Boolean layer of consideration. For the sake of presentation
5

---

Boolean Layer
KK, E
Layer
Boas 8x
R
(wi,
B)
1+1
dlane
E or B
Figure Illustration of backpropagation signals with Boolean linear layer. Notice that the subsequent layer can be any FP/Boolean layers activation functions.
simplicity, layer is assumed fully-connected layer, and:
wh.s + LL wi,)), isjsn. i=1
where L is the utilized Boolean logic, denotes sample index in the batch, m and n are the usual layer input and output sizes. Layer is connected to layer + 1 that can be an activation layer, batch normalization, the property of layer 1 + 1. It can be the usual gradient if layer + 1 is real-valued input layer, or a Boolean variation if layer + 1 is Boolean- inglea layer. Given òooss 8x 1+1 layer needs to optimize its Boolean weights and compute signal 8Loss bosss/ for the upstream. Hereafter, we consider I. xnor when showing concrete illustrations of the method.
arithmetic layer, any others. The nature of oLsss/8akk 1+1 depends on
Atomic Variation. First, using Theorem 3.12 and its extension to the multivariate case by Proposi- tion 3.14 in the same manner as shown in Example 3.16, we have: oL(ate. wp,s)
1+1 1 k.j 8w
SL(Tk, wig) coxoor
6xk
Loxxnr wh.
5w
5x k,s
8x
Using the chain rules given by Theorem 3.12-(4 & 5), we have:
8Loss Jw! IK-
xnor(
ôLoss
kxk
1+1 k.j
5w
I. xnor
xnor
ÖLoss 141 kjj
Fb,3).
(5)
ôLoss 6x4,5
ôLoss
ôLoss [+1
1j xnor
xnor
w
(6)
8at,
8xk
Aggregation. Atomic variation d.y. is aggregated over batch dimension l while ge, aggre- gated over output dimension j. Let 1(-) be the indicator function. For E B and variable æ, define: 1 b) if Jogic b and (xr b) otherwise. Atomie variations aggregated as:
ôLoss
dhs = dwhj
Σ
(dh.s = T)ldka Σ
(7)
8Loss
o =
(ghen = Tolok. Σ
Σ 1 (gk. = F) sk.zol-
(8)
6ar..
Boolean Optimizer. With of.y obtained in Eq. 7, the rule for optimizing wh, subjected to making the loss decreased simply given according its definition
w w if xnor (gi.,> wh.)) T.
Eq. is the core optimization logic based on which more sophisticated forms of optimizer can be developed in the same manner as different methods such as Adam, Adaptive Adam, etc. have been developed from the basic gradient descent principle. For instance, the following is an optimizer that J.t accumulates gf over training iterations. Denote by 4. the optimization signal at iteration f, and by 1.0 miy its accumulator with m.j := 0 and:
l++1 m,j
3a'mm L.t. + + gi
1.t+1
(10)

---

where 'f' is an accumulation factor that can be tuned as hyper parameter, and 3 is an auto- regularizing factor that expresses the system's 's state time t. Its usage linked to brain plasticity [31] and Hebbian theory [40] forcing weights to adapt to their neighhorhood. For the chosen weight's neighborhood, for instance, neuron, layer, or network level, /8 given as:
B Number of unchanged weights at L
(11)
Total number of weights
In the experiments presented later, 3 is set to per-layer basis. Finally, the learning process as described in Algorithm 1. We encourage the readers to check the detailed implementations, practical considerations, and example codes of our proposed method, available in Appendix B and Appendix C.
Convergence Analysis. The following result de- scribes how the iterative logic optimization based on Eq. 9 minimizes predefined loss f. under the standard non-convex assumption. The tech- nical assumptions and the proof are given in Ap- pendix A.2.
Algorithm 1: Illustration with a FC layer.
Input Learning rate 13. nb iterations T; Initialize: m 1.0 0; 80 1:
for f .,..., do
/* 1. Forward +/
Theorem 3.17. Under the specified assumptions, Boolean optimization logic converges at:
Compute x 1+1 following Eq. 3;
/* 2. Backward +/
Receive _Lees from downstream layer: 5.1T1.7
A" Tn
Σ t=0
E
|
+B' +ra- of (wx)) &
/* 2.1 Backpropagation +/
T
Compute and backpropagate g¹ of Eq. 8; /* 2.2 Weight update process */ Nun == 0, Nunctanged := 0;
(12)
where A ((((o)))))) - f.) with f. being uniform lower bound assumed exists, B 2o C 4I2²2 (1-7zz in which is the assumed Lipschitz constant, and r== dx/2.
5
foreach w',, do
Compute g.j following Eq. Update
mi m.t+1 = ( lit + + 1
1,+1,
The bound in Theorem 3.17 contains four terms. The first is typical for a general non-convex target and expresses how initialization affects the con- 10
Nu f- N + 1;
xxnormm!
1.t+1
w = T then
vergence. The second and third terms depend on the fluctuation of the minibatch gradients. There is an "error bound" of 2dd independent T' This error bound is the cost of using discrete weights as part of the optimization algorithm. Previous work with quantized models also includes such error bounds [61, 62].
11
wi Le+1 = 0;
- /+ invert */
12 else
mij
" 11-11 N Nuschanged t Nunchunged + 1;
w
/ keep */
15
16
Update rf
ge+1 Nunchanged/ Nux
Regularization. Exploding and vanishing gradients are two well-known issues when it comes to train deep neural networks. During Boolcan Logic training, our preliminary experiments indicated that the backpropagation signal also experiences similar phenomenon, resulting in unstable training. Our idea is to scale the backpropagation signals Boolean structure, assumptions on the involved signals can be made so that the scaling factor can be analytically derived in closed-form without need of learning or batch statistics computation. Precisely, through linear layers of output size m, the backpropagation signal is scaled with v2/m, and for convolutional layers of output size Caus, stride v and kernel sizes liz, by. the backpropagation signal is scaled with 2 /2//omkkk, if maxpooling is applied, or /20/cunk.hy otherwise. The full detail is presented in Appendix C.
match their variance. Thanks to the
Experiments
Our B@LD method achieves extreme compression by using both Boolean activations and weights. We rigorously evaluate its performance on challenging precision-demanding tasks, including image classification on CIFAR10 [55] and IMAGENET [56], as well as super-resolution on five popular datasets. Furthermore, recognizing the necessity of deploying efficient lightweight models for edge computing, we delve into three fine-tuning scenarios, showcasing the adaptability of our approach. Specifically, we investigate fine-tuning Boolean models for image classification on CIFAR 10 and CIFAR 100 using VGG-SMALL. For segmentation tasks, we study DEEPLABY3 [17] fine-tuned on
7

---

CITYSCAPES [23] and PASCAL VOC 2012 [29] datasets. The backbone for such a model is our Boolean RESNETIS 8 [39] network trained from scratch on IMAGENET. Finally, we consider an evaluation in the domain of natural language understanding, fine-tuning BERT [26], a transformer- based [100] language model, on the GLUU benchmark [102].
Experimental Setup. To construct our BELD models, we introduce Boolean weights and activa- tions and substitute full- full-precision (FP) arithmetic layers with Boolean equivalents. Throughout all benchmarks, we maintain the general network design of the chosen FP baseline. while excluding -e-specific components like ReLU, PReLU activations, or batch normalization (BN) [49], unless spec- ified otherwise. Consistent with the common setup in existing literature [see, e.g., 86, 21, 1 11], only the first and last layers remain in FP and are optimized using an Adam optimizer [54]. Comprehensive experiment details for reproducibility are provided in Appendix D.
Complexity Evaluation. has been demonstrated that relying solely on FLOPS and BOPS for complexity assessment is inadequate [94, 95, 108, 92]. In fact, these metrics fail to capture the actual load caused by propagating FP data through the BNNs. Instead, energy consumption serves as a crucial indicator of efficiency. Given the absence of native Boolean accelerators, we estimate analytically energy consumption by analyzing the arithmetic operations, data movements within storage/processingg units, and the energy cost of each operation. This approach is implemented for the Nvidia GPU (Tesla V100) and Ascend [63] architectures. Further details are available in Appendix E.
4.1 Image Classification
Our BeLD method is tested on two network configurations small & compuct and large & deep. In the former scenario, we utilize the VGG-SMALL [90] bascline trained on CIFAR Evaluation of our
Boolean architecture is conducted both without BN [24], and with BN including activation from [69]. These designs achieve 90.29 19.%% (estimated over six repetitions) and 92.37:t0.014 % (estimated over five repetitions) accuracy, respectively (see Table 2). Notably, without BN, our results align closely with BINARYCONNECT [24], which employs 32-bit activations during both inference and training. Furthermore, BN brings the accuracy within 1 point of the FP baseline. Additional results are provided in the supplementary material for VGG-SMALL models ending with FC layer.
Our method requires much less energy than the FP baseline. In particular, it consumes less than 5% of energy for our designs with and without BN respectively. These results highlight the remarkable energy efficiency of our B&LD method in both inference and training, surpassing latent-weight based training methods [24, 86, 48] reliant on FP weights. Notably, despite slight increase energy consumption, utilizing BN yields superior accuracy. Even with BN, our approach maintains superior efficiency compared to alternative methods, further emphasizing the flexibility of our approach in training networks with a blend of Boolean and FP components.
In the large & deep case, we consider the RESNET18 18 baseline trained from scratch on IMAGENET. We compare our approach to methods employing the same baseline, larger architectures, and additional training strategies such as KD with a RESNET34 teacher or FP-based shortcuts [69]. Our method consistently achieves the highest accuracy across all categories, ranging from the standard model (51.8% accuracy) to larger configurations (70.0% accuracy), as shown in Table 5. Additionally, our B@LD method exhibits the smallest energy consumption in most categories, with a remarkable 24. 45% for our large architecture with and without KD. Notably, our method outperforms the FP baseline when using 4x filter enlargement (base 256), providing significant energy reduction (24.45%). Furthermore, it surpasses the SOTA POKEBNN [117], utilizing RESNET50 as teacher.
For completeness, we also implemented neural gradient quantization, utilizing INT4 quantization with a logarithmic round-to-nearest approach [21] and statistics-aware weight binning [22]. Our experiments on IMAGENET confirm that 4-bit quantization is sufficient to achieve standard FP performances, reaching 67.53% accuracy in 100 epochs (further details provided in Appendix D.1.4).
4.2 Image Super-resolution
Next, we evaluate the efficacy of our BOLD method to synthesize data. We use a compact EDSR network [64] as our baseline, referred to as SMALL EDSR, comprising eight residual blocks. Our
2VGG- SIGG-SMALLAAE with the last layer mapping to 100 classes.
8

---

Table 2: Results with VGG-SMALL on CI 'Cons.' is the energy consumption w.r.t. the FP baseline, evaluated on 1 training iteration.
Table Results with RESNET 18 baseline on IMAGENET. 'Base' is the mapping dimension of the first layer. Energy consumption is evaluated on I training iteration. 'Cons.' is the energy consumption w.r.t. the FP baseline.
Method
W/A
Acc(%)
(ons(())
Ascend
Testa V100
Cons. (%)
(8) CINARYCONNECTT [24]
Pull puecisceciiinn [114]
32/32
1/32
10
38.59
100.00
48
Training Modallty
Metheel
Arc.
(%)
Cone. 1%)
Asccnd
Testa V100
Cons. (%%
(0) XNOR NET [86]
1/1
89.83
34.21
45.68
09 HINARYSELT [47]
1/1
89.85
32.60
43.61
PP RASSE INR
RISNATIN [70]
09.7
100.00
100.00
(N) BSL.D wio BN [Oues]
1X1
90.29
3.64
2.78
08 BINARYSET [47]
(8) nen.D with RN [Ours]
1/1
92:37
4.87
3,71
ANDR-NNIT [60]
51.2
8.77
FC SHORFCLY
09 HEALMES: [09]
56.4
46.00
32.99
Table 3: Super-resolution results measured in
LARGE
MODOLS
08 81 REALMET:34 54 (o0)
B1 REALNET:
62.2
61.5
$0.00
58.24
PSNR (dB) (1), using the EDSR baseline [64].
24.45
Task
SE714
[113]
Bsp100
[46]
URSAN100
(72)
(1.91
DIv2K
KD:
KERNET34
9M WRAI ZRINARY [73)
0M REACTSET RESNETLS (68)
09 KNENT-18 [88]
65.4
65.5
68.4
45.43
45.48
77.89
FULL BESR (FP)
38.11
53.92
32.32
32.05
35.00
BOILD BN (Boc 192
65.9
25.91
16.91
x2 SMALL EDSE (FF)
38.01
53.63
32.19
31.60
34.67
(0) BOLD [Ours]
37.42
33.00
31.75
30.26
33.82
KD: RESNET5O
(80 POKIDNN- RESNETIR (117]
65.2
PUTT FIORR (FP)
34.65
40.53
20:25
31.36
x3 SMALL EDSR (197
34.37
50.24
20.10
30.93
DOLD [Ours]
33.56
29.70
26.72
30.22
Table 6: Results with VGG-SMALL baseline fine-
FULL EDSK 128)
tuned on CIFAR 10 and CIFAR 100. 'FT' means
SMALL
32.17
28.53
26.14
BOLD (Ours]
31:25
27.97
27.24
25.12
28.36
Fine-Tuning"
Ref.
Method
Model
Train.F1
Bitwidth W/AG
Acc. (%)
Table 4: Image segmentation results.
Init.
Dalaset
Datuset
Model
mloU (1)
FP BASELINE
EP BASELINE
Random
Random
CIFAR100
CIFARIO
32/32/32
32/32/32
95.27
77.27
EP BASELINE
70.7
N00 BELD
Random
CIFAR1O
1/1/16
90.29
CITYSCAPES
RINARY DAD-KET [30]
58.1
(0) BELDD
Randon
CIFAR100
1/1/16
[Ours)
67.4
FP BASRLINES
FIFAR100
32/32/33
76.74
NO0 BELDD
CIFAR100
1/1/16
68.37
PASCAL VOC 2012
(8) BELD [Ours]
FP BASELINE
72.1
67,3
(40 BELD
BASELINE
CIPAR1O
CIFARIO
32/32/32
1/1/16
92,09
95.77
BOLD model employs Boolean residual blocks without BN. Results, presented in Table 3, based on the official implementation and benchmark', reveal remarkable similarity to the FP reference at each scale. Particularly noteworthy are the prominent results achieved SET 4 and BSD100 datasets. Our method consistently delivers high PSNR for high-resolution images, such as DIV2K, and even higher for low-resolution ones, like SET5. However, akin to EDSR, our approach exhibits a moderate performance reduction at scale 4x. These findings highlight the capability of our method to perform adequately on -ddandinn tasks while exhibiting considcrable robustness across image resolutions.
4.3 Adaptability on New Data
Image classification fine-tuning. We aim to assess the adaptability of our method to similar problems but different datasets, a common scenario for edge inference tasks. We employ the VGG- SMALL architecture without BN under two training configurations. Firstly, the BOLD model is trained from scratch with random initialization fine-tune the trained networks on CIFAR 100 (REF. F) and CIFAR 10 (REF. H), respectively. Notably, in Table 6, fine-tuning our trained model on CIFAR (REF. F) results in model almost identical to the model trained entirely from scratch (REF. D). Additionally, a noteworthy result is observed with our model (RBF. H), which achieves higher accuracy than the model trained from scratch (REF. C).
CIFAR10 (REF. C) and CIFAR 100 (REF. D). Secondly, we
Image segmentation fine-tuning. Next, we expand the scope of the aforementioned fine-tuning experiment to encompass a larger network and a different task. The baseline the DEEPLABV3 network for semantic segmentation. It consists of our Boolean RESNET18 8 (without BN) as the backbone, followed by the Boolean atrous pyramid pooling (ASPP) module [17]. We refrain from utilizing auxiliary loss or knowledge distillation techniques, as these methods introduce additional computational burdens, which are contrary to our objective of efficient on-device training. As demonstrated in Table 4, our method achieves notable 67. .4. mloU on CITYSCAPES (see Fig. 3 for prediction examples). This result surpasses the SOTA, BINARY DAD-NET [30], and approaches
"https://githur wwt.:ooo//aaaaaeee
9

---

the performance of the FP baseline. Likewise, on PASCAL VOC 2012, our methodology nears the performance the baseline. Importantly, these improvements are attained without the intermediate use of FP parameters during training, highlighting the efficiency and effectiveness of our approach. This shows that our method not only preserves the inherent lightweight advantages highly quantized neural networks but also significantly enhances performance in complex segmentation tasks.
BERT fine-tuning for NLU tasks. Finally, we consider fine-tuning BERT [26], a transformer- based model [100], on the GLUE benchmark [102]. We follow the standard experimental protocol in [26, 6, 82]. Our model and the chosen baselines are employed with 1-bit bitwidth for both weights and activations. Our Boolcan BERT model is inspired by BIT [67] for binarizing activations and incorporating KDD during training, where the FP teacher guides the student a layer-wise manner. We follow the experimental setup of BIT, including using the same method for binarizing activations and backpropagation for softmax and attention in the BERT model. As shown in Table 7, all methods suffer from performance drop compared to the FP model extreme binarization of transformer- -based model is not trivial. Nevertheless, our method yields results comparable to BIT [67], the SOTA method on this task, outperforming BINARYBERT [6] and BIBERT [82] on average. This is remarkable as method natively uses Boolean weights during the training, whereas the baselines heavily rely on FP latent weights. These findings indicate potential for energy-efficient large language models (LLMS) using our method for both training and inference.
Reference Image
Ground Truth
Table 7: BERT models results. SSorce code [67].
GLUE Benchmark (Accuracy, f)
Method
QQP QNLI SST-2 COLA SST-B
Avg.
Full-precision
BAFLD (Ours)
FP BERT
84.9
91.4
92.1
93.2
59.7
90.1
86.3
72.2 83.9
BINARYBERT
35.6
66.2
51.5
53.2
0.0
6.1
68.3
52.7 41.0
RIBERT
66.1
84.8
72.6
88.7
25,4
33.6
72.5
57.4 63.2
77.1
82.9
85.7
87.7
25,1
71.1
79.7
58.8 71.0
BIT (Reprod.)
76.8
87.2
85.6
87.5
24.1
70,5
78.9
58.8 69.7
75.6
85.9
84.1
88.7
27.1
68.7
78.4
58.8
70.9
Figure 3: An example of CITYSCAPES.
Conclusions
We introduced the notion of Boolean variation and developed first framework of its calculus. This novel mathematical principle enabled the development of Boolean logic backpropagation and Boolean optimization replacing gradient backpropagation and gradient descent for binary deep learning. Deep models can be built with native Boolean weights and/or Boolean activations, and trained in Boolean natively by this principled exact Boolean optimization. That brings a key advantage to the existing popular quantized/binarizz
training approach that suffers from critical bottlenecks - (i) performance loss due to an arbitrary approximation of the latent weight gradient through its discretizationnbiiarizatii function, (ii) training computational intensiveness due to full-precision latent weights We have extensively explored
capabilities, highlighting: (i) both training and inference are now possible in binary; (iv) deep training complexity can be drastically reduced to unprecedented levels. (iā) Boolean models can handle finer tasks beyond classification, contrary to common belief; (ii) in some applications, suitablely enlarging Boolean model can recover FP performance while still gaining significant complexity reduction.
Limitations. Due to current computing accelerators, such as GPUs, primarily designed for real arithmetic, our method could not be assessed on native Boolean accelerator. Nevertheless, its considerable potential may inspire the development of new logic circuits and architectures utilizing Boolean logic processing. It also remains as an open question the approximation capacity of Boolean neural networks. A mathematical result equivent to the existing universal approximation theory of real-valued neural networks would provide a solid guarantee.
10

---

Acknowledgments
This work has been made possible through the invaluable support of various departments and colleagues within Huawei. Van Minh Nguyen would like extend his sincere thanks to everyone involved, with special uppreciation to Jean-Claud Belfiore and the former students who have participated in this project over the years: Valentin Abadie, Tom Huix, Tianyu Li, and Youssef Chaabouni.
References
[1] E. Agustsson and R. Timofte. NTIRE 2017 Challenge on Single Image Resolutesoo Dataset and Study. In The IEEE Conference Computer Vision and Pottern Recognition (CVPR) Workshops, July 2017.
[2] T. Ajanthan, P. K. Dokania, R. Hartley, and P. H. Torr. Proximal Mean-field for Neural Network Quantization. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV). October 2019.
[3] T. Ajanthan, K. Gupta, P. Torr. R. Hartley, and P. Dokania. Mirror Descent View for Neural Network Quantization. In Proceedings The 24th International Conference on Artificial Intelligence and Statisticx, volume 130, pages 2809-2817, PMLR, 13-15 Apr 2021.
[4] D. Alistarh, D. Grubie, J. Li, R. Tomioka, and M. Vojnovie. QSGD: Communication-Effiicin SGD via Gradient Quantization and Encoding. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[5] A. T. L. Bacellar, Z. Susskind, M. Breternitz Jr. E. John, L. K. John, P. M. V. Lima, and F. M. França. Differentiable weightless neural networks. In R. Salakhutdinov, Z. Kolter, Heller, Weller, N. Oliver, J. Scarlett, and Berkenkamp, editors, Proceedings of the 4 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 2277-22979 PMLR, 21-27 Jul 2024.
[6] H. Bai, W. Zhang, L. Hou, L. Shang. J. Jin, X. Jiang, Q. Liu, M. Lyu, and I. King. BinaryBERT: Pushing the Limit of BERT Quantization. In C. Zong, F. Xia, W. Li, and R. Navigli, editors. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1thh International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4334-4348. Association for Computational Linguistics, 2021.
[7] Y. Bai. Y.-X. Wang. and E. Liberty. ProxQuant: Quantized Neural Networks via Proximal Operators. In International Conference on Learning Representations, 2018.
[8] C. Baldassi. Generalization Learning in Perceptron with Binary Synapses. Journal of Statistical Physics, 136(5):902-916, Sep 2009.
[9] C. Baldassi and A. Braunstein. A Max-Sum Algorithm for Training Discrete Neural Networks, Journal of Statistical Mechanics: Theory and Experiment, P08508), 2015.
[10] C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina. Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses. Physical Review Letters, 115(12): 128101, 2015.
[11] J. Bethge, C. Bartz, H. Yang, Y. Chen, and C. Meinel. MeliusNet: An Improved Network Architecture for Binary Neural Networks. In Proceedings of the IEFF/CVF Winter Conference on Applications of Computer Vision (WACV), pages 1439-1448, January 2021.
[12] M. Bevilacqua, A. Roumy, C. Guillemot, and M. line Alberi Morel. Low Cow-Cooplyxity Single-Image based Nonnegative Neighbor Embedding, In Proceedings of the British Machine Vision Conference, pages 1-5.1-135.10. BMVA Press, 2012.
[13] S. Bianco, R. Cadene, L. Celona, and P. Napoletano. Benchmark Analysis of Representative Deep Neural Network Architectures. IEEE Access, 6:64270-64277, 2018.
[14] A. Canziani, A. Paszke, and E. Culurciello. An Analysis of Deep Neural Network Models for Practical 2016.
Applications. arXiv preprint
[15] H. Chen, Y. Wang. C. Xu, B. Shi, C. Xu, Q. Tian, and C. Xu. AdderNet: Do We Really Need Multiplications in Deep Learning? In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.

---

[16] J. Chen, Y. Gai, Z. Yao, M. W. Mahoney, and J. E. Gonzalez. A Statistical Framework for Low-bitwidee Training of Deep Neural Networks. In Advances in Neural Information Processing Systems, volume 33, pages 883-894, Curran Associates, Inc., 2020.
[17] L.-C.. Chen, G. Papandreou, F. Schroff, and H. Adam. Rethinking Atrous Convolution for Semantic Image Segmentation. arXiv preprint arXiv: (0o::00006.888888 2017.
[18] Y.-H. Chen, Emer, and V. Sze. Byeriss: Spatial Architecture for Energy--Efficiee Dataflow for Convolutional Neural Networks. SIGARCH Computer Architecture News, 44(3):367-333 1199, jun 2016.
[19] Y.-H. Chen, T. Krishna, J. S. Emer, and V. Sze. Eyeriss: An Energy-efficient Reconfigurable Accelerator for Deep Convolutional Neural Networks. IEEF Journal of Solid-stote Circuits, 52(1):127-133, 2016.
[20] Y. Cheng, D. Wang, P. Zhou, and T. Zhang. Model Compression and Acceleration for Deep Neural Networks: The Principles, Progress, and Challenges. IEEE Signal Processing Magazine, 35(1):126 136, 2018.
[21] B. Chmiel, R. Banner, E. Hoffer, H. B. Yaacov, and D. Soudry. Logarithmic Unbiased Quantizaaion: Simple 4-bit Training in Deep Learning. arXiv:21 10769, 2021.
[22] J. Choi, P. I.-J Chuang, Z. Wang, S. Venkataramani, V. Srinivasan, and K. Gopalakrishnan. Bridging the Accuracy Gap for 2- 2-Bit Quantized Neural Networks (QNN). arXiv preprint arXiv: 06964, 2018.
[23] M. Cordts, M. Omran, S. Ramos, T. Rehfeld, M. Enzweiler, R. Benenson, U. Franke, S. Roth, and Schicle. The Cityscapes Dataset for Semantic Urban Scene Understanding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
[24] M. Courbariaux, Y. Bengio, and J.-P. David, BinaryConnect: Training Deep Neural Networks with Binary Weights during Propagations. In Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015.
[25] C. De Sa, M. Leszczynski, J. Zhang, A. Marzoev, C. R. Aberger, K. Olukotun, and C. Ré. High-Accuracy Low-Precision Training. arXiv preprint arXiv: 03383, 2018
[26] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of Deep Bidirectional Transform- ers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (L.ng and Short Papers), pages 4171 1171-4186. Association for Computational Linguistics, 2019.
[27] R. Ding, T. Chin, Z. Liu, and D. Marculescu. Regularizing Activation Distribution for Training Binarized Deep Networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
[28] Z. Du, R. Fasthuber, T. Chen, P. Ienne, L. Li, T. Luo, X. Feng. Y. Chen, and O. Temam. ShiDianNao: Shifting Vision Processing Closer the Sensor. In Proceedings the 42nd Annual International Symposium on Computer Architecture, pages 92-104, 2015.
[29] M. Everingham, L. Van Gool, K. 1. Williams, J. Winn, and Zisserman. PASCAI. Visual Object Classes Challenge 2012 (VOC2012) Results. network wwtpl//ggwe/////oo////////aeeeee
The http:/www.pascul
htmll
[30] A. Frickenstein, M.-R. Vemparala, J. Mayr, N.-S. Nagaraja, C. Unger, F. Tombari, and W. Stechele. Binary DAD-Net: Binarized Driveable Area Detection Network for Autonomous Driving. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 2295 2301. IEEÉ, 2020.
[31] E. Fuchs, G. Flügge, et al. Adult Neuroplasticity: More than 40 Years of Research. Neural plasticity, 2014, 2014.
[32] Y. Gao, Y. Liu, H. Zhang, Z. Li, Y. Zhu, H. Lin, and M. Yang. Estimating GPU Memory Consumption of Deep Learning Models. In Proceedings of the 28th ACM Joint Meeting on European Sofwwree Engineering Conference and Symposium on the Foundations of Software Engineering, pages 1342 1352, 2020.
[33] E. Gartin, C. F. Rodrigues, G. Rilcy, and H. Grahn. Estimation Energy Consumption in Machine Learning. Journal of Parallel and Distributed Computing, 134:75-88, 2019.
[34] A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer. A Survey of Quantization Methods for Efficient Neural Network Inference. In Low-Power Computer Vision, pages 291-326. Chapman and 2022
12

---

[35] C. Grimm and N. Verma. Neural Network Training on In- Hn--Memory-Computiee Hardware With Radix-4 Gradients. IEEE Transactions Circuits and Systems Regular Pupers I, 69(10))405-44688, 2022.
[36] N. Guo, J. Bethge, C. Meinel, and H. Yang. Join the High Accuracy Club on ImageNet with A Binary Neural Network Ticket. arXiv preprint (tx:::2221111992 2022.
[37] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan. Deep Learning with Limited Numerical Precision. In Proceedings of the 32nd International Conference Machine Learning, volume 37, pages 1737-1746, Lille, France, 07-09 Jul 2015. PMLR.
[38] S. Han, H. Mao, and W. J. Dally. Deep Compression: Compressing Deep Neural Networks with Pruning. Trained Quantization and Huffman Coding, In International Conference on Learning Representations. 2015.
[39] K. He, X. Zhang. S. Ren, and J. Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). June 2016.
[40] D. O. Hebb. The Organization of Behavior: A Neuropsychologica Theory. Psychology press, 2005.
[41] K. Helwegen, Widdicombe, I.. Geiger, 7. Liu, K.-T. Cheng, and R. Nusselder. Latent Weights Do Not Exist: Rethinking Binarized Neural Network Optimization. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[42] M. Horowitz. 1.1 Computing's 's Energy Problem (and What We Can Do about It). 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), pages 10-14, 2014.
[43] L. Hou, Q. Yao, and J. T. Kwok. Loss-aware Binarization Deep Networks, In International Conference on Learning Representations, 2016.
[44] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam. MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications. arXiv preprint arXiv: 044666, 2017.
[45] L. Hoyer, D. Dai, and L. Van Gool. DAFomer: Improving Network Architectures and Training Strategies for Domain-Adaptive Semantic Segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9924-9935, 2022.
[46] J.-B. Huang, A. Singh, and N. Ahuja. Single Image Super-Resolution from Transformed seff-xxepplars Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2015.
[47] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio. Binarized Neural Networks. In Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[48] I. Hubara, M. Courbariaux, D. Soudry, R. EI- Yaniv, and Y. Bengio. Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations. The Journal of Machine Learning Research, 18( (886666696,888 2017.
[49] S. Toffe and C. Szegedy. Batch Normalization: Accelerating Deep Network Training hy Reducing Internal Covariate Shift. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 448 448-456, Lille, France, 07-09 Jul 2015. PMLR.
[50] Ito and T. Saito. Dynamic Binary Neural Networks and Evolutionary Learning. The 2010 International Joint Conference on Neural Networks, pages 1-5. IEEF, 2010.
[51] Q. Jin, J. Ren, R. Zhuang, S. Hanumante, Z. Li, Z. Chen, Y. Wang, K. Yang, and S. Tulyakov. F8Net: Fixed-Point 8-bit Only Multiplication for Network Quantization. In International Conference on Learning Representations, 2021.
[52] C. Jordan. Calculus of Finite Differences. Chelsea Publishing Company, New York, 2nd edition, 1950.
[53] P. Karimireddy, Q Rebjock, S. Stich, and M. Jaggi. Error Feedback Fixes SignSGD and other Gradient Compression Schemes. In Proceedings of the 36th International Conference on Machine Learning. volume 97, pages 3252-3261. PMLR, 09-15 Jun 2019.
[54] D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations, 2015.
[55] A. Krizhevsky and G. Hinton. Learning Multiple Layers of Features from Tiny Images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
13

---

[56] A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet Classification with Deep Convolutional Neural Networks. In Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[57] H. Kwon, P. Chatarasi, M. Pellauer, A. Parashar, V. Sarkar, and T. Krishna. Understanding Reuse, Performance, and Hardware Cost of DNN Dataflow: Data-centric Approach. In Proceedings of the 52nd Annual IEEF/ACM International Symposium on Microarciitecture, pages 754-768, 2019.
[58] I. Lavi, S. Avidan, Y. Singer, and Y. Hcl-Or. Proximity Preserving Binary Code Using Signed Graph-Cut. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4535 4535-4544, April 2020.
[59] Y. LeCun, Y. Bengio, and G. Hinton, Deep Learning. Nature, 521 2015.
[60] C. Lee, H. Kim, E. Park, and J.-J Kim. INSTA-BNI BNN: Binary Neural Network with INSTAnce-aware Threshold. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 17325 17334, October 2023.
[61] H. Li, S. De, Z. Xu, C. Studer, H. Samet, and T. Goldstein. Training Quantized Nets: A Deeper Understanding. Advances Neural Information Processing Systems, volume 30, Curran Associates. Inc., 2017.
[62] Z. Li and C. M. De Sa. Dimension- Free Bounds for Low-Precision Training. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[63] H. Liao, J. Tu, J. Xia, H. Liu, X. Zhou, H. Yuan, and Y. Hu. Ascend: a Scalable and Unified Architecture for Ubiquitous Deep Neural Network Computing: Industry Track Puper. In 2021 IEEE International Symposium
Pirfo-Performacce Computer Architecture (HPCA). pages 789-801, 2021.
[64] B. Lim, S. Son, H. Kim, S. Nah, and K. Mu Lee. Enhanced Deep Residual Networks for Single Image Super-Resolution. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, 2017.
[65] M. Lin, R. Ji, Z. Xu, B. Zhang, Y. Wang, Y. Wu, F. Huang, and C.-W. Lin. Rotated Binary Neural Network. In Advances in Neural Information Processing Systems, volume 33, pages 1474-7485. Curran Associates, Inc., 2020.
[66] C. Liu, W. Ding, P. Chen, B. Zhuang, Y. Wang, Y. Zhao, B. Zhang, and Y. Han. RB-Net: Training Highly Accurate and Efficient Binary Neural Networks with Reshaped Point-wise Convolution and Balanced activation. IEEE Transactions Circuits and Systems for Video Technology, 32(9))6414-6422 2022.
[67] Z. Liu, B. Oguz, A. Pappu. L. Xiao, S. Yih, M. Li, R. Krishnamoorthi, and Y. Mehdad. BIT: Robustly Binarized Multi-distiledd Transformer. In Advances in Neural Information Processing Systems, volume 35, pages 14303-14 1730--1116666 14316. Curran Associates, Inc., 2022.
[68] Liu, Z. Shen, M. Savvides, and K.-T. Cheng. ReActNet: Towards Precise Binary Neural Network with Generalized Activation Functions. In Proceedings of the European Conference on Computer Vision (ECCV), August 2020.
[69] 7. Liu, B. Wu, W. Luo, X. Yang, W. Liu, and K.-T. Cheng. Bi-Real Net: Enhancing the Performance of 1-bit CNNs with Improved Representational Capability and Advanced Training Algorithm. In Proceedings the European Conference on Computer Vision (ECCV), September 2018.
[70] J. Long, E. Shelhamer, and T. Darrell. Fully Convolutional Networks for Semantic Segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
[71] I. Loshchilov and F. Hutter. Decoupled Weight Decay Regularization. In International Conference on Learning Representations, 2017.
[72] D. Martin, C. Fowlkes, Tal, and Malik. A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), July 2001.
[73] B. Martinez, J. Yang, A. Bulat, and G. Tzimiropoulos. Training Binary Neural Networks with Real-to- binary Convolutions. In International Conference on Leurning Representations, 2020.
[74] X. Mei, K. Zhao, C. Liu, and X. Chu. Benchmarking the Memory Hierarchy of Modem GPUs. In IFIP International Conference on Network and Parallel Computing, pages 144-156, Springer. 2014.
14

---

[75] G. Morse and K. O. Stanley, Simple Evolutionary Optimization Can Rival Stochastic Gradient Descent in Neural Networks. In Proceedings of the Genetic and Evolutionary Compulation Conference 2016, pages 477-484, 2016.
[76] V. M. Nguyen. Boolcan Variation and Boolean Logic BackPropagation. arXiv:2311.07427, May 2024.
[77] G. Nie, L. Xiao, M. Zhu, D. Chu, Y. Shen, P. Li. K. Yang. L. Du, and B. Chen. Binary Neural Networks as a proppose Compute Paradigm for On-device Computer Vision. arXiv preprint arx11.2202...7 2022.
[78] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An Imperative Style, Pigh-Peerformncce Deep Learning Library. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[79] Petersen, C. Borgelt, H. Kuehne, and O. Deussen. Deep differentiahle logic gate networks. In S. Kayejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 2006-2018. Curran Associates, Inc., 2022.
[80] C. Philippenko and A. Dieuleveut. Bidirectional Compression in Heterogeneous Settings for Dis- tributed or Federated Learning with Partial Participation: Tight Convergence Guarantees. arXiv preprint urXiv:2006. 14591, 2020.
[81] B. T. Polyak. Introduction to Optimization. Translations Series in Mathematics and Engineering. Optimization Software Inc. Publication Division, New York, 1987.
[82] H. Qin, Ding. M. Zhang, Q Yan, A. Liu, Q. Dang. Liu, and X. Liu. BiBERT: Accurate Fully Binarized BERT. International Conference on Learning Representations, 2022.
[83] H. Qin, R. Gong, X. Liu, X. Bai, J. Song, and N. Sebe. Binary Neural Networks: A Survey. Patter Recognition, 105: 107280,,,, 2020.
[84] H. Qin, Gong, X. Liu, M. Shen, Wei, F. Yu, and J. Song. Forward and Backward Information Retention Accurate Binary Neural Networks, In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[85] H. Qin, M. Zhang, Y. Ding, A. Li, 7. Cai, 7. Liu, F. Yu, and X. Liu. BiBench: Benchmarking and Analyzing Network Binarization. In Proceedings of the 40th International Conference Machine Learning, volume 202 Proceedings of Machine Learning Research, pages 08351-28358 PMLR, 23-29 Jul 2023.
[86] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi. XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks. In Proceedings of the European Conference on Computer Vision (ECCV), October 2016.
[87] A. Sebastian, M. Le Gallo, R. Khaddam- Aljameh, and E. Eleftheriou. Memory Devices and Applications for in-memory Computing. Nature Nanotechnology, 15(7):529-544, 2020.
[88] Y. S. Shao and D. Brooks. Energy Characterization and Instruction-Level Energy Model of Intelé Xcon Phi Processor. In International Symposium on Low Power Electronics and Design (ISLPED), pages 389-30 989-394, 2013.
[89] J. Sim, S. Lee, and L.-S. Kim. An Energy-Efficient Deep Convolutional Neural Network Inference Processor With Enhanced Output Stationary Dataflow in 65-nm CMOS. IEEE Transactions Very Large Scale Integration (VLSI) Systems, 28(1):87-100, 2019.
[90] K. Simonyan and Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. In International Conference on Learning Representations, 2015.
[91] D. Soudry, I. Hubara, and R. Meir. Expectation Backpropagation: Parameter-Free Training of Multilayer Neural Networks with Continuous Discrete Weights. In Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014.
[92] E. Strubell, A. Ganesh, and A. McCallum. Energy and Policy Considerations for Deep Learning in NLP. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguisties, pages 6655-6600, Florence, Italy, Jul 2019. Association for Computational Linguistics.
15

---

[93] X. Sun, N. Wang, C.-Y. Chen. J. Ni, A. Agrawal, X. Cui, S. Venkataramani, K. El Maghraoui, V. V. Srinivasan, and K. Gopalakrishnan. Ultra-Lww Precision 4-bit Training of Deep Neural Networks. In Advances in Neural Information Processing Systems, volume 33, pages 1796-1807, Curran Associates, Inc., 2020.
[94] Sze, Y.-H. Chen, T.-J. Yang, and J. S. Emer. Efficient Processing of Deep Neural Networks: A Tutorial and Survey. Proceedings of the IEEE, 105(12):225--233) 2017.
[95] V. Sze, Y.-H. Chen, T.-J. Yang, and J. S. Emer. How to Evaluate Deep Neural Network Processors: Tops/w (Alone) Considered Harmful. IEEE Solid-State Circuits Magazine, 12(3):28 41, 2020.
[96] M. Tan and Q. Le. EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedingy of the 36th International Conference on Muchine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6105-61 6114. PMLR, 09-15 Jun 2019.
[97] R. Timofte, E. Agustsson, L. Van Gool, M.-H. Yang, L. Zhang. B. Lim, et al. NTIR 2017 Challenge on Single Image Super- Respeutesoottion: Methods and Results. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
[98] H. Touvron, A. Vedaldi, M. Douze, and H. Jegou. Fixing the Train-Test Resolution Discrepancy. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[99] Z. Tu, X. Chen, P. Ren, and Y. Wang. AdaBin: Improving Binary Neural Networks with Adaptive Binary Scts. In Proceedings of the European Conference on Computer Vision (ECCV), October 2022.
[100] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[101] N. Verma, H. Jia, H. Valavi, Y. Tang, M. Ozatay, L.-Y. Chen, B. Zhang, and P. Deaville. In-Memory Computing: Advances and Prospects. IEEE Solid-State Circuits Magazine, 1 11(3):33-55, 2019.
[102] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman. GLUE: Multi- Task Benchmark and Analysis Platform for Natural Language Understanding. International Conference on Learning Representations, 2019.
[103] Wang. J. Davis, D. Moro, P. Zielinski. J. J. Lim, C. Coelho, Chatterjee, P. Y. Cheung, and G. A. Constantinides. Enabling Binary Neural Network Training on the Edge. In Proceedings of the 5th International Workshop on Embedded and Mobile Deep Learning, pages 37-38, 2021.
[104] J. Wangni, J. Wang, J. Liu, and T. Zhang. Gradient sparsification for communication--ffiiccnn distributed optimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[105] S. Williams, A. Waterman, and D. Patterson. Roofline: An Insightful Visual Performance Model for Multicore Architectures. Communications of the ACM, 52(4))65--7, apr 2009.
[106] G. Xiao, J. Lin, M. Seznec, H. Wu, J. Demouth, and S. Han. SmoothQuant: Accurate and Efficient Post- Training Quantization for Large Language Models. Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 38087-38099, PMLR, 23-29 Jul 2023.
[107] X. Xing, Y. Li, W. Li, W. Ding, Y. Jiang, Y. Wang. J. Shao, C. Liu, and X. Liu. Towards Accurate Binary Neural Networks via Modeling Contextual Dependencies. In Proceedings of the European Conference on Computer Vision (ECCV), October 2022.
[108] T.J. Yang, Y.H.. Chen, J. Emer, and V. Szc. A Method to Estimate the Energy Consumption of Deep Neural Networks. In 2017 51st Asilomar Conference Signals, Systems, and Computers, pages 1916-1920, October 2017.
[109] T.J.. Yang, Y.-H. Chen, and V. Sze. Designing Energy-Efficte Convolutional Neural Networks Using Energy-Aware Pruning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
[110] X. Yang, M. Gao, Q. Liu. J. Setter, Pu. A. Nayak, S. Bell, K. Cao, H. Ha, Raina, al. Interstellar: Using Halide's s Scheduling Language to Analyze DNN Accelerators. In Proceedings of the Twenty-Fihh Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. pages 0893-83,,30 2020.
16

---

[111] Z. Yang. Y. Wang, K. Han, C. Xu, D. Tao, and C. Xu. Searching for Low-Bit Weights in Quantized Neural Networks. In Advances in Neural Information Processing Systems, volume 33, pages 4091-4102. Curran Associates, Inc., 2020.
[112] Yu and P.Y.. Chen. Emerging Memory Technologies: Recent Trends and Prospects. IEEE Solid-State Circuits Magazine, 8(2):33-56 2016.
[113] R. Zeyde, M. Elad, and M. Protter. On Single Image Scale-up using ReprsseReprssnttaiionn. In Curves and Surfaces: 7th International Conference, Avignon, France, June 24-30, 2010, Revised Selected Papers 7, pages 711-730, Springer, 2012.
[114] Zhang. Yang, Ye, and G. Hua. LQ-Nets: Learned Quantization Highly Accurate and Compact Deep Neural Networks. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018.
[115] H. Zhang, M. Cisse, N. Dauphin, and D. Lapez-Paz. Mixup: Beyond Empirical Risk Minimization. In International Conference on Learning Representations, 2018.
[116] R. Zhang, A. G. Wilson, and C. De Sa. Low-Precision Stochastic Gradient Langevin Dynamics. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162, pages 26624 26644. PMLR, 17 23 Jul 2022.
[117] Y. Zhang, Z. Zhang, and L. Lew. PokeBNN; A Binary Pursuit of Lightweight Accuracy, In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 12475-12485 June 2022.
[118] Zhang.
Derivation of Backpropagation Convolutional Neural Network (CNN). University of Tennessee, Knoxville, TN, 22:23, 2016.
[119] Zhuang, C. Shen, M. Tan, L. Liu, and I. Reid. Structured Binary Neural Networks for Accurate Image Classification and Semantic Segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
17

---

Appendix
Table of Contents
A Details of the Boolean Variation Method
18
A.I Boolean Variation Calculus
18
A.2 Convergence Proof
22
Code Sample of Core Implementation
26
Training Regularization
28
C.I Assumptions and Notations
28
C.2 Backpropagation Scaling
29
BackPropngation Through Boolean Activation Function
Experimental Details
31
D.I Image Classification
D.2 Image Super-resolution
34
D.3 Semantic Segmentation
34
D.4 Boolean BERT Fine-tuning
40
Energy Estimation
40
E.1 Hardware Specification
40
E.2 Compute Energy
E.3 Memory Energy
Broader Impacts
44
A Details of the Boolean Variation Method
A.1 Boolean Variation Calculus
This section provides supplementary details of the Boolean Variation method, a sole development can be found in [76]. With reference to Example 3.10, Table 8 gives the variation truth table of f(x) = xor (,, r). for a, x E
Table Variation truth table of f(x) = xor(a, a, B.
8(x
+ xx)
f(a,x)
f(a, -x)
8f
f((
T
T
F
F
F
T
T
FF
T
F
T
T
T
F
F
F
T
F
F
T
F
F
T
T
F
T
T
T
We now proceed the proof of Theorem 3.12.
18

---

Definition A.1 (Type conversion). Define:
p: +
T, if > 0,
x 2 p(x)
0, if 0,
(13)
F, if < O.
e: L-
+1, ifa T, 0, if O, -1, ifa F.
a a e(a)
(14)
P projects a numeric type in logic, and embeds a logic type in numeric. The following properties are straightforward:
Proposition A.2. The following properties hold:
1. Vz, y E N: p(ay) = xnor(p(z), p(y)))
2. Va, b E L: e(xnor(e a, b)) = e(a) e(b).
3. Vz, y E N: x = y + |x| = ly| and p(z) = p(y)-
In partieular, property Proposition A.2(2) implies that by the embedding map c(-), have:
((T, F}. xor) = (f=1),-x),
(15)
F), xnor) ~ ([=1},x).
(16)
where = and x stand for isomorphic relation, and the real multiplication, resp. A consequence is that by e(.), computing sequence of pointwise XOR/XNOR, counting, and majority vote is equivalent to sequence of pointwise multiplications and accumulation performed on the embedded data. This property will be used in Appendices A.2 and C for studying Boolean method using some results from BNNs literature and real analysis.
Proposition A.3. The following properties hold:
1. a E L, x E N: xnor(a, x) = e(a)a.
2. x, y E N: xnor(x, y) = zy.
3. x E (L, N}, y/, E N: xnor(r, (r, y + z) = xnor(x, y) + xnor(r, 2).
4. x E (L, y, N: xnor(x, (r. Ay) Axnor(xx,))
5. x E [I, y N: xor(æ, y) -xnor(xx y).
Proof: The proof follows definitions 3.5 and A.1.
Following Definition 3.1 have Vt E M. xnor(T,t) = xmor(F, = -t, and xnor(0. f) = Put e = xnor(a, a, r). We have |o| = [x] and p(v) = (nor(a,p(x))
Hence, 0 p(u) 0
0;
T p(u) p(z)
z;;
a = F = p(r) = =p(r) = v = -r. x. Hence (1).
The result is trivial if x = or y = 0. For æ, * O, put e = xnor(z, y). we have
||| |x||y| and p(u)
(por(p(x)). p(y)). According to Definition A.1, if sign(x)
sign(v) (v), we have p(v) = = e = J | = ry. Otherwise, ie., sign(x) = sign(y).
p(u) = -| zy. Hence (2).
(3) and (4) follow (1) for L and follow (2) for E.
For (5), write = xor(r,)) v) and xnor(x, y), we have lu| = |u| and p(u) xor(p(e), = exnor(p(z),p()) pp()). Thus, sign(u) -iign()) +
19

---

Proposition A.4. For f.g E B), Vz, y B the following properties hold:
1. 6f(x + 1) xnor(ó(z- - v), (x)).
2. (-f)(xx)= = (z)
3. (g f)((x) = xn (f())
Proof. The proof is by definition:
1. Vx, y I. there are two cases. If y = I, then the result is trivial. Otherwise, i.e. y -. by definition we have:
f()) xnor + -2). + =x))
8f(r + -x) xnor (8(2 + - (x)).
Hence the result.
2. Vx, y E TB, is easy to verify by truth table that 8(-f(1 - y)) = -5 (o - y). Hence, by definition,
(-f)(x) = xnor( ((x + 0(- + +x))))
xnor(ō(# -w), os(x -r))
= -xnord6(= + -r), 6f(x + -r))
= -f)
3. Using definition, property (i), and associativity of xnor, Va E B we have: (go f)()) xnor(ō(x + -x), 5g (x) + ((=))) xnor(ō(x + -x), xnor xnor(6](r
x) (f)'((
smor(g'(f(an)) xnor(ō(: 11:000-0000 -z), 6f(x + +z))
Proposition A.S. For J E F(B, N), the the following properties hold:
1. E. B: ff y) = xnor fz)).
2. x Ra
3. x g ((,N (z)) f(()+
Proof. The proof is as follows:
1. For x, E B. Firstly, the result is trivial if x. For y # v. i.e., xx, by definition:
f((x) = xnor (5(x - ( - -z)).
Hence, 1ōf(x + -x)] = 1f(xx) since 10(x + -z)l = and
(x)) = xnor 6(x + - p(ff + xz))
p(ff(z + x)) = xnor (6(x + p(
where p(-) is the logic projector Eq. 13. Thus, 8f(z + -x) xnor(ó(z -x), (x)). Hence the result.
2. Firstly Vz, y E B, we have
8(af(x - = af(z)
adf(ι + v).
Hence, by definition,
(af)((x) xnor (6( (6xx -1) + + =z))
= xnor(ō(z ( adf(2 =))
axmor(6(x=== -x), 0f(z -z)), due to Proposition A.3(4)
= af)
20

---

3. For E F(B,N)
g)+ = xnor(ō(x + ,), + gz( + -x)
xnor(8(2 - -I), 5f -x) + ōg(x - -a))
xnor(ō(x + -x), 6f(x + -x)) + xnor(ó( + -z), + -x)),, f'(x) g'(),,
where (+) is due to Proposition A.3(3).
Proposition A.6 (Composition rules). The following properties hold:
1. For B 4 B 4 D: (go (z) xnorld((((=) Vr
2. For 4 D. B. if (z) and g(U 1). then: (go f)) = xnor ((())
Proof. The proof is as follows.
1. The case of B I IB 2 B is obtained from Proposition A.4(3). For B 4 B 3, N, by using Proposition A.5(1), the proof similar to that of Proposition A.4(3).
2. By definition, have
f)(x) = xnor(ō(1 + -z), 0g(f(x) + f(-x))).
(17)
Using property (1) of Proposition A.5, we have:
f(-x) f(x) 8f(x + -x)
= fx) xnor(ō(x + -x), (x))).
(18)
Applying Eq. 18 back to Eq. 17, the result is trivial if f'(x) = 0. The remaining case
[x) for which we have xnor(ō(# +
=1. First, for xnor(ō(x
-x fx))) = 1, we have:
(g([(x) ((-x)) )g([(z) + ((x) +1)
=f(((x)))
xnor()'[(zz)))
xnor(y' ( -a),
(19)
Substitute Eq. 19 back to Eq. 17, we obtain:
(g o f))(z) xmor 66(z + -z), 8g(f(x) f(-x)))
xmor (8(z -z), xnor(g (f(z)) x fx),
xnor(g' (x)))
where that last equality is by the associativity of xnor and that xnor(x, xx) = T for r e B.
Similarly, for xnor(ô(z + -x), (x)) -1, we have:
8g(f(z) + f(-x)) = 6g(f(z) - f(x)) 1)
= -g'(f(x)111
xnor(g((f(z) xnor ((xx +
(20)
Substitute Eq. 20 back to Eq. 17 and use the assumption that g' g(((x)) = g((((z) 1), have:
g f)(x) xnor(ō(x: + dg(((() + f(-=))
xnor 60zz -z), xmor 1), xnor(6(x f())))
Hence the result.
The results of Theorem 3.12 are from Propositions A.4 to A.6.
21

---

A.2 Convergence Proof
To the best of our knowledge, in the quantized neural network literature and in particular BNN, one can only prove the convergence to an irreducible eπror floor [61]. This idea has been extended to SVRG [25]. and recently SGLD in [116], which also up to an error limit.
In this section we provide complexity bounds for Boolean Logic in a smooth non-convex environment. We introduce abstraction model its optimization process and prove its convergence.
A.2.1 Continuous Abstraction
Boolean optimizer is discrete, proving convergence directly is a hard problem. The idea is to find continuous equivalence so that some proof techniques existing from the BNN and quantized neural networks literature can be employed. We also abstract the logic optimization rules as compressor QoO, Qa and define gradient accumulator a as a++1 d + ((()). When is constant, recover the definition (10) and obtain my = 1ja, Our analysis is based on the following standard non-convex assumptions f:
A. Uniform Lower Bound: There exists fa R s.t. f(w) 2 fa, Vu R
A. 2. Smooth Derivatives: The gradient V ((w) is I--Lipschitz continuous for some I, > 0, ie.,
Vw, Vo E : (VV(w)
S -Vvll
A. 3. Bounded Variance: The variance the stochastic gradients is bounded by some o² 0, i.e.
Vw E Rd: E f(w) = f(w) and E [[))(w)]? o²
A. 4. Compressor: There exists < 1 s.t. Ye, Vu E Rd, [Q: (v. w) u112 S >/|ui|2
A. 5. Bounded Accumulator: There exists E R. s.t. Vt and Vi [d]. we have laele $ K.
A. Stochastic Flipping Rule: For all w E Rdd, we have E[Qo(w)lur w.
In existing frameworks, quantity f-) denotes the stochastic gradient computed random mini- batch of data. Boolean framework does not have the notion of gradient, it however has an optimization signal (i.e., plq) or its accumulator m, (10)) that plays the same role as f-). Therefore, these two notions, i.e., continuous gradient and Boolean optimization signal, can be encompassed into generalized notion. That is the root to the following continuous relaxation in which f-(-) standards for the optimization signal computed on a random mini-batee of data.
Within this continuous relaxation framework, A. 6 expresses our assumption that the flipping rule is stochastic and unbiased. Note that this assumption is standard in the literature related to (stochastic) quantization, see e.g., [4, 81, 104].
For reference, the original Boolean optimizer formulated in 3 is summarized in Algorithm in which flip(w;, (e, m241) flips weight and reset(ws (W, m4+1) resets its accumulator when the flip condition triggered.
Algorithm 2: Boolean optimizer
m 8.m, m)p())) 2 W1+1 + flip(w, (w,, m241);
m++1 < reset(w) mc+1);
Algorithm 3: Equivalent formulation of Boolean optimizer
Data: Qo, Qı quantizer
my +- v/ (we) tes
A, Q (m,, we);
3 W++1 + Qo Ar);
1.41 f- m. A.;
Algorithm 3 describes an equivalent formulation of Boolean optimizer. Therein, Qo. Q are quantizers which are specified in the following. Note that EF-SIGNSGD (SIGNSGD with Error-Feedbaut
22

---

algorithm from [53] is particular case of this formulation with Qo0 = Identity() and Q1(
sign(). For Boolean Logic abstraction, they are given by:
Q (m,, wx) = wi (ReLu(w,m, 1) sign(w,m, + 2) (Qu(ws) = sign(w:).
(21)
The combination of Q1 and Qo is crucial to take into account the reset property of the accumulator my- Indeed in practice, 4 := Q1 (m,, wt) is always equal to except when |mg] > and (ig)(m;) = sign(w,) (i.e., when the flipping rule is applied). As we has only values in {+1}, Qo acts as identity function, except when A, is non-zero (i.e., when the flipping rule is applied). With the choices (21), we can identify flip(wr, my) = Qa (w: (m,, Wx)). We do not have closed-form formula for reset (w;, m++1 1) from Algorithm 2, but the residual errors et play this role. Indeed, Ex+1 m, except when A is non-zero (i.e., when the flipping rule is applied and e1+1 is equal to 0).
The main difficulty in the analysis comes from the parameters quantization Qu(). Indeed, we can follow the derivations in Appendix B.3 from [53] to bound the error term E [[]]=|]]]. but we also have additional terms coming from the quantity:
hr Qo Qi (m), (w: Qi (Me,, wx)).
(22)
As a consequence, assumptions to 6 enable us to obtain [hh,] = and to bound the variance of h,- Remark A.7. Assumptions 1 to 3 are standard. Assumptions 4 to 6 are non-classic but dedicated to Boolean Logic strategy. A. is equivalent to assuming Boolean Logic optimization presents at least one flip at every iteration t. A. is classic in the literature of compressed SGD [53, 4, 80). Moreover, A. and A. 6 are not restrictive, but algorithmic choices. For example, rounding (Qu function) can be stochastic based the value of the accumulator my Similar to STE clipping strategy, the accumulator can be clipped to some pre-defined value x before applying the flipping rule to verify
A. 5.
Remark A.8. Our proof assumes that the step size 1j is constant over iterations. But in practice, we gently decrease the value of 17 at some time steps. Our proof can be adapted to this setting by defining a gradient accumulator such that 0++1 = dt + (p(e)). When 7) is constant we recover the definition (10) and we obtain m, naa-- In the proposed algorithm, gradients are computed on binary weight wy and accumulated in dz. Then, one applies the flipping rule on the quantity We = n/0 (w: = my when 1) is constant), and one (may) reset the accumulator d₁.
We start by stating a key lemma which shows that the residual errors et maintained in Algorithm do not accumulate too much.
Lemma A.9. Under A. 3 and A. 4, the error can be bounded as B[[lee|1]] <
[1->)> 2
2y
Proof. We start by using the definition of the error sequence:
| 2 ||Qu (me, (r)e,w))= m, 1
Next we make use of A. 4:
||ett 112 < 1111m1112
We develop the accumulator update:
||ec+1| 1| < 7/le, + fw:))11
We thus have recurrence relation on the bound of es, Using Young's incquality, we have that for any
3 > O,
||c++]|12 >>(1 + B)lle 7(1 + ))72(((())))1
23

---

Rolling the recursion over and using A. 3 we obtain:
B[]|e++11l] Sx(1 + [Il 11 + y(1 +
8 )1y² [V)(w)))
S + ||e + + +
3 g)rp?
1
3 inid
(+(1+ x11
711 + ) 71 + 30?
Take
1-2 and plug it in the above bounds gives: 24
27
E |ett1111 [1
(1 7)3" 1
Then, the next Lemma allows us to bound the averaged norm-squared of the distance between the Boolean weight and wA Qı (m,, wz). We make use of the previously defined quantity ha (22) and have: Lemma A.10. Under assumptions and A. 6: [[[ S nds..
Proof. Let consider coordinate i E [d]. Qoli 1 or +1 for value with some probability Pt, For the ease of presentation, we will drop the subscript i. Denote u, := We Qi(m,, Wz). Hence, h2 can take value (1 u²) with some probability pt and (-1 u,) with probability 1 Ps. Assumption A. 6 yields 2p,--
u. Therefore, we can compute the variance of h, as follows:
E h4
12
E
+ (wi Qm w2))² - 2Qu(w, - Q1 w.)(w: - Qi Qm ws)
Σ ((1 u (-1 (-1-4))2(1 pt))
Σ - u2)
The definition of uy leads to
uf = 1- (1+ Qi (m, = -2w;Q (m+, w:))
(m, w/) w2)( Q1 wt)).
When m, 1, we directly have (m,,, (2 - Qi we)) = 0 S qpc. When m, 2 1, we apply the definition of Q1 to obtain:
Qi (m,, wx) Q1 (m,, wx)) S m2 m.)
Therefore, we can apply this result to every coordinate, and conclude that:
E [1x S qds.
(23)
A.2.2 Proof of Theorem 3.17
We now can proceed to the proof of Theorem 3.17.

---

Proof. Consider the virtual sequence = We C2. We have:
1x+1 Qo (w:+ A.) (m+ At)
(Qo(u, A,) + A, ee) [(m)).
Considering the expectation with respect the random variable Qo and the gradient noise, we have:
B[ my = 32 - (ww)).
We consider F- the expectation with respect to every random process know up to time We apply
the L-smoothness assumption A. 2, and assumptions A. 3, A. 6 to obtain:
L E 2
(e(f((e+1)- - f(x)]] S (V( Vf(w)))
[1Qo(u; - A.) + D.) 7 - wrl3
We now reuse he from (22) and simplify the above:
(e]((r=))- f(x)) - V.(w.) + _ Ee 1141111111 n/ {wm)))
n s (-<()((>)>>>>>>> Vf(w;) + vf(w)), f((w))) + - 2 _ [11 [ ((w())1
Using Young's inequality, we have that for any 0, [e[ - [x+)) S - (V (x+) - V[(w)) Vs(w:), Vs((w)) L
+ 1 + B) [1 2
"1
1
)o
Making again of smoothness and Young's inequality we have:
(x((()))))) s(x))) < 7/ ([())) ().)) V[(W)), vs(wi))
+ $ [1+ || 2 + L
L
1
71 +
)0²
2
3
- --IlV((,)) + 7P
[[
+
|| f
- V 1
2
2p
+ _ B) B)E |
L
n (1
+ 8)0²
1
2
nL?
< - n| (w( + 2 [1:)(()))
| well ?
2p
||c+11
L
+
2 (1 + (1+ [1rl)
1 (1 +
002
2
3
Under the law of total expectation, we make use of Lemma A.9 and Lemma A.10 to obtain:
112
47
1 - ()
(1 - 7)2 1'002
2p
L 71 + 3)dx - (1+
L
3002
1
+ 8
2
B
Rearranging the terms and averaging over t gives for < 2 (we can choose for instance p = 3 = 1):
1
Σ [W t=
2(f(wp) - f+) 2T 4T?02 T(T +1)
(1 (1-7)2"² + dr.
7
L
T+1
The bound in Theorem 3.17 contains 4 terms. The first term is standard for a general non-convex target and expresses how initialization affects convergence. The second and third terms depend on the fluctuation of the minibatch gradients. Another important aspect of the rate determined by Theorem 3.17 is its dependence on the quantization error. Note that there is an "error bound" of 4 dl that remains independent of the number of update iterations. The error bound is the cost of using discrete weights as part of the optimization algorithm. Previous work with quantized models also includes error bounds [61, 62].
25

---

B Code Sample of Core Implementation
In this section we provide example codes in Python of Boolean linear layer that employs xor logic kernel. This implementation is in particular based on PyTorch [78]. The class of Boolean línear layer defined Algorithm and its backpropagation mechanism, overwritten from autograd, shown in Algorithm 5. Here, we consider both cases of the received backpropagation signal Z as described Fig. 2, which are either Boolean (see Algorithm 6) or real-valued (see Algorithm 7), An example code of the Boolean optimizer is provided in Algorithm 8.
Notice that custom XORLinear layer be flexibly combined with any FP PyTorch modules to define a model. The parameters of this layer are optimized by the BooleanOptimizen whereas those FP layers are optimized by a common FP optimizer like Adam [54].
Algorithm 4: Python code of XOR linear layer
import torch
from torch import Tensor, an, autograd typing import Any List, Optionsl, Callable
class XORLinear (no. Linear):
__init (self, in_features: out_features: int, bool_bprop: bool, s*kuargs):
10
super (XORLinear, self) ielitt..init__. (in_fextures, out_features, **vvargs) self. bool_bprop bool_bprop
12
13
def peranetere (eelf):
14
self seight an Parameter wwnriih. (0, 2, self NeiggN.tiht..ppppp
15
self. biee self. bias nn. Parameter (torch. randint
17
(torch.randiat (0, 2, (salf maalf.out_fent fut_rrauure ,)))
19
def forward (self, (self, x): return UDIFunction.applyy self veight self bias, self bool_
20
Algorithm 5: Python code of the backpropagation logic of XOR linear layer
XORFunction (autograd. Function):
@staticmethod
def forxard(ctx, I, W, B, bool, bproppprop: bool):
etx save_for_ wawe__orrbbccaarddeee (X. bool_bprop baol_bprop
Elementvise
logic torch. logicallg (XC:
Nlna, NKna,, (N)))
10
Sun over the input S s. (din=2)
12
14
0-centered for use with BatchNorn when preferred R. (1]/2
16
17
return
18
19
@staticmethod
backvard 2):
21
if ctx. bool, cox.bbob_pprep bprop:
22
G_x. G_v. Q_ backvard_bool (ctx, 2)
24
C_X. C_V, G_B
backward_ (ctx, 2)
26
return G_X, G G_B, None
26

---

Algorithm 6: Backpropagation logic with Boolean received backpropagation
def backward, brrevarrdbboolcttt (ctx, 2):
an*
Variation of input:
delta (xor (x..)))ddltaaax
ddelta (Lose)(ooo))// (oss))deltaa( (x) xnor nzg neg x) xor (2
Variatiion of reighta:
nog
delta (Lossa))ead) = xnor (z, x) xor (z,x)
Variation of biag:
10
bias xnor (bias, (beasbias,
True) (ruue -.y Variation bias is driven in the basie that of veight with xhor logic and input True.
11
Aggregation:
13
Count the number of TRUEs - sun over the Boolean data Aggr
(TOT TRUEs) 2TRUES share TOT is the size of the aggragated dimenaion
15
16
17
X, N, ctx saved, tavaooe tensors
18
Boolean variation input C_I torch. lorch.logical ( Nonel, ;)))
20
22
Aggregate over the fetturee dimension G_X 2 aum (din-1) N.ahape
23
25
a Boolean variation of veights logiha.oical (Z[: Nonel, x(:, ;])
27
28
a Aggragate over the batch dimenaion S.W.sunndiienn
[bapape
30
Boolean variation bias
32
is not None: Aggregate the batch dimension
33
34
6_B (din--)))) z. shapp
15
37
return G_X, G_W, G_B
Algorithm 7: Backpropagation logic with real received backpropagation
backward_rral (ctx, X, N. ctx rax..aard_tennorr
*.*
Boolean variation of input processed using torch avoiding loop: Boolean)
emb (W): T->1, P->-1 => enb 24-1 delta (Loes)
(=(12) *мa
G_X z. nn (1-2+W)
10
..*
12
Boolean variation of zeighta prosessed using torch avoiding loop: emb(X)
xer Real, X: Boolean)
14
emb (X): T->1, F-2-1 => enb (X) 2I-1
15
>> (Lossa)(a//)) = 2 (1-2X)
2.t(). (1-2xX)
17
*** Boolean variation bias
19
not None:
20
G_B Z. (din---))
22
# Return
x_X, G_W,
27

---

Algorithm 8: Python code of Boolean optimizer
class Booleandp:imizer (torch, optim Optimizer):
def ...itt... (self, parans, ir: float):
super (BoolesnOpeinizer: for param, group in self. wellf.prram_e.. paran.groupa:
self) (elf)...init_... (parans, diet
param_ param_group(" (aam-ggrop(Paccccc ("acuuns" '] = [torch. zaros_1ike data) for param_group
parane '1]
param grw.pprratiioo
[o For p in param_groupl (aimm paranaa ']]
self aalf._ab_flips
10
Oproperty
ab_ ab_flips (solf):
12
self. _bb ffipp self._mb.rlip
14
raturn
15
16
step(selr))
17
for paran_group in self welf..pram_.ee param_groupa
for P in enumerate (paran_grous) group ''params "]):
19
calf.update paran_group, idx)
21
def (edafe paran: Tensor, paren_group: dict, idx: int):
22
accun paran. (rroup(rratioo' [[ixx] paran.group l'accuns 'I [1dx] paran.group("Ir
param.grad. graa..grddddaa gata.
23
paren.groupl al
accun
paran_to_fiig
(2*param. data-1) datar-))
25
paran paran.data (at.apaaaaatooooeeeeeo to
torch. torch.logica. caaaaaatttttaaaaeeaaaaeaaaaaaaal (param.
dataranddtaaliie data ta
26
paran.groupl ("cccup"s
[paran_tt_ooo
=
(rraaggopppPratioo param_groupl ["ration [idx]
paran_to_flll f.l.p..looate.... () mean()
28
falfi_ + float foliaa_to_fllpp.._. float ())
C Training Regularization
C.1 Assumptions and Notations
We capital letters denote tensors. So, W X', S', and Z' denote weight, input, pre-activation, and received backpropagation tensors of a layer We also use Proposition A.2 and the discussion therein for studying Boolean logic in its embedding binary domain. follows that in this section B denotes the binary set {+1).
Let (eu, 2 denote the Gaussian distribution of mean and variance a², and (p)) denote Bernoulli distribution on I with E [0, 1]. Note that for X ~ B(p), if E[X] = 0, then E [ = 1.
We assume that the backpropagation signal to each layer follows Gaussian distribution. In addition, according to experimental evidence, cf. Fig. 4, we assume that their mean f can be neglected w.r.t. their variance ²²
follows that:
z (H, with P M
(24)
We also assume that signals mutually independent, i.e., computations going be made random vectors, matrices and tensors, and it assumed that the coefficients of these vectors, matrices and tensors mutually independent. We assume that forward signals, backpropagation signals, and weights (and biases) of the layers involved are independent.
Consider Boolean linear layer of input size and output size denote:
Boolean weights: W E Bmxx,
Boolean inputs: X E B":
Pre-activation and Outputs: s E [| n,, n/ , X e B";
Downstream backpropagated signal: Z m.
Upstream backpropagated signal: z I!"
In the forward pass, we have: 5t xor(W') X*), and x maj(S))
With the following notations:
28

---

W = ~ (B(Pt))) with Poj [0, 1];
X (Xi)sen (B(R))een with q E [0, 1]:
Z (Z))iem ~ (Mis,, df))mmm
Z stands for the truncated (with derivative of tanh) version of Z for sake of simplicity.
And assuming that Vi,o; o, 14 and < σ, we can derive scaling factors for linear layers in next paragraph.
Remark C.I. The scaling factor inside a convolutional layer behaves in a similar fashion except that the scalar dot product is replace by full convolution with the 180-rotated kernel matrix.
C.2 Backpropagation Scaling
We now compute the variance of the upstream backpropagated signal Z'-1 with respect to the number of neurons and the variance of the downstream backpropagated signal:
vj n, Var 12-1)
Σ
Var(W, Z),
(W, Z self mutually independent)
(25)
W 2 2
W 2
E8
(26)
W 2
2
EE B[W 1/
1 ²B "
(W, Z are independent)
(27)
(2pis 1) 1)
(28)
mE
(μ < σ)
(29)
mE
2
E
a tanh
(u aW' x//2
(independence assump.) (30)
Iu
Ratio mean over standard deviation of the backprop over the first batch epochs
Ratio mean over standard deviation the backprop
10
10-4
10-3
10-4
7
10-a
BoolConv1
BoolConv2
BoolDense
RealDense
Figure 4: Empirical ratio of the mean to standard deviation of the backpropagation signal, experi- mented with CNN composed of BoolConv BoolConv BoolDense RealDense layers and MNIST dataset.
29

---

E[ (u)
0.55
60
0.54
0.53
200
400
600
800
1000
layer size m
Figure 5: Expected value of tanh derivative with integer values as input, for several output sizes m.
Let us focus on the term EE| @tanh is computed thanks to enumeration. The event "u 1" indicates that we have k + scalar values at level "+1" and level "-1" such that 2k m. Hence,
des (u)² where E [| m, m|] for m even. The probability P(u
171 2
Pluu ()
(31)
2
Thus,
i tanh
tanh
E
(u)2
= Σ
(u)²p(u)
(32)
Ou
Du
tanh
2
(p)),
(with symmetry)
(33)
Ou
u=0
m
(1 (ann?((o)))
(34)
2
m-1
10=0, euen.
The latter can be easily pre-computed for a given value of output layer size m, see Figure5.
The above figure suggests that for reasonable layer sizes m, E @ (u aW زو } As consequence we can make use of (30), and approximate the variance of the backpropagated signal as:
Far(z"=1) = Var(Z').
(35)
Remark C.2. The backpropagation inside convolutional layer behaves in similar fashion except that the tensor dot product is replace by a full convolution with the 180-rotated kernel matrix. For given stride and kernel sizes kay ky. the variance of the backpropagated signal is affected follow:
mkaky Var Var(Z!).
(36)
2v
Let denote by MP the maxpooling operator (we assume its size to be (2, 2)). In the backward pass, one should not forget the impact of the tanh' (a))) and the MP operator so that:
ttanh Ou (u MP(Conv(aW'' x'))) 0MP
z Convaal (W WO 2¹)
(u Conv(aW" ,x'))
Ou.
(37)
30

---

Let focus on the last term: Hence,
@MP Ou
(u
Conv(aW", = 1(u max(Conv(aW", ))))
OMP
TMPP
E
(u
Conv(aW' ,x1))
E
(u Conv(aW",
(38)
Ou
du
x 1
(39)
As a consequence, for a given stride and kernel sizes kz ky, the variance of the backpropagated signal is affected follow:
Var(Z"-1) = 1
Var(Z) (
(40)
2v
C,3 BackPropagation Through Boolean Activation Function
Due to the binary activation, the effect on the loss function by an action on weight w diminishes with the distance A : |s -| from threshold pre-activation s to which contributes. Throughout the step activation function, the backpropagation signal can be optionally re-weighted by a function which is inversely proportional having this property. In our study, tanh' (aA) turns out to be a good candidate which a is used to match the spreading in terms of standard deviation of this function and that of the prt-avtivation distribution.
A, for instance, tanh' (A), (1 + A) 2 cxp( (p((-),, any other
We start by computing the variance of the pre-activation signal St with respect to the number of neurons, without considering the influence of backward tanh':
fj n, Var(S))=
Σ Var(W!,x))
(W, X' self mutually independent)
(41)
W!! 2 xx - E W x
E
(42)
W
B [x[x;²] - E E[W! B[x]]²
(W, X are independent)
(43)
13 xx!²
(2pis [)?
(44)
x11
mE
since μ <
(45)
m.
(46)
This leads
(47)
2 3m
in order to have Var(aS) = x² where is the range of the pre-activation, c.g., m Cin x k2 x ky for a 2D convolution layer of filter dimensions (Cin, hi bi, Com))
D Experimental Details
D.1 Image Classification
D.1.1 Training Setup
The presented methodology and the architecture of the described Boolean neural networks (NNs) were implemented in PyTorch [78] and trained on 8 Nvidia Tesla V100 GPUs. The networks thought predominantly Boolean, also contain fraction of FP parameters that were optimized using the Adam optimizer [54] with learning rate 10-3, For learning the Boolean parameters we used the Boolean optimizer (see Algorithm 8). Training the Boolean networks for image classification was conducted
31

---

with learning rates 1) = 150 and 17 12 (see Equation 10), for architectures with and without batch normalization, respectively. The sayee--aramettrs were chosen by grid search using the validation data. During the experiments, both optimizers used the cosine scheduler iterating over 300 epochs.
We employ data augmentation techniques when training low bitwidth models which otherwise would overfit with standard techniques. In addition to techniques like random resize crop or random horizontal flip, we used RandAugment, lighting [68] and Mixup [115]. Following [98], used different resolutions for the training and validation sets. For IMAGENET, the training images were 192x 192 px and 224 x24 px for validation images. The batch size was 300 for both sets and the cross-entropy loss was used during training.
D.1.2 CIFAR10
VGG-SMALL found in the literature with different fully-connected fully-connected (FC) layers. Several works take inspiration from the classic work of [24], which uses FC layers. Since other BNN methodologies only use a single FC. layer, Table 9 presents the results with the modified VGG-SMALL.
Table 9: Top-1 accuracy for different binary methodologies using the modified VGG-SMALL (ending with FC layer) on the CIFAR 0 dataset.
Forward Bit-width (W/A)
Training Bit-width (W/))
Method
(%)
12/32
32/32
XNOR-NET [86]
1/1
32/32
87.4
LAB [43]
1/1
32/32
87.7
RAD [27]
1/1
32/32
90.0
IR IR-NET [84]
1/1
32/32
90.4
[65]
I/1
32/32
91.3
SLD [111]
1/1
32/32
92.0
BBLD [Ours]
1/1
1/16
90.8
D.1.3 Ablation Study on Image Classification
The final block design for image classification was established after iterating over two models. The Boolean blocks examined were evaluated using the RESNET 8 baseline architecture and adjusting the training settings to improve performance. Figure presents the preliminary designs.
The Boolean Block I, Figure 6a, is similar to the original RESNET1S 8 block in that BN operations removed and ReLUs are replaced by the Boolean activation. This design always includes convolution in the shortcut with spatial resolution being handled by the stride. Notice that for this block we add Boolean activation after the Maxpool module in the baseline (also for the final baseline architecture). The Boolean Block II. Figure 6b, is composed by two stacked residual modules. For downsampling blocks we use the reshaping operation to reduce the spatial resolution and enlarge the channel dimensions both by a factor of 2. The shortcut is modified accordingly with different operations in order to guarantee similar spatial dimensions before the summation.
Table 10 summarizes the results obtained with the proposed designs on IMAGENET. During our experimentation, we validated the hypothesis that increasing network capacity the convolutional layers yielded higher accuracy values. However, similar to FP CNNs, we confirmed there is a limit by which the hypothesis ceases to be true, leading overfitting. Incorporating more severe training strategy had a sustained positive impact. Even so, for larger configurations, the compromise between accuracy and size can be cumbersome.
Among the strategies to reduce overfitting during training we included: mixup aata-augmeetation [115], image illumination tweaking, rand-augment and smaller input resolution for training than for validation [98]. All combined, increased the accuracy by ~03 points (check results for Block + base channel 230 with and w/o additional data augmentation).
Compared to Block II, notice that the data streams Block are predominantly Boolean throughout the design. This is because it makes use of lightweight data types such as integer (after convolutions) and binary (after activations). addition, avoids the need of using a spatial transformation that may affect the data type and data distribution. In that regard, Block II requires 4 times more parameters
32

---

Japst
Conttt
Block (e..))
Signcit
Maspool
B0onw(M.N.9
ROoeqEar, X.2)
(MOon 1)
BignX)
Rasi: Block
Downe: Flock
M1.3)
Sin..3)
Basic Block (v.
Easic Block (8x. St..
Downs, Blook (s. 2n,
MrgPool
BigeXK)
Block 26,
Boolean block
(b) Boolcan block II.
(c) RESNETIS layout.
Figure 6: Preliminary designs for the baseline architecture and the Boolean basic blocks. The dashed and red-shaded operations in the Boolean block II introduced for downsampling blocks.
for the convolution after reshaping. than the corresponding operation in Block I. This is exacerbated in upper layer convolutions, where the feature maps are deeper. Therefore, makes sense to use Block I, as it is lighter and less prone overfitting when the network capacity is expanded.
D.1.4 Neural Gradient Quantization
For completeness, we also implemented neural gradient quantization to quantize it by using INT4 quantization with logarithmic round-to- te-eaesst approach [21] and statisties aware weight binning [22]. Statistics aware weight binning is method that seeks for the optimal scaling factor, per layer, that minimizes the quantization error based on the statistical characteristies of neural gradients. involves per layer additional computational computations, but stays negligible with respect to other (convolution) operations. On IMAGENET, we recover the findings from [21]: 4 bits quantization enough to recover standard backpropagation performances.
D.1.5 Basic Blocks SOTA BNNs for Classification
Recent BNN methodologies have proposed different mechanisms to improve performance, Most of them exploit full-precision operations adjust datastreams within the network, like shift and scaling factors before binary activations [68] or channel scaling through Squeeze-and axnd-xxittation modules [73, 36]. Figure 7 shows the basic blocks of three methodologies that perform particularly well in IMAGENET. Together with BN and regular activations, those techniques not only add an additional level of complexity but also lead heavier use of computational resources and latency delays.
For comparison we also show the proposed block (Figure 7a) used in our experiments for Image Classification, Image Segmentation and Image Repee-Resolttion. Our block is compact in the sense that it only includes Boolean convolutions and Boolean activations, strategically placed to keep the input and output datastreams Boolean.
Table 10: Evaluation of the proposed blocks in IMAGENET and their respective configurations during training.
Buse Channel
1s Bit-width
Shoricut Fil. Size
Acc.
Design
Augmentation
(%)
128
32
I x 1
Random Crop, Random Flip
$3.35
192
32
Random Crop. Random
56.79
Block
192
x 32
Lighting, Mixap, Rand Augment and [98]
61.90
256
32
I Xx
Lighting. Mixup. Rand and [98]
64.32
x 3
Lighting, Mixup, Rand-Augment and [98]
66.89
128
I
1 x
Random Crop, Random Flip
$6.05
128
Random Crop.
58.38
Block II
192
192
32
32
Ix
Lighting. Mixup. Rand-Augment and [98]
Random Crop. Random Flip
61.10
63.21
230
32
Random Crop. Random Flpp
61.22
230
32
x
Lighting, Mixup, Rand Augment and [98]
64.41
33

---

PReLU
X
BOOL
BCONW
AVGFOOL P3
FINEXT
PReLU
SCORW
BOOL
BCOW 3x3
HEank/ 8/)
$1.90
S2
BCONV 3xd
Shoieal Pootis
8001
KCONV.10
Fictu(x B)) i
$1.
64.11 P1
ICONy
PRuLU
RetU
BOOL
CONY 1x1
BCOWV Te:
BCONY jx $3
T- B-BN +
51,00
linary datuPow dasalow
GMODD
EN
PX
8))
lad dateflrr
Eastanette
800L
linary sime
Rel
(a) Boolean Block w/o BN.
(b) BNEXT sub-blos block [36].
(c) REACTNET [68].
(d) BINEAL-NET [77].
Figure 7: Comparative graph of popular techniques and Boolean module. Notice how multiple full-precision operations like BN, PReLU, or Squecze-and-Excialll are overly used on each BNN block.
D.2 Image Super-resolution
The seminal EDSR [64] method for super-rexolution was used together with our Boolean methodology. In particular, the residual blocks are directly replaced by our Boolean basic block, Figure 8. For all three tasks in super-resolution, (i.c. x2, x3, x4), training was carried out with small patches of 96x96 px (40 of them extracted randomly from each single image in the DIV2K dataset) and validated with the original full-resolution images. The learning rate for real and boolean parameters were 10-4 and 17 36, respectively. The networks the ground-truth and the predicted upsampled image while using the Adam optimizer and Boolean optimizer (see Algorithm 8). In experiments the batch size was 20. Some example images generated by our methodology are showed in Figures and 10.
trained by minimizing the -nom between
D.3
Semantic Segmentation
D.3.1
Network architecture
Our Boolean architecture is based DEEPLABV3 [17], which has shown great success in semantic segmentation. It is proven that using dilated or atrous convolutions, which preserve the large feature maps, instead strided convolutions prominent for this task. our Boolean model with RESNET layout, we replace the strided convolutions in the last two RESNET 8 layers with the non-strided version, and the dilated convolutions are employed to compensate for the reduced receptive field. Thus, the images are 8x downsampled instead of 32x, preserving small object features and allowing more information flow through the Boolean network. As shown in Figure 6a, in the Boolean basic block, a 3 x 3 convolution instead of x convolution is used to ensure the comparable dynamic range pre-activations between the main path and the shortcut. Keeping these Boolean convolutional layers non-dilated naturally allows the backbone to extract multi-scale features without introducing additional computational cost.
The Atrous Spatial Pyramid Pooling (ASPP) consists of multiple dilated convolution layers with different dilation rates and global average pooling parallel, which effectively captures multi-scale information. In the Boolean ASPP (BOOL-ASPP), we use one 1 x Boolean convolution and three 3 x Boolean dilated convolution with dilation rates {12, 24, 36) following by Boolean activation functions. The global average pooling (GAP) branch in ASPP captures image-level features, which crucial for global image understanding as well as large object segmenting accuracy. However, in BOOL-ASPP, shown in Figure 12c, the Boolean input X leads to significant information loss
34

---

Comm.3...3
Conwi3, K;
Sign/ [X]
Convi
BCComiss
Bign
BConn'x m.8
Convie
@Comiin.s
Scaling
8x
8
BigniXX
Convie
Sign X]
Convix,
Conn's
Pixel Shuftle
Pixot Shuttle 2
Convis,
Comwis 3,3)
Small EDSR.
(b) Our Boolcan EDSR.
Figure 8: Small EDSR for single scale x2 super-resolution and our Boolean version with Boolean residual blocks. both architectures the channels dimensions are k. 256 and the shaded blocks are repeated 8x.
(a) Ground-truth targets.
(b) Enlarged crops.
(c) Predicted images.
(d) Enlarged crops.
Figure 9: Ground-truth high resolution images and the output of our Boolean super-resolution methodology. First row: image "013" from BSD100, with PSNR: 35.54 dB. Second row: image "014" from Set14, with PSNR: 33.92 dB.
before the global average pooling may cause performance degradation large objects. Therefore, we keep the inputs integer for the GAP branch demonstrated in Figure 12d. To prevent numerical instability, batch normalization used in the GAP branch before each activation function. Using
35

---

(a) Ground-truth target.
(b) Enlarged crop.
(c) Predicted image.
(d) Enlarged crop.
Figure 10: Ground- -ruth high resolution target image (top) and the output of our Boolean super-
resolution methodology (bottom). Image "0810" from the validation set of DIV2K, with PSNR: 34.90 dB
BOOL-ASPP enhances the multi-scale feature extraction and avoids parameterized upsampling layers, e.g. transposed convolution.
D.3.2 Training setup
The model was trained on the CITYSCAPES dataset for 400 epochs with a batch size of 8. The AdamW optimizer [71] with an initial learning rate of 5 10-4 and the Boolean logic optimizer (see Algorithm 8) with a learning rate of r 12 were used respectively for real and Boolean parameters. At the early training stage, parameters could easily flipped due to the large backward signal; thus, backbone, we reduce the learning rate for Boolean parameters in the backbone to y = 6. We employed the polynomial learning rate policy with p = 0.9 for all parameters. The cross-entropy loss used for optimization. We did not employ auxiliary
to better benefit from the MAAGENTT-rretriinn
36

---

X E
Features
X c IB
Conv x 1. di (Fig. 12a)
Conv 3 3, (Fig. 12b)
Conv x 3, d24 (Fig. 126)
Conv 3 x d36 (Fig. 12b)
GAP (Fig. 12c)
concat
Conv
Multi-scale Features
ConvClassifier
Logits
Bilinear Interpolation
SegMap
Figure 11: Boolean segmentation architecture.
X"
X
ReLU BN
X E
Global Aug Pool
Global Aug Pool
M.
BC
BConwi ar N.
Xign(X)
Sign X
Sign(X)
BN Sign(X)
(a)
(b)
(c)
(d)
Figure 12: Boolean Atrous Spatial Pyramid Pooling (BOOL-ASPP) architecture. (a) 1 x Cony
branch. (b) 3 3 dilated Conv branch with dilation rate of (c) Naive global average pooling branch. (d) Global average pooling branch.
loss knowledge distillation as these training techniques require additional computational cost, which is not in line with our efficient on-device training objective.
D.3.3 Data sampling and augmentation
We aim reproduce closely full-precision model performance in the semantic segmentation task with Boolean architecture and Boolean logic training. Due to nature the Boolean network, common regularization method, e.g., weight decay, is not applicable. Moreover, with more trainable parameters, the Boolean network can suffer from over-fitting. In particular, as shown Table 11, the imbalanced dataset for semantic segmentation aggravates the situation. There is significant performance gap for several classes which has low occurrence rate, including rider (9.5%), motor (11.2%), bus (9.5%), truck (6.9%) train (17.0%). We argue that the performance gap is due to the similarity between classes and the dataset's 's low occurrence rate, which confirmed as shown in Figure 13.
Data augmentation and sampling are thus critical for Boolean model training. Regarding data augmentation, employed multi-scale scaling with random scaling factor ranging from 0.5 to 2. We adopted random horizontal flip with probability p 0.5 and color jittering. In addition, we used rare class sampling (RCS) [45] avoid the model over-fitting to frequent classes. For class
37

---

Table 11: Class per image and performance gap occurrence rates in CITYSCAPES training set with naive BOOL-ASPP design. Class with low performance gap' and class with high performance gap".
Image ratio (%)
À mloU (%)
Roadt
98.62
0.0
Sidewayt
94,49
0.7
Building!
98.62
0.6
Wall
32.61
7.4
Fence
43,56
3.8
Polc
99.13
1.8
Light
55.73
6.5
Signt
94.39
2.8
Vegetation
97.18
0.1
Terrain
55.60
0.8
Sky
90.29
-0.2
Person
78.76
1.5
Rider
34.39
7.4
Car
95.19
0.3
Truck
12.07
6.9
Bus
9.21
12.8
Train*
4.77
Motor
17.24
15.3
bike
55.33
2.0
100
17.5
15.0
Per image occurence rate (%)
80
12.5
10.0
60
miou
7.5
5.0
2.5
20
0.0
-2.5
pole
car
sky
vegetation
Road
building
sideway
terrain
person
bike
sign
fence
light
truck
rider
wall
bus
motor
train
Figure 13: Class per image occurrence ratio and performance gap with naive BOOL--ASPP design.
the occurrence frequency in image fe given by:
fe ΣN I E)
(48)
N
where N is the number of samples and yi is the set of classes existing in sample i. The sampling probability of class is thus defined as:
1-/e
exp
T
Pe
(49)
Σø=1
K
exp
1-f0
38

---

where K is the number of classes, and T' is Syyer--prameee for sampling rate balancing. In particular, for the CITYSCAPES dataset, we selected T 0.5.
Input image
Ground truth
Full-precision
BELD (Ours)
Figure 14: Qualitative comparison of Boolean model CITYSCAPES validation set.
D.3.4 Qualitative analysis on cityscapes validation set
The qualitative results of our Boolean network and the full-precision based are demonstrated in Figure 14. Despite the loss of model capacity, the proposed Boolean network trained with Boolean logic optimizer has comparable performance with large objects in the frequent classes, even in the complicated scene.
D.3.5 More experiments on semantic segmentation
We evaluated the effectiveness of BOOL-ASPP by investigating the per-class performance gap to the full-precision model. As demonstrated in Table 12, significant gap exists between the Boolean architecture with naive BOOL-ASPP design; i.c., using Boolean activations for ASPP module as illustrated in Figure 12c. However, the gap could be reduced by using BOOL-ASPP and RCS. In particular, the BOOL-ASP improves the loU of truck from 54.5% to 64.1% and bus from 65.5% to 88.8% bike from 68.8% 69.1% and motor from 42.8% 46.8%. This indicates that combining proposed BOOL-ASPP and RCS improves the model performance on low occurrence classes as well as similar classes with which are easy to be confused.
D.3.6 Validation on PASCAL. VOC 2012 dataset
We also evaluated our Boolean model on the 21-class PASCAL VOC 2012 dataset with augmented additional annotated data containing 10, 582, 1, 1,4, and 1, 456 images in training, validation, and test set, respectively. The same setting is used as in the experiments on the CITYSCAPES dataset, except the model was trained for 60 epochs.
As shown in Table 13, our model with fully Boolean logic training paradigm, i.e., without any additional intermediate latent weight, achieved comparable performance the state-of-the latent- weight-based method. Our Boolean model improved performance by incorporating multi-resolution feature extraction modules to 67.3% mloU.
Table 12: Class-wise IoU performance CITYSCAPES validation set.
addeway
bulding
ismain
rood
Hight
Fder
Methods
mloU
79.8
59.3
78.3
70.8
70.7
Naive
67.3
52.7
90.1
56.7
72.8
66.5
0.0
0.7
0.6
1.4
3.8
+1.8
6.5
2.8
0.1
0.8
002
1.5
7.4
0.3
6.9
12.8
17.0
15.3
2.0
4.4
RG [Oons]
97.1
78.
80.8
46.3
51.3
53.7
53.3
66.5
90.3
58.
92.7
72.6
45.1
91.9
61.1
69.8
48.7
46.8
69.1
67.4
0.2
1.8
0.3
2.3
3.7
-3.
5.9
2.5
4.2
+0,5
+0.
1.7
9.5
4.7
0.3
9.5
17.9
11.2
1.7
3.3
39

---

Table 13: Performance on PASCAL VOC 2012 val set.
Seg, head
Model
mloU (%)
A
baseline
64.9
FCN-32s [70]
GROUP-NET [119]
60.5
4,4
B@LD [Ours]
60.1
4.8
FP baseline
72.1
DEEPLABV3 [17]
BBLD [Ours]
67.3
4,8
D.4 Boolean BERT Fine-tuning
We conducted experiments on the BERT model [26] drawing on the experimental framework proposed in BIT [67]. For this experiment, our goal to fine-tune the original pre-trained BERT model using Boolean precision. To validate our method we used the GLUE benchmark [102] with 8 datasets. For our experiments,
modified the baseline architecture using the proposed methodology Algorithm 8, That is, core operations within the transformer are substituted by native Boolean components, e.g. Boolean activations and Boolean linear layers. The FP parameters were optimized using the Adam optimizer with the learning rates proposed in [67]. Correspondingly for Boolean weights, we used our Boolean optimizer with learning rate 77 100.
E
Energy Estimation
Energy consumption is fundamental metric for measuring hardware complexity. However, it requires specific knowledge of computing systems and makes it hard to estimate. Few results are available, though asprimental--aased and limited to specific tested models [see, e.g., 32, 88. 74, 13, 14, 33]. Although experimental evaluation precise, it requires considerable implementation efforts while not generalizing. In addition, most relevant works are only limited to inference and not training [19, 57, 110].
E.1 Hardware Specification
Ascend architecture. We intend to estimate the training energy consumption on Ascend chip architecture introduced in [63] and dedicated DNN computing. The core design of Ascend described in [63]. Essentially, it introduces 3D (cube) computing unit, providing the bulk of high-intensity computation and increasing data reuse. On the other hand, it provides multiple levels of on-chip memory. In particular, memory LO, which is nearest to the computing cube, is tripled to boost further near-memory computing capability, namely LO-A dedicated to the left-hand-side (LHS) input data, LO-B dedicated to RHS input data, and LO-C for the output. For instance, in convolution, LÓ-A, LO-B, and LO-C correspond to the input feature maps (IFMAPS), FILTERS, and output feature maps (OFMAPS), respectively. In addition, the output results going through LO-C be processed by a Vector Unit for in-place operations such as normalization and activation. Table 14 shows energy efficiency and capacity of the memory hierarchy of commercial Ascend architecture [63].
Table 14: Memory hierarchy and energy efficiency (EE) of an Ascend core [63] used in our evaluation.
L3 (DRAM)
L2
L1
LO-A
L0-B
LO-C
EE [GBPS/mW]
0.02
0.2
0.4
4.9
3.5
5.4
Capacity [KB]
8192
1024
64
64
256
Nvidia architecture. We also have estimated the energy consumption for the Nvidia GPU (Tesla V100). Similarly, this architecture utilizes different memory levels with varying read and write energy characteristics. For instance, the L.2 cache size is 6 MB per GPU. The cache 64 KB per Streaming Multiprocessor (SM). Each Tesla V100 GPU has 80 SMs, so the total LI cache is 5120 KB (5 MB). However, specific details on the read and write energy consumption for each memory level of the Tesla V100 GPU are proprictary and not publicly disclosed by Nvidia. Thus, we show
40

---

the normalized energy consumption relative to the computation of MAC at the arithmetic logic unit (ALU). Table 15 shows the numbers for each storage level, which are extracted from commercial 65 nm process [18].
Table 15: Normalized energy cost relative to the computation of one MAC operation at ALU.
DRAM
L2
L1
RF
1 MAC at ALU
200
6x
2x
1x
1x
E,2 Compute Energy
Energy consumption is the sum of compute and memory energies. Compute energy is simply given by the number of arithmetic operations multiplied by their unit cost. The number of arithmetic operations is directly determined from the layer's s parameters. For the Ascend architecture, their unit cost is obtained by considering the compute efficiency 1.7 TOPS/W [63]. For Boolean logic operations, we follow the usual estimation that ADD INT-n costs (2n - 1) logic operations where n stands for bitwidth.
E.3 Memory Energy
On the other hand, memory energy all consumed for moving data between their storage through memory levels and the computing unit during the entire lifetime of the process. Since energy consumed at each memory level given by the number of data accesses to that level times per- access energy cost, it consists in determining the number of accesses to each level of all data streams (i.e., LHS, RHS, Output). Besides taking into account the hardware architecture and memory hierarchy of chip, our approach to quantifying memory energy is based on existing methods [19, 94, 57, 110, 42, 108] for dataflow and energy evaluation. Given the layer parameters and memory hierarchy, it amounts to:
1. Tiling: determining the tiling strategy for allocating data streams on each memory level.
2. Movement: specifying how data streams are reused or kept stationary to determine their access numbers.
In the following, we present our method for the forward and backward passes by taking the example of a convolution layer, as convolutions are the main components of CNNs and the primary source of complexity due their high data reuse. The parameters of 2D convolution layer are summarized in Table 16. Here, we denote IFMAPS, FILTERS, and OFMAPS by I, F. and O, respectively.
Table 16: Shape parameters of convolution layer.
Parameter
Description
N
hatch size
M
number OPMAPS channels
C
number of IFMAPS channels
II' /W!
IFMAPS plane height/width
H" H*/W /WF
FILTERS plane height/width
HO/WO
OFMAPS plane height/width
E.3.1 Tiling
Since the IFMAPS and FILTERS are usually too large to be stored in buffers, the tiling strategy is aimed efficiently transferring them to the computing unit. Determining tiling parameters, which summarized in Table 17, is an Ha-Hard problem [110].
41

---

Table 17:
Tiling parameters of convolution layer.
Parameter
Description
M2
number of tiling weights in buffer
M1
number of tiling weights in L1 buffer
Mo
number of tiling weights in LO-B buffer
N2
number tiling IFMAPS in buffer
N₂
number of tiling IFMAPS in L1 buffer
No
number of tiling IFMAPS in LO-A buffer
H//W2
height/width tiling 1FMAPS in buffer
H /W!
height/width of tiling 1FMAPS in L.2 buffer
Hg /W6
height/width of tiling IFMAPS LO-A buffer
An iterative search over possibilities subject memory capacity constraint provides tiling com- binations of IFMAPS and FILTERS on each memory level. Different approaches can be used and Algorithm 9 shows example that explores the best tiling parameters subjected to maximizing the
buffer utilization and near compute stationary (i.e., as much reuse as possible to reduce the number of accesses to higher levels). Therein, the amount of data stored in level i is calculated as:
Qf N₁ C, x H x W x bb, of M₁ X, x H X WF x b",
(50)
where / and b' /bF represent the memory and bitwidth of IFMAPS/HLLTERS, respectively.
Algorithm 9: Loop tiling strategy in the ith level
Input:
tiling parameters of IFMAPS and FILTERS level i 1, and buffer capacity of level Output: tiling parameters of IFMAPS and FILTERS at level i.
Initialize
Emin OC;
3 for Mj <- M,+1 to do
for N; No+1 to do
for H +- H
H= do
for ! + W i+1 to F do Calculate Q,, the required amount of IFMAPS and FILTERS be stored in the ith level of capacity ! Calculate ε,, the energy cost of moving IFMAPS and FILTERS from the ith level;
8
if (Q, S QuLax and (E, < m then
Retain tiling parameters as best;
Emin +- Egi
12 return Best tiling parameters
E.3.2 Data movement
For data movement, at level LO, several data stationary strategies, called dataflows, have been proposed in the literature, notably weight, input, output, and row stationary [19]. Since Ascend chip provides tripled LO buffers, partial sums can be directly stationary
the computing cube, hence equivalent to output stationary whose implementation is described in [28]. For the remaining levels, our question of interest is how to move IFMAPS block [Ni+1, C++1, H H4 W and FILTERS block [M++1, C++1, F FF1 from level i + 1 to level efficiently. Considering that:
IFMAPS are reused by the FILTERS over output channels,
FILTERS reused over the IFMAPS spatial dimensions,
FILTERS reused over the batch dimension,
42

---

IFMAPS are usually very large whereas FILTERS are small,
the strategy that we follow is keep FILTERS stationary on level i and cycle through IFMAPS when fetching them from level i + 1 as shown in Algorithm 10. Therein, FILTERS and IFMAPS read block-by-block of their tiling sizes, i.e., FILTERS block [M, C, 11 WF) and IFMAPS block [N; C. H W Hence, the number of filter accesses to level + is 1 whereas the number of IFMAPS accesses level + 1 equals the number of level-i FILTERS blocks contained in level i 1. Following this method, the number of accesses to memory levels of each data stream can be determined. Hence, denote by:
d. number of accesses to level i of data d,
E energy cost of accessing level i, given as the inverse of energy efficiency from Table 14.
Following [19], the energy cost of moving data from DRAM (L3) into the cube is given as:
Ed n353 ngng=2 + nonGn4ei + nangninfs
(51)
Regarding the output partial sums, the number of accumulations at each level is defined as the number of times each data goes in and out of its lower-cost levels during its lifetime. Its data movement energy is then given as:
00_ = (2ng 1)e3 + 2 (m2 1)82 + 2ng 2 (n (nf 1)81 + 2ng i 1)80:
(52)
where factor of 2 accounts for both reads and writes and the subtraction of is because we have only one write the beginning [19].
Algorithm 10: Data movement from + levels
Input: tiling parameters of IFMAPS and FILTERS at levels + and i. repeat
read next FILTERS block of size [M, C. HF, WFF from levels i + 1 to repeat
read next IFMAPS block of size [N, C, H/, WF] from levels + let the data loaded to be processed; until all IFMAPS are read into level i; until all FILTERS are read into level i:
E.3.3 Forward
In the forward pass, there are three types of input data reuse:
For an HJ x W IFMAP, there are HO x WO convolutions performed with a single HP x WF filter generate partial sum. The filter reused 170 x Wo times, and this type of reuse is defined as filter convolutional reuse. Also, each feature in the IFMAPS is reused H W times, and this is called feature convolutional reuse.
Fach IFMAP further reused across M filters to generate M output channels. This is called IFMAPS reuse.
Each FILTER is further reused across the batch of IFMAPS. This type of reuse called filter reuse.
From the obtained tiling parameters, the number accesses that is used for (51) and (52) determined by taking into account the data movement strategy shown in Algorithm 10. As result, Table 18 summarizes the number of accesses to memory levels for each data type in the forward pass. Therein, a" H HH/H' " Wo/ /W', HD !W? define the height/width of tiling OFMAPS in Li buffers, a = H and at W /w! for i 2, 1, and O.
43

---

Table 18: Numbers of accesses different memory levels of forward convolution.
Data
DRAM (L3)
L2
L1
L0
M My
H x W x og
0g
og
ag
M
Mg
F F(n))
N N2
H01 RD
Two WP
Na N2
x
x
W
4 MC
x
(n
E.3.4 Backward
For the backward pass, given that @Loss00 is backpropagated from the downstream, it consists in computing @Loss/OF and @ooss/O1. Following the derivation of backpropagation in CNNs by [118], it is given that:
@Loss/OF = Conv(I, (000))0,,, ÖLoss (01 Conv(Rot, (F), @oss//80)
(53)
(54)
where Rot, (F) is the filter rotated by 180-degree. As a result, the backward computation structure is also convolution operations, hence follows the same process detailed above for the forward pass. For instance, Table 19 summarizes the number of accesses at each memory level in the backward pass
when calculating the gradient G osss OT, Therein, C, defines the number of tiling IFMAPS in
Li buffer, 3 11' /H0 8hh W /Wo 8. H!! HP and 8 W! /WO for 2, 1, and 0.
Table 19: Numbers of accesses at different memory levels for @Loss/ /01.
Data
DRAM (L3)
L2
L1
LO
(n9)
A
HF
WF
x
ay
F (xx)
H
R
W
W7
II
W
G (n(²)
F Broader Impacts
Our multidomain comprehensive examination confirms that is possible to create high performing binary deep neural networks thanks to the proposed method. Our findings suggest the positive impacts many domains, making deep learning more environmentally friendly, in particular reduce the complexity of huge models like LLMs, and enabling new applications like online, incremental, on-device training, and user-centric AI models. Given the prevalence of LLMS, our approach can facilitate faster predictions learning. On the other hand, computing architectures have been so far pushed far from its native logic by high-precision arithmetic applications, e.g., 16-bit floating-point is currently most popular AI computing architecture. Boolean logic deep learning would motivate new software optimization and hardware accelerator architectures in the direction of bringing them back to the native Boolean logic computing. The proposed mathematical notion and its calculus could also benefit other fields such as circuit theory, binary optimization, etc.
more affordable devices, contributing the democratization of deep
44

---

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]
The contributions claimed the abstract and introduction are fully based on the method descrihed in and performance gains benchmarked in $ 4.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations, in particular, of using our method in the current computing architectures the paragraph "Limitations" in $ 5, and provide details about the convergence assumptions in Appendix A.2.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.imiations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
45

---

Answer: [Yes]
Justification: The assumption of each theoretical result is explicty and formally stated. However, due space constraint, all the proofs postponed Appendix A.2, and in particular the long list of convergence analysis assumptions are also reported in the appendix due to the space constraint.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the training details are described in 4, addition the utilized training reg- ularization techniques are also fully described in Appendix C. Python code implementation is also provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
46

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
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, described in supplemental material?
Answer: [Yes]
Justification: We used publicly common datasets in experiments. In Appendix provide example codes and experimental details for reproduction purpose.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
hti.bmmmsssiooicciiooooccoooc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//n cttpss.ccppbbbccguuucicc gww.d//////eeeeeee/e /CodeSubmis ss onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All details can be found in $ training regularization techniques in Appendix C and the code in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
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:
[Yes]
Justification: Standard deviation are provided (when computationally doable) 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
47

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide information on the computer resources in Appendix D and Ap- pendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:/ //tprr:////uuips... cc wewbblic/tthissuidddeeoo
Answer:
[Ye]]
Justification: It has been and continues be first priority be fully compliant with the scientific research spirit, and with NeurlPS Code of Ethics in particular.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., ., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See
Guidelines:
The answer NA means that there is no societal impact of the work performed.
48

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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]
Justification: Our work poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or 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]
Justification: We used publicly common datasets and code package. We fully cited the original paper that produced those assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
49

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
50

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
51


Reviews:
[{"review_id": "59Om7mZuBh", "reviewer": "Reviewer_xoY6", "summary": "The paper proposes a strategy for 1-bit backpropagating through the logic expressions of binary neural networks, drastically improving training speeds of BNNs.", "questions": "Listed in weaknesses.", "limitations": "Listed as references to paragraphs in weaknesses:\n\n6. \n\n9. \n\n12.\n\n14.\n\n17.\n\nNo potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "It is great to see a paper tackling 1-bit precision training. \nThis is a really important topic, and tackling it on the level of logic is very interesting. \nWith the right hardware, the approach could lead to drastic training speedups.", "weaknesses": "Not in any particular order.\n\n\n1. The grammar in the sentence “It is clear that there can be only a unique family of binary activation functions that is the threshold one.” is unclear.\n\n2. The notation $f’(x)$ appears to be overloaded (first defined as the variation of $f$ w.r.t. x, then defined as the derivative of $f$.)\n\n3. Notationally, I find it a bit odd that a binary value or Boolean value is called “logic” and a logic operation is called “logic connective”.\n\n4. It is hard to follow l. 169 ”its derivative has been defined in the literature as …” because there is no reference to any literature.\nIn general it would have been helpful to have references in Section 3, as it is unclear whether these notations 3.1—3.10 are proposed by you or are common in some literature you mention but not cite. Also reviewing the supplementary material, I didn’t find a reference for the notation or the derivative that \"has been defined in the literature”.\n\n5. What does the notation of an equality with a superscript of “xnor” mean?\n\n6. At first, it is not clear whether Figure 1 relates to training or inference cost or whether is estimated; a reference to Table 2 would also be helpful. Reviewing the supplementary, details of the estimation become clear, but it would be helpful to already more clearly understand how you come to the numbers and without significant effort, it is difficult to follow the 4.5 pages that state the assumptions for the energy estimation. After rereading the paper, I am still left wondering whether any of the V100 energy consumption reductions are measured or just “we estimate analytically energy consumption”. The sentences l. 243-245 imply it is estimated, but how could you estimate the energy for a device V100 to be efficient, if you cannot measure it because it is not energy efficient in reality? If you estimate it and it is in fact not efficient, it means that your estimate is incorrect and uses assumptions that do not fit the V100 device. \n\n7. In Equation 7, it seems like the variation (gradient?) can be larger than 1. Am I misunderstanding this?\nThen, in Eq. 9, we apply xnor between an integer and a ternary weight?\n\n8. Given that you respond to provide your code in the checklist, and provide a few code snippets in Apx. B, it would have been really helpful if you had actually provided executable code, rather than snippets that leave significant room for interpretation. Unfortunately, the code is not directly copyable, and reimplementing it is out of scope for reviewing.\n\n9. What is the precision used for the computations and accumulator states within the optimizer? Are they included in the energy estimate? In the code, accumulator seems to be a full precision float (param_group[’accums’]).\n\n10. On the boolean optimizer, does it make sense to replace “accumulator” with “momentum” or is that an inappropriate correspondance. It would be great if the notations are aligned with existing literature.\n\n11. What is the “VGG-SMALL” architecture? Reviewing [86], I do not find a “small” architecture for CIFAR-10.\n\n12. What is “base” in table 5? “‘Base’ is the mapping dimension of the first layer” doesn’t clarify it for me unambiguously. Does it mean the number of channels after the first layer? What is the precision of this first layer? Do you use binary inputs? Why do the larger models (e.g., B⊕LD (Base 256)) use such a base of 256, that would be 4x the original number of channels? If you are using full precision inputs, that would mean that you made the most expensive layer 4x as expensive here, giving you a potentially unfair advantage over the baselines (as your model is bigger and more expensive.)\n\n13. Details on which layers exactly are binary and which are integer or full precision for each architecture are missing.\n\n14. It would be helpful to include in each (2-5), whether you are using only logic or also floating point precision more expliclity. “FP shortcut” clearly indicates floats. \nIt should be pointed out more expliclity that the only ImageNet model with drastic speedups achieves 51.8% accuracy. \nFor the KD, knowledge distallation, it could be unfair to specify a training cost reduction, if training requires first training a larger full precision network.\n\n15. No details on the backpropagation through softmax and attention in the BERT experiments is given beyond the statement \"extreme binarization of transformer-based model is not trivial”.\n\n16. The regularization details (Apx. C) seem to be nowhere mentioned in the main paper.\n\n17. Number of epochs are very important in extremely low precision training, it seems like the paper uses substantially more epochs than typical for the data sets. This makes sense as such training usually requires more epochs than regular training, but it would be very important to clarify this in the main paper. This is an important limitation because if we need 2-5x as many epochs, the training time savings are reduced.\n\n18. Regarding related work, it is already extensive.\nRecently, \"Differentiable Weightless Neural Networks\" (DWNN, https://openreview.net/pdf?id=GBxflz0qdX) was published.\nThis paper covers backpropagation through differentiable logic gate networks via binary precision, see first equation of paragraph \"Finite Difference (FD)\".\nWhile DWNN is designed for logic gate networks (in particular differentiable logic gate networks (https://arxiv.org/pdf/2210.08277)) and not for binary neural networks, DWNN still somewhat applies to binary neural networks. (full-1bit BNNs are LGNs, but not all LGNs are BNNs.) \nAs your work and DWNN both deal with binary training of a network that is considered from a logic perspective, a short discussion would be great, in particular when considering your all encompassing \"for the first time\" claims. (I am not arguing against the claim, as the mentioned works do LGNs directly and you do BNNs (from an LGN perspective), but there are methodological relevances.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's effort to analyze our paper. Due to the 6000 character limitation, our response is split in two sets. Below we address the main questions (Q: 6, 9, 12, 13, 14). The remaining questions are addressed in the “Official Comment” following the review. Note that this is in compliance with the instruction from PC. We hope the reviewer will consider all the responses which are aimed at comprehensively addressing the questions.\n\n---\n\n**Q6.**\n\nFig 1 relates to the training cost vs. accuracy, and thank you for the suggestion we will reference it to Tab 2.\n\nWe confirm hereby that we estimate the energy consumption analytically, as also stated in the contributions at L.68: “we rigorously evaluate analytically the complexity of BOLD and BNNs”.\n\nFor energy estimation of the V100, we used an analytical approach for several reasons: (1) experimental estimation requires significant effort for hardware implementation, (2) each design needs specific hardware, making comparative assessments time-consuming, and (3) experimental methods are limited by current software and hardware capabilities, which lack neither per-bit memory allocation nor native logic gates, but the real multiplicator in the compute unit. Thus, analytical estimation is the only feasible method to overcome these challenges.\n\nTo analytically estimate energy consumption, we considered multiple factors, including hardware specifications, memory hierarchy, dataflow, and the design itself. These elements are intricate, with dataflow alone being a comprehensive field of study. The current literature mainly addresses the inference phase not the training of 2D convolution layers and is limited to real (full-precision (FP) and quantized) arithmetic. Consequently, developing an efficient analytical model for energy consumption required significant effort. The length of the presentation is due to the detailed nature of these considerations and the necessity of addressing them thoroughly.\n\n---\n\n**Q9.**\n\nThe accumulator is real-valued, and yes, it is included in our energy estimation. For further information, for CNNs, conv. layers are largely the dominating part as also shown in the literature.\n\n---\n\n**Q12.**\n\nAbout \"Base\": This term refers to the channel mapping of the 1st convolution in the ResNet, which converts a FP 3-channel image into a multi-dimensional feature map.\n\nRelation between base and channels after the 1st layer: Yes, in the ResNet, the \"base\" channel determines the mapping dimensions for following layers. In Appen. D, we show the ResNet18 layout for image classification, where \"base\" is denoted as $\\kappa$.\n\nPrecision of the 1st layer: Our designs use full precision for the 1st convolution and the last fully connected layer. This is detailed in the experimental setup (line 236) and in the training setup (Appen. D.1.1, line 1262). Including a small number of real params. in the BNN reduces the accuracy drop compared to fully real networks (as noted on line 122). This approach is standard in the BNN community and is also employed by other methodologies with which we compare our method. The ablation study in Appen. D.1.3 highlights the significance of the data type in the 1st conv.\n\nAbout binary inputs: The networks in our designs primarily consist of binary layers, where all binary convolutions receive Boolean inputs, as stated in the Experimental Setup (line 232). The exceptions are the full precision operations in the 1st and last layers. This approach is a common practice in the BNN community.\n\nAbout larger models: How much is cost saving for a comparable performance is a key question. \n- We increase the Boolean parameters only and not FP parameters as assumed. Our network remains predominantly Boolean.\n- For fairness, we grouped models with more params. into \"Larger Models\" (e.g., Bi-RealNet with 34 \\& 152 layers vs. our 18 layers), and we tested a 4x param. increase to study the param.-accu relationship.\n- Our paper highlights that BNN efficiency depends on more than just parameter count but also energy and accuracy. For instance, the \"KD: Resnet34\" category shows that even with default params., other networks consume more energy than ours.\n\n---\n\n**Q13.**\n\nThe information provided in the main text of the experimental section and experimental setup indicate the baselines employed in this study and explains how to obtain the Boolean designs from them. In brief, we respect the original layout of every baseline converting FP convolutions into Boolean and preceding these Convolutions by Boolean activations. Due to space constraints, detailed information for each network is provided in the Appen. D. We include diagrams specifying data precision and params. for each operation across tasks: image classification (Appen. D.1.3, Fig. 6), image super-resol. (Appen. D.2, Fig. 8), image segmen. (Appen. D.3.1, Fig. 11-12), and NLP (Appen. D.4).\n\n---\n\n**Q14.**\n\nThe Tabs 2-5 are self-explanatory as they only compare BNNs, as stated in the paper (line 236) and in response 12. The networks combine FP and binary params., with FP results clearly labeled as \"FP\" or \"full precision.\"\n\nFor the FP shortcut category in Tab 5, although it is not part of our method, we included it because it represents a significant work in the field and provides a useful comparison, particularly highlighting models with more FP data flows (specifically in the shortcuts of each block) than ours.\n\nFor ImageNet results, the title in Tab 5 specifies that all methods were trained on ImageNet, with accuracy and energy consumption during training being the key metrics.\n\nFor KD, we assert that the experiment and comparison setup are fair since all BNN models were guided by a pre-trained FP ResNet34 teacher. As noted in the Tab, the energy consumption calculation only accounts for the training of the BNN models, excluding the teacher's training.", "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": "XofQZlAvII", "reviewer": "Reviewer_faoj", "summary": "The paper explores advancements in binary neural networks (BNNs), particularly focusing on Boolean-weighted methods. It highlights the limitations of current BNN approaches and proposes a new method, B⊕LD, that operates directly on Boolean weights, improving energy efficiency and accuracy without relying heavily on full-precision components.", "questions": "What are the practical implications of deploying the B⊕LD method in real-world applications with respect to computational resource requirements and scalability?", "limitations": "NA", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method significantly reduces energy consumption compared to existing BNN approaches by directly operating on Boolean weights.\nThe method achieves higher accuracy than several state-of-the-art BNN methods, as demonstrated on the CIFAR10 dataset.", "weaknesses": "The method's reliance on Boolean weights may limit its adaptability to new data and tasks that require more flexible representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your positive feedback and insightful comments.\n\n---\n\n**Q1. The method's reliance on Boolean weights may limit its adaptability to new data and tasks that require more flexible representations.**\n\nThanks for your comment. It is true that low-precision neural networks often raise concerns regarding the flexibility. However, our method offers a notable advantage by allowing for a combination of full-precision and Boolean components within neural networks in a principled way. This approach not only significantly reduces complexity but also maintains model flexibility. We demonstrate this benefit with strong results on tasks requiring high precision, such as image super-resolution and segmentation. Additionally, in Section 4.3, we showcase our model's adaptability to new data and tasks in computer vision and NLP.\n\n---\n\n**Q2. What are the practical implications of deploying the B⊕LD method in real-world applications with respect to computational resource requirements and scalability?**\n\nAs presented in the Conclusion and Broader Impact sections, BOLD method by its low computational complexity, its design flexibility and seamless integration with the real-valued components can firstly reduce the computational intensiveness of the current deep learning. Secondly, BOLD can reduce the current issue of large model fine-tuning in which it has been shown that the real model weights and SGD-based optimizer are the dominant part of the memory consumption. And thirdly, BOLD can pave the way or enable new areas of applications that need online training or frequent model fine-tuning as well as on-device and tiny machine learning.", "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": "5Bbvf4FvTw", "reviewer": "Reviewer_VF3V", "summary": "Proposal of a training method for binary (or ternary) neural networks (inputs and weights are 2-valued, -1,+1, or 3-valued, -1,0,+1), which works without latent floating-point weights, but directly adapts the binary (or ternary) weights, thus improving training (especially in terms of memory consumption). A kind of \"discretized\" calculus for binary (or ternary) weights is derived for this purpose.", "questions": "Forward activation: Wouldn't it be natural to define y = 0 if s = tau for 3-valued logic? As it is written, the threshold function appears to be the same for 2-valued and 3-valued logic. Is this intentional? Same with Def. 3.6: Shouldn't there be some order relations involving 0? (I understand that it is stated that a and b are in B, but why this restriction?) Def. 3.7 uses 0, so this seems to be 3-valued logic, at least for the result, while a and b are again in B. The mixed use of 2- and 3-valued logic is confusing.\n\nThe notation with the caligraphic F does not seem to be defined anywhere, not even in the Appendix. What exactly does it mean? It's some function class, but what are the two arguments to F, given that functions f from F have only one argument? Domain and image space of f?\n\nIf I understand correctly, pre-activations are *not* Boolean, but integer. There is counting involved, not just Boolean operations (even though one can, of course, construct a Boolean gate network that performs the counting, but that requires something like 7n logic gates (asymptotically) for counting the 1s in n bits). I do not really understand how this counting is modeled and whether it is properly taken into account for the cost/energy evaluation (should be in E.3.3, I guess, but I don't really see it there).\n\nMore sophisticated optimizers, as described on page 6, seem to need floating point numbers for the aggregates q, not just Boolean values, right? If that is the case, does that not defeat the purpose? Because the weights may now be Boolean (2- or 3-valued), but with each weight at least one floating point aggregate has to be associated (depending on the optimizer). Doesn't this considerably reduces the memory gains during training? And how is it with batch normalization (Figure 1 shows BOLD with batch norm)? Floating point? Discretized to Boolean values before fed into next layer?\n\nHow are the Boolean functions L chosen? Can they be any Boolean function, possibly even including those that are constant or ignore one input? Are they the same for all neurons? Or are they different and maybe randomly initialized? I understand that the use of xnor in Section 3.3 is only an example (this is how I interpret page 5, line 199) and not meant to say that L is always xnor.", "limitations": "A short paragraph on page 9 addresses potential limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The approach seems to hold considerable potential as it bypasses the need for latent floating-point weights for training binary neural networks. The theoretical underpinning based on a \"discretized\" calculus for binary (or ternary) numbers appears to be sound and general. A convergence result is presented, as well as various experimental results that support the claims.", "weaknesses": "The presentation of the theory is extremely condensed, with a lot of specifics delegated to the appendix. Together with the appendix, the paper has more than 50 pages and hence would be long even for a journal publication (which might be more appropriate for this material, since it requires quite some preliminaries for which a conference publication does not offer appropriate space). As a consequence, the paper left me with a lot of questions (see below, maybe some are answered in the appendix, which I did not read in detail, as it is simply too long). This makes it a bit difficult to properly judge the merits of the paper. In principle, the idea is intriguing and I see a lot of potential in it, but I doubt that the very condensed presentation is appealing and conveys the intricacies well enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your insightful comments.\n\n---\n\n**Q1. The presentation of the theory is extremely condensed, with a lot of specifics delegated to the appendix...**\n\nThanks for your comment. We strongly believe that a self-contained and detailed paper is beneficial. Therefore, we aimed to provide comprehensive insights into our method in the appendices. We hope these details will be helpful for the community in gaining a better understanding our method, enhancing reproducibility, and facilitating researchers in extending our method, as well as practitioners in applying it to real-world problems. We focused on presenting the main results and maintaining the main storyline in the main paper. Many impactful works published at NeurIPS, such as [1], include extensive supplementary materials.\n\nIndeed, the reviewer ojfg highlighted this strength in our paper, stating, \"The methodology of the paper is clear (detailed derivations of theoretical statements are provided, code samples in Python are available, and there is significant discussion on training regularization techniques, model architectures used for experiments, as well as the process for energy estimation).\" \n\nRef:\n\n[1] Yang et al. Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes. NeurIPS 2019.\n\n---\n\n**Q2. Forward activation: Wouldn't it be natural to define y = 0 if s = tau for 3-valued logic? ... the threshold function appears to be the same for 2-valued and 3-valued logic. Is this intentional? Same with Def. 3.6: Shouldn't there be some order relations involving 0? ... The mixed use of 2- and 3-valued logic is confusing.**\n\nThanks for your question. Mathematically, it is completely possible to formulate that way. However, for the following main reasons that we didn’t: the current computing hardware is binary-based architecture, introducing a ternary base would encounter some application difficulty beside its possible higher complexity than binary one. \n\nFor Def 3.6 and related ones, we understand your insightful questions and are happy to provide you with the following clarification. Our final goal is to have a Boolean logic neural networks with Boolean logic processing, the introduced three-valued logic M is mainly for the mathematical formulation whose role arises from Def 3.7. Therefore, while our mathematical framework of Boolean variation can be directly generalized to other logics such as the 3-valued logic M, we remain focusing on the Boolean variation.\n\n---\n\n**Q3. The notation with the caligraphic F does not seem to be defined anywhere...**\n\nThe $\\mathcal{F}$ denotes the set of functions, for instance $\\mathcal{F}(A,B)$ denotes the set of all functions from source domain $A$ to image domain $B$. It was our consideration that this is a common notation, we didn’t introduce it. Thank you for your feedback, we will add a short introduction of this notation in the revised paper.\n\n---\n\n**Q4. ... pre-activations are not Boolean, but integer. There is counting involved, not just Boolean operations ...how this counting is modeled and whether it is properly taken into account for the cost/energy evaluation ...**\n\nYes, the pre-activation is integer. In the existing hardware, there can be at least two ways for that. The first is to use COUNTER gate after the kernel logic (i.e., XNOR in our example). The second is to use the Logic Threshold Gate, which due to space limitation we didn’t discuss this part. In our energy estimation, counter is modelled as an integer ADDER.\n\n---\n\n**Q5. More sophisticated optimizers seem to need floating point numbers for the aggregates q, not just Boolean values, right? .... Doesn't this considerably reduces the memory gains during training? And how is it with batch normalization? Floating point? Discretized to Boolean values before fed into next layer?**\n\nYes, you are right, q in (9) is an aggregate real-valued signal. For the second part of the question, there are several levels of consideration as follows:\n\n- In the basic form of the Boolean optimizer as shown in (9), there is only a real-valued tensor q of the layer whose weights are being updated. This tensor q is the same size at the weight tensor. In terms of memory consumption, the order of magnitude that this tensor q requires is at 1/total number of layers.\n\n- More importantly, note that in terms of the energy consumption, optimizer is very little compared to arithmetic layers such as convolution and fully-connected layers because optimizers do not involve data-reuse (data-reuse refers to the fact that a data element is reused several times in a computation, for instance in the matrix multiplication A*B a row of a matrix A is reused over all the columns of matrix B. Energy consumption increases quickly with the level of data-reuse due to data movement.)\n\n- Finally, from the mathematical point of view, it is possible to develop more sophisticated form of Boolean optimizer. However, as you mentioned, such development will need to take into account possible increase of the optimizer complexity. Therefore, we currently use Boolean accumulator optimizer as the best current option.\n\nAbout the BatchNorm, the output of a Boolean layer can be directly connected to a BatchNorm when this is used without need of any type conversion thanks to the composition rule of Theorem 3.11. \n\n---\n\n**Q6. How are the Boolean functions L chosen? ...**\n\nIn principle, the neuron kernel logic L can be any logic operators such as AND, OR, XOR, XNOR or even a new gate that is constant or ignores an input as you suggest. Moreover, it is completely open to use different logic gate for different neurons or different layers, can be even randomly chosen. In our experiments, for the implementation efforts, we only use XNOR as an example. Given that XOR = neg XNOR, the performance would be the same, then in final implementation, one can choose the gate according to its material cost.", "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": "Z0TuHP2egW", "reviewer": "Reviewer_HRmB", "summary": "The paper introduces an innovative approach to deep learning by flipping the binary weights and inputs. This method optimizes convergence in the Boolean domain, promising significant improvements in training efficiency and energy consumption. The extensive experiments conducted validate the effectiveness of this approach.\n\nPros:\n- Extensive Experiments: The paper conducts comprehensive experiments to validate the proposed method.\n- First to Provide Convergence Bound for Binary Weight: This is the first work to present a convergence bound for binary weights, a significant advancement over previous works that only considered convergence bounds for latent weights.\n- Entire Binary Data Stream: The method operates on a completely binary data stream, ensuring reduced complexity and improved efficiency.\n\nCons:\n- Assumption A6 (E[Q0(w) | w] = w): The paper assumes E[Q0(w)∣w]=wE[Q0(w) | w] = wE[Q0(w)∣w]=w. However, the justification for this assumption is unclear and needs further explanation.\n\nSuggestions:\n- Ablation Study on \\beta_t​: An ablation study on the parameter $\\beta_t$ could provide more insights into its impact on the model's performance and convergence.\n- Stochastic Rounding: The current method of stochastic rounding by taking the sign might not ensure that the expectation equals zero. Investigating alternative rounding methods could enhance the performance and reliability of the proposed approach.", "questions": "Suggestions:\n- Ablation Study on \\beta_t​: An ablation study on the parameter $\\beta_t$ could provide more insights into its impact on the model's performance and convergence.\n- Stochastic Rounding: The current method of stochastic rounding by taking the sign might not ensure that the expectation equals zero. Investigating alternative rounding methods could enhance the performance and reliability of the proposed approach.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Extensive Experiments: The paper conducts comprehensive experiments to validate the proposed method.\n- First to Provide Convergence Bound for Binary Weight: This is the first work to present a convergence bound for binary weights, a significant advancement over previous works that only considered convergence bounds for latent weights.\n- Entire Binary Data Stream: The method operates on a completely binary data stream, ensuring reduced complexity and improved efficiency.", "weaknesses": "- Assumption A6 (E[Q0(w) | w] = w): The paper assumes E[Q0(w)∣w]=wE[Q0(w) | w] = wE[Q0(w)∣w]=w. However, the justification for this assumption is unclear and needs further explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your positive feedback and insightful comments.\n\n---\n\n**Q1. Assumption A6 (E[Q0(w) | w] = w): The paper assumes E[Q0(w)∣w]=wE[Q0(w) | w] = wE[Q0(w)∣w]=w. However, the justification for this assumption is unclear and needs further explanation.**\n\nThank you the reviewer for this in-depth feedback. Our method to Theorem.3.16 is to firstly develop an equivalent abstraction of the Boolean optimization process: the Boolean optimizer is deterministic (conditionally to $q^l_{i,j}$) and discrete, but we define a continuous stochastic equivalent problem so as to employ standard non-convex analysis tools (see Appendix A.2). In our continuous relaxation, we assume that the flipping rule is stochastic and unbiased, i.e. $\\mathbb{E}[Q_0(w) | w]= w$. This assumption is standard in the literature related to (stochastic) quantization (see [1, 2, 3]).  We will add such a justification to the assumption A.6 in the camera-ready version.\n\nRefs:\n\n[1] Boris T. Polyak. Introduction to Optimization. OptimizationSoftware, Inc., 1987. \n\n[2] Alistarh et al. QSGD: Communication-efficient SGD via gradient quantization and encoding. NeurIPS 2017. \n\n[3] Wangni et al. Gradient sparsification for communication-efficient distributed optimization. NeurIPS 2018.\n\n---\n\n**Q2. Ablation Study on \\beta_t: An ablation study on the parameter beta_t could provide more insights into its impact on the model's performance and convergence.**\n\nThank you for the interesting suggestion. In fact, $\\beta_t$ is a scalar that adjusts automatically at each iteration (refer to Eq. 11). To evaluate its impact, we set $\\beta_t$ to a constant value and analyze the final accuracy of the training process. We conduct experiments using the VGG-Small model on the CIFAR-10 dataset, maintaining all other training configurations as outlined in the paper. The table below presents the results, showing the mean and standard deviation (mean(std)) for 5 fixed values, each tested 5 times. The attached PDF file in the general response consists of the convergence w.r.t. different choices of $\\beta_t$\n\n| $\\beta_t$               | Accuracy (%)  |\n|--------------------|---------------|\n| Adaptive (default) | 92.37 (0.105) |\n| 1.0                | 91.19 (0.090)   |\n| 0.5                | 63.47 (0.160)  |\n| 0.25               | 62.56 (0.629)  |\n| 0                  | 62.16 (0.210)  |\n| 5.0                | 59.54 (0.240)  |\n\nIt's important to note that setting $\\beta = 0$ effectively eliminates the accumulator's influence during optimization, resulting in suboptimal performance. When $\\beta$ is fixed at 1, we achieve full contribution from the accumulator, which enhances the change of state in the Boolean parameters and leads to improved performance. However, if the accumulator is given a lower weight (i.e., $\\beta < 1$), the performance declines significantly. Furthermore, setting $\\beta > 1$ causes instability in the optimization process from the first iteration, as the accumulator overshoots the optimal state.\n\nIn terms of convergence, only $\\beta=1$ has a sharp improvement at the beginning of training. At later epochs it shows a steady improvement both during training and validation, approaching our adaptive design. This is confirmed by the number of changes in parameter state (or flips), which is initially very large and then progressively reduced until only a few changes occur (please refer to Fig. 1c red curve in the provided Graphical Material). \nConversely, for $\\beta<1$  or $\\beta>1$ the convergence slows down drastically, to the point of no accuracy change. For such cases, the Boolean parameters are not updated and only the FP parameters are learned.\n\nNotably, even the best attempt, using $\\beta = 1$, reduces the accuracy by more than $1$ % compared to our proposed method. Therefore, adopting a constant value for weighting the accumulator has a negative impact on the accuracy of the model. This strengthens our point that a better alternative is to use an auto-regulator that adapts to the current state of the model, as we already do (refer to Eq. 10 and Eq. 11).\n\n---\n\n**Q3. Stochastic Rounding: The current method of stochastic rounding by taking the sign might not ensure that the expectation equals zero. Investigating alternative rounding methods could enhance the performance and reliability of the proposed approach.**\n\nThank you for the suggestion. Currently, our method does not use stochastic rounding, nevertheless investigating a method for the binary activation could help to gain better performance. This is a promising avenue for future research.", "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": "rkAbqr2N0d", "reviewer": "Reviewer_ojfq", "summary": "This paper proposes a novel mathematical concept, termed Boolean variation, and demonstrates that it can be used to define optimization algorithms for training deep neural networks (NNs) consisting of Boolean weights and activations. This is in stark contrast to contemporary binarized NNs, which achieve efficient inference but rely on floating-point latent weights during training, and hence are relatively computationally expensive. \n\nSpecifically, the authors introduce Boolean variation under Boolean algebra and show how it can be related to integer and real arithmetic to define NN blocks that operate with mixed-signals (e.g., real and Boolean). The authors then develop an optimization algorithm that can be used to train NNs with Boolean weights and activations, without the need of floating-point latent weights, and present a convergence analysis of the algorithm. \n\nUtilizing the newly introduced Boolean variation and its optimization algorithm that integrates well into existing deep learning frameworks, the authors conduct a wide range of experiments within various domains (image classification, super-resolution, image segmentation and NLP). The experimental results show that the proposed method achieves performance almost at the level of full floating-point models while consuming significantly less energy during training and inference. In almost all benchmarks, the proposed method sets the SOTA compared to binarized NNs.", "questions": "- **Methods / Experimental setting:** What logic gate/s were used for $\\text{L}$? Were different gate types tested, and were there significant performance differences? Is a mix of gate types better than a single gate type? Do different architectures/blocks perform best with different gate types?\n- **Experimental results:** On Line 279 it reads: “Particularly noteworthy are the superior results achieved on SET14 and BSD100”. In Table 3, all BOLD results have less PSNR than SMALL EDSR. The results are strong, although “superior” made me think these were instances in which BOLD outperformed a FP baseline.", "limitations": "The authors have adequately addressed limitations.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The work introduces a novel mathematical concept (that of Boolean variation) and demonstrates how it can be used to define optimization algorithms for training NNs with Boolean weights and activations. This offers a different (more energy efficient) path for arriving at optimized binary NNs for efficient inference vs. existing related work on binarized NNs (that rely on floating-point latent weights for training).\n- The related work is adequately cited.\n- Theoretical analysis is presented for the proposed optimization algorithm.\n- The authors perform experiments across various deep learning application domains (image classification, super-resolution, image segmentation and NLP). The experimental results support their claims.\n- The methodology of the paper is clear (detailed derivations of theoretical statements are provided, code samples in Python are provided, and significant discussion is presented on training regularization techniques, model architectures used for experiments, as well as how the energy estimation was conducted).\n- The proposed method advances the SOTA with respect to binarized NNs across various deep learning domains. Moreover, the proposed method offers a potential solution to reduce the energy demands of training large models. The ideas presented are therefore of both theoretical and practical interest to the NN and deep learning communities.", "weaknesses": "- Small points on clarity and quality for experiments (see Questions for details)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your positive feedback and insightful comments.\n\n---\n\n**Q1. Methods / Experimental setting: What logic gate/s were used for L? Were different gate types tested, and were there significant performance differences? Is a mix of gate types better than a single gate type? Do different architectures/blocks perform best with different gate types?**\n\nThank you for the question. Currently XNOR gate was used for L throughout all Boolean neurons. Given that XOR = neg XNOR, using XOR gate for L must give the same performance. In the early stage of this work, we have tested AND and OR gates, however some preliminary results showed that the resulting performance was slightly lower than XOR/XNOR. It could be due to the asymmetry property of AND/OR gate, it is to be confirmed and further investigated in the future. In addition, a mix of gates is completely possible, either at the layer level or at the neuron level. It would be also interesting to develop a method for mixing gates however we have not investigated this topic yet. \n\n---\n\n**Q2. Experimental results: On Line 279 it reads: “Particularly noteworthy are the superior results achieved on SET14 and BSD100”. In Table 3, all BOLD results have less PSNR than SMALL EDSR. The results are strong, although “superior” made me think these were instances in which BOLD outperformed a FP baseline.**\n\nThanks for pointing this out. Indeed, we wrote superior in the sense that our method is closer to the baseline for Set14 and BSD100 than for the other datasets. It will be replaced by “prominent” to avoid confusion.", "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:
Dear Reviewers,

We thank the Reviewers for having carefully reviewed our paper and provided insightful comments, which help to improve the paper. We are strongly encouraged by the endorsements and highly positive feedbacks from all the reviewers in the initial review on several aspects:

**1) Potential impacts.** *The paper tackles a really important topic (**Reviewer xoY6**). The approach holds considerable potential (**Reviewer VF3V**), could lead drastic training speedups (**Reviewer xoY6**) and significantly reduces energy consumption compared to existing BNN approaches (**Reviewer faoj**). The proposed method offers a potential solution to reduce the energy demands of training large models. The ideas presented are therefore of both theoretical and practical interest to the NN and deep learning communities (**Reviewer ojfq**).*

**2) Theoretical contributions.** *The work introduces a novel mathematical concept. This offers a different (more energy efficient) path for arriving at optimized binary NNs for efficient inference vs. existing related work on binarized NNs (**Reviewer ojfq**). The theoretical underpinning based on a "discretized" calculus for binary (or ternary) numbers appears to be sound and general (**Reviewer VF3V**). This is the first work to present a convergence bound for binary weights, a significant advancement over previous works that only considered convergence bounds for latent weights (**Reviewer HRmB**).*

**3) Empirical results.**  *The experiments are very extensive across various deep learning application domains (**Reviewers HRmB, ojfq**). The paper sets SOTA on many benchmarks compared to binarized NNs (**Reviewers faoj, ojfq**).*

**4) Presentation.** *The methodology of the paper is clear (detailed derivations of theoretical statements are provided, code samples in Python are provided, and significant discussion is presented on training regularization techniques, model architectures used for experiments, as well as how the energy estimation was conducted) (**Reviewer ojfq**). The related work is extensive and adequately cited (**Reviewers xoY6, ojfq**).*

We also appreciate many insightful and suggestive questions from the Reviewers. We have thoroughly studied them and hope that our response to individual comments here-below can address the Reviewers' concerns.  

The attached file contains additional results used to address Q2 of Reviewer HRmB.

Best wishes,

The Authors

Meta-review: The paper introduces methods of optimization of neural networks with boolean weights and activations. Specifically, the authors introduce boolean variation for discretized calculus on binary variables to define and derive optimization algorithms, and also provide convergence bounds for binary neural nets. The paper demonstrates the efficacy of the algorithms on wide variety of tasks such as image classification, segmentation, NLP.

I recommend acceptance of the paper.
Decision: Accept (poster)