Vector indexes¶

Every recommender here scores a query against the whole catalog, which is exact and linear in the catalog. An index trades one of those properties away, and there are two of them, which give up different things.

index="hnsw" gives up linear: the model builds a navigable graph over its item vectors at fit time, and recommend walks it instead of scoring everything, so a query touches a few hundred items rather than all of them. What it gives up in return is exactness — the answer is the best items the walk found.

index="quantized-flat" gives up exact, but only just, and keeps linear. It stores the item vectors a second time as narrow codes, scans every candidate with those, and then rescores the best oversample * k of them with the original vectors. The scores it returns are therefore always exact, at any code width; the only thing quantization can cost is a true top-k item that never made the shortlist.

from skrecsys.indexing import HNSW, QuantizedFlatIndex
from skrecsys.recommendation import AlternatingLeastSquares

rec = AlternatingLeastSquares(index=None).fit(X, y)  # exact scoring (the default)
rec = AlternatingLeastSquares(index="hnsw").fit(X, y)  # always index
rec = AlternatingLeastSquares(index=HNSW(m=32, ef_search=128)).fit(X, y)
rec = AlternatingLeastSquares(index=QuantizedFlatIndex(bits=4, oversample=8)).fit(X, y)

Choosing an index. On the catalogs benchmarked below, the quantized index keeps near-exact recall with exact scores, but it is slower than the exact path for every model. Use the exact path (the default) or HNSW when latency matters; see what the quantized scan costs for the numbers.

QuantizedFlatIndex takes four parameters:

• bits (default 8), one of 1, 2, 4, 8. Codes are bit-packed, so four bits really is half the memory of eight. Widths that are not powers of two are refused rather than rounded: a code that straddled a byte would cost a two-byte read and a pair of shifts per value.
• quantile (default 0.0), the share of each tail clipped when the code range is chosen. A single outlier in a dimension otherwise spends the whole range on itself and leaves the bulk two levels to share; trimming puts it outside the range, where it clips — losing its magnitude but not its rank.
• oversample (default 4), the shortlist in multiples of k. The recall-for-latency dial, and like ef_search the only one that can be turned on a model that is already fitted. Narrow codes need a wider shortlist: measured on the test fixture, eight and four bits keep the exact top ten at oversample=4 for most models, while one bit needs thirty-two and still reaches only 0.36 on AlternatingLeastSquares. SimpleX needs more than the rest at every width; see what the quantized scan costs.
• min_index_size (default 4096), as on HNSW.

Quantization is affine — value ≈ code * scale + offset — with a scale and an offset per dimension for a dense space, and one pair over all the stored values for a sparse one, where a catalog-sized column dimension has no per-column statistics worth keeping. The scan never decodes: the scale is folded into the query once, so the inner loop multiplies a query value by a code and nothing else. It also skips the norm-equalizing dimension HNSW needs, since a scan reaches every candidate whatever its norm.

One thing it does not do is shrink a fitted model: the original vectors are kept for the rerank, so the codes are an addition to the footprint. The index MB and vectors MB columns below are printed side by side for that reason.

Choose an index explicitly after measuring it for your model and data. With the default index=None, recommendations score candidates exactly and build no index. index="hnsw" is honoured at any size and density, subject to the index's own query-time floor.

Everything recommend promised it still promises. It returns exactly the number of items asked for, excludes what the user has seen, breaks ties by fitted item order, and raises rather than padding when too few items are eligible; a fitted model still holds nothing but numpy arrays, so it still pickles and scores anywhere. What changes is that the items are the best ones the walk found, which is usually and not always the best ones there are.

Two further details of the graph index. An index is skipped at query time too, for candidate sets below min_index_size (4096 by default), because a graph walked with few eligible nodes needs proportionally more walking while an exact scan over a short list is already cheap — so candidates= filters quietly stay exact and identical. And scores are inner products, which are not a metric, so the index spends one extra dimension equalizing the item norms; without it a model with a bias term loses about a fifth of its recall. A build on more than one thread is not reproducible, because concurrent insertions see different partial graphs, so a model with random_state set builds on one thread unless n_jobs says otherwise.

Whether an index pays off depends on the model and the catalog. The benchmark harness measures both on your own data:

uv run python benchmarks/run.py run indexes --dataset movielens-100k     # re-measure what changed
uv run python benchmarks/run.py run indexes --dataset amazon-books --only BM25 ALS BPR
uv run python benchmarks/run.py run indexes --index hnsw --kind sweep --no-store   # look, keep nothing

MovieLens 100K, official ua split, k=10, default hyper-parameters. Regenerate with python benchmarks/run.py run indexes --dataset movielens-100k.

