mirror of
https://github.com/facebookresearch/faiss.git
synced 2026-10-12 02:13:36 +00:00
Alexandr Guzhva
799bf3aaec
Summary: # Introduce early-stop controls for IVF search This PR adds optional early-stop controls to IVF search through `SearchParametersIVF`. IVF search looks in a sequence of buckets. Normally it keeps looking until it has checked all requested buckets. This PR adds a few ways to stop earlier: - stop after enough candidate vectors have been checked, - stop FastScan after enough buckets have been checked, - stop range search after several nearby buckets produce no results. All new fields default to disabled, so existing searches keep their current behavior unless callers opt in. ## New SearchParametersIVF fields Default values: | Field | Default | Effect | |---|---:|---| | `ensure_topk_full` | `false` | disabled; keep the existing hard `max_codes` behavior | | `max_lists_num` | `0` | disabled; FastScan is bounded only by `nprobe` | | `max_empty_result_buckets` | `0` | disabled; range search scans all requested probes | `ensure_topk_full` For k-NN search, `max_codes` limits how many candidate vectors are scanned. With `ensure_topk_full=false`, the search stops when the budget is reached. With `ensure_topk_full=true`, very small budgets become less aggressive: `max_codes` is treated as at least `k` post-filter scans. This helps when `max_codes < k`, or when an `IDSelector` filters out many candidates before a distance is computed. In the generic IVF path this is supported for `parallel_mode` 0 and 3. In FastScan k-NN it is supported by the per-query implementations 10 and 11. `max_lists_num` FastScan k-NN can also stop after visiting a limited number of inverted lists. `0` means disabled. With `ensure_topk_full`, this list budget is treated as at least `k` lists. This is only used by the FastScan per-query path (`search_implem_10`, also used for implementation 11). When FastScan is left on `implem = 0`, setting an early-stop k-NN option makes the dispatcher choose the per-query implementation automatically. If an incompatible FastScan implementation is selected explicitly, Faiss throws instead of ignoring the option. `max_empty_result_buckets` This is for range search. It stops probing a query after that many consecutive probed lists add no in-radius results. The counter resets as soon as a list adds at least one result. `0` means disabled. Setting this trades recall for less work: once nearby buckets repeatedly produce no hits, farther buckets are less likely to help. The generic IVF range path supports this in `parallel_mode == 0`. FastScan range search also supports it through implementation 10. With `implem = 0`, FastScan selects implementation 10 automatically when this option is set; explicit incompatible implementations throw. ## Selector-aware scan accounting This PR adds `InvertedListScannerStats`, returned by inverted-list scanner methods. It currently reports: - `scan_cnt`: number of distances actually computed, - `nheap_updates`: number of result updates. The important behavior change is that `IndexIVFStats::ndis` now uses `scan_cnt`. With an `IDSelector`, candidates rejected by the selector are not counted as computed distances. Without a selector, this matches the previous count because every scanned code reaches distance computation. This same post-filter count is used by `ensure_topk_full`, so a restrictive selector no longer consumes the search budget with candidates that were never eligible for the result heap. ## FastScan behavior FastScan k-NN now applies `max_codes`, `max_lists_num`, and `ensure_topk_full` in the per-query implementation. The code keeps separate counters per query, so multi-query batches have independent budgets. For `max_codes`, FastScan uses the result handler's scanned-row count. This means filtered-out rows do not consume the code budget. FastScan range search rejects k-NN-only options (`max_codes`, `max_lists_num`, and `ensure_topk_full`). It accepts `max_empty_result_buckets` when the selected implementation can preserve per-query probe order. ## API exposure The new fields are exposed through: - C++ `SearchParametersIVF`, - Python bindings, - the C API. The statistics is tracked via `InvertedListScanner::scan_codes(..., ResultHandler& handler)` call. In order to make it work inside `IndexIVF::search()`, it has been decided to transition it into this particular override of `InvertedListScanner::scan_codes()`. As a result, non-`ResultHandler` version of `scan_codes()` has been marked as non-virtual, so the custom `InvertedListScanner` implementations should override `ResultHandler`-based versions only. Another consequence is that `IndexIVFPQFastScanScanner` and `IndexIVFRaBitQFastScanScanner` accept only `HeapResultHandler` types of `ResultHandler`. These are the compromises that had to be made. ## Tests The tests cover: - default parameters preserving baseline k-NN and range-search results, - `ensure_topk_full` filling more result slots under tight budgets, - selector-aware `IndexIVFStats::ndis`, - range-search early exit and counter reset behavior, - unsupported parallel modes and FastScan implementations, - FastScan k-NN and range-search early-stop behavior, - Python and C API field exposure. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5160 Reviewed By: limqiying Differential Revision: D103044128 Pulled By: mnorris11 fbshipit-source-id: 80f1241c13ffc8173a3da0f2974fa9b6dd318890