HarperFast / HarperFast/harper

Flaky test: HNSW greedy routing (ROUTING_EF) returns a different neighbour set than full-ef search

Open
#2,306 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
JavaScript
Stars
89
Forks
10
Avg merge
2d 6h
Merged PRs (30d)
200

Description

## Symptom

`unitTests/resources/vectorIndex.test.js:1009` — *"HNSW greedy routing above layer 0 (ROUTING_EF) returns the same neighbours as searching every layer at the full ef"* — fails intermittently in `Unit Test`, on one Node version while the others pass **the same commit**.

```
AssertionError: greedy descent changed the result set for target 3
+ actual '538,537,536,535,505,534,503,502,533,549' <- greedy
- expected '450,461,460,449,459,448,458,472,439,447' <- full ef at every layer
```

## What the numbers say

The test computes both sides at runtime: `greedy[i]` from a normal `T.search(...)`, then monkey-patches `customIndex.searchLayer` to use the resolved layer-0 ef at every level and re-runs.

Across three runs of the same commit (harper#2202, Node 22, attempts 1 and 3):

| run | `expected` (full ef) | `actual` (greedy) |
|---|---|---|
| 1 | `450,461,460,449,459,448,458,472,439,447` | `527,526,525,524,494,493,523,492,491,522` |
| 3 | `450,461,460,449,459,448,458,472,439,447` | `538,537,536,535,505,534,503,502,533,549` |

**The full-ef side is byte-identical; the greedy side differs every time.** The two id sets are also fully disjoint ranges rather than a near-miss reordering, so this is not a ranking tie-break.

## Why it looks nondeterministic rather than version-specific

It has now been observed failing on **different Node versions on different PRs** — v24 on harper#2173 (2026-08-14, v22 and v26 green on that same commit), v22 here on harper#2202 (v24 and v26 green, failed 2 of 3 attempts). A version-specific defect would not move.

It also does **not** reproduce locally: `npm run test:unit:resources` on Node 22 passes (1687/0), as does the `HARPER_STORAGE_ENGINE=lmdb` leg (1438/0).

## Why it matters

It is currently a coin-flip gate on unrelated PRs — it blocked harper#2202 for three rerun cycles, on a change that touches only SQL authorization and cannot reach the vector index. Each occurrence costs a full CI cycle and invites misattribution to the PR under review.

## Suggested direction

Either seed whatever varies in graph construction/entry-point selection so both sides are reproducible, or assert a weaker invariant than exact set equality (e.g. recall overlap above a threshold) if greedy descent is legitimately allowed to differ. The comment above the test says the intent is "descending greedily must not cost accuracy" — that is a recall claim, and exact id-set equality is a stricter proxy for it.

Contributor guide

Open the contributing guide

Research direction

Start at unitTests/resources/vectorIndex.test.js:1009 and inspect the normal T.search call alongside the monkey-patched customIndex.searchLayer path. Run npm run test:unit:resources and compare the greedy and full-ef results across Node versions or repeated runs. Done means graph construction or entry-point selection is reproducible, or the assertion checks the intended recall invariant rather than exact set equality.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript, node.js
Domain
testing-qa
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
50/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.