Measured under an earlier version of the index, and due a re-run: quantized-flat(bits=8) for SimpleX, XSimGCL; quantized-flat(bits=4) for SimpleX, XSimGCL.

What the index costs in answers

What it costs to build, hold and search

What one request costs

How ranking time answers to the size of the catalog

Measured on Apple M4 Pro (12 usable cores), macOS-26.7-arm64-arm-64bit-Mach-O, CPython 3.14.3, numpy 2.5.3, skrecsys 0.4.0, _core built in release mode. The quality table above is deterministic and portable; the timings below are not comparable across machines or builds.

The exact row of each model is the baseline every delta in its block is measured against. recall@10 is agreement with that exact model, not with the truth, which is why dNDCG@10 is beside it: recall counts items the index missed, and dNDCG@10 says whether missing them cost anything. The dial column names the query-time width each row was measured at: ef is HNSW's candidate list and ov is the quantized scan's shortlist, in multiples of k. Those two are not comparable to each other -- they are each index's own recall-for-latency knob, and only the columns either side of them are. The quantized rows' scores are always exact, because the shortlist is rescored with the original vectors before anything is returned: their score gap@1 moves only when the shortlist missed the true best item, never because a number was dequantized. A speedup below 1.00x means the index costs more than it saves. This is expected for neighbourhood models, whose exact path is an inverted-index scan that only touches items a user's history reaches. This catalog holds 1,680 items, which is below the default min_index_size of 4,096, so a model configured with index="hnsw" would have taken the exact path here and the rows below would not exist. The benchmark lowers that floor to measure the index itself; a speedup under 1.00x on a catalog this small is the reason the default floor exists.

Amazon Books (amzn-books-l50), leave-one-out split, k=10, default hyper-parameters. Scored on a fixed random sample of 10,000 held-out users. Not run: EASE (a dense 674k x 674k item matrix does not fit in memory); SLIM (one elastic net per item over a 674k-item catalog does not finish); SimpleX (one training epoch of 7.4M interactions runs over an hour on CPU); XSimGCL (one training epoch of 7.4M interactions runs over an hour on CPU). Regenerate with python benchmarks/run.py run indexes --dataset amazon-books.

What the index costs in answers

What it costs to build, hold and search

What one request costs

Measured on Apple M4 Pro (12 usable cores), macOS-26.7-arm64-arm-64bit-Mach-O, CPython 3.14.3, numpy 2.5.3, skrecsys 0.4.0, _core built in release mode. The quality table above is deterministic and portable; the timings below are not comparable across machines or builds.

The exact row of each model is the baseline every delta in its block is measured against. recall@10 is agreement with that exact model, not with the truth, which is why dNDCG@10 is beside it: recall counts items the index missed, and dNDCG@10 says whether missing them cost anything. The dial column names the query-time width each row was measured at: ef is HNSW's candidate list and ov is the quantized scan's shortlist, in multiples of k. Those two are not comparable to each other -- they are each index's own recall-for-latency knob, and only the columns either side of them are. The quantized rows' scores are always exact, because the shortlist is rescored with the original vectors before anything is returned: their score gap@1 moves only when the shortlist missed the true best item, never because a number was dequantized. A speedup below 1.00x means the index costs more than it saves. This is expected for neighbourhood models, whose exact path is an inverted-index scan that only touches items a user's history reaches.

What those two tables say about explicit index choices.

A latent-factor model is where an index pays. It compresses a catalog into a few dozen dimensions, which is the geometry a graph is good at. On Amazon Books, BPR ranks 10,000 users 66x faster at 0.96 recall (ef=64) and ALS 56x faster at 0.94 (ef=32), for a build that costs about as much as the fit. Those multiples are over an exact path that scores all 660,940 items for every user, which no kernel can make sublinear. On a 1,680-item catalog the same models keep essentially perfect recall and lose on time, because there is nothing there to save.

A neighbourhood model is where it does not. recommend::top_k_from_similarity is already an inverted-index scan whose cost follows the user's history and the width of a similarity row rather than the catalog, so a graph has little to win — and at six figures it does not merely lose on time, it stops working. BM25 retrieves 0.0002 of the exact answer on Amazon Books, ItemKNN 0.016. That is noise, not approximation, and the reason is structural: an item keeps 50 neighbours out of 660,940 columns, so two item vectors share a stored value with probability about 0.004. Nearly every pair scores zero while the graph is being built, the graph comes out of ties, and the walk returns whatever it reaches.

EASE is the row that justifies printing both tables. On MovieLens the graph retrieves 0.27 of the right answer at ef=16 and gives up 0.10 of NDCG, and it is no longer even fast: the exact path adds one catalog-wide row per item a user has seen and ranks all 943 users in 3 ms, so the graph is 1.04x at best and 0.62x at ef=64. The quantized scan is the same row read the other way: on that model it keeps 1.0000 recall at bits=8, ov=2, and runs at 0.04x of the exact path's speed.

