diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformFunction.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformFunction.java
index 0a2bd18..05c63c8 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformFunction.java
@@ -17,7 +17,6 @@
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.ConfiguredTargetValue;
 import com.google.devtools.build.lib.analysis.config.CommonOptions;
-import com.google.devtools.build.lib.analysis.platform.PlatformValue.PlatformKeyParams;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.Label.PackageContext;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
@@ -57,7 +56,7 @@
   @Override
   public PlatformValue compute(SkyKey skyKey, Environment env)
       throws PlatformFunctionException, InterruptedException {
-    PlatformKeyParams params = (PlatformKeyParams) skyKey.argument();
+    PlatformValue.Key params = (PlatformValue.Key) skyKey.argument();
     var platformLabel = params.label();
     var pkgId = platformLabel.getPackageIdentifier();
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformValue.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformValue.java
index a1ba13a..8d1c8e6 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformValue.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformValue.java
@@ -16,14 +16,15 @@
 
 import static java.util.Objects.requireNonNull;
 
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.skyframe.config.ParsedFlagsValue;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
+import java.util.List;
+import java.util.Map;
 import java.util.Optional;
 
 /**
@@ -47,31 +48,24 @@
     return new PlatformValue(platformInfo, Optional.of(parsedFlags));
   }
 
-  public static PlatformKey key(
-      Label platformLabel, ImmutableMap<String, String> flagAliasMappings) {
-    return PlatformKey.intern(
-        new PlatformKey(new PlatformKeyParams(platformLabel, flagAliasMappings)));
+  public static Key key(Label platformLabel, List<Map.Entry<String, String>> flagAliasMappings) {
+    return Key.create(platformLabel, flagAliasMappings);
   }
 
   /**
-   * Key parameters.
+   * Key definition.
    *
    * @param label The platform label.
    * @param flagAliasMappings {@code --flag_alias} maps that apply to this build.
    */
   @AutoCodec
-  public record PlatformKeyParams(Label label, ImmutableMap<String, String> flagAliasMappings) {}
+  public record Key(Label label, List<Map.Entry<String, String>> flagAliasMappings)
+      implements SkyKey {
+    private static final SkyKeyInterner<Key> interner = new SkyKeyInterner<>();
 
-  private static final class PlatformKey extends AbstractSkyKey<PlatformKeyParams> {
-    private static final SkyKeyInterner<PlatformKey> interner = new SkyKeyInterner<>();
-
-    @AutoCodec.Interner
-    static PlatformKey intern(PlatformKey key) {
-      return interner.intern(key);
-    }
-
-    private PlatformKey(PlatformKeyParams arg) {
-      super(arg);
+    @AutoCodec.Instantiator
+    static Key create(Label label, List<Map.Entry<String, String>> flagAliasMappings) {
+      return interner.intern(new Key(label, flagAliasMappings));
     }
 
     @Override
@@ -80,7 +74,7 @@
     }
 
     @Override
-    public SkyKeyInterner<PlatformKey> getSkyKeyInterner() {
+    public SkyKeyInterner<Key> getSkyKeyInterner() {
       return interner;
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/producers/BUILD b/src/main/java/com/google/devtools/build/lib/analysis/producers/BUILD
index 694c3e2..1492ba8 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/producers/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/analysis/producers/BUILD
@@ -142,7 +142,6 @@
         "//src/main/java/com/google/devtools/build/skyframe",
         "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
         "//src/main/java/com/google/devtools/common/options",
-        "//third_party:guava",
         "//third_party:jsr305",
     ],
 )
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/producers/BuildConfigurationKeyProducer.java b/src/main/java/com/google/devtools/build/lib/analysis/producers/BuildConfigurationKeyProducer.java
index ed241e3..ad49dde 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/producers/BuildConfigurationKeyProducer.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/producers/BuildConfigurationKeyProducer.java
@@ -15,7 +15,6 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.base.Verify;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.PlatformOptions;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.CoreOptions;
@@ -135,7 +134,7 @@
       tasks.enqueue(
           new PlatformProducer(
               targetPlatforms.getFirst(),
-              ImmutableMap.copyOf(options.get(CoreOptions.class).commandLineFlagAliases),
+              options.get(CoreOptions.class).commandLineFlagAliases,
               this,
               this::checkTargetPlatformFlags));
       return runAfter;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/producers/DependencyContextProducerWithCompatibilityCheck.java b/src/main/java/com/google/devtools/build/lib/analysis/producers/DependencyContextProducerWithCompatibilityCheck.java
index 3dfe06c..b3534c6 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/producers/DependencyContextProducerWithCompatibilityCheck.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/producers/DependencyContextProducerWithCompatibilityCheck.java
@@ -18,6 +18,7 @@
 import com.google.devtools.build.lib.analysis.ToolchainCollection;
 import com.google.devtools.build.lib.analysis.TransitiveDependencyState;
 import com.google.devtools.build.lib.analysis.config.ConfigConditions;
+import com.google.devtools.build.lib.analysis.config.CoreOptions;
 import com.google.devtools.build.lib.analysis.constraints.IncompatibleTargetChecker.IncompatibleTargetException;
 import com.google.devtools.build.lib.analysis.constraints.IncompatibleTargetChecker.IncompatibleTargetProducer;
 import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
@@ -99,7 +100,11 @@
     // toolchains mark the target incompatible instead of failing the build.
     return new PlatformProducer(
         platformConfiguration.getTargetPlatform(),
-        targetAndConfiguration.getConfiguration().getCommandLineFlagAliases(),
+        targetAndConfiguration
+            .getConfiguration()
+            .getOptions()
+            .get(CoreOptions.class)
+            .commandLineFlagAliases,
         (PlatformProducer.ResultSink) this,
         /* runAfter= */ this::computeConfigConditions);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/producers/PlatformProducer.java b/src/main/java/com/google/devtools/build/lib/analysis/producers/PlatformProducer.java
index 078abbd..cd24aa7 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/producers/PlatformProducer.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/producers/PlatformProducer.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.analysis.producers;
 
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.platform.PlatformValue;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.skyframe.toolchains.PlatformLookupUtil.InvalidPlatformException;
@@ -21,6 +20,8 @@
 import com.google.devtools.build.skyframe.state.StateMachine;
 import com.google.devtools.build.skyframe.state.StateMachine.ValueOrException2Sink;
 import com.google.devtools.common.options.OptionsParsingException;
+import java.util.List;
+import java.util.Map;
 import javax.annotation.Nullable;
 
 /** Retrieves {@link PlatformValue} for a given platform. */
@@ -38,7 +39,7 @@
 
   // -------------------- Input --------------------
   private final Label platformLabel;
-  private final ImmutableMap<String, String> flagAliasMappings;
+  private final List<Map.Entry<String, String>> flagAliasMappings;
 
   // -------------------- Output --------------------
   private final ResultSink sink;
@@ -48,7 +49,7 @@
 
   PlatformProducer(
       Label platformLabel,
-      ImmutableMap<String, String> flagAliasMappings,
+      List<Map.Entry<String, String>> flagAliasMappings,
       ResultSink sink,
       StateMachine runAfter) {
     this.platformLabel = platformLabel;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/producers/RuleTransitionApplier.java b/src/main/java/com/google/devtools/build/lib/analysis/producers/RuleTransitionApplier.java
index a5498b7..f83b674 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/producers/RuleTransitionApplier.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/producers/RuleTransitionApplier.java
@@ -169,12 +169,11 @@
       tasks.enqueue(
           new PlatformProducer(
               platformConfiguration.getTargetPlatform(),
-              ImmutableMap.copyOf(
-                  preRuleTransitionKey
-                      .getConfigurationKey()
-                      .getOptions()
-                      .get(CoreOptions.class)
-                      .commandLineFlagAliases),
+              preRuleTransitionKey
+                  .getConfigurationKey()
+                  .getOptions()
+                  .get(CoreOptions.class)
+                  .commandLineFlagAliases,
               (PlatformProducer.ResultSink) this,
               this::computeConfigConditions));
     } else {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 0ef72ef..61b0c0e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -115,7 +115,7 @@
 import com.google.devtools.build.lib.analysis.config.transitions.TransitionUtil;
 import com.google.devtools.build.lib.analysis.constraints.RuleContextConstraintSemantics;
 import com.google.devtools.build.lib.analysis.platform.PlatformFunction;
-import com.google.devtools.build.lib.analysis.platform.PlatformValue.PlatformKeyParams;
+import com.google.devtools.build.lib.analysis.platform.PlatformValue;
 import com.google.devtools.build.lib.analysis.producers.ConfiguredTargetAndDataProducer;
 import com.google.devtools.build.lib.analysis.starlark.StarlarkAttributeTransitionProvider;
 import com.google.devtools.build.lib.bazel.bzlmod.BazelDepGraphValue;
@@ -1829,7 +1829,7 @@
     // Parse the options.
     PackageContext rootPackage = mainRepoContext.rootPackage();
     ParsedFlagsValue.Key parsedFlagsKey =
-        ParsedFlagsValue.Key.create(args, rootPackage, /* flagAliasMappings= */ ImmutableMap.of());
+        ParsedFlagsValue.Key.create(args, rootPackage, /* flagAliasMappings= */ ImmutableList.of());
     EvaluationResult<SkyValue> result =
         evaluateSkyKeys(eventHandler, ImmutableList.of(parsedFlagsKey));
     if (result.hasError()) {
@@ -4077,7 +4077,7 @@
           // a non-ActionLookupKey depending on an ActionLookupKey. So we can skip any other
           // non-ActionLookupKeys in the traversal as an optimization.
           if (dep.functionName().equals(SkyFunctions.PLATFORM)) {
-            var platformLabel = ((PlatformKeyParams) dep.argument()).label();
+            var platformLabel = ((PlatformValue.Key) dep.argument()).label();
             dep = PlatformFunction.configuredTargetDep(platformLabel);
           }
           if (!(dep instanceof ActionLookupKey depKey)) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/config/BuildConfigurationFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/config/BuildConfigurationFunction.java
index 8c1e8ab..3666acc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/config/BuildConfigurationFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/config/BuildConfigurationFunction.java
@@ -15,7 +15,6 @@
 
 import static com.google.devtools.build.lib.analysis.constraints.ConstraintConstants.CPU_CONSTRAINT_SETTING;
 
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.PlatformOptions;
@@ -115,9 +114,7 @@
 
     PlatformValue platformValue =
         (PlatformValue)
-            env.getValue(
-                PlatformValue.key(
-                    platformLabel, ImmutableMap.copyOf(coreOptions.commandLineFlagAliases)));
+            env.getValue(PlatformValue.key(platformLabel, coreOptions.commandLineFlagAliases));
     if (platformValue == null) {
       return null;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsFunction.java
index 6926b0f..8210def 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsFunction.java
@@ -17,6 +17,7 @@
 import static com.google.devtools.common.options.OptionsParser.STARLARK_SKIPPED_PREFIXES;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.config.FragmentOptions;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -56,6 +57,7 @@
 
     ImmutableList.Builder<String> nativeFlags = ImmutableList.builder();
     ImmutableList.Builder<String> starlarkFlags = ImmutableList.builder();
+    ImmutableMap<String, String> flagAliasMappings = ImmutableMap.copyOf(key.flagAliasMappings());
     for (String flagSetting : key.rawFlags()) {
       if (!flagSetting.startsWith("--")) {
         // This is either something like "-c" or an invalid setting. Let options parsing handle it.
@@ -76,7 +78,7 @@
         flagName = flagSetting.substring(2); // --<flag>
       }
       // If --flag_alias=foo=//bar and we see --foo=1, use the canonical setting --//bar=1.
-      String actualFlag = key.flagAliasMappings().get(flagName);
+      String actualFlag = flagAliasMappings.get(flagName);
       if (actualFlag != null) {
         flagSetting =
             "--%s%s%s"
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsValue.java
index 7903492..19318df 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/config/ParsedFlagsValue.java
@@ -19,7 +19,6 @@
 import com.github.benmanes.caffeine.cache.LoadingCache;
 import com.google.common.base.MoreObjects;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.FragmentOptions;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -36,6 +35,7 @@
 import com.google.devtools.common.options.OptionValueDescription;
 import com.google.devtools.common.options.OptionsParsingException;
 import com.google.devtools.common.options.OptionsParsingResult;
+import java.util.List;
 import java.util.Map;
 
 /** Stores the {@link OptionsParsingResult} from {@link ParsedFlagsFunction}. */
@@ -55,7 +55,7 @@
     public static Key create(
         ImmutableList<String> rawFlags,
         PackageContext packageContext,
-        ImmutableMap<String, String> flagAliasMappings) {
+        List<Map.Entry<String, String>> flagAliasMappings) {
       return create(rawFlags, packageContext, /* includeDefaultValues= */ false, flagAliasMappings);
     }
 
@@ -68,7 +68,7 @@
         ImmutableList<String> rawFlags,
         PackageContext packageContext,
         boolean includeDefaultValues,
-        ImmutableMap<String, String> flagAliasMappings) {
+        List<Map.Entry<String, String>> flagAliasMappings) {
       return interner.intern(
           new Key(rawFlags, packageContext, includeDefaultValues, flagAliasMappings));
     }
@@ -77,13 +77,13 @@
     private final PackageContext packageContext;
     private final boolean includeDefaultValues;
 
-    private final ImmutableMap<String, String> flagAliasMappings;
+    private final List<Map.Entry<String, String>> flagAliasMappings;
 
     private Key(
         ImmutableList<String> rawFlags,
         PackageContext packageContext,
         boolean includeDefaultValues,
-        ImmutableMap<String, String> flagAliasMappings) {
+        List<Map.Entry<String, String>> flagAliasMappings) {
       this.rawFlags = checkNotNull(rawFlags);
       this.packageContext = checkNotNull(packageContext);
       this.includeDefaultValues = includeDefaultValues;
@@ -102,7 +102,7 @@
       return includeDefaultValues;
     }
 
-    ImmutableMap<String, String> flagAliasMappings() {
+    List<Map.Entry<String, String>> flagAliasMappings() {
       return flagAliasMappings;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/config/PlatformMappingFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/config/PlatformMappingFunction.java
index b04b339..ce07291 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/config/PlatformMappingFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/config/PlatformMappingFunction.java
@@ -215,7 +215,7 @@
     // here unless a compelling case demands it.
     ParsedFlagsValue.Key parsedFlagsKey =
         ParsedFlagsValue.Key.create(
-            rawFlags, rootPackage, /* flagAliasMappings= */ ImmutableMap.of());
+            rawFlags, rootPackage, /* flagAliasMappings= */ ImmutableList.of());
     try {
       return (ParsedFlagsValue) env.getValueOrThrow(parsedFlagsKey, OptionsParsingException.class);
     } catch (OptionsParsingException e) {
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/producers/PlatformProducerTest.java b/src/test/java/com/google/devtools/build/lib/analysis/producers/PlatformProducerTest.java
index 02d69a4..a9317ae 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/producers/PlatformProducerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/producers/PlatformProducerTest.java
@@ -16,12 +16,14 @@
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertThrows;
 
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.analysis.platform.PlatformValue;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.skyframe.toolchains.PlatformLookupUtil.InvalidPlatformException;
 import com.google.devtools.build.skyframe.state.StateMachine;
 import com.google.devtools.common.options.OptionsParsingException;
+import java.util.List;
+import java.util.Map;
 import javax.annotation.Nullable;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -56,7 +58,7 @@
         """);
 
     Label platformLabel = Label.parseCanonicalUnchecked("//lookup:basic");
-    PlatformValue result = fetch(platformLabel, /* flagAliasMappings= */ ImmutableMap.of());
+    PlatformValue result = fetch(platformLabel, /* flagAliasMappings= */ ImmutableList.of());
 
     assertThat(result).isNotNull();
     assertThat(result.platformInfo().label()).isEqualTo(platformLabel);
@@ -89,7 +91,7 @@
         """);
 
     Label platformLabel = Label.parseCanonicalUnchecked("//lookup:alias");
-    PlatformValue result = fetch(platformLabel, /* flagAliasMappings= */ ImmutableMap.of());
+    PlatformValue result = fetch(platformLabel, /* flagAliasMappings= */ ImmutableList.of());
 
     assertThat(result).isNotNull();
     assertThat(result.platformInfo().label())
@@ -111,7 +113,7 @@
     Label platformLabel = Label.parseCanonicalUnchecked("//lookup:basic");
     assertThrows(
         InvalidPlatformException.class,
-        () -> fetch(platformLabel, /* flagAliasMappings= */ ImmutableMap.of()));
+        () -> fetch(platformLabel, /* flagAliasMappings= */ ImmutableList.of()));
   }
 
   @Test
@@ -128,7 +130,7 @@
     Label platformLabel = Label.parseCanonicalUnchecked("//lookup:basic");
     assertThrows(
         OptionsParsingException.class,
-        () -> fetch(platformLabel, /* flagAliasMappings= */ ImmutableMap.of()));
+        () -> fetch(platformLabel, /* flagAliasMappings= */ ImmutableList.of()));
   }
 
   @Test
@@ -180,13 +182,10 @@
     PlatformValue result =
         fetch(
             Label.parseCanonicalUnchecked("//lookup:basic"),
-            /* flagAliasMappings= */ ImmutableMap.of(
-                "aliasname1",
-                "//starlark:actual1",
-                "aliasname2",
-                "//starlark:actual2",
-                "aliasname3",
-                "//starlark:actual3"));
+            /* flagAliasMappings= */ ImmutableList.of(
+                Map.entry("aliasname1", "//starlark:actual1"),
+                Map.entry("aliasname2", "//starlark:actual2"),
+                Map.entry("aliasname3", "//starlark:actual3")));
 
     // Native flags:
     assertThat(result.parsedFlags().get().parsingResult().canonicalize())
@@ -197,7 +196,8 @@
             "//starlark:actual1", "fast", "//starlark:actual2", true, "//starlark:actual3", false);
   }
 
-  private PlatformValue fetch(Label platformLabel, ImmutableMap<String, String> flagAliasMappings)
+  private PlatformValue fetch(
+      Label platformLabel, List<Map.Entry<String, String>> flagAliasMappings)
       throws InvalidPlatformException, OptionsParsingException, InterruptedException {
     PlatformInfoSink sink = new PlatformInfoSink();
     PlatformProducer producer =