diff --git a/src/gn/builder.cc b/src/gn/builder.cc
index 7e36deb..adb39ab 100644
--- a/src/gn/builder.cc
+++ b/src/gn/builder.cc
@@ -5,6 +5,7 @@
 #include "gn/builder.h"
 
 #include <stddef.h>
+#include <algorithm>
 #include <utility>
 
 #include "gn/action_values.h"
@@ -34,9 +35,7 @@
 bool RecursiveFindCycle(const BuilderRecord* search_in,
                         std::vector<const BuilderRecord*>* path) {
   path->push_back(search_in);
-  BuilderRecordSet unresolved_deps = search_in->GetUnresolvedDeps();
-  for (auto it = unresolved_deps.begin(); it.valid(); ++it) {
-    const BuilderRecord* cur = *it;
+  for (const auto& cur : search_in->GetSortedUnresolvedDeps()) {
     std::vector<const BuilderRecord*>::iterator found =
         std::find(path->begin(), path->end(), cur);
     if (found != path->end()) {
@@ -136,6 +135,8 @@
   result.reserve(records_.size());
   for (const auto& record : records_)
     result.push_back(&record);
+  // Ensure deterministic outputs.
+  std::sort(result.begin(), result.end(), BuilderRecord::LabelCompare);
   return result;
 }
 
@@ -148,7 +149,10 @@
       result.push_back(record.item());
     }
   }
-
+  // Ensure deterministic outputs.
+  std::sort(result.begin(), result.end(), [](const Item* a, const Item* b) {
+    return a->label() < b->label();
+  });
   return result;
 }
 
@@ -160,6 +164,10 @@
         record.should_generate() && record.item())
       result.push_back(record.item()->AsTarget());
   }
+  // Ensure deterministic outputs.
+  std::sort(result.begin(), result.end(), [](const Target* a, const Target* b) {
+    return a->label() < b->label();
+  });
   return result;
 }
 
@@ -183,21 +191,27 @@
   // but none will be resolved. If this happens, we'll check explicitly for
   // that below.
   std::vector<const BuilderRecord*> bad_records;
