Lossless hardening with ∂B nets

Ian Wright 1

Abstract∂B nets are differentiable neural networks thatlearn discrete boolean-valued functions by gradient descent. ∂B nets have two semanticallyequivalent aspects: a differentiable soft-net, withreal weights, and a non-differentiable hard-net,with boolean weights. We train the soft-net bybackpropagation and then ‘harden’ the learned
weights to yield boolean weights that bind withthe hard-net. The result is a learned discrete function. Unlike existing approaches to neural network binarization the ‘hardening’ operation involves no loss of accuracy. Preliminary experiments demonstrate that ∂B nets achieve comparable performance on standard machine learning
problems yet are compact (due to 1-bit weights)
and interpretable (due to the logical nature of thelearnt functions).

Figure 1. Learning discrete functions with a ∂B net.

2. ∂B nets
Definition 2.1 (Soft-bits and hard-bits). A soft-bit is a realvalue in the range [0, 1] and a hard-bit is a boolean value
from the set {0, 1}. A soft-bit, x, is high if x > 1/2, otherwise it is low.

1. Introduction

A hardening function converts soft-bits to hard-bits.

Neural networks must be differentiable. But differentiability
means we cannot directly learn discrete functions, such as
logical predicates. We can approximate discrete functions
by defining continuous relaxations. This paper explores adifferent approach: we define differentiable functions that
‘harden’, without approximation, to discrete functions.

Definition 2.2 (Hardening). The hardening function,
harden(x1 , . . . , xn ) = [f (x1 ), . . . , f (xn )], converts softbits to hard-bits, where f (x) = 1 if x > 1/2 and f (x) = 0
otherwise.
Soft-nets use soft-bits and hard-nets use hard-bits. A soft-net
learns 1-bit weights by representing them, at training time,
as real numbers. The equivalent hard-net, at inference time,
simply uses 1-bit weights. A soft-net is any differentiable, ordifferentiable a.e., function, f , that ‘hardens’ to a hard-net
that is a semantically equivalent discrete function, g.

Specifically, ∂B nets have two aspects: a soft-net, which isa differentiable function with real weights, and a hard-net,
which is a discrete function with boolean weights. Bothaspects are semantically equivalent. We train the soft-net as
normal, using backpropagation, then ‘harden’ the learned
weights to boolean values, which bind with the hard-net
to yield a discrete function with identical predictive performance (see Figure 1).

Definition 2.3 (Hard-equivalence). A function, f :[0, 1]n → [0, 1]m , is hard-equivalent to a discrete function,g : {1, 0}n → {1, 0}m , if harden(f (x)) = g(harden(x))
for all x ∈ {(x1 , . . . , xn ) | xi ∈ [0, 1] \ {1/2}}. For shorthand write f ▶ g.

1
GitHub, Oxford, UK. Correspondence to: Ian Wright<wrighti@acm.org>.

∂B nets are composed from ‘activation’ functions that are
hard-equivalent to boolean functions (and natural generalisations).

Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

12.1. Learning to negate
Say we aim to learn to negate a boolean value, x, or leave it
unaltered. Represent this decision by a boolean weight, w,
where low w means negate and high w means do not. The
boolean function that meets this requirement is ¬(x ⊕ w).
However, this function is not differentiable. Define thedifferentiable function, ∂¬ (w, x) = 1 − w + x(2w − 1),
where ∂¬ (w, x) ▶ ¬(x ⊕ w) (see proposition F.1).
Many kinds of differentiable fuzzy logic operators exist(see van Krieken et al. (2022) for a review). So why thisfunctional form? Product logics, where f (x, y) = xy is asa soft version of x ∧ y, although hard-equivalent at extreme
values, e.g. f (1, 1) = 1 and f (0, 1) = 0, are not hardequivalent at intermediate values, e.g. f (0.6, 0.6) = 0.36,
which hardens to False not True. Gödel-style min and max
functions, although hard-equivalent over the entire soft-bit
range, i.e. min(x, y) ▶ x ∧ y and max(x, y) ▶ x ∨ y, aregradient-sparse in the sense that their outputs do not always∂
vary when any input changes, e.g. ∂xmax(x, y) = 0 when(x, y) = (0.1, 0.9). So although the composite function
max(min(w, x), min(1 − w, 1 − x)) is differentiable and▶ ¬(x ⊕ w) it does not always backpropagate error to its
inputs. In contrast, ∂¬ always backpropagates error to its
inputs because it is a gradient-rich function (see Figure 3).

Figure 2. Margin packing for constructing gradient-rich, hardequivalent functions. A representative bit, z, is hard-equivalent to adiscrete target function but gradient-sparse (e.g. z = min(x, y) ▶
x ∧ y). On the left z is low, z < 1/2; on the right z is high,z > 1/2. We can pack a fraction of the margin between z andthe hard threshold 1/2 with additional gradient-rich information
without affecting hard-equivalence. A natural choice is the mean
soft-bit, x̄ ∈ [0, 1]. The grey shaded areas denote the packed
margins and the final augmented bit. On the left ≈ 60% of themargin is packed; on the right ≈ 90%.

