# REWA: A General Theory of Witness-Based Similarity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 5 references that are in the map.
- First posted on arXiv 25 Nov 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)

## Built on by (most cited first, 1 of 1)

- [The Information Theory of Similarity](https://mlsanity.com/paper/2512.00378/) (2025)

## Abstract (arXiv)

We present a universal framework for similarity-preserving encodings that subsumes all discrete, continuous, algebraic, and learned similarity methods under a single theoretical umbrella. By formulating similarity as functional witness projection over monoids, we prove that [ O!left(frac1Delta2log Nright) ] encoding complexity with ranking preservation holds for arbitrary algebraic structures. This unification reveals that Bloom filters, Locality Sensitive Hashing (LSH), Count-Min sketches, Random Fourier Features, and Transformer attention kernels are instances of the same underlying mechanism. We provide complete proofs with explicit constants under 4-wise independent hashing, handle heavy-tailed witnesses via normalization and clipping, and prove [ O(log N) ] complexity for all major similarity methods from 1970-2024. We give explicit constructions for Boolean, Natural, Real, Tropical, and Product monoids, prove tight concentration bounds, and demonstrate compositional properties enabling multi-primitive similarity systems.