Squeezing the codes themselves

1The indices are not uniform

A PQ or RQ code stores each index in a flat 8 bits. That is optimal only if all 256 codewords of a stage are used equally often. They are not: some are popular, and later RQ stages have skewed usage.

An entropy coder can store each index in about $-\log_2 p$ bits instead.

def code_entropy_bits(codes_train, codes_test, K=256):
    total = 0.0
    for m in range(codes_train.shape[1]):
        p = np.bincount(codes_train[:, m], minlength=K) + 0.5
        p /= p.sum()
        total += -np.log2(p[codes_test[:, m]]).mean()   # ideal code length
    return total                                       # bits per vector

2Where the saving is

• Stage 1 remembers. The first, coarse stage says roughly what kind of passage this is. It repeats its previous value 33% of the time, and conditioning on it cuts its cost from 8.0 to 5.5 bits.
• Later stages forget. They encode fine detail that changes from window to window. Conditioning buys a few tenths of a bit.

3The catch

Variable-length codes cannot be scanned with SIMD fast-scan, and they must be decoded before ADC can use them. So this is for storage and transport, not for the hot index in RAM:

4The ids deserve the same treatment

An index stores an id next to every code, often 4 to 8 bytes: as much as the code itself.

• Inside an IVF list, sort the ids and store the gaps between consecutive ones. Gaps are small and skewed, exactly what a Golomb–Rice code or ANS handles well.
• Marginalia’s ids are (book, offset). Neighbouring windows of a book often land in the same list, so many gaps are exactly 1.