diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxRunner.java
index 40d9623..c9c330d 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxRunner.java
@@ -50,7 +50,7 @@
       Set<Path> inaccessiblePaths,
       Path runUnderPath,
       boolean verboseFailures) {
-    super(sandboxPath, sandboxExecRoot, verboseFailures);
+    super(sandboxExecRoot, verboseFailures);
     this.sandboxExecRoot = sandboxExecRoot;
     this.argumentsFilePath = sandboxPath.getRelative("sandbox.sb");
     this.writableDirs = writableDirs;
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java
index 592ea3d..bb4a82f 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java
@@ -31,6 +31,7 @@
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.config.RunUnder;
 import com.google.devtools.build.lib.buildtool.BuildRequest;
+import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.rules.test.TestRunnerAction;
 import com.google.devtools.build.lib.shell.Command;
 import com.google.devtools.build.lib.shell.CommandException;
@@ -51,7 +52,6 @@
 import java.util.Map;
 import java.util.Set;
 import java.util.UUID;
-import java.util.concurrent.ExecutorService;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
 
@@ -78,7 +78,6 @@
       BuildRequest buildRequest,
       Map<String, String> clientEnv,
       BlazeDirectories blazeDirs,
-      ExecutorService backgroundWorkers,
       boolean verboseFailures,
       String productName,
       ImmutableList<Path> confPaths,
@@ -86,7 +85,6 @@
     super(
         buildRequest,
         blazeDirs,
-        backgroundWorkers,
         verboseFailures,
         buildRequest.getOptions(SandboxOptions.class));
     this.clientEnv = ImmutableMap.copyOf(clientEnv);
@@ -103,7 +101,6 @@
       BuildRequest buildRequest,
       Map<String, String> clientEnv,
       BlazeDirectories blazeDirs,
-      ExecutorService backgroundWorkers,
       boolean verboseFailures,
       String productName)
       throws IOException {
@@ -122,7 +119,6 @@
         buildRequest,
         clientEnv,
         blazeDirs,
-        backgroundWorkers,
         verboseFailures,
         productName,
         writablePaths.build(),
@@ -213,14 +209,30 @@
             getInaccessiblePaths(),
             runUnderPath,
             verboseFailures);
