diff --git a/centipede/BUILD b/centipede/BUILD
index f634d7e..f9dd983 100644
--- a/centipede/BUILD
+++ b/centipede/BUILD
@@ -947,6 +947,7 @@
     name = "runner_cmp_trace",
     hdrs = ["runner_cmp_trace.h"],
     copts = DISABLE_SANCOV_COPTS,
+    deps = ["@abseil-cpp//absl/base:core_headers"],
 )
 
 # Library for manipulating centipede runner flags. This is not used by the
diff --git a/centipede/byte_array_mutator_test.cc b/centipede/byte_array_mutator_test.cc
index 7c20d48..abc96b5 100644
--- a/centipede/byte_array_mutator_test.cc
+++ b/centipede/byte_array_mutator_test.cc
@@ -158,7 +158,7 @@
 }
 
 TEST(CmpDictionary, CmpDictionaryIsCompatibleWithCmpTrace) {
-  CmpTrace<0, 13> traceN;
+  CmpTrace<0, 13> traceN = {};
   traceN.Clear();
   constexpr uint8_t long_array[20] = {0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
                                       10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
diff --git a/centipede/fuzztest_mutator.cc b/centipede/fuzztest_mutator.cc
index 2fcf8d2..57261cb 100644
--- a/centipede/fuzztest_mutator.cc
+++ b/centipede/fuzztest_mutator.cc
@@ -43,6 +43,16 @@
     decltype(fuzztest::VectorOf(fuzztest::Arbitrary<uint8_t>()));
 
 template <typename T>
+bool SampleInsert(const T& cmp_table, size_t& counter) {
+  static thread_local absl::BitGen bitgen;
+  counter++;
+  if (counter <= cmp_table.kTableSize) {
+    return true;
+  }
+  return absl::Uniform<size_t>(bitgen, 0, counter) < cmp_table.kTableSize;
+}
+
+template <typename T>
 void InsertCmpEntryIntoIntegerDictionary(const uint8_t* a, const uint8_t* b,
                                          TablesOfRecentCompares& cmp_tables) {
   T a_int;
@@ -59,25 +69,36 @@
   // Size limits on the cmp entries to be populated.
   static constexpr uint8_t kMaxCmpEntrySize = 15;
   static constexpr uint8_t kMinCmpEntrySize = 2;
+  size_t uint16_sample_counter = 0;
+  size_t uint32_sample_counter = 0;
+  size_t uint64_sample_counter = 0;
+  size_t mem_sample_counter = 0;
 
-  metadata.ForEachCmpEntry([&cmp_tables](fuzztest::internal::ByteSpan a,
-                                         fuzztest::internal::ByteSpan b) {
+  metadata.ForEachCmpEntry([&](fuzztest::internal::ByteSpan a,
+                               fuzztest::internal::ByteSpan b) {
     FUZZTEST_CHECK(a.size() == b.size())
         << "cmp operands must have the same size";
     const size_t size = a.size();
     if (size < kMinCmpEntrySize) return;
     if (size > kMaxCmpEntrySize) return;
-    if (size == 2) {
+    if (size == 2 && SampleInsert(cmp_tables.GetMutable<sizeof(uint16_t)>(),
+                                  uint16_sample_counter)) {
       InsertCmpEntryIntoIntegerDictionary<uint16_t>(a.data(), b.data(),
                                                     cmp_tables);
-    } else if (size == 4) {
+    } else if (size == 4 &&
+               SampleInsert(cmp_tables.GetMutable<sizeof(uint32_t)>(),
+                            uint32_sample_counter)) {
       InsertCmpEntryIntoIntegerDictionary<uint32_t>(a.data(), b.data(),
                                                     cmp_tables);
-    } else if (size == 8) {
+    } else if (size == 8 &&
+               SampleInsert(cmp_tables.GetMutable<sizeof(uint64_t)>(),
+                            uint64_sample_counter)) {
       InsertCmpEntryIntoIntegerDictionary<uint64_t>(a.data(), b.data(),
                                                     cmp_tables);
     }
-    cmp_tables.GetMutable<0>().Insert(a.data(), b.data(), size);
+    if (SampleInsert(cmp_tables.GetMutable<0>(), mem_sample_counter)) {
+      cmp_tables.GetMutable<0>().Insert(a.data(), b.data(), size);
+    }
   });
 }
 
diff --git a/centipede/runner_cmp_trace.h b/centipede/runner_cmp_trace.h
index 6687875..7267950 100644
--- a/centipede/runner_cmp_trace.h
+++ b/centipede/runner_cmp_trace.h
@@ -18,10 +18,14 @@
 // Capturing arguments of CMP instructions, memcmp, and similar.
 // WARNING: this code needs to have minimal dependencies.
 
+#include <sys/time.h>
+
 #include <cstddef>
 #include <cstdint>
 #include <cstring>
 
+#include "absl/base/optimization.h"
+
 namespace fuzztest::internal {
 
 // Captures up to `kNumItems` different CMP argument pairs.
@@ -33,7 +37,8 @@
 //
 // Every new captured pair may overwrite a pair stored previously.
 //
-// Outside of tests, objects of this class will be created in TLS, thus no CTOR.
+// Outside of tests, objects of this class will be zero-initialized in TLS,
+// thus no CTOR. In tests the objects should be default-initialized.
 template <uint8_t kFixedSize, size_t kNumItems>
 class CmpTrace {
  public:
@@ -45,16 +50,34 @@
   // No CTOR - objects will be created in TLS.
 
   // Clears `this`.
-  void Clear() { memset(this, 0, sizeof(*this)); }
+  void Clear() { to_clear = true; }
 
   // Captures one CMP argument pair, as two byte arrays, `size` bytes each.
   void Capture(uint8_t size, const uint8_t *value0, const uint8_t *value1) {
+    if (ABSL_PREDICT_FALSE(to_clear)) {
+      for (size_t i = 0; i < kNumItems; ++i) {
+        if (sizes_[i] == 0) break;
+        sizes_[i] = 0;
+      }
+      capture_count_ = 0;
+      to_clear = false;
+    }
     if (size > kNumBytesPerValue) size = kNumBytesPerValue;
-    // We choose a pseudo-random slot each time.
-    // This way after capturing many pairs we end up with up to `kNumItems`
-    // pairs which are typically, but not always, the most recent.
-    rand_seed_ = rand_seed_ * 1103515245 + 12345;
-    const size_t index = rand_seed_ % kNumItems;
+    // Fill the initial `kNumItems` pairs sequentially, then randomly overwrite
+    // previous entries with diminishing probability.
+    size_t index = capture_count_++;
+    if (index >= kNumItems) {
+      if (rand_seed_ == 0) {
+        // Initialize the random seed (likely) once.
+        struct timeval tv = {};
+        constexpr size_t kUsecInSec = 1000000;
+        gettimeofday(&tv, nullptr);
+        rand_seed_ = tv.tv_sec * kUsecInSec + tv.tv_usec;
+      }
+      rand_seed_ = rand_seed_ * 1103515245 + 12345;
+      index = rand_seed_ % capture_count_;
+      if (index >= kNumItems) return;
+    }
     Item& item = items_[index];
     sizes_[index] = size;
     __builtin_memcpy(item.value0, value0, size);
@@ -74,12 +97,14 @@
   // Iterates non-zero CMP pairs.
   template <typename Callback>
   void ForEachNonZero(Callback callback) {
+    if (ABSL_PREDICT_FALSE(to_clear)) return;
     for (size_t i = 0; i < kNumItems; ++i) {
       const auto size = sizes_[i];
-      if (size == 0 || size > kNumBytesPerValue) continue;
-      sizes_[i] = 0;
+      if (size == 0) break;
+      if (size > kNumBytesPerValue) continue;
       callback(size, items_[i].value0, items_[i].value1);
     }
+    to_clear = true;
   }
 
  private:
@@ -89,17 +114,22 @@
     uint8_t value1[kNumBytesPerValue];
   };
 
-  // Value sizes of argument pairs. zero-size indicates that the corresponding
-  // entry is empty.
+  volatile bool to_clear;
+
+  // Value sizes of argument pairs. Zero-size indicates end of valid entries.
   //
   // Marked volatile because of the potential racing between the owning thread
-  // and the main thread, which is tolerated gracefully.
+  // and the main thread, which is tolerated gracefully. It is written by only
+  // the owning thread.
   volatile uint8_t sizes_[kNumItems];
+
+  size_t capture_count_;
   // Values of argument pairs.
   Item items_[kNumItems];
 
-  // Pseudo-random seed.
-  size_t rand_seed_;
+  // Pseudo-random seed from glibc
+  // (https://en.wikipedia.org/wiki/Linear_congruential_generator).
+  uint32_t rand_seed_;
 };
 
 }  // namespace fuzztest::internal
diff --git a/centipede/runner_cmp_trace_test.cc b/centipede/runner_cmp_trace_test.cc
index 492c18f..04d20ca 100644
--- a/centipede/runner_cmp_trace_test.cc
+++ b/centipede/runner_cmp_trace_test.cc
@@ -56,10 +56,10 @@
     observed_pairs.push_back(cmp_pair);
   };
 
-  CmpTrace<2, 10> trace2;
-  CmpTrace<4, 11> trace4;
-  CmpTrace<8, 12> trace8;
-  CmpTrace<0, 13> traceN;
+  CmpTrace<2, 10> trace2 = {};
+  CmpTrace<4, 11> trace4 = {};
+  CmpTrace<8, 12> trace8 = {};
+  CmpTrace<0, 13> traceN = {};
   trace2.Clear();
   trace4.Clear();
   trace8.Clear();
diff --git a/fuzztest/internal/table_of_recent_compares.h b/fuzztest/internal/table_of_recent_compares.h
index ed59b71..742bf55 100644
--- a/fuzztest/internal/table_of_recent_compares.h
+++ b/fuzztest/internal/table_of_recent_compares.h
@@ -1,4 +1,3 @@
-
 // Copyright 2022 Google LLC
 //
 // Licensed under the Apache License, Version 2.0 (the "License");