diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java b/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java
index 0d2d033..fff507e 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/SkyframeBuilder.java
@@ -240,7 +240,7 @@
     }
 
     @Override
-    public void invalidated(SkyValue node, InvalidationState state) {}
+    public void invalidated(SkyKey skyKey, InvalidationState state) {}
 
     @Override
     public void enqueueing(SkyKey skyKey) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index 3ccc363..74794aa 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -94,9 +94,9 @@
   // Used to see if checks of graph consistency need to be done after analysis.
   private volatile boolean someConfiguredTargetEvaluated = false;
 
-  // We keep the set of invalidated configuration targets so that we can know if something
+  // We keep the set of invalidated configuration target keys so that we can know if something
   // has been invalidated after graph pruning has been executed.
-  private Set<ConfiguredTargetValue> dirtyConfiguredTargets = Sets.newConcurrentHashSet();
+  private Set<SkyKey> dirtiedConfiguredTargetKeys = Sets.newConcurrentHashSet();
   private volatile boolean anyConfiguredTargetDeleted = false;
 
   public SkyframeBuildView(ConfiguredTargetFactory factory,
@@ -414,12 +414,12 @@
 
   /** Clear the invalidated configured targets detected during loading and analysis phases. */
   public void clearInvalidatedConfiguredTargets() {
-    dirtyConfiguredTargets = Sets.newConcurrentHashSet();
+    dirtiedConfiguredTargetKeys = Sets.newConcurrentHashSet();
     anyConfiguredTargetDeleted = false;
   }
 
   public boolean isSomeConfiguredTargetInvalidated() {
-    return anyConfiguredTargetDeleted || !dirtyConfiguredTargets.isEmpty();
+    return anyConfiguredTargetDeleted || !dirtiedConfiguredTargetKeys.isEmpty();
   }
 
   /**
@@ -454,15 +454,16 @@
 
   private class ConfiguredTargetValueInvalidationReceiver implements EvaluationProgressReceiver {
     @Override
-    public void invalidated(SkyValue value, InvalidationState state) {
-      if (value instanceof ConfiguredTargetValue) {
-        ConfiguredTargetValue ctValue = (ConfiguredTargetValue) value;
-        // If the value was just dirtied and not deleted, then it may not be truly invalid, since
-        // it may later get re-validated.
+    public void invalidated(SkyKey skyKey, InvalidationState state) {
+      if (skyKey.functionName() == SkyFunctions.CONFIGURED_TARGET) {
         if (state == InvalidationState.DELETED) {
           anyConfiguredTargetDeleted = true;
         } else {
-          dirtyConfiguredTargets.add(ctValue);
+          // If the value was just dirtied and not deleted, then it may not be truly invalid, since
+          // it may later get re-validated. Therefore adding the key to dirtiedConfiguredTargetKeys
+          // is provisional--if the key is later evaluated and the value found to be clean, then we
+          // remove it from the set.
+          dirtiedConfiguredTargetKeys.add(skyKey);
         }
       }
     }
@@ -473,14 +474,18 @@
     @Override
     public void evaluated(SkyKey skyKey, SkyValue value, EvaluationState state) {
       if (skyKey.functionName() == SkyFunctions.CONFIGURED_TARGET && value != null) {
-        if (state == EvaluationState.BUILT) {
-          evaluatedConfiguredTargets.add(skyKey);
-          // During multithreaded operation, this is only set to true, so no concurrency issues.
-          someConfiguredTargetEvaluated = true;
+        switch (state) {
+          case BUILT:
+            evaluatedConfiguredTargets.add(skyKey);
+            // During multithreaded operation, this is only set to true, so no concurrency issues.
+            someConfiguredTargetEvaluated = true;
+            break;
+          case CLEAN:
+            // If the configured target value did not need to be rebuilt, then it wasn't truly
+            // invalid.
+            dirtiedConfiguredTargetKeys.remove(skyKey);
+            break;
         }
-        Preconditions.checkNotNull(value, "%s %s", skyKey, state);
-        ConfiguredTargetValue ctValue = (ConfiguredTargetValue) value;
-        dirtyConfiguredTargets.remove(ctValue);
       }
     }
   }
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 55566ba..f926b5a 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
@@ -1488,12 +1488,12 @@
     @Nullable EvaluationProgressReceiver executionProgressReceiver = null;
 
     @Override
-    public void invalidated(SkyValue value, InvalidationState state) {
+    public void invalidated(SkyKey skyKey, InvalidationState state) {
       if (ignoreInvalidations) {
         return;
       }
       if (skyframeBuildView != null) {
-        skyframeBuildView.getInvalidationReceiver().invalidated(value, state);
+        skyframeBuildView.getInvalidationReceiver().invalidated(skyKey, state);
       }
     }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java b/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java
index aeef2e4..62dcf1e 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java
@@ -43,18 +43,14 @@
   }
 
   /**
-   * Notifies that {@code value} has been invalidated.
+   * Notifies that the node named by {@code key} has been invalidated.
    *
    * <p>{@code state} indicates the new state of the value.
    *
-   * <p>This method is not called on invalidation of values which do not have a value (usually
-   * because they are in error).
-   *
-   * <p>May be called concurrently from multiple threads, possibly with the same {@code value}
-   * object.
+   * <p>May be called concurrently from multiple threads, possibly with the same {@code key}.
    */
   @ThreadSafety.ThreadSafe
-  void invalidated(SkyValue value, InvalidationState state);
+  void invalidated(SkyKey skyKey, InvalidationState state);
 
   /**
    * Notifies that {@code skyKey} is about to get queued for evaluation.
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 6ea61d6..e0d5b8c 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -121,10 +121,10 @@
 
   protected abstract long count();
 
-  protected void informInvalidationReceiver(SkyValue value,
+  protected void informInvalidationReceiver(SkyKey key,
       EvaluationProgressReceiver.InvalidationState state) {
-    if (invalidationReceiver != null && value != null) {
-      invalidationReceiver.invalidated(value, state);
+    if (invalidationReceiver != null) {
+      invalidationReceiver.invalidated(key, state);
     }
   }
 
@@ -255,9 +255,8 @@
                 }
               }
             }
-            // Allow custom Value-specific logic to update dirtiness status.
-            informInvalidationReceiver(entry.getValue(),
-                EvaluationProgressReceiver.InvalidationState.DELETED);
+            // Allow custom key-specific logic to update dirtiness status.
+            informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DELETED);
           }
           if (traverseGraph) {
             // Force reverseDeps consolidation (validates that attempts to remove reverse deps were
@@ -380,8 +379,7 @@
             child.removeReverseDep(key);
           }
 
-          SkyValue value = ValueWithMetadata.justValue(depsAndValue.second);
-          informInvalidationReceiver(value, EvaluationProgressReceiver.InvalidationState.DIRTY);
+          informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DIRTY);
           dirtyKeyTracker.dirty(key);
           // Remove the node from the set as the last operation.
           pendingVisitations.remove(invalidationPair);
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 31bf8aa..8c25d3a 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -15,6 +15,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.skyframe.GraphTester.CONCATENATE;
+import static com.google.devtools.build.skyframe.GraphTester.NODE_TYPE;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
@@ -159,12 +160,12 @@
 
   @Test
   public void receiverWorks() throws Exception {
-    final Set<String> invalidated = Sets.newConcurrentHashSet();
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         Preconditions.checkState(state == expectedState());
-        invalidated.add(((StringValue) value).getValue());
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -186,21 +187,21 @@
 
     set("a", "c");
     invalidateWithoutError(receiver, skyKey("a"));
-    assertThat(invalidated).containsExactly("a", "ab");
+    assertThat(invalidated).containsExactly(skyKey("a"), skyKey("ab"));
     assertValueValue("ab", "cb");
     set("b", "d");
     invalidateWithoutError(receiver, skyKey("b"));
-    assertThat(invalidated).containsExactly("a", "ab", "b", "cb");
+    assertThat(invalidated).containsExactly(skyKey("a"), skyKey("ab"), skyKey("b"));
   }
 
   @Test
-  public void receiverIsNotNotifiedAboutValuesInError() throws Exception {
-    final Set<String> invalidated = Sets.newConcurrentHashSet();
+  public void receiverIsNotifiedAboutNodesInError() throws Exception {
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         Preconditions.checkState(state == expectedState());
-        invalidated.add(((StringValue) value).getValue());
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -214,23 +215,31 @@
       }
     };
 
+    // Given a graph consisting of two nodes, "a" and "ab" such that "ab" depends on "a",
+    // And given "ab" is in error,
     graph = new InMemoryGraph();
     set("a", "a");
     tester.getOrCreate("ab").addDependency("a").setHasError(true);
     eval(false, skyKey("ab"));
 
+    // When "a" is invalidated,
     invalidateWithoutError(receiver, skyKey("a"));
-    assertThat(invalidated).containsExactly("a").inOrder();
+
+    // Then the invalidation receiver is notified of both "a" and "ab"'s invalidations.
+    assertThat(invalidated).containsExactly(skyKey("a"), skyKey("ab"));
+
+    // Note that this behavior isn't strictly required for correctness. This test is
+    // meant to document current behavior and protect against programming error.
   }
 
   @Test
   public void invalidateValuesNotInGraph() throws Exception {
-    final Set<String> invalidated = Sets.newConcurrentHashSet();
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         Preconditions.checkState(state == InvalidationState.DIRTY);
-        invalidated.add(((StringValue) value).getValue());
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -323,17 +332,17 @@
     tester.getOrCreate(parent).addDependency(family[numValues - 1]).setComputedValue(CONCATENATE);
     eval(/*keepGoing=*/false, parent);
     final Thread mainThread = Thread.currentThread();