What the quantized scan costs¶

On both datasets QuantizedFlatIndex is slower than the exact path for every model, at every setting measured. On MovieLens the speedups run from 0.12x (ALS, bits=8, ov=1) down to 0.01x (RP3Beta, bits=4); on Amazon Books the best is 0.09x (BPR, bits=8) and the neighbourhood models round to 0.00x. The scan visits every candidate on one thread, while the exact neighbourhood path only touches the items a user's history reaches, and the exact factor path is a tiled, multi-threaded kernel.

What it does deliver is the other three columns:

• Accuracy, essentially free. At bits=8, ov=2 it reproduces the exact answer — recall@10 of 1.0000 — on ALS, BPR, ItemKNN, BM25, RP3Beta, SLIM, EASE and XSimGCL on MovieLens, and on Amazon Books it holds 1.0000 for ALS and BPR and at least 0.999 for the neighbourhood models, where the graph retrieves under 0.03. Compare the graph on EASE, which needs ef=256 to reach the same place.
• Exact scores, and a score gap@1 that says something different from the graph's. 81 of the 90 MovieLens quantized rows show +0.0000, and the nine that do not are all bits=4, all under +0.0006; on Amazon Books the thirteen that do not are bits=4 too, all under +0.02. Those rows are not dequantized numbers leaking into the output — they cannot be, because the shortlist is rescored with the original vectors before anything is returned. They are rows where the shortlist missed the true best item, so first place went to a genuinely lower-scoring one, and the gap is the real difference between two real scores. The graph's gaps reach +0.16 on MovieLens and +0.99 on Amazon Books for the same reason.
• A build that rounds to nothing. 0 to 17 ms on MovieLens, against 88 ms for the graph on ALS and 402 ms on EASE; 17 to 254 ms on Amazon Books, against graph builds of 14 s (BM25) to 14 minutes (RP3Beta).

SimpleX is the model that does not fit the summary, and is worth reading before choosing bits. At bits=8 it needs ov=8 to pass 0.99; at bits=4 it reaches only 0.84 even at ov=16. Its factors evidently carry more in their fine structure than the other models' do, and four bits throws that away. The graph has no such trouble with it (0.992 at ef=16). Narrow codes are a per-model decision, not a global one.

Integer arithmetic in the quantized scan¶

QuantizedFlatIndex scans with narrow item codes and a floating-point query. A natural extension is to quantize the query as well and run the inner loop as int8×int8→int32, which is where real quantized indexes get their speed: one ARM udot does sixteen multiply-accumulates against NEON's two f64 ones. It was built and measured, and not adopted. This note records why.

The arithmetic works out cleanly — an integer accumulator can only hold Σ qc·vc, so every scale has to come out of the sum:

<q,v> ~= sq·sv·Σ(qc·vc) + sq·ov·Σqc + oq·sv·Σvc + oq·ov·dim

with Σvc precomputed per item. Three findings decided against it:

1. It was worth 1.26x, not 7x. Measured on the 60,000-item catalog: 5.44 → 4.33 ns per candidate at eight bits, 5.66 → 3.97 at four. Still 4.8x slower than the exact path, so nothing about the decision changes.
2. udot never appeared. LLVM emits u32 multiplies from safe Rust, not the sixteen-lane widening dot product the estimate assumed. Reaching it needs std::arch::aarch64 intrinsics, which are unsafe, and this crate does not use unsafe anywhere. That is a deliberate property worth more than 1.3x.
3. It set a trap for EASE. An integer accumulator forces one global scale in place of the per-dimension ones. EASE's space is dense, so it qualified at fit time — but it always scores through sparse queries, so it fell back to the float kernel and paid the accuracy cost for none of the speed. Recall went to 0.059 at four bits and 0.000 at two, against 0.998 with per-dimension scales. Silent, catastrophic, and exactly the "fast and wrong" outcome the index benchmarks in the README exist to catch.

Tiling survived because it is free: it changes the loop order, not the numbers. Integer arithmetic is not free — it trades away per-dimension resolution — and at 1.26x the trade does not pay.

The Amazon Books block is a long run to reproduce: the quantized rows alone take hours over a 660,940-item catalog, because the scan is sequential by design, and the ItemKNN and RP3Beta graph builds are 686 s and 869 s. python benchmarks/run.py run indexes --dataset amazon-books re-measures only the rows whose config has changed.

Use index=None for the exact path, which is the default. The tables show where an explicit approximate index helps and where it costs time or quality; measure the model and catalog before choosing one.

MostPopularRecommender has no index parameter and appears in neither table: its score does not depend on the query, so there is nothing for a neighbour index to narrow.