Two-Stage Unit Tying for Simplifying Differentiable Logic Gate Networks

Seungheon Lee, Jeongmin Sun, Jaeyong ChungICML 2026 · OpenReview

Differentiable logic gate networks (DLGNs) represent an exciting frontier in AI hardware. Unlike traditional neural networks that rely on heavy floating-point arithmetic, DLGNs learn to perform inference using simple Boolean logic gates (AND, OR, XOR). This unique architecture allows them to be mapped directly onto Field-Programmable Gate Arrays (FPGAs) or Application-Specific Integrated Circuits (ASICs) for ultra-low-latency, real-time applications.

However, deploying these networks often encounters a major hurdle: the FPGA feasibility gap. A trained logic network frequently requires more Look-Up Tables (LUTs)—the fundamental building blocks of FPGAs—than the target hardware provides. To tightly fit a trained model to a target FPGA, engineers need a post-training mechanism to trade off network complexity and accuracy, analogous to pruning in standard neural networks.

The Challenge of Discrete Logic

Standard neural network pruning, which involves removing continuous weights, does not translate well to logic networks because logic is inherently discrete. In a DLGN, changing a single gate's function is not a "small perturbation"; it is a structural shift that can wildly alter the network's output.

Because the weight gap required to change a gate's function is orders of magnitude larger than in standard architectures like ResNets, "local" mathematical approximations used in standard pruning are unreliable. Consequently, traditional Taylor-expansion-based pruning criteria often fail to predict which gates are safe to remove.

Methodology: Two-Stage Unit Tying

To overcome this, researchers introduce Unit Tying, a post-training simplification technique. Instead of deleting a connection, the method forces a selected gate’s output to a constant 0 or 1. This triggers "constant propagation" during hardware synthesis: tying one gate to '0' might force an entire downstream AND gate to always output '0', allowing the compiler to automatically delete entire chains of downstream logic.

Because naively extending pruning criteria to logic networks is unreliable, the authors propose a robust two-stage algorithm to decide which units to tie:

  1. Stage-A (Gauss-Newton Screening): A fast, second-order screening step that uses a "teacher-referenced logit-distortion" objective. It attempts to keep the simplified network's output as close as possible to the original trained "teacher" network. By utilizing Jacobian-vector products, the algorithm efficiently scores thousands of candidate gates without the massive computational cost of calculating a full Hessian matrix.
  2. Stage-B (Binary Split Refinement): Because screening ignores how gates interact with one another, it is not perfectly accurate. This second stage takes an "overshoot set" of high-recall candidates from Stage-A and employs a search strategy inspired by group testing. It partitions candidates into groups and evaluates them via finite-difference (running data through the modified network) to isolate and correct approximation and interaction-driven errors.

Key Insights

  • MSE Outperforms KL Divergence: For logic networks, minimizing the Mean Squared Error (MSE) between the teacher and student logits proved more effective and less sensitive to hyperparameters than the Kullback–Leibler (KL) divergence typically used in knowledge distillation.
  • Hardware-Awareness is Crucial: "Gate count" in software does not strictly equate to "LUT count" in hardware. The proposed method focuses on post-synthesis results, which ultimately determine if a model fits on a physical chip.

Experimental Results

The two-stage unit tying method was evaluated on standard computer vision benchmarks (MNIST and CIFAR-10) using "Small" and "Medium" variants of LogicTreeNet architectures. The results demonstrate a substantial improvement in the accuracy-versus-area trade-off over common saliency baselines:

  • Area Reduction: On CIFAR-10, the method achieved up to a 48.3% reduction in post-synthesis LUT usage at a 50% tied ratio. On MNIST, the reduction reached 42.9%.
  • Hardware Feasibility: In a striking practical example, a model that originally required a high-end $22,000 FPGA** (Virtex-7 2000T) was compressed enough to fit onto a budget-friendly **$2,200 FPGA (Kintex-7 410T) while maintaining usable accuracy.
  • Accuracy Retention: With post-tying fine-tuning, accuracy degradation was remarkably modest. For MNIST, tying 50% of the units resulted in an accuracy loss of only 0.35%.

Limitations and Future Directions

While highly effective, the approach has a few limitations that pave the way for future research:

  • Layer-wise Greediness: The current algorithm processes the network layer-by-layer. A global optimization approach might discover even better tying configurations across the entire depth of the network.
  • Calibration Data: The refinement stage requires a small amount of calibration data. Although it is robust with as few as 80 samples, it introduces an additional step to the deployment pipeline.
  • Search Complexity: While the Binary Split is faster than an exhaustive search, the "overshoot" parameter presents a trade-off between optimization time and final model quality. Future iterations could automate the selection of this parameter to streamline the process.

Summary updated

Abstract

Differentiable logic gate networks map directly to gate-level circuits, enabling ultra-low-latency inference, yet their logic footprint often exceeds FPGA capacity budgets. Tightly fitting a trained model to a target FPGA requires a post-training mechanism to trade off network complexity and accuracy—analogous to pruning in standard neural networks. To this end, we introduce *unit tying*: a simplification that forces selected gates to constants (0 or 1), enabling constant propagation and downstream logic elimination. However, we observe that naively extending pruning criteria to logic networks is unreliable under such near-discrete modifications. We therefore propose a two-stage algorithm for unit tying: (i) a fast Gauss–Newton screening step under a teacher-referenced logit-distortion objective that constructs a high-recall overshoot set and (ii) a refinement step that corrects approximation and interaction-driven errors using a small number of finite-difference evaluations. On CIFAR-10 and MNIST, our method consistently improves the accuracy–area trade-off over common saliency baselines, yielding substantial post-synthesis LUT reductions of up to 48% on CIFAR-10 and 43% on MNIST, with modest accuracy degradation.
BibTeX
@inproceedings{lee2026two,
  author = {Seungheon Lee and Jeongmin Sun and Jaeyong Chung},
  title = {{Two-Stage Unit Tying for Simplifying Differentiable Logic Gate Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=QVt9dgerpS},
}
Figure