Metadata-Version: 2.5
Name: mvhnsw
Version: 0.2.1
Summary: HNSW sizing and measurement for Qdrant collections with more than one named vector
Project-URL: Homepage, https://github.com/matijani/hnsw-multivector-tuning
Project-URL: Issues, https://github.com/matijani/hnsw-multivector-tuning/issues
Project-URL: Source, https://github.com/matijani/hnsw-multivector-tuning
Author-email: Marouane Tijani <mrntjn@gmail.com>
License: Apache-2.0
License-File: LICENSE
Keywords: ann,benchmark,hnsw,qdrant,vector-search
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Database :: Database Engines/Servers
Requires-Python: >=3.10
Requires-Dist: numpy>=1.24
Provides-Extra: dev
Requires-Dist: coverage>=7.4; extra == 'dev'
Requires-Dist: pytest>=7.4; extra == 'dev'
Requires-Dist: qdrant-client>=1.9; extra == 'dev'
Requires-Dist: ruff>=0.5; extra == 'dev'
Provides-Extra: qdrant
Requires-Dist: qdrant-client>=1.9; extra == 'qdrant'
Description-Content-Type: text/markdown

# hnsw-multivector-tuning

Measures what HNSW parameters cost on a Qdrant collection that carries more
than one named vector, and models what it measured.

`m` and `ef_construct` are documented per collection. A collection with a
1536-dimensional image vector and a 1024-dimensional text vector builds two
graphs from one setting, pays for both, and none of the three costs — memory,
build time, recall — divides between them the way the dimensions suggest. This
repository is the measurement of all three on both vectors of the same live
collection, the script that produced it, and the sizing model fitted to the
result.

Three things came out of it that I did not expect, and one of them is the
reason the rest of this exists.

**The graph does not know the dimension.** At the same `m` over the same
points, the 1536-dimensional index and the 1024-dimensional one come out the
same size to within 0.2%. Raising `m` costs the same number of bytes on your
narrow vector as on your wide one. There is therefore no reason to let both
inherit a single collection-level `m`, and no reason to assume the big vector
is the one to economise on.

**One `full_scan_threshold` is two different cutoffs.** It is configured as a
size in kilobytes and compared against a count of points, so the server divides
it by the width of the vector. The default of 10000 becomes 1666 points on the
1536-dimensional index and 2500 on the 1024-dimensional one. Between those
numbers, the same query against the same segment walks the graph for one vector
and brute forces the other.

**You cannot retune one named vector.** The optimiser rewrites segments, not
vector indexes. Changing `m` on the image vector throws away and rebuilds the
text vector's graph too, at whatever it was already set to.

## Install

```bash
pip install mvhnsw
```

Python 3.10 or newer. The sizing model and the vector generator need only
numpy. Talking to a server needs `pip install "mvhnsw[qdrant]"`.

## The smallest thing that runs

Size a collection before you build it, with no server involved:

```python
from mvhnsw import CollectionPlan, HnswParams, VectorSpec, plan_memory

plan = CollectionPlan(
    [VectorSpec("image", 1536), VectorSpec("text", 1024)],
    HnswParams(m=64),
)
print(plan_memory(plan, 10_000_000).table())
print(plan.full_scan_points())
```

```
vector         dim    m     vectors       graph  graph %
image         1536   64   57.22 GiB    1.84 GiB     3.1%
text          1024   64   38.15 GiB    1.84 GiB     4.6%
total                     95.37 GiB    3.67 GiB     3.7%
{'image': 1666, 'text': 2500}
```

Same thing from a shell:

```bash
mvhnsw plan image:1536 text:1024 --m 64 --points 10000000 --budget-gib 3
```

And against a collection that already exists, to find out what it is really
doing rather than what you configured:

```bash
mvhnsw scan /var/lib/qdrant --collection photos --verbose
```

## What the numbers say

Everything below was measured on 100,000 points, one segment, Qdrant 1.19.0 on
sixteen cores, the collection carrying both named vectors except where a
section says otherwise. `results/` holds the raw csv and `bench/` holds the
scripts that wrote it. Every recall figure was checked against the
server's own execution counters to confirm the search actually went through the
graph; see the note on brute force further down for why that matters.

### Memory

`m` sweep at `ef_construct=100`, graph bytes read off the segment files:

