fix(search): break score ties deterministically so ranking is reproducible - #303

Description

Two identical searches over an unchanged index can come back in a different order, and under a limit with a different set of results.

GOBStore.Search (store/gob.go:74) builds its result slice by ranging over the s.chunks map, and ReciprocalRankFusion (search/hybrid.go:73) builds its slice by ranging over its scores map. Go randomizes map iteration order on every call. Both then sort with sort.Slice, which is not stable, so any two results holding exactly the same score came out in an order that changed from one call to the next.

Equal scores are the normal case here rather than a corner case. RRF scores a result purely by its rank, 1/(k+rank+1), so in a hybrid search the top hit of the vector list and the top hit of the text list always tie, and so does every rank below them. In the store, identical code (boilerplate, generated files, the same helper vendored twice) embeds to an identical vector and gets an identical cosine score. Both functions truncate to the limit after sorting, so the coin flip decided not only the order but which results the caller ever saw.

Measured on main, fusing two disjoint three-result lists 1000 times produced 6 different orderings of the same 6 chunks, and the same fusion with limit=1 returned chunk a 604 times and chunk b 396 times.

The fix is store.SortResultsByScore (new, store/ranking.go): sort by descending score, break ties on the chunk ID. Chunk IDs are unique within a store, so the comparator is a total order and the output stops depending on the order the caller happened to build the slice in. All four score sorts in the search path use it now: GOBStore.Search, TextSearch, ReciprocalRankFusion and ApplyBoost. ApplyBoost is in that list because boost factors can map two different scores onto the same product and so create ties of their own, which the unstable sort then reordered.

Scores still decide the ranking. The chunk ID only settles an exact tie.

Related Issue

No open issue covers this. I hit it reading the hybrid search path.

Type of Change

• Bug fix (non-breaking change that fixes an issue)
• New feature (non-breaking change that adds functionality)
• Breaking change (fix or feature that would cause existing functionality to change)
• Documentation update
• Refactoring (no functional changes)
• Performance improvement
• Test update

How Has This Been Tested?

Six new tests pin the ordering. All six fail on main at b355512 and pass with the change:

$ go test -run 'TiedScores|RanksByScoreFirst' -v ./search/ ./store/     # on main, with the new tests copied in
--- FAIL: TestReciprocalRankFusion_TiedScoresAreDeterministic
    hybrid_test.go:186: call 0 returned [b a d c f e], want [a b c d e f]
--- FAIL: TestReciprocalRankFusion_TiedScoresKeepSameSubsetUnderLimit
    hybrid_test.go:201: call 20 returned [b], want [a]
--- FAIL: TestTextSearch_TiedScoresOrderByChunkID
    hybrid_test.go:220: TextSearch() = [d c b a], want [a b c d]
--- FAIL: TestApplyBoost_TiedScoresOrderByChunkID
    boost_test.go:170: ApplyBoost() = [d b c a], want [a b c d]
--- FAIL: TestGOBStore_SearchTiedScoresAreDeterministic
    ranking_test.go:65: call 0 returned [f e d c b a h g], want [a b c d e f g h]
--- FAIL: TestGOBStore_SearchTiedScoresKeepSameSubsetUnderLimit
    ranking_test.go:88: call 0 returned [g f e], want [a b c]

TestGOBStore_SearchRanksByScoreFirst and TestSortResultsByScore_ScoreWinsOverID go the other way: they pass on main too, and guard against a tiebreak that displaces scoring.

On this branch:

$ gofmt -l store/ranking.go store/ranking_test.go store/gob.go search/hybrid.go search/hybrid_test.go search/boost.go search/boost_test.go
(no output)
$ go vet ./...
(no output, exit 0)
$ golangci-lint run --timeout=5m ./search/... ./store/...     # v2.13.2, the version CI pins
0 issues.
$ go test -race ./search/ ./store/
ok  	github.com/yoanbernabeu/grepai/search	4.315s
ok  	github.com/yoanbernabeu/grepai/store	3.608s
$ go test -race ./...
exit 0, 14 packages ok, 0 failures

The tests are pure functions over in-memory chunks and a t.TempDir() GOB store, so no embedder, no network and no timing assumptions.

• Unit tests
• Integration tests
• Manual testing

Test Configuration:

• OS: macOS, darwin/arm64
• Go version: 1.26.4
• Embedding provider: none, the changed code sits below the embedder and the tests supply vectors directly

Checklist

• My code follows the project's code style
• I have run golangci-lint run and fixed any issues
• I have added tests that prove my fix/feature works
• I have updated the documentation if needed
• I have added an entry to CHANGELOG.md (if applicable)
• My changes generate no new warnings
• All new and existing tests pass

Screenshots (if applicable)

N/A

Additional Notes

Scope: this covers the sorts that happen in Go. The Postgres and Qdrant backends order inside the query engine (ORDER BY vector <=> $1, store/postgres.go:169) and have the same tie ambiguity. Pinning that needs a tiebreaking column in the SQL and a database to verify against, so it is not in this PR. Happy to do it as a follow-up, and happy to add a CHANGELOG line here if you want one.