diff --git a/payload_generator/cycle_breaker.cc b/payload_generator/cycle_breaker.cc
index bb91a19..a8a04ab 100644
--- a/payload_generator/cycle_breaker.cc
+++ b/payload_generator/cycle_breaker.cc
@@ -23,10 +23,10 @@
 #include <string>
 #include <utility>
 
+#include <base/stl_util.h>
 #include <base/strings/string_util.h>
 #include <base/strings/stringprintf.h>
 
-#include "update_engine/common/utils.h"
 #include "update_engine/payload_generator/graph_utils.h"
 #include "update_engine/payload_generator/tarjan.h"
 
@@ -84,7 +84,7 @@
            jt != component_indexes.end(); ++jt) {
         // If there's a link from *it -> *jt in the graph,
         // add a subgraph_ edge
-        if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt))
+        if (base::ContainsKey(subgraph_[*it].out_edges, *jt))
           subgraph_[*it].subgraph_edges.insert(*jt);
       }
     }
@@ -147,7 +147,7 @@
   for (vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
            e = stack_.end(); it != e; ++it) {
     Edge edge = make_pair(*(it - 1), *it);
-    if (utils::SetContainsKey(cut_edges_, edge)) {
+    if (base::ContainsKey(cut_edges_, edge)) {
       return true;
     }
   }
diff --git a/payload_generator/cycle_breaker_unittest.cc b/payload_generator/cycle_breaker_unittest.cc
index e92bc30..7554dbb 100644
--- a/payload_generator/cycle_breaker_unittest.cc
+++ b/payload_generator/cycle_breaker_unittest.cc
@@ -22,9 +22,9 @@
 #include <vector>
 
 #include <base/logging.h>
+#include <base/stl_util.h>
 #include <gtest/gtest.h>
 
-#include "update_engine/common/utils.h"
 #include "update_engine/payload_generator/graph_types.h"
 
 using std::make_pair;
@@ -83,14 +83,14 @@
   // C->D->E
   // G->H
 
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_e)) ||
-              utils::SetContainsKey(broken_edges, make_pair(n_e, n_b)) ||
-              utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_c, n_d)) ||
-              utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)) ||
-              utils::SetContainsKey(broken_edges, make_pair(n_e, n_c)));
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_g, n_h)) ||
-              utils::SetContainsKey(broken_edges, make_pair(n_h, n_g)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_a, n_e)) ||
+              base::ContainsKey(broken_edges, make_pair(n_e, n_b)) ||
+              base::ContainsKey(broken_edges, make_pair(n_b, n_a)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_c, n_d)) ||
+              base::ContainsKey(broken_edges, make_pair(n_d, n_e)) ||
+              base::ContainsKey(broken_edges, make_pair(n_e, n_c)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_g, n_h)) ||
+              base::ContainsKey(broken_edges, make_pair(n_h, n_g)));
   EXPECT_EQ(3U, broken_edges.size());
 }
 
@@ -217,11 +217,11 @@
   breaker.BreakCycles(graph, &broken_edges);
 
   // These are required to be broken:
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c)));
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)));
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g)));
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_b, n_a)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_b, n_c)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_d, n_e)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_f, n_g)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_h, n_i)));
 }
 
 TEST(CycleBreakerTest, UnblockGraphTest) {
@@ -248,8 +248,8 @@
   breaker.BreakCycles(graph, &broken_edges);
 
   // These are required to be broken:
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b)));
-  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_a, n_b)));
+  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_a, n_c)));
 }
 
 TEST(CycleBreakerTest, SkipOpsTest) {
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index b858c2b..febdcce 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -23,6 +23,8 @@
 #include <utility>
 #include <vector>
 
+#include <base/stl_util.h>
+
 #include "update_engine/common/utils.h"
 #include "update_engine/payload_consumer/payload_constants.h"
 #include "update_engine/payload_generator/cycle_breaker.h"
@@ -341,7 +343,7 @@
   vector<Vertex::Index> new_op_indexes;
   new_op_indexes.reserve(op_indexes->size());
   for (Vertex::Index vertex_index : *op_indexes) {
-    if (utils::SetContainsKey(deleted_nodes, vertex_index))
+    if (base::ContainsKey(deleted_nodes, vertex_index))
       continue;
     new_op_indexes.push_back(vertex_index);
   }
diff --git a/payload_generator/tarjan.cc b/payload_generator/tarjan.cc
index 98e29f9..d99ae12 100644
--- a/payload_generator/tarjan.cc
+++ b/payload_generator/tarjan.cc
@@ -19,8 +19,7 @@
 #include <vector>
 
 #include <base/logging.h>
-
-#include "update_engine/common/utils.h"
+#include <base/stl_util.h>
 
 using std::min;
 using std::vector;
@@ -59,7 +58,7 @@
       Tarjan(vertex_next, graph);
       (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
                                      (*graph)[vertex_next].lowlink);
-    } else if (utils::VectorContainsValue(stack_, vertex_next)) {
+    } else if (base::ContainsValue(stack_, vertex_next)) {
       (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
                                      (*graph)[vertex_next].index);
     }
@@ -73,7 +72,7 @@
       component.push_back(other_vertex);
     } while (other_vertex != vertex && !stack_.empty());
 
-    if (utils::VectorContainsValue(component, required_vertex_)) {
+    if (base::ContainsValue(component, required_vertex_)) {
       components_.resize(components_.size() + 1);
       component.swap(components_.back());
     }
diff --git a/payload_generator/tarjan_unittest.cc b/payload_generator/tarjan_unittest.cc
index c29cbdc..b271227 100644
--- a/payload_generator/tarjan_unittest.cc
+++ b/payload_generator/tarjan_unittest.cc
@@ -20,9 +20,9 @@
 #include <utility>
 
 #include <base/logging.h>
+#include <base/stl_util.h>
 #include <gtest/gtest.h>
 
-#include "update_engine/common/utils.h"
 #include "update_engine/payload_generator/graph_types.h"
 
 using std::make_pair;
@@ -66,11 +66,11 @@
     tarjan.Execute(i, &graph, &vertex_indexes);
 
     EXPECT_EQ(5U, vertex_indexes.size());
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a));
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b));
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c));
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d));
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_a));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_b));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_c));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_d));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_e));
   }
 
   {
@@ -78,7 +78,7 @@
     tarjan.Execute(n_f, &graph, &vertex_indexes);
 
     EXPECT_EQ(1U, vertex_indexes.size());
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_f));
   }
 
   for (Vertex::Index i = n_g; i <= n_h; i++) {
@@ -86,8 +86,8 @@
     tarjan.Execute(i, &graph, &vertex_indexes);
 
     EXPECT_EQ(2U, vertex_indexes.size());
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g));
-    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_g));
+    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_h));
   }
 }