-    final AtomicReference<SkyValue> badValue = new AtomicReference<>();
+    final AtomicReference<SkyKey> badKey = new AtomicReference<>();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
-        if (value == childValue) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
+        if (skyKey.equals(child)) {
           // Interrupt on the very first invalidate
           mainThread.interrupt();
-        } else if (!childValue.equals(value)) {
-          // All other invalidations should be of the same value.
+        } else if (skyKey.functionName() != NODE_TYPE) {
+          // All other invalidations should have the GraphTester's key type.
           // Exceptions thrown here may be silently dropped, so keep track of errors ourselves.
-          badValue.set(value);
+          badKey.set(skyKey);
         }
         try {
           assertTrue(visitor.get().awaitInterruptionForTestingOnly(2, TimeUnit.HOURS));
@@ -359,16 +368,16 @@
     } catch (InterruptedException e) {
       // Expected.
     }
-    assertNull(badValue.get());
+    assertNull(badKey.get());
     assertFalse(state.isEmpty());
-    final Set<SkyValue> invalidated = Sets.newConcurrentHashSet();
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     assertFalse(isInvalidated(parent));
     SkyValue parentValue = graph.getValue(parent);
     assertNotNull(parentValue);
     receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
-        invalidated.add(value);
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -382,7 +391,7 @@
       }
     };
     invalidateWithoutError(receiver);
