diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 41c4964..d5e9066 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -962,6 +962,11 @@
     return tracksStateForIncrementality();
   }
 
+  @ForOverride
+  protected boolean shouldDeleteActionNodesWhenDroppingAnalysis() {
+    return true;
+  }
+
   /**
    * If not null, this is the only source root in the build, corresponding to the single element in
    * a single-element package path. Such a single-source-root build need not plant the execroot
@@ -1115,8 +1120,12 @@
   protected final void deleteAnalysisNodes() {
     memoizingEvaluator.delete(
         keepBuildConfigurationNodesWhenDiscardingAnalysis
-            ? SkyframeExecutor::basicAnalysisInvalidatingPredicate
-            : SkyframeExecutor::fullAnalysisInvalidatingPredicate);
+            ? shouldDeleteActionNodesWhenDroppingAnalysis()
+                ? SkyframeExecutor::basicAnalysisInvalidatingPredicateWithActions
+                : SkyframeExecutor::basicAnalysisInvalidatingPredicate
+            : shouldDeleteActionNodesWhenDroppingAnalysis()
+                ? SkyframeExecutor::fullAnalysisInvalidatingPredicateWithActions
+                : SkyframeExecutor::fullAnalysisInvalidatingPredicate);
   }
 
   // We delete any value that can hold an action -- all subclasses of ActionLookupKey.
@@ -1125,10 +1134,19 @@
     return key instanceof ArtifactNestedSetKey || key instanceof ActionLookupKey;
   }
 
+  // Also remove ActionLookupData since all such nodes depend on ActionLookupKey nodes and deleting
+  // en masse is cheaper than deleting via graph traversal (b/192863968).
+  private static boolean basicAnalysisInvalidatingPredicateWithActions(SkyKey key) {
+    return basicAnalysisInvalidatingPredicate(key) || key instanceof ActionLookupData;
+  }
+
   // We may also want to remove BuildConfigurationValue.Keys to fix a minor memory leak there.
   private static boolean fullAnalysisInvalidatingPredicate(SkyKey key) {
-    return key instanceof ArtifactNestedSetKey
-        || key instanceof ActionLookupKey
+    return basicAnalysisInvalidatingPredicate(key) || key instanceof BuildConfigurationValue.Key;
+  }
+
+  private static boolean fullAnalysisInvalidatingPredicateWithActions(SkyKey key) {
+    return basicAnalysisInvalidatingPredicateWithActions(key)
         || key instanceof BuildConfigurationValue.Key;
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index 843eba5..d403651 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
 import com.google.errorprone.annotations.ForOverride;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 import java.util.Set;
 import javax.annotation.Nullable;
@@ -458,21 +459,21 @@
   }
 
   @Override
-  public synchronized Set<SkyKey> getReverseDepsForDoneEntry() {
+  public synchronized Collection<SkyKey> getReverseDepsForDoneEntry() {
     assertKeepRdeps();
     Preconditions.checkState(isDone(), "Called on not done %s", this);
-    return ReverseDepsUtility.getReverseDeps(this);
+    return ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ true);
   }
 
   @Override
-  public synchronized Set<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
+  public synchronized Collection<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
     assertKeepRdeps();
     if (!isDone()) {
       // This consolidation loses information about pending reverse deps to signal, but that is
       // unimportant since this node is being deleted.
       ReverseDepsUtility.consolidateDataAndReturnNewElements(this, getOpToStoreBare());
     }
-    return ReverseDepsUtility.getReverseDeps(this);
+    return ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ false);
   }
 
   @Override
@@ -525,7 +526,7 @@
       this.directDeps = null;
       return new MarkedDirtyResult(
           KeepEdgesPolicy.ALL.equals(keepEdges())
-              ? ReverseDepsUtility.getReverseDeps(this)
+              ? ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ true)
               : ImmutableList.of());
     }
     if (dirtyType.equals(DirtyType.FORCE_REBUILD)) {
@@ -723,7 +724,7 @@
     newEntry.value = value;
     newEntry.lastChangedVersion = this.lastChangedVersion;
     newEntry.lastEvaluatedVersion = this.lastEvaluatedVersion;
-    for (SkyKey reverseDep : ReverseDepsUtility.getReverseDeps(this)) {
+    for (SkyKey reverseDep : ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ true)) {
       ReverseDepsUtility.addReverseDep(newEntry, reverseDep);
     }
     newEntry.directDeps = directDeps;
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 2dbd3e9..fc30181 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -261,8 +261,6 @@
                 // normal rdep. That information is used to remove this node as an rdep from the
                 // correct list of rdeps in the child -- because of our compact storage of rdeps,
                 // checking which list contains this parent could be expensive.
-                Set<SkyKey> signalingDeps =
-                    entry.isDone() ? ImmutableSet.of() : entry.getTemporaryDirectDeps().toSet();
                 Iterable<SkyKey> directDeps;
                 try {
                   directDeps =
@@ -277,29 +275,44 @@
                           + entry,
                       e);
                 }
+                // No need to do reverse dep surgery on nodes that are deleted/about to be deleted
+                // anyway.
                 Map<SkyKey, ? extends NodeEntry> depMap =
-                    graph.getBatch(key, Reason.INVALIDATION, directDeps);
-                for (Map.Entry<SkyKey, ? extends NodeEntry> directDepEntry : depMap.entrySet()) {
-                  NodeEntry dep = directDepEntry.getValue();
-                  if (dep != null) {
-                    if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) {
-                      try {
-                        dep.removeReverseDep(key);
-                      } catch (InterruptedException e) {
-                        throw new IllegalStateException(
-                            "Deletion cannot happen on a graph that may have blocking "
-                                + "operations: "
-                                + key
-                                + ", "
-                                + entry,
-                            e);
+                    graph.getBatch(
+                        key,
+                        Reason.INVALIDATION,
+                        Iterables.filter(
+                            directDeps,
+                            k ->
+                                !visited.contains(k)
+                                    && !pendingVisitations.contains(
+                                        Pair.of(k, InvalidationType.DELETED))));
+                if (!depMap.isEmpty()) {
+                  // Don't do set operation below for signalingDeps if there's no work.
+                  Set<SkyKey> signalingDeps =
+                      entry.isDone() ? ImmutableSet.of() : entry.getTemporaryDirectDeps().toSet();
+                  for (Map.Entry<SkyKey, ? extends NodeEntry> directDepEntry : depMap.entrySet()) {
+                    NodeEntry dep = directDepEntry.getValue();
+                    if (dep != null) {
+                      if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) {
+                        try {
+                          dep.removeReverseDep(key);
+                        } catch (InterruptedException e) {
+                          throw new IllegalStateException(
+                              "Deletion cannot happen on a graph that may have blocking "
+                                  + "operations: "
+                                  + key
+                                  + ", "
+                                  + entry,
+                              e);
+                        }
+                      } else {
+                        // This step is not strictly necessary, since all in-progress nodes are
+                        // deleted during graph cleaning, which happens in a single
+                        // DeletingNodeVisitor visitation, aka the one right now. We leave this
+                        // here in case the logic changes.
+                        dep.removeInProgressReverseDep(key);
                       }
-                    } else {
-                      // This step is not strictly necessary, since all in-progress nodes are
-                      // deleted during graph cleaning, which happens in a single
-                      // DeletingNodeVisitor visitation, aka the one right now. We leave this
-                      // here in case the logic changes.
-                      dep.removeInProgressReverseDep(key);
                     }
                   }
                 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
index 7bcce44..b6eafd6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
@@ -15,6 +15,7 @@
 
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
@@ -123,7 +124,8 @@
     maybeDelayReverseDepOp(entry, reverseDep, Op.REMOVE);
   }
 
-  static ImmutableSet<SkyKey> getReverseDeps(InMemoryNodeEntry entry) {
+  static ImmutableCollection<SkyKey> getReverseDeps(
+      InMemoryNodeEntry entry, boolean checkConsistency) {
     consolidateData(entry);
 
     // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side
@@ -134,6 +136,9 @@
     } else {
       @SuppressWarnings("unchecked")
       List<SkyKey> reverseDeps = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil();
+      if (!checkConsistency) {
+        return ImmutableList.copyOf(reverseDeps);
+      }
       ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
       maybeAssertReverseDepsConsistency(
           set.size() == reverseDeps.size(),
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 5b348b8..5cf73e9 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -463,7 +463,7 @@
     SkyKey[] values = constructLargeGraph(graphSize);
     eval(/*keepGoing=*/false, values);
     final Thread mainThread = Thread.currentThread();
