Introduction
The integration of symbolic logic and deep learning remains a central challenge in Artificial Intelligence. While symbolic logic excels at human-readable reasoning, deep learning thrives on continuous, gradient-based optimization. Bridging these worlds requires a way to map discrete logical formulae into a smooth, continuous vector space. Previous attempts at creating "semantic embeddings" often failed at the "inversion" problem: while a formula could be turned into a vector, the reverse process—turning a vector back into a valid, meaningful formula—was unreliable.
This paper introduces LogicGVAE, a Graph Variational Autoencoder designed to create an invertible and semantic-preserving latent space for logical formulae. By treating logic as structured data and applying syntactic constraints, the researchers enable bidirectional movement between symbols and vectors.
LogicGVAE Architecture
The LogicGVAE framework treats logical formulae as Abstract Syntax Trees (ASTs) and is built upon three primary pillars:
- Asynchronous Encoding: Standard Graph Neural Networks (GNNs) typically update all nodes simultaneously. In contrast, LogicGVAE employs an asynchronous scheme where messages flow through the tree according to its natural dependency structure (top-down or bottom-up). The authors evaluated three encoder architectures: Gated Recurrent Units (GRU), Graph Convolutional Networks (GCN), and Graph Attention Networks (GAT).
- Syntactic-Constrained Decoding: To prevent the generation of invalid "gibberish," the decoder is constrained by the formal rules of logic. For example, if the model selects an "AND" ($\wedge$) operator, the architecture is hard-coded to require exactly two child sub-formulae. This inductive bias ensures that every point in the latent space maps to a syntactically valid tree.
- Semantic Conditioning (CVAE): To ensure the latent space reflects meaning rather than just structure, the authors utilize a Conditional VAE (CVAE) framework. They compute a "Boolean kernel"—a measure of truth-value consistency across assignments—which serves as a context vector to guide the embedding process toward semantically similar groupings.
Experimental Setup
The model was evaluated using synthetic datasets of propositional logic formulae. These datasets were generated using a recursive scheme with varying numbers of variables ($n \in \{3, 4, 5\}$). The training set consisted of 4,000 unique formulae, while testing was conducted on a separate set of 300 formulae.
Results and Discussion
The experimental results highlight the effectiveness of combining structural constraints with attention-based encoding.
Encoder Performance and Fidelity
As shown in the results, the Graph Attention Network (GAT) consistently outperformed GCN and GRU encoders. For formulas with 5 variables, the GAT-based VAE achieved a reconstruction accuracy of 93.92%, which rose to 95.42% when considering the most frequent decoded output. The authors attribute this success to the attention mechanism's ability to capture local substructure patterns within logical trees.
The Role of Constraints and Semantics
A critical finding was the necessity of syntactic constraints. Removing these constraints caused reconstruction accuracy to drop significantly (from ~90% to ~25-30%), demonstrating that architectural inductive bias is more powerful than learning syntax from data alone. Furthermore, the CVAE framework successfully grouped semantically equivalent formulas (e.g., $A \wedge B$ and $B \wedge A$) together, despite their different structural representations.
Latent Space Smoothness
Qualitative analysis using spherical linear interpolation (slerp) revealed a "smooth" latent space. Moving between two points resulted in logical, incremental changes to the formulas, rather than erratic jumps between unrelated structures. The models also maintained high validity, ensuring that sampled vectors almost always correspond to "legal" logical expressions.
Conclusion and Future Work
LogicGVAE provides a robust "proof of concept" for invertible, semantic-preserving embeddings. However, challenges remain regarding scalability. The current reliance on truth tables for semantic calculation leads to exponential complexity ($2^n$), limiting the model to approximately 5 variables.
Future research will explore hierarchical learning to manage larger formula trees and aim to extend this framework to Linear Temporal Logic (LTL). Embedding LTL is particularly desirable for robotics and autonomous systems, where it is used to specify complex temporal behaviors that would benefit from continuous optimization.
Summary updated