diff --git a/src/test/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollectorTest.java b/src/test/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollectorTest.java
index 64dd871..f4b78b3 100644
--- a/src/test/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollectorTest.java
+++ b/src/test/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollectorTest.java
@@ -13,14 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.android.desugar.dependencies;
 
+import static com.google.common.collect.ImmutableList.toImmutableList;
 import static com.google.common.truth.Truth.assertThat;
 
-import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.android.desugar.proto.DesugarDeps;
-import com.google.devtools.build.android.desugar.proto.DesugarDeps.Dependency;
 import com.google.devtools.build.android.desugar.proto.DesugarDeps.DesugarDepsInfo;
 import com.google.devtools.build.android.desugar.proto.DesugarDeps.InterfaceDetails;
-import com.google.devtools.build.android.desugar.proto.DesugarDeps.InterfaceWithCompanion;
+import java.util.Arrays;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -42,65 +41,79 @@
     collector.assumeCompanionClass("a", "a$$CC");
 
     DesugarDepsInfo info = extractProto(collector);
+
     assertThat(info.getAssumePresentList())
         .containsExactly(
-            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("b$$CC")).build(),
-            Dependency.newBuilder().setOrigin(wrapType("b")).setTarget(wrapType("b$$CC")).build(),
-            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("a$$CC")).build());
+            dependency("a", "a$$CC"), dependency("a", "b$$CC"), dependency("b", "b$$CC"));
   }
 
   @Test
   public void testMissingImplementedInterface() throws Exception {
     MetadataCollector collector = new MetadataCollector(true);
     collector.missingImplementedInterface("a", "b");
-    collector.missingImplementedInterface("a", "c");
     collector.missingImplementedInterface("c", "b");
+    collector.missingImplementedInterface("a", "c");
 
     DesugarDepsInfo info = extractProto(collector);
-    assertThat(info.getMissingInterfaceList())
-        .containsExactly(
-            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("b")).build(),
-            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("c")).build(),
-            Dependency.newBuilder().setOrigin(wrapType("c")).setTarget(wrapType("b")).build());
+    assertThat(info.getMissingInterfaceList().get(0)).isEqualTo(dependency("a", "b"));
+    assertThat(info.getMissingInterfaceList().get(1)).isEqualTo(dependency("a", "c"));
+    assertThat(info.getMissingInterfaceList().get(2)).isEqualTo(dependency("c", "b"));
   }
 
   @Test
   public void testRecordExtendedInterfaces() throws Exception {
     MetadataCollector collector = new MetadataCollector(false);
-    collector.recordExtendedInterfaces("a", "b", "c");
-    collector.recordExtendedInterfaces("b");
     collector.recordExtendedInterfaces("c", "d");
+    collector.recordExtendedInterfaces("a", "c", "b");
+    collector.recordExtendedInterfaces("b");
 
     DesugarDepsInfo info = extractProto(collector);
-    assertThat(info.getInterfaceWithSupertypesList())
-        .containsExactly(
-            InterfaceDetails.newBuilder()
-                .setOrigin(wrapType("a"))
-                .addAllExtendedInterface(ImmutableList.of(wrapType("b"), wrapType("c")))
-                .build(),
-            InterfaceDetails.newBuilder()
-                .setOrigin(wrapType("c"))
-                .addAllExtendedInterface(ImmutableList.of(wrapType("d")))
-                .build());
+
+    assertThat(info.getInterfaceWithSupertypesList().get(0))
+        .isEqualTo(interfaceDetails("a", "b", "c"));
+    assertThat(info.getInterfaceWithSupertypesList().get(0).getExtendedInterfaceList().get(0))
+        .isEqualTo(wrapType("b"));
+    assertThat(info.getInterfaceWithSupertypesList().get(0).getExtendedInterfaceList().get(1))
+        .isEqualTo(wrapType("c"));
+
+    assertThat(info.getInterfaceWithSupertypesList().get(1)).isEqualTo(interfaceDetails("c", "d"));
   }
 
   @Test
   public void testRecordDefaultMethods() throws Exception {
     MetadataCollector collector = new MetadataCollector(false);
-    collector.recordDefaultMethods("a", 0);
     collector.recordDefaultMethods("b", 1);
+    collector.recordDefaultMethods("a", 0);
 
     DesugarDepsInfo info = extractProto(collector);
-    assertThat(info.getInterfaceWithCompanionList())
-        .containsExactly(
-            InterfaceWithCompanion.newBuilder()
-                .setOrigin(wrapType("a"))
-                .setNumDefaultMethods(0)
-                .build(),
-            InterfaceWithCompanion.newBuilder()
-                .setOrigin(wrapType("b"))
-                .setNumDefaultMethods(1)
-                .build());
+    assertThat(info.getInterfaceWithCompanionList().get(0))
+        .isEqualTo(interfaceWithCompanion("a", 0));
+    assertThat(info.getInterfaceWithCompanionList().get(1))
+        .isEqualTo(interfaceWithCompanion("b", 1));
+  }
+
+  private DesugarDeps.InterfaceWithCompanion interfaceWithCompanion(String origin, int count) {
+    return DesugarDeps.InterfaceWithCompanion.newBuilder()
+        .setOrigin(wrapType(origin))
+        .setNumDefaultMethods(count)
+        .build();
+  }
+
+  private DesugarDeps.InterfaceDetails interfaceDetails(String originName, String... interfaces) {
+    return InterfaceDetails.newBuilder()
+        .setOrigin(wrapType(originName))
+        .addAllExtendedInterface(
+            Arrays.stream(interfaces)
+                .map(MetadataCollectorTest::wrapType)
+                .collect(toImmutableList()))
+        .build();
+  }
+
+  private DesugarDeps.Dependency dependency(String origin, String target) {
+    return DesugarDeps.Dependency.newBuilder()
+        .setOrigin(wrapType(origin))
+        .setTarget(wrapType(target))
+        .build();
   }
 
   private static DesugarDeps.Type wrapType(String name) {
diff --git a/src/tools/android/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollector.java b/src/tools/android/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollector.java
index 2a8a0e3..048e588 100644
--- a/src/tools/android/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollector.java
+++ b/src/tools/android/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollector.java
@@ -22,13 +22,21 @@
 import com.google.devtools.build.android.desugar.proto.DesugarDeps.InterfaceDetails;
 import com.google.devtools.build.android.desugar.proto.DesugarDeps.InterfaceWithCompanion;
 import com.google.devtools.build.android.r8.DependencyCollector;
+import java.util.ArrayList;
+import java.util.Comparator;
 import javax.annotation.Nullable;
 
 /** Dependency collector that emits collected metadata as a {@link DesugarDepsInfo} proto. */
 public final class MetadataCollector implements DependencyCollector {
 
   private final boolean tolerateMissingDeps;
-  private final DesugarDepsInfo.Builder info = DesugarDeps.DesugarDepsInfo.newBuilder();
+
+  private final ArrayList<DesugarDeps.Dependency> assumePresents = new ArrayList<>();
+  private final ArrayList<DesugarDeps.Dependency> missingInterfaces = new ArrayList<>();
+  private final ArrayList<DesugarDeps.InterfaceDetails> interfacesWithSupertypes =
+      new ArrayList<>();
+  private final ArrayList<DesugarDeps.InterfaceWithCompanion> interfacesWithCompanion =
+      new ArrayList<>();
 
   public MetadataCollector(boolean tolerateMissingDeps) {
     this.tolerateMissingDeps = tolerateMissingDeps;
@@ -43,8 +51,8 @@
   public void assumeCompanionClass(String origin, String target) {
     checkArgument(
         isInterfaceCompanionClass(target), "target not a companion: %s -> %s", origin, target);
-    info.addAssumePresent(
-        Dependency.newBuilder().setOrigin(wrapType(origin)).setTarget(wrapType(target)));
+    assumePresents.add(
+        Dependency.newBuilder().setOrigin(wrapType(origin)).setTarget(wrapType(target)).build());
   }
 
   @Override
@@ -59,37 +67,70 @@
         "Couldn't find interface %s on the classpath for desugaring %s",
         target,
         origin);
-    info.addMissingInterface(
-        Dependency.newBuilder().setOrigin(wrapType(origin)).setTarget(wrapType(target)));
+    missingInterfaces.add(
+        Dependency.newBuilder().setOrigin(wrapType(origin)).setTarget(wrapType(target)).build());
   }
 
   @Override
   public void recordExtendedInterfaces(String origin, String... targets) {
     if (targets.length > 0) {
       InterfaceDetails.Builder details = InterfaceDetails.newBuilder().setOrigin(wrapType(origin));
+      ArrayList<DesugarDeps.Type> types = new ArrayList<>();
       for (String target : targets) {
-        details.addExtendedInterface(wrapType(target));
+        types.add(wrapType(target));
       }
-      info.addInterfaceWithSupertypes(details);
+      types.sort(Comparator.comparing(DesugarDeps.Type::getBinaryName));
+      details.addAllExtendedInterface(types);
+      interfacesWithSupertypes.add(details.build());
     }
   }
 
   @Override
   public void recordDefaultMethods(String origin, int count) {
     checkArgument(!isInterfaceCompanionClass(origin), "seems to be a companion: %s", origin);
-    info.addInterfaceWithCompanion(
+    interfacesWithCompanion.add(
         InterfaceWithCompanion.newBuilder()
             .setOrigin(wrapType(origin))
-            .setNumDefaultMethods(count));
+            .setNumDefaultMethods(count)
+            .build());
   }
 
   @Override
   @Nullable
   public byte[] toByteArray() {
-    DesugarDepsInfo result = info.build();
-    return DesugarDepsInfo.getDefaultInstance().equals(result) ? null : result.toByteArray();
+    DesugarDeps.DesugarDepsInfo result = buildInfo();
+    return DesugarDeps.DesugarDepsInfo.getDefaultInstance().equals(result)
+        ? null
+        : result.toByteArray();
   }
 
+  private DesugarDeps.DesugarDepsInfo buildInfo() {
+
+    // Sort these for determinism.
+    assumePresents.sort(dependencyComparator);
+    missingInterfaces.sort(dependencyComparator);
+    interfacesWithSupertypes.sort(interfaceDetailComparator);
+    interfacesWithCompanion.sort(interFaceWithCompanionComparator);
+
+    DesugarDeps.DesugarDepsInfo.Builder info = DesugarDeps.DesugarDepsInfo.newBuilder();
+    info.addAllAssumePresent(assumePresents);
+    info.addAllMissingInterface(missingInterfaces);
+    info.addAllInterfaceWithSupertypes(interfacesWithSupertypes);
+    info.addAllInterfaceWithCompanion(interfacesWithCompanion);
+
+    return info.build();
+  }
+
+  private static final Comparator<? super DesugarDeps.Dependency> dependencyComparator =
+      Comparator.comparing((DesugarDeps.Dependency o) -> o.getOrigin().getBinaryName())
+          .thenComparing((DesugarDeps.Dependency o) -> o.getTarget().getBinaryName());
+
+  private static final Comparator<? super DesugarDeps.InterfaceDetails> interfaceDetailComparator =
+      Comparator.comparing((DesugarDeps.InterfaceDetails o) -> o.getOrigin().getBinaryName());
+
+  private static final Comparator<? super DesugarDeps.InterfaceWithCompanion>
+      interFaceWithCompanionComparator = Comparator.comparing(o -> o.getOrigin().getBinaryName());
+
   private static DesugarDeps.Type wrapType(String internalName) {
     return DesugarDeps.Type.newBuilder().setBinaryName(internalName).build();
   }