| m | image graph | text graph | ratio | build | recall@10, ef=128 (image / text) |
|---|---|---|---|---|---|
| 8 | 4.08 MiB | 4.07 MiB | 1.002 | 54.9 s | 0.779 / 0.792 |
| 16 | 6.52 MiB | 6.53 MiB | 0.999 | 88.7 s | 0.948 / 0.964 |
| 24 | 7.92 MiB | 7.92 MiB | 0.999 | 96.8 s | 0.983 / 0.981 |
| 32 | 8.82 MiB | 8.83 MiB | 0.999 | 106.5 s | 0.987 / 0.989 |
| 48 | 9.97 MiB | 9.98 MiB | 1.000 | 119.8 s | 0.991 / 0.992 |
| 64 | 10.53 MiB | 10.61 MiB | 0.993 | 117.5 s | 0.983 / 0.992 |

The ratio column is the point. A 50% wider vector produces the same graph,
because the neighbour lists hold point offsets and a point offset has no
opinion about how wide the vector it points at is.

The second thing in that table is the knee. Going from 48 to 64 buys nothing —
recall is flat or slightly worse — and costs another half a megabyte per
vector, which at ten million points is another 0.3 GiB across the two of them.
The default of 16 is low for this data and 64 is past the point of usefulness;
the useful band is narrow and it is worth finding rather than assuming.

The usual estimate for graph memory is `m * 2 * 4` bytes per point: `m0` links
holding a four-byte offset each. It is too big, and the amount by which it is
too big depends on `m`, which is the part that makes it dangerous. Measured
against the table above, it overstates the graph by 1.6x at `m=8` and by 4.7x
at `m=64`, because it counts slots and the slots do not get filled — the next
section is what fills them. `graph_bytes_per_point(m, n)` is fitted to
`results/graph_bytes.csv`, six values of `m` across four segment sizes, and is
3% out at worst over that range; refit it for your own build with
`fit_graph_model(rows)`. At ten million points and `m=64` it puts the two
graphs at 3.7 GiB where the rule of thumb says 9.6 GiB, which is the difference
between provisioning a box and provisioning a bigger one.

Two values of `m` are not enough to fit it, and that is not a detail. Fitted at
`m=16` and `m=48` only, a straight line through the two is indistinguishable
from the curve, and it says 280 bytes a point at `m=64` where the segment says
110.

`ef_construct` is the cheap knob, and I expected it to be the free one. It
mostly is. Sweeping it at `m=16`:

| ef_construct | build | image graph | recall@10, ef=64 | recall@10, ef=128 |
|---|---|---|---|---|
| 50 | 45.4 s | 5.88 MiB | 0.802 | 0.918 |
| 100 | 88.7 s | 6.52 MiB | 0.861 | 0.948 |
| 200 | 152.8 s | 6.66 MiB | 0.871 | 0.965 |
| 400 | 246.2 s | 6.66 MiB | 0.887 | 0.970 |

Not flat, and not monotonic either. The graph grows 13% from 50 to 200 and then
stops dead, because a wider construction search finds more valid neighbours and
fills more of the `m0` link slots, and at `m=16` there are only thirty-two of
them to fill. That ceiling is specific to this `m`; the next section is what
happens when there are a hundred and twenty-eight. Either way, a low
`ef_construct` does not just cost you recall, it
leaves you holding an underfilled graph you are paying `m` for. Compare with
2.6x for `m` over 8 to 64: `ef_construct` is the cheap knob, worth raising
before `m` when memory is the constraint, but the sizing model leaves the term
out entirely and is a slight underestimate below 100.

Build time is close to linear in `ef_construct` and stays that way; recall is
not, and past 200 it has stopped moving.

### How much of the `m` you paid for you receive

The two paragraphs above disagree, and the disagreement is the useful part.
The `m` sweep says the graph grows 2.6x while `m` grows 8x, so the link slots
are not all being used. The `ef_construct` sweep at `m=16` says they fill up
and then stop. Both cannot be the whole story, so `bench/fill_ratio.py` holds
`m` and moves `ef_construct` a long way at two larger values of `m`. The
column that matters is bytes per layer-zero slot: if every slot were occupied
it would be constant.

| m | m0 | ef_construct | bytes/point | bytes/slot | build | recall@10 ef=128 |
|---|---|---|---|---|---|---|
| 32 | 64 | 100 | 92.6 | 1.42 | 101.7 s | 0.987 |
| 32 | 64 | 400 | 102.7 | 1.58 | 317.8 s | 0.996 |
| 64 | 128 | 100 | 110.7 | 0.86 | 113.8 s | 0.991 |
| 64 | 128 | 400 | 136.6 | 1.06 | 367.6 s | 0.997 |

