diff --git a/centipede/BUILD b/centipede/BUILD
index 4e1de94..b01c22c 100644
--- a/centipede/BUILD
+++ b/centipede/BUILD
@@ -369,7 +369,7 @@
     deps = [
         ":centipede_callbacks",
         ":environment",
-        ":mutation_input",
+        ":mutation_data",
         ":runner_result",
         ":stop",
         ":thread_pool",
@@ -442,6 +442,7 @@
         # used in centipede_runner.
         ":feature",
         ":execution_metadata",
+        ":mutation_data",
         ":shared_memory_blob_sequence",
         "@com_google_fuzztest//common:defs",
     ],
@@ -457,14 +458,15 @@
         # used in centipede_runner.
         ":shared_memory_blob_sequence",
         ":execution_metadata",
-        ":mutation_input",
+        ":mutation_data",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
     ],
 )
 
 cc_library(
-    name = "mutation_input",
-    hdrs = ["mutation_input.h"],
+    name = "mutation_data",
+    hdrs = ["mutation_data.h"],
     copts = DISABLE_SANCOV_COPTS,
     deps = [
         # This target must have a minimal set of dependencies since it is
@@ -483,8 +485,9 @@
     deps = [
         ":execution_metadata",
         ":knobs",
-        ":mutation_input",
+        ":mutation_data",
         "@abseil-cpp//absl/base:nullability",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
     ],
 )
@@ -627,7 +630,7 @@
         ":control_flow",
         ":environment",
         ":fuzztest_mutator",
-        ":mutation_input",
+        ":mutation_data",
         ":runner_request",
         ":runner_result",
         ":shared_memory_blob_sequence",
@@ -641,6 +644,7 @@
         "@abseil-cpp//absl/strings",
         "@abseil-cpp//absl/synchronization",
         "@abseil-cpp//absl/time",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:blob_file",
         "@com_google_fuzztest//common:defs",
         "@com_google_fuzztest//common:hash",
@@ -719,7 +723,7 @@
         ":environment",
         ":feature",
         ":feature_set",
-        ":mutation_input",
+        ":mutation_data",
         ":pc_info",
         ":runner_result",
         ":rusage_profiler",
@@ -737,6 +741,7 @@
         "@abseil-cpp//absl/strings:str_format",
         "@abseil-cpp//absl/synchronization",
         "@abseil-cpp//absl/time",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:blob_file",
         "@com_google_fuzztest//common:defs",
         "@com_google_fuzztest//common:hash",
@@ -855,11 +860,12 @@
     deps = [
         ":centipede_callbacks",
         ":environment",
-        ":mutation_input",
+        ":mutation_data",
         ":runner_result",
         ":stop",
         "@abseil-cpp//absl/status",
         "@abseil-cpp//absl/status:statusor",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
         "@com_google_fuzztest//common:logging",
     ],
@@ -873,7 +879,7 @@
         ":byte_array_mutator",
         ":execution_metadata",
         ":knobs",
-        ":mutation_input",
+        ":mutation_data",
         "@abseil-cpp//absl/random",
         "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
@@ -941,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
@@ -958,6 +965,7 @@
     hdrs = ["dispatcher.h"],
     deps = [
         ":execution_metadata",
+        ":mutation_data",
         ":runner_request",
         ":runner_result",
         ":shared_memory_blob_sequence",
@@ -1033,7 +1041,7 @@
     ":foreach_nonzero",
     ":int_utils",
     ":knobs",
-    ":mutation_input",
+    ":mutation_data",
     ":rolling_hash",
     ":runner_cmp_trace",
     ":runner_fork_server",
@@ -1098,8 +1106,9 @@
     linkstatic = True,  # Must be linked statically even when dynamic_mode=on.
     deps = [
         ":centipede_runner_no_main",
-        ":mutation_input",
+        ":mutation_data",
         "@abseil-cpp//absl/base:nullability",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
     ],
 )
@@ -1237,9 +1246,10 @@
         ":corpus",
         ":environment",
         ":feature",
-        ":mutation_input",
+        ":mutation_data",
         ":runner_result",
         ":util",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
         "@com_google_fuzztest//common:logging",
     ],
@@ -1279,6 +1289,7 @@
         ":centipede_callbacks",
         ":environment",
         ":runner_result",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
         "@googletest//:gtest_main",
     ],
@@ -1456,6 +1467,7 @@
         ":util",
         ":workdir",
         "@abseil-cpp//absl/base:nullability",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
         "@com_google_fuzztest//common:test_util",
         "@googletest//:gtest_main",
@@ -1509,6 +1521,7 @@
     deps = [
         ":execution_metadata",
         ":feature",
+        ":mutation_data",
         ":runner_result",
         ":shared_memory_blob_sequence",
         "@com_google_fuzztest//common:defs",
@@ -1518,10 +1531,10 @@
 )
 
 cc_test(
-    name = "mutation_input_test",
-    srcs = ["mutation_input_test.cc"],
+    name = "mutation_data_test",
+    srcs = ["mutation_data_test.cc"],
     deps = [
-        ":mutation_input",
+        ":mutation_data",
         "@com_google_fuzztest//common:defs",
         "@googletest//:gtest_main",
     ],
@@ -1534,7 +1547,7 @@
         ":byte_array_mutator",
         ":execution_metadata",
         ":knobs",
-        ":mutation_input",
+        ":mutation_data",
         ":runner_cmp_trace",
         "@abseil-cpp//absl/container:flat_hash_set",
         "@com_google_fuzztest//common:defs",
@@ -1567,7 +1580,7 @@
         ":execution_metadata",
         ":fuzztest_mutator",
         ":knobs",
-        ":mutation_input",
+        ":mutation_data",
         "@abseil-cpp//absl/container:flat_hash_set",
         "@abseil-cpp//absl/strings",
         "@com_google_fuzztest//common:defs",
@@ -1662,6 +1675,7 @@
     deps = [
         ":runner_fork_server",
         "@abseil-cpp//absl/base:nullability",
+        "@abseil-cpp//absl/time",
     ],
 )
 
@@ -1872,6 +1886,7 @@
         "@abseil-cpp//absl/container:flat_hash_map",
         "@abseil-cpp//absl/strings:str_format",
         "@abseil-cpp//absl/time",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
         "@com_google_fuzztest//common:hash",
         "@com_google_fuzztest//common:temp_dir",
@@ -1914,7 +1929,7 @@
         ":centipede_interface",
         ":environment",
         ":feature",
-        ":mutation_input",
+        ":mutation_data",
         ":runner_result",
         ":stop",
         ":util",
@@ -1922,6 +1937,7 @@
         "@abseil-cpp//absl/container:flat_hash_set",
         "@abseil-cpp//absl/strings",
         "@abseil-cpp//absl/time",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//common:defs",
         "@com_google_fuzztest//common:hash",
         "@com_google_fuzztest//common:logging",
diff --git a/centipede/byte_array_mutator.cc b/centipede/byte_array_mutator.cc
index 9a29a43..fc2597d 100644
--- a/centipede/byte_array_mutator.cc
+++ b/centipede/byte_array_mutator.cc
@@ -22,9 +22,10 @@
 #include <utility>
 #include <vector>
 
