The Information Theory of Similarity Witness Overlap as Mutual Information and the Capacity Limits of Semantic Search
Nikit Phadke · 2025
Read The Information Theory of Similarity Witness Overlap as Mutual Information and the Capacity Limits of Semantic Search by Nikit Phadke (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00378.txt.
Introduction
Semantic search ranks documents by meaning, and witness-based systems are one way to build it. Nikit Phadke establishes a mathematical equivalence between such systems and Shannon's information theory in 2025. The system studied is called REWA, built on similarity witnesses.
Phadke proves that witness overlap is mutual information, a core quantity in information theory. REWA's bit complexity bounds are shown to arise from channel capacity limits, and ranking-preserving encodings obey rate-distortion constraints. Grounding a practical search method in classic theory clarifies its capacity limits and tells builders what no encoding can beat. Shannon's theory also sets the ceiling that no search encoding can exceed. Equivalence proofs like this one turn engineering intuition into settled mathematics.
Catalog record
| CREATOR | Nikit Phadke |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00378
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Information Theory of Similarity Witness Overlap as Mutual Information and the Capacity Limits of Semantic Search Nikit Phadke Abstract 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 ( Δ − 2 log N ) 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. 1 Introduction In 1948, Claude Shannon established that communication has fundamental limits [ 1 ] . The channel capacity C bounds the rate at which information can be reliably transmitted; no coding scheme, however clever, can exceed this limit. This insight unified telegraphy, radio, and all future communication systems under a single mathematical framework. We prove that similarity search obeys an analogous law. The REWA framework (Rank-Embedding Witness Approximators) established that diverse similarity methods—Bloom filters, locality-sensitive hashing, random projections, neural attention—share a common structure: similarity arises from witness overlap [ 2 ] . Two concepts are similar when they share witnesses; encoding preserves rankings when the overlap gap exceeds collision noise. This paper reveals that REWA is information theory. Specifically: (i) Witness overlap equals mutual information. The REWA overlap \Delta(x,y)=|W(x)\cap W(y)| is monotonically equivalent to I(W_{x};W_{y}) , the mutual information between witness distributions. (ii) Bit complexity equals inverse channel capacity. The REWA bound m=O(\Delta^{-2}\log N) arises from Shannon’s channel coding theorem applied to the “hash channel.” (iii) Ranking preservation equals rate-distortion optimization. The minimum bits required to preserve top- k rankings is characterized by the rate-distortion function for ranking loss. These equivalences are not analogies—they are mathematical identities. The implication is profound: REWA bounds are optimal . Just as no communication system can exceed channel capacity, no similarity encoding can beat the witness-information limits. 1.1 Contributions • The Isomorphism Theorem ( Theorem 4.1 ): Formal proof that witness overlap and mutual information are monotonically equivalent. • The Capacity Theorem ( Theorem 5.2 ): Derivation of REWA bit complexity from channel coding principles. • The Rate-Distortion Theorem ( Theorem 6.2 ): Characterization of ranking-preserving compression via rate-distortion theory. • The Dictionary ( Table 1 ): Complete translation between REWA concepts and information-theoretic primitives. • Optimality Results ( Theorem 8.1 ): Proof that REWA bounds cannot be improved. 1.2 Implications If REWA contradicted Shannon, REWA would be wrong. Because REWA is Shannon, we obtain: • Fundamental limits : Every similarity search algorithm must obey capacity bounds. • Design principles : Optimize witness extraction (the signal), not hash functions (the channel). • Unification : All retrieval methods are instantiations of the same information-theoretic structure. 2 Preliminaries 2.1 Information-Theoretic Foundations Definition 2.1 (Entropy) . For a discrete random variable X with probability mass function p(x) , the Shannon entropy is: H(X)=-\sum_{x}p(x)\log p(x) (1) Definition 2.2 (Mutual Information) . For jointly distributed random variables (X,Y) with marginals p_{X},p_{Y} and joint distribution p_{XY} : I(X;Y)=H(X)+H(Y)-H(X,Y)=\sum_{x,y}p_{XY}(x,y)\log\frac{p_{XY}(x,y)}{p_{X}(x)p_{Y}(y)} (2) Definition 2.3 (Channel Capacity) . A discrete memoryless channel with input X , output Y , and transition probabilities p(y|x) has capacity: C=\max_{p(x)}I(X;Y) (3) Definition 2.4 (Rate-Distortion Function) . For source X , reconstruction \hat{X} , and distortion measure d(x,\hat{x}) : R(D)=\min_{p(\hat{x}|x):\mathbb{E}[d(X,\hat{X})]\leq D}I(X;\hat{X}) (4) 2.2 REWA Foundations Definition 2.5 (Witness Sets) . Each concept v\in V is associated with a finite witness set W(v)\subseteq\Omega , where \Omega is the witness universe. Definition 2.6 (Witness Overlap) . The overlap between concepts u,v is: \Delta(u,v)=|W(u)\cap W(v)| (5) Definition 2.7 (REWA Encoding) . A REWA encoder maps concepts to binary codes B:V\to\{0,1\}^{m} such that expected binary similarity is monotone in witness overlap: \mathbb{E}[\langle B(u),B(v)\rangle]=\alpha\cdot\Delta(u,v)+\beta (6) for constants \alpha>0 , \beta\geq 0 . Definition 2.8 (Overlap Gap Condition) . For query q with true neighborhood N_{k}(q) , there exists \Delta>0 such that: \min_{u\in N_{k}(q)}\Delta(q,u)-\max_{w\notin N_{k}(q)}\Delta(q,w)\geq\Delta (7) 3 The Probabilistic Witness Space The key insight enabling the Shannon-REWA bridge is treating concepts not as fixed objects but as stochastic sources of witness information. Definition 3.1 (Concept as Random Variable) . Let \Omega be the universe of all possible witnesses. A data point x\in\mathcal{X} defines a random variable W_{x} distributed over \Omega with probability mass function p_{x}(w) . Different REWA instantiations correspond to different witness distributions: Example 3.2 (Boolean REWA) . For set-based witnesses S_{x}\subseteq\Omega : p_{x}(w)=\frac{1}{|S_{x}|}\mathbf{1}[w\in S_{x}] (8) This is the uniform distribution over the witness set. Example 3.3 (Weighted REWA) . For weighted witnesses with importance scores \alpha_{x}(w) : p_{x}(w)=\frac{\alpha_{x}(w)}{\sum_{w^{\prime}}\alpha_{x}(w^{\prime})} (9) Example 3.4 (Measure-Theoretic REWA) . For continuous witness measures \mu_{x} : p_{x}(w)=\frac{d\mu_{x}}{d\nu}(w) (10) where \nu is a base measure on \Omega . Definition 3.5 (Witness Entropy) . The information content of a concept x is its Shannon entropy: H(W_{x})=-\sum_{w\in\Omega}p_{x}(w)\log p_{x}(w) (11) Remark 3.6 . For uniform witnesses over set S_{x} , we have H(W_{x})=\log|S_{x}| . The entropy measures the “semantic volume” of the concept—how many bits are required to specify a typical witness. 4 Similarity is Mutual Information We now establish the fundamental equivalence between witness overlap and mutual information. Theorem 4.1 (The Overlap-Information Isomorphism) . Let x,y be concepts with witness distributions p_{x},p_{y} over universe \Omega . Define the joint witness process (W_{x},W_{y}) with joint distribution: p_{xy}(w,w^{\prime})=p_{x}(w)\cdot p_{y}(w^{\prime})\cdot\kappa(w,w^{\prime}) (12) where \kappa(w,w^{\prime})=\mathbf{1}[w=w^{\prime}] for exact matching. Then the mutual information I(W_{x};W_{y}) is a monotonically increasing function of the normalized overlap: I(W_{x};W_{y})=f\left(\frac{\Delta(x,y)}{|W(x)\cup W(y)|}\right) (13) for a strictly increasing function f:[0,1]\to\mathbb{R}_{\geq 0} with f(0)=0 . Proof. Consider Boolean REWA with uniform witness distributions over sets A=W(x) and B=W(y) . The individual entropies are: \displaystyle H(W_{x}) \displaystyle=\log|A| (14) \displaystyle H(W_{y}) \displaystyle=\log|B| (15) For the joint entropy, we consider the support of the joint distribution. Two witnesses “match” when w=w^{\prime} and both w\in A and w\in B , i.e., when w\in A\cap B . The joint entropy over the union is: H(W_{x},W_{y})=\log|A\cup B| (16) Therefore, the mutual information is: \displaystyle I(W_{x};W_{y}) \displaystyle=H(W_{x})+H(W_{y})-H(W_{x},W_{y}) (17) \displaystyle=\log|A|+\log|B|-\log|A\cup B| (18) \displaystyle=\log\frac{|A|\cdot|B|}{|A\cup B|} (19) By inclusion-exclusion, |A\cup B|=|A|+|B|-|A\cap B|=|A|+|B|-\Delta , so: I(W_{x};W_{y})=\log\frac{|A|\cdot|B|}{|A|+|B|-\Delta} (20) Define the Jaccard index J=\frac{\Delta}{|A\cup B|}=\frac{\Delta}{|A|+|B|-\Delta} . Then: I(W_{x};W_{y})=\log\frac{|A|\cdot|B|}{|A|+|B|}+\log\frac{1}{1-J\cdot\frac{|A|+|B|}{|A|+|B|}} (21) For the symmetric case |A|=|B|=L : I(W_{x};W_{y})=\log\frac{L}{2}+\log\frac{2L}{2L-\Delta}=\log\frac{L^{2}}{2L-\Delta} (22) Taking the Taylor expansion for small overlap ratio \rho=\Delta/(2L) : I(W_{x};W_{y})\approx\log L-\log 2-\log(1-\rho)\approx\log L-\log 2+\rho+O(\rho^{2}) (23) Thus I(W_{x};W_{y}) is monotonically increasing in \Delta , with: \frac{\partial I}{\partial\Delta}=\frac{1}{2L-\Delta}>0 (24) ∎ Corollary 4.2 (Gap Preservation) . The REWA overlap gap condition \Delta_{neighbor}-\Delta_{far}\geq\Delta implies an information gap: I(W_{q};W_{neighbor})-I(W_{q};W_{far})\geq\frac{\Delta}{2L-\Delta_{neighbor}}>0 (25) Remark 4.3 . This theorem reveals why witness overlap is the “right” similarity measure: it directly quantifies the mutual information between concepts. Two things are similar precisely because knowing one tells you about the other—the fundamental information-theoretic definition of dependence. 5 Hashing as a Noisy Channel The REWA encoding process—mapping witnesses to bits via hash functions—is mathematically equivalent to transmitting information over a noisy channel. Definition 5.1 (The Hash Channel) . Define a discrete memoryless channel \mathcal{C} as follows: • Input : A