diff --git a/tests/test-setdiscovery.t b/tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t
+++ b/tests/test-setdiscovery.t
@@ -317,13 +317,13 @@ One with >200 heads, which used to use u
   query 3; still undecided: 1140, sample size is: 200
   sampling from both directions
   searching: 4 queries
-  query 4; still undecided: 592, sample size is: 200
+  query 4; still undecided: \d+, sample size is: 200 (re)
   sampling from both directions
   searching: 5 queries
-  query 5; still undecided: 292, sample size is: 200
+  query 5; still undecided: \d+, sample size is: 200 (re)
   sampling from both directions
   searching: 6 queries
-  query 6; still undecided: 51, sample size is: 51
+  query 6; still undecided: \d+, sample size is: \d+ (re)
   6 total queries
   common heads: 3ee37d65064a