-    runSpawn(
-        spawn,
-        actionExecutionContext,
-        spawnEnvironment,
-        hardlinkedExecRoot,
-        outputs,
-        runner,
-        writeOutputFiles);
+    try {
+      runSpawn(
+          spawn,
+          actionExecutionContext,
+          spawnEnvironment,
+          hardlinkedExecRoot,
+          outputs,
+          runner,
+          writeOutputFiles);
+    } finally {
+      if (!sandboxDebug) {
+        try {
+          FileSystemUtils.deleteTree(sandboxPath);
+        } catch (IOException e) {
+          executor
+              .getEventHandler()
+              .handle(
+                  Event.error(
+                      String.format(
+                          "Cannot delete sandbox directory after action execution: %s (%s)",
+                          sandboxPath.getPathString(), e)));
+        }
+      }
+    }
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxRunner.java
index c3d36a6..9c5649d 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxRunner.java
@@ -58,7 +58,7 @@
       ImmutableSet<Path> bindMounts,
       boolean verboseFailures,
       boolean sandboxDebug) {
-    super(sandboxPath, sandboxExecRoot, verboseFailures);
+    super(sandboxExecRoot, verboseFailures);
     this.execRoot = execRoot;
     this.sandboxExecRoot = sandboxExecRoot;
     this.sandboxTempDir = sandboxTempDir;
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
index b052bdb..3ccb517 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
@@ -24,13 +24,14 @@
 import com.google.devtools.build.lib.actions.UserExecException;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.buildtool.BuildRequest;
+import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.runtime.CommandEnvironment;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.io.IOException;
 import java.util.Set;
 import java.util.UUID;
-import java.util.concurrent.ExecutorService;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
 
@@ -63,14 +64,12 @@
   LinuxSandboxedStrategy(
       BuildRequest buildRequest,
       BlazeDirectories blazeDirs,
-      ExecutorService backgroundWorkers,
       boolean verboseFailures,
       String productName,
       boolean fullySupported) {
     super(
         buildRequest,
         blazeDirs,
-        backgroundWorkers,
         verboseFailures,
         buildRequest.getOptions(SandboxOptions.class));
     this.sandboxOptions = buildRequest.getOptions(SandboxOptions.class);
@@ -123,14 +122,30 @@
     }
 
     SandboxRunner runner = getSandboxRunner(spawn, sandboxPath, sandboxExecRoot, sandboxTempDir);
-    runSpawn(
-        spawn,
-        actionExecutionContext,
-        spawn.getEnvironment(),
-        symlinkedExecRoot,
-        outputs,
-        runner,
-        writeOutputFiles);
+    try {
+      runSpawn(
+          spawn,
+          actionExecutionContext,
+          spawn.getEnvironment(),
+          symlinkedExecRoot,
+          outputs,
+          runner,
+          writeOutputFiles);
+    } finally {
+      if (!sandboxOptions.sandboxDebug) {
+        try {
+          FileSystemUtils.deleteTree(sandboxPath);
+        } catch (IOException e) {
+          executor
+              .getEventHandler()
+              .handle(
+                  Event.error(
+                      String.format(
+                          "Cannot delete sandbox directory after action execution: %s (%s)",
+                          sandboxPath.getPathString(), e)));
+        }
+      }
+    }
   }
 
   private SandboxRunner getSandboxRunner(
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperRunner.java
index 0122b64..f871ea7 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/ProcessWrapperRunner.java
@@ -33,7 +33,7 @@
 
   ProcessWrapperRunner(
       Path execRoot, Path sandboxPath, Path sandboxExecRoot, boolean verboseFailures) {
-    super(sandboxPath, sandboxExecRoot, verboseFailures);
+    super(sandboxExecRoot, verboseFailures);
     this.execRoot = execRoot;
     this.sandboxExecRoot = sandboxExecRoot;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxActionContextProvider.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxActionContextProvider.java
index 8153f1d..1efa891 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxActionContextProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxActionContextProvider.java
@@ -23,7 +23,6 @@
 import com.google.devtools.build.lib.runtime.CommandEnvironment;
 import com.google.devtools.build.lib.util.OS;
 import java.io.IOException;
-import java.util.concurrent.ExecutorService;
 
 /**
  * Provides the sandboxed spawn strategy.
@@ -43,8 +42,7 @@
   }
 
   public static SandboxActionContextProvider create(
-      CommandEnvironment env, BuildRequest buildRequest, ExecutorService backgroundWorkers)
-      throws IOException {
+      CommandEnvironment env, BuildRequest buildRequest) throws IOException {
     boolean verboseFailures = buildRequest.getOptions(ExecutionOptions.class).verboseFailures;
     ImmutableList.Builder<ActionContext> contexts = ImmutableList.builder();
 
@@ -60,7 +58,6 @@
               new LinuxSandboxedStrategy(
                   buildRequest,
                   env.getDirectories(),
-                  backgroundWorkers,
                   verboseFailures,
                   env.getRuntime().getProductName(),
                   fullySupported));
@@ -73,7 +70,6 @@
                   buildRequest,
                   env.getClientEnv(),
                   env.getDirectories(),
-                  backgroundWorkers,
                   verboseFailures,
                   env.getRuntime().getProductName()));
         }
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java
index de018b1..211a6a6 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxHelpers.java
@@ -26,45 +26,16 @@
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.buildtool.BuildRequest;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.standalone.StandaloneSpawnStrategy;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import java.io.IOException;
 import java.util.UUID;
-import java.util.concurrent.ExecutorService;
 import java.util.concurrent.atomic.AtomicInteger;
 
 /** Helper methods that are shared by the different sandboxing strategies in this package. */
 final class SandboxHelpers {
 
-  static void lazyCleanup(
-      ExecutorService backgroundWorkers,
-      final EventHandler eventHandler,
-      final SandboxRunner runner) {
-    // By deleting the sandbox directory in the background, we avoid having to wait for it to
-    // complete before returning from the action, which improves performance.
-    backgroundWorkers.execute(
-        new Runnable() {
-          @Override
-          public void run() {
-            try {
-              runner.cleanup();
-            } catch (IOException e) {
-              // Can't do anything except logging here. SandboxModule#afterCommand will try again
-              // and alert the user if cleanup still fails.
-              eventHandler.handle(
-                  Event.warn(
-                      String.format(
-                          "Could not delete sandbox directory after action execution: %s (%s)",
-                          runner.getSandboxPath(), e)));
-            }
-          }
-        });
-  }
-
   static void fallbackToNonSandboxedExecution(
       Spawn spawn, ActionExecutionContext actionExecutionContext, Executor executor)
       throws ExecException {
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java
index df28aaf..8334e00 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java
@@ -16,22 +16,16 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.eventbus.Subscribe;
-import com.google.common.util.concurrent.ThreadFactoryBuilder;
 import com.google.devtools.build.lib.actions.ActionContextConsumer;
 import com.google.devtools.build.lib.actions.ActionContextProvider;
 import com.google.devtools.build.lib.buildtool.BuildRequest;
 import com.google.devtools.build.lib.buildtool.buildevent.BuildStartingEvent;
-import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.runtime.BlazeModule;
 import com.google.devtools.build.lib.runtime.Command;
 import com.google.devtools.build.lib.runtime.CommandEnvironment;
 import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.lib.vfs.FileSystemUtils;
-import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.common.options.OptionsBase;
 import java.io.IOException;
-import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Executors;
 
 /**
  * This module provides the Sandbox spawn strategy.
@@ -40,18 +34,14 @@
   // Per-command state
   private CommandEnvironment env;
   private BuildRequest buildRequest;
-  private ExecutorService backgroundWorkers;
-  private SandboxOptions sandboxOptions;
 
   @Override
   public Iterable<ActionContextProvider> getActionContextProviders() {
     Preconditions.checkNotNull(env);
     Preconditions.checkNotNull(buildRequest);
-    Preconditions.checkNotNull(backgroundWorkers);
-    sandboxOptions = buildRequest.getOptions(SandboxOptions.class);
     try {
       return ImmutableList.<ActionContextProvider>of(
-          SandboxActionContextProvider.create(env, buildRequest, backgroundWorkers));
+          SandboxActionContextProvider.create(env, buildRequest));
     } catch (IOException e) {
       throw new IllegalStateException(e);
     }
@@ -72,55 +62,14 @@
 
   @Override
   public void beforeCommand(Command command, CommandEnvironment env) {
-    backgroundWorkers =
-        Executors.newCachedThreadPool(
-            new ThreadFactoryBuilder().setNameFormat("sandbox-background-worker-%d").build());
     this.env = env;
     env.getEventBus().register(this);
   }
 
   @Override
   public void afterCommand() {
-    // We want to make sure that all sandbox directories are deleted after a command finishes or at
-    // least the user gets notified if some of them can't be deleted. However we can't rely on the
-    // background workers for that, because a) they can't log, and b) if a directory is undeletable,
-    // the Runnable might never finish. So we cancel them and delete the remaining directories here,
-    // where we have more control.
-    backgroundWorkers.shutdownNow();
-    if (sandboxOptions != null && !sandboxOptions.sandboxDebug) {
-      Path sandboxRoot =
-          env.getDirectories()
-              .getOutputBase()
-              .getRelative(env.getRuntime().getProductName() + "-sandbox");
-      if (sandboxRoot.exists()) {
-        try {
-          for (Path child : sandboxRoot.getDirectoryEntries()) {
-            try {
-              FileSystemUtils.deleteTree(child);
-            } catch (IOException e) {
-              env.getReporter()
-                  .handle(
-                      Event.warn(
-                          String.format(
-                              "Could not delete sandbox directory: %s (%s)",
-                              child.getPathString(), e)));
-            }
-          }
-          sandboxRoot.delete();
-        } catch (IOException e) {
-          env.getReporter()
-              .handle(
-                  Event.warn(
-                      String.format(
-                          "Could not delete %s directory: %s", sandboxRoot.getBaseName(), e)));
-        }
-      }
-    }
-
     env = null;
     buildRequest = null;
-    backgroundWorkers = null;
-    sandboxOptions = null;
   }
 
   @Subscribe
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxRunner.java
index dabbf66..b20da1b 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxRunner.java
@@ -23,7 +23,6 @@
 import com.google.devtools.build.lib.shell.TerminationStatus;
 import com.google.devtools.build.lib.util.CommandFailureUtils;
 import com.google.devtools.build.lib.util.io.OutErr;
-import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import java.io.IOException;
 import java.util.Arrays;
@@ -32,12 +31,11 @@
 
 /** A common interface of all sandbox runners, no matter which platform they're working on. */
 abstract class SandboxRunner {
-  private final Path sandboxPath;
+
   private final boolean verboseFailures;
   private final Path sandboxExecRoot;
 
-  SandboxRunner(Path sandboxPath, Path sandboxExecRoot, boolean verboseFailures) {
-    this.sandboxPath = sandboxPath;
+  SandboxRunner(Path sandboxExecRoot, boolean verboseFailures) {
     this.sandboxExecRoot = sandboxExecRoot;
     this.verboseFailures = verboseFailures;
   }
@@ -116,14 +114,4 @@
   protected int getSignalOnTimeout() {
     return 14; /* SIGALRM */
   }
-
-  void cleanup() throws IOException {
-    if (sandboxPath.exists()) {
-      FileSystemUtils.deleteTree(sandboxPath);
-    }
-  }
-
-  Path getSandboxPath() {
-    return sandboxPath;
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java
index b5d787c..77334e9 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java
@@ -27,13 +27,11 @@
 import com.google.devtools.build.lib.buildtool.BuildRequest;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.io.IOException;
 import java.util.Map;
 import java.util.Set;
-import java.util.concurrent.ExecutorService;
 import java.util.concurrent.atomic.AtomicReference;
 
 /** Abstract common ancestor for sandbox strategies implementing the common parts. */
@@ -42,7 +40,6 @@
   private final BuildRequest buildRequest;
   private final BlazeDirectories blazeDirs;
   private final Path execRoot;
-  private final ExecutorService backgroundWorkers;
   private final boolean verboseFailures;
   private final SandboxOptions sandboxOptions;
   private final SpawnHelpers spawnHelpers;
@@ -50,13 +47,11 @@
   public SandboxStrategy(
       BuildRequest buildRequest,
       BlazeDirectories blazeDirs,
-      ExecutorService backgroundWorkers,
       boolean verboseFailures,
       SandboxOptions sandboxOptions) {
     this.buildRequest = buildRequest;
     this.blazeDirs = blazeDirs;
     this.execRoot = blazeDirs.getExecRoot();
-    this.backgroundWorkers = Preconditions.checkNotNull(backgroundWorkers);
     this.verboseFailures = verboseFailures;
     this.sandboxOptions = sandboxOptions;
     this.spawnHelpers = new SpawnHelpers(blazeDirs.getExecRoot());
@@ -98,9 +93,6 @@
                       + e));
         }
       }
-      if (!sandboxOptions.sandboxDebug) {
-        SandboxHelpers.lazyCleanup(backgroundWorkers, eventHandler, runner);
-      }
     }
 
     if (Thread.interrupted()) {