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                    # 40 tests, one per claim in the paper, ~20 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.

A worked case: telling that a served language model changed

A next-token distribution is peaked — median effective support around 10 — but long-tailed: the top-64 holds only 82 % of the mass on GPT-2. A truncated top-k fingerprint is therefore blind, by construction, to any change that lives in that tail, and that is where serve-time filtering and weight quantisation act.

Measured over 1500 positions of real text per model, with changes applied to the weights where a deployment would apply them. True distance computed on the full softmax:

The nucleus filter is the case that matters. It moves the output distribution by 0.149 while leaving the most likely token unchanged at every position and perplexity unchanged to two decimals — so neither output diffing nor a log-loss sees it. A top-k fingerprint reports half the true value and does not converge: four times the memory moves it from 0.057 to 0.078.

It holds across models, and the size of the advantage tracks the tail mass exactly as the criterion above predicts — a sharper model with a lighter tail gives truncation less to miss:

Where nothing changed, nothing is reported: rounding Qwen's already-bf16 weights to bfloat16 gives exactly 0.0000 from every method.

from sqsketch.llm import fingerprint, Fingerprint

ref = fingerprint(model, tokenizer, probe_texts, D=256)
ref.save("gpt2-fp32.npz")           # 1 KB per position; keep it for years
...
Fingerprint.load("gpt2-fp32.npz").compare(fingerprint(served_model, tokenizer, probe_texts))
# mean_hellinger, positions_moved, aggregate_kl_lower_bound, ...

The probe texts are hashed into the metadata, so two fingerprints refuse to be compared unless they saw the same prompts. experiments/benchmark_llm.py reproduces the tables.

Measured against sourmash, on real sequencing reads

Eight human gut metagenomes from the ENA, 400 000 reads each, 17–71 M distinct canonical 21-mers per run. Both arms read the same truncated files with no filtering, and each method is scored against the quantity it is defined to estimate — sourmash reports angular similarity on raw abundances (the chord transformation), sqsketch estimates the Bhattacharyya coefficient (the Hellinger transformation). On these runs those two targets order the 28 pairs at a Spearman of only 0.37, so scoring both against one of them would measure the choice of transformation rather than the quality of the summary.

The sketch's error lands below the predicted floor at all four budgets and halves as D quadruples; sourmash's is flat. But two results cut the other way and are reported in the paper with the same weight: retrieval of the related samples does not discriminate between the two methods, and ranking all pairs is poor for both — the true coefficients here have median 0.0042, far under the floor. Restricted to pairs above √(2/D) the Spearman is 0.783 / 0.933 / 0.988 / 0.987.

Reproduce with benchmark_reads_controlled.py; diagnose_reads.py produces the noise-floor analysis.

What it will not do

• Raw reads without abundance filtering. 70–98 % of distinct k-mers in a shallow run are seen exactly once and are overwhelmingly sequencing error. The square-root transform gives a k-mer seen once weight 1 against 10² for one seen 10⁴ times, where chord gives 1 against 10⁴ — the property that makes Hellinger valuable on ecological data is the one that makes it absorb error here. Filter first. This is a property of the geometry, not the sketch: it applies to the exact computation too.
• 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. Two conditions have to hold, not one: the tail-mass criterion says whether a sketch beats truncation at representing a distribution; ordering the results also needs the spread of the true coefficients to exceed √(2/D). On the metagenomes above the two disagree — tail mass 0.992 recommends the sketch, an interquartile spread of 0.0945 against a floor of 0.0884 at 1 KB says the full ranking is not recoverable 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                                    # 40 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

# these need downloaded data (~700 MB) and an installed sourmash
python fetch_metagenomes.py                               # 8 ENA gut metagenomes
python benchmark_reads_controlled.py > outputs/reads_output.txt
python diagnose_reads.py             > outputs/diagnose_output.txt

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 202 of 202, and names the one figure it exempts: a recall number the paper explicitly retracts, which must not be reproducible.

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 and sequencing runs, 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.