+#include "absl/types/span.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/knobs.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./common/defs.h"
 
 namespace fuzztest::internal {
@@ -321,27 +322,28 @@
 // TODO(kcc): add tests with different values of knobs.
 const KnobId knob_mutate_or_crossover = Knobs::NewId("mutate_or_crossover");
 
-std::vector<ByteArray> ByteArrayMutator::MutateMany(
-    const std::vector<MutationInputRef> &inputs, size_t num_mutants) {
+std::vector<Mutant> ByteArrayMutator::MutateMany(
+    absl::Span<const MutationInputRef> inputs, size_t num_mutants) {
   if (inputs.empty()) abort();
   // TODO(xinhaoyuan): Consider metadata in other inputs instead of always the
   // first one.
   SetMetadata(inputs[0].metadata != nullptr ? *inputs[0].metadata
                                             : ExecutionMetadata());
   size_t num_inputs = inputs.size();
-  std::vector<ByteArray> mutants;
+  std::vector<Mutant> mutants;
   mutants.reserve(num_mutants);
   for (size_t i = 0; i < num_mutants; ++i) {
-    auto mutant = inputs[rng_() % num_inputs].data;
-    if (mutant.size() <= max_len_ &&
+    const size_t origin = rng_() % num_inputs;
+    auto mutant = Mutant{inputs[origin].data, origin};
+    if (mutant.data.size() <= max_len_ &&
         knobs_.GenerateBool(knob_mutate_or_crossover, rng_())) {
       // Do crossover only if the mutant is not over the max_len_.
       // Perform crossover with some other input. It may be the same input.
       const auto &other_input = inputs[rng_() % num_inputs].data;
-      CrossOver(mutant, other_input);
+      CrossOver(mutant.data, other_input);
     } else {
       // Perform mutation.
-      Mutate(mutant);
+      Mutate(mutant.data);
     }
     mutants.push_back(std::move(mutant));
   }
diff --git a/centipede/byte_array_mutator.h b/centipede/byte_array_mutator.h
index 3c6978c..fae36f3 100644
--- a/centipede/byte_array_mutator.h
+++ b/centipede/byte_array_mutator.h
@@ -23,9 +23,10 @@
 #include <vector>
 
 #include "absl/base/nullability.h"
+#include "absl/types/span.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/knobs.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./common/defs.h"
 
 namespace fuzztest::internal {
@@ -33,7 +34,7 @@
 // A simple class representing an array of up to kMaxEntrySize bytes.
 class DictEntry {
  public:
-  static constexpr uint8_t kMaxEntrySize = 16;
+  static constexpr uint8_t kMaxEntrySize = 128;
 
   explicit DictEntry(ByteSpan bytes)
       : bytes_{},  // initialize bytes_ to all zeros
@@ -108,8 +109,8 @@
   }
 
   // Takes non-empty `inputs` and produces `num_mutants` mutants.
-  std::vector<ByteArray> MutateMany(const std::vector<MutationInputRef> &inputs,
-                                    size_t num_mutants);
+  std::vector<Mutant> MutateMany(absl::Span<const MutationInputRef> inputs,
+                                 size_t num_mutants);
 
   using CrossOverFn = void (ByteArrayMutator::*)(ByteArray &,
                                                  const ByteArray &);
diff --git a/centipede/byte_array_mutator_test.cc b/centipede/byte_array_mutator_test.cc
index ae35641..e28dff3 100644
--- a/centipede/byte_array_mutator_test.cc
+++ b/centipede/byte_array_mutator_test.cc
@@ -18,6 +18,7 @@
 #include <cstdint>
 #include <cstring>
 #include <limits>
+#include <numeric>
 #include <vector>
 
 #include "gmock/gmock.h"
@@ -25,7 +26,7 @@
 #include "absl/container/flat_hash_set.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/knobs.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_cmp_trace.h"
 #include "./common/defs.h"
 
@@ -93,8 +94,9 @@
 namespace {
 
 TEST(DictEntry, DictEntry) {
-  uint8_t bytes[17] = {0, 1,  2,  3,  4,  5,  6,  7, 8,
-                       9, 10, 11, 12, 13, 14, 15, 16};
+  uint8_t bytes[129];
+  std::iota(bytes, bytes + 129, 0);
+
   DictEntry a_0_10({bytes + 0, 10});
   DictEntry a_0_4({bytes + 0, 4});
   DictEntry a_1_8({bytes + 1, 8});
@@ -103,7 +105,7 @@
   EXPECT_LT(a_0_10, a_1_8);
   EXPECT_EQ(memcmp(a_0_10.begin(), bytes, a_0_10.end() - a_0_10.begin()), 0);
 
-  EXPECT_DEATH({ DictEntry a_0_10({bytes, 17}); }, "");
+  EXPECT_DEATH({ DictEntry a_0_10({bytes, 129}); }, "");
 }
 
 TEST(CmpDictionary, CmpDictionary) {
@@ -158,11 +160,11 @@
 }
 
 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};
-  traceN.Capture(20, long_array, long_array);  // will be trimmed to 16.
+  traceN.Capture(20, long_array, long_array);
 
   ExecutionMetadata metadata;
   bool append_failed = false;
@@ -928,12 +930,12 @@
       {0, 1, 2, 3, 4, 5, 6, 7},
       {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},
   };
-  const std::vector<ByteArray> mutants =
+  const std::vector<Mutant> mutants =
       mutator.MutateMany(GetMutationInputRefsFromDataInputs(aligned_inputs),
                          kNumMutantsToGenerate);
   EXPECT_EQ(mutants.size(), kNumMutantsToGenerate);
-  for (const ByteArray &mutant : mutants) {
-    EXPECT_EQ(mutant.size() % kSizeAlignment, 0);
+  for (const Mutant& mutant : mutants) {
+    EXPECT_EQ(mutant.data.size() % kSizeAlignment, 0);
   }
 }
 
@@ -958,13 +960,13 @@
       {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
       {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
   };
-  const std::vector<ByteArray> mutants =
+  const std::vector<Mutant> mutants =
       mutator.MutateMany(GetMutationInputRefsFromDataInputs(unaligned_inputs),
                          kNumMutantsToGenerate);
   EXPECT_EQ(mutants.size(), kNumMutantsToGenerate);
-  for (const ByteArray &mutant : mutants) {
-    if (mutant.size() % kSizeAlignment != 0) {
-      EXPECT_LE(mutant.size(), 11);
+  for (const Mutant& mutant : mutants) {
+    if (mutant.data.size() % kSizeAlignment != 0) {
+      EXPECT_LE(mutant.data.size(), 11);
     }
   }
 }
@@ -982,12 +984,12 @@
       {0, 1, 2},
       {0, 1, 2, 3},
   };
-  const std::vector<ByteArray> mutants = mutator.MutateMany(
+  const std::vector<Mutant> mutants = mutator.MutateMany(
       GetMutationInputRefsFromDataInputs(inputs), kNumMutantsToGenerate);
   EXPECT_EQ(mutants.size(), kNumMutantsToGenerate);
 
-  for (const ByteArray &mutant : mutants) {
-    EXPECT_LE(mutant.size(), kMaxLen);
+  for (const Mutant& mutant : mutants) {
+    EXPECT_LE(mutant.data.size(), kMaxLen);
   }
 }
 
@@ -1001,16 +1003,16 @@
   const std::vector<ByteArray> large_input = {
       {0, 1, 2, 3, 4, 5, 6, 7}, {0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3},
   };
-  const std::vector<ByteArray> mutants = mutator.MutateMany(
+  const std::vector<Mutant> mutants = mutator.MutateMany(
       GetMutationInputRefsFromDataInputs(large_input), kNumMutantsToGenerate);
   EXPECT_EQ(mutants.size(), kNumMutantsToGenerate);
 
-  for (const ByteArray &mutant : mutants) {
-    if (mutant.size() > kMaxLen) {
+  for (const Mutant& mutant : mutants) {
+    if (mutant.data.size() > kMaxLen) {
       // The only mutant larger than max length should be the same large input
       // that mutation originally started with. All other mutants should be
       // within the maximum length specified.
-      EXPECT_EQ(mutant, large_input[0]);
+      EXPECT_EQ(mutant.data, large_input[0]);
     }
   }
 }
diff --git a/centipede/centipede.cc b/centipede/centipede.cc
index b18f995..f204cce 100644
--- a/centipede/centipede.cc
+++ b/centipede/centipede.cc
@@ -72,6 +72,7 @@
 #include "absl/synchronization/mutex.h"
 #include "absl/time/clock.h"
 #include "absl/time/time.h"
+#include "absl/types/span.h"
 #include "./centipede/binary_info.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/command.h"
@@ -82,7 +83,7 @@
 #include "./centipede/environment.h"
 #include "./centipede/feature.h"
 #include "./centipede/feature_set.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/rusage_profiler.h"
 #include "./centipede/rusage_stats.h"
@@ -99,6 +100,19 @@
 
 namespace fuzztest::internal {
 
+namespace {
+
+std::vector<MutantRef> InputsToMutantRefs(const std::vector<ByteSpan>& inputs) {
+  std::vector<MutantRef> mutants;
+  mutants.reserve(inputs.size());
+  for (const auto input : inputs) {
+    mutants.push_back(MutantRef{input, Mutant::kOriginNone});
+  }
+  return mutants;
+}
+
+}  // namespace
+
 Centipede::Centipede(const Environment& env, CentipedeCallbacks& user_callbacks,
                      const BinaryInfo& binary_info,
                      CoverageLogger& coverage_logger, std::atomic<Stats>& stats)
@@ -362,7 +376,7 @@
   }
 }
 
-bool Centipede::InputPassesFilter(const ByteArray &input) {
+bool Centipede::InputPassesFilter(ByteSpan input) {
   if (env_.input_filter.empty()) return true;
   WriteToLocalFile(input_filter_path_, input);
   bool result = input_filter_cmd_.Execute() == EXIT_SUCCESS;
@@ -371,8 +385,8 @@
 }
 
 bool Centipede::ExecuteAndReportCrash(std::string_view binary,
-                                      const std::vector<ByteArray> &input_vec,
-                                      BatchResult &batch_result) {
+                                      absl::Span<const ByteSpan> input_vec,
+                                      BatchResult& batch_result) {
   bool success = user_callbacks_.Execute(binary, input_vec, batch_result);
   if (success) return true;
   if (ShouldStop()) {
@@ -427,20 +441,24 @@
 }
 
 bool Centipede::RunBatch(
-    const std::vector<ByteArray> &input_vec,
-    BlobFileWriter *absl_nullable corpus_file,
-    BlobFileWriter *absl_nullable features_file,
-    BlobFileWriter *absl_nullable unconditional_features_file) {
+    absl::Span<const MutantRef> mutants,
+    BlobFileWriter* absl_nullable corpus_file,
+    BlobFileWriter* absl_nullable features_file,
+    BlobFileWriter* absl_nullable unconditional_features_file) {
   BatchResult batch_result;
-  bool success = ExecuteAndReportCrash(env_.binary, input_vec, batch_result);
-  FUZZTEST_CHECK_EQ(input_vec.size(), batch_result.results().size());
+  std::vector<ByteSpan> inputs;
+  inputs.reserve(mutants.size());
+  for (auto mutant : mutants) {
+    inputs.push_back(mutant.data);
+  }
+  bool success = ExecuteAndReportCrash(env_.binary, inputs, batch_result);
+  FUZZTEST_CHECK_EQ(mutants.size(), batch_result.results().size());
 
   for (const auto &extra_binary : env_.extra_binaries) {
     if (ShouldStop()) break;
     BatchResult extra_batch_result;
-    success =
-        ExecuteAndReportCrash(extra_binary, input_vec, extra_batch_result) &&
-        success;
+    success = ExecuteAndReportCrash(extra_binary, inputs, extra_batch_result) &&
+              success;
   }
   if (EarlyStopRequested()) return false;
   if (!success && env_.exit_on_crash) {
@@ -448,9 +466,8 @@
     RequestEarlyStop(EXIT_FAILURE);
     return false;
   }
-  FUZZTEST_CHECK_EQ(batch_result.results().size(), input_vec.size());
   bool batch_gained_new_coverage = false;
-  for (size_t i = 0; i < input_vec.size(); i++) {
+  for (size_t i = 0; i < mutants.size(); i++) {
     if (ShouldStop()) break;
     FeatureVec &fv = batch_result.results()[i].mutable_features();
     bool function_filter_passed = function_filter_.filter(fv);
@@ -459,28 +476,28 @@
       input_gained_new_coverage = true;
     if (unconditional_features_file != nullptr) {
       FUZZTEST_CHECK_OK(unconditional_features_file->Write(
-          PackFeaturesAndHash(input_vec[i], fv)));
+          PackFeaturesAndHash(inputs[i], fv)));
     }
     if (input_gained_new_coverage) {
       // TODO(kcc): [impl] add stats for filtered-out inputs.
-      if (!InputPassesFilter(input_vec[i])) continue;
+      if (!InputPassesFilter(inputs[i])) continue;
       fs_.MergeFeatures(fv);
       LogFeaturesAsSymbols(fv);
       batch_gained_new_coverage = true;
       FUZZTEST_CHECK_GT(fv.size(), 0UL);
       if (function_filter_passed) {
-        corpus_.Add(input_vec[i], fv, batch_result.results()[i].metadata(),
+        corpus_.Add(inputs[i], fv, batch_result.results()[i].metadata(),
                     batch_result.results()[i].stats(), fs_, coverage_frontier_);
       }
       if (corpus_file != nullptr) {
-        FUZZTEST_CHECK_OK(corpus_file->Write(input_vec[i]));
+        FUZZTEST_CHECK_OK(corpus_file->Write(inputs[i]));
       }
       if (!env_.corpus_dir.empty() && !env_.corpus_dir[0].empty()) {
-        WriteToLocalHashedFileInDir(env_.corpus_dir[0], input_vec[i]);
+        WriteToLocalHashedFileInDir(env_.corpus_dir[0], inputs[i]);
       }
       if (features_file != nullptr) {
         FUZZTEST_CHECK_OK(
-            features_file->Write(PackFeaturesAndHash(input_vec[i], fv)));
+            features_file->Write(PackFeaturesAndHash(inputs[i], fv)));
       }
     }
   }
@@ -582,11 +599,12 @@
   while (!to_rerun.empty()) {
     if (ShouldStop()) break;
     size_t batch_size = std::min(to_rerun.size(), env_.batch_size);
-    std::vector<ByteArray> batch(to_rerun.end() - batch_size, to_rerun.end());
-    to_rerun.resize(to_rerun.size() - batch_size);
-    if (RunBatch(batch, nullptr, nullptr, features_file.get())) {
+    if (RunBatch(
+            InputsToMutantRefs({to_rerun.end() - batch_size, to_rerun.end()}),
+            nullptr, nullptr, features_file.get())) {
       UpdateAndMaybeLogStats("rerun-old", 1);
     }
+    to_rerun.resize(to_rerun.size() - batch_size);
   }
 }
 
@@ -778,7 +796,8 @@
     seed_inputs.push_back({0});
   }
 
-  RunBatch(seed_inputs, corpus_file, features_file,
+  RunBatch(InputsToMutantRefs({seed_inputs.begin(), seed_inputs.end()}),
+           corpus_file, features_file,
            /*unconditional_features_file=*/nullptr);
   FUZZTEST_LOG(INFO) << "Number of input seeds available: "
                      << num_seeds_available
@@ -859,23 +878,38 @@
     auto remaining_runs = env_.num_runs - new_runs;
     auto batch_size = std::min(env_.batch_size, remaining_runs);
     std::vector<MutationInputRef> mutation_inputs;
+    std::vector<size_t> mutate_input_to_corpus_idx;
     mutation_inputs.reserve(env_.mutate_batch_size);
+    mutate_input_to_corpus_idx.reserve(env_.mutate_batch_size);
     for (size_t i = 0; i < env_.mutate_batch_size; i++) {
-      const auto& corpus_record = env_.use_corpus_weights
-                                      ? corpus_.WeightedRandom(rng_)
-                                      : corpus_.UniformRandom(rng_);
+      const size_t origin = env_.use_corpus_weights
+                                ? corpus_.WeightedRandom(rng_)
+                                : corpus_.UniformRandom(rng_);
+      mutate_input_to_corpus_idx.push_back(origin);
+      const auto& corpus_record = corpus_.Records()[origin];
       mutation_inputs.push_back(
           MutationInputRef{corpus_record.data, &corpus_record.metadata});
     }
 
-    const std::vector<ByteArray> mutants =
+    std::vector<Mutant> mutants =
         user_callbacks_.Mutate(mutation_inputs, batch_size);
     if (ShouldStop()) break;
-
-    bool gained_new_coverage =
-        RunBatch(mutants, corpus_file.get(), features_file.get(), nullptr);
     new_runs += mutants.size();
 
+    std::vector<MutantRef> mutant_refs;
+    mutant_refs.reserve(mutants.size());
+    for (auto& mutant : mutants) {
+      if (mutant.origin == Mutant::kOriginNone) {
+        mutant_refs.push_back(MutantRef{mutant.data, Mutant::kOriginNone});
+      } else {
+        FUZZTEST_CHECK_LT(mutant.origin, mutate_input_to_corpus_idx.size());
+        mutant_refs.push_back(
+            MutantRef{mutant.data, mutate_input_to_corpus_idx[mutant.origin]});
+      }
+    }
+    bool gained_new_coverage =
+        RunBatch(mutant_refs, corpus_file.get(), features_file.get(), nullptr);
+
     if (gained_new_coverage) {
       UpdateAndMaybeLogStats("new-feature", 1);
     } else if (((batch_index - 1) & batch_index) == 0) {
@@ -917,8 +951,8 @@
 }
 
 void Centipede::ReportCrash(std::string_view binary,
-                            const std::vector<ByteArray> &input_vec,
-                            const BatchResult &batch_result) {
+                            absl::Span<const ByteSpan> input_vec,
+                            const BatchResult& batch_result) {
   FUZZTEST_CHECK_EQ(input_vec.size(), batch_result.results().size());
 
   const size_t suspect_input_idx = std::clamp<size_t>(
@@ -1014,7 +1048,7 @@
       << "Executing inputs one-by-one, trying to find the reproducer";
   for (auto input_idx : input_idxs_to_try) {
     if (ShouldStop()) break;
-    const auto &one_input = input_vec[input_idx];
+    const auto one_input = input_vec[input_idx];
     BatchResult one_input_batch_result;
     if (!user_callbacks_.Execute(binary, {one_input}, one_input_batch_result) &&
         one_input_batch_result.IsInputFailure() &&
diff --git a/centipede/centipede.h b/centipede/centipede.h
index 625938f..18fa83d 100644
--- a/centipede/centipede.h
+++ b/centipede/centipede.h
@@ -24,6 +24,7 @@
 #include "absl/base/nullability.h"
 #include "absl/status/status.h"
 #include "absl/time/time.h"
+#include "absl/types/span.h"
 #include "./centipede/binary_info.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/command.h"
@@ -75,7 +76,7 @@
                                      std::string_view dir);
 
  private:
-  // Executes inputs from `input_vec`.
+  // Executes inputs from `mutants` and update the corpus.
   // For every input, its pruned features are written to
   // `unconditional_features_file`, (if that's non-null).
   // For every input that caused new features to be observed:
@@ -83,11 +84,11 @@
   //   * the input is written to `corpus_file` (if that's non-null).
   //   * its features are written to `features_file` (if that's non-null).
   // Returns true if new features were observed.
-  // Post-condition: `batch_result.results.size()` == `input_vec.size()`.
-  bool RunBatch(const std::vector<ByteArray> &input_vec,
-                BlobFileWriter *absl_nullable corpus_file,
-                BlobFileWriter *absl_nullable features_file,
-                BlobFileWriter *absl_nullable unconditional_features_file);
+  // Post-condition: `batch_result.results.size()` == `mutants.size()`.
+  bool RunBatch(absl::Span<const MutantRef> mutants,
+                BlobFileWriter* absl_nullable corpus_file,
+                BlobFileWriter* absl_nullable features_file,
+                BlobFileWriter* absl_nullable unconditional_features_file);
   // Loads seed inputs from the user callbacks, execute them, and store them
   // with the corresponding features into `corpus_file` and `features_file`.
   void LoadSeedInputs(BlobFileWriter *absl_nonnull corpus_file,
@@ -140,13 +141,13 @@
                                         size_t batch_index);
 
   // Returns true if `input` passes env_.input_filter.
-  bool InputPassesFilter(const ByteArray &input);
+  bool InputPassesFilter(ByteSpan input);
   // Executes `binary` with `input_vec` and `batch_result` as input/output.
   // If the binary crashes, calls ReportCrash().
   // Returns true iff there were no crashes.
   bool ExecuteAndReportCrash(std::string_view binary,
-                             const std::vector<ByteArray> &input_vec,
-                             BatchResult &batch_result);
+                             absl::Span<const ByteSpan> input_vec,
+                             BatchResult& batch_result);
   // Reports a crash and saves the reproducer to workdir/crashes, if possible.
   // `binary` is the binary causing the crash.
   // Prints the first `env_.max_num_crash_reports` logs.
@@ -156,8 +157,8 @@
   // as a hint when choosing which input to try first.
   // Stops early if `EarlyExitRequested()`.
   void ReportCrash(std::string_view binary,
-                   const std::vector<ByteArray> &input_vec,
-                   const BatchResult &batch_result);
+                   absl::Span<const ByteSpan> input_vec,
+                   const BatchResult& batch_result);
   // Merges shard `shard_index_to_merge` of the corpus in `merge_from_dir`
   // into the current corpus.
   // Writes added inputs to the current shard.
diff --git a/centipede/centipede_callbacks.cc b/centipede/centipede_callbacks.cc
index 14e11e8..c37fa85 100644
--- a/centipede/centipede_callbacks.cc
+++ b/centipede/centipede_callbacks.cc
@@ -45,10 +45,11 @@
 #include "absl/synchronization/mutex.h"
 #include "absl/time/clock.h"
 #include "absl/time/time.h"
+#include "absl/types/span.h"
 #include "./centipede/binary_info.h"
 #include "./centipede/command.h"
 #include "./centipede/control_flow.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_request.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/stop.h"
@@ -534,7 +535,7 @@
 }
 
 int CentipedeCallbacks::ExecuteCentipedeSancovBinaryWithShmem(
-    std::string_view binary, const std::vector<ByteArray>& inputs,
+    std::string_view binary, absl::Span<const ByteSpan> inputs,
     BatchResult& batch_result) {
   auto start_time = absl::Now();
   batch_result.ClearAndResize(inputs.size());
@@ -734,7 +735,7 @@
 
 // See also: MutateInputsFromShmem().
 MutationResult CentipedeCallbacks::MutateViaExternalBinary(
-    std::string_view binary, const std::vector<MutationInputRef>& inputs,
+    std::string_view binary, absl::Span<const MutationInputRef> inputs,
     size_t num_mutants) {
   FUZZTEST_CHECK(!env_.has_input_wildcards)
       << "Standalone binary does not support custom mutator";
diff --git a/centipede/centipede_callbacks.h b/centipede/centipede_callbacks.h
index 0a946f1..a4fb2bb 100644
--- a/centipede/centipede_callbacks.h
+++ b/centipede/centipede_callbacks.h
@@ -25,12 +25,13 @@
 
 #include "absl/base/nullability.h"
 #include "absl/status/statusor.h"
+#include "absl/types/span.h"
 #include "./centipede/binary_info.h"
 #include "./centipede/byte_array_mutator.h"
 #include "./centipede/command.h"
 #include "./centipede/environment.h"
 #include "./centipede/fuzztest_mutator.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/shared_memory_blob_sequence.h"
 #include "./centipede/util.h"
@@ -68,12 +69,12 @@
   // Post-condition:
   // `batch_result` has results for every `input`, even on failure.
   virtual bool Execute(std::string_view binary,
-                       const std::vector<ByteArray> &inputs,
-                       BatchResult &batch_result) = 0;
+                       absl::Span<const ByteSpan> inputs,
+                       BatchResult& batch_result) = 0;
 
   // Takes non-empty `inputs` and returns at most `num_mutants` mutated inputs.
-  virtual std::vector<ByteArray> Mutate(
-      const std::vector<MutationInputRef> &inputs, size_t num_mutants) {
+  virtual std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                                     size_t num_mutants) {
     return env_.use_legacy_default_mutator
                ? byte_array_mutator_.MutateMany(inputs, num_mutants)
                : fuzztest_mutator_.MutateMany(inputs, num_mutants);
@@ -105,9 +106,9 @@
 
   // Same as ExecuteCentipedeSancovBinary, but uses shared memory.
   // Much faster for fast targets since it uses fewer system calls.
-  int ExecuteCentipedeSancovBinaryWithShmem(
-      std::string_view binary, const std::vector<ByteArray> &inputs,
-      BatchResult &batch_result);
+  int ExecuteCentipedeSancovBinaryWithShmem(std::string_view binary,
+                                            absl::Span<const ByteSpan> inputs,
+                                            BatchResult& batch_result);
 
   // Constructs a string CENTIPEDE_RUNNER_FLAGS=":flag1:flag2:...",
   // where the flags are determined by `env` and also include `extra_flags`.
@@ -151,7 +152,7 @@
   // whether the binary has a custom mutator, and if it does, `mutants` contains
   // at most `num_mutants` non-empty mutants.
   MutationResult MutateViaExternalBinary(
-      std::string_view binary, const std::vector<MutationInputRef> &inputs,
+      std::string_view binary, absl::Span<const MutationInputRef> inputs,
       size_t num_mutants);
 
   // Loads the dictionary from `dictionary_path`,
diff --git a/centipede/centipede_callbacks_test.cc b/centipede/centipede_callbacks_test.cc
index 60fb8fc..ad8c68a 100644
--- a/centipede/centipede_callbacks_test.cc
+++ b/centipede/centipede_callbacks_test.cc
@@ -18,6 +18,7 @@
 #include <vector>
 
 #include "gtest/gtest.h"
+#include "absl/types/span.h"
 #include "./centipede/environment.h"
 #include "./centipede/runner_result.h"
 #include "./common/defs.h"
@@ -28,7 +29,7 @@
 class FakeCallbacks : public CentipedeCallbacks {
  public:
   explicit FakeCallbacks(const Environment& env) : CentipedeCallbacks(env) {}
-  bool Execute(std::string_view binary, const std::vector<ByteArray>& inputs,
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
                BatchResult& batch_result) override {
     return true;
   }
diff --git a/centipede/centipede_default_callbacks.cc b/centipede/centipede_default_callbacks.cc
index 73b8b8e..3f07174 100644
--- a/centipede/centipede_default_callbacks.cc
+++ b/centipede/centipede_default_callbacks.cc
@@ -23,9 +23,10 @@
 
 #include "absl/status/status.h"
 #include "absl/status/statusor.h"
+#include "absl/types/span.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/environment.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/stop.h"
 #include "./common/defs.h"
@@ -46,8 +47,8 @@
 }
 
 bool CentipedeDefaultCallbacks::Execute(std::string_view binary,
-                                        const std::vector<ByteArray> &inputs,
-                                        BatchResult &batch_result) {
+                                        absl::Span<const ByteSpan> inputs,
+                                        BatchResult& batch_result) {
   return ExecuteCentipedeSancovBinaryWithShmem(binary, inputs, batch_result) ==
          0;
 }
@@ -72,8 +73,8 @@
       "Failed to get serialized configuration from the target binary.");
 }
 
-std::vector<ByteArray> CentipedeDefaultCallbacks::Mutate(
-    const std::vector<MutationInputRef> &inputs, size_t num_mutants) {
+std::vector<Mutant> CentipedeDefaultCallbacks::Mutate(
+    absl::Span<const MutationInputRef> inputs, size_t num_mutants) {
   if (num_mutants == 0) return {};
   // In persistent mode, mutation could fail due to previous asynchronous
   // failure, thus give it one more chance to mutate in a clean state.
diff --git a/centipede/centipede_default_callbacks.h b/centipede/centipede_default_callbacks.h
index 0b78562..02fff74 100644
--- a/centipede/centipede_default_callbacks.h
+++ b/centipede/centipede_default_callbacks.h
@@ -26,9 +26,10 @@
 #include <vector>
 
 #include "absl/status/statusor.h"
+#include "absl/types/span.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/environment.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_result.h"
 #include "./common/defs.h"
 
@@ -40,10 +41,10 @@
   explicit CentipedeDefaultCallbacks(const Environment &env);
   size_t GetSeeds(size_t num_seeds, std::vector<ByteArray> &seeds) override;
   absl::StatusOr<std::string> GetSerializedTargetConfig() override;
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override;
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override;
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override;
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override;
 
  private:
   std::optional<bool> custom_mutator_is_usable_ = std::nullopt;
diff --git a/centipede/centipede_interface.cc b/centipede/centipede_interface.cc
index cd5e00d..9031169 100644
--- a/centipede/centipede_interface.cc
+++ b/centipede/centipede_interface.cc
@@ -111,12 +111,9 @@
     }
     ByteSpan blob;
     while (blob_reader->Read(blob) == absl::OkStatus()) {
-      ByteArray bytes;
-      bytes.insert(bytes.begin(), blob.data(), blob.end());
-      // TODO(kcc): [impl] add a variant of WriteToLocalFile that accepts Span.
-      WriteToLocalFile(tmpfile, bytes);
+      WriteToLocalFile(tmpfile, blob);
       std::string command_line = absl::StrReplaceAll(
-          env.for_each_blob, {{"%P", tmpfile}, {"%H", Hash(bytes)}});
+          env.for_each_blob, {{"%P", tmpfile}, {"%H", Hash(blob)}});
       Command cmd(command_line);
       // TODO(kcc): [as-needed] this creates one process per blob.
       // If this flag gets active use, we may want to define special cases,
diff --git a/centipede/centipede_test.cc b/centipede/centipede_test.cc
index 16e928f..d5497f3 100644
--- a/centipede/centipede_test.cc
+++ b/centipede/centipede_test.cc
@@ -33,12 +33,13 @@
 #include "absl/strings/str_cat.h"
 #include "absl/time/clock.h"
 #include "absl/time/time.h"
+#include "absl/types/span.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/centipede_default_callbacks.h"
 #include "./centipede/centipede_interface.h"
 #include "./centipede/environment.h"
 #include "./centipede/feature.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/stop.h"
 #include "./centipede/util.h"
@@ -61,6 +62,13 @@
 using ::testing::Not;
 using ::testing::SizeIs;
 
+inline std::vector<ByteSpan> AsByteSpans(const std::vector<ByteArray>& inputs) {
+  std::vector<ByteSpan> results;
+  results.reserve(inputs.size());
+  for (const auto& input : inputs) results.push_back(input);
+  return results;
+}
+
 // A mock for CentipedeCallbacks.
 class CentipedeMock : public CentipedeCallbacks {
  public:
@@ -68,8 +76,8 @@
   // Doesn't execute anything
   // Sets `batch_result.results()` based on the values of `inputs`:
   // Collects various stats about the inputs, to be checked in tests.
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     batch_result.results().clear();
     // For every input, we create a 256-element array `counters`, where
     // i-th element is the number of bytes with the value 'i' in the input.
@@ -106,19 +114,20 @@
   // (the value {0} is produced by the default GetSeeds()).
   // Next 65536 mutations are 2-byte sequences {0,0} ... {255, 255}.
   // Then repeat 2-byte sequences.
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    std::vector<ByteArray> mutants;
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    std::vector<Mutant> mutants;
     mutants.reserve(num_mutants);
     for (size_t i = 0; i < num_mutants; ++i) {
       num_mutations_++;
       if (num_mutations_ < 256) {
-        mutants.push_back({static_cast<uint8_t>(num_mutations_)});
+        mutants.push_back({/*data=*/{static_cast<uint8_t>(num_mutations_)},
+                           Mutant::kOriginNone});
         continue;
       }
       uint8_t byte0 = (num_mutations_ - 256) / 256;
       uint8_t byte1 = (num_mutations_ - 256) % 256;
-      mutants.push_back({byte0, byte1});
+      mutants.push_back({/*data=*/{byte0, byte1}, Mutant::kOriginNone});
     }
     return mutants;
   }
@@ -343,15 +352,15 @@
  public:
   explicit MutateCallbacks(const Environment &env) : CentipedeCallbacks(env) {}
   // Will not be called.
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     FUZZTEST_LOG(FATAL);
     return false;
   }
 
   // Will not be called.
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
     FUZZTEST_LOG(FATAL);
   }
 
@@ -436,8 +445,9 @@
           GetMutationInputRefsFromDataInputs(inputs), 10000);
       EXPECT_EQ(result.exit_code(), EXIT_SUCCESS);
       EXPECT_TRUE(result.has_custom_mutator());
-      EXPECT_THAT(result.mutants(), AllOf(IsSupersetOf(all_expected_mutants),
-                                          Each(Not(IsEmpty()))));
+      EXPECT_THAT(
+          GetDataFromMutants(result.mutants()),
+          AllOf(IsSupersetOf(all_expected_mutants), Each(Not(IsEmpty()))));
     }
   }
 
@@ -451,9 +461,10 @@
         10000);
     EXPECT_EQ(result.exit_code(), EXIT_SUCCESS);
     EXPECT_TRUE(result.has_custom_mutator());
-    EXPECT_THAT(result.mutants(), AllOf(IsSupersetOf(all_expected_mutants),
-                                        Each(Not(IsEmpty()))));
-    EXPECT_THAT(result.mutants(),
+    const auto mutant_data = GetDataFromMutants(result.mutants());
+    EXPECT_THAT(mutant_data, AllOf(IsSupersetOf(all_expected_mutants),
+                                   Each(Not(IsEmpty()))));
+    EXPECT_THAT(mutant_data,
                 AllOf(IsSupersetOf(all_expected_mutants), Each(Not(IsEmpty())),
                       // The byte_array_mutator may insert up to 20 bytes to an
                       // input, which may push the size over the max_len.
@@ -471,9 +482,10 @@
             binary_with_custom_mutator,
             GetMutationInputRefsFromDataInputs(inputs), 10000);
     // Must contain normal mutants, but not the ones from crossover.
-    EXPECT_THAT(result.mutants(), IsSupersetOf(some_of_expected_mutants));
+    const auto mutant_data = GetDataFromMutants(result.mutants());
+    EXPECT_THAT(mutant_data, IsSupersetOf(some_of_expected_mutants));
     for (const auto &crossover_mutant : expected_crossover_mutants) {
-      EXPECT_THAT(result.mutants(), Not(Contains(crossover_mutant)));
+      EXPECT_THAT(mutant_data, Not(Contains(crossover_mutant)));
     }
   }
 }
@@ -486,8 +498,8 @@
   // Doesn't execute anything.
   // All inputs are 1-byte long.
   // For an input {X}, the feature output is {X}.
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     batch_result.results().resize(inputs.size());
     for (size_t i = 0, n = inputs.size(); i < n; ++i) {
       FUZZTEST_CHECK_EQ(inputs[i].size(), 1);
@@ -497,12 +509,13 @@
   }
 
   // Every consecutive mutation is {number_of_mutations_} (starting from 1).
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    std::vector<ByteArray> mutants{num_mutants};
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    std::vector<Mutant> mutants(num_mutants);
     for (auto &mutant : mutants) {
-      mutant.resize(1);
-      mutant[0] = ++number_of_mutations_;
+      mutant.data.resize(1);
+      mutant.data[0] = ++number_of_mutations_;
+      mutant.origin = Mutant::kOriginNone;
     }
     return mutants;
   }
@@ -575,24 +588,25 @@
   }
 
   // Executes the target in the normal way.
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     return ExecuteCentipedeSancovBinaryWithShmem(env_.binary, inputs,
                                                  batch_result) == EXIT_SUCCESS;
   }
 
   // Sets the inputs to one of 3 pre-defined values.
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
     for (auto &input : inputs) {
       if (!seed_inputs_.contains(input.data)) {
         observed_inputs_.insert(input.data);
       }
     }
-    std::vector<ByteArray> mutants;
+    std::vector<Mutant> mutants;
     mutants.reserve(num_mutants);
     for (size_t i = 0; i < num_mutants; ++i) {
-      mutants.push_back(GetMutant(++number_of_mutations_));
+      mutants.push_back(
+          {/*data=*/GetMutant(++number_of_mutations_), Mutant::kOriginNone});
     }
     return mutants;
   }
