diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index 007fa9c..789ce09 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -181,7 +181,7 @@
                 env.getValueOrThrow(importFileKey, SkylarkImportFailedException.class);
       } else {
         skylarkImportLookupValue =
-            skylarkImportLookupFunctionForInlining.computeWithInlineCalls(importFileKey, env, 1);
+            skylarkImportLookupFunctionForInlining.computeWithInlineCalls(importFileKey, env);
       }
       if (skylarkImportLookupValue == null) {
         Preconditions.checkState(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java b/src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java
index 6cf404a..69bd17d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java
@@ -18,7 +18,6 @@
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import java.util.ArrayList;
-import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicReference;
@@ -34,14 +33,16 @@
     this.deps = deps;
   }
 
-  void traverse(DepGroupConsumer depGroupConsumer) throws InterruptedException {
-    deps.traverse(depGroupConsumer, new HashSet<>());
+  void traverse(
+      DepGroupConsumer depGroupConsumer,
+      Set<CachedSkylarkImportLookupFunctionDeps> visitedGlobalDeps)
+      throws InterruptedException {
+    deps.traverse(depGroupConsumer, visitedGlobalDeps);
   }
 
   SkylarkImportLookupValue getValue() {
     return value;
   }
-
   static CachedSkylarkImportLookupValueAndDeps.Builder newBuilder() {
     return new CachedSkylarkImportLookupValueAndDeps.Builder();
   }
@@ -88,7 +89,7 @@
     }
   }
 
-  private static class CachedSkylarkImportLookupFunctionDeps {
+  static class CachedSkylarkImportLookupFunctionDeps {
     private final ImmutableList<Iterable<SkyKey>> directDeps;
     private final ImmutableList<CachedSkylarkImportLookupFunctionDeps> transitiveDeps;
 
@@ -142,6 +143,11 @@
       }
     }
 
+    // Reference equality is fine here as most often, the deps objects for any given import
+    // label will be the same. It is technically possible for the same key to have two copies
+    // of associated cached deps but this just means we may visit the same deps more than once. We
+    // don't run the risk of chasing a cycle because these are detected prior to having any
+    // cached values.
     private void traverse(
         DepGroupConsumer depGroupConsumer, Set<CachedSkylarkImportLookupFunctionDeps> visitedDeps)
         throws InterruptedException {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 724f7fc..d20d47e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -614,8 +614,7 @@
         // Inlining calls to SkylarkImportLookupFunction
         for (SkyKey importLookupKey : importLookupKeys) {
           SkyValue skyValue =
-              skylarkImportLookupFunctionForInlining.computeWithInlineCalls(
-                  importLookupKey, env, importLookupKeys.size());
+              skylarkImportLookupFunctionForInlining.computeWithInlineCalls(importLookupKey, env);
           if (skyValue == null) {
             Preconditions.checkState(
                 env.valuesMissing(), "no starlark import value for %s", importLookupKey);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
index 6286a1f..c24b546 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
@@ -39,6 +39,7 @@
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.packages.SkylarkExportable;
 import com.google.devtools.build.lib.packages.WorkspaceFileValue;
+import com.google.devtools.build.lib.skyframe.CachedSkylarkImportLookupValueAndDeps.CachedSkylarkImportLookupFunctionDeps;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupValue.SkylarkImportLookupKey;
 import com.google.devtools.build.lib.syntax.AssignmentStatement;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
@@ -61,9 +62,11 @@
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.ValueOrException;
-import java.util.LinkedHashMap;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.logging.Logger;
 import javax.annotation.Nullable;
 
@@ -103,8 +106,9 @@
           key.workspaceChunk,
           key.workspacePath,
           env,
-          /*alreadyVisited=*/ null,
-          /*inlineCachedValueBuilder=*/ null);
+          /*visitedNested=*/ null,
+          /*inlineCachedValueBuilder=*/ null,
+          /*visitedGlobalDeps=*/ null);
     } catch (InconsistentFilesystemException e) {
       throw new SkylarkImportLookupFunctionException(e, Transience.PERSISTENT);
     } catch (SkylarkImportFailedException e) {
@@ -113,19 +117,21 @@
   }
 
   @Nullable
