Skip to main content

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}