diff --git a/fuzzers/tint_ast_fuzzer/mutation_finder.h b/fuzzers/tint_ast_fuzzer/mutation_finder.h
index 546dce4..1dd8732 100644
--- a/fuzzers/tint_ast_fuzzer/mutation_finder.h
+++ b/fuzzers/tint_ast_fuzzer/mutation_finder.h
@@ -54,7 +54,7 @@
   /// @return all the found mutations.
   virtual MutationList FindMutations(
       const tint::Program& program,
-      const NodeIdMap& node_id_map,
+      NodeIdMap* node_id_map,
       ProbabilityContext* probability_context) const = 0;
 
   /// @brief Compute a probability of applying a single mutation, returned by
diff --git a/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.cc b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.cc
index 7eb3f6d..aa23dab 100644
--- a/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.cc
+++ b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.cc
@@ -29,7 +29,7 @@
 
 MutationList MutationFinderReplaceIdentifiers::FindMutations(
     const tint::Program& program,
-    const NodeIdMap& node_id_map,
+    NodeIdMap* node_id_map,
     ProbabilityContext* probability_context) const {
   MutationList result;
 
@@ -61,8 +61,8 @@
               candidate_variables)];
 
       result.push_back(std::make_unique<MutationReplaceIdentifier>(
-          node_id_map.GetId(user->Declaration()),
-          node_id_map.GetId(replacement->Declaration())));
+          node_id_map->GetId(user->Declaration()),
+          node_id_map->GetId(replacement->Declaration())));
     }
   }
 
diff --git a/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h
index 957abf2..70a0b10 100644
--- a/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h
+++ b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h
@@ -29,7 +29,7 @@
  public:
   MutationList FindMutations(
       const tint::Program& program,
-      const NodeIdMap& node_id_map,
+      NodeIdMap* node_id_map,
       ProbabilityContext* probability_context) const override;
   uint32_t GetChanceOfApplyingMutation(
       ProbabilityContext* probability_context) const override;
diff --git a/fuzzers/tint_ast_fuzzer/mutator.cc b/fuzzers/tint_ast_fuzzer/mutator.cc
index f8ebb7c..d1b5efe 100644
--- a/fuzzers/tint_ast_fuzzer/mutator.cc
+++ b/fuzzers/tint_ast_fuzzer/mutator.cc
@@ -141,7 +141,7 @@
     // Get all applicable mutations from some mutation finder.
     const auto& mutation_finder =
         finders[probability_context->GetRandomIndex(finders)];
-    auto mutations = mutation_finder->FindMutations(program, node_id_map,
+    auto mutations = mutation_finder->FindMutations(program, &node_id_map,
                                                     probability_context);
 
     const auto old_applied_mutations = applied_mutations;
diff --git a/fuzzers/tint_ast_fuzzer/node_id_map.cc b/fuzzers/tint_ast_fuzzer/node_id_map.cc
index bdb22eb..7987fcf 100644
--- a/fuzzers/tint_ast_fuzzer/node_id_map.cc
+++ b/fuzzers/tint_ast_fuzzer/node_id_map.cc
@@ -40,17 +40,21 @@
 
 void NodeIdMap::Add(const ast::Node* node, IdType id) {
   assert(!node_to_id_.count(node) && "The node already exists in the map");
-  assert(!id_to_node_.count(id) && "Id already exists in the map");
+  assert(IdIsFreshAndValid(id) && "Id already exists in the map or Id is zero");
   assert(node && "`node` can't be a nullptr");
-  assert(id && "`id` can't be equal to 0");
 
   node_to_id_[node] = id;
   id_to_node_[id] = node;
+
   if (id >= fresh_id_) {
     fresh_id_ = id + 1;
   }
 }
 
+bool NodeIdMap::IdIsFreshAndValid(IdType id) {
+  return id && !id_to_node_.count(id);
+}
+
 NodeIdMap::IdType NodeIdMap::TakeFreshId() {
   assert(fresh_id_ != 0 && "`NodeIdMap` id has overflowed");
   return fresh_id_++;
diff --git a/fuzzers/tint_ast_fuzzer/node_id_map.h b/fuzzers/tint_ast_fuzzer/node_id_map.h
index e6e2e3d..3105e4d 100644
--- a/fuzzers/tint_ast_fuzzer/node_id_map.h
+++ b/fuzzers/tint_ast_fuzzer/node_id_map.h
@@ -67,6 +67,13 @@
   /// @param id - may not be 0 and can't be present in this map.
   void Add(const ast::Node* node, IdType id);
 
+  /// @brief Returns whether the id is fresh by checking if it exists in
+  /// the id map and the id is not 0.
+  /// @param id - an id that is used to check in the map.
+  /// @return true the given id is fresh and valid (non-zero).
+  /// @return false otherwise.
+  bool IdIsFreshAndValid(IdType id);
+
   /// @brief Returns an id that is guaranteed to be unoccupied in this map.
   ///
   /// This will effectively increase the counter. This means that two