# Fitting Multilinear Polynomials for Logic Gate Networks

arXiv: https://arxiv.org/abs/2605.08657 · HTML: https://mlsanity.com/paper/2605.08657/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 9 May 2026.

## Builds on (most cited first, 15 of 15)

- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Soft-to-Hard Vector Quantization for End-to-End Learning Compressible Representations](https://mlsanity.com/paper/1704.00648/) (2017)
- [Analyzing Differentiable Fuzzy Logic Operators](https://mlsanity.com/paper/2002.06100/) (2020)
- [Straightening Out the Straight-Through Estimator: Overcoming Optimization Challenges in Vector Quantized Networks](https://mlsanity.com/paper/2305.08842/) (2023)
- [Deep Differentiable Logic Gate Networks](https://mlsanity.com/paper/2210.08277/) (2022)
- [Convolutional Differentiable Logic Gate Networks](https://mlsanity.com/paper/2411.04732/) (2024)
- [PolyLUT: Learning Piecewise Polynomials for Ultra-Low Latency FPGA LUT-based Inference](https://mlsanity.com/paper/2309.02334/) (2023)
- [Differentiable Weightless Neural Networks](https://mlsanity.com/paper/2410.11112/) (2024)
- [Light Differentiable Logic Gate Networks](https://mlsanity.com/paper/2510.03250/) (2025)
- [Towards Narrowing the Generalization Gap in Deep Boolean Networks](https://mlsanity.com/paper/2409.05905/) (2024)
- [Align Forward, Adapt Backward: Closing the Discretization Gap in Logic Gate Networks](https://mlsanity.com/paper/2603.14157/) (2026)

## Abstract (arXiv)

We study learnable logic gate networks that stack layers of 2-input Boolean gates to build combinational circuits. Every 2-input gate has a unique multilinear polynomial with 4 coefficients, so the 16 Boolean gates form a codebook of prototypes in a 4-dimensional space, reducing training to a vector-quantization problem. The baseline method, Soft-Mix, learns a 16-dimensional softmax over gate identities, but the codebook has rank~4: 11 of 15 simplex directions carry nullspace gradient, and at uniform initialization the backward signal vanishes exactly. We prove that no affine product reparameterization fixes the resulting interaction-coefficient starvation under STE, and show that the covariance Jacobian of soft-VQ selection bypasses it by coupling the starved coefficient to the always-active constant channel. Working in the 4-dimensional polynomial space reduces each neuron from 16 to 4 parameters. On seven datasets, at least one 4-parameter method matches or exceeds Soft-Mix on every dataset; the CovJac advantage over STE grows monotonically with interaction demand across all seven datasets. At depth, Soft-Mix collapses (-37.3pp on CIFAR-10 at 12 layers) while CovJac holds (-0.5pp on CIFAR-10, stable on MNIST).