@@ -684,8 +698,8 @@
 
   // Doesn't execute anything.
   // On certain combinations of {binary,input} returns false.
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     bool res = true;
     for (const auto &input : inputs) {
       if (input.size() != 1) continue;
@@ -703,12 +717,13 @@
   }
 
   // Sets the mutants to different 1-byte values.
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    std::vector<ByteArray> mutants{num_mutants};
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    std::vector<Mutant> mutants(num_mutants);
     for (auto &mutant : mutants) {
-      mutant.resize(1);
-      mutant[0] = ++number_of_mutations_;
+      mutant.data.resize(1);
+      mutant.data[0] = ++number_of_mutations_;
+      mutant.origin = Mutant::kOriginNone;
     }
     return mutants;
   }
@@ -803,8 +818,8 @@
   // Doesn't execute anything.
   // Crash when 0th char of input to binary b1 equals `crashing_input_idx_`, but
   // only on 1st exec.
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     batch_result.ClearAndResize(inputs.size());
     bool res = true;
     if (!first_pass_) {
@@ -816,7 +831,7 @@
       if (input[0] == crashing_input_idx_) {
         if (first_pass_) {
           first_pass_ = false;
-          crashing_input_ = input;
+          crashing_input_ = {input.begin(), input.end()};
           // TODO(b/274705740): `num_outputs_read()` is the number of outputs
           //  that Centipede engine *expects* to have been read from *the
           //  current BatchResult* by the *particular* implementation of
@@ -836,13 +851,14 @@
   }
 
   // Sets the mutants to different 1-byte values.
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    std::vector<ByteArray> mutants;
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    std::vector<Mutant> mutants;
     mutants.reserve(num_mutants);
     for (size_t i = 0; i < num_mutants; ++i) {
       // The contents of each mutant is simply its sequential number.
-      mutants.push_back({static_cast<uint8_t>(curr_input_idx_++)});
+      mutants.push_back({/*data=*/{static_cast<uint8_t>(curr_input_idx_++)},
+                         Mutant::kOriginNone});
     }
     return mutants;
   }
@@ -971,7 +987,7 @@
 
   BatchResult batch_result;
   const std::vector<ByteArray> inputs = {{0}};
-  ASSERT_TRUE(callbacks.Execute(env.binary, inputs, batch_result));
+  ASSERT_TRUE(callbacks.Execute(env.binary, AsByteSpans(inputs), batch_result));
   ASSERT_EQ(batch_result.results().size(), 1);
   bool found_startup_cmp_entry = false;
   batch_result.results()[0].metadata().ForEachCmpEntry(
@@ -988,17 +1004,17 @@
                                           std::thread::id execute_thread_id)
       : CentipedeCallbacks(env), execute_thread_id_(execute_thread_id) {}
 
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     batch_result.ClearAndResize(inputs.size());
     thread_check_passed_ = thread_check_passed_ &&
                            std::this_thread::get_id() == execute_thread_id_;
     return true;
   }
 
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    return {num_mutants, {0}};
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    return {num_mutants, {/*data=*/{0}, Mutant::kOriginNone}};
   }
 
   bool thread_check_passed() { return thread_check_passed_; }
@@ -1033,7 +1049,8 @@
   BatchResult batch_result;
   const std::vector<ByteArray> inputs = {ByteArray{'s', 't', 'k'}};
 
-  ASSERT_FALSE(callbacks.Execute(env.binary, inputs, batch_result));
+  ASSERT_FALSE(
+      callbacks.Execute(env.binary, AsByteSpans(inputs), batch_result));
   EXPECT_THAT(batch_result.log(), HasSubstr("Stack limit exceeded"));
   EXPECT_EQ(batch_result.failure_description(), "stack-limit-exceeded");
 }
@@ -1042,8 +1059,8 @@
  public:
   using CentipedeCallbacks::CentipedeCallbacks;
 
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     ++execute_count_;
     batch_result.ClearAndResize(inputs.size());
     batch_result.exit_code() = EXIT_FAILURE;
@@ -1051,9 +1068,9 @@
     return false;
   }
 
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    return {num_mutants, {0}};
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    return {num_mutants, {/*data=*/{0}, Mutant::kOriginNone}};
   }
 
   int execute_count() const { return execute_count_; }
@@ -1079,8 +1096,8 @@
  public:
   using CentipedeCallbacks::CentipedeCallbacks;
 
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     ++execute_count_;
     batch_result.ClearAndResize(inputs.size());
     batch_result.exit_code() = EXIT_FAILURE;
@@ -1089,9 +1106,9 @@
     return false;
   }
 
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    return {num_mutants, {0}};
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    return {num_mutants, {/*data=*/{0}, Mutant::kOriginNone}};
   }
 
   int execute_count() const { return execute_count_; }
@@ -1117,8 +1134,8 @@
  public:
   using CentipedeCallbacks::CentipedeCallbacks;
 
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     ++execute_count_;
     batch_result.ClearAndResize(inputs.size());
     batch_result.exit_code() = EXIT_FAILURE;
@@ -1127,9 +1144,9 @@
     return false;
   }
 
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
-    return {num_mutants, {0}};
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
+    return {num_mutants, {/*data=*/{0}, Mutant::kOriginNone}};
   }
 
   int execute_count() const { return execute_count_; }
@@ -1160,11 +1177,11 @@
   CentipedeDefaultCallbacks callbacks(env);
 
   const std::vector<ByteArray> inputs = {{1}, {2}, {3}, {4}, {5}, {6}};
-  const std::vector<ByteArray> mutants = callbacks.Mutate(
+  const std::vector<Mutant> mutants = callbacks.Mutate(
       GetMutationInputRefsFromDataInputs(inputs), inputs.size());
 
   // The custom mutator just returns the original inputs as mutants.
-  EXPECT_EQ(inputs, mutants);
+  EXPECT_EQ(inputs, GetDataFromMutants(mutants));
 }
 
 TEST_F(CentipedeWithTemporaryLocalDir, FailsOnMisbehavingCustomMutator) {
@@ -1193,12 +1210,12 @@
   CentipedeDefaultCallbacks callbacks(env);
 
   const std::vector<ByteArray> inputs = {{1}, {2}, {3}, {4}, {5}, {6}};
-  const std::vector<ByteArray> mutants = callbacks.Mutate(
+  const std::vector<Mutant> mutants = callbacks.Mutate(
       GetMutationInputRefsFromDataInputs(inputs), inputs.size());
 
   // The built-in mutator performs non-trivial mutations.
   EXPECT_EQ(inputs.size(), mutants.size());
-  EXPECT_NE(inputs, mutants);
+  EXPECT_NE(inputs, GetDataFromMutants(mutants));
 }
 
 TEST_F(CentipedeWithTemporaryLocalDir,
@@ -1227,7 +1244,8 @@
   env.fork_server = false;
 
   // Test that the process does not get stuck and exits promptly.
-  EXPECT_FALSE(callbacks.Execute(env.binary, {{0}}, batch_result));
+  const ByteArray input = {0};
+  EXPECT_FALSE(callbacks.Execute(env.binary, {input}, batch_result));
 }
 
 TEST_F(CentipedeWithTemporaryLocalDir, ExecuteEndsAfterCustomFailure) {
@@ -1239,11 +1257,11 @@
       {'c', 'u', 's', 't', 'o', 'm'},
       {'c', 'u', 's', 't', 'o', 'm'},
   };
-  EXPECT_FALSE(callbacks.Execute(env.binary, inputs, result));
+  EXPECT_FALSE(callbacks.Execute(env.binary, AsByteSpans(inputs), result));
   EXPECT_THAT(result.failure_description(), HasSubstr("custom 0"));
   EXPECT_THAT(result.log(), AllOf(HasSubstr("custom failure 0"),
                                   Not(HasSubstr("custom failure 1"))));
-  EXPECT_FALSE(callbacks.Execute(env.binary, inputs, result));
+  EXPECT_FALSE(callbacks.Execute(env.binary, AsByteSpans(inputs), result));
   EXPECT_THAT(result.failure_description(), HasSubstr("custom 1"));
   EXPECT_THAT(result.log(), AllOf(HasSubstr("custom failure 1"),
                                   Not(HasSubstr("custom failure 2"))));
@@ -1259,7 +1277,7 @@
       {'s', 'o', 'm', 'e'},
   };
   ClearEarlyStopRequestAndSetStopTime(absl::InfiniteFuture());
