diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
index 58753ad..be934a5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
@@ -20,8 +20,8 @@
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.NotComparableSkyValue;
 import com.google.devtools.build.skyframe.SkyKey;
-import com.google.devtools.build.skyframe.SkyValue;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -31,7 +31,7 @@
  */
 @Immutable
 @ThreadSafe
-public class PackageValue implements SkyValue {
+public class PackageValue implements NotComparableSkyValue {
 
   private final Package pkg;
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
index 1f72484..d0d2573 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -300,6 +300,9 @@
    */
   boolean unchangedFromLastBuild(SkyValue newValue) {
     checkFinishedBuildingWhenAboutToSetValue();
+    if (newValue instanceof NotComparableSkyValue) {
+      return false;
+    }
     return getLastBuildValue().equals(newValue) && lastBuildDirectDeps.equals(directDeps);
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/NotComparableSkyValue.java b/src/main/java/com/google/devtools/build/skyframe/NotComparableSkyValue.java
new file mode 100644
index 0000000..5cb211b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/NotComparableSkyValue.java
@@ -0,0 +1,18 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.skyframe;
+
+/** A SkyValue which, after a fresh evaluation, can never be equal to its last value. */
+public interface NotComparableSkyValue extends SkyValue {
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java b/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java
index 6eab026..b702433 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java
@@ -60,7 +60,7 @@
     if (errorInfo == null) {
       return transitiveEvents.isEmpty()
           ? value
-          : new ValueWithEvents(value, transitiveEvents);
+          : ValueWithEvents.createValueWithEvents(value, transitiveEvents);
     }
     return new ErrorInfoValue(errorInfo, value, transitiveEvents);
   }
@@ -75,15 +75,24 @@
   public abstract NestedSet<TaggedEvents> getTransitiveEvents();
 
   /** Implementation of {@link ValueWithMetadata} for the value case. */
-  public static final class ValueWithEvents extends ValueWithMetadata {
+  public static class ValueWithEvents extends ValueWithMetadata {
 
     private final NestedSet<TaggedEvents> transitiveEvents;
 
-    public ValueWithEvents(SkyValue value, NestedSet<TaggedEvents> transitiveEvents) {
+    private ValueWithEvents(SkyValue value, NestedSet<TaggedEvents> transitiveEvents) {
       super(Preconditions.checkNotNull(value));
       this.transitiveEvents = Preconditions.checkNotNull(transitiveEvents);
     }
 
+    public static ValueWithEvents createValueWithEvents(SkyValue value,
+            NestedSet<TaggedEvents> transitiveEvents) {
+      if (value instanceof NotComparableSkyValue) {
+        return new NotComparableValueWithEvents(value, transitiveEvents);
+      } else {
+        return new ValueWithEvents(value, transitiveEvents);
+      }
+    }
+
     @Nullable
     @Override
     ErrorInfo getErrorInfo() { return null; }
@@ -124,8 +133,21 @@
     public String toString() { return value.toString(); }
   }
 
-  /** Implementation of {@link ValueWithMetadata} for the error case. */
-  private static final class ErrorInfoValue extends ValueWithMetadata {
+  private static final class NotComparableValueWithEvents extends ValueWithEvents
+          implements NotComparableSkyValue {
+    private NotComparableValueWithEvents(SkyValue value,
+            NestedSet<TaggedEvents> transitiveEvents) {
+      super(value, transitiveEvents);
+    }
+  }
+
+  /**
+   * Implementation of {@link ValueWithMetadata} for the error case.
+   *
+   * ErorInfo does not override equals(), so it may as well be marked NotComparableSkyValue.
+   */
+  private static final class ErrorInfoValue extends ValueWithMetadata
+          implements NotComparableSkyValue {
 
     private final ErrorInfo errorInfo;
     private final NestedSet<TaggedEvents> transitiveEvents;
@@ -198,7 +220,7 @@
     if (value instanceof ValueWithMetadata) {
       return (ValueWithMetadata) value;
     }
-    return new ValueWithEvents(value, NO_EVENTS);
+    return ValueWithEvents.createValueWithEvents(value, NO_EVENTS);
   }
 
   @Nullable
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
index 2d44e9d..2a3fc1b 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
@@ -291,7 +291,7 @@
    * Simple value class that stores strings.
    */
   public static class StringValue implements SkyValue {
-    private final String value;
+    protected final String value;
 
     public StringValue(String value) {
       this.value = value;
@@ -329,6 +329,24 @@
     }
   }
 
+  /** A StringValue that is also a NotComparableSkyValue. */
+  public static class NotComparableStringValue extends StringValue
+          implements NotComparableSkyValue {
+    public NotComparableStringValue(String value) {
+      super(value);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      throw new UnsupportedOperationException(value + " is incomparable - what are you doing?");
+    }
+
+    @Override
+    public int hashCode() {
+      throw new UnsupportedOperationException(value + " is incomparable - what are you doing?");
+    }
+  }
+
   /**
    * A callback interface to provide the value computation.
    */
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 8b7c0d2..0304513 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -492,7 +492,7 @@
   }
 
   @Test
-  public void pruneErrorValue() {
+  public void errorInfoCannotBePruned() {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
     SkyKey dep = key("dep");
@@ -514,7 +514,8 @@
     assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
     setValue(entry, /*value=*/null, errorInfo, /*graphVersion=*/1L);
     assertTrue(entry.isDone());
-    assertEquals(new IntVersion(0L), entry.getVersion());
+    // ErrorInfo is treated as a NotComparableSkyValue, so it is not pruned.
+    assertEquals(new IntVersion(1L), entry.getVersion());
   }
 
   @Test
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 fdae6b2..a24e93c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -45,12 +45,14 @@
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.testutil.TestThread;
 import com.google.devtools.build.lib.testutil.TestUtils;
+import com.google.devtools.build.skyframe.GraphTester.NotComparableStringValue;
 import com.google.devtools.build.skyframe.GraphTester.StringValue;
 import com.google.devtools.build.skyframe.GraphTester.TestFunction;
 import com.google.devtools.build.skyframe.GraphTester.ValueComputer;
 import com.google.devtools.build.skyframe.NotifyingInMemoryGraph.EventType;
 import com.google.devtools.build.skyframe.NotifyingInMemoryGraph.Listener;
 import com.google.devtools.build.skyframe.NotifyingInMemoryGraph.Order;
+import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 
 import org.junit.After;
@@ -3113,6 +3115,63 @@
   }
 
   @Test
+  public void notComparableNotPrunedNoEvent() throws Exception {
+    checkNotComparableNotPruned(false);
+  }
+
+  @Test
+  public void notComparableNotPrunedEvent() throws Exception {
+    checkNotComparableNotPruned(true);
+  }
+
+  private void checkNotComparableNotPruned(boolean hasEvent) throws Exception {
+    initializeTester();
+    SkyKey parent = GraphTester.toSkyKey("parent");
+    SkyKey child = GraphTester.toSkyKey("child");
+    NotComparableStringValue notComparableString = new NotComparableStringValue("not comparable");
+    if (hasEvent) {
+      tester.getOrCreate(child).setConstantValue(notComparableString).setWarning("shmoop");
+    } else {
+      tester.getOrCreate(child).setConstantValue(notComparableString);
+    }
+    final AtomicInteger parentEvaluated = new AtomicInteger();
+    final String val = "some val";
+    tester
+        .getOrCreate(parent)
+        .addDependency(child)
+        .setComputedValue(new ValueComputer() {
+          @Override
+          public SkyValue compute(Map<SkyKey, SkyValue> deps, Environment env)
+              throws InterruptedException {
+            parentEvaluated.incrementAndGet();
+            return new StringValue(val);
+          }
+        });
+    assertStringValue(val, tester.evalAndGet( /*keepGoing=*/false, parent));
+    assertThat(parentEvaluated.get()).isEqualTo(1);
+    if (hasEvent) {
+      assertContainsEvent(eventCollector, "shmoop");
+    } else {
+      assertEventCount(0, eventCollector);
+    }
+
+    tester.resetPlayedEvents();
+    tester.getOrCreate(child, /*markAsModified=*/true);
+    tester.invalidate();
+    assertStringValue(val, tester.evalAndGet( /*keepGoing=*/false, parent));
+    assertThat(parentEvaluated.get()).isEqualTo(2);
+    if (hasEvent) {
+      assertContainsEvent(eventCollector, "shmoop");
+    } else {
+      assertEventCount(0, eventCollector);
+    }
+  }
+
+  private static void assertStringValue(String expected, SkyValue val) {
+    assertThat(((StringValue) val).getValue()).isEqualTo(expected);
+  }
+
+  @Test
   public void changePruningWithEvent() throws Exception {
     initializeTester();
     SkyKey parent = GraphTester.toSkyKey("parent");