-    for (int run = 0; run < tries; run++) {
+    for (int run = 0; run < tries + 1; run++) {
       Set<Pair<SkyKey, InvalidationType>> valuesToInvalidate = getValuesToInvalidate(values);
       // Find how many invalidations will actually be enqueued for invalidation in the first round,
       // so that we can interrupt before all of them are done.
@@ -475,25 +475,28 @@
         }
       }
       int countDownStart = validValuesToDo > 0 ? random.nextInt(validValuesToDo) : 0;
-      final CountDownLatch countDownToInterrupt = new CountDownLatch(countDownStart);
-      final DirtyTrackingProgressReceiver receiver =
-          new DirtyTrackingProgressReceiver(
-              new EvaluationProgressReceiver() {
-                @Override
-                public void invalidated(SkyKey skyKey, InvalidationState state) {
-                  countDownToInterrupt.countDown();
-                  if (countDownToInterrupt.getCount() == 0) {
-                    mainThread.interrupt();
-                    // Wait for the main thread to be interrupted uninterruptibly, because the main
-                    // thread is going to interrupt us, and we don't want to get into an interrupt
-                    // fight. Only if we get interrupted without the main thread also being
-                    // interrupted will this throw an InterruptedException.
-                    TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
-                        visitor.get().getInterruptionLatchForTestingOnly(),
-                        "Main thread was not interrupted");
-                  }
-                }
-              });
+      CountDownLatch countDownToInterrupt = new CountDownLatch(countDownStart);
+      // Make sure final invalidation finishes.
+      DirtyTrackingProgressReceiver receiver =
+          run == tries
+              ? new DirtyTrackingProgressReceiver(null)
+              : new DirtyTrackingProgressReceiver(
+                  new EvaluationProgressReceiver() {
+                    @Override
+                    public void invalidated(SkyKey skyKey, InvalidationState state) {
+                      countDownToInterrupt.countDown();
+                      if (countDownToInterrupt.getCount() == 0) {
+                        mainThread.interrupt();
+                        // Wait for the main thread to be interrupted uninterruptibly, because the
+                        // main thread is going to interrupt us, and we don't want to get into an
+                        // interrupt fight. Only if we get interrupted without the main thread also
+                        // being interrupted will this throw an InterruptedException.
+                        TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
+                            visitor.get().getInterruptionLatchForTestingOnly(),
+                            "Main thread was not interrupted");
+                      }
+                    }
+                  });
       try {
         invalidate(
             graph,
@@ -502,7 +505,7 @@
                 .toArray(new SkyKey[0]));
         assertThat(state.getInvalidationsForTesting()).isEmpty();
       } catch (InterruptedException e) {
-        // Expected.
+        assertThat(run).isLessThan(tries);
       }
       if (state.isEmpty()) {
         // Ran out of values to invalidate.
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
index 8c99335..d2064341 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
@@ -33,7 +33,7 @@
   @Parameters(name = "numElements-{0}")
   public static List<Object[]> parameters() {
     List<Object[]> params = new ArrayList<>();
-    for (int i = 0; i < 20; i++) {
+    for (int i = 1; i < 2; i++) {
       params.add(new Object[] {i});
     }
     return params;
@@ -52,11 +52,13 @@
       }
       // Not a big test but at least check that it does not blow up.
       assertThat(ReverseDepsUtility.toString(example)).isNotEmpty();
-      assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
+      assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+          .hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
         ReverseDepsUtility.removeReverseDep(example, Key.create(i));
       }
-      assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
+      assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+          .hasSize(numElements - numRemovals);
       assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
     }
   }