At `m0=64` a wider construction search adds 11%; at `m0=128` it adds 23%. So
the slots at `m=16` really do fill, and at `m=64` they never do: widening the
search keeps finding neighbours the narrow search missed, and even at
`ef_construct=400` a slot at `m0=128` costs a third less than one at `m0=64`,
which it can only do by being empty more often. Doubling `m` from 32 to 64
therefore buys 20% more graph, not 100% more graph. That is the good news and
the bad news in one number: the memory is cheaper than you feared, and the
reason it is cheaper is that you are not getting what you asked for.

Read the last two columns together. `m=64, ef_construct=400` costs 33% more
memory and 16% more build time than `m=32, ef_construct=400`, for a recall
difference of 0.001. Spend on `ef_construct` first.

### Build time

The same 100,000 points built three ways on the same idle server: as a
collection holding only the 1536-dimensional vector, only the 1024-dimensional
one, and both. Sixteen cores, `max_indexing_threads` at its default of all of
them, so the optimistic answer is that the two graphs go up side by side and
the pair costs what the slower one costs.

| m / ef_construct | image only | text only | both | sum of parts | both / sum | image / text |
|---|---|---|---|---|---|---|
| 16 / 100 | 52.4 s | 34.2 s | 87.1 s | 86.6 s | 1.006 | 1.53 |
| 32 / 200 | 114.3 s | 79.1 s | 183.8 s | 193.4 s | 0.950 | 1.45 |

It is the sum. Adding a second named vector to a collection does not cost a
fraction of a build, it costs a whole second build, and the parallelism you
were counting on is already spent inside the one graph. Plan a reindex of a
three-vector collection as three reindexes.

The asymmetry between the two is the dimension and only the dimension. 1536 /
1024 is 1.50; the measured ratios are 1.53 and 1.45. A build spends its time
computing distances, and a distance over 1536 floats costs half again what one
over 1024 does. `build_work(m, ef_construct, dim, n)` is that ratio and nothing
more; use it to convert a build you have timed into one you have not, never as
a time.

Which is the mirror image of the memory result, and worth holding both at once:
the wide vector costs 50% more to build and exactly the same to keep.

Raw rows in `results/build_time.csv`, script in `bench/build_time.py`.

### Recall

Recall is the one number here that does not transfer, and publishing a single
curve for it would be misleading. It is governed by the intrinsic dimension of
your embeddings, not by the width of the column they are stored in. Three
collections, all 1536 dimensional, all 100,000 points, all built at `m=16` and
`ef_construct=100`, differing only in how many dimensions the data actually
occupies:

| latent dim | two_nn estimate | build | recall@10 ef=32 | ef=64 | ef=128 | ef=256 |
|---|---|---|---|---|---|---|
| 8 | 9.7 | 21.1 s | 0.996 | 1.000 | 1.000 | 1.000 |
| 32 | 31.9 | 53.4 s | 0.709 | 0.873 | 0.955 | 0.983 |
| 128 | 79.0 | 66.4 s | 0.210 | 0.318 | 0.467 | 0.641 |

Nothing in the schema distinguishes those three rows. At `ef=128` they span
0.467 to 1.000, where the entire `m` sweep from 8 to 64 spanned 0.779 to 0.991
on the same axis. The data matters more than the parameter, which is why a
recall number published for somebody else's embeddings — including the ones in
the table further up — tells you close to nothing about yours.

Build time moves with it too, three-fold across the same three rows at
identical parameters, because a harder neighbourhood means more candidates
examined per insertion. A build estimate carried over from an easy collection
to a hard one is wrong in the expensive direction.

So the useful thing is not a number, it is the axis. Run `two_nn_dimension(v)`
on a sample of each of your named vectors. If they come back different — and an
image encoder and a text encoder generally do — then they want different `m`,
and any shared collection-level `hnsw_config` is overpaying on one of them and
underserving the other.

Note also what did *not* differ. At matched intrinsic dimension the
1536-dimensional and 1024-dimensional vectors in the sweep above reach the same
recall at the same `m`, to within a percent. Nominal width drives build time
and nothing else.

Raw rows in `results/intrinsic_dim.csv`, script in `bench/intrinsic_dim.py`.

## Failure modes

**Your benchmark is measuring brute force.** Below the resolved full scan
threshold Qdrant ignores the graph and scans the segment, which has perfect
recall, so a small trial collection reports 1.0 for a configuration it never
used and the number collapses in production. Worse, on a two-vector collection
the cutoff is different per vector, so you get one of each. Measured:

