diff --git a/src/main/java/com/google/devtools/build/lib/analysis/Util.java b/src/main/java/com/google/devtools/build/lib/analysis/Util.java
index 22e9058..f1b24a4 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/Util.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Util.java
@@ -17,7 +17,6 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Sets;
-import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.packages.AttributeMap;
@@ -29,14 +28,12 @@
 import java.util.List;
 import java.util.Set;
 
-/**
- * Utility methods for use by ConfiguredTarget implementations.
- */
+/** Utility methods for use by ConfiguredTarget implementations. */
 public abstract class Util {
 
   private Util() {}
 
-  //---------- Label and Target related methods
+  // ---------- Label and Target related methods
 
   /**
    * Returns the workspace-relative path of the specified target (file or rule).
@@ -57,8 +54,8 @@
   }
 
   /**
-   * Returns the workspace-relative path of the specified target (file or rule),
-   * prepending a prefix and appending a suffix.
+   * Returns the workspace-relative path of the specified target (file or rule), prepending a prefix
+   * and appending a suffix.
    *
    * <p>For example, "//foo/bar:wiz" and "//foo:bar/wiz" both result in "foo/bar/wiz".
    */
@@ -66,9 +63,7 @@
     return target.getLabel().getPackageFragment().getRelative(prefix + target.getName() + suffix);
   }
 
-  /**
-   * Checks if a PathFragment contains a '-'.
-   */
+  /** Checks if a PathFragment contains a '-'. */
   public static boolean containsHyphen(PathFragment path) {
     return path.getPathString().indexOf('-') >= 0;
   }
@@ -76,12 +71,14 @@
   // ---------- Implicit dependency extractor
 
   /*
-   * Given a RuleContext, find all the implicit deps aka deps that weren't explicitly set in the
-   * build file and all toolchain deps.
+   * Given a RuleContext, find all the implicit attribute deps aka deps that weren't explicitly set
+   * in the build file but are attached behind the scenes to some attribute. This means this
+   * function does *not* cover deps attached other ways e.g. toolchain-related implicit deps
+   * (see {@link PostAnalysisQueryEnvironment#targetifyValues} for more info on further implicit
+   * deps filtering).
    * note: nodes that are depended on both implicitly and explicitly are considered explicit.
    */
   public static ImmutableSet<ConfiguredTargetKey> findImplicitDeps(RuleContext ruleContext) {
-    // (1) Consider rule attribute dependencies.
     Set<ConfiguredTargetKey> maybeImplicitDeps = CompactHashSet.create();
     Set<ConfiguredTargetKey> explicitDeps = CompactHashSet.create();
     AttributeMap attributes = ruleContext.attributes();
@@ -97,18 +94,6 @@
         }
       }
     }
-    // (2) Consider toolchain dependencies
-    ToolchainContext toolchainContext = ruleContext.getToolchainContext();
-    if (toolchainContext != null) {
-      BuildConfiguration config = ruleContext.getConfiguration();
-      for (Label toolchain : toolchainContext.resolvedToolchainLabels()) {
-        maybeImplicitDeps.add(ConfiguredTargetKey.of(toolchain, config));
-      }
-      maybeImplicitDeps.add(
-          ConfiguredTargetKey.of(toolchainContext.executionPlatform().label(), config));
-      maybeImplicitDeps.add(
-          ConfiguredTargetKey.of(toolchainContext.targetPlatform().label(), config));
-    }
     return ImmutableSet.copyOf(Sets.difference(maybeImplicitDeps, explicitDeps));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/PostAnalysisQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/PostAnalysisQueryEnvironment.java
index 50db0b9c..d670db1 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/PostAnalysisQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/PostAnalysisQueryEnvironment.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2;
 
-
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -70,7 +69,6 @@
 import com.google.devtools.build.skyframe.WalkableGraph;
 import java.io.IOException;
 import java.io.OutputStream;
-import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
@@ -239,8 +237,8 @@
     for (T target : targets) {
       targetsByKey.put(getSkyKey(target), target);
     }
