lance-format / lance-format/lance

bug: dist_table u16 accumulator may overflow at production dimensions, and the kernels disagree when it does

Open
#8,908 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

rust/lance-linalg/src/simd/dist_table.rs accumulates 4-bit distance tables into u16, and the scalar and SIMD kernels disagree on what happens when that overflows: the scalar reference uses saturating_add, while the AVX2 and NEON kernels use _mm256_add_epi16 and vaddq_u16, which wrap.

The file's one note on this, on the doc comment of test_simd_matches_scalar_varied_dimensions, says the divergence does not matter because "overflow never occurs with real quantized data". The arithmetic does not obviously support that at production dimensions.

Each row accumulates two table lookups per code byte, and quantize_dist_table_into in rust/lance-index/src/vector/bq/dist_table_quant.rs maps every entry onto the full 0..255 with factor = 255 / (qmax - qmin). So a row's sum runs to 510 * code_len and averages around 255 * code_len. For 1-bit codes, code_len = dim / 8:

dim code_len mean sum max sum
1024 128 ~32,600 65,280
1536 192 ~49,000 97,920
3072 384 ~97,900 195,840

u16::MAX is 65,535, so the maximum crosses it from code_len = 129 and the mean crosses it before dim 3072. This is the u16 path used by ApproxMode::Fast.

What I have not done is measure it on a real dataset: the numbers above assume quantized entries spread over the full range, and real distance tables may concentrate low enough that rows stay under the bound in practice. That measurement is what should settle this, and it decides between three outcomes: the comment is right and should say why, the comment is wrong and the accumulator should widen to u32, or the comment is wrong and the two kernels should at least agree.

Nothing here is introduced by any open pull request; every existing AVX2 and NEON host already wraps. It surfaced while reviewing #8866, which widens the set of hosts that take a wrapping kernel rather than the saturating scalar one, and which names the divergence rather than resolving it.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with rust/lance-linalg/src/simd/dist_table.rs and its test_simd_matches_scalar_varied_dimensions test, then inspect quantize_dist_table_into in rust/lance-index/src/vector/bq/dist_table_quant.rs. Measure real distance-table values at production dimensions and compare scalar, AVX2, and NEON behavior. Done means the comment is justified with evidence, or the accumulator and kernel behavior are made consistent.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.