Polynomial Surrogate Training for Differentiable Ternary Logic Gate Networks

Sai Sandeep Damera; Ryan Matheu; Aniruddh G. Puranic; John S. Baras

cs.LGFeb 27, 2026

Polynomial Surrogate Training for Differentiable Ternary Logic Gate Networks

Authors: Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras

Organizations: University of Maryland, College Park, MD, USA

Abstract

Differentiable logic gate networks (DLGNs) learn compact, interpretable Boolean circuits via gradient-based training, but all existing variants are restricted to the 16 two-input binary gates. Extending DLGNs to Ternary Kleene $K_3$ logic and training DTLGNs where the UNKNOWN state enables principled abstention under uncertainty is desirable. However, the support set of potential gates per neuron explodes to $19{,}683$ , making the established softmax-over-gates training approach intractable. We introduce Polynomial Surrogate Training (PST), which represents each ternary neuron as a degree- $(2,2)$ polynomial with 9 learnable coefficients (a $2{,}187\times$ parameter reduction) and prove that the gap between the trained network and its discretized logic circuit is bounded by a data-independent commitment loss that vanishes at convergence. Scaling experiments from 48K to 512K neurons on CIFAR-10 demonstrate that this hardening gap contracts with overparameterization. Ternary networks train $2$ - $3\times$ faster than binary DLGNs and discover true ternary gates that are functionally diverse. On synthetic and tabular tasks we find that the UNKNOWN output acts as a Bayes-optimal uncertainty proxy, enabling selective prediction in which ternary circuits surpass binary accuracy once low-confidence predictions are filtered. More broadly, PST establishes a general polynomial-surrogate methodology whose parameterization cost grows only quadratically with logic valence, opening the door to many-valued differentiable logic.

Figures & tables

Figure 1: End-to-end comparison of binary DLGN training (top) and the proposed Polynomial Surrogate Training pipeline for ternary logic gate networks (bottom). Input encoding maps normalized features to bits/trits using temperature thresholding. Training: binary DLGNs learn softmax distributions over 16 gates per neuron; PST instead learns 9 polynomial coefficients per neuron, parameterising the full space of $19{,}683$ ternary gates directly. Hardening: binary networks select the argmax gate; PST evaluates each polynomial on the $3{\times}3$ ternary grid, rounds to the nearest valid truth table, and recovers discrete gate coefficients via $\mathbf{w}_{j}^{\mathrm{hard}}=\mathbf{V}^{-1}\operatorname{round}_{\mathcal{T}}(\mathbf{V}\mathbf{w}_{j})$ . Inference: both pipelines produce logic circuits; which can be taped out as ultra-efficient ASICs for Inference

Model	Neurons	Soft Acc	Circuit Acc	Gap (pp)	UNK%	Speed
DLGN - small	48K	49.3%	48.9%	$+0.5$	—	1.5 $\times$
TLGN - small	48K	45.4%	42.6%	$+2.8$	5.9%	1.5 $\times$
DLGN - medium	96K	50.7%	51.4%	$-0.8$	—	2.0 $\times$
TLGN - medium	96K	50.3%	36.1%	$+14.1$	6.2%	2.0 $\times$
DLGN - large	144K	51.4%	51.7%	$-0.4$	—	2.1 $\times$
TLGN - large	144K	51.5%	38.5%	$+13.0$	6.0%	2.1 $\times$

Table 1: Performance across all scales. Soft: continuous forward pass (10K test). Circuit: post-hardening discrete evaluation (2K samples;

\pm 2.2

pp CI). Gap = Soft

-

Circuit. UNK%: fraction of TLGN output neurons producing zero (not sample-level abstention). Speed: DLGN / TLGN wall-time ratio (RTX 4090).

Figure 2: Per-class circuit accuracy ( vlarge and huge ). Blue: DLGN . Orange: TLGN . Solid: vlarge . Hatched: huge . TLGN - huge recovers on visually complex classes (bird

+32.3

pp, cat

+37.2

pp, frog

+26.9

pp vs. vlarge ), surpassing DLGN on bird and cat.

	Raw Accuracy			Ternary Selective Prediction
Dataset	Bin	Tern	$\Delta$	UNK%	Acc@90%	Acc@50%	AUC
Moons	91.8%	85.8%	$-6.0$	52.9%	90.2%	98.1%	$-0.955$
Circles	97.0%	78.2%	$-18.8$	45.1%	76.7%	84.9%	$-0.864$
Spirals	63.2%	64.2%	$+1.0$	50.1%	65.4%	78.2%	$-0.790$
Gaussians	90.5%	78.8%	$-11.8$	50.6%	78.8%	99.5%	$-0.846$
Ring Sector	97.0%	92.2%	$-4.7$	38.3%	96.9%	100.0%	$-0.986$