-  EXPECT_TRUE(callbacks.Execute(env.binary, inputs, result));
+  EXPECT_TRUE(callbacks.Execute(env.binary, AsByteSpans(inputs), result));
   // Match the error log to check for retrying mutation.
   EXPECT_DEATH(
       [&] {
diff --git a/centipede/command.cc b/centipede/command.cc
index 3536d93..3071428 100644
--- a/centipede/command.cc
+++ b/centipede/command.cc
@@ -185,12 +185,14 @@
 // PIMPL).
 Command::~Command() {
   if (is_executing()) {
-    FUZZTEST_LOG(WARNING)
-        << "Destructing Command object for " << path() << " with "
-        << (fork_server_ ? absl::StrCat("fork server PID ", fork_server_->pid_)
-                         : absl::StrCat("PID ", pid_))
-        << " still running. Requesting it to stop without waiting for it...";
-    RequestStop();
+    FUZZTEST_LOG(WARNING) << "Destructing Command object for " << path()
+                          << " with "
+                          << (fork_server_ ? absl::StrCat("fork server PID ",
+                                                          fork_server_->pid_)
+                                           : absl::StrCat("PID ", pid_))
+                          << " still running. Requesting it to force-stop "
+                             "without waiting for it...";
+    RequestStop(/*force=*/true);
   }
   ResetRedirectionFiles(/*new_suffix=*/"");
 }
@@ -520,15 +522,18 @@
   return exit_code;
 }
 
-void Command::RequestStop() {
+void Command::RequestStop(bool force) {
   FUZZTEST_CHECK(is_executing());
   if (fork_server_) {
     FUZZTEST_CHECK_NE(fork_server_->pid_, -1);
-    kill(fork_server_->pid_, SIGTERM);
+    // Cannot send SIGKILL to the fork server as it kills only the parent
+    // process, but not the child. The fork server would send SIGKILL to the
+    // child on SIGUSR1.
+    kill(fork_server_->pid_, force ? SIGUSR1 : SIGTERM);
     return;
   }
   FUZZTEST_CHECK_NE(pid_, -1);
-  kill(pid_, SIGTERM);
+  kill(pid_, force ? SIGKILL : SIGTERM);
 }
 
 std::string Command::ReadRedirectedStdout() const {
diff --git a/centipede/command.h b/centipede/command.h
index a2fab51..d9edf8d 100644
--- a/centipede/command.h
+++ b/centipede/command.h
@@ -96,10 +96,11 @@
   // call `RequestEarlyStop()` (see stop.h).
   std::optional<int> Wait(absl::Time deadline);
 
-  // Requests the command execution to stop. Must be called only when the
-  // command is executing. Note that after calling this, `Wait()` is still
-  // needed to complete the execution.
-  void RequestStop();
+  // Requests the command execution to stop by sending SIGTERM or SIGKILL (when
+  // `force` is true). Must be called only when the command is executing. Note
+  // that after calling this, `Wait()` is still needed to complete the
+  // execution.
+  void RequestStop(bool force = false);
 
   // Convenient method to execute synchronously.
   int Execute() {
diff --git a/centipede/command_test.cc b/centipede/command_test.cc
index f4aaa36..dc163c9 100644
--- a/centipede/command_test.cc
+++ b/centipede/command_test.cc
@@ -24,6 +24,7 @@
 #include <string_view>
 #include <utility>
 
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include "absl/strings/substitute.h"
 #include "absl/time/clock.h"
@@ -35,6 +36,8 @@
 namespace fuzztest::internal {
 namespace {
 
+using ::testing::Optional;
+
 TEST(CommandTest, ToString) {
   EXPECT_EQ(Command{"x"}.ToString(), "env \\\nx");
   {
@@ -149,6 +152,24 @@
   }
 
   {
+    const std::string input = "sleep";
+    const std::string log_prefix = std::filesystem::path{test_tmpdir} / input;
+    Command::Options cmd_options;
+    cmd_options.args = {input};
+    cmd_options.stdout_file_prefix = log_prefix;
+    cmd_options.stderr_file_prefix = log_prefix;
+    Command cmd{helper, std::move(cmd_options)};
+    ASSERT_TRUE(cmd.StartForkServer(test_tmpdir, "ForkServer"));
+    ASSERT_TRUE(cmd.ExecuteAsync());
+    EXPECT_EQ(cmd.Wait(absl::Now() + absl::Seconds(2)), std::nullopt);
+    cmd.RequestStop(/*force=*/false);
+    EXPECT_THAT(cmd.Wait(absl::Now() + absl::Seconds(2)), Optional(SIGTERM));
+    std::string log_contents;
+    ReadFromLocalFile(cmd.stdout_file(), log_contents);
+    EXPECT_EQ(log_contents, absl::Substitute("Got input: $0", input));
+  }
+
+  {
     const std::string input = "hang";
     const std::string log_prefix = std::filesystem::path{test_tmpdir} / input;
     Command::Options cmd_options;
@@ -159,6 +180,10 @@
     ASSERT_TRUE(cmd.StartForkServer(test_tmpdir, "ForkServer"));
     ASSERT_TRUE(cmd.ExecuteAsync());
     EXPECT_EQ(cmd.Wait(absl::Now() + absl::Seconds(2)), std::nullopt);
+    cmd.RequestStop(/*force=*/false);
+    EXPECT_EQ(cmd.Wait(absl::Now() + absl::Seconds(2)), std::nullopt);
+    cmd.RequestStop(/*force=*/true);
+    EXPECT_THAT(cmd.Wait(absl::Now() + absl::Seconds(2)), Optional(SIGKILL));
     std::string log_contents;
     ReadFromLocalFile(cmd.stdout_file(), log_contents);
     EXPECT_EQ(log_contents, absl::Substitute("Got input: $0", input));
diff --git a/centipede/command_test_helper.cc b/centipede/command_test_helper.cc
index ac5b00f..d3153a8 100644
--- a/centipede/command_test_helper.cc
+++ b/centipede/command_test_helper.cc
@@ -15,11 +15,14 @@
 #include <unistd.h>
 
 #include <cassert>
+#include <csignal>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 
 #include "absl/base/nullability.h"
+#include "absl/time/clock.h"
+#include "absl/time/time.h"
 
 // A binary linked with the fork server that exits/crashes in different ways.
 int main(int argc, char** absl_nonnull argv) {
@@ -31,6 +34,13 @@
   if (!strcmp(argv[1], "ret42")) return 42;
   if (!strcmp(argv[1], "abort")) abort();
   // Sleep longer than kTimeout in CommandDeathTest_ForkServerHangingBinary.
-  if (!strcmp(argv[1], "hang")) sleep(5);
+  if (!strcmp(argv[1], "sleep")) absl::SleepFor(absl::Seconds(5));
+  if (!strcmp(argv[1], "hang")) {
+    struct sigaction act{};
+    act.sa_handler = [](int) {};
+    sigaction(SIGTERM, &act, nullptr);
+    absl::SleepFor(absl::Seconds(10));
+  }
+
   return 17;
 }
diff --git a/centipede/corpus.cc b/centipede/corpus.cc
index f3bc001..ba1df9b 100644
--- a/centipede/corpus.cc
+++ b/centipede/corpus.cc
@@ -229,7 +229,7 @@
   return subset_to_remove.size();
 }
 
-void Corpus::Add(const ByteArray& data, const FeatureVec& fv,
+void Corpus::Add(ByteSpan data, const FeatureVec& fv,
                  const ExecutionMetadata& metadata,
                  const ExecutionResult::Stats& stats, const FeatureSet& fs,
                  const CoverageFrontier& coverage_frontier) {
@@ -237,17 +237,17 @@
   FUZZTEST_CHECK(!data.empty())
       << "Got request to add empty element to corpus: ignoring";
   FUZZTEST_CHECK_EQ(records_.size(), weighted_distribution_.size());
-  records_.push_back({data, fv, metadata, stats});
+  records_.push_back({{data.begin(), data.end()}, fv, metadata, stats});
   // Will be updated by `UpdateWeights`.
   weighted_distribution_.AddWeight(0);
 }
 
-const CorpusRecord& Corpus::WeightedRandom(absl::BitGenRef rng) const {
-  return records_[weighted_distribution_.RandomIndex(rng)];
+size_t Corpus::WeightedRandom(absl::BitGenRef rng) const {
+  return weighted_distribution_.RandomIndex(rng);
 }
 
-const CorpusRecord& Corpus::UniformRandom(absl::BitGenRef rng) const {
-  return records_[absl::Uniform<size_t>(rng, 0, records_.size())];
+size_t Corpus::UniformRandom(absl::BitGenRef rng) const {
+  return absl::Uniform<size_t>(rng, 0, records_.size());
 }
 
 void Corpus::DumpStatsToFile(const FeatureSet &fs, std::string_view filepath,
diff --git a/centipede/corpus.h b/centipede/corpus.h
index 1a1c4c1..4c16ad3 100644
--- a/centipede/corpus.h
+++ b/centipede/corpus.h
@@ -121,7 +121,7 @@
   // Adds a corpus element, consisting of 'data' (the input bytes, non-empty),
   // 'fv' (the features associated with this input), and execution `metadata`.
   // `fs` is used to compute weights of `fv`.
-  void Add(const ByteArray& data, const FeatureVec& fv,
+  void Add(ByteSpan data, const FeatureVec& fv,
            const ExecutionMetadata& metadata,
            const ExecutionResult::Stats& stats, const FeatureSet& fs,
            const CoverageFrontier& coverage_frontier);
@@ -149,11 +149,11 @@
   size_t NumActive() const { return records_.size(); }
   // Returns the max and avg sizes of the inputs.
   std::pair<size_t, size_t> MaxAndAvgSize() const;
-  // Returns a random active corpus record using weighted distribution.
+  // Returns a random active corpus record index using weighted distribution.
   // See WeightedDistribution.
-  const CorpusRecord& WeightedRandom(absl::BitGenRef rng) const;
-  // Returns a random active corpus record using uniform distribution.
-  const CorpusRecord& UniformRandom(absl::BitGenRef rng) const;
+  size_t WeightedRandom(absl::BitGenRef rng) const;
+  // Returns a random active corpus record index using uniform distribution.
+  size_t UniformRandom(absl::BitGenRef rng) const;
   // Returns the element with index 'idx', where `idx` < NumActive().
   const ByteArray &Get(size_t idx) const { return records_[idx].data; }
   // Returns the execution metadata for the element `idx`, `idx` < NumActive().
diff --git a/centipede/corpus_test.cc b/centipede/corpus_test.cc
index 4b47d5c..46e4d4e 100644
--- a/centipede/corpus_test.cc
+++ b/centipede/corpus_test.cc
@@ -173,8 +173,7 @@
     freq.clear();
     freq.resize(corpus.NumActive());
     for (int i = 0; i < kNumIter; i++) {
-      const auto& record = corpus.WeightedRandom(rng);
-      const auto id = record.data[0];
+      const auto id = corpus.Records()[corpus.WeightedRandom(rng)].data[0];
       ASSERT_LT(id, freq.size());
       freq[id]++;
     }
@@ -215,8 +214,7 @@
     freq.clear();
     freq.resize(corpus.NumActive());
     for (int i = 0; i < kNumIter; i++) {
-      const auto& record = corpus.WeightedRandom(rng);
-      const auto id = record.data[0];
+      const auto id = corpus.Records()[corpus.WeightedRandom(rng)].data[0];
       ASSERT_LT(id, freq.size());
       freq[id]++;
     }
@@ -256,8 +254,7 @@
     freq.clear();
     freq.resize(corpus.NumActive());
     for (int i = 0; i < kNumIter; i++) {
-      const auto& record = corpus.WeightedRandom(rng);
-      const auto id = record.data[0];
+      const auto id = corpus.Records()[corpus.WeightedRandom(rng)].data[0];
       ASSERT_LT(id, freq.size());
       freq[id]++;
     }
@@ -300,10 +297,8 @@
     freq.clear();
     freq.resize(corpus.NumActive());
     for (int i = 0; i < kNumIter; i++) {
-      const auto& record = corpus.WeightedRandom(rng);
-      const auto id = record.data[0];
-      ASSERT_LT(id, freq.size());
-      freq[id]++;
+      const size_t idx = corpus.WeightedRandom(rng);
+      freq[idx]++;
     }
   };
 
diff --git a/centipede/crash_deduplication_test.cc b/centipede/crash_deduplication_test.cc
index bd1966e..f878871 100644
--- a/centipede/crash_deduplication_test.cc
+++ b/centipede/crash_deduplication_test.cc
@@ -27,6 +27,7 @@
 #include "absl/strings/str_format.h"
 #include "absl/time/clock.h"
 #include "absl/time/time.h"
+#include "absl/types/span.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/crash_summary.h"
 #include "./centipede/environment.h"
@@ -168,7 +169,7 @@
       absl::flat_hash_map<std::string, Crash> crashing_inputs)
       : CentipedeCallbacks(env), crashing_inputs_(std::move(crashing_inputs)) {}
 
-  bool Execute(std::string_view binary, const std::vector<ByteArray>& inputs,
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
                BatchResult& batch_result) override {
     batch_result.ClearAndResize(inputs.size());
     for (ByteSpan input : inputs) {
diff --git a/centipede/dispatcher.cc b/centipede/dispatcher.cc
index d82cd28..3ecb1f0 100644
--- a/centipede/dispatcher.cc
+++ b/centipede/dispatcher.cc
@@ -31,6 +31,7 @@
 
 #include "absl/base/nullability.h"
 #include "./centipede/execution_metadata.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_request.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/shared_memory_blob_sequence.h"
@@ -433,6 +434,7 @@
 using fuzztest::internal::kDispatcherTestGetSeedsOutputDirFlagHeader;
 using fuzztest::internal::kDispatcherTestListingPrefixFlagHeader;
 using fuzztest::internal::kDispatcherTestNameFlagHeader;
+using fuzztest::internal::MutantRef;
 using fuzztest::internal::MutationResult;
 
 int FuzzTestDispatcherIsEnabled() {
@@ -536,7 +538,11 @@
   auto* output = GetOutputsBlobSequence();
   DispatcherCheck(output != nullptr, "outputs blob sequence must exist");
   DispatcherCheck(MutationResult::WriteMutant(
-                      {static_cast<const uint8_t*>(data), size}, *output),
+                      MutantRef{{static_cast<const uint8_t*>(data), size},
+                                // TODO(xinhaoyuan): change the dispatcher
+                                // interface to include the origin.
+                                fuzztest::internal::Mutant::kOriginNone},
+                      *output),
                   "failed to write mutant");
 }
 
diff --git a/centipede/fuzztest_mutator.cc b/centipede/fuzztest_mutator.cc
index 0690f28..1af4e17 100644
--- a/centipede/fuzztest_mutator.cc
+++ b/centipede/fuzztest_mutator.cc
@@ -29,7 +29,7 @@
 #include "./centipede/byte_array_mutator.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/knobs.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./common/defs.h"
 #include "./common/logging.h"
 #include "./fuzztest/domain_core.h"
@@ -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;
@@ -57,27 +67,38 @@
 void PopulateCmpEntries(const ExecutionMetadata& metadata,
                         TablesOfRecentCompares& cmp_tables) {
   // Size limits on the cmp entries to be populated.
-  static constexpr uint8_t kMaxCmpEntrySize = 15;
+  static constexpr uint8_t kMaxCmpEntrySize = 128;
   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);
+    }
   });
 }
 
@@ -139,31 +160,31 @@
   }
 }
 
-std::vector<ByteArray> FuzzTestMutator::MutateMany(
-    const std::vector<MutationInputRef> &inputs, size_t num_mutants) {
+std::vector<Mutant> FuzzTestMutator::MutateMany(
+    absl::Span<const MutationInputRef> inputs, size_t num_mutants) {
   if (inputs.empty()) abort();
   auto& cmp_tables = mutation_metadata_->cmp_tables;
   cmp_tables.resize(inputs.size());
-  std::vector<ByteArray> mutants;
+  std::vector<Mutant> mutants;
   mutants.reserve(num_mutants);
-  for (int i = 0; i < num_mutants; ++i) {
-    auto index = absl::Uniform<size_t>(prng_, 0, inputs.size());
-    if (!cmp_tables[index].has_value() && inputs[index].metadata != nullptr) {
-      cmp_tables[index].emplace(/*compact=*/true);
-      PopulateCmpEntries(*inputs[index].metadata, *cmp_tables[index]);
+  for (size_t i = 0; i < num_mutants; ++i) {
+    const size_t origin = absl::Uniform<size_t>(prng_, 0, inputs.size());
+    if (!cmp_tables[origin].has_value() && inputs[origin].metadata != nullptr) {
+      cmp_tables[origin].emplace(/*compact=*/true);
+      PopulateCmpEntries(*inputs[origin].metadata, *cmp_tables[origin]);
     }
-    auto mutant = inputs[index].data;
-    if (mutant.size() > max_len_) mutant.resize(max_len_);
+    auto mutant = Mutant{inputs[origin].data, origin};
+    if (mutant.data.size() > max_len_) mutant.data.resize(max_len_);
     if (knobs_.GenerateBool(knob_mutate_or_crossover, prng_())) {
       // Perform crossover with some other input. It may be the same input.
       const auto &other_input =
           inputs[absl::Uniform<size_t>(prng_, 0, inputs.size())].data;
-      CrossOver(mutant, other_input);
+      CrossOver(mutant.data, other_input);
     } else {
       domain_->Mutate(
-          mutant, prng_,
-          {/*cmp_tables=*/cmp_tables[index].has_value() ? &*cmp_tables[index]
-                                                        : nullptr},
+          mutant.data, prng_,
+          {/*cmp_tables=*/cmp_tables[origin].has_value() ? &*cmp_tables[origin]
+                                                         : nullptr},
           /*only_shrink=*/false);
     }
     mutants.push_back(std::move(mutant));
diff --git a/centipede/fuzztest_mutator.h b/centipede/fuzztest_mutator.h
index 8b68460..8ee29ae 100644
--- a/centipede/fuzztest_mutator.h
+++ b/centipede/fuzztest_mutator.h
@@ -20,9 +20,10 @@
 #include <memory>
 #include <vector>
 
+#include "absl/types/span.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/knobs.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./common/defs.h"
 #include "./fuzztest/internal/table_of_recent_compares.h"
 
@@ -44,8 +45,8 @@
   ~FuzzTestMutator();
 
   // Takes non-empty `inputs` and produces `num_mutants` mutants.
-  std::vector<ByteArray> MutateMany(const std::vector<MutationInputRef> &inputs,
-                                    size_t num_mutants);
+  std::vector<Mutant> MutateMany(absl::Span<const MutationInputRef> inputs,
+                                 size_t num_mutants);
 
   // Adds `dict_entries` to the internal mutation dictionary.
   void AddToDictionary(const std::vector<ByteArray>& dict_entries);
diff --git a/centipede/fuzztest_mutator_test.cc b/centipede/fuzztest_mutator_test.cc
index 327bc83..a732bca 100644
--- a/centipede/fuzztest_mutator_test.cc
+++ b/centipede/fuzztest_mutator_test.cc
@@ -24,7 +24,7 @@
 #include "absl/strings/str_join.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/knobs.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./common/defs.h"
 
 namespace fuzztest::internal {
@@ -33,6 +33,7 @@
 
 using ::testing::AllOf;
 using ::testing::Each;
+using ::testing::Field;
 using ::testing::IsSupersetOf;
 using ::testing::Le;
 using ::testing::SizeIs;
@@ -49,10 +50,10 @@
     std::vector<MutationInputRef> mutation_inputs = {{data}};
     constexpr size_t kMutantSequenceLength = 100;
     for (size_t iter = 0; iter < kMutantSequenceLength; iter++) {
-      const std::vector<ByteArray> mutants =
+      const std::vector<Mutant> mutants =
           mutator[i].MutateMany(mutation_inputs, 1);
       ASSERT_EQ(mutants.size(), 1);
-      res[i].push_back(mutants[0]);
+      res[i].push_back(mutants[0].data);
     }
   }
   EXPECT_NE(res[0], res[1]);
@@ -64,7 +65,7 @@
   FuzzTestMutator mutator(knobs, /*seed=*/1);
   EXPECT_TRUE(mutator.set_max_len(kMaxLen));
   constexpr size_t kNumMutantsToGenerate = 10000;
-  const std::vector<ByteArray> mutants = mutator.MutateMany(
+  const std::vector<Mutant> mutants = mutator.MutateMany(
       {
           {/*data=*/{0, 1, 2, 3, 4, 5, 6, 7}},
           {/*data=*/{0}},
@@ -74,70 +75,70 @@
       },
       kNumMutantsToGenerate);
 
-  EXPECT_THAT(mutants,
-              AllOf(SizeIs(kNumMutantsToGenerate), Each(SizeIs(Le(kMaxLen)))));
+  EXPECT_THAT(mutants, AllOf(SizeIs(kNumMutantsToGenerate),
+                             Each(Field(&Mutant::data, SizeIs(Le(kMaxLen))))));
 }
 
 TEST(FuzzTestMutator, CrossOverInsertsDataFromOtherInputs) {
   const Knobs knobs;
   FuzzTestMutator mutator(knobs, /*seed=*/1);
   constexpr size_t kNumMutantsToGenerate = 100000;
-  const std::vector<ByteArray> mutants = mutator.MutateMany(
+  const std::vector<Mutant> mutants = mutator.MutateMany(
       {
           {/*data=*/{0, 1, 2, 3}},
           {/*data=*/{4, 5, 6, 7}},
       },
       kNumMutantsToGenerate);
 
-  EXPECT_THAT(mutants, IsSupersetOf(std::vector<ByteArray>{
-                           // The entire other input
-                           {4, 5, 6, 7, 0, 1, 2, 3},
-                           {0, 1, 4, 5, 6, 7, 2, 3},
-                           {0, 1, 2, 3, 4, 5, 6, 7},
-                           // The prefix of other input
-                           {4, 5, 6, 0, 1, 2, 3},
-                           {0, 1, 4, 5, 6, 2, 3},
-                           {0, 1, 2, 3, 4, 5, 6},
-                           // The suffix of other input
-                           {5, 6, 7, 0, 1, 2, 3},
-                           {0, 1, 5, 6, 7, 2, 3},
-                           {0, 1, 2, 3, 5, 6, 7},
-                           // The middle of other input
-                           {5, 6, 0, 1, 2, 3},
-                           {0, 1, 5, 6, 2, 3},
-                           {0, 1, 2, 3, 5, 6},
-                       }));
+  EXPECT_THAT(GetDataFromMutants(mutants), IsSupersetOf(std::vector<ByteArray>{
+                                               // The entire other input
+                                               {4, 5, 6, 7, 0, 1, 2, 3},
+                                               {0, 1, 4, 5, 6, 7, 2, 3},
+                                               {0, 1, 2, 3, 4, 5, 6, 7},
+                                               // The prefix of other input
+                                               {4, 5, 6, 0, 1, 2, 3},
+                                               {0, 1, 4, 5, 6, 2, 3},
+                                               {0, 1, 2, 3, 4, 5, 6},
+                                               // The suffix of other input
+                                               {5, 6, 7, 0, 1, 2, 3},
+                                               {0, 1, 5, 6, 7, 2, 3},
+                                               {0, 1, 2, 3, 5, 6, 7},
+                                               // The middle of other input
+                                               {5, 6, 0, 1, 2, 3},
+                                               {0, 1, 5, 6, 2, 3},
+                                               {0, 1, 2, 3, 5, 6},
+                                           }));
 }
 
 TEST(FuzzTestMutator, CrossOverOverwritesDataFromOtherInputs) {
   const Knobs knobs;
   FuzzTestMutator mutator(knobs, /*seed=*/1);
   constexpr size_t kNumMutantsToGenerate = 100000;
-  const std::vector<ByteArray> mutants = mutator.MutateMany(
+  const std::vector<Mutant> mutants = mutator.MutateMany(
       {
           {/*data=*/{0, 1, 2, 3, 4, 5, 6, 7}},
           {/*data=*/{100, 101, 102, 103}},
       },
       kNumMutantsToGenerate);
 
-  EXPECT_THAT(mutants, IsSupersetOf(std::vector<ByteArray>{
-                           // The entire other input
-                           {100, 101, 102, 103, 4, 5, 6, 7},
-                           {0, 1, 100, 101, 102, 103, 6, 7},
-                           {0, 1, 2, 3, 100, 101, 102, 103},
-                           // The prefix of other input
-                           {100, 101, 102, 3, 4, 5, 6, 7},
-                           {0, 1, 2, 100, 101, 102, 6, 7},
-                           {0, 1, 2, 3, 4, 100, 101, 102},
-                           // The suffix of other input
-                           {101, 102, 103, 3, 4, 5, 6, 7},
-                           {0, 1, 2, 101, 102, 103, 6, 7},
-                           {0, 1, 2, 3, 4, 101, 102, 103},
-                           // The middle of other input
-                           {101, 102, 2, 3, 4, 5, 6, 7},
-                           {0, 1, 2, 101, 102, 5, 6, 7},
-                           {0, 1, 2, 3, 4, 5, 101, 102},
-                       }));
+  EXPECT_THAT(GetDataFromMutants(mutants), IsSupersetOf(std::vector<ByteArray>{
+                                               // The entire other input
+                                               {100, 101, 102, 103, 4, 5, 6, 7},
+                                               {0, 1, 100, 101, 102, 103, 6, 7},
+                                               {0, 1, 2, 3, 100, 101, 102, 103},
+                                               // The prefix of other input
+                                               {100, 101, 102, 3, 4, 5, 6, 7},
+                                               {0, 1, 2, 100, 101, 102, 6, 7},
+                                               {0, 1, 2, 3, 4, 100, 101, 102},
+                                               // The suffix of other input
+                                               {101, 102, 103, 3, 4, 5, 6, 7},
+                                               {0, 1, 2, 101, 102, 103, 6, 7},
+                                               {0, 1, 2, 3, 4, 101, 102, 103},
+                                               // The middle of other input
+                                               {101, 102, 2, 3, 4, 5, 6, 7},
+                                               {0, 1, 2, 101, 102, 5, 6, 7},
+                                               {0, 1, 2, 3, 4, 5, 101, 102},
+                                           }));
 }
 
 // Test parameter containing the mutation settings and the expectations of a
@@ -181,12 +182,12 @@
   const std::vector<MutationInputRef> inputs = {
       {/*data=*/GetParam().seed_input, /*metadata=*/&metadata}};
   for (size_t i = 0; i < GetParam().max_num_iterations; i++) {
-    const std::vector<ByteArray> mutants = mutator.MutateMany(inputs, 1);
+    const std::vector<Mutant> mutants = mutator.MutateMany(inputs, 1);
     ASSERT_EQ(mutants.size(), 1);
     const auto& mutant = mutants[0];
-    EXPECT_FALSE(unexpected_mutants.contains(mutant))
-        << "Unexpected mutant: {" << absl::StrJoin(mutant, ",") << "}";
-    unmatched_expected_mutants.erase(mutant);
+    EXPECT_FALSE(unexpected_mutants.contains(mutant.data))
+        << "Unexpected mutant: {" << absl::StrJoin(mutant.data, ",") << "}";
+    unmatched_expected_mutants.erase(mutant.data);
     if (unmatched_expected_mutants.empty() &&
         i >= GetParam().min_num_iterations)
       break;
@@ -284,22 +285,34 @@
 INSTANTIATE_TEST_SUITE_P(SkipsLongCmpEntry, MutationStepTest, Values([] {
                            MutationStepTestParameter params;
                            params.seed_input = {0};
+                           ByteArray short_entry;
+                           for (size_t i = 0; i < 5; ++i) {
+                             short_entry.push_back(i);
+                           }
                            params.expected_mutants = {
-                               {0, 1, 2, 3, 4},
+                               short_entry,
                            };
+                           ByteArray long_entry;
+                           for (size_t i = 0; i < 129; ++i) {
+                             long_entry.push_back(i);
+                           }
                            params.unexpected_mutants = {
-                               {0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
-                                11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
+                               long_entry,
                            };
-                           params.cmp_data = {
-                               20,  // size
-                               1,  2,  3,  4,  5,  6,  7,  8,  9,  10,
-                               11, 12, 13, 14, 15, 16, 17, 18, 19, 20,  // lhs
-                               1,  2,  3,  4,  5,  6,  7,  8,  9,  10,
-                               11, 12, 13, 14, 15, 16, 17, 18, 19, 20,  // rhs
-                               4,                                       // size
-                               1,  2,  3,  4,                           // lhs
-                               1,  2,  3,  4};                          // rhs
+                           params.cmp_data.push_back(short_entry.size());
+                           params.cmp_data.insert(params.cmp_data.end(),
+                                                  short_entry.begin(),
+                                                  short_entry.end());  // lhs
+                           params.cmp_data.insert(params.cmp_data.end(),
+                                                  short_entry.begin(),
+                                                  short_entry.end());  // rhs
+                           params.cmp_data.push_back(long_entry.size());
+                           params.cmp_data.insert(params.cmp_data.end(),
+                                                  long_entry.begin(),
+                                                  long_entry.end());  // lhs
+                           params.cmp_data.insert(params.cmp_data.end(),
+                                                  long_entry.begin(),
+                                                  long_entry.end());  // rhs
                            return params;
                          }()));
 
diff --git a/centipede/minimize_crash.cc b/centipede/minimize_crash.cc
index d9fa681..245846c 100644
--- a/centipede/minimize_crash.cc
+++ b/centipede/minimize_crash.cc
@@ -26,7 +26,7 @@
 #include "absl/synchronization/mutex.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/environment.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/stop.h"
 #include "./centipede/thread_pool.h"
@@ -114,21 +114,21 @@
     // discarding all inputs that are too large.
     // TODO(kcc): modify the Mutate() interface such that max_len can be passed.
     //
-    const std::vector<ByteArray> mutants = callbacks->Mutate(
+    const std::vector<Mutant> mutants = callbacks->Mutate(
         GetMutationInputRefsFromDataInputs(recent_crashers), env.batch_size);
-    std::vector<ByteArray> smaller_mutants;
+    std::vector<ByteSpan> smaller_mutants;
     for (const auto &m : mutants) {
-      if (m.size() < min_known_size) smaller_mutants.push_back(m);
+      if (m.data.size() < min_known_size) smaller_mutants.push_back(m.data);
     }
 
     // Execute all mutants. If a new crasher is found, add it to `queue`.
     if (!callbacks->Execute(env.binary, smaller_mutants, batch_result)) {
       size_t crash_inputs_idx = batch_result.num_outputs_read();
       FUZZTEST_CHECK_LT(crash_inputs_idx, smaller_mutants.size());
-      const auto &new_crasher = smaller_mutants[crash_inputs_idx];
+      const auto new_crasher = smaller_mutants[crash_inputs_idx];
       FUZZTEST_LOG(INFO) << "Crasher: size: " << new_crasher.size() << ": "
                          << AsPrintableString(new_crasher, /*max_len=*/40);
-      queue.AddCrasher(new_crasher);
+      queue.AddCrasher({new_crasher.begin(), new_crasher.end()});
     }
   }
 }
diff --git a/centipede/minimize_crash_test.cc b/centipede/minimize_crash_test.cc
index 30a145a..655c222 100644
--- a/centipede/minimize_crash_test.cc
+++ b/centipede/minimize_crash_test.cc
@@ -23,6 +23,7 @@
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include "absl/base/nullability.h"
+#include "absl/types/span.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/environment.h"
 #include "./centipede/runner_result.h"
@@ -40,10 +41,10 @@
   MinimizerMock(const Environment &env) : CentipedeCallbacks(env) {}
 
   // Runs FuzzMe() on every input, imitates failure if FuzzMe() returns true.
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     batch_result.ClearAndResize(inputs.size());
-    for (auto &input : inputs) {
+    for (auto input : inputs) {
       if (FuzzMe(input)) {
         batch_result.exit_code() = EXIT_FAILURE;
         return false;
diff --git a/centipede/mutation_data.h b/centipede/mutation_data.h
new file mode 100644
index 0000000..4dc0ee5
--- /dev/null
+++ b/centipede/mutation_data.h
@@ -0,0 +1,95 @@
+// Copyright 2023 The Centipede Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Data types used for mutation.
+//
+// This library is for both engine and runner.
+
+#ifndef THIRD_PARTY_CENTIPEDE_MUTATION_DATA_H_
+#define THIRD_PARTY_CENTIPEDE_MUTATION_DATA_H_
+
+#include <cstddef>
+#include <vector>
+
+#include "./centipede/execution_metadata.h"
+#include "./common/defs.h"
+
+namespace fuzztest::internal {
+
+// {data (required), metadata (optional)} reference pairs as mutation inputs.
+struct MutationInputRef {
+  const ByteArray &data;
+  const ExecutionMetadata *metadata = nullptr;
+};
+
+inline std::vector<ByteArray> CopyDataFromMutationInputRefs(
+    const std::vector<MutationInputRef> &inputs) {
+  std::vector<ByteArray> results;
+  results.reserve(inputs.size());
+  for (const auto &input : inputs) results.push_back(input.data);
+  return results;
+}
+
+inline std::vector<MutationInputRef> GetMutationInputRefsFromDataInputs(
+    const std::vector<ByteArray> &inputs) {
+  std::vector<MutationInputRef> results;
+  results.reserve(inputs.size());
+  for (const auto &input : inputs) results.push_back({/*data=*/input});
+  return results;
+}
+
+// Represents a mutation result.
+struct Mutant {
+  // The mutant `data`.
+  ByteArray data;
+  // The index of the input used to mutate into `data`. The base array may be
+  // different depending on the context: As mutation output it refers to the
+  // mutation input batch; As execution input it refers to the in-memory corpus.
+  size_t origin = kOriginNone;
+  // A special `origin` value to indicate that the mutant has no origin.
+  static constexpr size_t kOriginNone = static_cast<size_t>(-1);
+};
+
+inline bool operator==(const Mutant& mutant, const Mutant& other) {
+  return mutant.data == other.data && mutant.origin == other.origin;
+}
+
+// A reference counterpart of `Mutant`. Needed because it can be constructed
+// from std::string and/or by the C-only dispatcher without copying the
+// underlying data.
+struct MutantRef {
+  MutantRef() = default;
+
+  explicit MutantRef(const Mutant& mutant) : data(mutant.data) {}
+
+  explicit MutantRef(ByteSpan data, size_t origin)
+      : data(data), origin(origin) {}
+
+  ByteSpan data;
+  size_t origin = Mutant::kOriginNone;
+};
+
+inline std::vector<ByteArray> GetDataFromMutants(
+    const std::vector<Mutant>& mutants) {
+  std::vector<ByteArray> results;
+  results.reserve(mutants.size());
+  for (const auto& mutant : mutants) {
+    results.push_back(mutant.data);
+  }
+  return results;
+}
+
+}  // namespace fuzztest::internal
+
+#endif  // THIRD_PARTY_CENTIPEDE_MUTATION_DATA_H_
diff --git a/centipede/mutation_input_test.cc b/centipede/mutation_data_test.cc
similarity index 96%
rename from centipede/mutation_input_test.cc
rename to centipede/mutation_data_test.cc
index f1bc741..4ccf7ca 100644
--- a/centipede/mutation_input_test.cc
+++ b/centipede/mutation_data_test.cc
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 
 #include <vector>
 
diff --git a/centipede/mutation_input.h b/centipede/mutation_input.h
deleted file mode 100644
index 504c753..0000000
--- a/centipede/mutation_input.h
+++ /dev/null
@@ -1,53 +0,0 @@
-// Copyright 2023 The Centipede Authors.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      https://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-// Data types used for mutation inputs.
-//
-// This library is for both engine and runner.
-
-#ifndef THIRD_PARTY_CENTIPEDE_MUTATION_INPUT_H_
-#define THIRD_PARTY_CENTIPEDE_MUTATION_INPUT_H_
-
-#include <vector>
-
-#include "./centipede/execution_metadata.h"
-#include "./common/defs.h"
-
-namespace fuzztest::internal {
-
-// {data (required), metadata (optional)} reference pairs as mutation inputs.
-struct MutationInputRef {
-  const ByteArray &data;
-  const ExecutionMetadata *metadata = nullptr;
-};
-
-inline std::vector<ByteArray> CopyDataFromMutationInputRefs(
-    const std::vector<MutationInputRef> &inputs) {
-  std::vector<ByteArray> results;
-  results.reserve(inputs.size());
-  for (const auto &input : inputs) results.push_back(input.data);
-  return results;
-}
-
-inline std::vector<MutationInputRef> GetMutationInputRefsFromDataInputs(
-    const std::vector<ByteArray> &inputs) {
-  std::vector<MutationInputRef> results;
-  results.reserve(inputs.size());
-  for (const auto &input : inputs) results.push_back({/*data=*/input});
-  return results;
-}
-
-}  // namespace fuzztest::internal
-
-#endif  // THIRD_PARTY_CENTIPEDE_MUTATION_INPUT_H_
diff --git a/centipede/runner.cc b/centipede/runner.cc
index fbf5a2b..e085b54 100644
--- a/centipede/runner.cc
+++ b/centipede/runner.cc
@@ -49,11 +49,12 @@
 
 #include "absl/base/nullability.h"
 #include "absl/base/optimization.h"
+#include "absl/types/span.h"
 #include "./centipede/byte_array_mutator.h"
 #include "./centipede/dispatcher_flag_helper.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/feature.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_interface.h"
 #include "./centipede/runner_request.h"
 #include "./centipede/runner_result.h"
@@ -215,20 +216,21 @@
   }
 }
 
-__attribute__((noinline)) void CheckStackLimit(uintptr_t sp) {
+__attribute__((noinline)) void CheckStackLimit(size_t stack_usage,
+                                               bool is_current_stack) {
   static std::atomic_flag stack_limit_exceeded = ATOMIC_FLAG_INIT;
   const size_t stack_limit = state->run_time_flags.stack_limit_kb.load() << 10;
   // Check for the stack limit only if sp is inside the stack region.
-  if (stack_limit > 0 && tls.stack_region_low &&
-      tls.top_frame_sp - sp > stack_limit) {
+  if (stack_limit > 0 && stack_usage > stack_limit) {
     const bool test_not_running = state->input_start_time == 0;
-    if (test_not_running) return;
+    if (test_not_running && is_current_stack) return;
     if (stack_limit_exceeded.test_and_set()) return;
     fprintf(stderr,
-            "========= Stack limit exceeded: %" PRIuPTR
+            "========= Stack limit exceeded: %zu"
             " > %zu"
-            " (byte); aborting\n",
-            tls.top_frame_sp - sp, stack_limit);
+            " (byte) in %s; aborting\n",
+            stack_usage, stack_limit,
+            is_current_stack ? "the current stack" : "a previous stack");
     CentipedeSetFailureDescription(
         fuzztest::internal::kExecutionFailureStackLimitExceeded.data());
     std::abort();
@@ -327,8 +329,8 @@
 std::string RunnerCallbacks::GetSerializedTargetConfig() { return ""; }
 
 bool RunnerCallbacks::Mutate(
-    const std::vector<MutationInputRef> & /*inputs*/, size_t /*num_mutants*/,
-    std::function<void(ByteSpan)> /*new_mutant_callback*/) {
+    absl::Span<const MutationInputRef> /*inputs*/, size_t /*num_mutants*/,
+    std::function<void(MutantRef)> /*new_mutant_callback*/) {
   RunnerCheck(!HasCustomMutator(),
               "Class deriving from RunnerCallbacks must implement Mutate() if "
               "HasCustomMutator() returns true.");
@@ -358,8 +360,8 @@
     return custom_mutator_cb_ != nullptr;
   }
 
-  bool Mutate(const std::vector<MutationInputRef> &inputs, size_t num_mutants,
-              std::function<void(ByteSpan)> new_mutant_callback) override;
+  bool Mutate(absl::Span<const MutationInputRef> inputs, size_t num_mutants,
+              std::function<void(MutantRef)> new_mutant_callback) override;
 
  private:
   FuzzerTestOneInputCallback test_one_input_cb_;
@@ -623,7 +625,7 @@
   }
   if (!callbacks.HasCustomMutator()) return EXIT_SUCCESS;
 
-  if (!callbacks.Mutate(input_refs, num_mutants, [&](ByteSpan mutant) {
+  if (!callbacks.Mutate(input_refs, num_mutants, [&](MutantRef mutant) {
         MutationResult::WriteMutant(mutant, outputs_blobseq);
       })) {
     return EXIT_FAILURE;
@@ -632,36 +634,43 @@
 }
 
 bool LegacyRunnerCallbacks::Mutate(
-    const std::vector<MutationInputRef> &inputs, size_t num_mutants,
-    std::function<void(ByteSpan)> new_mutant_callback) {
+    absl::Span<const MutationInputRef> inputs, size_t num_mutants,
+    std::function<void(MutantRef)> new_mutant_callback) {
   if (custom_mutator_cb_ == nullptr) return false;
   unsigned int seed = GetRandomSeed();
   const size_t num_inputs = inputs.size();
   const size_t max_mutant_size = state->run_time_flags.max_len;
   constexpr size_t kAverageMutationAttempts = 2;
-  ByteArray mutant(max_mutant_size);
+  // Reused across iterations to save memory allocations.
+  Mutant mutant;
   for (size_t attempt = 0, num_outputs = 0;
        attempt < num_mutants * kAverageMutationAttempts &&
        num_outputs < num_mutants;
        ++attempt) {
-    const auto &input_data = inputs[rand_r(&seed) % num_inputs].data;
+    mutant.origin = rand_r(&seed) % num_inputs;
+    const auto& input_data = inputs[mutant.origin].data;
 
     size_t size = std::min(input_data.size(), max_mutant_size);
-    std::copy(input_data.cbegin(), input_data.cbegin() + size, mutant.begin());
+    mutant.data.resize(max_mutant_size);
+    std::copy(input_data.cbegin(), input_data.cbegin() + size,
+              mutant.data.begin());
     size_t new_size = 0;
     if ((custom_crossover_cb_ != nullptr) &&
         rand_r(&seed) % 100 < state->run_time_flags.crossover_level) {
       // Perform crossover `crossover_level`% of the time.
       const auto &other_data = inputs[rand_r(&seed) % num_inputs].data;
-      new_size = custom_crossover_cb_(
-          input_data.data(), input_data.size(), other_data.data(),
-          other_data.size(), mutant.data(), max_mutant_size, rand_r(&seed));
+      new_size = custom_crossover_cb_(input_data.data(), input_data.size(),
+                                      other_data.data(), other_data.size(),
+                                      mutant.data.data(), max_mutant_size,
+                                      rand_r(&seed));
     } else {
-      new_size = custom_mutator_cb_(mutant.data(), size, max_mutant_size,
+      new_size = custom_mutator_cb_(mutant.data.data(), size, max_mutant_size,
                                     rand_r(&seed));
     }
     if (new_size == 0) continue;
-    new_mutant_callback({mutant.data(), new_size});
+    if (new_size > max_mutant_size) new_size = max_mutant_size;
+    mutant.data.resize(new_size);
+    new_mutant_callback(MutantRef{mutant});
     ++num_outputs;
   }
   return true;
diff --git a/centipede/runner_cmp_trace.h b/centipede/runner_cmp_trace.h
index 6687875..53d15c6 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,28 +37,49 @@
 //
 // 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:
   // kMaxNumBytesPerValue does not depend on kFixedSize.
-  static constexpr size_t kMaxNumBytesPerValue = 16;
+  static constexpr size_t kMaxNumBytesPerValue = 128;
   static constexpr size_t kNumBytesPerValue =
       kFixedSize ? kFixedSize : kMaxNumBytesPerValue;
 
   // 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 (rand_seed_ == 0) {
+        // Initialize the random seed (likely) once.
+        struct timeval tv = {};
+        constexpr size_t kUsecInSec = 1000000;
+        // There is a chance that `gettimeofday()` triggers `Capture()`
+        // recursively, but this should be fine as we unset `to_clear` before.
+        gettimeofday(&tv, nullptr);
+        rand_seed_ = tv.tv_sec * kUsecInSec + tv.tv_usec;
+      }
+    }
     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) {
+      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 +99,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 +116,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..ade09d4 100644
--- a/centipede/runner_cmp_trace_test.cc
+++ b/centipede/runner_cmp_trace_test.cc
@@ -16,6 +16,7 @@
 
 #include <cstddef>
 #include <cstdint>
+#include <numeric>
 #include <vector>
 
 #include "gmock/gmock.h"
@@ -56,10 +57,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();
@@ -102,12 +103,12 @@
 
   constexpr uint8_t value0[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
   constexpr uint8_t value1[10] = {0, 9, 8, 7, 6, 5, 4, 3, 2, 1};
-  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};
+  uint8_t long_array[129];
+  std::iota(long_array, long_array + 129, 0);
   traceN.Capture(7, value0, value1);
   traceN.Capture(3, value0, value1);
   traceN.Capture(10, value0, value1);
-  traceN.Capture(20, long_array, long_array);  // will be trimmed to 16.
+  traceN.Capture(129, long_array, long_array);  // will be trimmed to 128.
   observed_pairs.clear();
   traceN.ForEachNonZero(callback);
   EXPECT_THAT(observed_pairs,
@@ -115,7 +116,7 @@
                   TwoArraysToByteVector(value0, value1, 10),
                   TwoArraysToByteVector(value0, value1, 7),
                   TwoArraysToByteVector(value0, value1, 3),
-                  TwoArraysToByteVector(long_array, long_array, 16)));
+                  TwoArraysToByteVector(long_array, long_array, 128)));
 }
 
 }  // namespace
diff --git a/centipede/runner_fork_server.cc b/centipede/runner_fork_server.cc
index 359128d..afd7bc2 100644
--- a/centipede/runner_fork_server.cc
+++ b/centipede/runner_fork_server.cc
@@ -209,6 +209,9 @@
   struct sigaction sigchld_act{};
   sigchld_act.sa_handler = [](int) {};
 
+  struct sigaction sigusr1_act{};
+  sigusr1_act.sa_handler = [](int) {};
+
   sigset_t server_sigset;
   if (sigprocmask(SIG_SETMASK, nullptr, &server_sigset) != 0) {
     Exit("###sigprocmask() failed to get the existing sigset\n");
@@ -222,6 +225,9 @@
   if (sigaddset(&server_sigset, SIGCHLD) != 0) {
     Exit("###sigaddset() failed to add SIGCHLD\n");
   }
+  if (sigaddset(&server_sigset, SIGUSR1) != 0) {
+    Exit("###sigaddset() failed to add SIGUSR1\n");
+  }
 
   sigset_t wait_sigset;
   if (sigemptyset(&wait_sigset) != 0) {
@@ -236,10 +242,14 @@
   if (sigaddset(&wait_sigset, SIGCHLD) != 0) {
     Exit("###sigaddset() failed to add SIGCHLD to the wait sigset\n");
   }
+  if (sigaddset(&wait_sigset, SIGUSR1) != 0) {
+    Exit("###sigaddset() failed to add SIGUSR1 to the wait sigset\n");
+  }
 
   struct sigaction old_sigint_act{};
   struct sigaction old_sigterm_act{};
   struct sigaction old_sigchld_act{};
+  struct sigaction old_sigusr1_act{};
   sigset_t old_sigset;
   bool to_restore_signal_handling = false;
   // Loop.
@@ -258,7 +268,7 @@
           Exit("###sigpending() failed\n");
         }
         if (sigismember(&pending, SIGINT) || sigismember(&pending, SIGTERM) ||
-            sigismember(&pending, SIGCHLD)) {
+            sigismember(&pending, SIGCHLD) || sigismember(&pending, SIGUSR1)) {
           int unused_sig;
           if (sigwait(&wait_sigset, &unused_sig) != 0) {
             Exit("###sigwait() failed\n");
@@ -276,6 +286,9 @@
       if (sigaction(SIGCHLD, &old_sigchld_act, nullptr) != 0) {
         Exit("###sigaction failed on SIGCHLD for the child");
       }
+      if (sigaction(SIGUSR1, &old_sigusr1_act, nullptr) != 0) {
+        Exit("###sigaction failed on SIGUSR1 for the child");
+      }
       if (sigprocmask(SIG_SETMASK, &old_sigset, nullptr) != 0) {
         Exit("###sigprocmask() failed to restore the previous sigset\n");
       }
@@ -303,6 +316,9 @@
     if (sigaction(SIGCHLD, &sigchld_act, &old_sigchld_act) != 0) {
       Exit("###sigaction failed on SIGCHLD for the fork server");
     }
+    if (sigaction(SIGUSR1, &sigusr1_act, &old_sigusr1_act) != 0) {
+      Exit("###sigaction failed on SIGUSR1 for the fork server");
+    }
     if (sigprocmask(SIG_SETMASK, &server_sigset, &old_sigset) != 0) {
       Exit("###sigprocmask() failed to set the fork server sigset\n");
     }
@@ -335,6 +351,9 @@
       } else if (sig == SIGTERM) {
         Log("###Got SIGTERM - forwarding to the child\n");
         kill(pid, SIGTERM);
+      } else if (sig == SIGUSR1) {
+        Log("###Got SIGUSR1 - sending SIGKILL to the child\n");
+        kill(pid, SIGKILL);
       } else if (sig == SIGCHLD) {
         Log("###Got SIGCHLD - reaping the child\n");
         const pid_t ret = waitpid(pid, &status, WNOHANG);
diff --git a/centipede/runner_interface.h b/centipede/runner_interface.h
index 09e2bbd..c622daf 100644
--- a/centipede/runner_interface.h
+++ b/centipede/runner_interface.h
@@ -25,7 +25,8 @@
 #include <vector>
 
 #include "absl/base/nullability.h"
-#include "./centipede/mutation_input.h"
+#include "absl/types/span.h"
+#include "./centipede/mutation_data.h"
 #include "./common/defs.h"
 
 // Typedefs for the libFuzzer API, https://llvm.org/docs/LibFuzzer.html
@@ -153,9 +154,9 @@
   //
   // TODO(xinhaoyuan): Consider supporting only_shrink to speed up
   // input shrinking.
-  virtual bool Mutate(const std::vector<MutationInputRef> &inputs,
+  virtual bool Mutate(absl::Span<const MutationInputRef> inputs,
                       size_t num_mutants,
-                      std::function<void(ByteSpan)> new_mutant_callback);
+                      std::function<void(MutantRef)> new_mutant_callback);
   virtual ~RunnerCallbacks() = default;
 };
 
diff --git a/centipede/runner_request.cc b/centipede/runner_request.cc
index 7d286d3..3cdfbad 100644
--- a/centipede/runner_request.cc
+++ b/centipede/runner_request.cc
@@ -17,8 +17,9 @@
 #include <cstring>
 #include <vector>
 
+#include "absl/types/span.h"
 #include "./centipede/execution_metadata.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/shared_memory_blob_sequence.h"
 #include "./common/defs.h"
 
@@ -37,8 +38,8 @@
 };
 
 // Writes `inputs` to `blobseq`, returns the number of inputs written.
-static size_t WriteInputs(const std::vector<ByteArray> &inputs,
-                          BlobSequence &blobseq) {
+static size_t WriteInputs(absl::Span<const ByteSpan> inputs,
+                          BlobSequence& blobseq) {
   size_t num_inputs = inputs.size();
   if (!blobseq.Write(kTagNumInputs, num_inputs)) return 0;
   size_t result = 0;
@@ -59,8 +60,8 @@
 }
 
 // Similar to above, but for mutation inputs.
-static size_t WriteInputs(const std::vector<MutationInputRef> &inputs,
-                          BlobSequence &blobseq) {
+static size_t WriteInputs(absl::Span<const MutationInputRef> inputs,
+                          BlobSequence& blobseq) {
   size_t num_inputs = inputs.size();
   if (!blobseq.Write(kTagNumInputs, num_inputs)) return 0;
   size_t result = 0;
@@ -75,15 +76,15 @@
 
 }  // namespace
 
-size_t RequestExecution(const std::vector<ByteArray> &inputs,
-                        BlobSequence &blobseq) {
+size_t RequestExecution(absl::Span<const ByteSpan> inputs,
+                        BlobSequence& blobseq) {
   if (!blobseq.Write({kTagExecution, 0, nullptr})) return 0;
   return WriteInputs(inputs, blobseq);
 }
 
 size_t RequestMutation(size_t num_mutants,
-                       const std::vector<MutationInputRef> &inputs,
-                       BlobSequence &blobseq) {
+                       absl::Span<const MutationInputRef> inputs,
+                       BlobSequence& blobseq) {
   if (!blobseq.Write({kTagMutation, 0, nullptr})) return 0;
   if (!blobseq.Write(kTagNumMutants, num_mutants)) return 0;
   return WriteInputs(inputs, blobseq);
diff --git a/centipede/runner_request.h b/centipede/runner_request.h
index 63b90a2..f1d7a5b 100644
--- a/centipede/runner_request.h
+++ b/centipede/runner_request.h
@@ -20,8 +20,9 @@
 #include <cstddef>
 #include <vector>
 
+#include "absl/types/span.h"
 #include "./centipede/execution_metadata.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/shared_memory_blob_sequence.h"
 #include "./common/defs.h"
 
@@ -35,14 +36,14 @@
 
 // Sends a request (via `blobseq`) to execute `inputs`.
 // Returns the number of sent inputs, which would normally be inputs.size().
-size_t RequestExecution(const std::vector<ByteArray> &inputs,
-                        BlobSequence &blobseq);
+size_t RequestExecution(absl::Span<const ByteSpan> inputs,
+                        BlobSequence& blobseq);
 
 // Sends a request (via `blobseq`) to compute `num_mutants` mutants of `inputs`.
 // Returns the number of sent inputs, which would normally be inputs.size().
 size_t RequestMutation(size_t num_mutants,
-                       const std::vector<MutationInputRef> &inputs,
-                       BlobSequence &blobseq);
+                       absl::Span<const MutationInputRef> inputs,
+                       BlobSequence& blobseq);
 
 // Returns whether `blob` indicates an execution request.
 bool IsExecutionRequest(Blob blob);
diff --git a/centipede/runner_result.cc b/centipede/runner_result.cc
index 3b726e7..07b7810 100644
--- a/centipede/runner_result.cc
+++ b/centipede/runner_result.cc
@@ -22,6 +22,7 @@
 
 #include "./centipede/execution_metadata.h"
 #include "./centipede/feature.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/shared_memory_blob_sequence.h"
 #include "./common/defs.h"
 
@@ -44,6 +45,7 @@
 
   // Mutation result tags.
   kTagHasCustomMutator,
+  kTagMutantOrigin,
   kTagMutant,
 };
 
@@ -185,8 +187,12 @@
        reinterpret_cast<const uint8_t *>(&has_custom_mutator)});
 }
 
-bool MutationResult::WriteMutant(ByteSpan mutant, BlobSequence &blobseq) {
-  return blobseq.Write({kTagMutant, mutant.size(), mutant.data()});
+bool MutationResult::WriteMutant(MutantRef mutant, BlobSequence& blobseq) {
+  if (!blobseq.Write({kTagMutantOrigin, sizeof(mutant.origin),
+                      reinterpret_cast<const uint8_t*>(&mutant.origin)})) {
+    return false;
+  }
+  return blobseq.Write({kTagMutant, mutant.data.size(), mutant.data.data()});
 }
 
 bool MutationResult::Read(size_t num_mutants, BlobSequence &blobseq) {
@@ -199,10 +205,17 @@
   mutants_.clear();
   mutants_.reserve(num_mutants);
   for (size_t i = 0; i < num_mutants; ++i) {
+    size_t origin = Mutant::kOriginNone;
+    {
+      const Blob blob = blobseq.Read();
+      if (blob.tag != kTagMutantOrigin) return false;
+      if (blob.size != sizeof(origin)) return false;
+      std::memcpy(&origin, blob.data, sizeof(origin));
+    }
     const Blob blob = blobseq.Read();
     if (blob.tag != kTagMutant) return false;
     if (blob.size == 0) break;
-    mutants_.emplace_back(blob.data, blob.data + blob.size);
+    mutants_.push_back({ByteArray{blob.data, blob.data + blob.size}, origin});
   }
   return true;
 }
diff --git a/centipede/runner_result.h b/centipede/runner_result.h
index 1b94f31..8266103 100644
--- a/centipede/runner_result.h
+++ b/centipede/runner_result.h
@@ -25,6 +25,7 @@
 
 #include "./centipede/execution_metadata.h"
 #include "./centipede/feature.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/shared_memory_blob_sequence.h"
 #include "./common/defs.h"
 
@@ -217,7 +218,7 @@
                                     BlobSequence& blobseq);
 
   // Writes one mutant to `blobseq`. Returns true iff successful.
-  static bool WriteMutant(ByteSpan mutant, BlobSequence& blobseq);
+  static bool WriteMutant(MutantRef mutant, BlobSequence& blobseq);
 
   // Reads whether the target has a custom mutator, and if so, reads at most
   // `num_mutants` mutants from `blobseq`. Returns true iff successful.
@@ -227,13 +228,13 @@
   int exit_code() const { return exit_code_; }
   int& exit_code() { return exit_code_; }
   bool has_custom_mutator() const { return has_custom_mutator_; }
-  const std::vector<ByteArray>& mutants() const& { return mutants_; }
-  std::vector<ByteArray>&& mutants() && { return std::move(mutants_); }
+  const std::vector<Mutant>& mutants() const& { return mutants_; }
+  std::vector<Mutant>&& mutants() && { return std::move(mutants_); }
 
  private:
   int exit_code_ = EXIT_SUCCESS;
   bool has_custom_mutator_ = false;
-  std::vector<ByteArray> mutants_;
+  std::vector<Mutant> mutants_;
 };
 
 }  // namespace fuzztest::internal
diff --git a/centipede/runner_result_test.cc b/centipede/runner_result_test.cc
index 864401a..20ce433 100644
--- a/centipede/runner_result_test.cc
+++ b/centipede/runner_result_test.cc
@@ -29,6 +29,7 @@
 #include "gtest/gtest.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/feature.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/shared_memory_blob_sequence.h"
 #include "./common/defs.h"
 #include "./common/test_util.h"
@@ -213,18 +214,18 @@
 
   // Write a mutation result.
   ASSERT_TRUE(MutationResult::WriteHasCustomMutator(true, blobseq));
-  ASSERT_TRUE(MutationResult::WriteMutant({1, 2, 3}, blobseq));
-  ASSERT_TRUE(MutationResult::WriteMutant({4, 5, 6}, blobseq));
-  ASSERT_TRUE(MutationResult::WriteMutant({7, 8, 9}, blobseq));
+  ASSERT_TRUE(MutationResult::WriteMutant(MutantRef{{1, 2, 3}, 3}, blobseq));
+  ASSERT_TRUE(MutationResult::WriteMutant(MutantRef{{4, 5, 6}, 2}, blobseq));
+  ASSERT_TRUE(MutationResult::WriteMutant(MutantRef{{7, 8, 9}, 1}, blobseq));
   blobseq.Reset();
 
   MutationResult mutation_result;
   ASSERT_TRUE(mutation_result.Read(3, blobseq));
 
   EXPECT_TRUE(mutation_result.has_custom_mutator());
-  EXPECT_THAT(
-      mutation_result.mutants(),
-      ElementsAre(ByteArray{1, 2, 3}, ByteArray{4, 5, 6}, ByteArray{7, 8, 9}));
+  EXPECT_THAT(mutation_result.mutants(),
+              ElementsAre(Mutant{{1, 2, 3}, 3}, Mutant{{4, 5, 6}, 2},
+                          Mutant{{7, 8, 9}, 1}));
 }
 
 TEST(ExecutionResult, ReadResultSucceedsOnlyWithInputBegin) {
diff --git a/centipede/runner_utils.h b/centipede/runner_utils.h
index 20fa40e..71b3005 100644
--- a/centipede/runner_utils.h
+++ b/centipede/runner_utils.h
@@ -24,6 +24,10 @@
 
 #include "absl/base/nullability.h"
 
+// Use this attribute for functions that must not be instrumented even if
+// the library is built with sanitizers (asan, etc).
+#define FUZZTEST_NO_SANITIZE __attribute__((no_sanitize("all")))
+
 namespace fuzztest::internal {
 
 // If `condition` prints `error` and calls exit(1).
diff --git a/centipede/sancov_callbacks.cc b/centipede/sancov_callbacks.cc
index 7e7fd15..3e5d0c5 100644
--- a/centipede/sancov_callbacks.cc
+++ b/centipede/sancov_callbacks.cc
@@ -29,6 +29,7 @@
 #include "./centipede/pc_info.h"
 #include "./centipede/reverse_pc_table.h"
 #include "./centipede/runner_dl_info.h"
+#include "./centipede/runner_utils.h"
 #include "./centipede/sancov_state.h"
 
 namespace fuzztest::internal {
@@ -61,10 +62,6 @@
 // https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html.
 #define ENFORCE_INLINE __attribute__((always_inline)) inline
 
-// Use this attribute for functions that must not be instrumented even if
-// the runner is built with sanitizers (asan, etc).
-#define NO_SANITIZE __attribute__((no_sanitize("all")))
-
 // NOTE: Enforce inlining so that `__builtin_return_address` works.
 ENFORCE_INLINE static void TraceLoad(void *addr) {
   if (ABSL_PREDICT_FALSE(!tls.traced) ||
@@ -127,55 +124,65 @@
 //------------------------------------------------------------------------------
 
 extern "C" {
-NO_SANITIZE void __sanitizer_cov_load1(uint8_t *addr) { TraceLoad(addr); }
-NO_SANITIZE void __sanitizer_cov_load2(uint16_t *addr) { TraceLoad(addr); }
-NO_SANITIZE void __sanitizer_cov_load4(uint32_t *addr) { TraceLoad(addr); }
-NO_SANITIZE void __sanitizer_cov_load8(uint64_t *addr) { TraceLoad(addr); }
-NO_SANITIZE void __sanitizer_cov_load16(__uint128_t *addr) { TraceLoad(addr); }
+FUZZTEST_NO_SANITIZE void __sanitizer_cov_load1(uint8_t* addr) {
+  TraceLoad(addr);
+}
+FUZZTEST_NO_SANITIZE void __sanitizer_cov_load2(uint16_t* addr) {
+  TraceLoad(addr);
+}
+FUZZTEST_NO_SANITIZE void __sanitizer_cov_load4(uint32_t* addr) {
+  TraceLoad(addr);
+}
+FUZZTEST_NO_SANITIZE void __sanitizer_cov_load8(uint64_t* addr) {
+  TraceLoad(addr);
+}
+FUZZTEST_NO_SANITIZE void __sanitizer_cov_load16(__uint128_t* addr) {
+  TraceLoad(addr);
+}
 
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_const_cmp1(uint8_t Arg1, uint8_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
            reinterpret_cast<uintptr_t>(__builtin_return_address(0)));
 }
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_const_cmp2(uint16_t Arg1, uint16_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
            reinterpret_cast<uintptr_t>(__builtin_return_address(0)));
 }
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_const_cmp4(uint32_t Arg1, uint32_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
            reinterpret_cast<uintptr_t>(__builtin_return_address(0)));
 }
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_const_cmp8(uint64_t Arg1, uint64_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
            reinterpret_cast<uintptr_t>(__builtin_return_address(0)));
 }
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_cmp1(uint8_t Arg1, uint8_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
            reinterpret_cast<uintptr_t>(__builtin_return_address(0)));
 }
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_cmp2(uint16_t Arg1, uint16_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
            reinterpret_cast<uintptr_t>(__builtin_return_address(0)));
 }
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_cmp4(uint32_t Arg1, uint32_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
            reinterpret_cast<uintptr_t>(__builtin_return_address(0)));
 }
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   TraceCmp(Arg1, Arg2,
@@ -188,7 +195,7 @@
 // LLVM/libFuzzer implementation).
 //
 // Source: https://clang.llvm.org/docs/SanitizerCoverage.html
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_switch(uint64_t val, uint64_t* cases) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   const auto num_cases = cases[0];
@@ -262,6 +269,23 @@
   sancov_state->path_feature_set.set(hash);
 }
 
+// Updates the lowest stack using the current stack pointer `sp` and checks
+// against the stack limit if needed.
+static ENFORCE_INLINE void UpdateLowestStackAndCheckLimit(uintptr_t sp) {
+  // It should be rare for the stack pointer to be valid and exceed the previous
+  // record.
+  if (ABSL_PREDICT_FALSE(sp < tls.lowest_sp && sp <= tls.top_frame_sp &&
+                         sp >= tls.stack_region_low &&
+                         tls.stack_region_low > 0)) {
+    tls.lowest_sp = sp;
+    if (fuzztest::internal::CheckStackLimit == nullptr) {
+      return;
+    }
+    fuzztest::internal::CheckStackLimit(tls.top_frame_sp - sp,
+                                        /*is_current_stack=*/true);
+  }
+}
+
 // Handles one observed PC.
 // `normalized_pc` is an integer representation of PC that is stable between
 // the executions.
@@ -278,18 +302,7 @@
 
   if (pc_guard.is_function_entry) {
     uintptr_t sp = reinterpret_cast<uintptr_t>(__builtin_frame_address(0));
-    // It should be rare for the stack depth to exceed the previous record.
-    if (__builtin_expect(
-            sp < tls.lowest_sp &&
-                // And ignore the stack pointer when it is not in the known
-                // region (e.g. for signal handling with an alternative stack).
-                (tls.stack_region_low == 0 || sp >= tls.stack_region_low),
-            0)) {
-      tls.lowest_sp = sp;
-      if (fuzztest::internal::CheckStackLimit != nullptr) {
-        fuzztest::internal::CheckStackLimit(sp);
-      }
-    }
+    UpdateLowestStackAndCheckLimit(sp);
     if (sancov_state->flags.callstack_level != 0) {
       tls.call_stack.OnFunctionEntry(pc_guard.pc_index, sp);
       sancov_state->callstack_set.set(tls.call_stack.Hash());
@@ -361,6 +374,7 @@
 // This instrumentation is redundant if other instrumentation
 // (e.g. trace-pc-guard) is available, but GCC as of 2022-04 only supports
 // this variant.
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_pc() {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   uintptr_t pc = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
@@ -386,7 +400,7 @@
 }
 
 // This function is called on every instrumented edge.
-NO_SANITIZE
+FUZZTEST_NO_SANITIZE
 void __sanitizer_cov_trace_pc_guard(PCGuard *absl_nonnull guard) {
   if (ABSL_PREDICT_FALSE(!tls.traced)) return;
   // This function may be called very early during the DSO initialization,
@@ -397,4 +411,12 @@
   HandleOnePc(*guard);
 }
 
+// This callback is called by the compiler on every function entry when enabled.
+// https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-stack-depth
+FUZZTEST_NO_SANITIZE void __sanitizer_cov_stack_depth() {
+  if (ABSL_PREDICT_FALSE(!tls.traced)) return;
+  UpdateLowestStackAndCheckLimit(
+      reinterpret_cast<uintptr_t>(__builtin_frame_address(0)));
+}
+
 }  // extern "C"
diff --git a/centipede/sancov_interceptors.cc b/centipede/sancov_interceptors.cc
index 304d949..cf1e9ac 100644
--- a/centipede/sancov_interceptors.cc
+++ b/centipede/sancov_interceptors.cc
@@ -22,6 +22,7 @@
 
 #include "absl/base/nullability.h"
 #include "absl/base/optimization.h"
+#include "./centipede/runner_utils.h"
 #include "./centipede/sancov_state.h"
 
 using fuzztest::internal::tls;
@@ -30,7 +31,6 @@
 // before or during the sanitizer initialization. Instead, we check if the
 // current thread is marked as started by the runner as the proxy of sanitizier
 // initialization. If not, we skip the interception logic.
-#define NO_SANITIZE __attribute__((no_sanitize("all")))
 
 namespace {
 
@@ -131,8 +131,8 @@
 
 // Fallback for the case *cmp_orig is null.
 // Will be executed several times at process startup, if at all.
-static NO_SANITIZE int memcmp_fallback(const void *s1, const void *s2,
-                                       size_t n) {
+static FUZZTEST_NO_SANITIZE int memcmp_fallback(const void* s1, const void* s2,
+                                                size_t n) {
   const auto *p1 = static_cast<const uint8_t *>(s1);
   const auto *p2 = static_cast<const uint8_t *>(s2);
   for (size_t i = 0; i < n; ++i) {
@@ -143,8 +143,8 @@
 }
 
 // Fallback for case insensitive comparison.
-static NO_SANITIZE int memcasecmp_fallback(const void* s1, const void* s2,
-                                           size_t n) {
+static FUZZTEST_NO_SANITIZE int memcasecmp_fallback(const void* s1,
+                                                    const void* s2, size_t n) {
   static uint8_t to_lower[256];
   [[maybe_unused]] static bool initialize_to_lower = [&] {
     for (size_t i = 0; i < sizeof(to_lower); ++i) {
@@ -166,7 +166,8 @@
 
 // memcmp interceptor.
 // Calls the real memcmp() and possibly modifies state.cmp_feature_set.
-extern "C" NO_SANITIZE int memcmp(const void *s1, const void *s2, size_t n) {
+extern "C" FUZZTEST_NO_SANITIZE int memcmp(const void* s1, const void* s2,
+                                           size_t n) {
   const int result =
       memcmp_orig ? memcmp_orig(s1, s2, n) : memcmp_fallback(s1, s2, n);
   if (ABSL_PREDICT_FALSE(!tls.traced)) {
@@ -183,7 +184,7 @@
 
 // strcmp interceptor.
 // Calls the real strcmp() and possibly modifies state.cmp_feature_set.
-extern "C" NO_SANITIZE int strcmp(const char *s1, const char *s2) {
+extern "C" FUZZTEST_NO_SANITIZE int strcmp(const char* s1, const char* s2) {
   // Find the length of the shorter string, as this determines the actual number
   // of bytes that are compared. Note that this is needed even if we call
   // `strcmp_orig` because we're passing it to `TraceMemCmp()`.
@@ -205,7 +206,8 @@
 
 // strncmp interceptor.
 // Calls the real strncmp() and possibly modifies state.cmp_feature_set.
-extern "C" NO_SANITIZE int strncmp(const char *s1, const char *s2, size_t n) {
+extern "C" FUZZTEST_NO_SANITIZE int strncmp(const char* s1, const char* s2,
+                                            size_t n) {
   // Find the length of the shorter string, as this determines the actual number
   // of bytes that are compared. Note that this is needed even if we call
   // `strncmp_orig` because we're passing it to `TraceMemCmp()`.
@@ -228,7 +230,7 @@
 
 // strcasecmp interceptor.
 // Calls the real strcasecmp() and possibly modifies state.cmp_feature_set.
-extern "C" NO_SANITIZE int strcasecmp(const char* s1, const char* s2) {
+extern "C" FUZZTEST_NO_SANITIZE int strcasecmp(const char* s1, const char* s2) {
   // Find the length of the shorter string, as this determines the actual number
   // of bytes that are compared. Note that this is needed even if we call
   // `strcasecmp_orig` because we're passing it to `TraceMemCmp()`.
@@ -251,8 +253,8 @@
 
 // strncasecmp interceptor.
 // Calls the real strncasecmp() and possibly modifies state.cmp_feature_set.
-extern "C" NO_SANITIZE int strncasecmp(const char* s1, const char* s2,
-                                       size_t n) {
+extern "C" FUZZTEST_NO_SANITIZE int strncasecmp(const char* s1, const char* s2,
+                                                size_t n) {
   // Find the length of the shorter string, as this determines the actual number
   // of bytes that are compared. Note that this is needed even if we call
   // `strncasecmp_orig` because we're passing it to `TraceMemCmp()`.
diff --git a/centipede/sancov_state.cc b/centipede/sancov_state.cc
index 25bcd73..19570d6 100644
--- a/centipede/sancov_state.cc
+++ b/centipede/sancov_state.cc
@@ -38,6 +38,10 @@
 __attribute__((weak)) extern fuzztest::internal::feature_t
     __stop___centipede_extra_features;
 
+// May be updated by sancov with -fsanitize-coverage=stack-depth.
+__attribute__((visibility("default")))
+__attribute__((weak)) thread_local uintptr_t __sancov_lowest_stack;
+
 namespace fuzztest::internal {
 
 ExplicitLifetime<SancovState> sancov_state;
@@ -56,9 +60,8 @@
 //
 // Must not be sanitized because sanitizers may trigger this on unsanitized
 // data, causing false positives and nested failures.
-__attribute__((no_sanitize("all"))) size_t LengthOfCommonPrefix(const void* s1,
-                                                                const void* s2,
-                                                                size_t n) {
+FUZZTEST_NO_SANITIZE size_t LengthOfCommonPrefix(const void* s1, const void* s2,
+                                                 size_t n) {
   const auto *p1 = static_cast<const uint8_t *>(s1);
   const auto *p2 = static_cast<const uint8_t *>(s2);
   static constexpr size_t kMaxLen = feature_domains::kCMPScoreBitmask;
@@ -122,7 +125,8 @@
   // Always trace threads by default. Internal threads that do not want tracing
   // will set this to false later.
   tls.traced = true;
-  tls.lowest_sp = tls.top_frame_sp =
+  tls.sancov_lowest_sp = &__sancov_lowest_stack;
+  *tls.sancov_lowest_sp = tls.lowest_sp = tls.top_frame_sp =
       reinterpret_cast<uintptr_t>(__builtin_frame_address(0));
   tls.stack_region_low = GetCurrentThreadStackRegionLow();
   if (tls.stack_region_low == 0) {
@@ -142,6 +146,13 @@
 void ThreadLocalSancovState::OnThreadStop() {
   tls.traced = false;
   LockGuard lock(sancov_state->tls_list_mu);
+  const size_t sancov_lowest_sp = *tls.sancov_lowest_sp;
+  tls.sancov_lowest_sp = nullptr;
+  if (sancov_lowest_sp <= tls.top_frame_sp &&
+      sancov_lowest_sp < tls.lowest_sp &&
+      sancov_lowest_sp >= tls.stack_region_low && tls.stack_region_low > 0) {
+    tls.lowest_sp = sancov_lowest_sp;
+  }
   // Remove myself from state.tls_list. The list never
   // becomes empty because the main thread does not call OnThreadStop().
   if (&tls == sancov_state->tls_list) {
@@ -297,13 +308,17 @@
 
 void CleanUpSancovTls() {
   sancov_state->CleanUpDetachedTls();
-  if (sancov_state->flags.path_level != 0) {
-    sancov_state->ForEachTls([](ThreadLocalSancovState& tls) {
+  sancov_state->ForEachTls([](ThreadLocalSancovState& tls) {
+    if (sancov_state->flags.path_level != 0) {
       tls.path_ring_buffer.Reset(sancov_state->flags.path_level);
+    }
+    if (sancov_state->flags.callstack_level != 0) {
       tls.call_stack.Reset(sancov_state->flags.callstack_level);
-      tls.lowest_sp = tls.top_frame_sp;
-    });
-  }
+    }
+    RunnerCheck(tls.sancov_lowest_sp != nullptr,
+                "sancov_lowest_sp is null for a live thread");
+    *tls.sancov_lowest_sp = tls.lowest_sp = tls.top_frame_sp;
+  });
 }
 
 void PrepareSancov(bool full_clear) {
@@ -439,10 +454,23 @@
 
   // Iterate all threads and get features from TLS data.
   sancov_state->ForEachTls([&feature_handler](ThreadLocalSancovState& tls) {
+    RunnerCheck(tls.top_frame_sp >= tls.lowest_sp,
+                "bad values of tls.top_frame_sp and tls.lowest_sp");
+    uintptr_t lowest_sp = tls.lowest_sp;
+    if (tls.sancov_lowest_sp != nullptr) {
+      const uintptr_t sancov_lowest_sp = *tls.sancov_lowest_sp;
+      if (sancov_lowest_sp <= tls.top_frame_sp &&
+          sancov_lowest_sp <= lowest_sp &&
+          sancov_lowest_sp >= tls.stack_region_low &&
+          tls.stack_region_low > 0) {
+        lowest_sp = sancov_lowest_sp;
+      }
+    }
+    const size_t sp_diff = tls.top_frame_sp - lowest_sp;
+    if (CheckStackLimit != nullptr) {
+      CheckStackLimit(sp_diff, /*is_current_stack=*/false);
+    }
     if (sancov_state->flags.callstack_level != 0) {
-      RunnerCheck(tls.top_frame_sp >= tls.lowest_sp,
-                  "bad values of tls.top_frame_sp and tls.lowest_sp");
-      size_t sp_diff = tls.top_frame_sp - tls.lowest_sp;
       feature_handler(feature_domains::kCallStack.ConvertToMe(sp_diff));
     }
   });
diff --git a/centipede/sancov_state.h b/centipede/sancov_state.h
index 3afb6c4..85407e3 100644
--- a/centipede/sancov_state.h
+++ b/centipede/sancov_state.h
@@ -110,8 +110,22 @@
   uintptr_t top_frame_sp;
   // The lower bound of the stack region of this thread. 0 means unknown.
   uintptr_t stack_region_low;
-  // Lowest observed value of SP.
+
+  // `lowest_sp` and `*sancov_lowest_sp` are read and written by both
+  // the current thread and the sancov processing thread. Thus race conditions
+  // may happen. We don't use mutex/atomic because they are slow (and it is not
+  // possible on sancov_lowest_sp). Instead we let race conditions happen and
+  // tolerate them with the best effort. An SP value is valid if and only if
+  // `stack_region_low <= SP <= top_frame_sp && stack_region_low > 0`.
+  // This should reject most bad values caused by race conditions.
+  //
+  // Lowest sp observed by the this library.
   uintptr_t lowest_sp;
+  // A pointer to the lowest sp updated by sancov (if enabled). It is constant
+  // and non-null when the thread is alive, and set to null when the thread
+  // is terminated, guarded by `state.tls_list_mu`. So no race conditions on
+  // the pointer itself.
+  uintptr_t* sancov_lowest_sp;
 
   // The (imprecise) call stack is updated by the PC callback.
   CallStack<> call_stack;
@@ -296,8 +310,10 @@
 // Gets the execution metadata gathered in `PostProcessSancov`.
 const ExecutionMetadata& SanCovRuntimeGetExecutionMetadata();
 
-// Check for stack limit for the stack pointer `sp` in the current thread.
-__attribute__((weak)) void CheckStackLimit(uintptr_t sp);
+// Check for stack limit for `stack_usage`, with `is_current_stack` set if it
+// is for the current calling stack.
+__attribute__((weak)) void CheckStackLimit(size_t stack_usage,
+                                           bool is_current_stack);
 
 extern ExplicitLifetime<SancovState> sancov_state;
 extern __thread ThreadLocalSancovState tls;
diff --git a/centipede/test_coverage_util.cc b/centipede/test_coverage_util.cc
index 2602a58..7a995a0 100644
--- a/centipede/test_coverage_util.cc
+++ b/centipede/test_coverage_util.cc
@@ -18,6 +18,7 @@
 #include <string>
 #include <vector>
 
+#include "absl/types/span.h"
 #include "./centipede/corpus.h"
 #include "./centipede/environment.h"
 #include "./centipede/feature.h"
@@ -41,7 +42,9 @@
   }
   BatchResult batch_result;
   // Run.
-  CBs.Execute(env.binary, byte_array_inputs, batch_result);
+  std::vector<ByteSpan> byte_span_inputs(byte_array_inputs.begin(),
+                                         byte_array_inputs.end());
+  CBs.Execute(env.binary, byte_span_inputs, batch_result);
 
   // Repackage execution results into a vector of CorpusRecords.
   std::vector<CorpusRecord> corpus_records;
diff --git a/centipede/test_coverage_util.h b/centipede/test_coverage_util.h
index c06a9bf..a338524 100644
--- a/centipede/test_coverage_util.h
+++ b/centipede/test_coverage_util.h
@@ -21,11 +21,12 @@
 #include <string_view>
 #include <vector>
 
+#include "absl/types/span.h"
 #include "./centipede/centipede_callbacks.h"
 #include "./centipede/corpus.h"
 #include "./centipede/environment.h"
 #include "./centipede/feature.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_result.h"
 #include "./common/defs.h"
 namespace fuzztest::internal {
@@ -43,15 +44,15 @@
 class TestCallbacks : public CentipedeCallbacks {
  public:
   explicit TestCallbacks(const Environment &env) : CentipedeCallbacks(env) {}
-  bool Execute(std::string_view binary, const std::vector<ByteArray> &inputs,
-               BatchResult &batch_result) override {
+  bool Execute(std::string_view binary, absl::Span<const ByteSpan> inputs,
+               BatchResult& batch_result) override {
     int result =
         ExecuteCentipedeSancovBinaryWithShmem(binary, inputs, batch_result);
     FUZZTEST_CHECK_EQ(EXIT_SUCCESS, result);
     return true;
   }
-  std::vector<ByteArray> Mutate(const std::vector<MutationInputRef> &inputs,
-                                size_t num_mutants) override {
+  std::vector<Mutant> Mutate(absl::Span<const MutationInputRef> inputs,
+                             size_t num_mutants) override {
     return {};
   }
 };
diff --git a/centipede/testing/BUILD b/centipede/testing/BUILD
index e127773..e40ae58 100644
--- a/centipede/testing/BUILD
+++ b/centipede/testing/BUILD
@@ -84,8 +84,9 @@
         "@abseil-cpp//absl/base:nullability",
         "@abseil-cpp//absl/flags:flag",
         "@abseil-cpp//absl/flags:parse",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//centipede:centipede_runner_no_main",
-        "@com_google_fuzztest//centipede:mutation_input",
+        "@com_google_fuzztest//centipede:mutation_data",
         "@com_google_fuzztest//common:defs",
     ],
 )
@@ -168,6 +169,7 @@
     ],
     deps = [
         "@abseil-cpp//absl/base:nullability",
+        "@abseil-cpp//absl/types:span",
         "@com_google_fuzztest//centipede:centipede_runner_no_main",
         "@com_google_fuzztest//common:defs",
     ],
diff --git a/centipede/testing/async_failing_target.cc b/centipede/testing/async_failing_target.cc
index e66ac8b..a3fc7dd 100644
--- a/centipede/testing/async_failing_target.cc
+++ b/centipede/testing/async_failing_target.cc
@@ -15,9 +15,9 @@
 #include <cstdio>
 #include <cstdlib>
 #include <functional>
-#include <vector>
 
 #include "absl/base/nullability.h"
+#include "absl/types/span.h"
 #include "./centipede/runner_interface.h"
 #include "./common/defs.h"
 
@@ -31,9 +31,9 @@
     return true;
   }
 
-  bool Mutate(const std::vector<fuzztest::internal::MutationInputRef>& inputs,
+  bool Mutate(absl::Span<const fuzztest::internal::MutationInputRef> inputs,
               size_t num_mutants,
-              std::function<void(fuzztest::internal::ByteSpan)>
+              std::function<void(fuzztest::internal::MutantRef)>
                   new_mutant_callback) override {
     if (to_fail_in_mutation) {
       fprintf(stderr, "Fail in mutation\n");
diff --git a/centipede/testing/fuzz_target_with_custom_mutator.cc b/centipede/testing/fuzz_target_with_custom_mutator.cc
index a95dbf8..e6c28af 100644
--- a/centipede/testing/fuzz_target_with_custom_mutator.cc
+++ b/centipede/testing/fuzz_target_with_custom_mutator.cc
@@ -14,12 +14,12 @@
 
 #include <cstdlib>
 #include <functional>
-#include <vector>
 
 #include "absl/base/nullability.h"
 #include "absl/flags/flag.h"
 #include "absl/flags/parse.h"
-#include "./centipede/mutation_input.h"
+#include "absl/types/span.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_interface.h"
 #include "./common/defs.h"
 
@@ -28,6 +28,7 @@
           "failure.");
 
 using fuzztest::internal::ByteSpan;
+using fuzztest::internal::MutantRef;
 
 class CustomMutatorRunnerCallbacks
     : public fuzztest::internal::RunnerCallbacks {
@@ -36,14 +37,12 @@
 
   bool HasCustomMutator() const override { return true; }
 
-  bool Mutate(const std::vector<fuzztest::internal::MutationInputRef>& inputs,
+  bool Mutate(absl::Span<const fuzztest::internal::MutationInputRef> inputs,
               size_t num_mutants,
-              std::function<void(ByteSpan)> new_mutant_callback) override {
-    size_t i = 0;
-    for (fuzztest::internal::MutationInputRef input : inputs) {
-      if (i++ >= num_mutants) break;
+              std::function<void(MutantRef)> new_mutant_callback) override {
+    for (size_t i = 0; i < inputs.size() && i < num_mutants; ++i) {
       // Just return the original input as a mutant.
-      new_mutant_callback(input.data);
+      new_mutant_callback(MutantRef{inputs[i].data, i});
     }
     return true;
   }
diff --git a/centipede/util.cc b/centipede/util.cc
index 376d7b4..83da9e7 100644
--- a/centipede/util.cc
+++ b/centipede/util.cc
@@ -226,13 +226,11 @@
   return res;
 }
 
-ByteArray PackFeaturesAndHash(const ByteArray &data,
-                              const FeatureVec &features) {
+ByteArray PackFeaturesAndHash(ByteSpan data, const FeatureVec& features) {
   return PackFeaturesAndHashAsRawBytes(data, AsByteSpan(features));
 }
 
-ByteArray PackFeaturesAndHashAsRawBytes(const ByteArray &data,
-                                        ByteSpan features) {
+ByteArray PackFeaturesAndHashAsRawBytes(ByteSpan data, ByteSpan features) {
   ByteArray feature_bytes_with_hash(features.size() + kHashLen);
   auto hash = Hash(data);
   FUZZTEST_CHECK_EQ(hash.size(), kHashLen);
diff --git a/centipede/util.h b/centipede/util.h
index a34feda..ac5e963 100644
--- a/centipede/util.h
+++ b/centipede/util.h
@@ -140,12 +140,10 @@
 std::string ExtractHashFromArray(ByteArray &ba);
 
 // Pack {features, Hash(data)} into a byte array.
-ByteArray PackFeaturesAndHash(const ByteArray &data,
-                              const FeatureVec &features);
+ByteArray PackFeaturesAndHash(ByteSpan data, const FeatureVec& features);
 
 // Pack `features` and the hash of `data` directly from their raw data format.
-ByteArray PackFeaturesAndHashAsRawBytes(const ByteArray &data,
-                                        ByteSpan features);
+ByteArray PackFeaturesAndHashAsRawBytes(ByteSpan data, ByteSpan features);
 
 // Given a `blob` created by `PackFeaturesAndHash`, unpack the features into
 // `features` and return the hash.
diff --git a/centipede/weak_sancov_stubs.cc b/centipede/weak_sancov_stubs.cc
index c9bfa63..66f78a6 100644
--- a/centipede/weak_sancov_stubs.cc
+++ b/centipede/weak_sancov_stubs.cc
@@ -12,6 +12,8 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
+#include <cstdint>
+
 #define WEAK_SANCOV_DEF(return_type, name, ...)                           \
   extern "C" __attribute__((visibility("default"))) __attribute__((weak)) \
   return_type                                                             \
@@ -42,3 +44,7 @@
 WEAK_SANCOV_DEF(void, __sanitizer_cov_load4, void) {}
 WEAK_SANCOV_DEF(void, __sanitizer_cov_load8, void) {}
 WEAK_SANCOV_DEF(void, __sanitizer_cov_load16, void) {}
+
+WEAK_SANCOV_DEF(void, __sanitizer_cov_stack_depth, void) {}
+extern "C" __attribute__((visibility("default")))
+__attribute__((weak)) thread_local uintptr_t __sancov_lowest_stack;
diff --git a/common/remote_file.cc b/common/remote_file.cc
index b628ad6..a729e0c 100644
--- a/common/remote_file.cc
+++ b/common/remote_file.cc
@@ -30,8 +30,7 @@
 
 absl::Status RemoteFileAppend(RemoteFile *absl_nonnull f,
                               const std::string &contents) {
-  ByteArray contents_ba{contents.cbegin(), contents.cend()};
-  return RemoteFileAppend(f, contents_ba);
+  return RemoteFileAppend(f, AsByteSpan(contents));
 }
 
 absl::Status RemoteFileRead(RemoteFile *absl_nonnull f, std::string &contents) {
@@ -42,18 +41,11 @@
 }
 
 absl::Status RemoteFileSetContents(std::string_view path,
-                                   const ByteArray &contents) {
-  ASSIGN_OR_RETURN_IF_NOT_OK(RemoteFile * file, RemoteFileOpen(path, "w"));
-  if (file == nullptr) {
-    return absl::UnknownError(
-        "RemoteFileOpen returned an OK status but a nullptr RemoteFile*");
-  }
-  RETURN_IF_NOT_OK(RemoteFileAppend(file, contents));
-  return RemoteFileClose(file);
+                                   const std::string& contents) {
+  return RemoteFileSetContents(path, AsByteSpan(contents));
 }
 
-absl::Status RemoteFileSetContents(std::string_view path,
-                                   const std::string &contents) {
+absl::Status RemoteFileSetContents(std::string_view path, ByteSpan contents) {
   ASSIGN_OR_RETURN_IF_NOT_OK(RemoteFile * file, RemoteFileOpen(path, "w"));
   if (file == nullptr) {
     return absl::UnknownError(
diff --git a/common/remote_file.h b/common/remote_file.h
index e59b484..0b70444 100644
--- a/common/remote_file.h
+++ b/common/remote_file.h
@@ -74,13 +74,13 @@
 absl::Status RemoteFileSetWriteBufferSize(RemoteFile *absl_nonnull f,
                                           size_t size);
 
-// Appends bytes from 'ba' to 'f'.
-absl::Status RemoteFileAppend(RemoteFile *absl_nonnull f, const ByteArray &ba);
-
 // Appends characters from 'contents' to 'f'.
 absl::Status RemoteFileAppend(RemoteFile *absl_nonnull f,
                               const std::string &contents);
 
+// Appends bytes from 'contents' to 'f'.
+absl::Status RemoteFileAppend(RemoteFile* absl_nonnull f, ByteSpan contents);
+
 // Flushes the file's internal buffer. Some dynamic results of a running
 // pipeline are consumed by itself (e.g. shard cross-pollination) and can be
 // consumed by external processes (e.g. monitoring): for such files, call this
@@ -99,11 +99,10 @@
 
 // Sets the contents of the file at 'path' to 'contents'.
 absl::Status RemoteFileSetContents(std::string_view path,
-                                   const ByteArray &contents);
+                                   const std::string& contents);
 
 // Sets the contents of the file at 'path' to 'contents'.
-absl::Status RemoteFileSetContents(std::string_view path,
-                                   const std::string &contents);
+absl::Status RemoteFileSetContents(std::string_view path, ByteSpan contents);
 
 // Reads the contents of the file at 'path' into 'contents'.
 absl::Status RemoteFileGetContents(std::string_view path, ByteArray &contents);
diff --git a/common/remote_file_oss.cc b/common/remote_file_oss.cc
index fb6f23a..10299f6 100644
--- a/common/remote_file_oss.cc
+++ b/common/remote_file_oss.cc
@@ -90,11 +90,11 @@
     return absl::OkStatus();
   }
 
-  absl::Status Write(const ByteArray &ba) {
-    static constexpr auto elt_size = sizeof(ba[0]);
-    const auto elts_to_write = ba.size();
+  absl::Status Write(ByteSpan contents) {
+    static constexpr auto elt_size = sizeof(contents[0]);
+    const auto elts_to_write = contents.size();
     const auto elts_written =
-        std::fwrite(ba.data(), elt_size, elts_to_write, file_);
+        std::fwrite(contents.data(), elt_size, elts_to_write, file_);
     if (elts_written != elts_to_write) {
       return absl::UnknownError(absl::StrCat(
           "fwrite() wrote less elements that expected, wrote: ", elts_written,
@@ -327,8 +327,8 @@
   return static_cast<LocalRemoteFile *>(f)->SetWriteBufSize(size);
 }
 
-absl::Status RemoteFileAppend(RemoteFile *absl_nonnull f, const ByteArray &ba) {
-  return static_cast<LocalRemoteFile *>(f)->Write(ba);
+absl::Status RemoteFileAppend(RemoteFile* absl_nonnull f, ByteSpan contents) {
+  return static_cast<LocalRemoteFile*>(f)->Write(contents);
 }
 
 absl::Status RemoteFileFlush(RemoteFile *absl_nonnull f) {
diff --git a/fuzztest/BUILD b/fuzztest/BUILD
index c3bd226..fe241cd 100644
--- a/fuzztest/BUILD
+++ b/fuzztest/BUILD
@@ -171,6 +171,7 @@
         "@com_google_fuzztest//common:logging",
         "@com_google_fuzztest//fuzztest/internal:io",
         "@com_google_fuzztest//fuzztest/internal/domains:core_domains_impl",
+        "@com_google_fuzztest//fuzztest/internal/domains:lazy",
     ],
     alwayslink = True,
 )
diff --git a/fuzztest/CMakeLists.txt b/fuzztest/CMakeLists.txt
index 960b6e2..ecaf619 100644
--- a/fuzztest/CMakeLists.txt
+++ b/fuzztest/CMakeLists.txt
@@ -235,4 +235,5 @@
     fuzztest::common_logging
     fuzztest::io
     fuzztest::core_domains_impl
+    fuzztest::lazy
 )
diff --git a/fuzztest/internal/BUILD b/fuzztest/internal/BUILD
index 0ea46b8..c5d988a 100644
--- a/fuzztest/internal/BUILD
+++ b/fuzztest/internal/BUILD
@@ -79,7 +79,7 @@
         "@com_google_fuzztest//centipede:environment",
         "@com_google_fuzztest//centipede:execution_metadata",
         "@com_google_fuzztest//centipede:fuzztest_mutator",
-        "@com_google_fuzztest//centipede:mutation_input",
+        "@com_google_fuzztest//centipede:mutation_data",
         "@com_google_fuzztest//centipede:runner_result",
         "@com_google_fuzztest//centipede:stop",
         "@com_google_fuzztest//centipede:workdir",
diff --git a/fuzztest/internal/centipede_adaptor.cc b/fuzztest/internal/centipede_adaptor.cc
index 9bb0256..71df38d 100644
--- a/fuzztest/internal/centipede_adaptor.cc
+++ b/fuzztest/internal/centipede_adaptor.cc
@@ -70,7 +70,7 @@
 #include "./centipede/environment.h"
 #include "./centipede/execution_metadata.h"
 #include "./centipede/fuzztest_mutator.h"
-#include "./centipede/mutation_input.h"
+#include "./centipede/mutation_data.h"
 #include "./centipede/runner_interface.h"
 #include "./centipede/runner_result.h"
 #include "./centipede/stop.h"
@@ -516,15 +516,14 @@
 
   bool HasCustomMutator() const override { return true; }
 
-  bool Mutate(const std::vector<fuzztest::internal::MutationInputRef>& inputs,
-              size_t num_mutants,
-              std::function<void(fuzztest::internal::ByteSpan)>
-                  new_mutant_callback) override {
+  bool Mutate(absl::Span<const MutationInputRef> inputs, size_t num_mutants,
+              std::function<void(MutantRef)> new_mutant_callback) override {
     if (inputs.empty()) return false;
     cmp_tables.resize(inputs.size());
     absl::Cleanup cmp_tables_cleaner = [this]() { cmp_tables.clear(); };
     for (size_t i = 0; i < num_mutants; ++i) {
       const auto choice = absl::Uniform<double>(prng_, 0, 1);
+      size_t origin_index = Mutant::kOriginNone;
       std::string mutant_data;
       constexpr double kDomainInitRatio = 0.0001;
       if (choice < kDomainInitRatio) {
@@ -532,8 +531,7 @@
             SerializeIRObject(fuzzer_impl_.params_domain_.SerializeCorpus(
                 fuzzer_impl_.params_domain_.Init(prng_)));
       } else {
-        const auto origin_index =
-            absl::Uniform<size_t>(prng_, 0, inputs.size());
+        origin_index = absl::Uniform<size_t>(prng_, 0, inputs.size());
         const auto& origin = inputs[origin_index].data;
         auto parsed_origin =
             fuzzer_impl_.TryParse({(const char*)origin.data(), origin.size()});
@@ -556,7 +554,8 @@
             fuzzer_impl_.params_domain_.SerializeCorpus(mutant.args));
       }
       new_mutant_callback(
-          {(unsigned char*)mutant_data.data(), mutant_data.size()});
+          MutantRef{{(unsigned char*)mutant_data.data(), mutant_data.size()},
+                    origin_index});
     }
     return true;
   }
@@ -864,6 +863,11 @@
   runtime_.SetRunMode(mode);
   runtime_.SetSkippingRequested(false);
   runtime_.SetCurrentTest(&test_, &configuration);
+  // We don't always enable reporter, but always disable it at the end for
+  // simplicity.
+  absl::Cleanup always_disable_reporter = [this]() {
+    runtime_.DisableReporter();
+  };
   if (is_running_property_function_in_this_process) {
     if (IsSilenceTargetEnabled()) SilenceTargetStdoutAndStderr();
     // TODO(b/393582695): Consider whether we need some kind of reporting
@@ -1018,7 +1022,7 @@
   using fuzztest::internal::CentipedeCallbacks::CentipedeCallbacks;
 
   bool Execute(std::string_view binary,
-               const std::vector<fuzztest::internal::ByteArray>& inputs,
+               absl::Span<const fuzztest::internal::ByteSpan> inputs,
                fuzztest::internal::BatchResult& batch_result) override {
     return false;
   }
diff --git a/fuzztest/internal/domains/BUILD b/fuzztest/internal/domains/BUILD
index 8434788..58a6a81 100644
--- a/fuzztest/internal/domains/BUILD
+++ b/fuzztest/internal/domains/BUILD
@@ -235,3 +235,16 @@
     hdrs = ["utf.h"],
     deps = ["@abseil-cpp//absl/strings:string_view"],
 )
+
+cc_library(
+    name = "lazy",
+    hdrs = ["lazy.h"],
+    deps = [
+        ":core_domains_impl",
+        "@abseil-cpp//absl/random:bit_gen_ref",
+        "@abseil-cpp//absl/status",
+        "@com_google_fuzztest//common:logging",
+        "@com_google_fuzztest//fuzztest/internal:meta",
+        "@com_google_fuzztest//fuzztest/internal:serialization",
+    ],
+)
diff --git a/fuzztest/internal/domains/CMakeLists.txt b/fuzztest/internal/domains/CMakeLists.txt
index 6e27f15..3c1759b 100644
--- a/fuzztest/internal/domains/CMakeLists.txt
+++ b/fuzztest/internal/domains/CMakeLists.txt
@@ -224,3 +224,16 @@
   DEPS
     absl::string_view
 )
+fuzztest_cc_library(
+  NAME
+    lazy
+  HDRS
+    "lazy.h"
+  DEPS
+    fuzztest::core_domains_impl
+    absl::random_bit_gen_ref
+    absl::status
+    fuzztest::common_logging
+    fuzztest::meta
+    fuzztest::serialization
+)
diff --git a/fuzztest/internal/domains/lazy.h b/fuzztest/internal/domains/lazy.h
new file mode 100644
index 0000000..ff9fd7e
--- /dev/null
+++ b/fuzztest/internal/domains/lazy.h
@@ -0,0 +1,130 @@
+// Copyright 2026 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_LAZY_H_
+#define FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_LAZY_H_
+
+#include <cstddef>
+#include <functional>
+#include <memory>
+#include <optional>
+#include <tuple>
+#include <utility>
+
+#include "absl/random/bit_gen_ref.h"
+#include "absl/status/status.h"
+#include "./common/logging.h"
+#include "./fuzztest/internal/domains/domain_base.h"
+#include "./fuzztest/internal/meta.h"
+#include "./fuzztest/internal/serialization.h"
+
+namespace fuzztest {
+namespace internal {
+
+// A helper domain that allows its inner domain to be lazily initialized.
+template <typename DomainT, typename... Args>
+class Lazy : public domain_implementor::DomainBase<Lazy<DomainT, Args...>,
+                                                   value_type_t<DomainT>,
+                                                   corpus_type_t<DomainT>> {
+ public:
+  using typename Lazy::DomainBase::corpus_type;
+  using typename Lazy::DomainBase::value_type;
+
+  Lazy(Args&&... args)
+      : args_(std::tuple<Args...>(std::forward<Args>(args)...)) {}
+
+  Lazy(const Lazy& other) {
+    if (other.inner_ != nullptr) {
+      inner_ = std::make_unique<DomainT>(*other.inner_);
+    } else {
+      args_ = other.args_;
+      setup_ = other.setup_;
+    }
+  }
+
+  Lazy(Lazy&& other) noexcept = default;
+  Lazy& operator=(Lazy&& other) = default;
+
+  corpus_type Init(absl::BitGenRef prng) { return GetInnerDomain().Init(prng); }
+
+  Lazy& WithLazySetup(std::function<void(DomainT&)> setup) {
+    setup_ = std::move(setup);
+    return *this;
+  }
+
+  void Mutate(corpus_type& corpus_value, absl::BitGenRef prng,
+              const domain_implementor::MutationMetadata& metadata,
+              bool only_shrink) {
+    GetInnerDomain().Mutate(corpus_value, prng, metadata, only_shrink);
+  }
+
+  value_type GetValue(const corpus_type& corpus_value) const {
+    return GetInnerDomain().GetValue(corpus_value);
+  }
+
+  std::optional<corpus_type> FromValue(const value_type& v) const {
+    return GetInnerDomain().FromValue(v);
+  }
+
+  std::optional<corpus_type> ParseCorpus(const IRObject& obj) const {
+    return GetInnerDomain().ParseCorpus(obj);
+  }
+
+  IRObject SerializeCorpus(const corpus_type& corpus_value) const {
+    return GetInnerDomain().SerializeCorpus(corpus_value);
+  }
+
+  absl::Status ValidateCorpusValue(const corpus_type& corpus_value) const {
+    return GetInnerDomain().ValidateCorpusValue(corpus_value);
+  }
+
+  auto GetPrinter() const { return GetInnerDomain().GetPrinter(); }
+
+ private:
+  template <std::size_t... Is>
+  void PopulateInner(std::index_sequence<Is...>) const {
+    FUZZTEST_CHECK(args_.has_value())
+        << "args is unavailable for creating the inner domain";
+    inner_ = std::make_unique<DomainT>(std::move(std::get<Is>(*args_))...);
+    if (setup_) setup_(*inner_);
+    args_ = std::nullopt;
+    setup_ = {};
+  }
+
+  const DomainT& GetInnerDomain() const {
+    if (inner_ == nullptr) {
+      PopulateInner(std::index_sequence_for<Args...>{});
+    }
+    return *inner_;
+  }
+
+  DomainT& GetInnerDomain() {
+    if (inner_ == nullptr) {
+      PopulateInner(std::index_sequence_for<Args...>{});
+    }
+    return *inner_;
+  }
+
+  mutable std::unique_ptr<DomainT> inner_ = nullptr;
+  // Arguments passed to the inner domain constructor. Set iff inner_ ==
+  // nullptr.
+  mutable std::optional<std::tuple<Args...>> args_;
+  // Must be the default value if inner_ != nullptr.
+  mutable std::function<void(DomainT&)> setup_;
+};
+
+}  // namespace internal
+}  // namespace fuzztest
+
+#endif  // FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_LAZY_H_
diff --git a/fuzztest/internal/googletest_adaptor.h b/fuzztest/internal/googletest_adaptor.h
index 98e8a8a..190da2c 100644
--- a/fuzztest/internal/googletest_adaptor.h
+++ b/fuzztest/internal/googletest_adaptor.h
@@ -122,6 +122,7 @@
   void OnTestPartResult(const TestPartResult& test_part_result) override {
     if (!test_part_result.failed()) return;
     Runtime& runtime = Runtime::instance();
+    if (!runtime.reporter_enabled()) return;
     runtime.SetCrashTypeIfUnset("GoogleTest assertion failure");
     if (runtime.run_mode() == RunMode::kFuzz) {
       if (runtime.should_terminate_on_non_fatal_failure()) {
diff --git a/fuzztest/internal/runtime.h b/fuzztest/internal/runtime.h
index bdefab5..ea867c3 100644
--- a/fuzztest/internal/runtime.h
+++ b/fuzztest/internal/runtime.h
@@ -175,6 +175,7 @@
     ResetCrashType();
   }
   void DisableReporter() { reporter_enabled_ = false; }
+  bool reporter_enabled() const { return reporter_enabled_; }
 
   struct Args {
     const GenericDomainCorpusType& corpus_value;
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");
diff --git a/fuzztest/llvm_fuzzer_main.cc b/fuzztest/llvm_fuzzer_main.cc
index a170236..f9b17c3 100644
--- a/fuzztest/llvm_fuzzer_main.cc
+++ b/fuzztest/llvm_fuzzer_main.cc
@@ -1,3 +1,4 @@
+#include <cstddef>
 #include <string>
 
 #include "gtest/gtest.h"
@@ -14,6 +15,9 @@
 ABSL_FLAG(std::string, llvm_fuzzer_wrapper_corpus_dir, "",
           "Path to seed corpus directory used by the wrapped legacy LLVMFuzzer "
           "target (https://llvm.org/docs/LibFuzzer.html#fuzz-target).");
+ABSL_FLAG(size_t, llvm_fuzzer_wrapper_max_input_size, 4096,
+          "Maximum input size for the wrapped legacy LLVMFuzzer target "
+          "(https://llvm.org/docs/LibFuzzer.html#fuzz-target).");
 
 int main(int argc, char** argv) {
   absl::ParseCommandLine(argc, argv);
diff --git a/fuzztest/llvm_fuzzer_wrapper.cc b/fuzztest/llvm_fuzzer_wrapper.cc
index 5340220..6407725 100644
--- a/fuzztest/llvm_fuzzer_wrapper.cc
+++ b/fuzztest/llvm_fuzzer_wrapper.cc
@@ -21,12 +21,12 @@
 #include "./fuzztest/internal/domains/arbitrary_impl.h"
 #include "./fuzztest/internal/domains/container_of_impl.h"
 #include "./fuzztest/internal/domains/domain_base.h"
+#include "./fuzztest/internal/domains/lazy.h"
 #include "./fuzztest/internal/io.h"
 
 ABSL_DECLARE_FLAG(std::string, llvm_fuzzer_wrapper_dict_file);
 ABSL_DECLARE_FLAG(std::string, llvm_fuzzer_wrapper_corpus_dir);
-
-constexpr static size_t kByteArrayMaxLen = 4096;
+ABSL_DECLARE_FLAG(size_t, llvm_fuzzer_wrapper_max_input_size);
 
 extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size);
 
@@ -56,7 +56,10 @@
   for (const fuzztest::internal::FilePathAndData& file : files) {
     out.push_back(
         {file.data.begin(),
-         file.data.begin() + std::min(file.data.size(), kByteArrayMaxLen)});
+         file.data.begin() +
+             std::min(
+                 file.data.size(),
+                 absl::GetFlag(FLAGS_llvm_fuzzer_wrapper_max_input_size))});
   }
   return out;
 }
@@ -177,16 +180,17 @@
  public:
   using typename Base::corpus_type;
 
-  ArbitraryByteVector() { WithMaxSize(kByteArrayMaxLen); }
+  ArbitraryByteVector() = default;
 
   void Mutate(corpus_type& val, absl::BitGenRef prng,
               const MutationMetadata& metadata, bool only_shrink) {
     if (LLVMFuzzerCustomMutator) {
       const size_t size = val.size();
-      const size_t max_size = only_shrink ? size : kByteArrayMaxLen;
-      val.resize(max_size);
+      const size_t mutant_max_size = only_shrink ? size : max_size();
+      val.resize(mutant_max_size);
       mutation_metadata_manager->Activate(metadata);
-      val.resize(LLVMFuzzerCustomMutator(val.data(), size, max_size, prng()));
+      val.resize(
+          LLVMFuzzerCustomMutator(val.data(), size, mutant_max_size, prng()));
       mutation_metadata_manager->Deactivate();
     } else {
       Base::Mutate(val, prng, metadata, only_shrink);
@@ -199,6 +203,9 @@
 }
 
 FUZZ_TEST(LLVMFuzzer, TestOneInput)
-    .WithDomains(ArbitraryByteVector()
-                     .WithDictionary(ReadByteArrayDictionaryFromFile)
-                     .WithSeeds(ReadByteArraysFromDirectory));
+    .WithDomains(fuzztest::internal::Lazy<ArbitraryByteVector>().WithLazySetup(
+        [](auto& d) {
+          d.WithMaxSize(absl::GetFlag(FLAGS_llvm_fuzzer_wrapper_max_input_size))
+              .WithDictionary(ReadByteArrayDictionaryFromFile)
+              .WithSeeds(ReadByteArraysFromDirectory);
+        }));