-    Map<SkyKey, Collection<T>> directDeps =
-        targetifyValues(graph.getDirectDeps(targetsByKey.keySet()));
+    Map<SkyKey, ImmutableList<ClassifiedDependency<T>>> directDeps =
+        targetifyValues(targetsByKey, graph.getDirectDeps(targetsByKey.keySet()));
     if (targetsByKey.size() != directDeps.size()) {
       Iterable<ConfiguredTargetKey> missingTargets =
           Sets.difference(targetsByKey.keySet(), directDeps.keySet()).stream()
@@ -249,7 +247,7 @@
       eventHandler.handle(Event.warn("Targets were missing from graph: " + missingTargets));
     }
     ThreadSafeMutableSet<T> result = createThreadSafeMutableSet();
-    for (Map.Entry<SkyKey, Collection<T>> entry : directDeps.entrySet()) {
+    for (Map.Entry<SkyKey, ImmutableList<ClassifiedDependency<T>>> entry : directDeps.entrySet()) {
       result.addAll(filterFwdDeps(targetsByKey.get(entry.getKey()), entry.getValue()));
     }
     return result;
@@ -261,9 +259,10 @@
     return getFwdDeps(targets);
   }
 
-  private Collection<T> filterFwdDeps(T configTarget, Collection<T> rawFwdDeps) {
+  private ImmutableList<T> filterFwdDeps(
+      T configTarget, ImmutableList<ClassifiedDependency<T>> rawFwdDeps) {
     if (settings.isEmpty()) {
-      return rawFwdDeps;
+      return getDependencies(rawFwdDeps);
     }
     return getAllowedDeps(configTarget, rawFwdDeps);
   }
@@ -275,8 +274,8 @@
     for (T target : targets) {
       targetsByKey.put(getSkyKey(target), target);
     }
-    Map<SkyKey, Collection<T>> reverseDepsByKey =
-        targetifyValues(graph.getReverseDeps(targetsByKey.keySet()));
+    Map<SkyKey, ImmutableList<ClassifiedDependency<T>>> reverseDepsByKey =
+        targetifyValues(targetsByKey, graph.getReverseDeps(targetsByKey.keySet()));
     if (targetsByKey.size() != reverseDepsByKey.size()) {
       Iterable<ConfiguredTargetKey> missingTargets =
           Sets.difference(targetsByKey.keySet(), reverseDepsByKey.keySet()).stream()
@@ -284,23 +283,27 @@
               .collect(Collectors.toList());
       eventHandler.handle(Event.warn("Targets were missing from graph: " + missingTargets));
     }
-    Map<T, Collection<T>> reverseDepsByCT = new HashMap<>();
-    for (Map.Entry<SkyKey, Collection<T>> entry : reverseDepsByKey.entrySet()) {
+    Map<T, ImmutableList<ClassifiedDependency<T>>> reverseDepsByCT = new HashMap<>();
+    for (Map.Entry<SkyKey, ImmutableList<ClassifiedDependency<T>>> entry :
+        reverseDepsByKey.entrySet()) {
       reverseDepsByCT.put(targetsByKey.get(entry.getKey()), entry.getValue());
     }
     return reverseDepsByCT.isEmpty() ? Collections.emptyList() : filterReverseDeps(reverseDepsByCT);
   }
 
-  private Collection<T> filterReverseDeps(Map<T, Collection<T>> rawReverseDeps) {
+  private Collection<T> filterReverseDeps(
+      Map<T, ImmutableList<ClassifiedDependency<T>>> rawReverseDeps) {
     Set<T> result = CompactHashSet.create();
-    for (Map.Entry<T, Collection<T>> targetAndRdeps : rawReverseDeps.entrySet()) {
-      ImmutableSet.Builder<T> ruleDeps = ImmutableSet.builder();
-      for (T parent : targetAndRdeps.getValue()) {
-        if (parent instanceof RuleConfiguredTarget
+    for (Map.Entry<T, ImmutableList<ClassifiedDependency<T>>> targetAndRdeps :
+        rawReverseDeps.entrySet()) {
+      ImmutableList.Builder<ClassifiedDependency<T>> ruleDeps = ImmutableList.builder();
+      for (ClassifiedDependency<T> parent : targetAndRdeps.getValue()) {
+        T dependency = parent.dependency;
+        if (parent.dependency instanceof RuleConfiguredTarget
             && dependencyFilter != DependencyFilter.ALL_DEPS) {
           ruleDeps.add(parent);
         } else {
-          result.add(parent);
+          result.add(dependency);
         }
       }
       result.addAll(getAllowedDeps(targetAndRdeps.getKey(), ruleDeps.build()));
@@ -312,7 +315,7 @@
    * @param target source target
    * @param deps next level of deps to filter
    */
-  protected Collection<T> getAllowedDeps(T target, Collection<T> deps) {
+  private ImmutableList<T> getAllowedDeps(T target, Collection<ClassifiedDependency<T>> deps) {
     // It's possible to query on a target that's configured in the host configuration. In those
     // cases if --notool_deps is turned on, we only allow reachable targets that are ALSO in the
     // host config. This is somewhat counterintuitive and subject to change in the future but seems
@@ -324,8 +327,8 @@
             deps.stream()
                 .filter(
                     dep ->
-                        getConfiguration(dep) != null
-                            && getConfiguration(dep).isToolConfiguration())
+                        getConfiguration(dep.dependency) != null
+                            && getConfiguration(dep.dependency).isToolConfiguration())
                 .collect(Collectors.toList());
       } else {
         deps =
@@ -336,53 +339,88 @@
                         // they can also appear on host-configured attributes like genrule#tools.
                         // While this may not be strictly correct, it's better to overapproximate
                         // than underapproximate the results.
-                        getConfiguration(dep) == null
-                            || !getConfiguration(dep).isToolConfiguration())
+                        getConfiguration(dep.dependency) == null
+                            || !getConfiguration(dep.dependency).isToolConfiguration())
                 .collect(Collectors.toList());
       }
     }
     if (settings.contains(Setting.NO_IMPLICIT_DEPS)) {
       RuleConfiguredTarget ruleConfiguredTarget = getRuleConfiguredTarget(target);
       if (ruleConfiguredTarget != null) {
-        Set<ConfiguredTargetKey> implicitDeps = ruleConfiguredTarget.getImplicitDeps();
-        deps =
-            deps.stream()
-                .filter(
-                    dep ->
-                        !implicitDeps.contains(
-                            ConfiguredTargetKey.of(getCorrectLabel(dep), getConfiguration(dep))))
-                .collect(Collectors.toList());
+        deps = deps.stream().filter(dep -> !dep.implicit).collect(Collectors.toList());
       }
     }
-    return deps;
+    return getDependencies(deps);
   }
 
   protected abstract RuleConfiguredTarget getRuleConfiguredTarget(T target);
 
-  protected Collection<T> targetifyValues(Iterable<SkyKey> dependencies)
-      throws InterruptedException {
-    Collection<T> values = new ArrayList<>();
-    for (SkyKey key : dependencies) {
-      if (key.functionName().equals(SkyFunctions.CONFIGURED_TARGET)) {
-        values.add(getValueFromKey(key));
-      } else if (key.functionName().equals(SkyFunctions.TOOLCHAIN_RESOLUTION)) {
-        // Also fetch these dependencies.
-        Collection<T> toolchainDeps = targetifyValues(graph.getDirectDeps(key));
-        values.addAll(toolchainDeps);
+  /**
+   * Returns targetified dependencies wrapped as {@link ClassifiedDependency} objects which include
+   * information on if the target is an implicit or explicit dependency.
+   *
+   * @param parent Parent target that knows about its attribute-attached implicit deps. If this is
+   *     null, that is a signal from the caller that all dependencies should be considered implicit.
+   * @param dependencies dependencies to targetify
+   */
+  private ImmutableList<ClassifiedDependency<T>> targetifyValues(
+      @Nullable T parent, Iterable<SkyKey> dependencies) throws InterruptedException {
+    Collection<ConfiguredTargetKey> implicitDeps = null;
+    if (parent != null) {
+      RuleConfiguredTarget ruleConfiguredTarget = getRuleConfiguredTarget(parent);
+      if (ruleConfiguredTarget != null) {
+        implicitDeps = ruleConfiguredTarget.getImplicitDeps();
       }
     }
-    return values;
+
+    ImmutableList.Builder<ClassifiedDependency<T>> values = ImmutableList.builder();
+    for (SkyKey key : dependencies) {
+      if (key.functionName().equals(SkyFunctions.CONFIGURED_TARGET)) {
+        T dependency = getValueFromKey(key);
+        boolean implicit =
+            implicitDeps == null
+                || implicitDeps.contains(
+                    ConfiguredTargetKey.of(
+                        getCorrectLabel(dependency), getConfiguration(dependency)));
+        values.add(new ClassifiedDependency<>(dependency, implicit));
+      } else if (key.functionName().equals(SkyFunctions.TOOLCHAIN_RESOLUTION)) {
+        // Also fetch these dependencies.
+        values.addAll(targetifyValues(null, graph.getDirectDeps(key)));
+      }
+    }
+    return values.build();
   }
 
-  protected Map<SkyKey, Collection<T>> targetifyValues(
-      Map<SkyKey, ? extends Iterable<SkyKey>> input) throws InterruptedException {
-    Map<SkyKey, Collection<T>> result = new HashMap<>();
+  private Map<SkyKey, ImmutableList<ClassifiedDependency<T>>> targetifyValues(
+      Map<SkyKey, T> fromTargetsByKey, Map<SkyKey, ? extends Iterable<SkyKey>> input)
+      throws InterruptedException {
+    Map<SkyKey, ImmutableList<ClassifiedDependency<T>>> result = new HashMap<>();
     for (Map.Entry<SkyKey, ? extends Iterable<SkyKey>> entry : input.entrySet()) {
-      result.put(entry.getKey(), targetifyValues(entry.getValue()));
+      SkyKey fromKey = entry.getKey();
+      result.put(fromKey, targetifyValues(fromTargetsByKey.get(fromKey), entry.getValue()));
     }
     return result;
   }
 
+  /** A class to store a dependency with some information. */
+  private static class ClassifiedDependency<T> {
+    // True if this dependency is attached implicitly.
+    boolean implicit;
+    T dependency;
+
+    private ClassifiedDependency(T dependency, boolean implicit) {
+      this.implicit = implicit;
+      this.dependency = dependency;
+    }
+  }
+
+  private static <T> ImmutableList<T> getDependencies(
+      Collection<ClassifiedDependency<T>> classifiedDependencies) {
+    return classifiedDependencies.stream()
+        .map(dep -> dep.dependency)
+        .collect(ImmutableList.toImmutableList());
+  }
+
   @Nullable
   protected abstract BuildConfiguration getConfiguration(T target);
 
diff --git a/src/test/java/com/google/devtools/build/lib/query2/testutil/PostAnalysisQueryTest.java b/src/test/java/com/google/devtools/build/lib/query2/testutil/PostAnalysisQueryTest.java
index 9a261e4..c984d1a 100644
--- a/src/test/java/com/google/devtools/build/lib/query2/testutil/PostAnalysisQueryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/query2/testutil/PostAnalysisQueryTest.java
@@ -258,6 +258,31 @@
         .doesNotContain(evalToListOfStrings(implicits));
   }
 
+  // Regression test for b/148550864
+  @Test
+  public void testNoImplicitDeps_platformDeps() throws Exception {
+    MockRule simpleRule = () -> MockRule.define("simple_rule");
+    helper.useRuleClassProvider(setRuleClassProviders(simpleRule).build());
+
+    writeFile(
+        "test/BUILD",
+        "simple_rule(name = 'my_rule')",
+        "platform(name = 'host_platform')",
+        "platform(name = 'execution_platform')");
+
+    ((PostAnalysisQueryHelper<T>) helper)
+        .useConfiguration(
+            "--host_platform=//test:host_platform",
+            "--extra_execution_platforms=//test:execution_platform");
+
+    // Check for platform dependencies
+    assertThat(evalToListOfStrings("deps(//test:my_rule)"))
+        .containsAtLeastElementsIn(
+            evalToListOfStrings("//test:execution_platform + //test:host_platform"));
+    helper.setQuerySettings(Setting.NO_IMPLICIT_DEPS);
+    assertThat(evalToListOfStrings("deps(//test:my_rule)")).containsExactly("//test:my_rule");
+  }
+
   @Test
   public void testNoImplicitDeps_computedDefault() throws Exception {
     MockRule computedDefaultRule =