Paper deep dive
Polynomial Surrogate Training for Differentiable Ternary Logic Gate Networks
Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/20/2026, 6:23:07 AM
Summary
The paper introduces Polynomial Surrogate Training (PST), a method for training Differentiable Ternary Logic Gate Networks (DTLGNs) using Kleene K3 logic. PST replaces the intractable softmax-over-gates approach with a degree-(2,2) polynomial representation, reducing parameters by 2,187x while covering all 19,683 possible ternary gates. The method proves a bounded hardening gap via a data-independent commitment loss and demonstrates that ternary networks train 2-3x faster than binary DLGNs, with the UNKNOWN state serving as a Bayes-optimal uncertainty proxy for selective prediction.
Entities (7)
Relation Signals (6)
Polynomial Surrogate Training → enablestrainingof → Differentiable Ternary Logic Gate Networks
confidence 95% · We introduce Polynomial Surrogate Training (PST), which represents each ternary neuron as a degree-(2,2) polynomial... Extending DLGNs to Ternary Kleene K3 logic and training DTLGNs
Polynomial Surrogate Training → reducesparametersby → 2,187x
confidence 92% · a 2,187× parameter reduction compared to softmax-over-gates
Polynomial Surrogate Training → evaluatedon → CIFAR-10
confidence 90% · Scaling experiments from 48K to 512K neurons on CIFAR-10 demonstrate that this hardening gap contracts
Polynomial Surrogate Training → usesbasisof → Kleene K3 Logic
confidence 90% · Extending DLGNs to Ternary Kleene K3 logic... PST represents each ternary neuron as a degree-(2,2) polynomial
Polynomial Surrogate Training → outperforms → Differentiable Logic Gate Networks
confidence 88% · Ternary networks train 2-3× faster than binary DLGNs
Unknown State → actsas → Uncertainty Proxy
confidence 85% · the UNKNOWN output acts as a Bayes-optimal uncertainty proxy, enabling selective prediction
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.00302v1
- Canonical: https://arxiv.org/abs/2603.00302v1
Trouble viewing inline? Open PDF directly →
Full Text
63,994 characters extracted from source content.
Expand or collapse full text
Sai Sandeep Damera @umd.edu Matheu @umd.edu G. Puranic @umd.edu S. Baras @umd.edu of Maryland, College Park, MD, USA Polynomial Surrogate Training for Differentiable Ternary Logic Gate Networks 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 K3K_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,68319,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)(2,2) polynomial with 9 learnable coefficients (a 2,187×2,187× 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 22-3×3× 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. keywords: Ternary Logic, Logic Gate Networks, Neuro-Symbolic AI. 1 Introduction Logic gate networks replace conventional arithmetic neurons with compositions of discrete two-input logic gates, producing circuits that are inherently compact and interpretable (petersen2022deep). Differentiable logic gate networks (DLGNs) make these circuits trainable through gradient descent by introducing continuous relaxations of the gate selection process. Since their introduction, DLGNs have been extended to convolutional architectures (petersen2024convolutional), recurrent variants (buhrer2025recurrent), and connection-optimized formulations (mommen2025method), demonstrating competitive accuracy at extreme parameter efficiency. All existing DLGNs share a common design: each two-input neuron maintains a softmax distribution over a fixed set of K=16K=16 Boolean gates, computes a weighted blend of their outputs during training, and selects a single gate via argmax at inference. This softmax-over-gates regime is viable precisely because the binary gate space is small enough to enumerate exhaustively. Yet it creates a structural train-test gap: the soft output ∑kpkgk(a,b) _kp_k\,g_k(a,b) disagrees with the hard output gk∗(a,b)g_k^*(a,b) unless the softmax probability concentrates entirely on one gate. This is a degenerate limit with vanishing gradients. Concurrent work has proposed Gumbel-noise injection and straight-through estimation to mitigate this gap (yousefi2025mind), though the fundamental issue with training cost remains unaddressed. Why Ternary Logic? Binary DLGNs inherit the fundamental limitation of classical Boolean logic: every signal is either True or False, with no capacity to express uncertainty or indeterminate outcomes. Many tasks require exactly this capacity—classification under sensor dropout, temporal logic evaluation over finite observation windows, and medical diagnosis from incomplete records all demand principled abstention, where a network can output “not yet determined” rather than committing to an unsupported decision. Kleene’s strong three-valued logic K3K_3 (kleene1952introduction; kleene2002mathematical), with truth values =−1,0,+1T=\-1,0,+1\ representing False, Unknown, and True, provides the minimal extension of Boolean logic that natively expresses this uncertainty. However, extending DLGNs to ternary logic reveals a fundamental limitation of the softmax-over-gates paradigm: a two-input ternary gate admits 332=19,6833^3^2=19,683 possible truth tables, making the categorical distribution approach intractable. Polynomial Surrogate Training. We introduce PST, which replaces the categorical parameterization entirely: instead of learning a distribution over gates, each neuron learns the coefficients of a low-degree polynomial that directly represents a function over 2T^2. For ternary logic, this is a degree-(2,2)(2,2) polynomial with exactly 9 coefficients, reducing parameters by 2,187×2,187× compared to softmax-over-gates while covering the full 19,683-gate vocabulary. PST is everywhere differentiable, requires no Gumbel tricks or softmax temperatures, and we prove that the per-neuron discretization error is bounded by a data-independent commitment loss (Theorem 4.1), providing a principled mechanism to narrow the train-test gap. The hardening gap. While commitment regularization bounds per-neuron discretization error, activation quantization across layers creates network-level train-test mismatch. Empirically, this gap contracts with overparameterization, falling from 14.1p to 3.7p as scale increases from 96K to 512K neurons on CIFAR-10. Fourier analysis on 2T^2. We develop a Fourier-analytic framework on −1,0,+1n\-1,0,+1\^n with an orthonormal basis appropriate for Kleene K3K_3 logic, including a quadratic term φ2(x)=x2−2/3 _2(x)=x^2-2/3 with no Boolean analogue that captures Unknown-sensitivity. Fourier coefficients serve as spectral complexity measures for principled regularization and post-hoc analysis. 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,68319,683 ternary gates directly. Hardening: binary networks select the argmax gate; PST evaluates each polynomial on the 3×33×3 ternary grid, rounds to the nearest valid truth table, and recovers discrete gate coefficients via jhard=−1round(j)w_j^hard=V^-1round_T(Vw_j). Inference: both pipelines produce logic circuits; which can be taped out as ultra-efficient ASICs for Inference Contributions. 1. We introduce Polynomial Surrogate Training (PST), the first training regime for logic gate networks that parameterizes the function space directly (9 coefficients per neuron for ternary logic) rather than through a distribution over gates. PST is everywhere differentiable and provides provable bounds on the per-neuron hardening gap via a data-independent commitment loss (Theorem 4.1). 2. We develop a Fourier-analytic framework on −1,0,1n\-1,0,1\^n with the orthogonal basis appropriate for Kleene K3K_3 logic, providing spectral characterization and principled regularization of learned gates. 3. Scaling experiments from 48K to 512K neurons on CIFAR-10 demonstrate PST trains ternary circuits 22-3×3× faster than binary DLGNs. On synthetic tasks, ternary circuits with Unknown outputs achieve selective prediction, surpassing binary accuracy when low-confidence predictions are filtered. 2 Related Work Efficient Neural Architectures. The computational demands of deep neural networks have motivated efficient model design bengio2013estimating, including binary networks, sparse networks (frankle2018lottery), and lookup-table approaches (zhu2016trained). DLGNs reduce every computation to a two-input logic gate lookup. Weightless neural networks (WNNs) (susskind2022weightless) use arbitrary lookup tables, whereas PST neurons are constrained to encode logic gates with compositional semantics, enabling formal verification and spectral analysis. Differentiable Logic Gate Networks Training networks of discrete components like logic gates is challenging because they are non-differentiable. petersen2022deep first introduced Differentiable Logic Gate Networks (DLGNs) to overcome this issue. Their approach relies relaxing discrete Boolean values 0,1\0,1\ to continuous [0,1][0,1] and representing each of the 16 two-input gates as differentiable functions. Crucially, the learning does not involve selecting a single gate per neuron a priori. Instead, each neuron in a DLGN learns a categorical probability distribution over all 16 possible logic gates, computing a weighted blend during training and selecting the mode gate via argmax at inference to produce a discrete logic circuit. This final hardened network is a pure logic circuit, composed of fixed connections and discrete gates, making it extremely fast at inference and fully transparent. These networks can, in theory, be synthesized directly onto digital hardware for further speed, energy efficiency, and cybersecurity gains. 3 Background and Preliminaries 3.1 Polynomial Representations for Boolean Logic Functions The mathematical foundation of PST rests on the fact that logic functions over finite domains have exact polynomial representations. Boolean functions admit exact real polynomial representations (nisan1994degree; o2014analysis). Concretely, a real polynomial p:ℝn→ℝp:R^n is said to represent a Boolean function f:−1, 1n→−1, 1f:\-1,\,1\^n→\-1,\,1\ if for all x∈−1, 1nx∈\-1,\,1\^n, p(x)=f(x)p(x)=f(x). Here we interpret True as +1+1 and False as −1-1. Because z2k=1,z2k+1=z,k∈ℕz^2k=1,\,z^2k+1=z,\,k for all z∈−1, 1z∈\-1,\,1\, these polynomials are reduced to multi-linear polynomials. Let the set PnP_n contain all real multi-linear polynomials that represent Boolean functions with n inputs. Then (Pn,⋅)(P_n,\,·\,) is a finite abelian group with group multiplication “⋅\,·\,” defined as polynomial multiplication. This subtle notion allows for the definition of a Fourier expansion on representing polynomials, the details of which are described in Appendix D. We extend this to the balanced ternary system with truth constants =−1,0,+1T=\-1,0,+1\ representing False, Unknown, and True respectively. Analogous to the Boolean case, a real multivariate polynomial p is said to represent a ternary function of the form f:n→f:T^n if for all x∈nx∈T^n, p(x)=f(x)p(x)=f(x). Consider z∈z . For integer k odd, k≥1k≥ 1, zk=z^k=z. For integer k even, k≥2k≥ 2, zk=z2z^k=z^2. Therefore multivariate polynomials representing ternary functions are multi-quadratic, containing variables with powers no greater than two. 3.2 Fourier Analysis on T The monomial basis, while convenient for parameterization, is not orthogonal under the uniform inner product ⟨f,g⟩=13n∑x∈nf(x)g(x) f,\,g = 13^n _x ^nf(x)\,g(x). Consider the set of single input (n=1n=1) ternary functions of the form f:→f:T . Applying Gram-Schmidt orthogonalization to the basis 1,x,x2\1,\,x,\,x^2\ yields the univariate orthogonal basis: φ0(x)=1,φ1(x)=x,φ2(x)=x2−23. _0(x)=1, _1(x)=x, _2(x)=x^2- 23. The term φ2 _2 is the “centered quadratic”: it measures whether x is extreme (±1± 1, where φ2(x)=13 _2(x)= 13) versus neutral (0, where φ2(x)=−23 _2(x)=- 23). This basis function has no Boolean analogue—it captures the Unknown-sensitivity that distinguishes Kleene K3K_3 from classical logic. The bivariate Fourier basis consists of the nine products φi(x)φj(y)0≤i,j≤2\ _i(x)\, _j(y)\_0≤ i,j≤ 2, and the Fourier expansion of any f:2→ℝf:T^2 is f=∑i,jf^ijφiφjf= _i,j f_ij\, _i _j. The Fourier coefficients f^ij f_ij serve as spectral complexity measures: the L1L_1 norm ∑|f^ij|Σ| f_ij| quantifies gate complexity, and we use it as a regularizer during training to bias learning toward spectrally sparse (interpretable) gates. The full derivation is provided in Appendix B. 4 The Polynomial Surrogate Training Framework for DTLGNs 4.1 PST Formulation The softmax-over-gates training regime creates an irreducible train-test gap: the soft network computes convex combinations of gate outputs while the hard network executes a single discrete gate. Gumbel relaxation approaches (kim2023deep) and Straight Through Estimation techniques (yousefi2025mind) reduce but do not eliminate this gap, and are intractable for ternary logic’s 19,683-gate support. Our proposed Polynomial Surrogate Training (PST) regime addresses this gap by replacing the categorical parameterization with a direct polynomial parameterization. Each neuron learns a 9-coefficient polynomial p:ℝ2→ℝp_w:R^2 that approximates a ternary gate truth table on 2T^2, with per-neuron discretization error bounded by a commitment regularizer. PST neuron. Each PST neuron represents a two-input ternary function as a degree-(2,2)(2,2) polynomial with 9 learnable coefficients ∈ℝ9w ^9: p(a,b)=⊤(a,b),p_w(a,b)=w m(a,b), (1) where (a,b)=[1,a,b,ab,a2,b2,a2b,ab2,a2b2]⊤m(a,b)=[1,\,a,\,b,\,ab,\,a^2,\,b^2,\,a^2b,\,ab^2,\,a^2b^2] is the monomial basis. Since the 9×99×9 Vandermonde matrix V evaluating this polynomial on 2T^2 is invertible, the parameterization is universal: any function f:2→ℝf:T^2 has a unique representation. The polynomial is C∞C^∞-smooth and linear in w, requiring no softmax or Gumbel relaxations, and evaluates in 8 multiplications and 8 additions per neuron. Network architecture. A PST-DTLGN is specified by its depth L, widths nll=0L\n_l\_l=0^L, a connectivity map C assigning two parent neurons to each neuron, and polynomial coefficients j(l)∈ℝ9w_j^(l) ^9. The training forward pass applies a clip nonlinearity after each polynomial evaluation: hj(l)=clip(pj(l)(hsj(⋅),htj(⋅))),h_j^(l)=clip\! (p_w_j^(l)\! (h_s_j^(·),\,h_t_j^(·) ) ), (2) where clip(x)=max(−1,min(1,x))clip(x)= (-1, (1,x)). Clipping preserves the range [−1,1][-1,1], prevents polynomial blowup across layers, preserves grid points −1,0,+1\-1,0,+1\ exactly, and implicitly regularizes toward ternary-range outputs through its zero-gradient saturation regime. Initialization. Weights are drawn i.i.d. from (0,0.452)N(0,0.45^2), chosen to ensure Var[p(a,b)]≈1Var[p_w(a,b)]≈ 1 on ternary inputs, analogous to Xavier initialization (pmlr-v9-glorot10a). 4.2 Training The training objective combines task loss with a commitment regularizer: ℒ()=ℒtask()+λ(t)⋅ℛA(),L(W)=L_task(W)+λ(t)·R_A(W), (3) where =j(l)W=\w_j^(l)\ is the set of all polynomial coefficients and the commitment loss is: ℛA()=1N∑j1q2∑(a,b)∈2dist(pj(a,b),)2,R_A(W)= 1N _j 1q^2 _(a,b) ^2dist\! (p_w_j(a,b),\,Q )^2, (4) with dist(x,)=minv∈|x−v|dist(x,Q)= _v |x-v|, where Q is the set of q truth values. For ternary logic, q=3q=3 and =−1,0,1Q=\-1,0,1\. The regularization weight λ(t)=λmax(t/T)γλ(t)= _ (t/T)^γ is annealed from ≈0≈ 0 (free exploration) to λmax _ (strong commitment) using a scheduling regime. 4.3 Hardening: From Polynomials to Gates At inference, each PST neuron is converted to a discrete ternary gate via Algorithm 1. Since rounding always produces a valid truth table in 9T^9, every trained PST neuron discretizes to one of the 19,683 possible two-input ternary gates without requiring a curated vocabulary—a fundamental advantage over the softmax regime, where the vocabulary must be fixed before training. Algorithm 1 PST Neuron Hardening Polynomial coefficients j∈ℝ9w_j ^9, Vandermonde matrix V, gate library G gate gj∗:2→g_j^*:T^2 j←jt_j _j *Evaluate polynomial at grid points 2T^2 ¯j←round(j) t_j _T(t_j) *Round each entry to nearest value in T gj∗←[¯j]g_j^* [ t_j] *Lookup gate in precomputed library return gj∗g_j^* 4.4 The Hardening Gap Hardening converts the continuous training-time model into a discrete circuit by rounding each neuron’s polynomial to the nearest gate in the truth-table lattice Λq=q2 _q=Q^q^2 (see Appendix A for lattice geometry). For ternary logic, this lattice has 39=19,6833^9=19,683 points in ℝ9R^9. Theorem 4.1 (PST Hardening Gap Bound). Let N be a q-logic PST network with N neurons. Let j=[pj(a,b)](a,b)∈2t_j=[p_w_j(a,b)]_(a,b) ^2 be neuron j’s soft truth table and ¯j∈Λq t_j∈ _q its hardened truth table. Then ℛA()=1N∑j=1N1q2‖j−¯j‖22.R_A(W)= 1N _j=1^N 1q^2\|t_j- t_j\|_2^2. Proof 4.2. By Algorithm 1, hardening rounds each polynomial evaluation to the nearest value in Q, so t¯j,(a,b)=argminv∈|pj(a,b)−v| t_j,(a,b)= _v |p_w_j(a,b)-v|. Therefore (pj(a,b)−t¯j,(a,b))2=dist(pj(a,b),)2(p_w_j(a,b)- t_j,(a,b))^2=dist(p_w_j(a,b),Q)^2. Summing over all grid points and averaging over neurons yields the result. Remark 4.3 (Scaling and Data-Independence). PST’s design improves with logic valence: a q-logic neuron requires only q2q^2 coefficients (vs. softmax’s super-exponential q2q^q^2 logits) while achieving O(1/q)O(1/q) rounding tolerance. The commitment loss ℛAR_A is data-independent, so Theorem 4.1 holds for all inputs in nQ^n, not just the training distribution. 5 Results We evaluate PST on two fronts: scaling experiments demonstrating that ternary networks train efficiently at CIFAR-10 scale (Section 5.1), and analysis of principled abstention via UNKNOWN (U) outputs on synthetic tasks (Section 5.2). All models use JAX (jax2018github) with Equinox (kidger2021equinox) and Adam. Binary DLGNs follow petersen2022deep. Full details in Appendix C. 5.1 Training DTLGNs at scale using PST We demonstrate that Polynomial Surrogate Training (PST) successfully trains differentiable ternary logic gate networks (TLGN) at CIFAR-10 scale, achieving soft accuracy parity with binary DLGNs while training 2–3× faster. The hardening gap (the accuracy cost of converting continuous polynomials to discrete ternary circuits) contracts from 14.1 p to 3.7 p as network scale increases from 96K to 512K neurons, establishing a clear trajectory toward gap elimination through overparameterization and commitment loss modulation. Setup. CIFAR-10 (50K train / 10K test) is flattened to 3,072 dimensions and encoded via resolution-4 balanced encoding (K=3K=3 thresholds), producing 9,216 binary or ternary input features. We evaluate six homogeneous 4-layer architectures from small (4×12K neurons, 48K total) to huge (4×128K, 512K total), plus a 5-layer deeper variant (60K total); see Table 3 for full configurations. All share identical random sparse connectivity (seed=\,=\,42) with two inputs per neuron. Binary DLGN uses Adam (lr=\,=\,0.01), cross-entropy via GroupSum (k=10k=10, τ=33.3τ=33.3). Ternary PST uses Adam (lr adapted per scale), λmax=0.1 _ =0.1, γ=2.0γ=2.0 (quadratic lambda annealing), MSE via GroupSum. Batch size 100 for both. Soft accuracy: full 10K test set; circuit accuracy: 2K samples (±2.2± 2.2 p Wilson CI at ∼50% 50\%). Table 1 presents the central results across all scales. Table 1: Performance across all scales. Soft: continuous forward pass (10K test). Circuit: post-hardening discrete evaluation (2K samples; ±2.2± 2.2 p CI). Gap = Soft −- Circuit. UNK%: fraction of TLGN output neurons producing zero (not sample-level abstention). Speed: DLGN/TLGN wall-time ratio (RTX 4090). Model Neurons Soft Acc Circuit Acc Gap (p) UNK% Speed DLGN-small 48K 49.3% 48.9% +0.5+0.5 — 1.5× TLGN-small 48K 45.4% 42.6% +2.8+2.8 5.9% DLGN-medium 96K 50.7% 51.4% −0.8-0.8 — 2.0× TLGN-medium 96K 50.3% 36.1% +14.1+14.1 6.2% DLGN-large 144K 51.4% 51.7% −0.4-0.4 — 2.1× TLGN-large 144K 51.5% 38.5% +13.0+13.0 6.0% DLGN-vlarge 192K 51.6% 52.0% −0.4-0.4 — 2.1× TLGN-vlarge 192K 51.2% 39.2% +11.9+11.9 9.3% DLGN-huge 512K 52.5% 53.0% −0.5-0.5 — 3.1× TLGN-huge 512K 52.1% 48.4% +3.7+3.7 24.6% DLGN-deeper 60K 49.3% 49.4% −0.1-0.1 — 1.8× TLGN-deeper 60K 45.0% 43.0% +2.0+2.0 7.3% PST trains ternary circuits at scale. Both architectures achieve comparable soft accuracy at all scales ≥ medium, plateauing at ∼52% 52\%, a ceiling imposed by the resolution-4 encoding rather than network capacity. At huge: TLGN 52.1% vs. DLGN 52.5% (p=0.57p=0.57, not significant). This parity is the key feasibility result: PST’s free polynomial parameterization (9 coefficients per neuron, searching 19,683 possible ternary gates) matches the representational capacity of the constrained softmax-over-16-gates approach, confirming that the ternary polynomial search space is trainable at scale. The hardening gap closes with overparameterization. The PST hardening gap follows a non-monotonic trajectory: modest at small (+2.8+2.8 p), peaking at medium (+14.1+14.1 p), then contracting steadily through large (+13.0+13.0), vlarge (+11.9+11.9), to huge (+3.7+3.7 p). This contraction is accompanied by a 10×10× reduction in per-neuron hardening error (0.298 → 0.029) and a 4×4× increase in U output neurons (5.9% → 24.6%). For the neurons whose hardened truth tables map to zero, contributing no signal to the GroupSum class scores (a possibility unique to ternary circuits, where 0 is a valid output value). This indicates that overparameterization enables implicit pruning: poorly-committed neurons are mapped to zero-output gates during hardening, while the surviving neurons are well-committed to valid ternary truth tables. The mechanism is detailed in §C.1.2; Figure 2 shows the per-class impact. 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+32.3 p, cat +37.2+37.2 p, frog +26.9+26.9 p vs. vlarge), surpassing DLGN on bird and cat. TLGNs train 2-3× faster. PST evaluates one polynomial per neuron (9 multiply-adds) vs. DLGN’s softmax over 16 gates, yielding 1.5× to 3.1× speedup across scales. PST matches binary DLGN soft accuracy while producing circuits whose hardening gap contracts with scale. Takeaway. PST is a viable and efficient training regime for ternary logic gate networks. It matches binary DLGN soft accuracy, trains 2–3× faster, and produces circuits whose hardening gap contracts with scale. The intrinsic advantages of ternary logic (principled abstention via U outputs, a 500×500× richer gate vocabulary, and three-valued expressiveness) are examined in the following subsection. 5.2 Salient Features of Ternary LGNs Binary logic gate networks (DLGN) must always commit to a classification: every neuron outputs 0,1\0,1\, and the GroupSum aggregation always produces a decisive class score. Ternary logic gate networks (TLGN), by contrast, operate in −1,0,+1\-1,0,+1\, where zero propagates through truth-table lookup as a first-class signal. This three-valued logic endows the deployed circuit with principled abstention, selective prediction, and Bayes-tracking uncertainty. These capabilities have no analog in binary DLGNs and are only accessible via PST, the first training regime that makes ternary gate networks trainable. We validate these properties on five 2D synthetic datasets (Moons, Circles, Spirals, Gaussians, Ring Sector; n=2,000n=2,000 train, 500500 test) using matched architectures: body [512]3[512]^3, output=200=200, GroupSum(k=2k=2, τ=10.0τ=10.0), resolution-4 encoding (K=3K=3, input dim=6=6). Both architectures are trained for 5,000 steps with discrete inputs. 5.2.1 The U signal: principled abstention absent in binary DLGNs Table 2 presents the head-to-head comparison. Binary DLGN achieves higher raw accuracy on four of five datasets (+4.7+4.7 to +18.8+18.8 p), but this comparison is misleading: the ternary circuit deliberately abstains on ambiguous inputs via its U mechanism, concentrating zero-valued outputs at decision boundaries (Figure 3). Under margin-based selective prediction, the ternary circuit surpasses binary full-coverage accuracy: at 50% coverage, Moons achieves 98.1% (vs. binary’s 91.8%), Gaussians 99.5%, and Ring Sector 100.0%. This demonstrates that ternary circuits provide more reliable predictions on inputs they choose to classify, a capability unavailable to binary circuits (see Appendix C.2.1–C.2.2 for full decision boundary gallery and accuracy-vs-coverage curves). Table 2: Ternary vs. binary: accuracy, abstention, and selective prediction. Δ : 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). Raw Accuracy Ternary Selective Prediction Dataset Bin Tern Δ UNK% Acc@90% Acc@50% AUC Moons 91.8% 85.8% −6.0-6.0 52.9% 90.2% 98.1% −0.955-0.955 Circles 97.0% 78.2% −18.8-18.8 45.1% 76.7% 84.9% −0.864-0.864 Spirals 63.2% 64.2% +1.0+1.0 50.1% 65.4% 78.2% −0.790-0.790 Gaussians 90.5% 78.8% −11.8-11.8 50.6% 78.8% 99.5% −0.846-0.846 Ring Sector 97.0% 92.2% −4.7-4.7 38.3% 96.9% 100.0% −0.986-0.986 Figure 3: Ternary U tracks Bayes-optimal uncertainty. Top row: Bayes posterior entropy, ternary U density, and their overlay for Gaussians (separation=1.5=1.5). Bottom row: as class separation increases from 0.5 to 3.0σ, 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. U as a Bayes-optimal uncertainty proxy To confirm that the U signal reflects genuine statistical uncertainty rather than training failure, we parametrically vary the difficulty of the Gaussian classification task (Appendix Table 10). As class separation increases from 0.5σ to 3.0σ, three quantities decrease together: the Bayes error, the ternary U fraction, and the spatial overlap between U density and the Bayes entropy H(y∣x)H(y x) (Figure 3). The binary baseline matches the Bayes rate at every separation level, confirming that these tasks are within both architectures’ capacity. The ternary circuit trades coverage for accuracy in precisely the regions where the Bayes posterior is ambiguous, a behavior that emerges naturally from the three-valued signal domain without any explicit calibration objective. 5.2.2 PST delivers ternary circuits with near-zero hardening gap The practical value of these ternary-specific features depends on whether PST can faithfully transfer the trained behavior to the deployed circuit. Table 2 includes the hardening gap (|soft−circuit||soft-circuit|) for both architectures: the binary gap is 0.00% on four of five datasets (3.19% on Spirals); the ternary gap is 0.00% on Moons, 0.31% on Gaussians, and 0.38% on Ring Sector. These near-zero gaps confirm that the polynomial surrogate training regime, including quadratic lambda annealing and ternary commitment regularization, produces circuits that preserve the training-time abstention behavior after hardening. The elevated ternary gaps on Circles (8.31%) and Spirals (4.31%) are consistent with the narrow hardening basins identified in the loss landscape analysis (Appendix Figure 13). 6 Conclusion and Future Work We introduced Polynomial Surrogate Training (PST), which makes ternary logic gate networks practical by parameterizing the full 19,683-gate vocabulary with just 9 coefficients per neuron. PST provides provable bounds on per-neuron discretization error through a data-independent commitment loss and trains ternary circuits 2–3× faster than binary DLGNs. Ternary logic’s key advantage is principled abstention via Unknown outputs, which enables selective prediction where circuits surpass binary accuracy by filtering low-confidence predictions: ternary circuits achieve 98.1% accuracy at 50% coverage (vs. 91.8% binary full-coverage accuracy on Moons), with Unknown density tracking Bayes-optimal uncertainty across varying task difficulty, demonstrating that three-valued logic is a practical mechanism for uncertainty-aware inference in deployed circuits. Two directions warrant immediate attention: (a) adapting straight-through estimation and Gumbel-noise regularization (bengio2013estimating; yousefi2025mind) to PST’s polynomial regime may further narrow the network-level hardening gap that contracts empirically with scale but lacks theoretical guarantees; and, (b) extending PST to recurrent architectures would enable online temporal monitoring with three-valued logic, as Signal Temporal Logic (STL) specifications inherently require ternary verdicts (True, False, Unknown) over finite observation windows, making recurrent DTLGNs a natural fit for runtime verification in safety-critical systems where partial observations demand principled abstention rather than forced binary classification. References Appendix A Hardening Gap: Lattice Geometry A.1 Truth-Table Lattice Quantization Both the softmax-over-gates and PST training regimes face the same geometric problem: after training, each neuron must be assigned one of finitely many discrete gates. We formalize this as a quantization problem on a truth-table lattice. Definition A.1 (Truth-Table Lattice). Let =v0,v1,…,vq−1⊂ℝQ=\v_0,v_1,…,v_q-1\ be an equally spaced set of q truth values. The truth-table lattice Λq=q2 _q=Q^q^2 is the set of all valid truth tables for two-input q-logic gates, embedded in ℝq2R^q^2. The lattice has |Λq|=q2| _q|=q^q^2 points. For the cases of interest: Boolean logic has q=2q=2, |Λ2|=24=16| _2|=2^4=16 gates in ℝ4R^4; ternary logic has q=3q=3, |Λ3|=39=19,683| _3|=3^9=19,683 gates in ℝ9R^9; and quaternary logic has q=4q=4, |Λ4|=416≈4.3×109| _4|=4^16≈ 4.3× 10^9 gates in ℝ16R^16. Hardening maps each neuron’s continuous output (a point in ℝq2R^q^2) to the nearest lattice point in Λq _q. The per-neuron hardening error is the ℓ2 _2 distance from the neuron’s soft truth table to the nearest valid gate. The key geometric quantity is the covering radius of Λq _q: the maximum distance from any point in the ambient space to the nearest lattice point. Proposition A.2 (Covering Radius). The covering radius of the lattice Λq _q (with truth values uniformly spaced by Δ=2/(q−1) =2/(q-1) in [−1,1][-1,1]) satisfies rcov(Λq)=q−1,r_cov( _q)= qq-1, and the maximum per-entry rounding error is ϵq=1q−1. _q= 1q-1. Proof A.3. Each coordinate of the truth table independently rounds to the nearest value in Q. With q uniformly spaced values in [−1,1][-1,1], consecutive values are separated by Δ=2/(q−1) =2/(q-1). The worst-case per-coordinate error is Δ/2=1/(q−1) /2=1/(q-1). The ℓ2 _2 covering radius over all q2q^2 coordinates is q2⋅(Δ/2)2=q⋅Δ/2=q/(q−1) q^2·( /2)^2=q· /2=q/(q-1). For ternary logic (q=3q=3), ϵ3=1/2=0.5 _3=1/2=0.5; for quaternary (q=4q=4), ϵ4=1/3≈0.333 _4=1/3≈ 0.333. As q increases, each coordinate need only be accurate to within O(1/q)O(1/q) to snap to the correct gate entry. Proposition A.4 (PST Architectural Scaling). A q-logic PST neuron over two inputs requires q2q^2 learnable coefficients. The maximum per-entry rounding error at hardening time is ϵq=1/(q−1)=O(1/q) _q=1/(q-1)=O(1/q). Therefore, a higher-valence PST architecture achieves tighter rounding tolerance per truth-table entry at a cost that grows only quadratically in q. By contrast, a softmax-over-gates neuron for q-ary logic requires K=q2K=q^q^2 logits (super-exponential in q), and its rounding error is governed by the concentration of a categorical distribution over K categories. PST’s design improves with logic valence: the polynomial representation cost grows polynomially (q2q^2 coefficients) while the lattice becomes denser (ϵq→0 _q→ 0). The softmax-over-gates regime faces the opposite situation: its parameterization cost explodes super-exponentially while the concentration problem worsens. Appendix B Spectral Analysis of Ternary Logic Gate Networks Computing the Orthonormal Basis. We have the ternary set =−1,0,+1T=\-1,0,+1\ and want to represent every function f:2→ℝf:T^2 as a linear combination of basis functions. Since |2|=9 |T^2 |=9, the space of such functions is ℝ9−R^9- nine-dimensional. We need exactly 9 basis functions, and we want them orthogonal under some inner product. The Inner Product. The uniform measure on T assigns probability 1/31/3 to each value. The inner product on functions f,g:→ℝf,g:T is: ⟨f,g⟩=13∑x∈f(x)g(x)=13[f(−1)g(−1)+f(0)g(0)+f(1)g(1)] f,g = 13 _x f(x)g(x)= 13[f(-1)g(-1)+f(0)g(0)+f(1)g(1)] Each ternary input is equally weighted. The factor 1/31/3 is a normalization - it makes ⟨1,1⟩=1 1,1 =1 so the constant function has unit norm. The bivariate inner product on 2T^2 uses the same idea with factor 1/9. The Monomial Basis. The monomials 1,x,x2 \1,x,x^2 \ are a valid basis for polynomials of degree ≤2≤ 2 in one variable, and they span the right space (any function →ℝT is determined by 3 values, and 3 monomials give 3 degrees of freedom). But they are not orthogonal under this inner product: ⟨1,x2⟩=13[1⋅1+1⋅0+1⋅1]=23≠0 1,x^2 = 13[1· 1+1· 0+1· 1]= 23≠ 0 The constant function and x2x^2 are correlated on T because x2x^2 evaluates to 1 at both ±1± 1 and 0 at 0 . Under the uniform measure, x2x^2 has mean 2/32/3 - it is biased toward 1 because two out of three ternary inputs are extreme ( ±1± 1 ) and only one is neutral ( 0 ). Since x2x^2 is nonzero at two-thirds of the domain, its mean is nonzero, which means it is not orthogonal to the constant. The monomial basis is fine for computation (and is what we use for the weight parameterization), but it is unsuitable for analysis because the coefficients are entangled and we cannot ascribe meaning to the values of these coefficients like we can with the Fourier coefficients. Gram-Schmidt Orthogonalization. We generate the orthonormal basis from the monomial basis by following the Gram-Schmidt process: Step 1: φ0(x)=1 _0(x)=1. Norm: ‖φ0‖2=⟨1,1⟩=1 \| _0 \|^2= 1,1 =1. Step 2: Start with x , subtract its projection onto φ0 _0. ⟨x,φ0⟩=13(−1⋅1+0⋅1+1⋅1)=0 x, _0 = 13(-1· 1+0· 1+1· 1)=0 The projection is zero; x is already orthogonal to the constant. This happens because x is an odd function and the measure is symmetric around 0. So φ1(x)=x _1(x)=x, with ∥φ1∥2==2/3 \| _1 \|^2==2/3. Step 3: Start with x2x^2, subtract projections onto φ0 _0 and φ1 _1. ⟨x2,φ1⟩=13((−1)2(−1)+02⋅0+12⋅1)=0 x^2, _1 = 13 ((-1)^2(-1)+0^2· 0+1^2· 1 )=0 Zero by symmetry −x2-x^2 is even, x is odd, their product is odd, and odd functions sum to zero on T. So we only need to subtract the φ0 _0 projection: ⟨x2,φ0⟩=13(1+0+1)=23φ2(x)=x2−⟨x2,φ0⟩‖φ0‖2⋅φ0=x2−2/31⋅1=x2−23 gathered x^2, _0 = 13(1+0+1)= 23\\ _2(x)=x^2- x^2, _0 \| _0 \|^2· _0=x^2- 2/31· 1=x^2- 23 gathered The −2/3-2/3 is not arbitrary - it is the mean of x2x^2 under the uniform measure on T. The polynomial φ2(x)=x2−2/3 _2(x)=x^2-2/3 is the “centered” quadratic: it measures whether x is extreme (±1 (± 1 ., where φ2=1/3) . _2=1/3 ) versus neutral (0 (0 ., where φ2=−2/3) . _2=-2/3 ). It has zero mean on T by construction with ‖φ2‖2=2/9 \| _2 \|^2=2/9. In Boolean analysis on −1,+1\-1,+1\, every function of one variable is a linear combination of 1 and x - there are only two basis functions because |−1,+1|=2|\-1,+1\|=2. The quadratic φ2 _2 is the ”extra dimension” that ternary logic provides, and it captures exactly the UNKNOWN-sensitivity that makes Kleene K3 logic different from Boolean logic. Remark B.1. Our basis differs from the additive-combinatorial convention in two ways: (i) we use real-valued orthogonal polynomials rather than complex characters, matching the real polynomial parameterization of PST neurons; and (i) we construct the basis via Gram-Schmidt from 1,x,x2\1,x,x^2\ rather than from the group characters of ℤ3Z_3, yielding a basis that is adapted to the Kleene interpretation where −1,+1\-1,+1\ are “decided” values and 0 is “undetermined.” The resulting quadratic basis function φ2=x2−2/3 _2=x^2-2/3 is orthogonal to both the constant and linear terms and captures precisely the sensitivity to Unknown that has no analogue in Boolean Fourier analysis. The full list of the Fourier coefficients is as follows: Φ00=1,Φ10=x,Φ01=y,Φ11=xy,Φ20=x2−2/3,Φ02=y2−2/3,Φ21=(x2−2/3)y,Φ12=x(y2−2/3),Φ22=(x2−2/3)(y2−2/3) _00=1, _10=x, _01=y, _11=xy, _20=x^2-2/3, _02=y^2-2/3, _21=(x^2-2/3)y, _12=x(y^2-2/3), _22=(x^2-2/3)(y^2-2/3). Spectral complexity classes. The Fourier spectrum naturally stratifies the 19,683 ternary gates into complexity classes. Linear gates have energy only in f^00,f^10,f^01 f_00, f_10, f_01. These include MAJORITY and the trivial pass-through gates, and they are the only gates that can be computed by a single linear threshold on ternary inputs. Bilinear gates additionally use the interaction term f^11 f_11; AND, OR, XOR, and their variants fall here. Quadratic gates involve f^20 f_20 or f^02 f_02 and are the genuinely “ternary” gates that distinguish between decided and undecided inputs. Full gates use all nine terms. The Fourier L1L_1 norm ‖f^‖1=∑ij|f^ij|\| f\|_1= _ij| f_ij| is a rigorous complexity measure: it upper-bounds the number of random examples needed to learn the gate to constant accuracy, and it determines the gate’s sensitivity to random input perturbations. Fourier sparsity regularization. The L1L_1 norm of Fourier coefficients serves as a sparsity regularizer independent of the commitment loss: ℛF()=1N∑j=1N∑i,k|f^ik(j)|.R_F(W)= 1N _j=1^N _i,k| f_ik^(j)|. (B.1) The commitment loss ℛAR_A drives neurons toward any of the 19,683 gates; the Fourier regularizer biases that choice toward spectrally sparse, interpretable gates. The combined training objective is ℒ=ℒtask+λ(t)⋅ℛA+β⋅ℛFL=L_task+λ(t)·R_A+β·R_F. Post-hoc spectral profiling. After training and discretization, the aggregate spectral energy distribution across all neurons reveals whether the task genuinely exploits ternary structure. If most energy concentrates in linear Fourier terms (f^10 f_10, f^01 f_01, f^11 f_11), the network is essentially performing sign propagation and could function as a Boolean circuit. If substantial energy appears in quadratic terms (f^20 f_20, f^02 f_02, f^22 f_22), the network is genuinely exploiting the three-valued distinction, routing information differently based on whether inputs are decided versus undetermined. This spectral profile is a principled diagnostic for whether K3K_3 logic adds value over binary logic for a given task. Vocabulary coverage. The Hamming distance between a neuron’s discretized truth table and the nearest curated gate quantifies vocabulary coverage. The Level 2 coverage (the fraction of neurons whose nearest curated gate has Hamming distance zero) reveals which tasks are “natively ternary” (high coverage) versus tasks requiring gates outside the standard vocabulary. One of the more interesting, formally defined vocabularies of ternary gates is that of threshold logic (jones2012ternary). In threshold logic, each input iji_j is multiplied by a constant kjk_j and then the inputs are summed and then compared to two thresholds t+t_+ and t–t_–. If the sum is t+t_+ or greater, the output is +1+1. If the sum is t–t_–, the output is –1–1. According to merrill1965ternary, 471 of the 19,683 diadic ternary operators can be computed using threshold logic. Appendix C Additional Experimental Results C.1 Supplementary: CIFAR-10 scaling details Table 3: Architecture configurations. All use GroupSum(k=10k=10, τ=33.3τ=33.3) for 10-class output. Input dimension: 9,216. Scale Widths Neurons PST LR Steps small [12000, 12000, 12000, 12000][12000,\;12000,\;12000,\;12000] 48,000 0.003 100K medium [24000, 24000, 24000, 24000][24000,\;24000,\;24000,\;24000] 96,000 0.001 150K large [36000, 36000, 36000, 36000][36000,\;36000,\;36000,\;36000] 144,000 0.001 200K deeper [12000, 12000, 12000, 12000, 12000][12000,\;12000,\;12000,\;12000,\;12000] 60,000 0.003 100K vlarge [48000, 48000, 48000, 48000][48000,\;48000,\;48000,\;48000] 192,000 0.001 150K huge [128000, 128000, 128000, 128000][128000,\;128000,\;128000,\;128000] 512,000 0.001 200K C.1.1 Training dynamics Base scales (48K-144K). Figure 4 shows training loss curves for four scales. At small and medium scales, DLGN enters a noisy plateau (oscillating in 0.5-1.4), while PST achieves 1010-38×38× lower task loss (e.g., TLGN-large: 0.017 vs. DLGN-large: 0.65). The 5-layer deeper variant shows the same plateau as small, confirming that depth alone does not resolve it. Figure 4: Training loss curves (small–large + deeper). 2×22× 2 grid, log-scale y-axis. Blue: DLGN. Dashed orange: TLGN task loss. Solid orange: TLGN total loss (task + λ⋅λ· commitment). TLGN converges 1-2 orders of magnitude below DLGN at medium and large scales, while both remain comparable at small scale. Extended scales (192K-512K). Figure 5 extends to vlarge and huge. DLGN-huge (512K) breaks through to 0.015, a qualitative transition from plateau-dominated to clean convergence, suggesting the softmax-over-gates parameterization requires a threshold overparameterization level (between 48K and 128K per-layer width). TLGN-huge reaches 0.004, the lowest task loss of any model. 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. Ternary convergence. Figure 6 overlays TLGN task loss curves for vlarge and huge. TLGN-huge reaches its floor (∼10−3 10^-3) by step 30K, matching TLGN-vlarge’s asymptotic performance in 15% of the training budget. Periodic spikes coincide with lambda annealing ramp-up; these are transient (recovery within 1-2K steps) and do not affect final performance. Figure 6: Ternary task loss convergence (vlarge and huge). Triangles mark the minimum. Both use lr=0.001=0.001. TLGN-huge reaches its floor (∼10−3 10^-3) by step 30K, matching TLGN-vlarge’s asymptotic performance in 15% of the training budget, then continues improving to 3×10−43× 10^-4. Periodic spikes (visible as upward excursions) coincide with lambda annealing ramp-up. Table 4: Training wall time (single RTX 4090). Speed ratio = DLGN time / TLGN time. Scale Neurons DLGN (s) TLGN (s) Speedup small 48K 241 156 1.5× medium 96K 587 292 2.0× large 144K 1023 479 2.1× deeper 60K 297 167 1.8× vlarge 192K 936 455 2.1× huge 512K 4408 1401 3.1× C.1.2 Hardening gap mechanism Three regimes govern the gap trajectory. Regime I: Low capacity (48K-60K). Gap is modest (2.02.0-2.82.8 p). The polynomials have limited freedom; the gap is small because there is little to lose in hardening. However, hardening error is high (0.298): the polynomials are not close to valid gates, but per-neuron rounding errors do not compound catastrophically at this scale. Regime I: Mid capacity (96K-192K). Gap peaks at 14.114.1 p (medium) and remains elevated through vlarge (11.911.9 p). The network develops rich polynomial representations far from valid ternary truth tables. The commitment regularizer reduces hardening error monotonically (0.253 → 0.067), but accumulated rounding through four layers remains destructive. Regime I: High capacity (512K). Gap contracts to 3.73.7 p with hardening error 0.029, meaning each truth table entry is within 0.029 of the nearest ternary value on average. The contraction is accompanied by a sharp increase in UNKNOWN output neurons (24.6%24.6\% vs. ∼6% 6\% at smaller scales), reflecting implicit pruning: neurons near Voronoi cell boundaries in truth-table space are mapped to zero-output gates, while surviving neurons carry sufficient discriminative signal. Table 5: Hardening error and UNKNOWN% across scales. Hardening error drops 10×10× while UNKNOWN% increases 4×4× at huge scale. Scale TLGN Gap (p) Hard Err UNK% small +2.8+2.8 0.298 5.9% deeper +2.0+2.0 0.218 7.3% medium +14.1+14.1 0.253 6.2% large +13.0+13.0 0.074 6.0% vlarge +11.9+11.9 0.067 9.3% huge +3.7+3.7 0.029 24.6% C.1.3 Gate diversity and Fourier spectral analysis Table 6 reports gate diversity and functional redundancy. The effective diversity ratio (TLGN/DLGN) ranges from 286× (small) to 523× (large). Unique gates grow from 8,987 (small) to ∼14,000 14,000 (large-vlarge) then decrease slightly to 13,955 at huge, while Gini increases monotonically (0.603 → 0.696) and effective diversity drops from 7,590 to 5,437. The huge model uses fewer distinct gate types but copies each more frequently. 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 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 DLGN-vlarge 16 14.4 0.231 100.0% 23,263 0 TLGN-vlarge 14,360 7,239 0.610 92.5% 338 2,181 DLGN-huge 16 14.2 0.251 100.0% 66,609 0 TLGN-huge 13,955 5,437 0.696 97.3% 1,490 1,710 Table 7 decomposes the unique gates into Fourier complexity bands. Larger networks learn more complex gates: linear energy decreases from 36.8% (small) to 32.6% (large) while quadratic and cubic energy increase. The deeper variant has the most linear profile (37.7%), consistent with narrower per-layer width limiting inter-neuron interaction complexity. Over 98% of gates are genuinely ternary at all scales. 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). 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% C.1.4 Gate landscape geometry via MDS embedding The Fourier spectral profile (Table 7) summarizes aggregate complexity but does not reveal how the ∼9,000 9,000–14,00014,000 unique gates are organized relative to one another. We apply multidimensional scaling (MDS) under two complementary distance metrics: Hamming distance on truth tables; and, Euclidean (L2L^2) distance on Fourier coefficient vectors; to embed each unique gate as a point in ℝ2R^2. Figure 7 shows the result for all four base scales. 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 L2L^2 distance. Each point is a unique gate; area ∝log2(neuron count) _2(neuron count); colour encodes log10(neuron count) _10(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. Clustering of learned gates around named gates. Under both metrics and at all four scales, the highest-count learned gates (bright points, log10(count)>2 _10(count)>2) cluster in the same region as the 15 named curated gates (red diamonds). This co-location indicates that PST, despite searching an unconstrained space of 19,683 truth tables, independently converges toward the neighbourhood of classical logic operations (AND, OR, XOR, NAND, etc.). Low-count gates — including the ∼2,600 2,600 singletons at large (Table 6) - are scattered at greater embedding distances from this core, consistent with their role as rare, task-specific functions. The two metrics provide complementary views. Hamming distance captures how many truth table entries differ between gates (out of 9), so nearby points in the top row are functionally similar. Fourier L2L^2 distance captures differences in spectral energy distribution, so nearby points in the bottom row share similar complexity profiles regardless of which specific entries differ. The named gates occupy the high-count core under both metrics, confirming that they are central in both the functional and spectral sense. Scale dependence. From small to large, the gate cloud grows denser as unique gates increase (8,987 → 14,375) and effective diversity rises (4,268 → 7,590; Table 6). The deeper variant (rightmost column), despite a comparable neuron count to small, produces a more compact cloud, consistent with its higher constant-energy fraction (23.6% vs. 18.1%) and lower quadratic-energy fraction (26.8% vs. 31.4%; Table 7). C.1.5 Per-class analysis The per-class breakdown (Figure 8, Table 8) reveals that the TLGN hardening gap is not uniform across classes. 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. Table 8: Per-class circuit accuracy (%) at selected scales. Bold: best ternary result per class. Δ : improvement from vlarge to huge. Classes with vlarge accuracy <30%<30\% are marked with † . TLGN DLGN ref. Class small large vlarge huge vlarge huge Δvl→h _vl airplane 51.5 50.5 62.8 61.2 58.7 60.2 −1.6-1.6 automobile 55.1 62.1 55.6 56.6 58.6 65.2 +1.0+1.0 bird† 21.5 17.9 18.5 50.8 37.9 43.6 +32.3+32.3 cat† 33.2 42.7 13.6 50.8 32.7 30.7 +37.2+37.2 deer† 44.9 11.1 24.2 25.8 36.4 40.9 +1.6+1.6 dog 33.5 35.7 64.3 30.8 44.9 44.9 −33.5-33.5 frog† 42.6 28.2 24.5 51.4 65.7 65.3 +26.9+26.9 horse 46.6 59.6 37.8 46.1 55.4 56.5 +8.3+8.3 ship 48.8 30.4 42.4 56.2 69.1 62.2 +13.8+13.8 truck 47.3 48.3 51.2 52.7 57.1 58.6 +1.5+1.5 TLGN-huge recovers on hard classes. The most dramatic improvements from vlarge to huge occur on visually complex classes: bird (+32.3+32.3 p), cat (+37.2+37.2 p), frog (+26.9+26.9 p), and ship (+13.8+13.8 p). At huge scale, TLGN surpasses DLGN on bird (50.8% vs. 43.6%) and cat (50.8% vs. 30.7%). Dog class regression. TLGN-vlarge achieved 64.3% on dog but TLGN-huge drops to 30.8% (−33.5-33.5 p). The dog-cat confusability in CIFAR-10 and the 4×4× increase in UNKNOWN neurons suggest a redistribution of discriminative capacity rather than uniform improvement. DLGN is more uniform. Binary circuit accuracy has lower per-class variance (CoV: 0.23 for DLGN-huge vs. 0.28 for TLGN-huge) and dominates on “easy” classes (frog: 65.3% vs. 51.4%; automobile: 65.2% vs. 56.6%). C.1.6 Margin-based confidence Ternary circuits provide a natural confidence signal via the GroupSum margin (difference between highest and second-highest class scores). 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. Model Circ Acc Margin(C) Margin(W) Sep. Acc@90% Acc@50% DLGN-small 48.9% 37.1 19.5 1.90× 52.0% 64.3% TLGN-small 42.6% 38.4 22.9 1.68× 44.8% 54.5% DLGN-large 51.7% 49.3 26.6 1.85× 54.9% 66.1% TLGN-large 38.5% 66.3 41.3 1.61× 39.9% 48.3% DLGN-vlarge 52.0% 58.6 30.1 1.95× 54.6% 66.3% TLGN-vlarge 39.2% 85.6 51.9 1.65× 41.2% 49.5% DLGN-huge 53.0% 106.4 50.5 2.11× 55.7% 70.3% TLGN-huge 48.4% 131.7 73.9 1.78× 50.6% 61.5% Ternary margins are larger in absolute magnitude (−1,0,1\-1,0,1\ outputs actively suppress competing classes), but DLGN achieves better margin separation: 2.11× vs. 1.78× at huge scale, yielding Acc@50% of 70.3% vs. 61.5%. Ternary separation improves with scale (1.65× → 1.78× from vlarge to huge; Acc@50%: 49.5% → 61.5%), indicating genuine improvement in discriminative quality of surviving neurons. C.2 Appendix: Supporting Experiments C.2.1 Decision boundary gallery Figure 9 presents the full 5×45× 4 decision boundary gallery. Each row shows one dataset; columns display the raw data, binary circuit boundary, ternary circuit boundary, and UNKNOWN density overlay. Across all five datasets, the ternary UNKNOWN regions (orange) concentrate at decision boundaries, confirming the pattern described in Section 5.2.1. Figure 9: Decision boundary gallery (5×45× 4 grid). Rows: Moons, Circles, Spirals, Gaussians, Ring Sector. Columns: raw data, binary boundary, ternary boundary, UNKNOWN density. Orange regions mark where >50%>50\% of output neurons produce zero. The UNKNOWN fraction ranges from 38.3% (Ring Sector) to 52.9% (Moons), scaling with boundary complexity. Ring Sector, with its clean angular separation, produces the smallest UNKNOWN band; Moons, with its high boundary curvature and noise=0.5=0.5, produces the largest. 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. Separation Tern Acc UNK% Bin Acc Bayes 0.5σ0.5σ 59.8% 54.9% 68.2% 68.2% 1.0σ1.0σ 71.0% 53.1% 83.5% 83.5% 1.5σ1.5σ 78.7% 50.6% 90.5% 90.5% 2.0σ2.0σ 85.5% 44.0% 97.8% 97.8% 2.5σ2.5σ 92.2% 39.1% 99.0% 99.0% 3.0σ3.0σ 93.5% 37.5% 99.8% 99.8% C.2.2 Accuracy vs. coverage curves Figure 10 shows the full accuracy-vs-coverage curves for three representative datasets. The monotonic increase confirms that the GroupSum margin is a well-calibrated confidence proxy: low-margin predictions are disproportionately incorrect, and abstaining on them systematically improves accuracy on the retained set. 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-1.0 is better). C.2.3 Controlling the UNKNOWN band The delta_fraction parameter (δ∈[0,1]δ∈[0,1]) controls the width of the UNKNOWN encoding band. Table 11 and Figure 11 show that peak accuracy on Moons occurs at δ=0.50δ=0.50 (95.0%), not at either extreme. Notably, UNK% does not reach zero even at δ=0.0δ=0.0 (42.0%), because UNKNOWN outputs emerge from internal truth tables, not only from the input encoding. Figure 11: Asymmetric thresholding (Moons, four δ values). Peak accuracy (95.0%) at δ=0.50δ=0.50, not at the binary-like extreme. Table 11: Asymmetric thresholding sweep (Moons, test set). δ 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-0.81% C.2.4 Encoding resolution Higher resolution simultaneously increases accuracy and decreases UNKNOWN rate (Table 12, Figure 12): from 84.0% accuracy / 53.8% UNK at K=2K=2 to 95.5% / 23.8% at K=16K=16, confirming that the UNKNOWN band reflects input-level ambiguity resolvable by finer quantization. Figure 12: Resolution vs. accuracy and UNKNOWN rate (Moons). Higher resolution increases accuracy and decreases UNKNOWN fraction. Table 12: Resolution sweep (Moons, test set). K Input Dim Body Widths Test Acc UNK% 2 2 [128]3[128]^3 84.0% 53.8% 4 6 [256]3[256]^3 85.8% 50.8% 8 14 [512]3[512]^3 94.5% 34.2% 16 30 [1024]3[1024]^3 95.5% 23.8% C.2.5 Gate diversity PST discovers ∼1,200 1,200 unique gates per dataset (out of 19,683), with effective diversity ∼1,050 1,050, representing 70×70× greater vocabulary utilization than binary’s fixed 16 (Table 13). Ternary redundancy is 28-31% vs. binary’s 99.1%, reflecting the two strategies: binary achieves expressiveness through dense repetition; ternary through gate specialization. Table 13: Gate diversity (both architectures, all datasets). 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% C.2.6 Hardening gap comparison Figure 13 compares the hardening gap across all datasets. Both architectures achieve small gaps under discrete-input training (binary ≤3.19≤ 3.19%, ternary ≤8.31≤ 8.31%). The near-zero ternary gaps on Moons (0.00%), Gaussians (0.31%), and Ring Sector (0.38%) validate the fidelity of the PST hardening procedure. Figure 13: Hardening gap (all datasets). Both architectures achieve small gaps. The ternary gap is elevated on Circles and Spirals. Appendix D Polynomial Representations for Boolean Logic Functions Let PnP_n denote the set of real multi-linear polynomials that represent Boolean functions over n variables. Given real multi-linear polynomials p,q∈Pnp,\,q∈ P_n, define the binary operators meet (∧ ) and join (∨ ): p∧q:=−12+12p(x)+12q(x)+12p(x)q(x),p∨q:=12+12p(x)+12q(x)−12p(x)q(x),p q:=- 12+ 12p(x)+ 12q(x)+ 12p(x)q(x), p q:= 12+ 12p(x)+ 12q(x)- 12p(x)q(x), and define the unary operator complementation (¬ ): ¬p:=−p(x). p:=-p(x). Then (Pn,∨,∧,¬,⊥,⊤)(P_n,\, ,\, ,\, ,\, ,\, ) is a Boolean algebra with the top element being the constant polynomial p(x)=1p(x)=1 and the bottom element being the constant polynomial p(x)=−1p(x)=-1. For two-input Boolean functions (n=2n=2), the Boolean algebra of real multi-linear polynomials is generated by the set x1,x2\x_1,\,x_2\, meaning one can reconstruct all Boolean functions using the operations meet, join, and complement applied to the set of generators. D.1 The Boolean Group The exclusive not-or111Typically a Boolean group derived from a Boolean algebra uses symmetric difference (exclusive or) for group multiplication. If we instead defined True as −1-1 and False as +1+1 (intepreted as the square roots of unity), then XOR would be the intuitive choice satisfying p⊕q:=p(x)q(x)p q:=p(x)q(x). (XNOR) of elements in the Boolean algebra can be defined as: p⊙q:=p(x)q(x).p q:=p(x)q(x). The structure (Pn,⊙,⊤)(P_n,\, ,\, ) is a finite abelian group, with the constant polynomial p(x)=1p(x)=1 serving as the identity element and each element acting as its own inverse, p⊙p=⊤p p= . This subtle notion allows us to employ the results of Fourier analysis on finite groups (see: terras1999fourier). We restrict the remaining analysis to the case where n=2n=2. Define the character homomorphism :P2→ℝX:P_2 as the trivial mapping p↦p(x)p p(x) for p∈P2p∈ P_2, x∈−1, 12x∈\-1,\,1\^2. Characters satisfy the condition (p⊙q)=(p)(q)X(p q)=X(p)X(q) for all p,q∈P2p,\,q∈ P_2. Define an inner product on the space of characters as: ⟨φ,ψ⟩=14∑x∈−1, 12φ(x)ψ(x). ,\,ψ = 14 _x∈\-1,\,1\^2 (x)ψ(x). (D.1) We are interested in identifying orthonormal functions with respect to (D.1) that form the basis for all representations of Boolean functions. Consider the character functions 1,x1,x2,x1x2⊂(P2)\1,\,x_1,\,x_2,\,x_1x_2\ (P_2). These functions form an orthonormal basis for the characters of P2P_2. Enumerating the basis functions such that: φ0(x)=1,φ1(x)=x1,φ2(x)=x2,φ3(x)=x1x2, _0(x)=1, _1(x)=x_1, _2(x)=x_2, _3(x)=x_1x_2, we have: ⟨φi,φj⟩= 1,i=j, 0,i≠j. _i,\, _j = cases\;1, &i=j,\\ \;0, &i≠ j. cases Furthermore, any p∈P2p∈ P_2, (p)X(p) can be uniquely represented as a linear combination of these basis functions. Given p∈P2p∈ P_2, the Fourier coefficients are determined by: wi=⟨(p),φi⟩,w_i= (p),\, _i , and we have then: p(x)=∑i=14wiφi(x).p(x)= _i=1^4w_i _i(x).