-  SkylarkImportLookupValue computeWithInlineCalls(
-      SkyKey skyKey, Environment env, int expectedSizeOfVisitedSet)
+  SkylarkImportLookupValue computeWithInlineCalls(SkyKey skyKey, Environment env)
       throws InconsistentFilesystemException, SkylarkImportFailedException, InterruptedException {
-    // We use the visited set to track if there are any cyclic dependencies when loading the
-    // skylark file.
-    LinkedHashMap<Label, CachedSkylarkImportLookupValueAndDeps> visited =
-        Maps.newLinkedHashMapWithExpectedSize(expectedSizeOfVisitedSet);
+    // We use the visitedNested set to track if there are any cyclic dependencies when loading the
+    // skylark file and the visitedGlobalDeps set to avoid re-registering previously seen
+    // dependencies. Note that the visitedNested set must use insertion order to display the correct
+    // error.
     CachedSkylarkImportLookupValueAndDeps cachedSkylarkImportLookupValueAndDeps =
-        computeWithInlineCallsInternal(skyKey, env, visited);
+        computeWithInlineCallsInternal(
+            skyKey,
+            env,
+            /*visitedNested=*/ new LinkedHashSet<>(),
+            /*visitedGlobalDeps=*/ new HashSet<>());
     if (cachedSkylarkImportLookupValueAndDeps == null) {
       return null;
     }
-    cachedSkylarkImportLookupValueAndDeps.traverse(env::registerDependencies);
     return cachedSkylarkImportLookupValueAndDeps.getValue();
   }
 
@@ -133,14 +139,18 @@
   private CachedSkylarkImportLookupValueAndDeps computeWithInlineCallsInternal(
       SkyKey skyKey,
       Environment env,
-      LinkedHashMap<Label, CachedSkylarkImportLookupValueAndDeps> visited)
+      Set<Label> visitedNested,
+      Set<CachedSkylarkImportLookupFunctionDeps> visitedGlobalDeps)
       throws InconsistentFilesystemException, SkylarkImportFailedException, InterruptedException {
     SkylarkImportLookupKey key = (SkylarkImportLookupKey) skyKey.argument();
-    CachedSkylarkImportLookupValueAndDeps precomputedResult = visited.get(key.importLabel);
-    if (precomputedResult != null) {
-      // We have already registered all the deps for this value.
-      return precomputedResult;
+    Label importLabel = key.importLabel;
+
+    if (!visitedNested.add(importLabel)) {
+      ImmutableList<Label> cycle =
+          CycleUtils.splitIntoPathAndChain(Predicates.equalTo(importLabel), visitedNested).second;
+      throw new SkylarkImportFailedException("Starlark import cycle: " + cycle);
     }
+
     // Note that we can't block other threads on the computation of this value due to a potential
     // deadlock on a cycle. Although we are repeating some work, it is possible we have an import
     // cycle where one thread starts at one side of the cycle and the other thread starts at the
@@ -148,6 +158,7 @@
     CachedSkylarkImportLookupValueAndDeps cachedSkylarkImportLookupValueAndDeps =
         skylarkImportLookupValueCache.getIfPresent(skyKey);
     if (cachedSkylarkImportLookupValueAndDeps != null) {
+      cachedSkylarkImportLookupValueAndDeps.traverse(env::registerDependencies, visitedGlobalDeps);
       return cachedSkylarkImportLookupValueAndDeps;
     }
 
@@ -165,19 +176,19 @@
             inlineCachedValueBuilder::noteException);
     SkylarkImportLookupValue value =
         computeInternal(
-            key.importLabel,
+            importLabel,
             key.inWorkspace,
             key.workspaceChunk,
             key.workspacePath,
             recordingEnv,
-            Preconditions.checkNotNull(visited, key.importLabel),
-            inlineCachedValueBuilder);
+            Preconditions.checkNotNull(visitedNested, importLabel),
+            inlineCachedValueBuilder,
+            visitedGlobalDeps);
 
     if (value != null) {
       inlineCachedValueBuilder.setValue(value);
       cachedSkylarkImportLookupValueAndDeps = inlineCachedValueBuilder.build();
       skylarkImportLookupValueCache.put(skyKey, cachedSkylarkImportLookupValueAndDeps);
-      visited.put(key.importLabel, cachedSkylarkImportLookupValueAndDeps);
     }
     return cachedSkylarkImportLookupValueAndDeps;
   }
@@ -191,7 +202,7 @@
     skylarkImportLookupValueCache =
         CacheBuilder.newBuilder()
             .concurrencyLevel(BlazeInterners.concurrencyLevel())
-            .maximumSize(10000)
+            .maximumSize(20000)
             .recordStats()
             .build();
   }
@@ -206,8 +217,9 @@
       int workspaceChunk,
       RootedPath workspacePath,
       Environment env,