-    assertTrue(invalidated.contains(parentValue));
+    assertTrue(invalidated.contains(parent));
     assertThat(state.getInvalidationsForTesting()).isEmpty();
 
     // Regression test coverage:
@@ -451,7 +460,7 @@
       final CountDownLatch countDownToInterrupt = new CountDownLatch(countDownStart);
       final EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
         @Override
-        public void invalidated(SkyValue value, InvalidationState state) {
+        public void invalidated(SkyKey skyKey, InvalidationState state) {
           countDownToInterrupt.countDown();
           if (countDownToInterrupt.getCount() == 0) {
             mainThread.interrupt();
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index 3ee896e..99a8df6 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -199,9 +199,9 @@
     tester.delete("d1");
     tester.eval(true, "d3");
 
-    assertThat(tester.getDirtyValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
     assertEquals(
-        ImmutableSet.of(new StringValue("1"), new StringValue("123")), tester.getDeletedValues());
+        ImmutableSet.of(skyKey("d1"), skyKey("top")), tester.getDeletedKeys());
     assertEquals(null, tester.getExistingValue("top"));
     assertEquals(null, tester.getExistingValue("d1"));
     assertEquals(d2, tester.getExistingValue("d2"));
@@ -1888,11 +1888,11 @@
       private final AtomicBoolean firstInvalidation = new AtomicBoolean(true);
 
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         if (interruptInvalidation.get() && !firstInvalidation.getAndSet(false)) {
           thread.interrupt();
         }
-        super.invalidated(value, state);
+        super.invalidated(skyKey, state);
       }
     });
     SkyKey key = null;
