diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BUILD b/src/main/java/com/google/devtools/build/lib/analysis/BUILD
index fd9f55f..2fe6fca 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BUILD
@@ -712,6 +712,7 @@
     deps = [
         ":config/config_matching_provider",
         ":transitive_info_collection",
+        "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
         "//src/main/java/com/google/devtools/build/lib/skyframe:build_configuration",
         "//src/main/java/net/starlark/java/eval",
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTarget.java
index a53fea1..6795182 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTarget.java
@@ -16,6 +16,7 @@
 
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
@@ -42,6 +43,14 @@
   /** All <code>ConfiguredTarget</code>s have a "files" field. */
   String FILES_FIELD = "files";
 
+  /** Returns a key provider that may be used to lookup this {@link ConfiguredTarget}. */
+  ActionLookupKeyOrProxy getKeyOrProxy();
+
+  @Override
+  default Label getLabel() {
+    return getKeyOrProxy().getLabel();
+  }
+
   @Nullable
   default String getConfigurationChecksum() {
     return getConfigurationKey() == null ? null : getConfigurationKey().getOptions().checksum();
@@ -59,7 +68,9 @@
    * <p>If this changes, {@link AspectResolver#aspecMatchesConfiguredTarget} should be updated.
    */
   @Nullable
-  BuildConfigurationKey getConfigurationKey();
+  default BuildConfigurationKey getConfigurationKey() {
+    return getKeyOrProxy().getConfigurationKey();
+  }
 
   /** Returns keys for a legacy Starlark provider. */
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index b35a86a..0965348 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -22,7 +22,6 @@
 import com.google.common.base.Verify;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
@@ -271,11 +270,9 @@
               config,
               prerequisiteMap.get(DependencyKind.VISIBILITY_DEPENDENCY),
               visibility);
-      return new PackageGroupConfiguredTarget(targetContext, packageGroup);
+      return new PackageGroupConfiguredTarget(configuredTargetKey, targetContext, packageGroup);
     } else if (target instanceof EnvironmentGroup) {
-      TargetContext targetContext =
-          new TargetContext(analysisEnvironment, target, config, ImmutableSet.of(), visibility);
-      return new EnvironmentGroupConfiguredTarget(targetContext);
+      return new EnvironmentGroupConfiguredTarget(configuredTargetKey);
     } else {
       throw new AssertionError("Unexpected target class: " + target.getClass().getName());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java
index 811a731..28eb3c9 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java
@@ -14,21 +14,20 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.analysis.configuredtargets.AbstractConfiguredTarget;
-import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.Provider;
-import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import javax.annotation.Nullable;
 
 /** A configured target that is empty. */
 @Immutable
 public class EmptyConfiguredTarget extends AbstractConfiguredTarget {
-  public EmptyConfiguredTarget(Label label, BuildConfigurationKey configurationKey) {
-    super(label, configurationKey, NestedSetBuilder.emptySet(Order.STABLE_ORDER));
+  public EmptyConfiguredTarget(ActionLookupKeyOrProxy actionLookupKey) {
+    super(actionLookupKey, NestedSetBuilder.emptySet(Order.STABLE_ORDER));
   }
 
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/AbstractConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/AbstractConfiguredTarget.java
index 0c3330d..64221a0 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/AbstractConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/AbstractConfiguredTarget.java
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.analysis.AnalysisUtils;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.DefaultInfo;
@@ -24,7 +25,6 @@
 import com.google.devtools.build.lib.analysis.OutputGroupInfo;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.analysis.VisibilityProvider;
-import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -32,7 +32,6 @@
 import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.packages.semantics.BuildLanguageOptions;
-import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import java.util.function.Consumer;
 import javax.annotation.Nullable;
 import net.starlark.java.eval.EvalException;
@@ -45,8 +44,13 @@
  * default values.
  */
 public abstract class AbstractConfiguredTarget implements ConfiguredTarget, VisibilityProvider {
-  private final Label label;
-  private final BuildConfigurationKey configurationKey;
+  // This should really never be null, but is null in two cases.
+  // 1. MergedConfiguredTarget: these are ephemeral and never added to the Skyframe graph.
+  // 2. TestActionBuilder.EmptyPackageProvider: it is used here only to inject an empty
+  //    PackageSpecificationProvider.
+  // TODO(b/281522692): The existence of these cases suggest that there should be some additional
+  // abstraction that does not have a key.
+  private final ActionLookupKeyOrProxy actionLookupKey;
 
   private final NestedSet<PackageGroupContents> visibility;
 
@@ -74,20 +78,22 @@
           OutputGroupInfo.STARLARK_NAME,
           ACTIONS_FIELD_NAME);
 
-  public AbstractConfiguredTarget(Label label, BuildConfigurationKey configurationKey) {
-    this(label, configurationKey, NestedSetBuilder.emptySet(Order.STABLE_ORDER));
+  public AbstractConfiguredTarget(ActionLookupKeyOrProxy actionLookupKey) {
+    this(actionLookupKey, NestedSetBuilder.emptySet(Order.STABLE_ORDER));
   }
 
   protected AbstractConfiguredTarget(
-      Label label,
-      BuildConfigurationKey configurationKey,
-      NestedSet<PackageGroupContents> visibility) {
-    this.label = label;
-    this.configurationKey = configurationKey;
+      ActionLookupKeyOrProxy actionLookupKey, NestedSet<PackageGroupContents> visibility) {
+    this.actionLookupKey = actionLookupKey;
     this.visibility = visibility;
   }
 
   @Override
+  public ActionLookupKeyOrProxy getKeyOrProxy() {
+    return actionLookupKey;
+  }
+
+  @Override
   public boolean isImmutable() {
     return true; // all Targets are immutable and Starlark-hashable
   }
@@ -98,16 +104,6 @@
   }
 
   @Override
-  public BuildConfigurationKey getConfigurationKey() {
-    return configurationKey;
-  }
-
-  @Override
-  public Label getLabel() {
-    return label;
-  }
-
-  @Override
   public String toString() {
     return "ConfiguredTarget(" + getLabel() + ", " + getConfigurationChecksum() + ")";
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java
index 063009a..104076d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java
@@ -15,8 +15,7 @@
 package com.google.devtools.build.lib.analysis.configuredtargets;
 
 import com.google.common.base.Preconditions;
-import com.google.devtools.build.lib.analysis.TargetContext;
-import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.Provider;
@@ -29,13 +28,9 @@
 @Immutable
 public final class EnvironmentGroupConfiguredTarget extends AbstractConfiguredTarget {
 
-  private EnvironmentGroupConfiguredTarget(Label label) {
-    super(label, null);
-  }
-
-  public EnvironmentGroupConfiguredTarget(TargetContext targetContext) {
-    this(targetContext.getLabel());
-    Preconditions.checkState(targetContext.getConfiguration() == null, targetContext);
+  public EnvironmentGroupConfiguredTarget(ActionLookupKeyOrProxy actionLookupKey) {
+    super(actionLookupKey);
+    Preconditions.checkState(actionLookupKey.getConfigurationKey() == null, actionLookupKey);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
index 9e17350..677848f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.analysis.configuredtargets;
 
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.AnalysisUtils;
 import com.google.devtools.build.lib.analysis.FileProvider;
@@ -27,7 +28,6 @@
 import com.google.devtools.build.lib.analysis.TransitiveInfoProviderMapBuilder;
 import com.google.devtools.build.lib.analysis.VisibilityProvider;
 import com.google.devtools.build.lib.analysis.test.InstrumentedFilesInfo;
-import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -35,7 +35,6 @@
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
 import com.google.devtools.build.lib.packages.Provider;
-import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import com.google.devtools.build.lib.util.FileType;
 import javax.annotation.Nullable;
 import net.starlark.java.eval.Dict;
@@ -51,15 +50,14 @@
   private final TransitiveInfoProviderMap providers;
 
   FileConfiguredTarget(
-      Label label,
-      BuildConfigurationKey configurationKey,
+      ActionLookupKeyOrProxy actionLookupKey,
       NestedSet<PackageGroupContents> visibility,
       Artifact artifact,
       @Nullable InstrumentedFilesInfo instrumentedFilesInfo,
       @Nullable RequiredConfigFragmentsProvider configFragmentsProvider,
       @Nullable OutputGroupInfo generatingRuleOutputGroupInfo) {
 
-    super(label, configurationKey, visibility);
+    super(actionLookupKey, visibility);
 
     NestedSet<Artifact> filesToBuild = NestedSetBuilder.create(Order.STABLE_ORDER, artifact);
     FileProvider fileProvider = new FileProvider(filesToBuild);
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/InputFileConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/InputFileConfiguredTarget.java
index 70a44a3..3a0705c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/InputFileConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/InputFileConfiguredTarget.java
@@ -18,14 +18,12 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
 import com.google.devtools.build.lib.analysis.TargetContext;
-import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.InputFile;
 import com.google.devtools.build.lib.packages.License;
-import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
 import java.util.Objects;
 import javax.annotation.Nullable;
 import net.starlark.java.eval.Printer;
@@ -41,21 +39,19 @@
   private final SourceArtifact artifact;
   private final NestedSet<TargetLicense> licenses;
 
-  private InputFileConfiguredTarget(
-      Label label,
-      NestedSet<PackageGroupContents> visibility,
-      SourceArtifact artifact,
-      NestedSet<TargetLicense> licenses) {
-    super(label, null, visibility, artifact, null, null, null);
-    this.artifact = artifact;
-    this.licenses = licenses;
-  }
-
   public InputFileConfiguredTarget(
       TargetContext targetContext, InputFile inputFile, SourceArtifact artifact) {
-    this(inputFile.getLabel(), targetContext.getVisibility(), artifact, makeLicenses(inputFile));
+    super(
+        targetContext.getAnalysisEnvironment().getOwner(),
+        targetContext.getVisibility(),
+        artifact,
+        /* instrumentedFilesInfo= */ null,
+        /* configFragmentsProvider= */ null,
+        /* generatingRuleOutputGroupInfo= */ null);
     Preconditions.checkArgument(getConfigurationKey() == null, getLabel());
     Preconditions.checkArgument(targetContext.getTarget() == inputFile, getLabel());
+    this.artifact = artifact;
+    this.licenses = makeLicenses(inputFile);
   }
 
   private static NestedSet<TargetLicense> makeLicenses(InputFile inputFile) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
index 1a931a4..beb374b 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.analysis.AnalysisUtils;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
@@ -28,15 +29,18 @@
 import com.google.devtools.build.lib.analysis.test.AnalysisFailure;
 import com.google.devtools.build.lib.analysis.test.AnalysisFailureInfo;
 import com.google.devtools.build.lib.analysis.test.InstrumentedFilesInfo;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.Provider;
+import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import com.google.devtools.build.lib.starlarkbuildapi.ActionApi;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.List;
 import java.util.function.Consumer;
+import javax.annotation.Nullable;
 import net.starlark.java.eval.Dict;
 import net.starlark.java.eval.Printer;
 
@@ -62,13 +66,33 @@
       ConfiguredTarget base,
       Iterable<ConfiguredAspect> aspects,
       TransitiveInfoProviderMap nonBaseProviders) {
-    super(base.getLabel(), base.getConfigurationKey());
+    // TODO(b/281522692): it's unsound to pass a null key here, but the type system doesn't
+    // currently provide a better way to do this.
+    super(/* actionLookupKey= */ null);
     this.base = base;
     this.aspects = ImmutableList.copyOf(aspects);
     this.nonBaseProviders = nonBaseProviders;
   }
 
   @Override
+  public ActionLookupKeyOrProxy getKeyOrProxy() {
+    throw new IllegalStateException(
+        "MergedConfiguredTarget is ephemeral. It does not exist in the Skyframe graph and it does"
+            + " not have a key.");
+  }
+
+  @Override
+  public Label getLabel() {
+    return base.getLabel();
+  }
+
+  @Override
+  @Nullable
+  public BuildConfigurationKey getConfigurationKey() {
+    return base.getConfigurationKey();
+  }
+
+  @Override
   public <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass) {
     AnalysisUtils.checkProvider(providerClass);
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/OutputFileConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/OutputFileConfiguredTarget.java
index 7bc48ca..af6a19b 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/OutputFileConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/OutputFileConfiguredTarget.java
@@ -25,12 +25,9 @@
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.analysis.test.InstrumentedFilesInfo;
-import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.OutputFile;
-import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
-import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import net.starlark.java.eval.Printer;
 
 /** A ConfiguredTarget for an OutputFile. */
@@ -45,32 +42,15 @@
       OutputFile outputFile,
       ConfiguredTarget generatingRule,
       Artifact outputArtifact) {
-    this(
-        targetContext.getLabel(),
-        targetContext.getConfigurationKey(),
+    super(
+        targetContext.getAnalysisEnvironment().getOwner(),
         targetContext.getVisibility(),
         outputArtifact,
-        generatingRule);
-    Preconditions.checkArgument(targetContext.getTarget() == outputFile);
-  }
-
-  private OutputFileConfiguredTarget(
-      Label label,
-      BuildConfigurationKey configurationKey,
-      NestedSet<PackageGroupContents> visibility,
-      Artifact artifact,
-      ConfiguredTarget generatingRule) {
-
-    super(
-        label,
-        configurationKey,
-        visibility,
-        artifact,
         instrumentedFilesInfo(generatingRule),
         generatingRule.getProvider(RequiredConfigFragmentsProvider.class),
         Preconditions.checkNotNull(generatingRule).get(OutputGroupInfo.STARLARK_CONSTRUCTOR));
-
-    this.artifact = artifact;
+    Preconditions.checkArgument(targetContext.getTarget() == outputFile);
+    this.artifact = outputArtifact;
     this.generatingRule = Preconditions.checkNotNull(generatingRule);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java
index 2fd845d..93172eb 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java
@@ -16,6 +16,7 @@
 
 import static net.starlark.java.eval.Module.ofInnermostEnclosingStarlarkFunction;
 
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.Allowlist;
 import com.google.devtools.build.lib.analysis.FileProvider;
@@ -79,16 +80,19 @@
   }
 
   public PackageGroupConfiguredTarget(
-      Label label,
+      ActionLookupKeyOrProxy actionLookupKey,
       NestedSet<PackageGroupContents> visibility,
       NestedSet<PackageGroupContents> packageSpecifications) {
-    super(label, null, visibility);
+    super(actionLookupKey, visibility);
     this.packageSpecifications = packageSpecifications;
   }
 
-  public PackageGroupConfiguredTarget(TargetContext targetContext, PackageGroup packageGroup) {
+  public PackageGroupConfiguredTarget(
+      ActionLookupKeyOrProxy actionLookupKey,
+      TargetContext targetContext,
+      PackageGroup packageGroup) {
     this(
-        targetContext.getLabel(),
+        actionLookupKey,
         targetContext.getVisibility(),
         getPackageSpecifications(targetContext, packageGroup));
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
index 5ac5cab..ad2339a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
@@ -20,6 +20,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.AnalysisUtils;
 import com.google.devtools.build.lib.analysis.FileProvider;
@@ -42,7 +43,6 @@
 import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
 import com.google.devtools.build.lib.packages.Provider;
-import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.Instantiator;
@@ -87,8 +87,7 @@
   @Instantiator
   @VisibleForSerialization
   RuleConfiguredTarget(
-      Label label,
-      BuildConfigurationKey configurationKey,
+      ActionLookupKeyOrProxy actionLookupKey,
       NestedSet<PackageGroupContents> visibility,
       TransitiveInfoProviderMap providers,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
@@ -96,16 +95,16 @@
       String ruleClassString,
       ImmutableList<ActionAnalysisMetadata> actions,
       ImmutableMap<Label, Artifact> artifactsByOutputLabel) {
-    super(label, configurationKey, visibility);
+    super(actionLookupKey, visibility);
     this.artifactsByOutputLabel = artifactsByOutputLabel;
 
     // We don't use ImmutableMap.Builder here to allow augmenting the initial list of 'default'
     // providers by passing them in.
     TransitiveInfoProviderMapBuilder providerBuilder =
         new TransitiveInfoProviderMapBuilder().addAll(providers);
-    Preconditions.checkState(providerBuilder.contains(RunfilesProvider.class), label);
-    Preconditions.checkState(providerBuilder.contains(FileProvider.class), label);
-    Preconditions.checkState(providerBuilder.contains(FilesToRunProvider.class), label);
+    Preconditions.checkState(providerBuilder.contains(RunfilesProvider.class), actionLookupKey);
+    Preconditions.checkState(providerBuilder.contains(FileProvider.class), actionLookupKey);
+    Preconditions.checkState(providerBuilder.contains(FilesToRunProvider.class), actionLookupKey);
 
     // Initialize every StarlarkApiProvider
     for (int i = 0; i < providers.getProviderCount(); i++) {
@@ -128,8 +127,7 @@
       ImmutableList<ActionAnalysisMetadata> actions,
       ImmutableMap<Label, Artifact> artifactsByOutputLabel) {
     this(
-        ruleContext.getLabel(),
-        ruleContext.getConfigurationKey(),
+        ruleContext.getOwner(),
         ruleContext.getVisibility(),
         providers,
         ruleContext.getConfigConditions(),
@@ -159,15 +157,13 @@
 
   /** Use this constructor for creating incompatible ConfiguredTarget instances. */
   public RuleConfiguredTarget(
-      Label label,
-      BuildConfigurationKey configurationKey,
+      ActionLookupKeyOrProxy actionLookupKey,
       NestedSet<PackageGroupContents> visibility,
       TransitiveInfoProviderMap providers,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       String ruleClassString) {
     this(
-        label,
-        configurationKey,
+        actionLookupKey,
         visibility,
         providers,
         configConditions,
@@ -176,7 +172,8 @@
         ImmutableList.<ActionAnalysisMetadata>of(),
         ImmutableMap.<Label, Artifact>of());
 
-    Preconditions.checkState(providers.get(IncompatiblePlatformProvider.PROVIDER) != null, label);
+    Preconditions.checkState(
+        providers.get(IncompatiblePlatformProvider.PROVIDER) != null, actionLookupKey);
   }
 
   /** The configuration conditions that trigger this rule's configurable attributes. */
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/constraints/IncompatibleTargetChecker.java b/src/main/java/com/google/devtools/build/lib/analysis/constraints/IncompatibleTargetChecker.java
index 7fac664..037f43e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/constraints/IncompatibleTargetChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/constraints/IncompatibleTargetChecker.java
@@ -100,10 +100,8 @@
    * </ul>
    */
   public static class IncompatibleTargetProducer implements StateMachine, Consumer<SkyValue> {
-
-    private final Target target;
-    @Nullable // Non-null when the target has an associated rule.
-    private final BuildConfigurationValue configuration;
+    private final TargetAndConfiguration targetAndConfiguration;
+    private final ConfiguredTargetKey configuredTargetKey;
     private final ConfigConditions configConditions;
     // Non-null when the target has an associated rule and does not opt out of toolchain resolution.
     @Nullable private final PlatformInfo platformInfo;
@@ -124,15 +122,15 @@
     }
 
     public IncompatibleTargetProducer(
-        Target target,
-        @Nullable BuildConfigurationValue configuration,
+        TargetAndConfiguration targetAndConfiguration,
+        ConfiguredTargetKey configuredTargetKey,
         ConfigConditions configConditions,
         @Nullable PlatformInfo platformInfo,
         @Nullable NestedSetBuilder<Package> transitivePackages,
         ResultSink sink,
         StateMachine runAfter) {
-      this.target = target;
-      this.configuration = configuration;
+      this.targetAndConfiguration = targetAndConfiguration;
+      this.configuredTargetKey = configuredTargetKey;
       this.configConditions = configConditions;
       this.platformInfo = platformInfo;
       this.transitivePackages = transitivePackages;
@@ -142,12 +140,13 @@
 
     @Override
     public StateMachine step(Tasks tasks, ExtendedEventHandler listener) {
-      Rule rule = target.getAssociatedRule();
+      Rule rule = targetAndConfiguration.getTarget().getAssociatedRule();
       if (rule == null || !rule.useToolchainResolution() || platformInfo == null) {
         sink.acceptIncompatibleTarget(Optional.empty());
         return runAfter;
       }
 
+      BuildConfigurationValue configuration = targetAndConfiguration.getConfiguration();
       // Retrieves the label list for the target_compatible_with attribute.
       ConfiguredAttributeMapper attrs =
           ConfiguredAttributeMapper.of(rule, configConditions.asProviders(), configuration);
@@ -192,12 +191,12 @@
         sink.acceptIncompatibleTarget(
             Optional.of(
                 createIncompatibleRuleConfiguredTarget(
-                    target,
-                    configuration,
+                    configuredTargetKey,
+                    targetAndConfiguration.getConfiguration(),
                     configConditions,
                     IncompatiblePlatformProvider.incompatibleDueToConstraints(
                         platformInfo.label(), invalidConstraintValues),
-                    target.getAssociatedRule().getRuleClass(),
+                    targetAndConfiguration.getTarget().getAssociatedRule().getRuleClass(),
                     transitivePackages)));
         return runAfter;
       }
@@ -224,6 +223,7 @@
    */
   public static Optional<RuleConfiguredTargetValue> createIndirectlyIncompatibleTarget(
       TargetAndConfiguration targetAndConfiguration,
+      ConfiguredTargetKey configuredTargetKey,
       OrderedSetMultimap<DependencyKind, ConfiguredTargetAndData> depValueMap,
       ConfigConditions configConditions,
       @Nullable PlatformInfo platformInfo,
@@ -250,7 +250,7 @@
     Label platformLabel = platformInfo != null ? platformInfo.label() : null;
     return Optional.of(
         createIncompatibleRuleConfiguredTarget(
-            target,
+            configuredTargetKey,
             configuration,
             configConditions,
             IncompatiblePlatformProvider.incompatibleDueToTargets(platformLabel, incompatibleDeps),
@@ -273,7 +273,7 @@
 
   /** Creates an incompatible target. */
   private static RuleConfiguredTargetValue createIncompatibleRuleConfiguredTarget(
-      Target target,
+      ConfiguredTargetKey configuredTargetKey,
       BuildConfigurationValue configuration,
       ConfigConditions configConditions,
       IncompatiblePlatformProvider incompatiblePlatformProvider,
@@ -303,8 +303,7 @@
 
     RuleConfiguredTarget configuredTarget =
         new RuleConfiguredTarget(
-            target.getLabel(),
-            configuration.getKey(),
+            configuredTargetKey,
             convertVisibility(),
             providerBuilder.build(),
             configConditions.asProviders(),
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 18b44a6..56d272a 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
@@ -47,6 +47,7 @@
         UnloadedToolchainContextsProducer.ResultSink {
   // -------------------- Input --------------------
   private final TargetAndConfiguration targetAndConfiguration;
+  private final ConfiguredTargetKey configuredTargetKey;
   private final UnloadedToolchainContextsInputs unloadedToolchainContextsInputs;
 
   private final TransitiveDependencyState transitiveState;
@@ -63,10 +64,12 @@
 
   public DependencyContextProducerWithCompatibilityCheck(
       TargetAndConfiguration targetAndConfiguration,
+      ConfiguredTargetKey configuredTargetKey,
       UnloadedToolchainContextsInputs unloadedToolchainContextsInputs,
       TransitiveDependencyState transitiveState,
       DependencyContextProducer.ResultSink sink) {
     this.targetAndConfiguration = targetAndConfiguration;
+    this.configuredTargetKey = configuredTargetKey;
     this.unloadedToolchainContextsInputs = unloadedToolchainContextsInputs;
     this.transitiveState = transitiveState;
     this.sink = sink;
@@ -142,8 +145,8 @@
     }
 
     return new IncompatibleTargetProducer(
-        targetAndConfiguration.getTarget(),
-        targetAndConfiguration.getConfiguration(),
+        targetAndConfiguration,
+        configuredTargetKey,
         configConditions,
         targetPlatformInfo,
         transitiveState.transitivePackages(),
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/TestActionBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/test/TestActionBuilder.java
index ebafd05..53b905e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/TestActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/TestActionBuilder.java
@@ -77,7 +77,11 @@
 
   static class EmptyPackageProvider extends PackageGroupConfiguredTarget {
     EmptyPackageProvider() {
-      super(null, null, null);
+      // TODO(b/281522692): it's not good to pass a null key here.
+      super(
+          /* actionLookupKey= */ null,
+          (NestedSet<PackageGroupContents>) null,
+          (NestedSet<PackageGroupContents>) null);
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/AqueryProcessor.java b/src/main/java/com/google/devtools/build/lib/buildtool/AqueryProcessor.java
index ab7a01e..d8095da 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/AqueryProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/AqueryProcessor.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.CommandLineExpansionException;
+import com.google.devtools.build.lib.analysis.ConfiguredTargetValue;
 import com.google.devtools.build.lib.analysis.actions.TemplateExpansionException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
 import com.google.devtools.build.lib.events.Event;
@@ -24,7 +25,6 @@
 import com.google.devtools.build.lib.query2.aquery.ActionGraphQueryEnvironment;
 import com.google.devtools.build.lib.query2.aquery.AqueryActionFilter;
 import com.google.devtools.build.lib.query2.aquery.AqueryOptions;
-import com.google.devtools.build.lib.query2.aquery.KeyedConfiguredTargetValue;
 import com.google.devtools.build.lib.query2.engine.ActionFilterFunction;
 import com.google.devtools.build.lib.query2.engine.FunctionExpression;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
@@ -55,7 +55,7 @@
 import javax.annotation.Nullable;
 
 /** Performs {@code aquery} processing. */
-public final class AqueryProcessor extends PostAnalysisQueryProcessor<KeyedConfiguredTargetValue> {
+public final class AqueryProcessor extends PostAnalysisQueryProcessor<ConfiguredTargetValue> {
   private final AqueryActionFilter actionFilters;
 
   public AqueryProcessor(
@@ -135,7 +135,7 @@
   }
 
   @Override
-  protected PostAnalysisQueryEnvironment<KeyedConfiguredTargetValue> getQueryEnvironment(
+  protected PostAnalysisQueryEnvironment<ConfiguredTargetValue> getQueryEnvironment(
       BuildRequest request,
       CommandEnvironment env,
       TopLevelConfigurations topLevelConfigurations,
diff --git a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphProtoOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphProtoOutputFormatterCallback.java
index b5c6558..1d5374f 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphProtoOutputFormatterCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphProtoOutputFormatterCallback.java
@@ -64,7 +64,7 @@
       ExtendedEventHandler eventHandler,
       AqueryOptions options,
       OutputStream out,
-      TargetAccessor<KeyedConfiguredTargetValue> accessor,
+      TargetAccessor<ConfiguredTargetValue> accessor,
       OutputType outputType,
       AqueryActionFilter actionFilters) {
     super(eventHandler, options, out, accessor);
@@ -124,7 +124,7 @@
   }
 
   @Override
-  public void processOutput(Iterable<KeyedConfiguredTargetValue> partialResult)
+  public void processOutput(Iterable<ConfiguredTargetValue> partialResult)
       throws IOException, InterruptedException {
     if (options.parallelAqueryOutput
         && aqueryOutputHandler instanceof AqueryConsumingOutputHandler) {
@@ -136,21 +136,19 @@
       // Enabling includeParamFiles should enable includeCommandline by default.
       options.includeCommandline |= options.includeParamFiles;
 
-      for (KeyedConfiguredTargetValue keyedConfiguredTargetValue : partialResult) {
-        processSingleEntry(keyedConfiguredTargetValue);
+      for (ConfiguredTargetValue configuredTargetValue : partialResult) {
+        processSingleEntry(configuredTargetValue);
       }
     } catch (CommandLineExpansionException | TemplateExpansionException e) {
       throw new IOException(e.getMessage());
     }
   }
 
-  private void processSingleEntry(KeyedConfiguredTargetValue keyedConfiguredTargetValue)
+  private void processSingleEntry(ConfiguredTargetValue configuredTargetValue)
       throws CommandLineExpansionException,
           InterruptedException,
           IOException,
           TemplateExpansionException {
-    ConfiguredTargetValue configuredTargetValue =
-        keyedConfiguredTargetValue.getConfiguredTargetValue();
     if (!(configuredTargetValue instanceof RuleConfiguredTargetValue)) {
       // We have to include non-rule values in the graph to visit their dependencies, but they
       // don't have any actions to print out.
@@ -158,13 +156,13 @@
     }
     actionGraphDump.dumpConfiguredTarget((RuleConfiguredTargetValue) configuredTargetValue);
     if (options.useAspects) {
-      for (AspectValue aspectValue : accessor.getAspectValues(keyedConfiguredTargetValue)) {
+      for (AspectValue aspectValue : accessor.getAspectValues(configuredTargetValue)) {
         actionGraphDump.dumpAspect(aspectValue, configuredTargetValue);
       }
     }
   }
 
-  private void processOutputInParallel(Iterable<KeyedConfiguredTargetValue> partialResult)
+  private void processOutputInParallel(Iterable<ConfiguredTargetValue> partialResult)
       throws IOException, InterruptedException {
     AqueryConsumingOutputHandler aqueryConsumingOutputHandler =
         (AqueryConsumingOutputHandler) aqueryOutputHandler;
@@ -201,9 +199,9 @@
     }
   }
 
-  private ImmutableList<AqueryOutputTask> toTasks(Iterable<KeyedConfiguredTargetValue> values) {
+  private ImmutableList<AqueryOutputTask> toTasks(Iterable<ConfiguredTargetValue> values) {
     ImmutableList.Builder<AqueryOutputTask> tasks = ImmutableList.builder();
-    for (KeyedConfiguredTargetValue value : values) {
+    for (ConfiguredTargetValue value : values) {
       tasks.add(new AqueryOutputTask(value));
     }
     return tasks.build();
@@ -211,10 +209,10 @@
 
   private final class AqueryOutputTask implements Callable<Void> {
 
-    private final KeyedConfiguredTargetValue keyedConfiguredTargetValue;
+    private final ConfiguredTargetValue configuredTargetValue;
 
-    AqueryOutputTask(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-      this.keyedConfiguredTargetValue = keyedConfiguredTargetValue;
+    AqueryOutputTask(ConfiguredTargetValue configuredTargetValue) {
+      this.configuredTargetValue = configuredTargetValue;
     }
 
     @Override
@@ -223,7 +221,7 @@
             TemplateExpansionException,
             IOException,
             InterruptedException {
-      processSingleEntry(keyedConfiguredTargetValue);
+      processSingleEntry(configuredTargetValue);
       return null;
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryEnvironment.java
index 4a452f7..c3d3fbb 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryEnvironment.java
@@ -61,14 +61,14 @@
  * target graph.
  */
 public class ActionGraphQueryEnvironment
-    extends PostAnalysisQueryEnvironment<KeyedConfiguredTargetValue> {
+    extends PostAnalysisQueryEnvironment<ConfiguredTargetValue> {
 
   public static final ImmutableList<QueryFunction> AQUERY_FUNCTIONS = populateAqueryFunctions();
   public static final ImmutableList<QueryFunction> FUNCTIONS = populateFunctions();
   private AqueryOptions aqueryOptions;
 
   private AqueryActionFilter actionFilters;
-  private final KeyExtractor<KeyedConfiguredTargetValue, ConfiguredTargetKey>
+  private final KeyExtractor<ConfiguredTargetValue, ConfiguredTargetKey>
       configuredTargetKeyExtractor;
   private final ConfiguredTargetValueAccessor accessor;
 
@@ -90,7 +90,7 @@
         pkgPath,
         walkableGraphSupplier,
         settings);
-    this.configuredTargetKeyExtractor = KeyedConfiguredTargetValue::getConfiguredTargetKey;
+    this.configuredTargetKeyExtractor = ActionGraphQueryEnvironment::getConfiguredTargetKeyImpl;
     this.accessor =
         new ConfiguredTargetValueAccessor(
             walkableGraphSupplier.get(), this::getTarget, this.configuredTargetKeyExtractor);
@@ -131,9 +131,9 @@
   }
 
   @Override
-  public ImmutableList<NamedThreadSafeOutputFormatterCallback<KeyedConfiguredTargetValue>>
+  public ImmutableList<NamedThreadSafeOutputFormatterCallback<ConfiguredTargetValue>>
       getDefaultOutputFormatters(
-          TargetAccessor<KeyedConfiguredTargetValue> accessor,
+          TargetAccessor<ConfiguredTargetValue> accessor,
           ExtendedEventHandler eventHandler,
           OutputStream out,
           SkyframeExecutor skyframeExecutor,
@@ -173,42 +173,39 @@
   }
 
   @Override
-  protected KeyExtractor<KeyedConfiguredTargetValue, ConfiguredTargetKey>
+  protected KeyExtractor<ConfiguredTargetValue, ConfiguredTargetKey>
       getConfiguredTargetKeyExtractor() {
     return configuredTargetKeyExtractor;
   }
 
   @Override
-  public Label getCorrectLabel(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    ConfiguredTarget target = keyedConfiguredTargetValue.getConfiguredTarget();
+  public Label getCorrectLabel(ConfiguredTargetValue configuredTargetValue) {
+    ConfiguredTarget target = configuredTargetValue.getConfiguredTarget();
     // Dereference any aliases that might be present.
     return target.getOriginalLabel();
   }
 
   @Nullable
-  private KeyedConfiguredTargetValue createKeyedConfiguredTargetValueFromKey(
-      ConfiguredTargetKey key) throws InterruptedException {
-    ConfiguredTargetValue configuredTargetValue = getConfiguredTargetValue(key.toKey());
-    return configuredTargetValue == null
-        ? null
-        : KeyedConfiguredTargetValue.create(configuredTargetValue, key);
+  private ConfiguredTargetValue createConfiguredTargetValueFromKey(ConfiguredTargetKey key)
+      throws InterruptedException {
+    return getConfiguredTargetValue(key.toKey());
   }
 
   @Nullable
   @Override
-  protected KeyedConfiguredTargetValue getTargetConfiguredTarget(Label label)
+  protected ConfiguredTargetValue getTargetConfiguredTarget(Label label)
       throws InterruptedException {
     if (topLevelConfigurations.isTopLevelTarget(label)) {
-      return createKeyedConfiguredTargetValueFromKey(
+      return createConfiguredTargetValueFromKey(
           ConfiguredTargetKey.builder()
               .setLabel(label)
               .setConfiguration(topLevelConfigurations.getConfigurationForTopLevelTarget(label))
               .build());
     } else {
-      KeyedConfiguredTargetValue toReturn;
+      ConfiguredTargetValue toReturn;
       for (BuildConfigurationValue configuration : topLevelConfigurations.getConfigurations()) {
         toReturn =
-            createKeyedConfiguredTargetValueFromKey(
+            createConfiguredTargetValueFromKey(
                 ConfiguredTargetKey.builder()
                     .setLabel(label)
                     .setConfiguration(configuration)
@@ -223,24 +220,23 @@
 
   @Nullable
   @Override
-  protected KeyedConfiguredTargetValue getNullConfiguredTarget(Label label)
-      throws InterruptedException {
-    return createKeyedConfiguredTargetValueFromKey(
+  protected ConfiguredTargetValue getNullConfiguredTarget(Label label) throws InterruptedException {
+    return createConfiguredTargetValueFromKey(
         ConfiguredTargetKey.builder().setLabel(label).build());
   }
 
   @Nullable
   @Override
-  protected KeyedConfiguredTargetValue getValueFromKey(SkyKey key) throws InterruptedException {
+  protected ConfiguredTargetValue getValueFromKey(SkyKey key) throws InterruptedException {
     Preconditions.checkState(key instanceof ConfiguredTargetKey);
-    return createKeyedConfiguredTargetValueFromKey((ConfiguredTargetKey) key);
+    return createConfiguredTargetValueFromKey((ConfiguredTargetKey) key);
   }
 
   @Nullable
   @Override
   protected RuleConfiguredTarget getRuleConfiguredTarget(
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    ConfiguredTarget configuredTarget = keyedConfiguredTargetValue.getConfiguredTarget();
+      ConfiguredTargetValue configuredTargetValue) {
+    ConfiguredTarget configuredTarget = configuredTargetValue.getConfiguredTarget();
     if (configuredTarget instanceof RuleConfiguredTarget) {
       return (RuleConfiguredTarget) configuredTarget;
     }
@@ -249,9 +245,8 @@
 
   @Nullable
   @Override
-  protected BuildConfigurationValue getConfiguration(
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    ConfiguredTarget target = keyedConfiguredTargetValue.getConfiguredTarget();
+  protected BuildConfigurationValue getConfiguration(ConfiguredTargetValue configuredTargetValue) {
+    ConfiguredTarget target = configuredTargetValue.getConfiguredTarget();
     try {
       return target.getConfigurationKey() == null
           ? null
@@ -263,13 +258,13 @@
 
   @Override
   protected ConfiguredTargetKey getConfiguredTargetKey(
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    return keyedConfiguredTargetValue.getConfiguredTargetKey();
+      ConfiguredTargetValue configuredTargetValue) {
+    return getConfiguredTargetKeyImpl(configuredTargetValue);
   }
 
   @Override
   public QueryTaskFuture<Void> getTargetsMatchingPattern(
-      QueryExpression owner, String pattern, Callback<KeyedConfiguredTargetValue> callback) {
+      QueryExpression owner, String pattern, Callback<ConfiguredTargetValue> callback) {
     TargetPattern patternToEval;
     try {
       patternToEval = getPattern(pattern);
@@ -292,15 +287,15 @@
             patternToEval.evalAdaptedForAsync(
                 resolver,
                 getIgnoredPackagePrefixesPathFragments(),
-                /*excludedSubdirectories=*/ ImmutableSet.of(),
+                /* excludedSubdirectories= */ ImmutableSet.of(),
                 (Callback<Target>)
                     partialResult -> {
-                      List<KeyedConfiguredTargetValue> transformedResult = new ArrayList<>();
+                      List<ConfiguredTargetValue> transformedResult = new ArrayList<>();
                       for (Target target : partialResult) {
-                        KeyedConfiguredTargetValue keyedConfiguredTargetValue =
-                            getKeyedConfiguredTargetValue(target.getLabel());
-                        if (keyedConfiguredTargetValue != null) {
-                          transformedResult.add(keyedConfiguredTargetValue);
+                        ConfiguredTargetValue configuredTargetValue =
+                            getConfiguredTargetValue(target.getLabel());
+                        if (configuredTargetValue != null) {
+                          transformedResult.add(configuredTargetValue);
                         }
                       }
                       callback.process(transformedResult);
@@ -311,26 +306,29 @@
             MoreExecutors.directExecutor()));
   }
 
-  private KeyedConfiguredTargetValue getKeyedConfiguredTargetValue(Label label)
-      throws InterruptedException {
+  private ConfiguredTargetValue getConfiguredTargetValue(Label label) throws InterruptedException {
     // Try with target configuration.
-    KeyedConfiguredTargetValue keyedConfiguredTargetValue = getTargetConfiguredTarget(label);
-    if (keyedConfiguredTargetValue != null) {
-      return keyedConfiguredTargetValue;
+    ConfiguredTargetValue configuredTargetValue = getTargetConfiguredTarget(label);
+    if (configuredTargetValue != null) {
+      return configuredTargetValue;
     }
     // Last chance: source file.
     return getNullConfiguredTarget(label);
   }
 
   @Override
-  public ThreadSafeMutableSet<KeyedConfiguredTargetValue> createThreadSafeMutableSet() {
+  public ThreadSafeMutableSet<ConfiguredTargetValue> createThreadSafeMutableSet() {
     return new ThreadSafeMutableKeyExtractorBackedSetImpl<>(
         configuredTargetKeyExtractor,
-        KeyedConfiguredTargetValue.class,
+        ConfiguredTargetValue.class,
         SkyQueryEnvironment.DEFAULT_THREAD_COUNT);
   }
 
   public void setActionFilters(AqueryActionFilter actionFilters) {
     this.actionFilters = actionFilters;
   }
+
+  private static ConfiguredTargetKey getConfiguredTargetKeyImpl(ConfiguredTargetValue targetValue) {
+    return (ConfiguredTargetKey) targetValue.getConfiguredTarget().getKeyOrProxy();
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphSummaryOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphSummaryOutputFormatterCallback.java
index 6136303..69a74f0 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphSummaryOutputFormatterCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphSummaryOutputFormatterCallback.java
@@ -44,7 +44,7 @@
       ExtendedEventHandler eventHandler,
       AqueryOptions options,
       OutputStream out,
-      TargetAccessor<KeyedConfiguredTargetValue> accessor,
+      TargetAccessor<ConfiguredTargetValue> accessor,
       AqueryActionFilter actionFilters) {
     super(eventHandler, options, out, accessor);
     this.actionFilters = actionFilters;
@@ -56,14 +56,12 @@
   }
 
   @Override
-  public void processOutput(Iterable<KeyedConfiguredTargetValue> partialResult)
+  public void processOutput(Iterable<ConfiguredTargetValue> partialResult)
       throws IOException, InterruptedException {
     // Enabling includeParamFiles should enable includeCommandline by default.
     options.includeCommandline |= options.includeParamFiles;
 
-    for (KeyedConfiguredTargetValue keyedConfiguredTargetValue : partialResult) {
-      ConfiguredTargetValue configuredTargetValue =
-          keyedConfiguredTargetValue.getConfiguredTargetValue();
+    for (ConfiguredTargetValue configuredTargetValue : partialResult) {
       if (!(configuredTargetValue instanceof RuleConfiguredTargetValue)) {
         // We have to include non-rule values in the graph to visit their dependencies, but they
         // don't have any actions to print out.
@@ -74,7 +72,7 @@
         processAction(action);
       }
       if (options.useAspects) {
-        for (AspectValue aspectValue : accessor.getAspectValues(keyedConfiguredTargetValue)) {
+        for (AspectValue aspectValue : accessor.getAspectValues(configuredTargetValue)) {
           for (ActionAnalysisMetadata action : aspectValue.getActions()) {
             processAction(action);
           }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphTextOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphTextOutputFormatterCallback.java
index 8659205..adcd0c5 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphTextOutputFormatterCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/aquery/ActionGraphTextOutputFormatterCallback.java
@@ -69,7 +69,7 @@
       ExtendedEventHandler eventHandler,
       AqueryOptions options,
       OutputStream out,
-      TargetAccessor<KeyedConfiguredTargetValue> accessor,
+      TargetAccessor<ConfiguredTargetValue> accessor,
       AqueryActionFilter actionFilters,
       RepositoryMapping mainRepoMapping) {
     super(eventHandler, options, out, accessor);
@@ -83,15 +83,13 @@
   }
 
   @Override
-  public void processOutput(Iterable<KeyedConfiguredTargetValue> partialResult)
+  public void processOutput(Iterable<ConfiguredTargetValue> partialResult)
       throws IOException, InterruptedException {
     try {
       // Enabling includeParamFiles should enable includeCommandline by default.
       options.includeCommandline |= options.includeParamFiles;
 
-      for (KeyedConfiguredTargetValue keyedConfiguredTargetValue : partialResult) {
-        ConfiguredTargetValue configuredTargetValue =
-            keyedConfiguredTargetValue.getConfiguredTargetValue();
+      for (ConfiguredTargetValue configuredTargetValue : partialResult) {
         if (!(configuredTargetValue instanceof RuleConfiguredTargetValue)) {
           // We have to include non-rule values in the graph to visit their dependencies, but they
           // don't have any actions to print out.
@@ -102,7 +100,7 @@
           writeAction(action, printStream);
         }
         if (options.useAspects) {
-          for (AspectValue aspectValue : accessor.getAspectValues(keyedConfiguredTargetValue)) {
+          for (AspectValue aspectValue : accessor.getAspectValues(configuredTargetValue)) {
             if (aspectValue != null) {
               for (ActionAnalysisMetadata action : aspectValue.getActions()) {
                 writeAction(action, printStream);
diff --git a/src/main/java/com/google/devtools/build/lib/query2/aquery/AqueryThreadsafeCallback.java b/src/main/java/com/google/devtools/build/lib/query2/aquery/AqueryThreadsafeCallback.java
index 12db471..e2bdc3f 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/aquery/AqueryThreadsafeCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/aquery/AqueryThreadsafeCallback.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.aquery;
 
+import com.google.devtools.build.lib.analysis.ConfiguredTargetValue;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.query2.NamedThreadSafeOutputFormatterCallback;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.TargetAccessor;
@@ -21,7 +22,7 @@
 
 /** Base class for aquery output callbacks. */
 public abstract class AqueryThreadsafeCallback
-    extends NamedThreadSafeOutputFormatterCallback<KeyedConfiguredTargetValue> {
+    extends NamedThreadSafeOutputFormatterCallback<ConfiguredTargetValue> {
   protected final ExtendedEventHandler eventHandler;
   protected final AqueryOptions options;
   protected final PrintStream printStream;
@@ -31,7 +32,7 @@
       ExtendedEventHandler eventHandler,
       AqueryOptions options,
       OutputStream out,
-      TargetAccessor<KeyedConfiguredTargetValue> accessor) {
+      TargetAccessor<ConfiguredTargetValue> accessor) {
     this.eventHandler = eventHandler;
     this.options = options;
     this.printStream = out == null ? null : new PrintStream(out);
diff --git a/src/main/java/com/google/devtools/build/lib/query2/aquery/ConfiguredTargetValueAccessor.java b/src/main/java/com/google/devtools/build/lib/query2/aquery/ConfiguredTargetValueAccessor.java
index e3fc3a9..a65002e 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/aquery/ConfiguredTargetValueAccessor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/aquery/ConfiguredTargetValueAccessor.java
@@ -46,36 +46,36 @@
  *
  * <p>Incomplete; we'll implement getPrerequisites and getVisibility when needed.
  */
-public class ConfiguredTargetValueAccessor implements TargetAccessor<KeyedConfiguredTargetValue> {
+public class ConfiguredTargetValueAccessor implements TargetAccessor<ConfiguredTargetValue> {
 
   private final WalkableGraph walkableGraph;
   private final TargetLookup targetLookup;
-  private final KeyExtractor<KeyedConfiguredTargetValue, ConfiguredTargetKey>
+  private final KeyExtractor<ConfiguredTargetValue, ConfiguredTargetKey>
       configuredTargetKeyExtractor;
 
   public ConfiguredTargetValueAccessor(
       WalkableGraph walkableGraph,
       TargetLookup targetLookup,
-      KeyExtractor<KeyedConfiguredTargetValue, ConfiguredTargetKey> configuredTargetKeyExtractor) {
+      KeyExtractor<ConfiguredTargetValue, ConfiguredTargetKey> configuredTargetKeyExtractor) {
     this.walkableGraph = walkableGraph;
     this.targetLookup = targetLookup;
     this.configuredTargetKeyExtractor = configuredTargetKeyExtractor;
   }
 
   @Override
-  public String getTargetKind(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    Target actualTarget = getTargetFromConfiguredTargetValue(keyedConfiguredTargetValue);
+  public String getTargetKind(ConfiguredTargetValue configuredTargetValue) {
+    Target actualTarget = getTargetFromConfiguredTargetValue(configuredTargetValue);
     return actualTarget.getTargetKind();
   }
 
   @Override
-  public String getLabel(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    return keyedConfiguredTargetValue.getConfiguredTarget().getLabel().toString();
+  public String getLabel(ConfiguredTargetValue configuredTargetValue) {
+    return configuredTargetValue.getConfiguredTarget().getLabel().toString();
   }
 
   @Override
-  public String getPackage(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    return keyedConfiguredTargetValue
+  public String getPackage(ConfiguredTargetValue configuredTargetValue) {
+    return configuredTargetValue
         .getConfiguredTarget()
         .getLabel()
         .getPackageIdentifier()
@@ -84,27 +84,27 @@
   }
 
   @Override
-  public boolean isRule(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    Target actualTarget = getTargetFromConfiguredTargetValue(keyedConfiguredTargetValue);
+  public boolean isRule(ConfiguredTargetValue configuredTargetValue) {
+    Target actualTarget = getTargetFromConfiguredTargetValue(configuredTargetValue);
     return actualTarget instanceof Rule;
   }
 
   @Override
-  public boolean isTestRule(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    Target actualTarget = getTargetFromConfiguredTargetValue(keyedConfiguredTargetValue);
+  public boolean isTestRule(ConfiguredTargetValue configuredTargetValue) {
+    Target actualTarget = getTargetFromConfiguredTargetValue(configuredTargetValue);
     return TargetUtils.isTestRule(actualTarget);
   }
 
   @Override
-  public boolean isTestSuite(KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
-    Target actualTarget = getTargetFromConfiguredTargetValue(keyedConfiguredTargetValue);
+  public boolean isTestSuite(ConfiguredTargetValue configuredTargetValue) {
+    Target actualTarget = getTargetFromConfiguredTargetValue(configuredTargetValue);
     return TargetUtils.isTestSuiteRule(actualTarget);
   }
 
   @Override
-  public List<KeyedConfiguredTargetValue> getPrerequisites(
+  public List<ConfiguredTargetValue> getPrerequisites(
       QueryExpression caller,
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue,
+      ConfiguredTargetValue configuredTargetValue,
       String attrName,
       String errorMsgPrefix)
       throws QueryException, InterruptedException {
@@ -115,42 +115,36 @@
 
   @Override
   public List<String> getStringListAttr(
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue, String attrName) {
-    Target actualTarget = getTargetFromConfiguredTargetValue(keyedConfiguredTargetValue);
+      ConfiguredTargetValue configuredTargetValue, String attrName) {
+    Target actualTarget = getTargetFromConfiguredTargetValue(configuredTargetValue);
     return TargetUtils.getStringListAttr(actualTarget, attrName);
   }
 
   @Override
-  public String getStringAttr(
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue, String attrName) {
-    Target actualTarget = getTargetFromConfiguredTargetValue(keyedConfiguredTargetValue);
+  public String getStringAttr(ConfiguredTargetValue configuredTargetValue, String attrName) {
+    Target actualTarget = getTargetFromConfiguredTargetValue(configuredTargetValue);
     return TargetUtils.getStringAttr(actualTarget, attrName);
   }
 
   @Override
   public Iterable<String> getAttrAsString(
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue, String attrName) {
-    Target actualTarget = getTargetFromConfiguredTargetValue(keyedConfiguredTargetValue);
+      ConfiguredTargetValue configuredTargetValue, String attrName) {
+    Target actualTarget = getTargetFromConfiguredTargetValue(configuredTargetValue);
     return TargetUtils.getAttrAsString(actualTarget, attrName);
   }
 
   @Override
-  public ImmutableSet<QueryVisibility<KeyedConfiguredTargetValue>> getVisibility(
-      QueryExpression caller, KeyedConfiguredTargetValue from) throws QueryException {
+  public ImmutableSet<QueryVisibility<ConfiguredTargetValue>> getVisibility(
+      QueryExpression caller, ConfiguredTargetValue from) throws QueryException {
     // TODO(bazel-team): implement this if needed.
     throw new QueryException(
         "visible() is not supported on configured targets",
         ConfigurableQuery.Code.VISIBLE_FUNCTION_NOT_SUPPORTED);
   }
 
-  private Target getTargetFromConfiguredTargetValue(
-      KeyedConfiguredTargetValue keyedConfiguredTargetValue) {
+  private Target getTargetFromConfiguredTargetValue(ConfiguredTargetValue configuredTargetValue) {
     // Dereference any aliases that might be present.
-    Label label =
-        keyedConfiguredTargetValue
-            .getConfiguredTargetValue()
-            .getConfiguredObject()
-            .getOriginalLabel();
+    Label label = configuredTargetValue.getConfiguredTarget().getOriginalLabel();
     try {
       return targetLookup.getTarget(label);
     } catch (InterruptedException e) {
@@ -161,13 +155,13 @@
   }
 
   /** Returns the AspectValues that are attached to the given configuredTarget. */
-  public Set<AspectValue> getAspectValues(KeyedConfiguredTargetValue keyedConfiguredTargetValue)
+  public Set<AspectValue> getAspectValues(ConfiguredTargetValue configuredTargetValue)
       throws InterruptedException {
     Set<AspectValue> result = new HashSet<>();
-    SkyKey skyKey = configuredTargetKeyExtractor.extractKey(keyedConfiguredTargetValue).toKey();
+    SkyKey skyKey = configuredTargetKeyExtractor.extractKey(configuredTargetValue).toKey();
     Iterable<SkyKey> revDeps =
         Iterables.concat(walkableGraph.getReverseDeps(ImmutableList.of(skyKey)).values());
-    Label label = keyedConfiguredTargetValue.getConfiguredTarget().getLabel();
+    Label label = configuredTargetValue.getConfiguredTarget().getLabel();
     for (SkyKey revDep : revDeps) {
       SkyFunctionName skyFunctionName = revDep.functionName();
       if (SkyFunctions.ASPECT.equals(skyFunctionName)) {
diff --git a/src/main/java/com/google/devtools/build/lib/query2/aquery/KeyedConfiguredTargetValue.java b/src/main/java/com/google/devtools/build/lib/query2/aquery/KeyedConfiguredTargetValue.java
deleted file mode 100644
index c7a744c..0000000
--- a/src/main/java/com/google/devtools/build/lib/query2/aquery/KeyedConfiguredTargetValue.java
+++ /dev/null
@@ -1,43 +0,0 @@
-// Copyright 2022 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.query2.aquery;
-
-import com.google.auto.value.AutoValue;
-import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.ConfiguredTargetValue;
-import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
-
-/**
- * An object wrapping a ConfiguredTargetValue and its ConfiguredTargetKey.
- *
- * <p>WARNING: Strictly only for aquery. Do not use this elsewhere.
- *
- * <p>In an actual build, it's too expensive to establish this link, but we need it for correctness
- * in aquery.
- */
-@AutoValue
-public abstract class KeyedConfiguredTargetValue {
-  public abstract ConfiguredTargetValue getConfiguredTargetValue();
-
-  public abstract ConfiguredTargetKey getConfiguredTargetKey();
-
-  public ConfiguredTarget getConfiguredTarget() {
-    return getConfiguredTargetValue().getConfiguredTarget();
-  }
-
-  public static KeyedConfiguredTargetValue create(
-      ConfiguredTargetValue configuredTargetValue, ConfiguredTargetKey configuredTargetKey) {
-    return new AutoValue_KeyedConfiguredTargetValue(configuredTargetValue, configuredTargetKey);
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java
index 1471171..01ccc6a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableClassToInstanceMap;
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.ActionLookupKeyOrProxy;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.AliasProvider;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
@@ -36,7 +37,6 @@
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
 import com.google.devtools.build.lib.packages.Provider;
-import com.google.devtools.build.lib.skyframe.BuildConfigurationKey;
 import javax.annotation.Nullable;
 import net.starlark.java.eval.Dict;
 import net.starlark.java.eval.EvalException;
@@ -51,6 +51,16 @@
  * <p>Transitive info providers may also be overridden. At a minimum, {@link #getProvider} provides
  * {@link AliasProvider} and an explicit {@link VisibilityProvider} which takes precedent over the
  * actual target's visibility.
+ *
+ * <p>The {@link ConfiguredTarget#getConfigurationKey} returns the configuration of the alias itself
+ * and not the configuration of {@link AliasConfiguredTarget#actual} for the following reasons.
+ *
+ * <ul>
+ *   <li>{@code actual} might be an input file, in which case its configuration key is null, and we
+ *       don't want to have rules with a null configuration key.
+ *   <li>{@code actual} has a self transition. Self transitions don't get applied to the alias rule,
+ *       and so the configuration keys actually differ.
+ * </ul>
  */
 @Immutable
 public final class AliasConfiguredTarget implements ConfiguredTarget, Structure {
@@ -81,33 +91,31 @@
           RequiredConfigFragmentsProvider.class, ruleContext.getRequiredConfigFragments());
     }
     return new AliasConfiguredTarget(
-        ruleContext.getLabel(),
-        ruleContext.getConfigurationKey(),
-        actual,
-        allOverrides.build(),
-        ruleContext.getConfigConditions());
+        ruleContext.getOwner(), actual, allOverrides.build(), ruleContext.getConfigConditions());
   }
 
-  private final Label label;
-  private final BuildConfigurationKey configurationKey;
+  private final ActionLookupKeyOrProxy actionLookupKey;
   private final ConfiguredTarget actual;
   private final ImmutableClassToInstanceMap<TransitiveInfoProvider> overrides;
   private final ImmutableMap<Label, ConfigMatchingProvider> configConditions;
 
   private AliasConfiguredTarget(
-      Label label,
-      BuildConfigurationKey configurationKey,
+      ActionLookupKeyOrProxy actionLookupKey,
       ConfiguredTarget actual,
       ImmutableClassToInstanceMap<TransitiveInfoProvider> overrides,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions) {
-    this.label = checkNotNull(label);
-    this.configurationKey = checkNotNull(configurationKey);
+    this.actionLookupKey = actionLookupKey;
     this.actual = checkNotNull(actual);
     this.overrides = checkNotNull(overrides);
     this.configConditions = checkNotNull(configConditions);
   }
 
   @Override
+  public ActionLookupKeyOrProxy getKeyOrProxy() {
+    return this.actionLookupKey;
+  }
+
+  @Override
   public boolean isImmutable() {
     return true; // immutable and Starlark-hashable
   }
@@ -149,16 +157,6 @@
     return actual.containsKey(semantics, key);
   }
 
-  @Override
-  public BuildConfigurationKey getConfigurationKey() {
-    // It would be incorrect to return actual.getConfigurationKey() because of two cases:
-    // 1) actual might be an input file, in which case its configuration key is null, and we don't
-    //    want to have rules with a null configuration key.
-    // 2) actual has a self transition. Self transitions don't get applied to the alias rule, and so
-    //    the configuration keys actually differ.
-    return configurationKey;
-  }
-
   /* Structure methods */
 
   @Override
@@ -194,7 +192,7 @@
 
   @Override
   public Label getOriginalLabel() {
-    return label;
+    return actionLookupKey.getLabel();
   }
 
   @Override
@@ -204,14 +202,15 @@
 
   @Override
   public void repr(Printer printer) {
-    printer.append("<alias target " + label + " of " + actual.getLabel() + ">");
+    printer.append(
+        "<alias target " + actionLookupKey.getLabel() + " of " + actual.getLabel() + ">");
   }
 
   @Override
   public String toString() {
     return MoreObjects.toStringHelper(this)
-        .add("label", label)
-        .add("configurationKey", configurationKey)
+        .add("label", actionLookupKey.getLabel())
+        .add("configurationKey", getConfigurationKey())
         .add("actual", actual)
         .add("overrides", overrides)
         .add("configConditions", configConditions)
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index 9ece41f..4f76b79 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -250,8 +250,7 @@
         // TODO(b/267529852): see if we can remove this. It's not clear the conditions that trigger
         // InconsistentNullConfigException are even possible.
         return new NonRuleConfiguredTargetValue(
-            new EmptyConfiguredTarget(
-                configuredTargetKey.getLabel(), configuredTargetKey.getConfigurationKey()),
+            new EmptyConfiguredTarget(configuredTargetKey),
             state.transitivePackages == null ? null : state.transitivePackages.build());
       }
       // Any `TargetAndConfigurationError` has already been handled, so `result` can only
@@ -263,13 +262,14 @@
       // Otherwise, `result` contains a `ConfiguredTargetKey`.
     }
 
+    configuredTargetKey = (ConfiguredTargetKey) state.targetAndConfigurationResult;
     PrerequisiteProducer prereqs =
         new PrerequisiteProducer(computeDependenciesState.targetAndConfiguration);
     try {
       // Perform all analysis through dependency evaluation.
       if (!prereqs.evaluate(
           state.computeDependenciesState,
-          configuredTargetKey.getExecutionPlatformLabel(),
+          configuredTargetKey,
           ruleClassProvider,
           view,
           () -> maybeAcquireSemaphoreWithLogging(key),
@@ -286,6 +286,7 @@
       Optional<RuleConfiguredTargetValue> incompatibleTarget =
           IncompatibleTargetChecker.createIndirectlyIncompatibleTarget(
               prereqs.getTargetAndConfiguration(),
+              configuredTargetKey,
               prereqs.getDepValueMap(),
               prereqs.getConfigConditions(),
               prereqs.getPlatformInfo(),
@@ -321,10 +322,7 @@
               view,
               env,
               prereqs.getTargetAndConfiguration(),
-              // If the ConfiguredTarget has no Actions, a DelegatingConfiguredTargetKey passed here
-              // may fall out of the interning pool and lead to additional computation. It might be
-              // worth retaining them in the created ConfiguredTargets instead.
-              (ConfiguredTargetKey) state.targetAndConfigurationResult,
+              configuredTargetKey,
               prereqs.getDepValueMap(),
               prereqs.getConfigConditions(),
               toolchainContexts,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
index c67d4f7..e228204 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
@@ -320,12 +320,14 @@
     return new Builder();
   }
 
-  /** Returns a new {@link ConfiguredTargetKey}. */
+  /** Returns the {@link ConfiguredTargetKey} that owns {@code configuredTarget}. */
   public static ConfiguredTargetKey fromConfiguredTarget(ConfiguredTarget configuredTarget) {
-    return builder()
-        .setLabel(configuredTarget.getOriginalLabel())
-        .setConfigurationKey(configuredTarget.getConfigurationKey())
-        .build();
+    // If configuredTarget is a MergedConfiguredTarget unwraps it first. MergedConfiguredTarget is
+    // ephemeral and does not have a directly corresponding entry in Skyframe.
+    //
+    // The cast exists because the key passes through parts of analysis that work on both aspects
+    // and configured targets. This process discards the key's specific type information.
+    return (ConfiguredTargetKey) configuredTarget.unwrapIfMerged().getKeyOrProxy();
   }
 
   /** A helper class to create instances of {@link ConfiguredTargetKey}. */
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrerequisiteProducer.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrerequisiteProducer.java
index d22160b..b1da88b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrerequisiteProducer.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrerequisiteProducer.java
@@ -269,7 +269,7 @@
    */
   public boolean evaluate(
       State state,
-      @Nullable Label executionPlatformLabel,
+      ConfiguredTargetKey configuredTargetKey,
       RuleClassProvider ruleClassProvider,
       SkyframeBuildView view,
       SemaphoreAcquirer semaphoreLocker,
@@ -286,8 +286,7 @@
     semaphoreLocker.acquireSemaphore();
     try {
       var dependencyContext =
-          getDependencyContext(
-              state, executionPlatformLabel, ruleClassProvider, transitiveState, env);
+          getDependencyContext(state, configuredTargetKey, ruleClassProvider, transitiveState, env);
       if (dependencyContext == null) {
         return false;
       }
@@ -361,7 +360,7 @@
   @Nullable // Null when a Skyframe restart is needed.
   public static DependencyContext getDependencyContext(
       State state,
-      @Nullable Label parentExecutionPlatformLabel,
+      ConfiguredTargetKey configuredTargetKey,
       RuleClassProvider ruleClassProvider,
       TransitiveDependencyState transitiveState,
       Environment env)
@@ -378,7 +377,7 @@
       var unloadedToolchainContextsInputs =
           getUnloadedToolchainContextsInputs(
               targetAndConfiguration,
-              parentExecutionPlatformLabel,
+              configuredTargetKey.getExecutionPlatformLabel(),
               ruleClassProvider,
               env.getListener());
       state.execGroupCollectionBuilder = unloadedToolchainContextsInputs;
@@ -386,6 +385,7 @@
           new Driver(
               new DependencyContextProducerWithCompatibilityCheck(
                   targetAndConfiguration,
+                  configuredTargetKey,
                   unloadedToolchainContextsInputs,
                   transitiveState,
                   (DependencyContextProducer.ResultSink) state));
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/BUILD b/src/test/java/com/google/devtools/build/lib/analysis/BUILD
index 6699942..bf46426 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/analysis/BUILD
@@ -98,6 +98,7 @@
         "//src/main/java/com/google/devtools/build/lib/analysis:config/transitions/split_transition",
         "//src/main/java/com/google/devtools/build/lib/analysis:config/transitions/transition_factory",
         "//src/main/java/com/google/devtools/build/lib/analysis:configured_target",
+        "//src/main/java/com/google/devtools/build/lib/analysis:configured_target_value",
         "//src/main/java/com/google/devtools/build/lib/analysis:dependency",
         "//src/main/java/com/google/devtools/build/lib/analysis:dependency_key",
         "//src/main/java/com/google/devtools/build/lib/analysis:dependency_kind",
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/ConfigurableAttributesTest.java b/src/test/java/com/google/devtools/build/lib/analysis/ConfigurableAttributesTest.java
index c0df00d..280593f 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/ConfigurableAttributesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/ConfigurableAttributesTest.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.analysis;
 
+import static com.google.common.testing.GcFinalization.awaitClear;
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.lib.packages.Attribute.attr;
 import static com.google.devtools.build.lib.packages.BuildType.LABEL_LIST;
@@ -32,9 +33,12 @@
 import com.google.devtools.build.lib.packages.RuleClass.ToolchainResolutionMode;
 import com.google.devtools.build.lib.packages.Type;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
+import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
+import com.google.devtools.build.lib.skyframe.SkyframeExecutorWrappingWalkableGraph;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.FileTypeSet;
 import java.io.IOException;
+import java.lang.ref.WeakReference;
 import java.util.Collection;
 import java.util.Set;
 import org.junit.Before;
@@ -1568,7 +1572,7 @@
   }
 
   @Test
-  public void publicVisibilityConfigSetting__noVisibilityEnforcement() throws Exception {
+  public void publicVisibilityConfigSetting_noVisibilityEnforcement() throws Exception {
     // Production builds default to private visibility, but BuildViewTestCase defaults to public.
     setPackageOptions("--default_visibility=private",
         "--incompatible_enforce_config_setting_visibility=false");
@@ -1927,4 +1931,71 @@
         /*expected:*/ ImmutableList.of("bin java/foo/libb.jar", "bin java/foo/libb2.jar"),
         /*not expected:*/ ImmutableList.of("bin java/foo/liba.jar", "bin java/foo/liba2.jar"));
   }
+
+  @Test
+  public void proxyKeysAreRetained() throws Exception {
+    // This test case verifies that when a ProxyConfiguredTargetKey is created, it is retained.
+    scratch.file(
+        "conditions/BUILD",
+        "constraint_setting(name = 'animal')",
+        "constraint_value(name = 'manatee', constraint_setting = 'animal')",
+        "constraint_value(name = 'koala', constraint_setting = 'animal')",
+        "platform(",
+        "    name = 'manatee_platform',",
+        "    constraint_values = [':manatee'],",
+        ")",
+        "platform(",
+        "    name = 'koala_platform',",
+        "    constraint_values = [':koala'],",
+        ")");
+    scratch.file(
+        "check/BUILD",
+        "filegroup(name = 'adep', srcs = ['afile'])",
+        "filegroup(name = 'bdep', srcs = ['bfile'])",
+        "filegroup(name = 'hello',",
+        "    srcs = select({",
+        "        '//conditions:manatee': [':adep'],",
+        "        '//conditions:koala': [':bdep'],",
+        "    }))");
+
+    useConfiguration("--experimental_platforms=//conditions:manatee_platform");
+    ConfiguredTarget hello = getConfiguredTarget("//check:hello");
+
+    var koalaLabel = Label.parseCanonical("//conditions:koala");
+
+    // Shakes the interner to try to get any non-strongly reachable keys to fall out. This should
+    // cause the ProxyConfiguredTargetKey created for "//conditions:koala" to fall out if it's not
+    // otherwise retained.
+    //
+    // Creates and inserts a canary key into the interner that can be used to detect eviction of
+    // weak keys.
+    var canaryKey = new WeakReference<>(ConfiguredTargetKey.builder().setLabel(koalaLabel).build());
+    awaitClear(canaryKey);
+    // Once we get here we know that the canaryKey is no longer in the weak interner. Due to the
+    // collection properties of weak references, that implies the interner now has no weakly
+    // reachable keys at all.
+
+    // Since //conditions:koala is a ConfigCondition, so it would be requested by //check:hello
+    // using //check:hello's configuration.
+    var koalaOwner =
+        ConfiguredTargetKey.builder()
+            .setLabel(koalaLabel)
+            .setConfigurationKey(hello.getConfigurationKey())
+            .build();
+    // Uses a WalkableGraph lookup to ensure there is an existing //conditions:koala instance that
+    // was created using koalaOwner.
+    var walkableGraph = SkyframeExecutorWrappingWalkableGraph.of(skyframeExecutor);
+    var koala = (ConfiguredTargetValue) walkableGraph.getValue(koalaOwner.toKey());
+    assertThat(koala).isNotNull();
+
+    // constraint_value has a NoConfigTransition rule transition so a corresponding proxy key
+    // should exist.
+    ConfiguredTargetKey koalaKey =
+        ConfiguredTargetKey.builder()
+            .setLabel(koalaLabel)
+            .setConfigurationKey(koala.getConfiguredTarget().getConfigurationKey())
+            .build();
+    assertThat(koalaKey.isProxy()).isTrue();
+    assertThat(koalaKey.toKey()).isEqualTo(koalaOwner);
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
index 2df40a0..aa2c41c 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
@@ -651,7 +651,7 @@
       result =
           getDependencyContext(
               state,
-              /* parentExecutionPlatformLabel= */ null,
+              ConfiguredTargetKey.fromConfiguredTarget(configuredTarget),
               ruleClassProvider,
               TransitiveDependencyState.createForTesting(
                   transitiveRootCauses, /* transitivePackages= */ null),
diff --git a/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryHelper.java b/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryHelper.java
index d28dac3..0c93b1a 100644
--- a/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryHelper.java
+++ b/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryHelper.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.query2.aquery;
 
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.analysis.ConfiguredTargetValue;
 import com.google.devtools.build.lib.query2.PostAnalysisQueryEnvironment;
 import com.google.devtools.build.lib.query2.PostAnalysisQueryEnvironment.TopLevelConfigurations;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
@@ -23,14 +24,13 @@
 import java.util.Collection;
 
 /** Helper class for aquery test */
-public class ActionGraphQueryHelper extends PostAnalysisQueryHelper<KeyedConfiguredTargetValue> {
+public class ActionGraphQueryHelper extends PostAnalysisQueryHelper<ConfiguredTargetValue> {
 
   @Override
-  protected PostAnalysisQueryEnvironment<KeyedConfiguredTargetValue>
-      getPostAnalysisQueryEnvironment(
-          WalkableGraph walkableGraph,
-          TopLevelConfigurations topLevelConfigurations,
-          Collection<SkyKey> transitiveConfigurationKeys) {
+  protected PostAnalysisQueryEnvironment<ConfiguredTargetValue> getPostAnalysisQueryEnvironment(
+      WalkableGraph walkableGraph,
+      TopLevelConfigurations topLevelConfigurations,
+      Collection<SkyKey> transitiveConfigurationKeys) {
     ImmutableList<QueryFunction> extraFunctions =
         ImmutableList.copyOf(ActionGraphQueryEnvironment.AQUERY_FUNCTIONS);
     return new ActionGraphQueryEnvironment(
@@ -45,7 +45,7 @@
   }
 
   @Override
-  public String getLabel(KeyedConfiguredTargetValue configuredTargetValue) {
+  public String getLabel(ConfiguredTargetValue configuredTargetValue) {
     return configuredTargetValue.getConfiguredTarget().getLabel().toString();
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryTest.java b/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryTest.java
index f29657b..97320f2 100644
--- a/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/query2/aquery/ActionGraphQueryTest.java
@@ -17,6 +17,7 @@
 import static com.google.common.truth.Truth.assertThat;
 
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.analysis.ConfiguredTargetValue;
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationValue;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 import com.google.devtools.build.lib.query2.testutil.PostAnalysisQueryTest;
@@ -29,7 +30,7 @@
 
 /** Tests for {@link ActionGraphQueryEnvironment}. */
 @RunWith(JUnit4.class)
-public class ActionGraphQueryTest extends PostAnalysisQueryTest<KeyedConfiguredTargetValue> {
+public class ActionGraphQueryTest extends PostAnalysisQueryTest<ConfiguredTargetValue> {
   @Override
   protected HashMap<String, QueryFunction> getDefaultFunctions() {
     ImmutableList<QueryFunction> defaultFunctions =
@@ -45,8 +46,7 @@
   }
 
   @Override
-  protected BuildConfigurationValue getConfiguration(
-      KeyedConfiguredTargetValue configuredTargetValue) {
+  protected BuildConfigurationValue getConfiguration(ConfiguredTargetValue configuredTargetValue) {
     return getHelper()
         .getSkyframeExecutor()
         .getConfiguration(
@@ -55,7 +55,7 @@
   }
 
   @Override
-  protected QueryHelper<KeyedConfiguredTargetValue> createQueryHelper() {
+  protected QueryHelper<ConfiguredTargetValue> createQueryHelper() {
     return new ActionGraphQueryHelper();
   }
 
@@ -64,12 +64,12 @@
   public void testMultipleTopLevelConfigurations_nullConfigs() throws Exception {
     writeFile("test/BUILD", "java_library(name='my_java',", "  srcs = ['foo.java'],", ")");
 
-    Set<KeyedConfiguredTargetValue> result = eval("//test:my_java+//test:foo.java");
+    Set<ConfiguredTargetValue> result = eval("//test:my_java+//test:foo.java");
 
     assertThat(result).hasSize(2);
 
-    Iterator<KeyedConfiguredTargetValue> resultIterator = result.iterator();
-    KeyedConfiguredTargetValue first = resultIterator.next();
+    Iterator<ConfiguredTargetValue> resultIterator = result.iterator();
+    ConfiguredTargetValue first = resultIterator.next();
     if (first.getConfiguredTarget().getLabel().toString().equals("//test:foo.java")) {
       assertThat(getConfiguration(first)).isNull();
       assertThat(getConfiguration(resultIterator.next())).isNotNull();
@@ -126,7 +126,7 @@
         ")");
     appendToWorkspace("register_toolchains('//q:tc.toolchain')");
 
-    Set<KeyedConfiguredTargetValue> result = eval("deps('//q:r')");
+    Set<ConfiguredTargetValue> result = eval("deps('//q:r')");
 
     assertDoesNotContainEvent("Targets were missing from graph");
     assertThat(
diff --git a/src/test/java/com/google/devtools/build/lib/query2/aquery/BUILD b/src/test/java/com/google/devtools/build/lib/query2/aquery/BUILD
index 9ccefea..8f91b71 100644
--- a/src/test/java/com/google/devtools/build/lib/query2/aquery/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/query2/aquery/BUILD
@@ -16,6 +16,7 @@
     testonly = 1,
     srcs = ["ActionGraphQueryHelper.java"],
     deps = [
+        "//src/main/java/com/google/devtools/build/lib/analysis:configured_target_value",
         "//src/main/java/com/google/devtools/build/lib/query2",
         "//src/main/java/com/google/devtools/build/lib/query2/engine",
         "//src/main/java/com/google/devtools/build/skyframe",
@@ -33,6 +34,7 @@
     deps = [
         ":action_graph_query_helper",
         "//src/main/java/com/google/devtools/build/lib/analysis:config/build_configuration",
+        "//src/main/java/com/google/devtools/build/lib/analysis:configured_target_value",
         "//src/main/java/com/google/devtools/build/lib/query2",
         "//src/main/java/com/google/devtools/build/lib/query2/engine",
         "//src/test/java/com/google/devtools/build/lib/query2/testutil",
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/toolchains/ToolchainsForTargetsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/toolchains/ToolchainsForTargetsTest.java
index bec0a7f..98ca431 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/toolchains/ToolchainsForTargetsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/toolchains/ToolchainsForTargetsTest.java
@@ -140,7 +140,7 @@
         result =
             getDependencyContext(
                 state,
-                key.configuredTargetKey().getExecutionPlatformLabel(),
+                key.configuredTargetKey(),
                 stateProvider.lateBoundRuleClassProvider(),
                 TransitiveDependencyState.createForTesting(
                     transitiveRootCauses, /* transitivePackages= */ null),