Metadata-Version: 2.4
Name: sqsketch
Version: 0.3.0
Summary: Fixed-size, abundance-preserving sketches of count profiles over unbounded alphabets
Author: Abderrahmane Sghairi
License: MIT License
        
        Copyright (c) 2026 Abderrahmane Sghairi
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Homepage, https://github.com/riscoss63/sqsketch
Project-URL: Paper, https://github.com/riscoss63/sqsketch/tree/main/paper
Project-URL: DOI, https://doi.org/10.5281/zenodo.22214969
Keywords: sketching,Bhattacharyya,Hellinger,random projection,hyperdimensional computing,vector symbolic architectures
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.21
Requires-Dist: scipy>=1.7
Provides-Extra: experiments
Requires-Dist: scikit-learn>=1.0; extra == "experiments"
Requires-Dist: torch>=2.0; extra == "experiments"
Requires-Dist: transformers>=4.30; extra == "experiments"
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"
Dynamic: license-file

# sqsketch

[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.22214969.svg)](https://doi.org/10.5281/zenodo.22214969)
[![tests](https://github.com/riscoss63/sqsketch/actions/workflows/ci.yml/badge.svg)](https://github.com/riscoss63/sqsketch/actions/workflows/ci.yml)
[![licence: MIT](https://img.shields.io/badge/licence-MIT-blue.svg)](LICENSE)

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

```python
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³¹.

```bash
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:

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

| tail mass at your budget | verdict |
|--------------------------|---------|
| below ≈ 0.10 | keep the top `k` — simpler, and more accurate |
| 0.15 – 0.4 | sketch wins, by 1.4× to 4× |
| above 0.7 | sketch wins, by 4× to 7× |

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:

| domain | alphabet | tail mass | outcome |
|--------|---------:|----------:|---------|
| 21-mer abundance profiles (10 NCBI genomes) | 1 432 940 | 0.992 | sketch, 6.7× |
| USDT transfer counts per address (live chain) | 27 049 | 0.589 | sketch, 10× |
| personalised PageRank, 200 000-node graph | 200 000 | 0.502 | sketch, 2.1× |
| GPT-2 output aggregated over a corpus | 50 257 | 0.412 | sketch, 6.3× |
| GPT-2 next token, one position | 50 257 | 0.105 | truncation |
| USDT transfer *value* per address | 27 049 | 0.037 | truncation |
| document term counts | 45 969 | 0.039 | tie |
| binned returns, trade sizes (Binance) | 400 / 300 | 0.000 | truncation, exactly |

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:

| change | true `d_H` | sketch, 1 KB | top-256, 1 KB | Δ perplexity | top-1 unchanged |
|--------|-----------:|-------------:|--------------:|-------------:|----------------:|
| **serve: top-p 0.95** | 0.1489 | **0.1498** | 0.0780 | **0.00 %** | **100 %** |
| weights → int8 per tensor | 0.1841 | 0.1825 | 0.1646 | 6.82 % | 75.6 % |
| weights → bfloat16 | 0.0358 | 0.0353 | 0.0329 | 1.38 % | 95.1 % |
| serve: temperature 1.05 | 0.0442 | 0.0443 | 0.0431 | 0.00 % | 100 % |

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:

| model | vocabulary | mass outside top-64 | top-256 understates top-p by |
|-------|-----------:|--------------------:|-----------------------------:|
| pythia-160m | 50 304 | 0.187 | 48 % |
| GPT-2 | 50 257 | 0.183 | 48 % |
| Qwen2.5-0.5B | 151 936 | 0.087 | 28 % |

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

```python
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.

| bytes/sample | sourmash RMSE | sqsketch RMSE | ratio | predicted floor `√(2/D)` |
|---:|---:|---:|---:|---:|
| 1 KB | 0.1903 | **0.0686** | 2.8× | 0.0884 |
| 4 KB | 0.2167 | **0.0366** | 5.9× | 0.0442 |
| 16 KB | 0.1884 | **0.0162** | 11.6× | 0.0221 |
| 64 KB | 0.1442 | **0.0078** | 18.5× | 0.0110 |

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)`:

| `D` | bytes (float32) | standard error at most |
|-----|-----------------|------------------------|
| 256 | 1 KB | 0.088 |
| 1024 | 4 KB | 0.044 |
| 4096 | 16 KB | 0.022 |

`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.

```bash
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

```bibtex
@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.