@@ -1946,8 +1946,8 @@
     assertFalse(result.hasError());
     topValue = result.get(top);
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   @Test
@@ -1973,15 +1973,14 @@
     tester.invalidate();
     value = (StringValue) tester.evalAndGet("leaf");
     assertEquals("leafy", value.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("leafysuffix"),
-        new StringValue("leafysuffixsuffix"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(mid, top);
+    assertThat(tester.getDeletedKeys()).isEmpty();
     EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/false, top);
     assertFalse(result.hasError());
     value = result.get(top);
     assertEquals("leafysuffixsuffix", value.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   @Test
@@ -2025,9 +2024,8 @@
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("joyce drank whiskey", topValue.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("hemingway"),
-        new StringValue("hemingway drank absinthe"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(buildFile, top);
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   @Test
@@ -2042,21 +2040,21 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("ignore", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     // Change leaf.
     tester.set(leaf, new StringValue("crunchy"));
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("ignore", topValue.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("leafy"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(leaf);
+    assertThat(tester.getDeletedKeys()).isEmpty();
     tester.set(leaf, new StringValue("smushy"));
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("ignore", topValue.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("crunchy"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(leaf);
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   private static final SkyFunction INTERRUPT_BUILDER = new SkyFunction() {
@@ -2104,8 +2102,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     failBuildAndRemoveValue(leaf);
     // Leaf should no longer exist in the graph. Check that this doesn't cause problems.
     tester.set(leaf, null);
@@ -2129,8 +2127,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     failBuildAndRemoveValue(leaf);
     tester.set(leaf, new StringValue("crunchy"));
     tester.invalidate();
@@ -2199,8 +2197,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     // Change leaf.
     tester.getOrCreate(leaf, /*markAsModified=*/true).setHasError(true);
     tester.getOrCreate(top, /*markAsModified=*/false).setHasError(true);
@@ -2224,8 +2222,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafysecondError", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     // Invalidate leaf.
     tester.getOrCreate(leaf, /*markAsModified=*/true);
     tester.set(leaf, new StringValue("crunchy"));
@@ -3060,11 +3058,11 @@
       emittedEventState.clear();
     }
 
-    public Set<SkyValue> getDirtyValues() {
+    public Set<SkyKey> getDirtyKeys() {
       return invalidationReceiver.dirty;
     }
 
-    public Set<SkyValue> getDeletedValues() {
+    public Set<SkyKey> getDeletedKeys() {
       return invalidationReceiver.deleted;
     }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index af2c4e0..d414fea 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -249,7 +249,7 @@
     final Set<SkyKey> receivedValues = Sets.newConcurrentHashSet();
     revalidationReceiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {}
+      public void invalidated(SkyKey skyKey, InvalidationState state) {}
 
       @Override
       public void enqueueing(SkyKey key) {}
@@ -1886,7 +1886,7 @@
     final Set<SkyKey> evaluatedValues = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver progressReceiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         throw new IllegalStateException();
       }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java b/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java
index 465f32c..a9a7af3 100644
--- a/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java
+++ b/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java
@@ -22,21 +22,21 @@
  * A testing utility to keep track of evaluation.
  */
 public class TrackingInvalidationReceiver implements EvaluationProgressReceiver {
-  public final Set<SkyValue> dirty = Sets.newConcurrentHashSet();
-  public final Set<SkyValue> deleted = Sets.newConcurrentHashSet();
+  public final Set<SkyKey> dirty = Sets.newConcurrentHashSet();
+  public final Set<SkyKey> deleted = Sets.newConcurrentHashSet();
   public final Set<SkyKey> enqueued = Sets.newConcurrentHashSet();
   public final Set<SkyKey> evaluated = Sets.newConcurrentHashSet();
 
   @Override
-  public void invalidated(SkyValue value, InvalidationState state) {
+  public void invalidated(SkyKey skyKey, InvalidationState state) {
     switch (state) {
       case DELETED:
-        dirty.remove(value);
-        deleted.add(value);
+        dirty.remove(skyKey);
+        deleted.add(skyKey);
         break;
       case DIRTY:
-        dirty.add(value);
-        Preconditions.checkState(!deleted.contains(value));
+        dirty.add(skyKey);
+        Preconditions.checkState(!deleted.contains(skyKey));
         break;
       default:
         throw new IllegalStateException();
@@ -52,8 +52,10 @@
   public void evaluated(SkyKey skyKey, SkyValue value, EvaluationState state) {
     evaluated.add(skyKey);
     if (value != null) {
-      dirty.remove(value);
-      deleted.remove(value);
+      deleted.remove(skyKey);
+      if (state.equals(EvaluationState.CLEAN)) {
+        dirty.remove(skyKey);
+      }
     }
   }