Pinging @elastic/es-search-relevance (Team:Search Relevance)

Based on the problem of the possibility of large segments the capped linear formula won't work so we chnage it to a sublinear option and also added more modern dataset.

New Formulas

Property Comparison

Benchmarking: main (log₁₀²) vs fix (sublinear)

GIST-1M (N=1,000,000)

Wiki-Cohere (N=934,024)

from the reported numbers, it seems like we are exploring less, but it seems this exploration translates with similar multiplicative factor to recall drops, at least for lower visit_percentage. since the allocation logic hasn't changed, this is not surprising. the numbers for higher visit_percentage look good instead.
apart from that, moving num_candidates / visit_percentage to apply on a per segment basis makes a lot of sense.

@ah89 I need to see the actual visit percentages per segment and segment count, etc.

visiting only 1% maximally with 100M vectors seems like a horrible side effect.

@ah89 I need to see the actual visit percentages per segment and segment count, etc.

visiting only 1% maximally with 100M vectors seems like a horrible side effect.

@benwtrent The implementation is per-segment.

GIST-1M — HNSW (31 segments, ~33.3k vectors each)

GIST-1M — IVF (29 segments, ~33.3k vectors each)

Wiki-Cohere — HNSW (24 segments, ~39.5k vectors each)

Wiki-Cohere — IVF (22 segments, ~42.5k vectors each)

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

_{Comment @coderabbitai help to get the list of available commands and usage tips.}

Gist-1M (1M, 1 segment, k=10, MIP)

Wiki-Cohere (934k, 1 segment, k=10, MIP)

Please disregard the previous results, as they followed the legacy path:

Wiki-Cohere — 934,024 vectors, 768-dim, 1 segment, k=10, MIP

Gist-1M — 1,000,000 vectors, 960-dim, 1 segment, k=10, MIP

DBpedia-Arctic — 4,635,922 vectors, 768-dim, 1 segment, k=10, MIP

Updated default visit_percentage calculation for bbq_disk IVF search

Formulae

Previous formula (in IVFVectorsReader, segment-level fallback):

$$\text{visitRatio} = \frac{\text{round}(\log_{10}(N)^2 \times k)}{N}$$

where $N$ is the number of vectors in the segment. This formula is segment-size dependent and completely ignores num_candidates — it produces a flat visit budget regardless of how many candidates the user requests. As $N$ grows, the visit ratio shrinks toward zero, leading to severe recall degradation on large segments.

New formula — Two-Signal Model (in AbstractIVFKnnVectorQuery, query-level):

$$r = \frac{\text{num candidates}}{k}$$

$$z = 0.85 \cdot \text{logScale}(r, \ln(1 + 100)) + 0.15 \cdot \text{logScale}(k, \ln(1 + 10{,}000))$$

$$\text{visitRatio} = V_{\min} + (V_{\max} - V_{\min}) \cdot z$$

where:

• $\text{logScale}(x, m) = \text{clamp}\left(\frac{\ln(1 + x)}{m}, 0, 1\right)$
• $V_{\min} = 0.005$ (0.5%)
• $V_{\max} = 0.05$ (5%)

The Two-Signal Model uses two signals to determine how much of each segment to visit:

1. The num_candidates / k ratio (weight: 85%) — captures the user's intent for recall quality. Higher ratio = user wants more thorough search.
2. The absolute value of k (weight: 15%) — larger k queries benefit from slightly more exploration to fill the larger result set reliably.