is just such a gradient-rich fraction. We therefore define
margin-fraction(x, i) = x̄ × |xi − 1/2|. The packed fraction, x̄, of the margin increases or decreases with the averagesoft-bit value. The available margin, |xi − 1/2|, tends tozero as the representative bit, xi , tends to the hard threshold
1/2. At the threshold point there is no margin to pack. Now,
define the augmented bit as

Definition 2.4 (Gradient-rich). A function, f : [0, 1]n ↛= 0 for all x ∈[0, 1]m , is gradient-rich if ∂f∂x(x)i{(x1 , . . . , xn ) | xi ∈ [0, 1] \ {1/2}}.

augmented-bit(x, i) =(1/2 + margin-fraction(x, i)
xi + margin-fraction(x, i)∂B nets are composed of hard-equivalent ‘activation’ functions that are, where possible, gradient-rich. To meet thisrequirement we introduce the technique of margin packing.

if xi > 1/2
otherwise,(1)

which is differentiable a.e. Note that if the representative bit
is high (resp. low) then the augmented bit is also high (resp.
low). The difference between the augmented and representative bit depends on the size of the available margin and themean soft-bit value. Almost everywhere, an increase (resp.
decrease) of the mean soft-bit increases (resp. decreases)
the value of the augmented bit (see Figure 2). Note that
if the ith bit is representative (i.e. hard-equivalent to thetarget function) then so is the augmented bit (see lemma
F.2). We use margin packing, where appropriate, to define
gradient-rich, hard-equivalents of boolean functions.

2.2. Margin packing
Say we aim to construct a differentiable analogue of x ∧ y.
Note that min(x, y) essentially selects one of x or y as arepresentative soft-bit that is guaranteed hard-equivalent tox ∧ y. However, by selecting only one of x or y then min isalso guaranteed to be gradient-sparse. We define a ‘margin
packing’ method to solve this dilemma.
The main idea of margin packing is (i) select a representative bit that is hard-equivalent to the target discrete function,and then (ii) pack a fraction of the margin between the
representative bit and the hard threshold 1/2 with gradientrich information. The result is an augmented bit that is afunction of all inputs yet hard-equivalent to the target function. More concretely, say a vector of soft-bit inputs x has
an ith element that represents the target discrete function(e.g. if our target is x ∧ y then x = [x, y] and i is 1 if
x < y and i = 2 otherwise). Now, if we pack only a fraction of the available margin, |xi − 1/2|, we will not crossthe 1/2 threshold and break the hard-equivalence of therepresentative bit. The average soft-bit value, x̄ ∈ [0, 1],

2.3. Differentiable ∧, ∨ and ⇒We aim toVconstruct a differentiable analogue of the booleannfunction i=1 xi . A representative bit is min(x1 , . . . , xn ).
The function ∂∧ (x) = augmented-bit(x, argminiVx[i]) isntherefore hard-equivalent to the boolean function i=1 xi(see proposition F.3). In the special case n = 2 we
get the piecewise function, ∂∧(x, y) = 1/2 + 1/2(x +y)(min(x, y) − 1/2) if min(x, y) > 1/2, and ∂∧(x, y) =min(x, y) + 1/2(x + y)(1/2 − min(x, y)) otherwise. Note2

Figure 3. Gradient-rich versus gradient-sparse differentiable boolean functions. Each column contains contour plots of functions f (x, y)that are hard-equivalent to a boolean function (one of ¬(x ⊕ y), x ∧ y, x ∨ y, or x ⇒ y). Every function is continuous and differentiable
a.e. (white lines indicate non-continuous derivatives). The upper plots are gradient-sparse, where vertical and horizontal contours indicate
the function is constant with respect to one of its inputs, i.e. ∂f /∂y = 0 or ∂f /∂x = 0. The lower plots are gradient-rich, where thecurved contours indicate the function always varies with respect to any of its inputs, i.e. ∂f /∂y ̸= 0 and ∂f /∂x ̸= 0. ∂B nets use
gradient-rich functions to ensure that error is always backpropagated to all inputs.

that ∂∧ is differentiable a.e. and gradient-rich (see Figure 3). The differentiable analogue of ∨ is identical to ∧,except the representative bit is selected by max. The function ∂∨ (x) = augmented-bit(x,Wargmaxi x[i]) is hardnequivalent to the boolean function i=1 xi (see proposition
F.4) (see Figure 3). The differentiable analogue of ⇒ (material implication) is defined in terms of ∂∨ . The function∂⇒ (x, y) = ∂∨(y, 1 − x), is hard-equivalent to x ⇒ y (seeproposition F.5). We can define analogues of all the basic
boolean operators in a similar manner.

order. Then the ‘median’ soft-bit, majority-index(x) =Applying margin pack⌈ |x|
2 ⌉, is representative.
ing, define the differentiable function ∂Maj(x) =augmented-bit(sort(x), majority-index(x)), which is
hard-equivalent to Maj (see theorem F.7). Note that ∂Maj
is differentiable a.e. and gradient-rich (see Figure 4). If sortis quicksort then the average time-complexity of ∂Maj isO(n log n), which makes ∂Maj more expensive than ∂¬ ,∂∧ , ∂∨ and ∂⇒ at training time. The sort operation could
be replaced by the Floyd-Rivest algorithm, which has linear average time complexity (Kiwiel, 2005). However, inthe hard ∂B net we efficiently implement Maj as a discrete
program that simply checks if the majority of bits are high.
Note that we use sort to define a differentiable function thatis exactly equivalent to a discrete function (rather than defining a continuous approximation to sorting, e.g. Cuturi et al.
(2019), Grover et al. (2019) and Petersen et al. (2022b)).

2.4. Differentiable majority
The boolean majority function is particularly important for
tractable learning because it is a threshold function:1
Maj(x) =+2

Pn

i=1 xi − 1/2

n



,

We apply this methodology to construct functions that
harden to other kinds of boolean functions, such as boolean
counting (see Section C). This basic set of functions is sufficient to learn non-trivial relationships from data. ∂B net
layers are compositions of these functions, where composition preserves hard-equivalence (see Sections A and B).

where we count False as 0 and True as 1. We aim to construct a differentiable analogue of Maj.

Maj for n bits in DNF form is a disjunction of nk conjunctive clauses of size k, where k = ⌈n/2⌉. In principle we
can implement a differentiable analogue of Maj in termsof ∂∧ and ∂∨ . However, the number of terms grows exponentially with the variables. No general algorithm exists
to find the minimal representation of Maj for arbitrary n.
Instead, we trade-off time for memory costs. Assume thatthe function sort(x) sorts the elements of x in ascending

3. Learning discrete functions
We briefly illustrate the kind of discrete program that ∂B
nets can learn. Consider the toy problem of predicting
3

Figure 4. Differentiable boolean majority. The boolean majority function for three variables in DNF form is Maj(x, y, z) = (x ∧y) ∨ (x ∧ y) ∨ (y ∧ z). The upper row contains contour plots of f (x, y, z) = min(max(x, y), max(x, z), max(y, z)) for values ofz ∈ {0.2, 0.4, 0.6, 0.8}. f is differentiable and ▶ Maj but gradient-sparse (vertical and horizontal contours indicate constancy withrespect to an input). Also, the number of terms in f grows exponentially with the number of variables. The lower row contains contour
plots of ∂Maj(x, y, z) for the same values of z. ∂Maj is differentiable and ▶ Maj yet gradient-rich (curved contours indicate variability
with respect to any inputs). In addition, the number of terms in ∂Maj is constant with respect to the number of variables.

4. Related work

whether a person wears a t-shirt (label 0) or a coat (label
1) conditional on 5 boolean features (see Table 1).
very-cold

cold

warm

very-warm

outside

label

1
0
0
0
...

0
0
0
0
...

0
0
1
0
...

0
1
0
1
...

0
1
1
0
...

1
1
0
0
...

Binary neural networks, e.g. Courbariaux et al. (2015), reduce real weights and/or activations to binary, saving model
size and inference costs. The binarization step is lossy,
which loses accuracy (Qin et al., 2020). Deep differentiable
logic gate networks (Petersen et al., 2022a) consist of 2input neurons arranged in a fixed topology. Each neuron
learns a differentiable probability distribution over the 16
possible binary functions. Post-training the neurons are
discretized to the most probable binary function. This step
is lossy, which loses accuracy. ∂B nets aim to explore thedesign space of differentiable nets that enable lossless hardening.

Table 1. A toy learning problem

We train the ∂B net described in Figure 55. Once trained
we harden the net to a discrete program (see Section D)
that generates 2 hard-bits, corresponding to each label. The
program symbolically simplifies to:

5. Conclusion

def dbNet(very-cold, cold, warm, very-warm, outside):
return [4 !very-cold + 4 !cold + (3 warm + !warm) + (very-warm + 3 !verywarm) + (outside + 3 !outside) >= 11,(very-cold + 3 !very-cold) + 4 cold + 4 !warm + (3 very-warm + !
very-warm) + 2 (outside + !outside) >= 11]∂B nets are differentiable nets that are hard-equivalent tonon-differentiable, boolean-valued functions. ∂B nets cantherefore learn discrete functions by gradient descent. Ensuring hard-equivalence requires defining new kinds of activation functions and network layers. ‘Margin packing’ is apotentially general technique for constructing differentiable
functions that are hard-equivalent yet gradient-rich. An advantage of ∂B nets is that ‘hardening’ to 1-bit weights has
provably identical accuracy. At inference time ∂B nets arehighly compact and potentially cheap to evaluate. Preliminary experiments demonstrate that ∂B nets achieve comparable performance to existing approaches.

Note that the program linearly weights multiple pieces ofevidence due to the presence of the ∂Maj operator (overkill
for this toy problem). We can read-off that the ∂B net haslearned ‘if not very-cold and not cold and not outside thenwear a t-shirt’; and ‘if cold and not (warm or very-warm)and outside then wear a coat’ etc. Section E compares ∂Bnet performance against other classification algorithms on
standard machine learning problems.
4

Acknowledgements

library and ecosystem for JAX, 2023. URL http://
github.com/google/flax.

GitHub Next sponsored this research. Thanks to Pavel Augustinov, Richard Evans, Johan Rosenkilde, Max Schaefer,
Ganesh Sittampalam, Tamás Szabó, Albert Ziegler and theanonymous referees for helpful discussions and feedback.

Kiwiel, K. C. On Floyd and Rivest’s SELECT algorithm.
Theoretical Computer Science, 347(1):214–238, 2005.
ISSN 0304-3975.
doi:
https://doi.org/10.1016/j.tcs.2005.06.032.
URL
https://www.sciencedirect.com/
science/article/pii/S0304397505004081.

References
Bengio, Y., Léonard, N., and Courville, A. C. Estimatingor propagating gradients through stochastic neurons forconditional computation. CoRR, abs/1308.3432, 2013.
URL http://arxiv.org/abs/1308.3432.

LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradientbased learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. doi:
10.1109/5.726791.

Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary,C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J.,
Wanderman-Milne, S., and Zhang, Q. JAX: composable
transformations of Python+NumPy programs, 2018. URL
http://github.com/google/jax.

Petersen, F., Borgelt, C., Kuehne, H., and Deussen, O. Deep
differentiable logic gate networks. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A.
(eds.), Advances in Neural Information Processing Systems, volume 35, pp. 2006–2018. Curran Associates, Inc.,
2022a. URL https://proceedings.neurips.
cc/paper_files/paper/2022/file/
0d3496dd0cec77a999c98d35003203caPaper-Conference.pdf.

Courbariaux, M., Bengio, Y., and David, J.-P. Binaryconnect: Training deep neural networks with binary weights
during propagations. In Proceedings of the 28th International Conference on Neural Information Processing
Systems - Volume 2, NIPS’15, pp. 3123–3131, Cambridge,
MA, USA, 2015. MIT Press.

Petersen, F., Borgelt, C., Kuehne, H., and Deussen,
O. Monotonic differentiable sorting networks. In International Conference on Learning Representations,2022b. URL https://openreview.net/forum?
id=IcUWShptD7d.

Cuturi, M., Teboul, O., and Vert, J.-P. Differentiable ranking
and sorting using optimal transport. In Wallach, H.,
Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E.,
and Garnett, R. (eds.), Advances in Neural Information
Processing Systems, volume 32. Curran Associates, Inc.,
2019. URL https://proceedings.neurips.
cc/paper_files/paper/2019/file/d8c24ca8f23c562a5600876ca2a550cePaper.pdf.

Qin, H., Gong, R., Liu, X., Bai, X., Song, J., andSebe, N. Binary neural networks: A survey. Pattern
Recognition, 105:107281, 2020. ISSN 0031-3203.
doi:
https://doi.org/10.1016/j.patcog.2020.107281.
https://www.sciencedirect.com/
URL
science/article/pii/S0031320320300856.

Granmo, O.-C.
The binary iris dataset.
GitHubrepository, a. URL https://github.com/cair/
TsetlinMachine.

Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever,I., and Salakhutdinov, R. Dropout: A simple way
to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56):1929–1958,
2014. URL http://jmlr.org/papers/v15/
srivastava14a.html.

