diff --git a/src/test/java/com/google/devtools/build/lib/BUILD b/src/test/java/com/google/devtools/build/lib/BUILD
index 706db4f..fe8ec3a 100644
--- a/src/test/java/com/google/devtools/build/lib/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/BUILD
@@ -1315,6 +1315,7 @@
         "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/lib/actions:localhost_capacity",
         "//src/main/java/com/google/devtools/build/lib/clock",
+        "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/exec/local",
         "//src/main/java/com/google/devtools/build/lib/exec/local:options",
         "//src/main/java/com/google/devtools/build/lib/rules/apple",
diff --git a/src/test/java/com/google/devtools/build/lib/exec/util/SpawnBuilder.java b/src/test/java/com/google/devtools/build/lib/exec/util/SpawnBuilder.java
index 88ddf2c..cce2e41 100644
--- a/src/test/java/com/google/devtools/build/lib/exec/util/SpawnBuilder.java
+++ b/src/test/java/com/google/devtools/build/lib/exec/util/SpawnBuilder.java
@@ -16,6 +16,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.ActionExecutionMetadata;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
@@ -27,6 +28,8 @@
 import com.google.devtools.build.lib.actions.SimpleSpawn;
 import com.google.devtools.build.lib.actions.Spawn;
 import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
@@ -45,7 +48,7 @@
   private final Map<String, String> environment = new HashMap<>();
   private final Map<String, String> executionInfo = new HashMap<>();
   private ImmutableMap<String, String> execProperties = ImmutableMap.of();
-  private final List<ActionInput> inputs = new ArrayList<>();
+  private final NestedSetBuilder<ActionInput> inputs = NestedSetBuilder.stableOrder();
   private final List<ActionInput> outputs = new ArrayList<>();
   private final Map<Artifact, ImmutableList<FilesetOutputSymlink>> filesetMappings =
       new HashMap<>();
@@ -66,9 +69,9 @@
         ImmutableMap.copyOf(executionInfo),
         runfilesSupplier,
         ImmutableMap.copyOf(filesetMappings),
-        ImmutableList.copyOf(inputs),
-        /*tools=*/ ImmutableList.<Artifact>of(),
-        ImmutableList.copyOf(outputs),
+        inputs.build(),
+        /*tools=*/ NestedSetBuilder.emptySet(Order.STABLE_ORDER),
+        ImmutableSet.copyOf(outputs),
         ResourceSet.ZERO);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/remote/BUILD b/src/test/java/com/google/devtools/build/lib/remote/BUILD
index 7421605..02c3d79 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/remote/BUILD
@@ -50,6 +50,7 @@
         "//src/main/java/com/google/devtools/build/lib/authandtls",
         "//src/main/java/com/google/devtools/build/lib/buildeventstream",
         "//src/main/java/com/google/devtools/build/lib/clock",
+        "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/remote",
         "//src/main/java/com/google/devtools/build/lib/remote/common",
         "//src/main/java/com/google/devtools/build/lib/remote/disk",
diff --git a/src/test/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutionClientTest.java b/src/test/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutionClientTest.java
index c498b47..90fc834 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutionClientTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutionClientTest.java
@@ -58,6 +58,8 @@
 import com.google.devtools.build.lib.authandtls.AuthAndTLSOptions;
 import com.google.devtools.build.lib.authandtls.GoogleAuthUtils;
 import com.google.devtools.build.lib.clock.JavaClock;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.exec.ExecutionOptions;
 import com.google.devtools.build.lib.exec.util.FakeOwner;
 import com.google.devtools.build.lib.remote.RemoteRetrier.ExponentialBackoff;
@@ -167,8 +169,9 @@
             ImmutableList.of("/bin/echo", "Hi!"),
             ImmutableMap.of("VARIABLE", "value"),
             /*executionInfo=*/ ImmutableMap.<String, String>of(),
