Differentiable Logic Synthesis: Spectral Coefficient Selection via Sinkhorn-Constrained Composition

AI summary

Overview

• Research area: Machine learning / neurosymbolic AI, specifically differentiable logic synthesis grounded in Boolean Fourier analysis.
• Technical level: Advanced. The paper assumes familiarity with Fourier analysis of Boolean functions, doubly stochastic matrices, the Birkhoff polytope, Sinkhorn-Knopp normalization, and gradient-based optimization with Gumbel-softmax relaxation.
• Scope in one sentence: The paper introduces "Hierarchical Spectral Composition," a transparent-by-design architecture that selects coefficients from a frozen Boolean Fourier basis and composes them through Sinkhorn-constrained routing with learned sign flips, validated across five experimental phases from n = 2 to n = 28.

What This Paper Is About

Neural networks approximate Boolean logic with "fuzzy" continuous boundaries that degrade when quantized for deployment, and existing neurosymbolic approaches either require heavy supervision, use relaxations that resist discretization, or fail to generalize. This paper instead freezes the classical Boolean Fourier (Walsh-Hadamard) basis as a dictionary of interpretable primitives and learns which coefficients to select and how to compose them, so that the final model is exactly ternary and human-readable. The goal is to show that continuous optimization can reliably land on exact discrete logic while producing representations that are explainable by construction.

Key Contributions

1. Adaptation of Manifold-Constrained Hyper-Connections (mHC) to logic synthesis. The paper takes the Birkhoff polytope projection (via Sinkhorn-Knopp iterations), originally developed for LLM training stability, and applies it to Boolean logic composition.
2. Column-sign modulation for negation. Doubly stochastic routing can only produce convex combinations of inputs and therefore cannot express Boolean negation; the authors factor the routing matrix as R = P · s[None, :] with learned sign parameters s ∈ {-1, +1}^n, adding only one bit of polarity control per output channel.
3. Sign-only diagnostic validation. Fixing routing to the identity (P = I) and learning only the signs achieves 100% accuracy, proving the column-sign mechanism works independently of Sinkhorn optimization.
4. Multi-scale and scalability validation. 100% accuracy on all 16 two-variable operations (n = 2, 10/10 seeds), on 10 operations at n = 3 (5/5 seeds, 39% sparsity), and 10 operations at n = 4 (5/5 seeds, 36% sparsity), plus exact fast Walsh-Hadamard transforms at 1.64B coefficients/sec up to n = 28.
5. Oracle learning and symbolic knowledge integration. Five coefficient estimation methods are compared at n = 16, showing that encoding known structural properties as hard spectral constraints outperforms generic black-box learning.
6. Hardware-efficient compilation. Ternary masks yield 10,959 MOps/s on GPU, described as approaching the efficiency of hand-coded RTL.

Main Findings