Both signals are log-scaled to produce diminishing returns (doubling num_candidates doesn't double the visit budget), and the result is linearly mapped into the $[V_{\min}, V_{\max}]$ range.

Reasoning

The key properties of the Two-Signal Model:

1. Segment-size independent (N-independent): The visit percentage depends only on num_candidates and k, not on how many vectors are in the segment. The same query parameters produce the same recall regardless of segment size. The old formula's visit ratio collapsed toward zero on large segments — e.g., for $N = 20M$, the old formula gives ~0.01% visit while the new formula gives a consistent ~3-5%.

2. num_candidates becomes a meaningful tuning knob: The old formula ignored num_candidates entirely for IVF. The new formula makes num_candidates directly control the recall/latency tradeoff, analogous to how it works for HNSW.

3. Bounded and well-calibrated: The visit ratio is bounded between 0.5% and 5%. This range was calibrated against multi-segment benchmarks on Wiki-Cohere (768d, ~934K vectors) and GIST-1M (960d, 1M vectors), targeting IVF recall within ~5 points of HNSW recall at equivalent num_candidates values. The IVF 4-bit quantization recall ceiling is ~0.96 (reached at approximately 7-10% actual visit with 2x SOAR multiplier), and visiting beyond that wastes cycles without improving recall.

4. Log-scaled diminishing returns: The log scaling matches the empirical observation from benchmarks: recall improvement from additional visiting follow a concave curve — the first few percent of visiting produce the most recall improvement, with rapidly diminishing gains after ~5-7% visits.

Recommendation for users

For production workloads, users should set visit_percentage directly rather than relying on the default calculation derived from num_candidates. The visit_percentage parameter provides direct, predictable control over the recall/latency tradeoff:

• Lower visit_percentage (e.g., 1-3%) → faster queries, lower recall
• Higher visit_percentage (e.g., 5-10%) → slower queries, higher recall
• The sweet spot for most workloads is between 3% and 10%
• IVF recall with 4-bit quantization plateuas at ~0.96 regardless of visit budget — visiting beyond ~10% provides no further recall benefit

Using visit_percentage removes the indirection through num_candidates and gives an explicit, segment-size-independent knob for search quality. The default_visit_percentage field mapping option can also be set at index time to establish a per-index default.

Impact on existing users

This changes adjusts the default visit_percentage calculation for bbq_disk knn searches when visit_percentage is not explicitly set. The new Two-Signal formula visits a significantly higher fraction of vectors per segment compared to the previous default (which was often far too low, especially on large segments). This will increase search latency for many users but substantially improves recall, which was previously unacceptably low in many configurations. Users who were relying on the previous (faster but lower-recall) defaults should expect increased query times. To restore previous latency characteristics, set visit_percentage explicitly to a lower value. We strongly recommend setting visit_percentage directly to control the recall/latency tradeoff for your specific workload.

Full analysis on 4 tables:

Wiki-Cohere 768d (934K docs, 1 segment, IVF BBQ-4bit)

GIST-1M 960d (1.0M docs, 1 segment, IVF BBQ-4bit)

DBpedia-arctic 768d (4.6M docs, 1 segment, IVF BBQ-4bit)

MSMARCO-v2 1024d (72M docs, 1 segment, IVF BBQ-4bit)

FWIW: My opinion is that for dynamic visit ratio, we should compute the value for each segment separately, taking into account only the size of the segment instead of a value for all segments and the divide the work evenly.

FWIW: My opinion is that for dynamic visit ratio, we should compute the value for each segment separately, taking into account only the size of the segment instead of a value for all segments and the divide the work evenly.

Yes — the Two-Signal formula computes a visit ratio (not an absolute count), and each segment independently applies that ratio to its own size via IVFKnnSearchStrategy.

Check IVFVectorsReader.java ~line 327:

long maxVectorVisited = (long) (2.0 * visitRatio * numVectors);

where numVectors = values.size() (line ~300) is per-segment, not the total index size.

Oh. I thought that if we are moving to compute this ratio in a per segment basis, there is not really point to compute it in the query and instead doing it in the codec (I hate we had this code in two places). I see. you have not changed the implementation here:

https://github.com/ah89/elasticsearch/blob/3a3173511d50d6631c6cb7c11b0f4980fd1bb2c8/server/src/main/java/org/elasticsearch/index/codec/vectors/diskbbq/IVFVectorsReader.java#L323

Are you planing to do something with this?

I see that maxVectorVisited is dependant on the size of the segment but the visit ratio is the same for each segment.

My experience is that the visit ratio can be smaller as the segment gets bigger to hit a specific recall.

Yes, every segment gets the same visit ratio, regardless of whether it contains 100K or 70M vectors. That makes sense given the uniform treatment of segments when no prior information is provided.

If, however, you mean that larger segments should have a smaller ratio because of IVF clustering, I can add a SEGMENT_SIZE_REFERENCE so the visit ratio changes based on the number of vectors in each segment. Since IVF groups vectors into buckets for faster search, it tends to work better as the amount of data grows.

@ah89 @iverase

I think this linear transformation we have in this PR is a good starting point. @ah89 please do adjust the other places were we are using the old formulae.

What do y'all think of having a small and limited bias that adjusts the final percentage according to segment size? It would have an asymptotic limit (to prevent bad scenarios like 0.00001% visit), and start near 0 when number of vectors is <10k?

I think a segment-size bias makes sense — large segments have better-populated IVF clusters so they need a smaller visit fraction, and tiny segments (<10K) with poor clustering could benefit from visiting more. That said, our Two-Signal formula already produces very small ratios (0.3%–4%), so the effect of an additive bias near 0 for small segments may be minimal. It also adds a tuning dimension that's hard to calibrate without benchmarks across many segment sizes.

I'm leaning towards adding this as a follow-up once we have more data, but I'll leave it to @benwtrent @iverase to decide.

I am fine leaving it as a follow up.

My suggestion is to index a fixed number of documents and force merge into one segment. Then compute how much visit percentage is needed to achieve a target recall.

Try the same thing for different number of documents so we can get a nice curve segment-size / visit percentage.

If we do it for a few datasets we can get a good idea on how visit percentage should change with the segment size?

@benwtrent

Please verify IVFVectorsReader#search. It is possible that this format is called without the IVF strategy and thus your logic won't work in that scenario.

Good catch — verified and fixed. When called without IVFKnnSearchStrategy (e.g., CheckIndex, tests), numCands=0 and the Two-Signal model produces a fixed visit ratio (~0.004) regardless of segment size, which visits nearly nothing on small segments.

Fixed by splitting the dynamic fallback: when numCands > 0 (IVF strategy with dynamic ratio), use Two-Signal; when numCands == 0 (no strategy), fall back to the original segment-size-aware formula (log10(N)² * k / N).

Do you have a better idea?

I am fine leaving it as a follow up.

My suggestion is to index a fixed number of documents and force merge into one segment. Then compute how much visit percentage is needed to achieve a target recall.

Try the same thing for different number of documents so we can get a nice curve segment-size / visit percentage.

If we do it for a few datasets we can get a good idea on how visit percentage should change with the segment size?

@iverase @benwtrent Here are the segment-size vs visit-percentage curves.

Setup: Same dataset indexed at different sizes (10K, 50K, 100K, 250K, 500K, full), force-merged to 1 segment, IVF BBQ-4bit, k=10, nc=1000. Sweep visit% from 0.1% to 20%.

GIST-1M (960d, euclidean)

Recall at each visit percentage

Minimum actual visit% for target recall

Wiki-Cohere (768d, MIP)

Recall at each visit percentage

Minimum actual visit% for target recall

Key observations & Possibilities

1. Larger segments need a smaller visit% for the same recall. IVF clustering becomes more effective with more data. To reach recall=0.90:

   • GIST: N=10K → 28% actual visit vs N=1M → 5%
   • Wiki-Cohere: N=10K → 43% vs N=934K → 4%

2. The relationship is roughly inverse-logarithmic. Going from 10K→100K (10×) cuts the required visit% by ~3×. Going from 100K→1M (10×) cuts it by another ~2×.

3. Small segments (<50K) need disproportionately more visiting because IVF clusters are poorly populated and quantization noise has more impact.

4. Note on actual vs configured visit%: SOAR causes actual visit% to be ~2× the configured value. The "minimum visit%" table uses actual visit%, which is the true cost. Very small segments also get a floor from minimum cluster visits.

The data clearly shows our current Two-Signal model (fixed ratio regardless of segment size) works well for segments ≥100K, but under-visits small segments. This supports @benwtrent's segment-size bias idea. Given that the data is now available and the shape of the curve is clear, do you think we should add the segment-size bias in this PR, or keep it as a follow-up?

10K vectors went from 0.77 → 0.94 recall (+0.17), 100K went from 0.86 → 0.98 (+0.12). The bias is applied per-segment, which means it fires for ALL sizes here. The threshold of for small segments is N_REF=500k.

New : with Bias
Old: without Bias

@ah89 this shows me that in a realistic scenario, adding the bias the way you did is expensive with no realistic benefit.

The bias that Ignacio was focusing on was REDUCING the visit percentage as segments get larger, not significantly increasing the visit percentage on smaller segments. I think the answer there is simply because the clusters are static and larger. We should not optimize for tiny segments, that just isn't realistic. Things will be merged and we will have a diversity of segment sizes.

@ah89 @iverase

I think this linear transformation we have in this PR is a good starting point. @ah89 please do adjust the other places were we are using the old formulae.

What do y'all think of having a small and limited bias that adjusts the final percentage according to segment size? It would have an asymptotic limit (to prevent bad scenarios like 0.00001% visit), and start near 0 when number of vectors is <10k?

@benwtrent This change is addressing your earlier point on small segments (<10k or so).

The bias improves recall, but it increases visit % significantly and adds ~1–2ms latency while applying to all segment sizes (N_REF=500k).

So it’s still a tradeoff for limited benefit in the scenarios we care about, and it’s different from Ignacio’s focus on larger segments. My point on his suggestion is the same as mentioned before, beyond uniformity, this starts to feel ad hoc data dependent solution.

Add segment-size-aware visit ratio cap to IVF search

Motivation (as per @iverase suggestion)

The Two-Signal model computes a dynamic visit ratio from num_candidates/k and k, producing values in [0.3%, 4%]. This works well for typical segment sizes (~100K–500K vectors), but for large segments (1M+ vectors), IVF clusters are better-formed and 4% visit is unnecessarily high — wasting latency without improving recall. Conversely, for very small segments the existing range is already appropriate.

Experiment Design

We ran controlled benchmarks across four datasets to measure recall as a function of visit% and segment size:

GIST & Wiki-Cohere sweep: Force-merged to 6 segment sizes (10K, 50K, 100K, 250K, 500K, full) × 11 visit percentages (0.1%–20%), k=10, nc=100, IVF 4-bit BBQ.

DBpedia segment sweep: 7 segment counts (1, 2, 4, 6, 8, 10, 12 segments → ~515K to 4.6M docs/segment) × 10 visit percentages (0.1%–20%).

DBpedia ceiling + oversampling test: Tested visit% up to 70% to find the recall ceiling (0.90–0.92 without oversampling), then tested oversample=5x and 10x (5x sufficient, 10x identical).

Formula

Fitted a power-law curve to the empirical data:

cap(N) = 0.045 × (1,000,000 / N)^0.35 × (0.1 / (1 - targetRecall))

Where N = number of vectors in the segment, targetRecall = 0.9 (default).

Example cap values (targetRecall=0.9):

Per-Segment Application

The cap is computed independently for each segment at search time. In IVFVectorsReader.search(), each segment knows its own numVectors = values.size() and computes:

visitRatio = Math.min(computeDynamicVisitRatio(numCands, k), computeSegmentSizeCap(numVectors));

This means in a multi-segment index, each segment gets a different final visit ratio based on its size. A 100K-doc segment gets cap≈10% (two-signal dominates since max is 4%), while a 5M-doc segment gets cap≈2.6% (cap dominates). The two-signal value is the same across all segments (it depends only on query parameters nc and k), but the cap varies per segment.

Comparison: origin/main vs Branch (Two-Signal + Cap)

All runs: IVF BBQ-4bit, k=10, visit_percentage=0.0 (dynamic), no force-merge.

Wiki-Cohere (934K docs, 2 segments, ~467K docs/seg)

GIST-1M (1M docs, 3 segments, ~333K docs/seg)

DBpedia-Arctic (4.6M docs, 9 segments, ~515K docs/seg)

Key Observations

1. Low nc (15–100): Branch visits significantly more → much higher recall (Wiki +0.30, DBpedia +0.57) at modest latency increase
2. Mid nc (~1000): Both approaches converge to similar recall/latency
3. High nc (5000–10000): origin/main visits explode (360K–900K vectors) while branch caps at a bounded count, saving 10–23ms per query on GIST/Wiki and 3–17ms on DBpedia with only 0.04–0.12 recall trade-off
4. The Two-Signal model makes num_candidates a meaningful tuning knob — origin/main's log10(N)² × k / N formula ignores it entirely