Docs: suggested n-tiers list cost more and cluster worse near their lower bounds.

Guidelines-to-choose-an-index.md, lines 82–110.

Concern

Two quantities move in opposite directions as a dataset sits lower in a tier.

1. Density. A centroid is the sample mean of the m = n/nlist points in its cell, so its standard error goes as sigma/sqrt(m), where sigma is the within-cell spread of the data. sigma is fixed by the dataset, so m is the only lever on centroid precision. Below the floor, centroids describe sampling noise rather than regions of the space, and enough cells come out empty that split_clusters begins repairing them by duplicating larger ones.

FAISS states this requirement itself — on the page as 30*K training vectors, and at runtime via min_points_per_centroid = 39:

import faiss, numpy as np                    # faiss 1.15.0
d, n = 64, 1_200_000
x = np.random.rand(n, d).astype('float32')
faiss.index_factory(d, "IVF65536_HNSW32,Flat").train(x)
# WARNING clustering 1200000 points to 65536 centroids:
#   please provide at least 2555904 training points

1. Cost. k-means has a per-iteration component that scales with nlist, not n.

With a fixed nlist, density n/nlist falls linearly as n approaches the tier's floor while that cost component stays flat — so the bottom of a tier pays the most compute for the least well-determined centroids. Continuing 4*sqrt(N)–16*sqrt(N) instead keeps density at sqrt(N)/mult, which grows with N rather than collapsing at a boundary.

Measured at the 10M boundary

A dataset grew ~960k vectors and crossed 10,000,000. d=64, IVFFlat, METRIC_INNER_PRODUCT, 4x L4, faiss-gpu-cu12:

0.3% growth in n, >5x the clustering time.

Controlled comparison: in the same run, on the same GPUs, at the same nlist = 262,144, a 49.5M-vector dataset (4.6x larger, 188 points per centroid) finished in 39 minutes. Neither n nor nlist explains the stall — density does.

It was also not GPU-bound; ~98% of wall clock was spent off-GPU. Worth flagging because the page's stated remedy for this tier is "do just the training on GPU" — we were, and it does not address this failure mode.

39 is a floor, not a safe operating point. 39 x 262144 = 10,223,616, so our 10,754,940 sat just above the threshold at 41 points per centroid and no warning was emitted — yet the run still failed. The dominated region extends well above where the warning stops.

At N = 1M the same shape holds: the tier gives 15 points per centroid against 62–250 from the sqrt band, for 4–16x the clustering work.

Secondary — docs only, no runtime impact

1. Line 82 frames these as the size of a sample of the dataset; line 92 asks for at least 30 x 65536 = 1,966,080 for a tier beginning at 1,000,000. Unsatisfiable for N in [1M, 1.97M]. (Only the lower bound is a requirement — the upper is a cap.)
2. The page says 30*K; min_points_per_centroid defaults to 39.
3. The sub-1M rule is self-consistent by contrast: 30*K with K = 4*sqrt(N) is 120*sqrt(N), below N for all N > 14,400.

Suggested fix

A note that the training-density requirement takes precedence over the tier table, and that datasets low in a tier should stay on the 4*sqrt(N)–16*sqrt(N) rule.

Concretely, a guard that refuses promotion to a larger nlist until the density is earned:

while nlist > 65536 and n / nlist < 50:
    nlist = <next tier down>

50 rather than 39 because 39 did not flag our case. On our data this would move the effective boundary from 10M to 13.1M. A note along these lines covers both tier boundaries and both thresholds (30 vs 39) without picking new constants; moving the boundaries to ~2M and ~10.3M would fix the arithmetic but leave the same cliff at the new positions.