diff --git a/src/lib_benchmark/base_samplers.ml b/src/lib_benchmark/base_samplers.ml
index ad0e2ecc92b1fdd9b6469ba73fd1b6bfb8c9c262..cb4809060a45c53fcd99342ad5b7acba6f15792e 100644
--- a/src/lib_benchmark/base_samplers.ml
+++ b/src/lib_benchmark/base_samplers.ml
@@ -42,6 +42,11 @@ let sample_in_interval ~range:{min; max} state =
   if max - min >= 0 then min + Random.State.int state (max - min + 1)
   else invalid_arg "Base_samplers.sample_in_interval"
 
+let sample_float_in_interval ~min ~max state =
+  let diff = max -. min in
+  if diff > 0. then min +. Random.State.float state diff
+  else invalid_arg "Base_samplers.sample_float_in_interval"
+
 let uniform_bool = Random.State.bool
 
 let uniform_byte state = Char.chr (Random.State.int state 256)
diff --git a/src/lib_benchmark/base_samplers.mli b/src/lib_benchmark/base_samplers.mli
index 3665559681556c2151b9f7022aa3b179f43a4089..a37a5fabd16988d25541164d6c3f6112c13727f1 100644
--- a/src/lib_benchmark/base_samplers.mli
+++ b/src/lib_benchmark/base_samplers.mli
@@ -38,6 +38,12 @@ val range_encoding : range Data_encoding.t
  *)
 val sample_in_interval : range:range -> int sampler
 
+(** [sample_float_in_interval ~min ~max] creates a sampler in the
+    specified interval.
+    @raise Invalid_argument if [max <= min].
+*)
+val sample_float_in_interval : min:float -> max:float -> float sampler
+
 (** Samples a boolean uniformly at random *)
 val uniform_bool : bool sampler
 
diff --git a/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml b/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml
index 7efce6c2a750809a81a5207aef439ea2888ed8cc..a74bc9df4045f16e8a0a316dcb97efa0b524ff5a 100644
--- a/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml
+++ b/src/proto_alpha/lib_benchmarks_proto/skip_list_benchmarks.ml
@@ -78,9 +78,14 @@ module Next : Benchmark.S = struct
   let create_benchmarks ~rng_state ~bench_num ({max_items} : config) =
     List.repeat bench_num @@ fun () ->
     let workload =
-      Base_samplers.sample_in_interval
-        rng_state
-        ~range:{min = 0; max = max_items}
+      (* Since the model we want to infer is logarithmic in
+         the length, we sample the logarithm of the length
+         (and not the length itself) uniformly in an interval. *)
+      let logmax = log (float_of_int max_items) in
+      let loglen =
+        Base_samplers.sample_float_in_interval ~min:0. ~max:logmax rng_state
+      in
+      int_of_float (exp loglen)
     in
     let prev_cell = create_skip_list_of_len workload in
     let prev_cell_ptr = () in
@@ -144,11 +149,14 @@ module Hash_cell = struct
   let models = [("skip_list_hash", hash_skip_list_cell_model)]
 
   let benchmark rng_state conf () =
-    let skip_list_len =
-      Base_samplers.sample_in_interval
-        ~range:{min = 1; max = conf.max_index}
-        rng_state
+    (* Since the model we want to infer is logarithmic in
+       the length, we sample the logarithm of the length
+       (and not the length itself) uniformly in an interval. *)
+    let skip_list_loglen =
+      let logmax = log (float_of_int conf.max_index) in
+      Base_samplers.sample_float_in_interval ~min:0. ~max:logmax rng_state
     in
+    let skip_list_len = int_of_float (exp skip_list_loglen) in
     let random_hash () =
       Hash.hash_string
         [Base_samplers.string ~size:{min = 32; max = 32} rng_state]