-  std::string depstring;
   for (const auto& src : records_) {
     if (!src.should_generate())
       continue;  // Skip ungenerated nodes.
 
-    if (!src.resolved()) {
+    if (!src.resolved())
       bad_records.push_back(&src);
+  }
+  if (bad_records.empty())
+    return true;
 
-      // Check dependencies.
-      BuilderRecordSet unresolved_deps = src.GetUnresolvedDeps();
-      for (const auto* dest : unresolved_deps) {
-        if (!dest->item()) {
-          depstring += src.label().GetUserVisibleName(true) + "\n  needs " +
-                       dest->label().GetUserVisibleName(true) + "\n";
-        }
+  // Sort by label to ensure deterministic outputs.
+  std::sort(bad_records.begin(), bad_records.end(),
+            BuilderRecord::LabelCompare);
+
+  std::string depstring;
+  for (const auto& src : bad_records) {
+    // Check dependencies.
+    for (const auto* dest : src->GetSortedUnresolvedDeps()) {
+      if (!dest->item()) {
+        depstring += src->label().GetUserVisibleName(true) + "\n  needs " +
+                     dest->label().GetUserVisibleName(true) + "\n";
       }
     }
   }
@@ -301,6 +315,11 @@
   return true;
 }
 
+BuilderRecord* Builder::GetOrCreateRecordForTesting(const Label& label) {
+  Err err;
+  return GetOrCreateRecordOfType(label, nullptr, BuilderRecord::ITEM_UNKNOWN, &err);
+}
+
 BuilderRecord* Builder::GetOrCreateRecordOfType(const Label& label,
                                                 const ParseNode* request_from,
                                                 BuilderRecord::ItemType type,
diff --git a/src/gn/builder.h b/src/gn/builder.h
index 4b85824..bebaa81 100644
--- a/src/gn/builder.h
+++ b/src/gn/builder.h
@@ -60,6 +60,9 @@
   // If there are any undefined references, returns false and sets the error.
   bool CheckForBadItems(Err* err) const;
 
+  // Get or create an empty record for unit-testing.
+  BuilderRecord* GetOrCreateRecordForTesting(const Label& label);
+
  private:
   bool TargetDefined(BuilderRecord* record, Err* err);
   bool ConfigDefined(BuilderRecord* record, Err* err);
diff --git a/src/gn/builder_record.cc b/src/gn/builder_record.cc
index 7849d91..d1d0c53 100644
--- a/src/gn/builder_record.cc
+++ b/src/gn/builder_record.cc
@@ -74,13 +74,15 @@
   return --unresolved_count_ == 0;
 }
 
-BuilderRecord::BuilderRecordSet BuilderRecord::GetUnresolvedDeps() const {
-  BuilderRecordSet result;
+std::vector<const BuilderRecord*> BuilderRecord::GetSortedUnresolvedDeps()
+    const {
+  std::vector<const BuilderRecord*> result;
   for (auto it = all_deps_.begin(); it.valid(); ++it) {
     BuilderRecord* dep = *it;
     if (dep->waiting_on_resolution_.contains(const_cast<BuilderRecord*>(this)))
-      result.add(dep);
+      result.push_back(dep);
   }
+  std::sort(result.begin(), result.end(), LabelCompare);
   return result;
 }
 
diff --git a/src/gn/builder_record.h b/src/gn/builder_record.h
index 28f75fe..c4dc867 100644
--- a/src/gn/builder_record.h
+++ b/src/gn/builder_record.h
@@ -78,9 +78,9 @@
   BuilderRecordSet& all_deps() { return all_deps_; }
   const BuilderRecordSet& all_deps() const { return all_deps_; }
 
-  // Return the set of unresolved records this one is depend on.
-  // This is a subset of all_deps() above.
-  BuilderRecordSet GetUnresolvedDeps() const;
+  // Get the set of unresolved records this one depends on,
+  // as a list sorted by label.
+  std::vector<const BuilderRecord*> GetSortedUnresolvedDeps() const;
 
   // Call this method to notify the record that its dependency |dep| was
   // just resolved. This returns true to indicate that the current record
@@ -97,6 +97,11 @@
   void AddGenDep(BuilderRecord* record);
   void AddDep(BuilderRecord* record);
 
+  // Comparator function used to sort records from their label.
+  static bool LabelCompare(const BuilderRecord* a, const BuilderRecord* b) {
+    return a->label_ < b->label_;
+  }
+
  private:
   ItemType type_;
   bool should_generate_ = false;
diff --git a/src/gn/builder_unittest.cc b/src/gn/builder_unittest.cc
index 2a354d5..79285ab 100644
--- a/src/gn/builder_unittest.cc
+++ b/src/gn/builder_unittest.cc
@@ -138,10 +138,13 @@
 
   // A should have two deps: B and the toolchain. Only B should be unresolved.
   EXPECT_EQ(2u, a_record->all_deps().size());
-  EXPECT_EQ(1u, a_record->GetUnresolvedDeps().size());
   EXPECT_TRUE(a_record->all_deps().contains(toolchain_record));
   EXPECT_TRUE(a_record->all_deps().contains(b_record));
-  EXPECT_TRUE(a_record->GetUnresolvedDeps().contains(b_record));
+
+  std::vector<const BuilderRecord*> a_unresolved =
+      a_record->GetSortedUnresolvedDeps();
+  EXPECT_EQ(1u, a_unresolved.size());
+  EXPECT_EQ(a_unresolved[0], b_record);
 
   // B should be marked as having A waiting on it.
   EXPECT_EQ(1u, b_record->waiting_on_resolution().size());
@@ -174,15 +177,47 @@
   EXPECT_TRUE(b_record->resolved());
   EXPECT_TRUE(c_record->resolved());
 
-  EXPECT_TRUE(a_record->GetUnresolvedDeps().empty());
-  EXPECT_TRUE(b_record->GetUnresolvedDeps().empty());
-  EXPECT_TRUE(c_record->GetUnresolvedDeps().empty());
+  EXPECT_TRUE(a_record->GetSortedUnresolvedDeps().empty());
+  EXPECT_TRUE(b_record->GetSortedUnresolvedDeps().empty());
+  EXPECT_TRUE(c_record->GetSortedUnresolvedDeps().empty());
 
   EXPECT_TRUE(a_record->waiting_on_resolution().empty());
   EXPECT_TRUE(b_record->waiting_on_resolution().empty());
   EXPECT_TRUE(c_record->waiting_on_resolution().empty());
 }
 
+TEST_F(BuilderTest, SortedUnresolvedDeps) {
+  SourceDir toolchain_dir = settings_.toolchain_label().dir();
+  std::string toolchain_name = settings_.toolchain_label().name();
+
+  // Construct a dependency graph with:
+  //    A -> B
+  //    A -> D
+  //    A -> C
+  //
+  // Ensure that the unresolved list of A is always [B, C, D]
+  //
+  Label a_label(SourceDir("//a/"), "a", toolchain_dir, toolchain_name);
+  Label b_label(SourceDir("//b/"), "b", toolchain_dir, toolchain_name);
+  Label c_label(SourceDir("//c/"), "c", toolchain_dir, toolchain_name);
+  Label d_label(SourceDir("//d/"), "d", toolchain_dir, toolchain_name);
+
+  BuilderRecord* a_record = builder_.GetOrCreateRecordForTesting(a_label);
+  BuilderRecord* b_record = builder_.GetOrCreateRecordForTesting(b_label);
+  BuilderRecord* c_record = builder_.GetOrCreateRecordForTesting(c_label);
+  BuilderRecord* d_record = builder_.GetOrCreateRecordForTesting(d_label);
+
+  a_record->AddDep(b_record);
+  a_record->AddDep(d_record);
+  a_record->AddDep(c_record);
+
+  std::vector<const BuilderRecord*> a_unresolved = a_record->GetSortedUnresolvedDeps();
+  EXPECT_EQ(3u, a_unresolved.size()) << a_unresolved.size();
+  EXPECT_EQ(b_record, a_unresolved[0]);
+  EXPECT_EQ(c_record, a_unresolved[1]);
+  EXPECT_EQ(d_record, a_unresolved[2]);
+}
+
 // Tests that the "should generate" flag is set and propagated properly.
 TEST_F(BuilderTest, ShouldGenerate) {
   DefineToolchain();