Granmo, O.-C.
The noisy XOR dataset.
GitHubrepository, b. URL https://github.com/cair/
TsetlinMachine.
Granmo, O.-C. The Tsetlin machine – a game theoretic
bandit driven approach to optimal pattern recognition
with propositional logic, 2018. URL https://arxiv.
org/abs/1804.01508.

van Krieken, E., Acar, E., and van Harmelen, F. Analyzing differentiable fuzzy logic operators. Artificial
Intelligence, 302:103602, 2022. ISSN 0004-3702.
doi:
https://doi.org/10.1016/j.artint.2021.103602.
URL
https://www.sciencedirect.com/
science/article/pii/S0004370221001533.

Grover, A., Wang, E., Zweig, A., and Ermon, S. Stochastic
optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2019. URL https://openreview.
net/forum?id=H1eSS3CcKX.
Heek, J., Levskaya, A., Oliver, A., Ritter, M., Rondepierre,B., Steiner, A., and van Zee, M. Flax: A neural network5

A. Boolean logic layers
The full variety of ∂B net architectures is to be explored. Here we define basic layers sufficient for the classification
experiments.
A ∂¬ Layer of width n learns to negate up to n different subsets of the elements of its input vector:∂¬ Layer : [0, 1]n×m × [0, 1]m → [0, 1]n×m ,∂¬ (w1,1 , x1 ) . . . ∂¬ (w1,m , xm )