-      @Nullable LinkedHashMap<Label, CachedSkylarkImportLookupValueAndDeps> alreadyVisited,
-      @Nullable CachedSkylarkImportLookupValueAndDeps.Builder inlineCachedValueBuilder)
+      @Nullable Set<Label> visitedNested,
+      @Nullable CachedSkylarkImportLookupValueAndDeps.Builder inlineCachedValueBuilder,
+      @Nullable Set<CachedSkylarkImportLookupFunctionDeps> visitedGlobalDeps)
       throws InconsistentFilesystemException, SkylarkImportFailedException, InterruptedException {
     PathFragment filePath = fileLabel.toPathFragment();
 
@@ -293,7 +305,7 @@
     }
     Map<SkyKey, SkyValue> skylarkImportMap;
     boolean valuesMissing = false;
-    if (alreadyVisited == null) {
+    if (visitedNested == null) {
       // Not inlining.
 
       Map<SkyKey, ValueOrException<SkylarkImportFailedException>> values =
@@ -314,13 +326,6 @@
           inlineCachedValueBuilder,
           "Expected inline cached value builder to be not-null when inlining.");
       // Inlining calls to SkylarkImportLookupFunction.
-      if (alreadyVisited.containsKey(fileLabel)) {
-        ImmutableList<Label> cycle =
-            CycleUtils.splitIntoPathAndChain(Predicates.equalTo(fileLabel), alreadyVisited.keySet())
-                .second;
-        throw new SkylarkImportFailedException("Starlark import cycle: " + cycle);
-      }
-      alreadyVisited.put(fileLabel, null);
       skylarkImportMap = Maps.newHashMapWithExpectedSize(imports.size());
 
       Preconditions.checkState(
@@ -330,7 +335,8 @@
       Environment strippedEnv = ((RecordingSkyFunctionEnvironment) env).getDelegate();
       for (SkyKey importLookupKey : importLookupKeys) {
         CachedSkylarkImportLookupValueAndDeps cachedValue =
-            this.computeWithInlineCallsInternal(importLookupKey, strippedEnv, alreadyVisited);
+            this.computeWithInlineCallsInternal(
+                importLookupKey, strippedEnv, visitedNested, visitedGlobalDeps);
         if (cachedValue == null) {
           Preconditions.checkState(
               env.valuesMissing(), "no starlark import value for %s", importLookupKey);
@@ -345,7 +351,7 @@
         }
       }
       // All imports traversed, this key can no longer be part of a cycle.
-      Preconditions.checkState(alreadyVisited.remove(fileLabel) == null, fileLabel);
+      Preconditions.checkState(visitedNested.remove(fileLabel), fileLabel);
     }
     if (valuesMissing) {
       // This means some imports are unavailable.
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDepsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDepsTest.java
index 621dedb..c45b1c8 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDepsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDepsTest.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.List;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -77,7 +78,7 @@
             .build();
 
     List<Iterable<SkyKey>> registeredDeps = new ArrayList<>();
-    p.traverse(registeredDeps::add);
+    p.traverse(registeredDeps::add, /*visitedGlobalDeps=*/ new HashSet<>());
 
     assertThat(registeredDeps)
         .containsExactly(
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
index 3b342a7..90c7efa 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
@@ -2809,9 +2809,9 @@
       } catch (BuildFileContainsErrorsException e) {
         // The reason that this is an exception and not reported to the event handler is that the
         // error is reported by the parent sky function, which we don't have here.
-        assertThat(e).hasMessageThat().contains("Starlark import cycle");
-        assertThat(e).hasMessageThat().contains("test/skylark:ext1.bzl");
-        assertThat(e).hasMessageThat().contains("test/skylark:ext2.bzl");
+        assertThat(e)
+            .hasMessageThat()
+            .contains("Starlark import cycle: [//test/skylark:ext1.bzl, //test/skylark:ext2.bzl]");
       }
     }
 
@@ -2835,10 +2835,11 @@
       } catch (BuildFileContainsErrorsException e) {
         // The reason that this is an exception and not reported to the event handler is that the
         // error is reported by the parent sky function, which we don't have here.
-        assertThat(e).hasMessageThat().contains("Starlark import cycle");
-        assertThat(e).hasMessageThat().contains("//test/skylark:ext2.bzl");
-        assertThat(e).hasMessageThat().contains("//test/skylark:ext3.bzl");
-        assertThat(e).hasMessageThat().contains("//test/skylark:ext4.bzl");
+        assertThat(e)
+            .hasMessageThat()
+            .contains(
+                "Starlark import cycle: [//test/skylark:ext2.bzl, "
+                    + "//test/skylark:ext3.bzl, //test/skylark:ext4.bzl]");
       }
     }
   }