sqsketch

Compare two probability or count profiles from a fixed number of bytes, however large the alphabet.

from sqsketch import Sketch

a = Sketch.from_dict({"apple": 12, "pear": 3, "quince": 1})
b = Sketch.from_dense(probability_vector, D=1024)

a.similarity(b)            # Bhattacharyya coefficient
a.hellinger(b)             # Hellinger distance
a.confidence_interval(b)   # computed from the two sketches alone, without the profiles
a.kl_lower_bound(b)        # certified: the KL divergence is at least this
a.merge(b)                 # a sketch of the pooled profile

Each sketch is D numbers. No vocabulary, no codebook, no inverted index; encoding is one pass over the items. The accuracy depends on D alone — the number of possible items never enters the error, so the same width serves an alphabet of a thousand or of 4³¹.

pip install -e .          # numpy and scipy, nothing else
pytest                    # 26 tests, one per claim in the paper, ~18 s

Should you use it? One number decides

The thing you are already doing — keeping the k heaviest items and lumping the rest into one bucket — is the competitor. Top-k logprobs, frequent-item tables, truncated term vectors are all this. What truncation cannot represent is the mass it throws away, so measure that:

from sqsketch.baselines import tail_mass
tail_mass(your_profiles, k)      # mass outside the top k, at your byte budget

The effective support 1/Σp² is not the predictor: across the sweep that produced this table it ranged from 4 to 800 000 without changing the verdict. Measured on real data, the criterion called 14 of 14 cases correctly:

Value-weighted flows are dominated by a handful of addresses; activity counts are spread over tens of thousands. Same data, opposite verdicts — which is why the criterion is worth measuring rather than guessing.

What it will not do

• Exact top-1 retrieval among near-identical neighbours. Accuracy is governed by the gap between the true nearest neighbour and the runner-up, against the noise floor √(2/D). On a real text corpus that gap is ~0.03 and recall@1 falls apart; recall@10 stays at 97 %. Use Index.search as a candidate generator and rerank the shortlist exactly.
• Sampling-noise-dominated histograms. If each profile is a small sample from a much larger alphabet, Hellinger between two empirical histograms mostly measures sample overlap. That is a property of the statistic, not of the sketch, but it rules the approach out there.
• Upper-bounding the KL divergence. kl_lower_bound is one-sided by construction: it certifies that two profiles are far apart, never that they are close.
• Forecasting anything. It measures a distance between two distributions. It has no notion of time, and confers no predictive edge.

Accuracy

Unbiased at every width, with variance σ²/D where σ² = 1 + BC² − 2⟨Q,P⟩ < 2 for every pair and every alphabet size, so the standard error is at most √(2/D):

confidence_interval is asymptotic in D and under-covers below D ≈ 256; above that it is valid and deliberately conservative, since its width is calibrated for the raw inner product while similarity returns the lower-variance self-normalised cosine.

How to audit this

Every claim is checked twice: as a unit test, and as an end-to-end reproduction.

pytest                                    # 26 tests, one per proposition
cd experiments
python reproduce.py > outputs/reproduce_output.txt        # 14 sections
python survey.py   > outputs/survey_output.txt            # the decision criterion
python verify.py                                          # 36 checks, 5 batteries

verify.py is the part worth knowing about. Beyond checking the mathematics, battery 3 extracts every experimental number printed in the paper and requires it to appear in a script's output. The manuscript this work supersedes reported a correlation from one column of a table as though it came from another; that class of error is invisible to proofreading, so it is checked mechanically. It currently matches 142 of 142.

Repository

sqsketch/        the library: core.py, hashing.py, baselines.py
                 adapters: genomics.py (k-mers, FASTA, MinHash baselines), llm.py
tests/           one test per proposition
paper/           square_root_sketch.tex, and the superseded v1 draft it retracts
experiments/     everything that produces a number in the paper, plus verify.py
data/            reference genomes, downloaded on demand (not in git)

The paper

Norm-Invariance in Vector-Symbolic Encodings of Probability Distributions — why the square root is the only exponent that makes the error independent of the alphabet size, what the vector's magnitude therefore cannot encode, and how to read one bit.

It carries three explicit retractions of earlier claims, an eight-item limitations section, and 20 references each checked against the publisher record. The variance formula it uses is not new and is attributed throughout to Li, Hastie and Church (2006).

Citing

@software{sghairi2026sqsketch,
  author  = {Sghairi, Abderrahmane},
  title   = {sqsketch: alphabet-independent sketches of discrete
             probability and count profiles},
  year    = {2026},
  version = {0.2.0},
  doi     = {10.5281/zenodo.22214969},
  url     = {https://github.com/riscoss63/sqsketch}
}

Licence

MIT for the code. The Zenodo record is deposited under the same terms; note that the manuscript in paper/ is part of the same deposit.