..
..
..
(W, x) 7→ .
.
.
∂¬ (wn,1 , x1 )...

∂¬ (wn,m , xm )where x is a soft-bit input vector, W is a weight matrix and n is the layer width. Similarly, A ∂⇒ Layer of width n learns to‘mask to true or nop’ up to n different subsets of the elements of its input vector:∂⇒ (w1,1 , x1 ) . . . ∂⇒ (w1,m , xm )


..
..
..
∂⇒ Layer(W, x) = .
.
.
.
∂⇒ (wn,1 , x1 )...

∂⇒ (wn,m , xm )A ∂∧ Neuron learns to logically ∧ a subset of its input vector:∂∧ Neuron : [0, 1]n × [0, 1]n → [0, 1],(w, x) 7→ min(∂⇒(w1 , x1 ), . . . , ∂⇒(wn , xn )),where w is a weight vector. Each ∂⇒ (wi , xi ) learns to include or exclude xi from the conjunction depending on weightwi . For example, if wi > 0.5 then xi affects the value of the conjunction since ∂⇒ (wi , xi ) passes-through a soft-bit thatis high if xi is high, and low otherwise; but if wi ≤ 0.5 then xi does not affect the conjunction since ∂⇒ (wi , xi ) always
passes-through a high soft-bit. A ∂∧ Layer of width n learns up to n different conjunctions of subsets of its input (ofwhatever size). A ∂∨ Neuron is defined similarly:∂∨ Neuron : [0, 1]n × [0, 1]n → [0, 1],(w, x) 7→ max(∂∧(w1 , x1 ), . . . , ∂∧(wn , xn )).
Each ∂∧ (wi , xi ) learns to include or exclude xi from the disjunction depending on weight wi . A ∂∨ Layer of width n learns
up to n different disjunctions of subsets of its input (of whatever size).
We can compose ∂¬ , ∂∧ and ∂∨ layers to learn boolean formulae of arbitrary width and depth.

