Technical Summary: Learning Compact Boolean Networks

Problem Statement

Floating-point neural networks dominate modern machine learning but incur substantial inference costs, limiting their deployment in resource-constrained environments like edge devices and IoT. While Boolean networks offer a promising alternative by operating directly on Boolean values (0 and 1) to achieve nanosecond-scale latency and lower power consumption, learning networks that are both compact and accurate remains a significant challenge.

Existing approaches face three primary bottlenecks:

1. Inefficient Connection Learning: Current methods either use randomly fixed connections (which are ineffective due to the ultra-sparsity of Boolean networks) or rely on parameterizing connections with large weight matrices, inducing significant training overhead (often quadratic in the number of neurons).
2. Expensive Convolutional Architectures: The only existing convolutional Boolean architecture utilizes hardcoded tree-like kernels. These structures require an exponential number of Boolean operations relative to their depth, resulting in high inference costs compared to feedforward layers.
3. Discretization Gap: The standard training paradigm involves relaxing a Boolean network into a differentiable representation, training it, and then discretizing it back. The discrepancy between the continuous relaxation and the discrete network causes a systematic accuracy drop upon discretization.

Methodology

The authors propose a unified framework to address these challenges through three complementary components:

1. Parameter-Free Connection Learning

Instead of fixing connections or using heavy weight matrices, the authors introduce a strategy that learns effective sparse connectivity without additional parameters.

• Mechanism: Each neuron is parameterized as a weighted aggregation of 16 possible Boolean operations, where each operation is assigned a specific pair of input neurons from the previous layer.
• Adaptive Resampling: To explore better input-function combinations, the method monitors the "stability" of a neuron via weight entropy. When a neuron's weight distribution converges (indicating it has settled on a specific triple of inputs and operation), the system adaptively resamples the candidate inputs for that neuron to explore new configurations. This allows the network to learn meaningful patterns without the memory overhead of large connection matrices.

2. Compact Convolutional Architecture

The paper replaces the tree-based kernels used in prior work (e.g., TreeLogicNet) with single-operation Boolean kernels.

• Mechanism: Leveraging the connection-learning strategy, a single Boolean operation kernel can aggregate information from multiple input pairs during training. This allows a kernel to effectively observe up to 32 distinct inputs from the receptive field, despite performing only one Boolean operation.
• Advantage: This approach eliminates the exponential growth of operations associated with tree depths and removes sequential dependencies, enabling higher parallelism and significantly smaller network sizes.

3. Adaptive Discretization

To mitigate the accuracy drop caused by the gap between continuous relaxation and discrete execution, the authors propose a progressive discretization strategy.

• Mechanism: The method monitors the convergence of each layer (using average weight entropy). Once a layer (particularly convolutional layers, which converge faster) stabilizes, it is immediately discretized and frozen. Training then continues on the remaining relaxed layers.
• Benefit: This progressive approach forces subsequent layers to adapt to Boolean inputs during training, narrowing the discretization gap and improving the final discrete model's performance without the computational overhead of noise injection methods.

Key Results

The proposed method was evaluated on standard vision benchmarks (MNIST, CIFAR-10) and other modalities (tabular, sequence data), as well as via FPGA synthesis.

• Accuracy vs. Complexity: The method improves the Pareto frontier over state-of-the-art methods. On CIFAR-10, it achieves higher accuracy with up to 47× fewer Boolean operations compared to prior methods.
• MNIST Performance: The model achieves 99.38% accuracy with 6.48 ns latency on an FPGA (Xilinx ZCU104). This surpasses previous state-of-the-art in both accuracy and runtime while generating a 7× smaller circuit.
• Convolutional Efficiency: On CIFAR-10, the authors' large model (Ours-L) achieves 72.56% accuracy with 3× fewer neurons and Boolean operations than the TreeLogicNet large model.
• Generalization: The approach demonstrates consistent improvements on TINYIMAGENET, Breast Cancer classification (tabular data), and ECG classification (sequence data), proving its generality across data modalities.
• Hardware Efficiency: FPGA synthesis results confirm that the reduced Boolean operation count translates directly to lower post-synthesis circuit sizes (MB) and faster inference times (ns).

Significance and Claims

The paper claims to present a unified approach for learning compact and accurate Boolean networks that effectively addresses the three main bottlenecks of existing methods.

• Efficiency: By learning sparse connections without parameter matrices and replacing tree kernels with single-operation kernels, the method drastically reduces the computational and memory footprint required for training and inference.
• Practicality: The adaptive discretization strategy provides a practical solution to the discretization gap without requiring complex hyperparameter tuning or noise injection, making the training of discrete networks more robust.
• Deployment: The results on FPGA demonstrate that these theoretical improvements translate into tangible hardware benefits, enabling high-accuracy, low-latency inference on resource-constrained edge devices.

The authors position this work as a step toward making machine learning more accessible and environmentally sustainable for edge deployment, while acknowledging that the training process still relies on floating-point computations and that future work could explore logic synthesis-aware training and input encoding schemes.