bifrost/config.rs
1use crate::{Error, Result};
2
3/// Construction and search parameters for an HNSW index.
4#[derive(Clone, Copy, Debug, PartialEq)]
5pub struct Config {
6 /// Vector dimensionality.
7 pub dim: u16,
8 /// Maximum neighbors selected for a newly inserted node in layer zero.
9 ///
10 /// Must be greater than zero. Upper layers select at most
11 /// [`Config::new_node_neighbors`] neighbors (`max(m / 2, 1)`). New-node
12 /// links and reverse-link pruning both use the paper / hnswlib diversity
13 /// heuristic, then cap outgoing degree at [`Config::max_degree`]: `2 * m`
14 /// at layer 0 (`Mmax0`) and `m` at upper layers (`Mmax`). Pruning is
15 /// one-sided: a dropped outgoing edge is not removed from the peer, so
16 /// adjacency may become directed.
17 pub m: u8,
18 /// Candidate search width during insertion.
19 ///
20 /// Must be greater than zero. A stored value of `0` is rejected rather
21 /// than silently clamped during construction search.
22 pub ef_construction: u16,
23 /// Candidate search width during queries.
24 ///
25 /// Must be greater than zero. `search` uses `max(ef_search, k)` so a
26 /// request larger than this value still returns up to `k` hits.
27 pub ef_search: u16,
28 /// Highest level that may be assigned to a node.
29 pub max_level: u8,
30 /// Probability of stopping at the current randomly selected level.
31 ///
32 /// Insertion stops at the current level with this probability, so
33 /// `P(level >= L) = (1 - level_mult)^L`. [`Config::default`] uses
34 /// [`Config::level_mult_for_m`] (`1.0 - 1.0 / m`) so
35 /// `P(level >= L) = m^{-L}`, matching the HNSW paper and hnswlib.
36 /// `1.0` always assigns level zero; `0.0` always assigns
37 /// [`Config::max_level`]. Stored snapshots may keep any finite value in
38 /// `[0, 1]`, including the former `0.5` default.
39 pub level_mult: f64,
40 /// Optional seed for repeatable construction with the pinned `rand` version.
41 /// Operating-system entropy is used when absent.
42 pub rng_seed: Option<u64>,
43 /// When `true`, insert and search return [`crate::Error::InvalidVector`]
44 /// for non-finite coordinates or an L2 norm more than
45 /// [`crate::vector::UNIT_NORM_TOLERANCE`] from `1`.
46 ///
47 /// Default is `false`: release builds keep the previous unchecked
48 /// contract. Debug builds always `debug_assert` the same conditions so
49 /// NaN/Inf and clearly unnormalized inputs fail in development. The flag
50 /// is not stored in `.hnsw` snapshots; call
51 /// [`crate::LoadedHnsw::set_check_vectors`] after mapping.
52 pub check_vectors: bool,
53}
54
55impl Default for Config {
56 fn default() -> Self {
57 let m = 16;
58 Self {
59 dim: 384,
60 m,
61 ef_construction: 200,
62 ef_search: 100,
63 max_level: 16,
64 level_mult: Self::level_mult_for_m(m),
65 rng_seed: None,
66 check_vectors: false,
67 }
68 }
69}
70
71impl Config {
72 /// Stop probability that yields `P(level >= L) = m^{-L}`.
73 ///
74 /// This is the HNSW paper / hnswlib formula: `1.0 - 1.0 / m`. `m` must
75 /// be greater than zero. `level_mult` is stored independently of `m`, so
76 /// a struct update that changes only `m` should call this if the paper
77 /// distribution is wanted.
78 #[must_use]
79 pub fn level_mult_for_m(m: u8) -> f64 {
80 1.0 - 1.0 / f64::from(m)
81 }
82
83 pub(crate) fn validate(self) -> Result<Self> {
84 if self.dim == 0 {
85 return Err(Error::InvalidConfig("dim must be greater than zero"));
86 }
87 if self.m == 0 {
88 return Err(Error::InvalidConfig("m must be greater than zero"));
89 }
90 if self.ef_construction == 0 {
91 return Err(Error::InvalidConfig(
92 "ef_construction must be greater than zero",
93 ));
94 }
95 if self.ef_search == 0 {
96 return Err(Error::InvalidConfig("ef_search must be greater than zero"));
97 }
98 if self.max_level == 0 || self.max_level == u8::MAX {
99 return Err(Error::InvalidConfig("max_level must be between 1 and 254"));
100 }
101 if !self.level_mult.is_finite() || !(0.0..=1.0).contains(&self.level_mult) {
102 return Err(Error::InvalidConfig(
103 "level_mult must be finite and between zero and one",
104 ));
105 }
106 Ok(self)
107 }
108
109 /// Neighbors selected for a newly inserted node at `level`.
110 ///
111 /// Layer 0 uses [`Config::m`]; upper layers use `max(m / 2, 1)`.
112 #[must_use]
113 pub fn new_node_neighbors(&self, level: u8) -> u8 {
114 if level == 0 {
115 self.m
116 } else {
117 (self.m / 2).max(1)
118 }
119 }
120
121 /// Maximum outgoing degree after reverse-link pruning (HNSW `Mmax` / `Mmax0`).
122 ///
123 /// Layer 0 allows `2 * m` neighbors; upper layers allow `m`.
124 #[must_use]
125 pub fn max_degree(&self, level: u8) -> usize {
126 if level == 0 {
127 2 * usize::from(self.m)
128 } else {
129 usize::from(self.m)
130 }
131 }
132}
133
134#[cfg(test)]
135mod tests {
136 use super::*;
137
138 #[test]
139 fn defaults_are_stable() {
140 assert_eq!(
141 Config::default(),
142 Config {
143 dim: 384,
144 m: 16,
145 ef_construction: 200,
146 ef_search: 100,
147 max_level: 16,
148 level_mult: 0.9375,
149 rng_seed: None,
150 check_vectors: false,
151 }
152 );
153 assert_eq!(Config::default().level_mult, Config::level_mult_for_m(16));
154 assert_eq!(Config::level_mult_for_m(16), 1.0 - 1.0 / 16.0);
155 assert_eq!(Config::level_mult_for_m(8), 1.0 - 1.0 / 8.0);
156 }
157
158 #[test]
159 fn historical_level_mult_half_still_validates() {
160 assert!(
161 Config {
162 level_mult: 0.5,
163 ..Config::default()
164 }
165 .validate()
166 .is_ok()
167 );
168 }
169
170 #[test]
171 fn invalid_configs_are_rejected() {
172 assert!(matches!(
173 Config {
174 dim: 0,
175 ..Config::default()
176 }
177 .validate(),
178 Err(Error::InvalidConfig(_))
179 ));
180 assert!(matches!(
181 Config {
182 level_mult: f64::NAN,
183 ..Config::default()
184 }
185 .validate(),
186 Err(Error::InvalidConfig(_))
187 ));
188 assert!(matches!(
189 Config {
190 max_level: u8::MAX,
191 ..Config::default()
192 }
193 .validate(),
194 Err(Error::InvalidConfig(_))
195 ));
196 assert!(matches!(
197 Config {
198 m: 0,
199 ..Config::default()
200 }
201 .validate(),
202 Err(Error::InvalidConfig(_))
203 ));
204 assert!(matches!(
205 Config {
206 ef_construction: 0,
207 ..Config::default()
208 }
209 .validate(),
210 Err(Error::InvalidConfig(_))
211 ));
212 assert!(matches!(
213 Config {
214 ef_search: 0,
215 ..Config::default()
216 }
217 .validate(),
218 Err(Error::InvalidConfig(_))
219 ));
220 }
221
222 #[test]
223 fn neighbor_caps_follow_hnsw_mmax() {
224 let config = Config {
225 m: 16,
226 ..Config::default()
227 };
228 assert_eq!(config.new_node_neighbors(0), 16);
229 assert_eq!(config.new_node_neighbors(1), 8);
230 assert_eq!(config.max_degree(0), 32);
231 assert_eq!(config.max_degree(1), 16);
232
233 let tiny = Config {
234 m: 1,
235 ..Config::default()
236 };
237 assert_eq!(tiny.new_node_neighbors(3), 1);
238 assert_eq!(tiny.max_degree(0), 2);
239 assert_eq!(tiny.max_degree(2), 1);
240 }
241}