B. Classification layers
In classification problems the final layer of a neural network is typically interpreted as a vector of real-valued logits, one foreach label, where the index of the maximum logit indicates the most probable label. However, we cannot interpret a soft-bit
vector as logits without violating hard-equivalence. In addition, when training ∂B nets, loss functions should be a function of
hardened bits, otherwise gradient descent may non-optimally traverse trajectories that take no account of the hard thresholdat 1/2. For example, consider that an instance is correctly classified by a 1-hot vector with high bit x = 0.51. Updating
the net’s weights to change this value to 0.51 + ϵ will not improve accuracy and may prevent the correct classification of adifferent instance.
For these reasons, ∂B nets have a final ‘hardening’ layer to ensure that loss is a function of hard, not soft, bits:∂harden : [0, 1]n → [0, 1]n ,x 7→ harden(x).
The harden function is not differentiable and therefore ∂harden uses the straight-through estimator (Bengio et al., 2013)
during backpropagation. By restricting the use of the straight-through estimator to final layers we avoid compounding
gradient estimation errors to deeper parts of the network. Note that ∂harden is hard-equivalent to a nop.
6∂B nets can re-use many of the techniques deployed in standard neural networks. For example, for improved generalisation,
we define a ‘boolean’ analogue of the dropout layer (Srivastava et al., 2014):∂dropout : [0, 1]n × [0, 1] → [0, 1]n ,(x, p) 7→ [f (x1 , p), . . . , f (xn , p)],where
f (x, p) =(1 − x,
x,with probability potherwise.

At train time ∂dropout randomly negates soft-bit values with probability p. At test time, and in the hard-net, ∂dropout is a
nop.

C. Differentiable counting
A boolean counting function f (x) is True if a counting predicate, c(x), holds over its n inputs. We aim to construct a
differentiable analogue of count(x, k) where c(x) := |{xi : xi = 1}| = k (i.e. ‘exactly k high’), which can be useful inmulticlass classification problems. Define∂count-hot : [0, 1]n → [0, 1]n+1 ,x 7→ low-high(sort(x)),
where

low-high : [0, 1]n → [0, 1]n+1 ,x 7→ [∂∧(1, x1 ), ∂∧(1 − x1 , x2 ), . . . , ∂∧(1 − xn−1 , xn ), ∂∧(1 − xn , 1)] .

∂count-hot(x) outputs a 1-hot vector where the index of the high bit is the number of low bits in x. Note that ∂count-hot
is differentiable, gradient-rich and hard-equivalent to the boolean function
count-hot : {0, 1}n → {0, 1}n+1 ,x 7→ [k-of-n(x, 0), k-of-n(x, 1), . . . , k-of-n(x, n)] ,where
k-of-n(x, k) =_ ^|S|=k i∈S

xi

^

¬xj

j ∈S
/

(see proposition F.8). However, in the hard ∂B net we efficiently implement count-hot as a discrete program that simply
counts the number of low bits.
We can construct various kinds of boolean counting functions from ∂count-hot. For example, ∂count(x, k) is straightforwardly ∂count-hot(x)[k] where margin-packing ensures that this single soft-bit is gradient-rich.

D. An example of hard-equivalence
The ∂B net specified in Figure 5 (with 40 soft-bit weights) has two single-bit output ports and is hard-equivalent to thefollowing discrete program (with 40 hard-bit weights):
def dbNet(very-cold, cold, warm, very-warm, outside):
return [ge(sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((0, not(xor(ne(very-cold, 0), w1)))), not(xor(ne(cold, 0), w2)))), not(xor(ne(warm, 0), w3)))), not(xor(ne(very-warm, 0), w4)))), not(xor(ne(outside, 0), w5)))),
not(xor(ne(very-cold, 0), w6)))), not(xor(ne(cold, 0), w7)))), not(xor(ne(warm, 0), w8)))), not(xor(ne(very-warm, 0), w9)))), not(xor(ne(outside, 0), w10)))), not(xor(ne(very-cold, 0), w11)))), not(xor(ne(cold, 0), w12)))), not(xor(ne(warm, 0), w13)))), not(xor(ne(very-warm, 0), w14)))), not(xor(ne(outside, 0), w15)))), not(xor(ne(very-cold, 0), w16)))), not(xor(ne(cold, 0), w17)))),
not(xor(ne(warm, 0), w18)))), not(xor(ne(very-warm, 0), w19)))), not(xor(ne(outside, 0), w20)))), 11),ge(sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((sum((0, not(xor(ne(very-cold, 0), w21)))), not(xor(ne(cold, 0), w22)))), not(xor(ne(warm, 0), w23)))), not(xor(ne(very-warm, 0), w24)))), not(xor(ne(outside, 0), w25)))), not(xor(ne(very-cold, 0), w26)))), not(xor(ne(cold, 0), w27)))), not(xor(ne(warm, 0), w28)))), not(xor(ne(very-warm, 0), w29)))), not(xor(ne(outside, 0), w30)))), not(xor(ne(very-cold, 0), w31)))), not(xor(ne(cold, 0), w32)))), not(xor(ne(warm, 0), w33)))), not(xor(ne(very-warm, 0), w34)))), not(xor(ne(outside, 0), w35)))), not(xor(ne(very-cold, 0), w36)))), not(xor(ne(cold, 0),w37)))), not(xor(ne(warm, 0), w38)))), not(xor(ne(very-warm, 0), w39)))), not(xor(ne(outside, 0), w40)))), 11)]7