| points | vector | cutoff | path taken | recall@10 |
|---|---|---|---|---|
| 1200 | image (1536d) | 1666 | brute force | 1.000 |
| 1200 | text (1024d) | 2500 | brute force | 1.000 |
| 2000 | image (1536d) | 1666 | hnsw | 1.000 |
| 2000 | text (1024d) | 2500 | brute force | 1.000 |
| 3200 | image (1536d) | 1666 | hnsw | 1.000 |
| 3200 | text (1024d) | 2500 | hnsw | 1.000 |

The recall column is identical everywhere and tells you nothing. The path
column is what you need, and it comes from the server's own counters, not from
inference. `execution_paths()` reads them; anything that lands on
`unfiltered_exact` was not served by the index you are trying to measure.

**`indexing_threshold=0` does not drop an index.** It stops new segments from
being indexed. Existing segments keep their graphs and keep serving searches.
If you are waiting for `indexed_vectors_count` to fall to zero before timing a
rebuild, you will wait forever. What drops the index is a configuration change,
which makes the optimiser rewrite the segment; with the threshold at zero it
rewrites it as plain. Two calls, and the order matters. `rebuild()` does it in
the right order.

**Asking for the parameters that are already built is not a change.** The
optimiser rewrites a segment when its built configuration stops matching its
intended one. Apply `m=16` to a segment already built at `m=16` and nothing
matches differently, so nothing is rewritten, so nothing is dropped, and code
waiting for the old index to disappear waits against a server sitting at zero
percent CPU. It only bites on a cell that repeats a value or on the second run
of a benchmark over a collection the first run left behind, which is why it
reads as intermittent. `rebuild()` gets around it by asking for an `m` nothing
is built at first, waiting for the segment to come back plain, and only then
applying the parameters being measured.

**Retuning one vector rebuilds all of them.** Covered above. Budget for it.

**`indexed_vectors_count` is not points.** It counts point-and-vector pairs, so
a healthy two-vector collection of a million points reports two million. People
see the doubling and go looking for duplicates.

**A batch of 1000 stops working when you add the second vector.** One point
carrying 1536 and 1024 float32 values is 10 KiB of binary and about 56 KiB of
JSON, and the server refuses bodies over 32 MiB. The error mentions a payload
size and neither a batch size nor a vector name. `batch_size_for(dims)` works
the limit backwards; measured sizes are in `results/payload_size.csv`. Over
gRPC the same collection takes five times the batch, which is reason enough to
use it for bulk loads.

**A `hnsw_config` on one vector does not isolate that vector.** It is a
field-by-field merge over the collection level, not a replacement.
`HnswConfigDiff(m=32)` on the image vector leaves its `ef_construct` and its
`full_scan_threshold` coming from the collection, so a later change at the
collection level silently moves them. `resolve_hnsw(spec, collection)` gives
you the effective values, and `mvhnsw scan` gives you the values a segment was
genuinely built with, which is the only version that cannot be wrong.

**The peak is during the build, not after it.** A sweep that fits comfortably
at rest still gets killed rebuilding the wide vector, because the optimiser
holds the old segment while it writes the new one. `run_sweep` takes a `guard`
for this, and the journal means the cells that already finished survive the
kill.

## What did not work

**Moving one graph to disk to save RAM.** `on_disk=true` on the narrower
vector's `hnsw_config` moves the links out of the heap and into a mapping,
which looks like a saving right up until the collection is under query load and
the page cache pulls it all back. You have not freed the memory, you have
reclassified it, and you have added a cliff on cold pages. It is worth doing
when the index genuinely does not fit and you accept the tail latency; it is
not worth doing to make a dashboard look better.

**Quantising to fix a memory problem that was the graph.** Scalar quantisation
cuts the stored vectors, which is usually right, but it does not touch the
graph at all. If you got where you are by setting `m=64` on a collection with
two named vectors, the thing that grew is the part quantisation does not
address, and the fix is `m`.

**Reaching for `m` when recall was short.** It is the parameter everybody
names first and it was the wrong one twice. Going from `m=32` to `m=64` at
`ef_construct=400` cost a third more memory and a sixth more build time for a
thousandth of recall, and it costs that on every named vector at once. What
moved recall was `ef_construct`, and after that `hnsw_ef` at query time, which
is free to change and does not need a rebuild to try.

**Tuning `m` on the harder vector and letting the other inherit it.** This is
the default behaviour and it was the original setup. Since the graph cost is
identical per vector, inheriting means paying the hard vector's price twice
while the easy vector sits well past its own knee. Setting the two separately
costs one extra line of configuration.