-            /*inputs=*/ ImmutableList.of(ActionInputHelper.fromPath("input")),
-            /*outputs=*/ ImmutableList.<ActionInput>of(
+            /*inputs=*/ NestedSetBuilder.create(
+                Order.STABLE_ORDER, ActionInputHelper.fromPath("input")),
+            /*outputs=*/ ImmutableSet.<ActionInput>of(
                 new ActionInput() {
                   @Override
                   public String getExecPathString() {
@@ -259,7 +262,8 @@
             logDir,
             /* filesToDownload= */ ImmutableSet.of());
 
-    inputDigest = fakeFileCache.createScratchInput(simpleSpawn.getInputFiles().get(0), "xyz");
+    inputDigest =
+        fakeFileCache.createScratchInput(simpleSpawn.getInputFiles().getSingleton(), "xyz");
     command =
         Command.newBuilder()
             .addAllArguments(ImmutableList.of("/bin/echo", "Hi!"))
diff --git a/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java b/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java
index 5c93a05..eca1c7e 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnCacheTest.java
@@ -48,6 +48,8 @@
 import com.google.devtools.build.lib.actions.SpawnResult.Status;
 import com.google.devtools.build.lib.actions.cache.MetadataInjector;
 import com.google.devtools.build.lib.clock.JavaClock;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.events.Reporter;
@@ -216,8 +218,9 @@
         ImmutableList.of("/bin/echo", "Hi!"),
         ImmutableMap.of("VARIABLE", "value"),
         executionInfo,
-        /* inputs= */ ImmutableList.of(ActionInputHelper.fromPath("input")),
-        /* outputs= */ ImmutableList.of(ActionInputHelper.fromPath("/random/file")),
+        /* inputs= */ NestedSetBuilder.create(
+            Order.STABLE_ORDER, ActionInputHelper.fromPath("input")),
+        /* outputs= */ ImmutableSet.of(ActionInputHelper.fromPath("/random/file")),
         ResourceSet.ZERO);
   }
 
@@ -254,7 +257,7 @@
     reporter.addHandler(eventHandler);
     cache = remoteSpawnCacheWithOptions(options);
 
-    fakeFileCache.createScratchInput(simpleSpawn.getInputFiles().get(0), "xyz");
+    fakeFileCache.createScratchInput(simpleSpawn.getInputFiles().getSingleton(), "xyz");
   }
 
   @SuppressWarnings("unchecked")
diff --git a/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnRunnerTest.java b/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnRunnerTest.java
index cc2d9e1..44b12d2 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnRunnerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/RemoteSpawnRunnerTest.java
@@ -55,6 +55,8 @@
 import com.google.devtools.build.lib.actions.SpawnResult.Status;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.clock.JavaClock;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.events.Reporter;
@@ -836,8 +838,8 @@
             /*arguments=*/ ImmutableList.of(),
             /*environment=*/ ImmutableMap.of(),
             /*executionInfo=*/ ImmutableMap.of(),
-            /*inputs=*/ ImmutableList.of(input),
-            /*outputs=*/ ImmutableList.<ActionInput>of(),
+            /*inputs=*/ NestedSetBuilder.create(Order.STABLE_ORDER, input),
+            /*outputs=*/ ImmutableSet.<ActionInput>of(),
             ResourceSet.ZERO);
     SpawnExecutionContext policy =
         new FakeSpawnExecutionContext(spawn, fakeFileCache, execRoot, outErr);
@@ -973,8 +975,8 @@
         /*arguments=*/ ImmutableList.of(),
         /*environment=*/ ImmutableMap.of(),
         /*executionInfo=*/ executionInfo,
-        /*inputs=*/ ImmutableList.of(),
-        /*outputs=*/ ImmutableList.copyOf(outputs),
+        /*inputs=*/ NestedSetBuilder.emptySet(Order.STABLE_ORDER),
+        /*outputs=*/ ImmutableSet.copyOf(outputs),
         ResourceSet.ZERO);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java b/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java
index 1a0ce10..f9c7b96 100644
--- a/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/standalone/StandaloneSpawnStrategyTest.java
@@ -19,6 +19,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
@@ -38,6 +39,8 @@
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
 import com.google.devtools.build.lib.clock.BlazeClock;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.events.PrintingEventHandler;
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.exec.BinTools;
@@ -158,8 +161,8 @@
         ImmutableList.copyOf(arguments),
         /*environment=*/ ImmutableMap.of(),
         /*executionInfo=*/ ImmutableMap.of(),
-        /*inputs=*/ ImmutableList.of(),
-        /*outputs=*/ ImmutableList.of(),
+        /*inputs=*/ NestedSetBuilder.emptySet(Order.STABLE_ORDER),
+        /*outputs=*/ ImmutableSet.of(),
         ResourceSet.ZERO);
   }
 
@@ -240,14 +243,15 @@
       // down where that env var is coming from.
       return;
     }
-    Spawn spawn = new SimpleSpawn(
-        new ActionsTestUtil.NullAction(),
-        ImmutableList.of("/usr/bin/env"),
-        /*environment=*/ ImmutableMap.of("foo", "bar", "baz", "boo"),
-        /*executionInfo=*/ ImmutableMap.of(),
-        /*inputs=*/ ImmutableList.of(),
-        /*outputs=*/ ImmutableList.of(),
-        ResourceSet.ZERO);
+    Spawn spawn =
+        new SimpleSpawn(
+            new ActionsTestUtil.NullAction(),
+            ImmutableList.of("/usr/bin/env"),
+            /*environment=*/ ImmutableMap.of("foo", "bar", "baz", "boo"),
+            /*executionInfo=*/ ImmutableMap.of(),
+            /*inputs=*/ NestedSetBuilder.emptySet(Order.STABLE_ORDER),
+            /*outputs=*/ ImmutableSet.of(),
+            ResourceSet.ZERO);
     run(spawn);
     assertThat(Sets.newHashSet(out().split("\n"))).isEqualTo(Sets.newHashSet("foo=bar", "baz=boo"));
   }