Technical Summary: Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks

1. Problem Statement

Monitoring safety specifications in real-time using Signal Temporal Logic (STL) presents a fundamental "causal gap." Standard offline STL monitors require future signal values to evaluate bounded temporal operators (e.g., $\square_{[0,5]} \mu$), which causal, online monitors cannot access. While Recurrent Neural Networks (RNNs) like LSTMs and GRUs have been used to bridge this gap by learning spatio-temporal patterns to predict verdicts from partial trajectories, they lack structural guarantees regarding input degradation.

In safety-critical systems, sensor inputs may degrade or become unavailable. Standard RNNs, operating in continuous domains, offer no mechanism to distinguish between "determined" and "uncertain" states. Consequently, a dropped input or indeterminate predicate can cause an RNN to silently flip a verdict from "safe" to "unsafe" (or vice versa), rather than gracefully degrading to an "unknown" state. There is a need for a learned monitor that combines the predictive power of neural networks with the conservative uncertainty propagation inherent in formal logic under partial information.

2. Methodology: The R-DTLGN Architecture

The authors propose the Recurrent Differentiable Ternary Logic Gate Network (R-DTLGN), a recurrent architecture that operates natively in Kleene's three-valued logic domain $\mathbb{T} = \{-1, 0, +1\}$, where $0$ explicitly represents "unknown."

Core Components

• Ternary Logic Domain: The network utilizes Kleene's strong three-valued logic, where logical connectives (AND, OR, NOT) propagate the "unknown" value conservatively. For instance, $True \land Unknown = Unknown$.
• Polynomial Surrogate Training (PST): To enable differentiable training of discrete logic gates, the network employs PST. Each neuron is represented as a degree-$(2,2)$ polynomial with 9 learnable coefficients. This allows the network to be trained via gradient descent on continuous values in $[-1, 1]$.
• Recurrent Cell Structure: The R-DTLGN cell ingests current predicate values and a previous hidden state, processes them through $L$ layers of ternary PST gates, and produces an updated hidden state and an output verdict. The hidden state is initialized to the "all-unknown" state $(0, \dots, 0)$.
• Hardening and Distillation: At inference, the soft polynomial network is "hardened" into a discrete ternary logic circuit. The authors introduce a trajectory distillation method for recurrent settings: instead of rounding neurons independently (which causes global incoherence), they perform a greedy coordinate-descent over a target vocabulary of gates to minimize verdict disagreement on a calibration set.

Gate Vocabularies and Orderings

The analysis relies on two partial orderings on the ternary domain:

1. Numerical Ordering ($\leq$): $-1 \leq 0 \leq +1$. Gates monotone under this ordering (NM) ensure stable recurrent dynamics during training.
2. Information Ordering ($\sqsubseteq$): $0 \sqsubseteq -1$ and $0 \sqsubseteq +1$ (with $-1$ and $+1$ incomparable). Gates monotone under this ordering (IM) guarantee principled degradation: replacing a determined input with unknown can only make the output less determined, never flip it to a wrong value.

The authors identify an intersection vocabulary ($NM \cap IM$) containing 17 non-constant gates (including AND and OR) that satisfy both stability and degradation guarantees.

3. Key Contributions

A. Architecture and Hardening

The R-DTLGN is the first recurrent architecture to couple learned temporal prediction with formal degradation guarantees rooted in three-valued logic. The authors introduce a novel two-phase hardening routine:

1. Phase 1: Distillation using the full set of numerically monotone (NM) gates to ensure stable dynamics.
2. Phase 2: Attempting to replace NM-only gates with $NM \cap IM$ candidates to extend degradation guarantees, accepting swaps only if accuracy loss is minimal.

B. Degradation Guarantees

The paper proves that R-DTLGN cells composed of information-monotone (IM) gates satisfy two critical properties:

1. Principled Abstention: If all inputs are unknown, the output is unknown. The monitor never fabricates a verdict from absent evidence.
2. Input Certainty Monotonicity: Replacing a determined input with unknown can only make the output less determined (or keep it the same); it cannot flip a determined verdict to the opposite value.
   These guarantees are structural invariants of the architecture, not artifacts of training.

C. Realizability Bounds

The authors derive a formula-driven specification for the network's hidden state dimension. Given a bounded STL formula $\varphi$, they define a state complexity $B(\varphi)$ based on the temporal operators' intervals and nesting depth.

• Theorem: Any R-DTLGN capable of monitoring $\varphi$ requires a hidden state dimension $S \geq B(\varphi)$.
• This replaces hyperparameter search with a direct calculation based on the STL formula's structure. For example, an "Until" operator over an interval of width $w$ requires $2w$ state bits.

D. Label Construction Pipelines

The paper evaluates two label construction strategies:

• Compute-then-Quantize (CtQ): Evaluates robustness on continuous signals, then quantizes. Targets true verdicts but may force the network to commit on insufficient information.
• Quantize-then-Compute (QtC): Quantizes predicates to ternary first, then evaluates robustness. Targets only structurally recoverable verdicts, aligning the training objective with the degradation guarantees.

4. Experimental Results

The R-DTLGN was evaluated on 816 trajectories from the D4RL PointMaze navigation environment against 6 bounded STL specifications.

• Bridging the Causal Gap: The R-DTLGN significantly outperformed the causal baseline (STLCG++ restricted to available data), improving accuracy by 33–38 percentage points on specific tasks. It matched or exceeded the performance of a vanilla RNN (Elman network) on 4 of 6 specifications.
• Hardening Performance: The two-phase distillation successfully converted soft networks to discrete circuits. While some specifications showed a "hardening gap" (accuracy drop), others showed the hardened circuit outperforming the soft version, suggesting distillation acts as a regularizer.
• Degradation Behavior:
  • Verdict Preservation: Under predicate dropout, the QtC-hardened R-DTLGN maintained perfect or near-perfect preservation of verdict signs (up to 100% on some specs), whereas the RNN showed steady degradation.
  • Lattice Monotonicity: The QtC pipeline achieved 93.0% mean compliance with input-certainty monotonicity across all predicate subsets. The CtQ pipeline achieved 85.4%, reflecting the trade-off between accuracy and structural safety.
  • Abstention: The QtC circuit correctly transitioned to "unknown" (abstention) as inputs were removed, while the RNN and CtQ circuits failed to abstain, often producing incorrect determined values.

5. Significance and Claims

The paper claims the R-DTLGN is the first recurrent architecture that couples learned temporal prediction with formal degradation guarantees rooted in three-valued logic.

• Structural Assurance: Unlike standard RNNs where degradation behavior depends on learned weights and training augmentation (e.g., dropout), the R-DTLGN's robustness to input uncertainty is guaranteed by its architecture (the choice of IM gates).
• Complementary Capabilities: The system offers two non-overlapping capabilities: (1) prediction capability to bridge the causal gap using learned patterns, and (2) degradation guarantees to ensure robustness when input information is lost.
• Design Efficiency: The realizability bound allows the network size to be derived directly from the STL formula, removing the need for extensive hyperparameter search for hidden state dimensions.

The authors acknowledge limitations, noting that the two-phase distillation does not fully close the hardening gap for all specifications and that the degradation guarantees strictly require information-monotone gates. Future work is suggested in gated variants for longer horizons and multi-trit encodings.