Table 2: Ternary vs. binary: accuracy, abstention, and selective prediction.

\Delta

: ternary

-

binary accuracy. UNK%: fraction of ternary output neurons producing zero. Acc@

k

%: ternary accuracy when retaining only the

k

% most confident samples (binary has no analogous mechanism).

Figure 3: Ternary $U$ tracks Bayes-optimal uncertainty. Top row: Bayes posterior entropy, ternary $U$ density, and their overlay for Gaussians (separation ${}=1.5$ ). Bottom row: as class separation increases from 0.5 to 3.0 $\sigma$ , $U$ fraction and Bayes error decrease in lockstep. Binary accuracy (red) matches the Bayes rate at every separation, confirming that neither architecture is capacity-limited; the ternary circuit chooses to abstain where the posterior is ambiguous.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Scale	Widths	Neurons	PST LR	Steps
small	$[12000,\;12000,\;12000,\;12000]$	48,000	0.003	100K
medium	$[24000,\;24000,\;24000,\;24000]$	96,000	0.001	150K
large	$[36000,\;36000,\;36000,\;36000]$	144,000	0.001	200K
deeper	$[12000,\;12000,\;12000,\;12000,\;12000]$	60,000	0.003	100K
vlarge	$[48000,\;48000,\;48000,\;48000]$	192,000	0.001	150K
huge	$[128000,\;128000,\;128000,\;128000]$	512,000	0.001	200K

Appendix

Table 3: Architecture configurations. All use GroupSum(

k{=}10

\tau{=}33.3

) for 10-class output. Input dimension: 9,216.

Figure 4: Training loss curves ( small – large + deeper ).

2\times 2

grid, log-scale

y

-axis. Blue: DLGN . Dashed orange: TLGN task loss. Solid orange: TLGN total loss (task +

\lambda\cdot

commitment). TLGN converges 1-2 orders of magnitude below DLGN at medium and large scales, while both remain comparable at small scale.

Figure 5: Training loss curves ( vlarge and huge ). Left: vlarge (192K neurons). Right: huge (512K neurons). At huge scale, DLGN finally achieves clean convergence (0.015), eliminating the noisy-plateau pathology. TLGN - huge reaches 0.004 (task), the lowest of any model.

Figure 6: Ternary task loss convergence ( vlarge and huge ). Triangles mark the minimum. Both use lr

{=}0.001

. TLGN - huge reaches its floor (

{\sim}10^{-3}

) by step 30K, matching TLGN - vlarge ’s asymptotic performance in 15% of the training budget, then continues improving to

3\times 10^{-4}

. Periodic spikes (visible as upward excursions) coincide with lambda annealing ramp-up.

Scale	Neurons	DLGN (s)	TLGN (s)	Speedup
small	48K	241	156	1.5 $\times$
medium	96K	587	292	2.0 $\times$
large	144K	1023	479	2.1 $\times$
deeper	60K	297	167	1.8 $\times$
vlarge	192K	936	455	2.1 $\times$
huge	512K	4408	1401	3.1 $\times$

Appendix

Table 4: Training wall time (single RTX 4090). Speed ratio = DLGN time / TLGN time.

Scale	TLGN Gap (pp)	Hard Err	UNK%
small	$+2.8$	0.298	5.9%
deeper	$+2.0$	0.218	7.3%
medium	$+14.1$	0.253	6.2%
large	$+13.0$	0.074	6.0%
vlarge	$+11.9$	0.067	9.3%
huge	$+3.7$	0.029	24.6%

Appendix

Table 5: Hardening error and UNKNOWN% across scales. Hardening error drops

10\times

while UNKNOWN% increases

4\times

at huge scale.

Model	Unique	Eff. Div	Gini	Redund.%	Max Copies	Singletons
DLGN - small	16	14.9	0.176	100.0%	4,128	0
TLGN - small	8,987	4,268	0.603	81.3%	224	3,149
DLGN - medium	16	14.7	0.209	100.0%	10,341	0
TLGN - medium	12,655	6,719	0.587	86.8%	144	3,032
DLGN - large	16	14.5	0.222	100.0%	16,620	0
TLGN - large	14,375	7,590	0.592	90.0%	190	2,578

Appendix

Table 6: Gate diversity and functional redundancy. Unique: distinct truth tables. Eff. Div: exponential Shannon entropy. Gini: concentration (higher = more concentrated). Max copies: neuron count of the most common gate. Singletons: gates used by exactly one neuron.

