# The Information Theory of Similarity

arXiv: https://arxiv.org/abs/2512.00378 · HTML: https://mlsanity.com/paper/2512.00378/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 15 references that are in the map.
- First posted on arXiv 29 Nov 2025.

## Builds on (most cited first, 2 of 2)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [REWA: A General Theory of Witness-Based Similarity](https://mlsanity.com/paper/2511.19998/) (2025)

## Abstract (arXiv)

We establish a precise mathematical equivalence between witness-based similarity systems (REWA) and Shannon's information theory. We prove that witness overlap is mutual information, that REWA bit complexity bounds arise from channel capacity limitations, and that ranking-preserving encodings obey rate-distortion constraints. This unification reveals that fifty years of similarity search research -- from Bloom filters to locality-sensitive hashing to neural retrieval -- implicitly developed information theory for relational data. We derive fundamental lower bounds showing that REWA's O(Delta-2 log N) complexity is optimal: no encoding scheme can preserve similarity rankings with fewer bits. The framework establishes that semantic similarity has physical units (bits of mutual information), search is communication (query transmission over a noisy channel), and retrieval systems face fundamental capacity limits analogous to Shannon's channel coding theorem.