diff --git a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
index fe2c785..c9bbefe 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.conversion;
 
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
@@ -13,12 +14,19 @@
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer;
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer.D8CfInstructionDesugaringEventConsumer;
 import com.android.tools.r8.ir.desugar.itf.InterfaceProcessor;
+import com.android.tools.r8.utils.MapUtils;
 import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.collections.ImmutableDeque;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Sets;
+import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Comparator;
+import java.util.Deque;
+import java.util.IdentityHashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
@@ -60,6 +68,48 @@
     return resultBuilder.build();
   }
 
+  private static Deque<List<DexProgramClass>> getDeterministicNestWaves(
+      Collection<DexProgramClass> classes) {
+    Map<DexType, List<DexProgramClass>> nestGroups = new IdentityHashMap<>();
+    for (DexProgramClass clazz : classes) {
+      if (clazz.isInANest()) {
+        nestGroups.computeIfAbsent(clazz.getNestHost(), k -> new ArrayList<>()).add(clazz);
+      }
+    }
+    if (nestGroups.isEmpty()) {
+      return ImmutableDeque.of();
+    }
+    int maxGroupSize = 0;
+    for (List<DexProgramClass> members : nestGroups.values()) {
+      maxGroupSize = Math.max(maxGroupSize, members.size());
+      members.sort(Comparator.comparing(DexClass::getType));
+    }
+    Deque<List<DexProgramClass>> processingList = new ArrayDeque<>(maxGroupSize);
+    for (int i = 0; i < maxGroupSize; i++) {
+      List<DexProgramClass> wave = new ArrayList<>(nestGroups.size());
+      final int index = i;
+      MapUtils.removeIf(
+          nestGroups,
+          (host, members) -> {
+            wave.add(members.get(index));
+            return index + 1 == members.size();
+          });
+      processingList.add(wave);
+    }
+    return processingList;
+  }
+
+  private static List<DexProgramClass> filterOutClassesInNests(
+      Collection<DexProgramClass> classes) {
+    List<DexProgramClass> filtered = new ArrayList<>(classes.size());
+    for (DexProgramClass clazz : classes) {
+      if (!clazz.isInANest()) {
+        filtered.add(clazz);
+      }
+    }
+    return filtered;
+  }
+
   private void internalConvertClasses(
       ClassConverterResult.Builder resultBuilder, ExecutorService executorService)
       throws ExecutionException {
@@ -78,19 +128,21 @@
 
     converter.prepareDesugaringForD8(executorService);
 
-    while (!classes.isEmpty()) {
-      Set<DexType> seenNestHosts = Sets.newIdentityHashSet();
-      List<DexProgramClass> deferred = new ArrayList<>(classes.size() / 2);
-      List<DexProgramClass> wave = new ArrayList<>(classes.size());
-      for (DexProgramClass clazz : classes) {
-        if (clazz.isInANest() && !seenNestHosts.add(clazz.getNestHost())) {
-          deferred.add(clazz);
-        } else {
-          wave.add(clazz);
+    // When adding nest members to the wave we must do so deterministically.
+    Deque<List<DexProgramClass>> nestProcessingWaves = getDeterministicNestWaves(classes);
+    Collection<DexProgramClass> wave;
+    if (nestProcessingWaves.isEmpty()) {
+      wave = classes;
+    } else {
+      List<DexProgramClass> firstWave = filterOutClassesInNests(classes);
+      firstWave.addAll(nestProcessingWaves.removeFirst());
+      wave = firstWave;
+    }
 
-          // TODO(b/179755192): Avoid marking classes as scheduled by building up waves of methods.
-          methodProcessor.addScheduled(clazz);
-        }
+    while (!wave.isEmpty()) {
+      // TODO(b/179755192): Avoid marking classes as scheduled by building up waves of methods.
+      for (DexProgramClass clazz : wave) {
+        methodProcessor.addScheduled(clazz);
       }
 
       D8CfInstructionDesugaringEventConsumer instructionDesugaringEventConsumer =
@@ -128,7 +180,11 @@
         assert instructionDesugaringEventConsumer.verifyNothingToFinalize();
       }
 
-      classes = deferred;
+      if (!nestProcessingWaves.isEmpty()) {
+        wave = nestProcessingWaves.removeFirst();
+      } else {
+        break;
+      }
     }
   }