Model	Unique	%Ternary	Const	Linear	Quad	Cubic	Quartic
TLGN - small	8,987	98.6%	18.1%	36.8%	31.4%	11.0%	2.8%
TLGN - medium	12,655	99.3%	17.4%	33.5%	33.1%	12.6%	3.3%
TLGN - large	14,375	99.4%	17.0%	32.6%	33.5%	13.4%	3.5%
TLGN - deeper	9,068	96.8%	23.6%	37.7%	26.8%	9.4%	2.5%

Appendix

Table 7: Fourier spectral profile ( TLGN models). Percentage of total Fourier energy in each degree band. %Ternary: fraction of unique gates that are genuinely ternary (not binary-equivalent).

Figure 7: Gate landscape - MDS embedding of ternary gates across scales. Top row: Hamming distance (number of differing truth table entries out of 9). Bottom row: Fourier $L^{2}$ distance. Each point is a unique gate; area $\propto\log_{2}(\text{neuron count})$ ; colour encodes $\log_{10}(\text{neuron count})$ . Red diamonds: the 15 named curated gates (AND, OR, XOR, etc.). Curated gates occupy the high-count core in all four embeddings, confirming that PST rediscovers classical logic operations without any gate-vocabulary constraint.

Figure 8: Per-class circuit accuracy at smaller scales. Blue: DLGN . Orange: TLGN . Solid: lower scale. Hatched: higher scale. TLGN shows high class-level variance at small - deeper scales, with catastrophic failures on visually complex classes (bird, cat, deer, frog). For larger scales ( vlarge , huge ) showing partial recovery, see Figure 2 in the main text.

	TLGN				DLGN ref.
Class	small	large	vlarge	huge	vlarge	huge	$\Delta_{\text{vl}\to\text{h}}$
airplane	51.5	50.5	62.8	61.2	58.7	60.2	$-1.6$
automobile	55.1	62.1	55.6	56.6	58.6	65.2	$+1.0$
bird †	21.5	17.9	18.5	50.8	37.9	43.6	$+32.3$
cat †	33.2	42.7	13.6	50.8	32.7	30.7	$+37.2$
deer †	44.9	11.1	24.2	25.8	36.4	40.9	$+1.6$

Appendix

Table 8: Per-class circuit accuracy (%) at selected scales. Bold: best ternary result per class.

\Delta

: improvement from vlarge to huge . Classes with vlarge accuracy

<30\%

are marked with

\dagger

Model	Circ Acc	Margin(C)	Margin(W)	Sep.	Acc@90%	Acc@50%
DLGN - small	48.9%	37.1	19.5	1.90 $\times$	52.0%	64.3%
TLGN - small	42.6%	38.4	22.9	1.68 $\times$	44.8%	54.5%
DLGN - large	51.7%	49.3	26.6	1.85 $\times$	54.9%	66.1%
TLGN - large	38.5%	66.3	41.3	1.61 $\times$	39.9%	48.3%
DLGN - vlarge	52.0%	58.6	30.1	1.95 $\times$	54.6%	66.3%
TLGN - vlarge	39.2%	85.6	51.9	1.65 $\times$	41.2%	49.5%

Appendix

Table 9: Margin-based selective classification (2K test samples). Margin(C/W): mean GroupSum margin for correct/wrong predictions. Separation: ratio of correct to wrong margin. Acc@

k

%: accuracy when retaining only the

k

% most confident samples.

Figure 9: Decision boundary gallery ( $5\times 4$ grid). Rows: Moons, Circles, Spirals, Gaussians, Ring Sector. Columns: raw data, binary boundary, ternary boundary, UNKNOWN density. Orange regions mark where $>50\%$ of output neurons produce zero.

Separation	Tern Acc	UNK%	Bin Acc	Bayes
$0.5\sigma$	59.8%	54.9%	68.2%	68.2%
$1.0\sigma$	71.0%	53.1%	83.5%	83.5%
$1.5\sigma$	78.7%	50.6%	90.5%	90.5%
$2.0\sigma$	85.5%	44.0%	97.8%	97.8%
$2.5\sigma$	92.2%	39.1%	99.0%	99.0%
$3.0\sigma$	93.5%	37.5%	99.8%	99.8%

Appendix

Table 10: Gaussian separation sweep. As separation increases, UNKNOWN fraction tracks the Bayes error. Binary accuracy matches the Bayes rate at all separations, confirming neither architecture is capacity-limited.

Figure 10: Accuracy vs. coverage (Spirals, Moons, Gaussians). As the circuit abstains on the lowest-margin samples, accuracy on the retained samples rises monotonically. The AUC quantifies selective prediction quality (closer to

-1.0

is better).