• All 16 two-variable operations solved exactly (n = 2): Learned ternary masks match theoretical predictions from Boolean Fourier analysis, with 100% accuracy, zero routing drift, and zero-loss quantization across 10/10 seeds.
• XOR is the hardest base operation: The parity character required roughly 3,000 steps to emerge, while AND, OR, and IMPLIES converged in under 500 steps (~500 for IMPLIES) due to their affine structure. Sequential training (XOR → AND → OR → IMPLIES, 5,000 steps each) was adopted because simultaneous training caused gradient interference.
• Column-sign modulation is what enables negation: Removing it ("No Sign Mod., mHC-style") caps accuracy at exactly 75% (12/16 operations, 0/10 seeds above 99%), confirming Proposition 4 that NAND, NOR, XNOR, and negated constants lie outside the convex hull of doubly stochastic combinations.
• Identity initialization matters: Random initialization converged in only 3/10 seeds with high routing drift (‖P − I‖_F = 0.8234) and 87.50% accuracy, consistent with mHC's finding that identity initialization is critical.
• Sinkhorn constraints are necessary for clean quantization: Unconstrained routing reached 93.75% soft accuracy but suffered 18.75% quantization loss, and an MLP baseline reached 100% soft accuracy but 43.75% quantization loss.
• Sign-only ablation matches the full method: Both "Ours (Full)" and "Sign-Only (P = I)" achieved 100.00% accuracy, 0.0000 routing drift, and 0.00% quantization drop across 10 seeds — isolating gradient coordination, not mechanism expressivity, as the joint-optimization challenge.
• Routing expressibility boundary at n = 2: The 4-dimensional Fourier basis represents all 16 two-variable operations with ternary masks, but Sinkhorn routing with column-sign modulation only works for the 8 "linear" operations; the 8 nonlinear operations (e.g., IF_a_THEN_XOR_ELSE_AND, MAJORITY(XOR, AND, OR)) require direct mask learning or an expanded primitive set.
• Sparsity structure: Linear operations showed 18.8% sparsity, nonlinear operations 43.8%, and 31.2% overall. At n = 3 the reported sparsity was 39% and at n = 4 it was 36%.
• Scalability: Exact Walsh-Hadamard transforms reached n ≤ 28 with 268M coefficients at 1.64B coefficients/sec, and hierarchical composition is reported for 64-bit adders.
• Symbolic structure beats black-box learning at n = 16: Exploiting symmetry constraints raised majority accuracy from 72% (Monte Carlo) to 86% (Goldreich-Levin + Symmetry), a +38% gain with p < 0.001; Birkhoff projection aided routing but did not help coefficient denoising.
• One validation check fails: The orthogonality test (target < 0.3 cosine similarity) is not met — maximum cosine similarity is 0.5, which the paper attributes to XOR's parity character appearing with opposite sign in AND and the same sign in OR, and states this does not affect accuracy.
• Tiny memory footprint at n = 2: 16 operations × 4 trits = 64 trits ≈ 102 bits.

Methodology in Plain English

Instead of asking a neural network to invent logic gates from scratch, the authors hand the network a fixed, mathematically complete dictionary: the Fourier characters of Boolean variables (for two inputs, the features 1, a, b, ab). Each dictionary entry has a clear meaning — it measures the correlation between the target function and the parity of a particular set of variables.

The network then learns two things. First, it picks a small set of these coefficients, keeping weights exactly at {-1, 0, +1} so the result is a sparse, readable polynomial. To make that selection trainable, each weight is parameterized as a three-way categorical distribution over {-1, 0, +1} and relaxed with Gumbel-softmax, with temperature annealed from 1.0 to 0.01, plus L1 regularization, plateau-driven micro-restarts, and a ternary attractor penalty λ Σ |w_i|(1 − |w_i|) that is zero exactly at ternary values.

Second, the network learns how to compose primitive operations into bigger ones. Composition is expressed as a routing matrix, and that matrix is pushed onto the Birkhoff polytope (doubly stochastic matrices) using Sinkhorn-Knopp iterations, following mHC. Because doubly stochastic matrices cannot express negation, each output channel also gets a learned sign, annealed via tanh(β·σ) with β from 1 to 10. Routing is initialized near the identity to avoid gradient interference. At inference, everything is discretized — routing becomes a hard k = 1 argmax assignment, signs become sign(σ) — producing exactly ternary composite masks.

The paper uses a three-stage ablation protocol (sign-only vs. full method vs. random initialization) to separate architectural expressivity from optimization dynamics, and a five-test validation suite covering spectral spike energy, mask sparsity, mask orthogonality, operation accuracy, and binary-valued inference. Experiments used JAX with Optax: Adam at learning rate 10^-2 with λ = 0.01 for Phase 1, and Adam at 10^-3 with 20 Sinkhorn iterations and identity bias γ = 2.0 for later phases.

Why This Matters

Impact on research. The paper reframes logic learning as coefficient selection from a frozen, provably complete basis rather than architecture discovery, and it provides a concrete expressivity proof (doubly stochastic routing cannot represent negation) plus a convergence argument for zero-loss quantization. It situates itself as complementary to convolutional differentiable logic gate networks — those enumerate gates, this work operates in the mathematically dual Fourier space — and it argues that explicit spectral coefficient selection may sidestep known hardness results for learning fixed parities with gradient descent. It also connects to a broader "transparent-by-design" thread of work by making each learned parameter semantically defined rather than post-hoc interpreted.

