diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java
index a333a2c..9546129 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java
@@ -38,6 +38,11 @@
           }
 
           @Override
+          public LookupHint getLookupHint(SkyKey key) {
+            return LookupHint.INDIVIDUAL;
+          }
+
+          @Override
           public Map<SkyKey, ? extends NodeEntry> getBatchMap(
               @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys)
               throws InterruptedException {
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
index f9d87a3..e698e10 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
@@ -54,6 +54,11 @@
   }
 
   @Override
+  default LookupHint getLookupHint(SkyKey key) {
+    return LookupHint.INDIVIDUAL;
+  }
+
+  @Override
   Map<SkyKey, ? extends NodeEntry> getBatchMap(
       @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys);
 
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 1a2824e..a58c8a2ca 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -61,6 +61,26 @@
     return getBatchMap(requestor, reason, keys)::get;
   }
 
+  /** A hint about the most efficient way to look up a key in the graph. */
+  enum LookupHint {
+    INDIVIDUAL,
+    BATCH
+  }
+
+  /**
+   * Hints to the caller about the most efficient way to look up a key in this graph.
+   *
+   * <p>A return of {@link LookupHint#INDIVIDUAL} indicates that the given key can efficiently be
+   * looked up by calling {@link #get}. In such a case, it is not worth the effort to aggregate the
+   * key into a collection with other keys for a {@link #getBatch} call.
+   *
+   * <p>A return of {@link LookupHint#BATCH} indicates that the given key should ideally be
+   * requested with other keys as part of a call to {@link #getBatch}. This may be the case if, for
+   * example, the corresponding node is stored remotely, and requesting keys in a single batch
+   * reduces trips to remote storage.
+   */
+  LookupHint getLookupHint(SkyKey key);
+
   /**
    * A version of {@link #getBatch} that returns an {@link InterruptibleSupplier} to possibly
    * retrieve the results later.
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
index ef306099..938ab2b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -35,6 +35,7 @@
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState;
 import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
+import com.google.devtools.build.skyframe.QueryableGraph.LookupHint;
 import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import com.google.devtools.build.skyframe.proto.GraphInconsistency.Inconsistency;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
@@ -490,16 +491,13 @@
     checkActive();
     int sizeBeforeRequest = newlyRequestedDepsValues.size();
     SkyValue depValue = lookupRequestedDep(depKey);
-    if (depValue == null) {
+    if (depValue != null) {
+      processDepValue(depKey, depValue);
+    } else {
       NodeEntry depEntry = evaluatorContext.getGraph().get(skyKey, Reason.DEP_REQUESTED, depKey);
-      depValue = getValueOrNullMarker(depEntry);
-      newlyRequestedDepsValues.put(depKey, depValue);
-      if (depValue != NULL_MARKER) {
-        maybeUpdateMaxTransitiveSourceVersion(depEntry);
-      }
+      depValue = processDepEntry(depKey, depEntry);
     }
     endDepGroup(sizeBeforeRequest);
-    processDepValue(depKey, depValue);
 
     return unwrapOrThrow(
         skyKey, depValue, exceptionClass1, exceptionClass2, exceptionClass3, exceptionClass4);
@@ -510,30 +508,37 @@
   public SkyframeLookupResult getValuesAndExceptions(Iterable<? extends SkyKey> depKeys)
       throws InterruptedException {
     checkActive();
-    List<SkyKey> missingKeys = new ArrayList<>();
+
+    // Lazily initialized when we encounter a missing key and the graph's lookup hint indicates that
+    // the key should be requested in a batch. If the graph supports efficient lookups of individual
+    // keys, we avoid constructing a list.
+    List<SkyKey> missingKeys = null;
 
     int sizeBeforeRequest = newlyRequestedDepsValues.size();
     for (SkyKey key : depKeys) {
       SkyValue value = lookupRequestedDep(key);
-      if (value == null) {
-        missingKeys.add(key);
-      } else if (value != PENDING_MARKER) {
+      if (value == PENDING_MARKER) {
+        continue; // Duplicate key in this request.
+      }
+      if (value != null) {
         processDepValue(key, value);
+      } else if (evaluatorContext.getGraph().getLookupHint(key) == LookupHint.BATCH) {
+        if (missingKeys == null) {
+          missingKeys = new ArrayList<>();
+        }
+        missingKeys.add(key);
+      } else {
+        NodeEntry depEntry = evaluatorContext.getGraph().get(skyKey, Reason.DEP_REQUESTED, key);
+        processDepEntry(key, depEntry);
       }
     }
     endDepGroup(sizeBeforeRequest);
 
-    if (!missingKeys.isEmpty()) {
+    if (missingKeys != null) {
       NodeBatch missingEntries =
           evaluatorContext.getGraph().getBatch(skyKey, Reason.DEP_REQUESTED, missingKeys);
       for (SkyKey key : missingKeys) {
-        NodeEntry depEntry = missingEntries.get(key);
-        SkyValue valueOrNullMarker = getValueOrNullMarker(depEntry);
-        processDepValue(key, valueOrNullMarker);
-        newlyRequestedDepsValues.put(key, valueOrNullMarker);
-        if (valueOrNullMarker != NULL_MARKER) {
-          maybeUpdateMaxTransitiveSourceVersion(depEntry);
-        }
+        processDepEntry(key, missingEntries.get(key));
       }
     }
 
@@ -577,7 +582,19 @@
     };
   }
 
-  private void processDepValue(SkyKey depKey, SkyValue depValue) throws InterruptedException {
+  @CanIgnoreReturnValue
+  private SkyValue processDepEntry(SkyKey depKey, @Nullable NodeEntry depEntry)
+      throws InterruptedException {
+    SkyValue valueOrNullMarker = getValueOrNullMarker(depEntry);
+    processDepValue(depKey, valueOrNullMarker);
+    newlyRequestedDepsValues.put(depKey, valueOrNullMarker);
+    if (valueOrNullMarker != NULL_MARKER) {
+      maybeUpdateMaxTransitiveSourceVersion(depEntry);
+    }
+    return valueOrNullMarker;
+  }
+
+  private void processDepValue(SkyKey depKey, SkyValue depValue) {
     if (depValue == NULL_MARKER) {
       valuesMissing = true;
       return;
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
index e7ddc37..f25d614 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
@@ -84,6 +84,11 @@
     }
 
     @Override
+    public LookupHint getLookupHint(SkyKey key) {
+      return delegate.getLookupHint(key);
+    }
+
+    @Override
     public void remove(SkyKey key) {
       delegate.remove(key);
     }