**Timing rebuilds by watching the collection status.** `green` is reported both
before a rebuild starts and after it finishes, so the first poll after issuing
a config change succeeds and the measurement comes back as a fraction of a
second. The wait in `rebuild()` requires the built parameters read from the
segment files to match what was asked for, and requires the condition twice in
a row.

## Reproducing it

```bash
docker run -d --name qlab -p 6333:6333 -p 6334:6334 \
    -v /tmp/qstore:/qdrant/storage qdrant/qdrant:v1.19.0

pip install -e ".[dev]"
export MVHNSW_STORAGE=/tmp/qstore

python bench/full_scan_threshold.py   # a few minutes
python bench/graph_scaling.py         # fits the memory model, about half an hour
python bench/sweep_m.py               # the main sweep, the better part of an hour
python bench/build_time.py            # additivity of two builds
python bench/intrinsic_dim.py         # recall against intrinsic dimension
python bench/fill_ratio.py            # how much of m0 a build actually fills
python bench/payload_size.py          # where a batch size stops fitting
```

Run them one at a time. Two of these against the same server at once is an
easy mistake to make when the first one is slow, and it does not fail, it just
returns build times inflated by however much the other one was doing.

`MVHNSW_STORAGE` has to point at the host side of the server's storage mount.
The size of an index is not available over the API — telemetry reports
`ram_usage_bytes` and `disk_usage_bytes` as zero, and not per named vector
either — so `scan_storage(path)` reads the segment directories instead. Point
it at the container side, or at a directory this user cannot read, and every
measurement in here silently has nothing to measure; `storage_problem(path)`
is checked before anything long starts and says which of those it was.
`MVHNSW_HOST` and `MVHNSW_PORT` move the scripts off `localhost:6333` if that
port is already taken.

The sweep journals every cell as it finishes and skips completed work on a
rerun, which matters because it does get interrupted. Failed cells are recorded
as failures rather than dropped, so a table with a hole in it looks like one.
The loads are skipped the same way: a script that finds its collection already
present with the right vector names, widths and point count reuses it rather
than spending another few minutes uploading the same vectors.

Turn a journal into a csv with:

```bash
mvhnsw report results/sweep_m.jsonl -o results/sweep_m.csv
```

### About the vectors

The benchmark generates its vectors rather than shipping a dataset, because
recall depends on the shape of your embeddings and no single dataset would let
you see that dependency. `iter_vectors(n, dim, intrinsic_dim=...)` produces
clustered, spectrally decaying, L2-normalised vectors on a manifold of the
width you ask for, streamed in chunks so that ten million of them is a stream
and not a 61 GiB array. Isotropic Gaussian noise, which is what most quick
benchmarks use, is the hardest possible input for an ANN index and produces
recall numbers nobody will ever reproduce.

To run any of this against your own embeddings instead, hand
`upload_vectors(client, name, sources)` an iterator of numpy chunks — a memory
mapped `.npy` sliced into blocks does fine — and the rest of the harness does
not care where the vectors came from.

The memory and build-time results do not depend on the data at all. The recall
results do, which is the reason `intrinsic_dim` is a knob and not a constant.

## Reference

| | |
|---|---|
| `resolve_hnsw(spec, collection)` | effective parameters for one named vector |
| `full_scan_points(kb, dim)` | the threshold in points rather than kilobytes |
| `plan_memory(plan, points)` | per-vector vectors and graph, and the totals |
| `graph_bytes_per_point(m, n)` | the fitted model, one number |
| `suggest_m(plan, points, budget)` | largest uniform `m` whose graphs fit |
| `fit_graph_model(rows)` | refit the model from your own measurements |
| `scan_storage(path)` | what every index in a storage directory really is |
| `storage_problem(path)` | why a storage path cannot be read, before you wait on it |
| `two_nn_dimension(vectors)` | intrinsic dimension of a sample |
| `iter_vectors(n, dim)` | streamed synthetic vectors |
| `batch_size_for(dims)` | largest upsert that fits the request limit |
| `upload_vectors(client, name, sources)` | streamed, resumable, backs off |
| `run_sweep(cells, fn, journal)` | resumable sweep with a memory guard |

`IndexProbe` wraps a live collection: `rebuild()`, `ground_truth()`,
`recall()`, `index_bytes()`, `execution_paths()`, `resolved()`.

## Licence

Apache-2.0.