Figure 5. A ∂B net to illustrate hardening. The net concatenates a ∂¬ Layer (of width 8) with a reshaping layer that outputs two vectors,
which get reduced, by a ∂Maj operator, to 2 soft-bits, one for each class label. A final ∂harden layer ensures the loss is a function of
hard bits. The net’s weights, once hardened, consume 40 bits (5 bytes).

Figure 6. A ∂B net for the binary Iris problem. The net concatenates the soft-bit input, x (length 16), with its negation, 1 − x, andsupplies the resulting vector (length 32) to a ∂∧ Layer (width 59), a ∂dropout layer for improved generalisation, a ∂count-hot layer thatgenerates a 1-hot vector (width 60) that is reduced by max to a 1-hot vector of 3 classification bits. A final ∂harden ensures the loss is afunction of hard bits. The net’s weights, once hardened, consume 236 bytes.

E. Experiments
The ∂B net library is implemented in Flax (Heek et al., 2023) and JAX (Bradbury et al., 2018) and available at github.
com/Z80coder/db-nets. The library supports the specification of a ∂B net as Python code, which automatically defines(i) the soft-net for training (weights are floats), (ii) a hard-net for inference (weights are booleans), and (iii) a symbolic net
for interpretation (weights and inputs are symbols). The symbolic net, when evaluated, interprets its own JAX expression
and outputs a description of the discrete program it computes.
We compare the performance of ∂B nets against standard ML approaches on three problems: the classic Iris dataset, anadversarial noisy XOR problem, and MNIST.
E.1. Binary Iris
The Iris dataset has 150 examples with 4 inputs (sepal length and width, and petal length and width), and 3 labels (setosa,
versicolour, and virginica). We use the binary version of the Iris dataset (Granmo, a) where each input float is represented
by 4 bits. We perform 1000 experiments, each with a different random seed. Each experiment randomly partitions the data
into 80% training and 20% test sets. We initialize the network, described in Figure 6, with all weights wi = 0.3 and train for
8Tsetlin∂Bneural network
SVM
naive Bayesmean
95.0 +/- 0.2
93.9 +/- 0.1
93.8 +/- 0.2
93.6 +/- 0.3
91.6 +/- 0.3

accuracy
5 %ile 95 %ile
86.7
100.0
86.7
100.0
86.7
100.0
86.7
100.0
83.3
96.7

min
80.0
80.0
80.0
76.7
70.0

max
100.0
100.0
100.0
100.0
100.0

Table 2. Binary Iris results measured over 1000 experiments.

Figure 7. A ∂B net for the noisy xor problem. The net concatenates the soft-bit input, x (length 12), with its negation, 1 − x, and supplies
the resulting vector (length 24) to a ∂∧Layer (width 32), ∂∨Layer (width 32), ∂¬ Layer (width 16), and a final ∂Maj to produce a single
soft-bit y ∈ [0, 1] (to predict odd parity) and its negation 1 − y (to predict even parity). The net’s weights, once hardened, consume 288
bytes.

