Semantic Identity Compression: Exact Zero-Error Laws, Rate-Distortion, and Neurosymbolic Necessity
This work addresses a foundational issue in neurosymbolic AI by showing that symbolic identity mechanisms are necessary complements to non-injective semantic representations, with implications for system design.
The paper tackles the problem of identity ambiguity in neural embeddings due to compression, proving exact information-theoretic bounds on the additional bits needed to recover precise identities, with results including a tight converse, scaling laws, and rate-distortion tradeoffs. Key findings include a fixed-length converse of L ≥ log₂ A_π and an explicit distortion floor.
Symbolic systems operate over exact identities: variables denote specific objects, pointers target precise memory locations, and database keys refer to singular records. Neural embeddings generalize by compressing away semantic detail, but this compression creates collision ambiguity: multiple distinct entities can share the same representation value. We characterize exactly how much additional information must be supplied to recover precise identity from such representations. The answer is controlled by a single combinatorial object: the collision-fiber geometry of the representation map $Ï$. Let $A_Ï=\max_u |Ï^{-1}(u)|$ be the largest collision fiber. We prove a tight fixed-length converse $L \ge \log_2 A_Ï$, an exact finite-block scaling law, a pointwise adaptive budget $\lceil \log_2 |Ï^{-1}(u)|\rceil$, and the rate-distortion tradeoff with an explicit distortion floor when identity bits are withheld. The same fiber geometry determines query complexity and canonical structure for distinguishing families. Because this residual ambiguity is structural rather than representation-specific, symbolic identity mechanisms (handles, keys, pointers, nominal tags) are the necessary system-level complement to any non-injective semantic representation. All main results are machine-checked in Lean 4. Keywords: semantics-aware compression, zero-error coding, neurosymbolic systems, learned representations, side information