@@ -69,11 +71,13 @@
       for (int j = 0; j < numElements; j++) {
         ReverseDepsUtility.addReverseDep(example, Key.create(j));
       }
-      assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
+      assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+          .hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
         ReverseDepsUtility.removeReverseDep(example, Key.create(i));
       }
-      assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
+      assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+          .hasSize(numElements - numRemovals);
       assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
     }
   }
@@ -88,13 +92,26 @@
     ReverseDepsUtility.addReverseDep(example, Key.create(0));
     if (numElements == 0) {
       // Will not throw.
-      ReverseDepsUtility.getReverseDeps(example);
+      assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true)).isEmpty();
     } else {
-      assertThrows(Exception.class, () -> ReverseDepsUtility.getReverseDeps(example));
+      assertThrows(
+          RuntimeException.class,
+          () -> ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true));
     }
   }
 
   @Test
+  public void duplicateAddNoThrowWithoutCheck() {
+    InMemoryNodeEntry example = new InMemoryNodeEntry();
+    for (int i = 0; i < numElements; i++) {
+      ReverseDepsUtility.addReverseDep(example, Key.create(i));
+    }
+    ReverseDepsUtility.addReverseDep(example, Key.create(0));
+    assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ false))
+        .hasSize(numElements + 1);
+  }
+
+  @Test
   public void doubleAddThenRemove() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
     SkyKey key = Key.create(0);
@@ -102,7 +119,9 @@
     // Should only fail when we call getReverseDeps().
     ReverseDepsUtility.addReverseDep(example, key);
     ReverseDepsUtility.removeReverseDep(example, key);
-    assertThrows(IllegalStateException.class, () -> ReverseDepsUtility.getReverseDeps(example));
+    assertThrows(
+        IllegalStateException.class,
+        () -> ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true));
   }
 
   @Test
@@ -129,7 +148,8 @@
     ReverseDepsUtility.addReverseDep(example, key);
     ReverseDepsUtility.removeReverseDep(example, key);
     ReverseDepsUtility.addReverseDep(example, key);
-    assertThat(ReverseDepsUtility.getReverseDeps(example)).containsExactly(fixedKey, key);
+    assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+        .containsExactly(fixedKey, key);
   }
 
   private static class Key extends AbstractSkyKey<Integer> {