1000 epochs with the RAdam optimizer and softmax cross-entropy loss.
We measure the accuracy of the final net to avoid hand-picking the best configuration. Table 2 compares the δB net against
other classifiers (Granmo, 2018). Naive Bayes performs the worst. The Tsetlin machine performs best on this problem, withthe ∂B net second.
E.2. Noisy XOR
The noisy XOR dataset (Granmo, b) is an adversarial parity problem with noisy non-informative features. The dataset
consists of 10K examples with 12 boolean inputs and a target label (where 0 = odd and 1 = even) that is a XOR functionof 2 of the inputs. The remaining 10 inputs are entirely random. We train on 50% of the data where, additionally, 40%of the labels are inverted. We initialize the network described in Figure 7 with random weights distributed close to thehard threshold at 1/2 (i.e. in the ∂∧ Layer, wi = 0.501 × b + 0.3 × (1 − b) where b ∼ Bernoulli(0.01); in the ∂∨ Layer,
wi = 0.7 × b + 0.499 × (1 − b) where b ∼ Bernoulli(0.99)); and in the ∂¬ Layer, wi ∼ Uniform(0.499, 0.501). We train
for 2000 epochs with the RAdam optimizer and softmax cross-entropy loss.
We measure the accuracy of the final net on the test data to avoid hand-picking the best configuration. Table 3 compares the∂B net against other classifiers (Granmo, 2018). The high noise causes logistic regression and naive Bayes to randomly
guess. The SVM hardly performs better. In contrast, the multilayer neural network, Tsetlin machine, and ∂B net all
successfully learn the underlying XOR signal. The Tsetlin machine performs best on this problem, with the ∂B net second.
E.3. MNISTThe MNIST dataset (LeCun et al., 1998) consists of 60K training and 10K test examples of handwritten digits (0-9). We
binarize the data by replacing pixels with grey value greater than 0.3 with 1, otherwise with 0. We initialize the network
9Tsetlin∂Bneural network
SVM
naive Bayes
logistic regressionmean
99.3 +/- 0.3
97.9 +/- 0.2
95.4 +/- 0.5
58.0 +/- 0.3
49.8 +/- 0.2
49.8 +/- 0.3

accuracy
5 %ile 95 %ile
95.9
100.0
95.4
100.0
90.1
98.6
56.4
59.2
48.3
51.0
47.8
51.1

min
91.6
93.6
88.2
55.4
41.3
41.1

max
100.0
100.0
99.9
66.5
52.7
53.1

Table 3. Noisy XOR results measured over 100 experiments.

Figure 8. A non-convolutional ∂B net for MNIST. The input is a 28 × 28 bit matrix representing an image. The net consists of a ∂⇒ Layer(of width 60, to produce a 2940 × 16 reshaped array), a ∂Maj layer (to produce a vector of size 2940), a ∂¬ Layer (of width 20, to
produce a 20 × 2940 array), and a final ∂harden operator to generate hard-bits split into 10 buckets and summed to produce 10 integer
logits. The net’s weights, once hardened, consume 13.23 kb.

described in Figure 8 with random weights distributed as wi = 0.501 × b + 0.3 × (1 − b) where b ∼ Bernoulli(0.01). We
train for 1000 epochs with a batch size of 6000 using the RAdam optimizer and softmax cross-entropy loss.
We measure the accuracy on the final net. Table 4 compares the ∂B net against other classifiers (reference data taken from
Granmo (2018)). Basic versions of the algorithms (e.g. no convolutional nets) are applied to unenhanced data (e.g. no data
augmentation). The aim is to compare raw performance rather than optimise for MNIST. A 2-layer neural network trainedon grey-value pixel data performs best. A Tsetlin machine of 40,000 automata each with 256 states (and therefore 40 kb ofparameters) trained on binary data achieves ≈ 98.2% accuracy. A ∂B net with 105,840 soft-bit weights that harden to 1-bit
booleans (and therefore 13.23 kb of parameters) trained on binary data achieves ≈ 94.0% accuracy. However, this ∂B net
underfits the training data and we expect better performance from a larger model.

