diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheAwareAction.java b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheAwareAction.java
new file mode 100644
index 0000000..256414b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheAwareAction.java
@@ -0,0 +1,24 @@
+// Copyright 2020 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.lib.actions;
+
+/**
+ * Actions that require special handling by the ActionCache. TODO(b/159326450): Remove this
+ * interface once Starlark supports mandatory inputs specification.
+ */
+public interface ActionCacheAwareAction {
+
+  /** By default, the action cache only stores non-mandatory inputs' execPaths. */
+  boolean storeInputsExecPathsInActionCache();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
index d8d32f8..8aad9ce 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
@@ -18,6 +18,7 @@
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
 import com.google.devtools.build.lib.actions.cache.ActionCache;
 import com.google.devtools.build.lib.actions.cache.DigestUtils;
@@ -275,7 +276,16 @@
       // The action doesn't know its inputs, but the caller has a good idea of what they are.
       Preconditions.checkState(action.discoversInputs(),
           "Actions that don't know their inputs must discover them: %s", action);
-      actionInputs = NestedSetBuilder.wrap(Order.STABLE_ORDER, resolvedCacheArtifacts);
+      if (action instanceof ActionCacheAwareAction
+          && ((ActionCacheAwareAction) action).storeInputsExecPathsInActionCache()) {
+        actionInputs = NestedSetBuilder.wrap(Order.STABLE_ORDER, resolvedCacheArtifacts);
+      } else {
+        actionInputs =
+            NestedSetBuilder.<Artifact>stableOrder()
+                .addTransitive(action.getMandatoryInputs())
+                .addAll(resolvedCacheArtifacts)
+                .build();
+      }
     }
     ActionCache.Entry entry = getCacheEntry(action);
     if (mustExecute(
@@ -400,11 +410,23 @@
         // to rebuild everything if only that file changes.
         FileArtifactValue metadata = getMetadataOrConstant(metadataHandler, output);
         Preconditions.checkState(metadata != null);
-        entry.addFile(output.getExecPath(), metadata);
+        entry.addFile(output.getExecPath(), metadata, /* saveExecPath= */ false);
       }
     }
+
+    boolean storeAllInputsInActionCache =
+        action instanceof ActionCacheAwareAction
+            && ((ActionCacheAwareAction) action).storeInputsExecPathsInActionCache();
+    ImmutableSet<Artifact> excludePathsFromActionCache =
+        !storeAllInputsInActionCache && action.discoversInputs()
+            ? action.getMandatoryInputs().toSet()
+            : ImmutableSet.of();
+
     for (Artifact input : action.getInputs().toList()) {
-      entry.addFile(input.getExecPath(), getMetadataMaybe(metadataHandler, input));
+      entry.addFile(
+          input.getExecPath(),
+          getMetadataMaybe(metadataHandler, input),
+          /* saveExecPath= */ !excludePathsFromActionCache.contains(input));
     }
     entry.getFileDigest();
     actionCache.put(key, entry);
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java b/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
index dd78db7..2de2969 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
@@ -105,18 +105,22 @@
      * Adds the artifact, specified by the executable relative path and its metadata into the cache
      * entry.
      */
-    public void addFile(PathFragment relativePath, FileArtifactValue md) {
+    public void addFile(PathFragment relativePath, FileArtifactValue md, boolean saveExecPath) {
       Preconditions.checkState(mdMap != null);
       Preconditions.checkState(!isCorrupted());
       Preconditions.checkState(digest == null);
 
       String execPath = relativePath.getPathString();
-      if (discoversInputs()) {
+      if (discoversInputs() && saveExecPath) {
         files.add(execPath);
       }
       mdMap.put(execPath, md);
     }
 
+    public void addFile(PathFragment relativePath, FileArtifactValue md) {
+      addFile(relativePath, md, /* saveExecPath= */ true);
+    }
+
     /**
      * @return action key string.
      */
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/StarlarkAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/StarlarkAction.java
index 2fef68c..474822d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/StarlarkAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/StarlarkAction.java
@@ -18,6 +18,7 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.ActionCacheAwareAction;
 import com.google.devtools.build.lib.actions.ActionEnvironment;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
@@ -53,7 +54,7 @@
 import javax.annotation.Nullable;
 
 /** A Starlark specific SpawnAction. */
-public final class StarlarkAction extends SpawnAction {
+public final class StarlarkAction extends SpawnAction implements ActionCacheAwareAction {
 
   private final Optional<Artifact> unusedInputsList;
   private final NestedSet<Artifact> allInputs;
@@ -225,6 +226,16 @@
         .build();
   }
 
+  /**
+   * StarlarkAction can contain `unused_input_list`, which rely on the action cache entry's file
+   * list to determine the list of inputs for a subsequent run, taking into account
+   * unused_input_list. Hence we need to store the inputs' execPaths in the action cache.
+   */
+  @Override
+  public boolean storeInputsExecPathsInActionCache() {
+    return unusedInputsList.isPresent();
+  }
+
   /** Builder class to construct {@link StarlarkAction} instances. */
   public static class Builder extends SpawnAction.Builder {
 
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java
index 06a8fd2..cc517c0 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.AbstractAction;
+import com.google.devtools.build.lib.actions.ActionCacheAwareAction;
 import com.google.devtools.build.lib.actions.ActionEnvironment;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionOwner;
@@ -51,7 +52,7 @@
 import javax.annotation.Nullable;
 
 /** Generic class for Ninja actions. Corresponds to the {@link NinjaTarget} in the Ninja file. */
-public class NinjaAction extends SpawnAction {
+public class NinjaAction extends SpawnAction implements ActionCacheAwareAction {
   private static final String MNEMONIC = "NinjaGenericAction";
 
   private final Root sourceRoot;
@@ -236,4 +237,13 @@
         .setNinjaAction(FailureDetails.NinjaAction.newBuilder().setCode(detailedCode))
         .build();
   }
+
+  /**
+   * NinjaAction relies on the action cache entry's file list to avoid re-running input discovery
+   * after a shutdown.
+   */
+  @Override
+  public boolean storeInputsExecPathsInActionCache() {
+    return discoversInputs();
+  }
 }