# Changelog
All notable changes to this project are documented here. The format follows
[Keep a Changelog](https://keepachangelog.com/en/1.1.0/), and this project
follows [Semantic Versioning](https://semver.org/spec/v2.0.0.html). The 0.x
series is unstable: minor bumps may break the public API.
## [Unreleased]
## [0.8.1] - 2026-04-30
### Fixed
- `HNSWIndex::search` and `batch_search_mqo` now also normalize the query
when `auto_normalize=true` for cosine and angular metrics. Previously the
flag normalized inserts only, so search queries silently produced
meaningless distances under cosine (the dot-only fast path assumes both
sides are unit-norm). The Python binding already did this in `prep_query`;
the Rust API now matches.
- README HNSW snippet ran but raised `InvalidParameter` on cosine because
the constant `[0.1; 128]` isn't unit-norm. Now uses `auto_normalize(true)`
on the builder so the literal copy-paste works.
- README IVF-PQ snippet trained 256 clusters on 2 vectors and silently
returned distance=0 for every result. Reframed as API-shape with a note
about training-data scale plus a pointer to `examples/ivf_pq_demo.rs`.
### Added
- `pyvicinity` Python bindings on PyPI (abi3 wheel, CPython 3.9+).
Ships hand-written `.pyi` stubs + `py.typed` (PEP 561), exposes
`HNSWIndex` + `DistanceMetric`. Verified in CI by `mypy.stubtest`,
`mypy --strict`, `ruff`, and 25 pytests.
- `examples/python/`: text similarity (sentence-transformers),
recall@k sweep, and ann-benchmarks/VIBE drop-in wrapper.
- Sentinels `pyvicinity.MISSING_LABEL` (= -1) and
`pyvicinity.MISSING_DISTANCE` (= +inf) for masking short rows in
`batch_search` results, matching faiss's convention.
- `auto_normalize` constructor flag normalizes vectors on **both**
insert and query (closes the hnswlib #592 class of correctness
bug). Rejected at construction with `L2`/`InnerProduct` since those
metrics don't have spherical semantics.
- CI gate on `publish-pypi` workflow: aborts unless the source SHA's
`ci.yml` run is `success`.
- musllinux x86_64 + aarch64 wheel matrix in publish-pypi.
### Changed
- All GitHub Actions in `publish-pypi.yml` pinned to specific minor
versions instead of mutable major tags.
## [0.8.0] - 2026-04-27
### Changed (breaking)
- Renamed `esg` module to `range_filtered`. The 0.7.x `esg` name implied
fidelity to the partition-aware structure of Yang et al. 2025
(arXiv:2504.04018); the shipped implementation is the paper's
strawman baseline (HNSW + attribute-range post-filter), so the rename
reflects what the module actually does. A paper-fidelity ESG variant
is planned as a separate module.
- `EsgIndex` -> `RangeFilteredIndex`
- `EsgParams` -> `RangeFilteredParams`
- feature `esg` -> `range_filtered`
- module path `vicinity::esg::*` -> `vicinity::range_filtered::*`
- `RangeFilteredParams::num_checkpoints` removed (was deprecated in
0.7.3; the partition-aware path that consumed it was never
implemented).
- `vicinity::spectral` module visibility downgraded from `pub` to
`pub(crate)`. The Marchenko-Pastur helpers were reachable only via
`ADSamplingState::new_auto`, which has no production consumer. The
`rmt-spectral` feature and the `rmt` dep remain available for the
internal `new_auto` path; the public wrappers `mp_lambda_plus` and
`count_mp_outliers` are no longer accessible from outside the crate.
### Migration from 0.7.x
```diff
-vicinity = { version = "0.7", features = ["esg"] }
+vicinity = { version = "0.8", features = ["range_filtered"] }
-use vicinity::esg::{EsgIndex, EsgParams};
+use vicinity::range_filtered::{RangeFilteredIndex, RangeFilteredParams};
let params = EsgParams {
- num_checkpoints: 16, // remove
hnsw_m: 16,
hnsw_ef_construction: 200,
ef_search: 100,
};
```
## [0.7.2] - 2026-04-27
### Changed
- `FreshGraphIndex::insert` no longer rebuilds the per-node `inbound_count`
array from scratch on every call. The count is maintained as a struct
field across `add_slice` / `insert` / `build` / `compact` and updated
per neighbor-list mutation. Per-insert cost was
`O(max_degree²) + O(n × max_degree)` and is now `O(max_degree²)` -
flat in `n` once every node is at cap. Measured on Apple Silicon at
dim=32, max_degree=16: ~120 µs/op at n=10K..50K vs an extrapolated
~920 µs/op pre-fix at n=50K (~7x speedup at scale). Both
reachability invariants (I1 entry-point liveness, I2 in-edge
survival under reverse-edge prune) survive the refactor.
- `HNSWIndex::save_to_file` is now atomic and durable. Writes to a
sibling temp file, fsyncs the temp, atomically renames into place,
then fsyncs the parent directory so the rename survives a crash on
filesystems that journal data and metadata independently (XFS,
some ext4 configs, overlayfs). A crash mid-write leaves the prior
file intact rather than truncated. P-HNSW (MDPI 2025) flagged
partial-write corruption as a recurring failure mode; this routine
is the in-tree counterpart to
`durability::storage::FsDirectory::atomic_write` (which is gated
behind the `persistence` feature). Cost: ~13 ms/op (durability
syncs) vs ~0.5 ms/op for the prior non-atomic path; trade-off is
correctness, dominated by typical save cadence.
- `AcornConfig` docstring now names the selectivity regimes where
2-hop expansion is load-bearing (2-20%), where it's overhead
(>20%), and where it hits a recall floor (<2%, fall back to
`selectivity_search` with `matching_ids`). Doc-only change;
`selectivity_search`'s Low branch already routes correctly.
### Added
- `acorn_search_with_stats` returns an `AcornStats { two_hop_invocations,
two_hop_nodes_examined }` struct alongside results, so regression
tests can assert "the 2-hop branch fired N>=1 times" rather than
relying on a noisier black-box recall delta. The existing
`acorn_search` becomes a thin wrapper that discards stats; signature
unchanged. `AcornStats` is `#[non_exhaustive]` so additional
counters can be added without bumping major. The wrapper has no
measurable overhead in release builds (Rust inlines the
discard-stats indirection; measured 803 ns/op for both entry
points).
- `tests/hnsw_integration_tests.rs::test_acorn_two_hop_branch_fires_at_sparse_selectivity`
asserts the 2-hop branch fires at least once at ~2.5% selectivity.
Verified to catch the gate-disabled regression by toggling
`enable_two_hop=false` and confirming the assertion fires with
`two_hop_invocations=0`.
- `src/hnsw/graph.rs::tests::test_delete_with_repair_preserves_self_search_reachability`
asserts every surviving doc_id is self-search-reachable after
deleting 60% of nodes via `delete_with_repair`. Existing tests
stop at 20-30% deletion and check result count or top-k recall;
this guards the failure mode where many cumulative repair calls
leave individual live nodes orphaned.
- `src/fresh_graph/mod.rs::tests::build_post_state_every_non_entry_node_has_inbound_edge`
is a static post-build connectivity guard: every non-entry node
has at least one inbound edge. Adapted from qdrant's
`test_graph_connectivity` shape, parameterized over five seeds.
Catches build-time orphans the dynamic delete-reinsert cycle
test wouldn't surface.
- `src/hnsw/graph.rs::tests::test_hnsw_save_to_file_uses_rename_not_truncate`
is a Unix-only inode-based gate guard: truncate-overwrite preserves
the inode, rename-overwrite replaces it. Verified to catch the
regression by reverting `save_to_file` to non-atomic and confirming
this test fails (left==right) while the happy-path roundtrip tests
still pass.
- `src/hnsw/graph.rs::tests::test_hnsw_build_save_reload_search_equality`
end-to-end build -> save_to_file -> drop -> load_from_file -> search-
equality round-trip via the path-based API on a fresh live index.
Plugs the gap between the in-memory roundtrip (already covered)
and the v0 fixture decode tests (which pin a static byte sequence
but don't exercise the writer).
- Three `#[ignore]`'d perf probes (`orphan_protection_scaling_probe`
extended to n=50K; `save_to_file_overhead_probe`;
`acorn_stats_overhead_probe`) for one-shot validation of the
changes above. Same shape as the existing scaling probe; not run
in CI.
### Dependencies
- No upstream dependency bumps. The session also added a
`sync_parent_of_path` helper to `durability` (0.6.4) for the
upstream concern that motivated `save_to_file`'s atomic refactor;
vicinity's own `save_to_file` inlines the equivalent pattern
rather than taking the helper as a dep, since `save_to_file` is
`serde`-gated and `durability` is `persistence`-gated.
## [0.7.1] - 2026-04-26
### Added
- Real v0.6.2-written segment fixture under `tests/fixtures/v0_segment_dim8/`
(~2.6 KB total) and a regression test
(`real_v0_fixture_loads_and_searches_correctly`) that loads it via
the v1 reader and asserts the search ordering matches the original
v0.6.2 run. Guards the legacy v0 decode path against silent
regression and documents that 0.6.x → 0.7.x persistence migration
works on real data. The 0.7.0 test set only proved no-panic on
random bytes; it did not prove correctness on a real legacy file.
- `tests/edge_cases.rs::search_returns_external_doc_ids_at_high_offset`
pins the external-`doc_id` contract at `u32::MAX - 200` (catches a
regression where the search path returns an internal slot index).
- `tests/edge_cases.rs::zero_query_does_not_panic_with_auto_normalize`
pins the documented zero-query path: search returns finite distances
or an explicit error, never a panic on the `0 / ||q||` normalization
step.
- `src/hnsw/graph.rs::tests::test_delete_with_repair_recall_floor_against_ground_truth`
is a recall-floor companion to the existing
`test_delete_with_repair_maintains_recall`. The original asserts
result count and absence-of-deleted-ids; this adds a
recall-vs-brute-force ground-truth assertion at >= 0.7 after
deleting 20% of nodes.
- `tests/hnsw_integration_tests.rs::test_acorn_low_selectivity_returns_valid_results`
guards ACORN at ~2.5% predicate selectivity. An earlier draft
compared `enable_two_hop` true vs false and asserted a positive
recall gap; in measurement the gap flipped sign at sparse
selectivity (2-hop adds candidates that displace better ones in a
tight beam). Reframed as a sparse-predicate regression guard with a
0.5 recall floor.
- `src/fresh_graph/mod.rs::tests::delete_reinsert_cycles_preserve_reachability`
guards two FreshGraph invariants that together close the
delete-reinsert unreachability failure mode of arxiv:2407.07871:
(I1) `entry_point` always references a non-tombstoned internal id,
and (I2) `insert`'s reverse-edge prune never evicts a node whose
only remaining in-edge would be the one through the neighbor being
pruned at. Runs 200 cycles on a 60-vector graph and asserts every
live `doc_id` is self-search-reachable. The assertion message names
the broken invariant when it fires.
- `src/fresh_graph/mod.rs::tests::orphan_protection_scaling_probe`
(`#[ignore]`'d, run with `--release --nocapture`) measures per-insert
cost of the orphan-protection rebuild as `n` grows. Sample on Apple
Silicon, dim=32: 12 µs/op below max-degree saturation, 300+ µs/op
once every node hits cap. Validates the rebuild-per-call cost is
acceptable at FreshGraph's target n; informs whether incremental
inbound-count maintenance is worth designing.
### Changed
- `DistanceMetric::InnerProduct` doc comment now states that the
caller is responsible for L2-normalization. Un-normalized
inner-product ranking is dominated by magnitude, which is rarely
the intended retrieval behavior (Milvus discussion #32479).
- `FreshGraph::build` and `FreshGraph::insert` now share a single
`add_reverse_edge_protected` helper. Previously the reverse-edge
prune was duplicated between the two paths and only `insert` had
orphan protection. The build path now applies the same I2 invariant
symmetrically: the initial RNG-prune pass cannot evict a node whose
only remaining in-edge would be the one being considered.
### Fixed
- FreshGraph delete-reinsert unreachability. Two paired changes:
- `delete()` now repromotes `entry_point` when it tombstones the
medoid. Previously the entry-point field was left pointing at the
deleted internal index, so subsequent searches and inserts rooted
their beam at a dead anchor. Repromotion prefers a live neighbor
of the stale entry (preserves graph locality) and falls back to a
linear scan over live nodes only if the entire neighborhood is
tombstoned.
- `insert()`'s reverse-edge prune now computes a per-insert
inbound-degree count, marks any candidate whose count is `<= 1`
as orphan-protected, and runs RNG-prune only over the unprotected
remainder. Without this, repeated cycles can evict a long-existing
in-edge from every list that referenced it, leaving its target
unreachable even though the node was never deleted.
- The two changes are paired because the entry-point fix alone
leaves the same unreachable set on the regression test (5 of 60
live ids after 200 cycles). The orphan-protection change is the
load-bearing one; the entry-point fix is shipped because rooting
search at a tombstoned anchor is incorrect on its own merits.
## [0.7.0] - 2026-04-26
### Added
- HNSW segment binary persistence now starts with a magic + version header
(`HNSW_SEGMENT_MAGIC = b"VCNHNSW\x01"` + `FORMAT_VERSION: u32 = 1`).
Mismatched magic returns `PersistenceError::Format` instead of silently
decoding garbage; unsupported version numbers return a descriptive error.
Files written by 0.6.x lack the magic — the load path falls back to a
legacy v0 decoder, so existing persisted indices round-trip transparently.
- `tests/persistence_robustness.rs::segment_binary` module:
`loading_corrupt_magic_returns_format_error` (sanity), and
`proptest_one_byte_corruption_never_panics` (random byte flip in the
metadata header always produces `Result::Err`, never a panic).
### Fixed
- `docs/GUIDE.md` outlier-detection example referenced a non-existent
`LidEstimate.category` field. Switched to `LidStats::from_estimates(&est).categorize(lid)`,
which is what `examples/lid_outlier_detection.rs` already does.
- Three rendered intra-doc-link errors in `src/lemur/model.rs` (`[hidden_dim]`
was parsed as a link target by rustdoc). All shape annotations now use
backticked code so they render literally.
- `docs/datasets.md` referenced a non-existent `hdf5` Cargo feature. Updated
to point at `scripts/download_ann_benchmarks.py` (the actual conversion path).
- `lib.rs` recommendation table claimed DiskANN persistence was mmap-based;
`src/diskann/disk_io.rs:95` documents it as planned. Now reads "file-based
save/load; mmap planned".
- README and benchmark-results.md called the GloVe-25 dataset "cosine"; the
ann-benchmarks dataset and the rendered plot are angular distance.
- README's NSG row claimed a 50K hard cap; the limit is empirical, not
enforced. Reworded to "build slows above ~50K vectors".
### Changed
- `docs/GUIDE.md` quickstart now uses `HNSWIndex::builder` to match the README
and the bulk of the examples. The direct `HNSWIndex::new(dim, m, m_max)`
constructor is still exposed.
- README's Supported Algorithms table now surfaces LSH (cross-polytope) and
`LsmIndex` (LSM-tree streaming HNSW), both previously implemented but
undocumented.
- `KD-Tree`, `Ball Tree`, and `RP-Forest` rows are flagged "(experimental)"
per `src/classic/mod.rs`.
## [0.6.2] - 2026-04-25
### Changed
- CI tightened to `-D warnings` for clippy across the per-feature matrix.
- Fixed six pre-existing clippy issues in production code (uncovered by the
stricter CI).
- Test code is now allowed to use `unwrap`/`expect`/`needless_update` via
scoped `#[cfg_attr(test, allow(...))]` in `lib.rs`.
[`6b92ae9`](https://github.com/arclabs561/vicinity/commit/6b92ae9) ·
[v0.6.1...v0.6.2](https://github.com/arclabs561/vicinity/compare/v0.6.1...v0.6.2)
## [0.6.1] - 2026-04-23
### Added
- `publish-pypi` GitHub Actions workflow with OIDC trusted publishing and a
full wheel matrix.
### Changed
- Python package renamed `vicinity` → `pyvicinity` for PyPI registration.
### Fixed
- IVF-RaBitQ cross-cluster ranking via the qntz typed-edge API (corrected a
cross-cluster comparability bug introduced when residuals are evaluated
against different cluster centroids).
[v0.6.0...v0.6.1](https://github.com/arclabs561/vicinity/compare/v0.6.0...v0.6.1)
## [0.6.0] - 2026-04-22
### Added
- Vamana parallel build with batched rayon and deferred pruning. Measured
9.5x speedup on SIFT-128 (35 min → 3.7 min) and 7.1x on GIST-960; default
build batch is 4096.
- DiskANN parallel build (same batched-rayon pattern as Vamana).
- NSW parallel build.
- Batched distance computation in HNSW beam search (Faiss pattern). +10% QPS
at `ef=100` on SIFT-128.
- SymphonyQG-VR (vertex-relative) variant with per-parent residual encoding,
ported to qntz's type-safe edge API.
### Changed
- Module docs across the crate were updated to drop stale version references
and machine-specific numbers from public doc comments.
- README opening trimmed to undersell tone (one-line description; no feature
list in the tagline).
### Fixed
- SymphonyQG-VR cross-space bias: recall jumped from 55-86% to 99.9% at ef=400
on the standard benchmark after correcting the cross-parent distance
comparison.
- SymphonyQG-VR cross-parent distance comparability (precondition for the
bias fix above).
### Removed
- Per-parent VR residual (kept the simpler global-rotation variant after the
per-parent variant showed no recall benefit).
[v0.5.0...v0.6.0](https://github.com/arclabs561/vicinity/compare/v0.5.0...v0.6.0)
## [0.5.0] - 2026-04-12
Highlights from the 0.5 line: generation-counter visited-tracking in HNSW
search (replacing per-search HashSet allocation), devirtualized distance
dispatch, SymphonyQG search variant, and KD-Tree pruning improvements. See
`git log v0.4.0..v0.5.0` for the full commit list.
[v0.4.0...v0.5.0](https://github.com/arclabs561/vicinity/compare/v0.4.0...v0.5.0)
## [0.4.0] - 2026-04-05
Highlights: ADSampling integration, SQ4 (4-bit scalar quantization) module,
and dependency bumps for `innr`, `clump`, `sbits`, `rankops`. See
`git log v0.3.6..v0.4.0` for details.
[v0.3.6...v0.4.0](https://github.com/arclabs561/vicinity/compare/v0.3.6...v0.4.0)
## [0.3.x] - 2026-03 to 2026-04
The 0.3 line covered the initial public-API stabilization, the
`MetadataValue` enum and Range filter (breaking, in 0.3.5), and a series of
CI-greening commits. Earlier than 0.3 the project was pre-public; consult
`git log v0.3.0..` for full history.
[v0.3.0...v0.3.6](https://github.com/arclabs561/vicinity/compare/v0.3.0...v0.3.6)
[Unreleased]: https://github.com/arclabs561/vicinity/compare/v0.6.2...HEAD