IndexIVF range_search ignores SearchParametersIVF.max_codes

Environment

• Faiss: faiss-cpu==1.15.0
• Interface: Python CPU runtime
• Index: IndexIVFFlat
• Metric: METRIC_L2

Summary

IndexIVF.range_search() accepts SearchParametersIVF.max_codes, but the range-search path does not enforce a nonzero code budget.

With max_codes=1, the search scans and returns both vectors in a list containing two codes. The k-NN path applies the same parameter correctly, but the range-search path ignores it.

Minimal reproduction

import faiss
import numpy as np

x = np.array([[0.0], [1.0]], dtype="float32")

index = faiss.IndexIVFFlat(
    faiss.IndexFlatL2(1),
    1,
    1,
)

index.train(x)
index.add(x)

params = faiss.SearchParametersIVF()
params.nprobe = 1
params.max_codes = 1

lims, D, I = index.range_search(
    x[:1],
    100.0,
    params=params,
)

print(lims, D, I)

Expected behavior

SearchParametersIVF.max_codes=1 should limit the number of codes visited for the query.

Therefore, at most one candidate should be scanned and returned:

lims = [0, 1]
len(D) <= 1
len(I) <= 1

For this dataset, a possible result is:

D = [0.0]
I = [0]

The exact single ID may depend on inverted-list order.

With max_codes=0, the parameter should mean unlimited scanning, and both vectors should be returned.

Actual behavior

lims = [0, 2]
D = [0.0, 1.0]
I = [0, 1]

Both codes are scanned despite max_codes=1.

The unlimited-budget control with max_codes=0 also returns both vectors, so the problem is specific to enforcing a nonzero budget.

Root cause

SearchParametersIVF documents max_codes as the maximum number of codes to visit:

size_t max_codes = 0;

In IndexIVF::range_search_preassigned(), the value is read:

idx_t cur_max_codes = params ? params->max_codes : this->max_codes;

However, for ordinary in-memory inverted lists, the implementation later scans the entire list:

size_t list_size = invlists->list_size(key);

scanner->scan_codes_range(
    list_size,
    scodes.get(),
    ids.get(),
    radius,
    qres);

There is no truncation to the remaining budget and no early-stop check.

The k-NN path has corresponding budget accounting and early-stop logic, but the range-search path does not.

Relevant source:

• [IndexIVF.h](https://github.com/facebookresearch/faiss/blob/v1.15.0/faiss/IndexIVF.h)
• IndexIVF.cpp range-search path
• IndexIVF.cpp k-NN budget path

The same structure is also present in the current main source at the time of this report.

Impact

Applications using range search to control work or latency may scan substantially more codes than requested. This can cause:

• unexpected CPU cost;
• violation of caller-specified scan budgets;
• inconsistent behavior between k-NN search and range search;
• incorrect assumptions about bounded candidate generation.

The API call succeeds and returns plausible results, so the violation is silent.

Suggested fix

Apply the same max_codes accounting used by the k-NN path to range search:

1. limit each list scan to the remaining budget;
2. increment the scanned-code counter;
3. stop scanning once the budget is reached;
4. keep max_codes=0 as the unlimited case.

If range search cannot support this budget for a particular inverted-list implementation, it should reject the parameter explicitly instead of silently ignoring it.

Regression test

Add a test with one list containing two vectors and verify:

params.max_codes = 1
lims, D, I = index.range_search(query, radius, params=params)

assert len(I) <= 1

Also verify that max_codes=0 returns both in-range vectors.

Duplicate search

A bounded search of Faiss issues and pull requests for range_search, max_codes, and SearchParametersIVF found no exact report for this behavior.

Issue #2649 and Issue #3201 are related to max_codes accounting in filtered k-NN searches, but use a different code path.