Real-world applications.

• Edge inference for combinatorial logic: Ternary masks compile to combinational logic blocks requiring no floating-point arithmetic, no multipliers, and minimal memory, targeting single-cycle GPU inference at 10,959 MOps/s.
• Verifiable learned logic: Because the learned functions are sparse ternary polynomials, they can be checked by formal methods or exhaustive testing, unlike black-box neural approximations — relevant wherever learned behavior must be audited.
• Arithmetic circuit construction: The paper reports hierarchical composition for 64-bit adders, a building block for learned or hybrid arithmetic hardware.
• Function property estimation: The n = 16 oracle learning experiments address estimating structural properties of Boolean functions (parity, majority, comparators) under multiple coefficient estimation methods.

Industry relevance. The paper's author affiliation (Lehigh University and Johnson and Johnson) and the framing around quantization robustness and edge deployment point to settings where models must survive precision reduction and be explainable — hardware compilation, safety-critical inference, and any pipeline that needs discrete, inspectable logic rather than soft approximations.

Future Directions

• Closing the routing expressibility gap. Eight nonlinear two-variable operations have valid ternary masks but cannot be reached by Sinkhorn routing with sign modulation; the paper explicitly points to direct mask learning or expanding the primitive set as the way forward.
• Separating routing benefits from denoising benefits. The n = 16 results show Birkhoff projection aids routing but not coefficient denoising, leaving open how routing constraints and coefficient estimation should be combined at scale.
• Building on the symbolic-constraint result. If encoding symmetry and degree bounds as hard spectral constraints produced both higher accuracy and greater interpretability, an open question is which other function properties can be encoded this way and how far that advantage extends across function families beyond parity, majority, and comparators.
• Scaling composition further. The paper validates exact Walsh-Hadamard transforms to n = 28 and mentions hierarchical composition for 64-bit adders, raising the question of how far hierarchical composition can be pushed toward practical circuit-scale synthesis. (The truncated text ends mid-sentence in Theorem 1, so the full set of theoretical results and any additional planned directions are not reported in the available content.)

Target Audience

Researchers working on neurosymbolic AI, differentiable logic and circuit synthesis, and transparent-by-design architectures; hardware and compilers engineers interested in quantization-robust models that compile to combinational logic; and machine learning practitioners with a background in Boolean Fourier analysis, optimal transport, or constrained optimization who want to understand how discrete logic can emerge from continuous training.

Authors’ abstract

Learning precise Boolean logic via gradient descent remains challenging: neural networks typically converge to "fuzzy" approximations that degrade under quantization. We introduce Hierarchical Spectral Composition, a differentiable architecture that selects spectral coefficients from a frozen Boolean Fourier basis and composes them via Sinkhorn-constrained routing with column-sign modulation. Our approach draws on recent insights from Manifold-Constrained Hyper-Connections (mHC), which demonstrated that projecting routing matrices onto the Birkhoff polytope preserves identity mappings and stabilizes large-scale training. We adapt this framework to logic synthesis, adding column-sign modulation to enable Boolean negation -- a capability absent in standard doubly stochastic routing. We validate our approach across four phases of increasing complexity: (1) For n=2 (16 Boolean operations over 4-dim basis), gradient descent achieves 100% accuracy with zero routing drift and zero-loss quantization to ternary masks. (2) For n=3 (10 three-variable operations), gradient descent achieves 76% accuracy, but exhaustive enumeration over 3^8 = 6561 configurations proves that optimal ternary masks exist for all operations (100% accuracy, 39% sparsity). (3) For n=4 (10 four-variable operations over 16-dim basis), spectral synthesis -- combining exact Walsh-Hadamard coefficients, ternary quantization, and MCMC refinement with parallel tempering -- achieves 100% accuracy on all operations. This progression establishes (a) that ternary polynomial threshold representations exist for all tested functions, and (b) that finding them requires methods beyond pure gradient descent as dimensionality grows. All operations enable single-cycle combinational logic inference at 10,959 MOps/s on GPU, demonstrating viability for hardware-efficient neuro-symbolic logic synthesis.