F. Proofs
Proposition F.1. ∂¬ (x, y) ▶ ¬(x ⊕ y).
Proof. Table 5 is the truth table of the boolean function ¬(x ⊕ w), where h(x) = harden(x).
Lemma F.2. If a representative bit, xi , is hard-equivalent to a target function, g, then so is the augmented bit, z.
Proof. As xi is representative then harden(xi ) = g(harden(x)). The augmented bit, z, is given by (1):(
1/2 + x̄ × |xi − 1/2| if xi > 1/2
z=xi + x̄ × |xi − 1/2|
otherwise.
10

accuracy
98.6
98.2 +/- 0.0
97.2
94.0
91.5
88.0
87.8
83.2

2-layer NN, 800 HU, cross-entropy loss
TsetlinK-nearest-neighbours, L3∂B
Logistic regression
Linear classifier (1-layer NN)
Decision tree
Multinomial Naive Bayes

Table 4. MNIST results. A classifier in italics was trained on grey-value pixel data, otherwise the classifier was trained on binarized data.
Note: the ∂B results are from a small model that under-fits the data (due to OOM errors on my GPU). The next draft will include results
using a larger ∂B net.

x

y

h(x)

h(y)

∂¬ (x, y)h(∂¬ (x, y))¬(h(y) ⊕ h(x))


0, 12

1
,1
2
 1
0, 2

1
2, 1

 1
0,
 21 
0, 2

1
2 , 1
1
2, 1

0
1
0
1

0
0
1
1

1
,1
 2 1
0,
 12 
0, 2

1
2, 1

1
0
0
1

1
0
0
1





Table 5. ∂¬ (x, y) ▶ ¬(y ⊕ x).

In consequence,
harden(z) =(10

if x > 1/2
otherwise,

since xi > 1/2 ⇒ z > 1/2 and xi ≤ 1/2 ⇒ z ≤ 1/2. Hence, harden(z) = harden(xi ) = g(harden(x))
Proposition F.3. ∂∧(x, y) ▶ x ∧ y.
Proof. Table 6 is the truth table of the boolean function x ∧ y, where h(x) = harden(x)..
x

y

h(x)

h(y)

∂∧ (x, y)h(∂∧ (x, y))h(x) ∧ h(y)


0, 12

1
,1
 2 1
0, 2

1
2, 1

 1
0,
 12 
0, 2

1
2 , 1
1
2, 1

0
1
0
1

0
0
1
1




0, 21

1 1
4, 2
1 1
4 , 2
1
2, 1

0
0
0
1

0
0
0
1



Table 6. ∂∧ (x, y) ▶ x ∧ y.

Proposition F.4. ∂∨(x, y) ▶ x ∨ y.
Proof. Table 7 is the truth table of the boolean function x ∨ y, where h(x) = harden(x)..
Proposition F.5. ∂⇒(x, y) ▶ x ⇒ y.
Proof. Table 8 is the truth table of the boolean function x ⇒ y, where h(x) = harden(x)..
Lemma F.6. Let i = majority-index(x), then the ith element of sort(x) is hard-equivalent to boolean majority, i.e.
harden(sort(x)[i]) = Maj(harden(x)).
11

x

y

h(x)

h(y)

∂∨ (x, y)h(∂∨ (x, y))h(x) ∨ h(y)


0, 12

1
,1
2
 1
0, 2

1
2, 1

 1
0,
 12 
0, 2

1
2 , 1
1
2, 1

0
1
0
1

0
0
1
1




0, 21

1
2 , 1
1
2 , 1
1
2, 1

0
1
1
1

0
1
1
1



Table 7. ∂∨ (x, y) ▶ x ∨ y.

x

y

h(x)

h(y)

∂⇒ (x, y)h(∂⇒ (x, y))h(x) ⇒ h(y)


0, 12

1
,1
2
 1
0, 2

1
2, 1

 1
0,
 21 
0, 2

1
2 , 1
1
2, 1

0
1
0
1

0
0
1
1

1
,1
 2 1
0, 2

1
2 , 1
1 7
2, 8

1
0
1
1

0
0
0
0





Table 8. ∂⇒ (x, y) ▶ x ⇒ y.

Proof. Let h denote the number of bits that are high in x = [x1 , . . . , xn ]. Then indices {j : n − h + 1 ≤ j ≤ n} are high insort(x). If the majority of bits are high, h ≥ ⌊n/2 + 1⌋, then index j = n − ⌊n/2 + 1⌋ + 1 = n − ⌊n/2⌋ = ⌈n/2⌉ is high insort(x). majority-index selects index i = ⌈n/2⌉ and therefore i = j. Hence, if the majority of bits are high then sort(x)[i]
is high. Similarly, if the majority of bits are low, h < ⌊n/2 + 1⌋, then index j = n − ⌊n/2 + 1⌋ + 1 = n − ⌊n/2⌋ = ⌈n/2⌉
is low in sort(x). Hence, if the majority of bits are low then sort(x)[i] is low.
 


1
= 1, and h < ⌊n/2 + 1⌋
Note that h ≥ ⌊n/2 + 1⌋ implies that Maj(harden(x))≥ 21 + n1 n2 + 1 − 12 ≥ 1 + 2n1
= 0.
implies that Maj(harden(x)) < 1 + 2n
In consequence, harden(sort(x)[i]) = Maj(harden(x)) for all h ∈ [0, . . . , n].

Theorem F.7. ∂Maj ▶ Maj.
Proof. ∂Maj augments the representative bit xi = sort(x)[majority-index(x)]. By lemma F.6 the representative
bit is ▶ Maj(harden(x)). By lemma F.2, the augmented bit, augmented-bit(sort(x), majority-index(x)), is also
▶ Maj(harden(x)). Hence ∂Maj ▶ Maj.
Proposition F.8. ∂count-hot ▶ count-hot.
Proof. Let l denote the number of bits that are low in x = [x1 , . . . , xn ], and let y = ∂count-hot(x). Then y[l + 1] is highand any y[i], where i ̸= l + 1, is low. Let z = count-hot(harden(x)). Then z[l + 1] is high and any z[i], where i ̸= l + 1,
is low. Hence, harden(y) = z, and therefore ∂count-hot ▶ count-hot.

12