Figure 11: Asymmetric thresholding (Moons, four $\delta$ values). Peak accuracy (95.0%) at $\delta{=}0.50$ , not at the binary-like extreme.

$\delta$	Test Acc	UNK%	Gap
1.00	85.8%	52.8%	0.00%
0.50	95.0%	38.3%	0.00%
0.25	93.0%	36.6%	0.00%
0.00	91.7%	42.0%	$-0.81$ %

Appendix

Table 11: Asymmetric thresholding sweep (Moons, test set).

Figure 12: Resolution vs. accuracy and UNKNOWN rate (Moons). Higher resolution increases accuracy and decreases UNKNOWN fraction.

$K$	Input Dim	Body Widths	Test Acc	UNK%
2	2	$[128]^{3}$	84.0%	53.8%
4	6	$[256]^{3}$	85.8%	50.8%
8	14	$[512]^{3}$	94.5%	34.2%
16	30	$[1024]^{3}$	95.5%	23.8%

Appendix

Table 12: Resolution sweep (Moons, test set).

	Ternary			Binary
Dataset	Unique	Eff. Div	Red.%	Unique	Eff. Div	Red.%
Moons	1,214	1,051.8	30.1%	16	15.3	99.1%
Circles	1,225	1,065.1	29.4%	16	15.6	99.1%
Spirals	1,224	1,062.2	29.5%	16	15.3	99.1%
Gaussians	1,201	1,037.9	30.8%	16	15.6	99.1%
Ring Sector	1,253	1,089.1	27.8%	16	15.8	99.1%

Appendix

Table 13: Gate diversity (both architectures, all datasets).

Figure 13: Hardening gap (all datasets). Both architectures achieve small gaps. The ternary gap is elevated on Circles and Spirals.

Differentiable Logic Gate Networks

See all 14 papers

On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks
May 23, 2026Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic +2Logical Reasoning Signal Temporal Logic
University of Maryland, College Park, USA
Task-Aware Discretization of Differentiable Logic Gate Networks
Sep 27, 2026Thore GerlachEfficient Neural Network Inference Differentiable Logic Gate Networks
Independent Researcher
Fully Trainable Deep Differentiable Logic Gate Networks and Lookup Table Networks
Jul 10, 2026Wout Mommen, Lars Keuninckx, Matthias Hartmann +2Neural Network Optimization Differentiable Logic Gate Networks
imec, Kapeldreef 75, Leuven, 3001, , Belgium · Vrije Universiteit Brussel, Peinlaan 2, Elsene, 1050, , Belgium

May 23, 2026J/K move · Enter open · S save

On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks

Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras+1

University of Maryland, College Park, USA

Logical Reasoning Signal Temporal Logic Recurrent Neural Networks Runtime Verification Differentiable Logic Gate Networks

Open paper AskPDF arXiv

Recurrent Neural Networks (RNNs) can learn to predict Signal Temporal Logic (STL) verdicts online from partial trajectories, but deploying them as runtime monitors in safety-critical systems demands more than predictive accuracy. Standard RNN architectures offer no structural guarantee that outputs degrade gracefully under sensor degradation; a dropped input can silently flip a verdict from safe to unsafe. We introduce the Recurrent Differentiable Ternary Logic Gate Network (R-DTLGN), a recurrent architecture that operates over Kleene's three-valued logic

\{-1, 0, +1\}

, where

0

explicitly represents unknown. The R-DTLGN trains through continuous polynomial surrogates and hardens to a discrete ternary logic circuit at inference. We analyze the hardened circuit through two gate vocabularies derived from two orderings on the ternary domain: numerically monotone gates ensure stable recurrent dynamics, while information-monotone gates, when present, guarantee principled abstention (unknown inputs never produce wrong outputs) and monotonicity in input certainty (more information can only improve the verdict). We show that the recurrent connections required by bounded STL operators use exclusively AND and OR, which belong to both vocabularies, linking the monitoring task to the architecture's guarantees. A realizability bound derived from the STL formula's temporal operators directly sizes the network's hidden state, replacing hyperparameter search with a formula-driven specification. We evaluate on STL specifications over D4RL PointMaze navigation data, testing prediction accuracy, degradation under predicate dropout, and the accuracy-versus-safety tradeoff between two label construction pipelines. The R-DTLGN is, to our knowledge, the first recurrent architecture that couples learned temporal prediction with formal degradation guarantees rooted in three-valued logic.

Abstract

Differentiable Logic Gate Networks

Explore similar work

On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks

Task-Aware Discretization of Differentiable Logic Gate Networks

Fully Trainable Deep Differentiable Logic Gate Networks and Lookup Table Networks