diff --git a/rust/hg-core/src/discovery.rs b/rust/hg-core/src/discovery.rs
--- a/rust/hg-core/src/discovery.rs
+++ b/rust/hg-core/src/discovery.rs
@@ -32,7 +32,7 @@
     common: MissingAncestors<G>,
     respect_size: bool,
     randomize: bool,
-    seed: Seed,
+    seed: Option<Seed>,
 }
 
 pub struct WithUndecided<G: Graph + Clone> {
@@ -175,11 +175,13 @@
         respect_size: bool,
         randomize: bool,
     ) -> Self {
-        let mut seed = [0; 16];
-        if randomize {
-            thread_rng().fill_bytes(&mut seed);
-        }
-        Self::new_with_seed(graph, target_heads, seed, respect_size, randomize)
+        Com(OnlyCommon::new(
+            graph,
+            target_heads,
+            None,
+            respect_size,
+            randomize,
+        ))
     }
 
     pub fn new_with_seed(
@@ -192,7 +194,7 @@
         Com(OnlyCommon::new(
             graph,
             target_heads,
-            seed,
+            Some(seed),
             respect_size,
             randomize,
         ))
@@ -333,7 +335,7 @@
     fn new(
         graph: G,
         target_heads: Vec<Revision>,
-        seed: Seed,
+        seed: Option<Seed>,
         respect_size: bool,
         randomize: bool,
     ) -> Self {
@@ -355,7 +357,7 @@
     /// of this crate (wrapper around index Python object).
     /// We don't want to implement `Default` for it right away.
     fn default(graph: &G) -> Self {
-        Self::new(graph.clone(), Vec::new(), [0; 16], false, false)
+        Self::new(graph.clone(), Vec::new(), None, false, false)
     }
 
     /// Register revisions known as being common
@@ -388,10 +390,17 @@
         undecided: impl IntoIterator<Item = Revision>,
         children_cache: FastHashMap<Revision, Vec<Revision>>,
     ) -> Self {
+        let seed = disco.seed.unwrap_or_else(|| {
+            let mut seed: Seed = [0; 16];
+            if disco.randomize {
+                thread_rng().fill_bytes(&mut seed);
+            }
+            seed
+        });
         WithUndecided {
             undecided: undecided.into_iter().collect(),
             children_cache: children_cache,
-            rng: Rng::from_seed(disco.seed),
+            rng: Rng::from_seed(seed),
             graph: disco.graph.clone(),
             missing: HashSet::new(),
             respect_size: disco.respect_size,
@@ -640,9 +649,15 @@
     }
 
     fn full_disco_with_undecided() -> WithUndecided<SampleGraph> {
-        OnlyCommon::new(SampleGraph, vec![10, 11, 12, 13], [0; 16], true, true)
-            .compute_undecided()
-            .unwrap()
+        OnlyCommon::new(
+            SampleGraph,
+            vec![10, 11, 12, 13],
+            Some([0; 16]),
+            true,
+            true,
+        )
+        .compute_undecided()
+        .unwrap()
     }
 
     /// A PartialDiscovery as for pushing the 12 head of `SampleGraph`