diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtiableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DirtiableGraph.java
index 0781222..96552bf 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtiableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtiableGraph.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
 /**
  * Interface for classes that need to remove values from graph. Currently just used by {@link
  * EagerInvalidator}.
@@ -20,6 +22,7 @@
  * <p>This class is not intended for direct use, and is only exposed as public for use in
  * evaluation implementations outside of this package.
  */
+@ThreadSafe
 public interface DirtiableGraph extends QueryableGraph {
   /**
    * Remove the value with given name from the graph.
diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
index 3d9a934..8cfd22f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
@@ -13,10 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
 /**
  * Interface between a single version of the graph and the evaluator. Supports mutation of that
  * single version of the graph.
  */
+@ThreadSafe
 interface EvaluableGraph extends QueryableGraph {
   /**
    * Creates a new node with the specified key if it does not exist yet. Returns the node entry
diff --git a/src/main/java/com/google/devtools/build/skyframe/ProcessableGraph.java b/src/main/java/com/google/devtools/build/skyframe/ProcessableGraph.java
index 8bf8a38..ec98918 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ProcessableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ProcessableGraph.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
 /**
  * A graph that is both Dirtiable (values can be deleted) and Evaluable (values can be added). All
  * methods in this interface (as inherited from super-interfaces) should be thread-safe.
@@ -20,5 +22,6 @@
  * <p>This class is not intended for direct use, and is only exposed as public for use in
  * evaluation implementations outside of this package.
  */
+@ThreadSafe
 public interface ProcessableGraph extends DirtiableGraph, EvaluableGraph {
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
index e050830..83a225d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
 import java.util.Map;
 import java.util.Set;
 
@@ -21,6 +23,7 @@
 /**
  * A graph that exposes its entries and structure, for use by classes that must traverse it.
  */
+@ThreadSafe
 public interface QueryableGraph {
   /**
    * Returns the node with the given name, or {@code null} if the node does not exist.