Approximate search breaks a different promise than cost

Status

To do

Component

server

Blocked by

a product decision, and SAPE-37's measurement

Blocks

—

The question

Not whether sapedb should have an approximate index — HNSW and IVF are what most people mean by vector search, and the owner has put vectors into 1.0.0. The question is how a result that may be wrong is presented honestly, in a product whose central claim is that nothing it returns is silently wrong.

The evidence, and it is the owner's own

From the owner's measurements of HNSW, published in their own material on the subject: a configuration reporting 97.75% mean recall was, broken down, 192 queries at 100%, 3 at 90%, 1 at 80% and 4 at 0%. Not every answer slightly worse — roughly one query in fifty wrong entirely.

And an answer at 0% recall looks exactly like an answer at 100%: k rows, each with a distance, in order. Nothing in it says it is wrong.

That is the same shape this board has refused three times today. hashRange refuses at its ceiling because a digest of part of a range is indistinguishable from a digest of all of it. deleteRange returns a flag saying it stopped. ISS-35 refuses a number rather than store a neighbouring one. In each case the rule was the same: a wrong answer must not look like a right one. An approximate index, left alone, breaks that rule by construction.

Why this is not a cost problem

The cost of an approximate search can be declared — ef_search, nprobe, a probe ceiling are all numbers written down before the call runs. That part fits. What does not fit is that the answer is probabilistic, and the probability is a property of the data and the build, not of the declaration. The owner's own measurements show five builds of one identical configuration landing between 97.75% and 99.75% — two points of spread from nothing but the build.

What would have to be decided

• Whether an approximate answer is marked as one. A flag on every result saying it came from an index and may be incomplete is the least a caller needs; whether it is enough is the decision.
• Whether exactness can be asked for. The same declared operation could offer exact search over the same field, so a caller who cannot tolerate a wrong answer is never forced into one. SAPE-37 is that path.
• Filtering. This store's operations are conditions plus a walk. A filtered approximate search has well-known failure modes — filtering after the index can collapse recall without any signal — which the owner's material covers in its own lesson on it.
• Whether 1.0.0 needs it at all, which depends on a number nobody has yet: up to what collection size and dimension exact search stays fast enough on the machine this product targets. That is being measured now, against the reporting standard in the owner's own material, and the result belongs on this page before this ticket is decided.

Why it is not simply scheduled after SAPE-37

Because the order of the decisions matters more than the order of the work. If approximate search lands first and without a marker, its results become part of what 1.0.0 promises, and marking them later is a change to the meaning of an answer that callers already rely on.