diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 55bcf81..5fed4a3 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -18,13 +18,10 @@
 import com.google.common.base.Function;
 import com.google.common.base.Predicate;
 import com.google.common.base.Verify;
-import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableListMultimap;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
@@ -74,6 +71,7 @@
 import com.google.devtools.build.lib.skyframe.SkyframeBuildView;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.RegexFilter;
@@ -877,12 +875,12 @@
   }
 
   @VisibleForTesting
-  public ListMultimap<Attribute, Dependency> getDirectPrerequisiteDependenciesForTesting(
+  public OrderedSetMultimap<Attribute, Dependency> getDirectPrerequisiteDependenciesForTesting(
       final EventHandler eventHandler, final ConfiguredTarget ct,
       BuildConfigurationCollection configurations)
       throws EvalException, InvalidConfigurationException, InterruptedException {
     if (!(ct.getTarget() instanceof Rule)) {
-      return ArrayListMultimap.create();
+      return OrderedSetMultimap.create();
     }
 
     class SilentDependencyResolver extends DependencyResolver {
@@ -965,23 +963,22 @@
     return ImmutableMap.copyOf(keys);
   }
 
-  private ListMultimap<Attribute, ConfiguredTarget> getPrerequisiteMapForTesting(
+  private OrderedSetMultimap<Attribute, ConfiguredTarget> getPrerequisiteMapForTesting(
       final EventHandler eventHandler, ConfiguredTarget target,
       BuildConfigurationCollection configurations)
       throws EvalException, InvalidConfigurationException, InterruptedException {
-    ListMultimap<Attribute, Dependency> depNodeNames = getDirectPrerequisiteDependenciesForTesting(
-        eventHandler, target, configurations);
+    OrderedSetMultimap<Attribute, Dependency> depNodeNames =
+        getDirectPrerequisiteDependenciesForTesting(eventHandler, target, configurations);
 
     ImmutableMap<Dependency, ConfiguredTarget> cts = skyframeExecutor.getConfiguredTargetMap(
         eventHandler,
         target.getConfiguration(), ImmutableSet.copyOf(depNodeNames.values()), false);
 
-    ImmutableListMultimap.Builder<Attribute, ConfiguredTarget> builder =
-        ImmutableListMultimap.builder();
+    OrderedSetMultimap<Attribute, ConfiguredTarget> result = OrderedSetMultimap.create();
     for (Map.Entry<Attribute, Dependency> entry : depNodeNames.entries()) {
-      builder.put(entry.getKey(), cts.get(entry.getValue()));
+      result.put(entry.getKey(), cts.get(entry.getValue()));
     }
-    return builder.build();
+    return result;
   }
 
   /**
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 ac47679..0ace78b 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
@@ -16,7 +16,6 @@
 
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -51,6 +50,7 @@
 import com.google.devtools.build.lib.rules.SkylarkRuleConfiguredTargetBuilder;
 import com.google.devtools.build.lib.rules.fileset.FilesetProvider;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
@@ -79,7 +79,7 @@
    * to the {@code AnalysisEnvironment}.
    */
   private NestedSet<PackageSpecification> convertVisibility(
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap, EventHandler reporter,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap, EventHandler reporter,
       Target target, BuildConfiguration packageGroupConfiguration) {
     RuleVisibility ruleVisibility = target.getVisibility();
     if (ruleVisibility instanceof ConstantRuleVisibility) {
@@ -125,7 +125,7 @@
   }
 
   private ConfiguredTarget findPrerequisite(
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap, Label label,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap, Label label,
       BuildConfiguration config) {
     for (ConfiguredTarget prerequisite : prerequisiteMap.get(null)) {
       if (prerequisite.getLabel().equals(label) && (prerequisite.getConfiguration() == config)) {
@@ -163,7 +163,8 @@
   @Nullable
   public final ConfiguredTarget createConfiguredTarget(AnalysisEnvironment analysisEnvironment,
       ArtifactFactory artifactFactory, Target target, BuildConfiguration config,
-      BuildConfiguration hostConfig, ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      BuildConfiguration hostConfig,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws InterruptedException {
     if (target instanceof Rule) {
@@ -218,7 +219,7 @@
   private ConfiguredTarget createRule(
       AnalysisEnvironment env, Rule rule, BuildConfiguration configuration,
       BuildConfiguration hostConfiguration,
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
     // Visibility computation and checking is done for every rule.
     RuleContext ruleContext =
@@ -310,7 +311,7 @@
       RuleConfiguredTarget associatedTarget,
       ConfiguredAspectFactory aspectFactory,
       Aspect aspect,
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       BuildConfiguration aspectConfiguration,
       BuildConfiguration hostConfiguration)
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
index 3956037..6816b42 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
@@ -14,12 +14,10 @@
 package com.google.devtools.build.lib.analysis;
 
 import com.google.common.base.Verify;
-import com.google.common.collect.ArrayListMultimap;
 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.common.collect.ListMultimap;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
@@ -45,6 +43,7 @@
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 
 import java.util.ArrayList;
@@ -92,14 +91,14 @@
    *
    * @return a mapping of each attribute in this rule or aspect to its dependent nodes
    */
-  public final ListMultimap<Attribute, Dependency> dependentNodeMap(
+  public final OrderedSetMultimap<Attribute, Dependency> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       @Nullable Aspect aspect,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws EvalException, InvalidConfigurationException, InterruptedException {
     NestedSetBuilder<Label> rootCauses = NestedSetBuilder.<Label>stableOrder();
-    ListMultimap<Attribute, Dependency> outgoingEdges = dependentNodeMap(
+    OrderedSetMultimap<Attribute, Dependency> outgoingEdges = dependentNodeMap(
         node, hostConfig, aspect, configConditions, rootCauses);
     if (!rootCauses.isEmpty()) {
       throw new IllegalStateException(rootCauses.build().iterator().next().toString());
@@ -135,7 +134,7 @@
    *
    * @return a mapping of each attribute in this rule or aspect to its dependent nodes
    */
-  public final ListMultimap<Attribute, Dependency> dependentNodeMap(
+  public final OrderedSetMultimap<Attribute, Dependency> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       @Nullable Aspect aspect,
@@ -144,7 +143,7 @@
       throws EvalException, InvalidConfigurationException, InterruptedException {
     Target target = node.getTarget();
     BuildConfiguration config = node.getConfiguration();
-    ListMultimap<Attribute, Dependency> outgoingEdges = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Dependency> outgoingEdges = OrderedSetMultimap.create();
     if (target instanceof OutputFile) {
       Preconditions.checkNotNull(config);
       visitTargetVisibility(node, rootCauses, outgoingEdges.get(null));
@@ -170,7 +169,7 @@
       @Nullable Aspect aspect,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Label> rootCauses,
-      ListMultimap<Attribute, Dependency> outgoingEdges)
+      OrderedSetMultimap<Attribute, Dependency> outgoingEdges)
       throws EvalException, InvalidConfigurationException, InterruptedException {
     Preconditions.checkArgument(node.getTarget() instanceof Rule);
     BuildConfiguration ruleConfig = Preconditions.checkNotNull(node.getConfiguration());
@@ -475,12 +474,13 @@
    * @throws IllegalArgumentException if the {@code node} does not refer to a {@link Rule} instance
    */
   public final Collection<Dependency> resolveRuleLabels(TargetAndConfiguration node,
-      ListMultimap<Attribute, Label> depLabels, NestedSetBuilder<Label> rootCauses) {
+      OrderedSetMultimap<Attribute, Label> depLabels, NestedSetBuilder<Label> rootCauses) {
     Preconditions.checkArgument(node.getTarget() instanceof Rule);
     Rule rule = (Rule) node.getTarget();
-    ListMultimap<Attribute, Dependency> outgoingEdges = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Dependency> outgoingEdges = OrderedSetMultimap.create();
     RuleResolver depResolver = new RuleResolver(rule, node.getConfiguration(), /*aspect=*/null,
         /*attributeMap=*/null, rootCauses, outgoingEdges);
+    Map<Attribute, Collection<Label>> m = depLabels.asMap();
     for (Map.Entry<Attribute, Collection<Label>> entry : depLabels.asMap().entrySet()) {
       for (Label depLabel : entry.getValue()) {
         depResolver.resolveDep(entry.getKey(), depLabel);
@@ -572,7 +572,7 @@
     private final Aspect aspect;
     private final ConfiguredAttributeMapper attributeMap;
     private final NestedSetBuilder<Label> rootCauses;
-    private final ListMultimap<Attribute, Dependency> outgoingEdges;
+    private final OrderedSetMultimap<Attribute, Dependency> outgoingEdges;
     private final List<Attribute> attributes;
 
     /**
@@ -587,7 +587,7 @@
      */
     RuleResolver(Rule rule, BuildConfiguration ruleConfig, Aspect aspect,
         ConfiguredAttributeMapper attributeMap, NestedSetBuilder<Label> rootCauses,
-        ListMultimap<Attribute, Dependency> outgoingEdges) {
+        OrderedSetMultimap<Attribute, Dependency> outgoingEdges) {
       this.rule = rule;
       this.ruleConfig = ruleConfig;
       this.aspect = aspect;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index d4cea81..321c385 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -78,6 +78,7 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.FileTypeSet;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
@@ -1398,7 +1399,7 @@
     private final PrerequisiteValidator prerequisiteValidator;
     @Nullable private final String aspectName;
     private final ErrorReporter reporter;
-    private ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap;
+    private OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap;
     private ImmutableMap<Label, ConfigMatchingProvider> configConditions;
     private NestedSet<PackageSpecification> visibility;
     private ImmutableMap<String, Attribute> aspectAttributes;
@@ -1455,7 +1456,7 @@
      * Sets the prerequisites and checks their visibility. It also generates appropriate error or
      * warning messages and sets the error flag as appropriate.
      */
-    Builder setPrerequisites(ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap) {
+    Builder setPrerequisites(OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap) {
       this.prerequisiteMap = Preconditions.checkNotNull(prerequisiteMap);
       return this;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java b/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
index ff60869..cf1afb2 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -48,14 +49,16 @@
 
   /**
    * The constructor is intentionally package private.
+   *
+   * <p>directPrerequisites is expected to be ordered.
    */
   TargetContext(AnalysisEnvironment env, Target target, BuildConfiguration configuration,
-      List<ConfiguredTarget> directPrerequisites,
+      Iterable<ConfiguredTarget> directPrerequisites,
       NestedSet<PackageSpecification> visibility) {
     this.env = env;
     this.target = target;
     this.configuration = configuration;
-    this.directPrerequisites = directPrerequisites;
+    this.directPrerequisites = ImmutableList.<ConfiguredTarget>copyOf(directPrerequisites);
     this.visibility = visibility;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index 9de5f09..c1f8c33 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -16,7 +16,6 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.analysis.CachingAnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
@@ -52,6 +51,7 @@
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction.SkylarkImportFailedException;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -230,7 +230,7 @@
         return null;
       }
 
-      ListMultimap<Attribute, ConfiguredTarget> depValueMap =
+      OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap =
           ConfiguredTargetFunction.computeDependencies(
               env,
               resolver,
@@ -310,7 +310,7 @@
       RuleConfiguredTarget associatedTarget,
       BuildConfiguration aspectConfiguration,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
-      ListMultimap<Attribute, ConfiguredTarget> directDeps,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> directDeps,
       NestedSetBuilder<Package> transitivePackages)
       throws AspectFunctionException, InterruptedException {
 
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 b09fc1d..9a82ef4 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
@@ -16,12 +16,11 @@
 import com.google.common.base.Function;
 import com.google.common.base.Joiner;
 import com.google.common.base.Verify;
-import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.LinkedHashMultimap;
 import com.google.common.collect.LinkedListMultimap;
-import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
@@ -68,6 +67,7 @@
 import com.google.devtools.build.lib.skyframe.AspectFunction.AspectCreationException;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -213,7 +213,7 @@
             new ConfiguredValueCreationException(transitiveLoadingRootCauses.build()));
       }
 
-      ListMultimap<Attribute, ConfiguredTarget> depValueMap =
+      OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap =
           computeDependencies(
               env,
               resolver,
@@ -275,7 +275,7 @@
    *     the host configuration as early as possible and pass this reference to all consumers
    * */
   @Nullable
-  static ListMultimap<Attribute, ConfiguredTarget> computeDependencies(
+  static OrderedSetMultimap<Attribute, ConfiguredTarget> computeDependencies(
       Environment env,
       SkyframeDependencyResolver resolver,
       TargetAndConfiguration ctgValue,
@@ -286,8 +286,8 @@
       NestedSetBuilder<Package> transitivePackages,
       NestedSetBuilder<Label> transitiveLoadingRootCauses)
       throws DependencyEvaluationException, AspectCreationException, InterruptedException {
-    // Create the map from attributes to list of (target, configuration) pairs.
-    ListMultimap<Attribute, Dependency> depValueNames;
+    // Create the map from attributes to set of (target, configuration) pairs.
+    OrderedSetMultimap<Attribute, Dependency> depValueNames;
     try {
       depValueNames = resolver.dependentNodeMap(
           ctgValue, hostConfiguration, aspect, configConditions, transitiveLoadingRootCauses);
@@ -318,7 +318,7 @@
     }
 
     // Resolve required aspects.
-    ListMultimap<SkyKey, ConfiguredAspect> depAspects = resolveAspectDependencies(
+    OrderedSetMultimap<SkyKey, ConfiguredAspect> depAspects = resolveAspectDependencies(
         env, depValues, depValueNames.values(), transitivePackages);
     if (depAspects == null) {
       return null;
@@ -421,8 +421,8 @@
    * changes you make.
    */
   @Nullable
-  static ListMultimap<Attribute, Dependency> trimConfigurations(Environment env,
-      TargetAndConfiguration ctgValue, ListMultimap<Attribute, Dependency> originalDeps,
+  static OrderedSetMultimap<Attribute, Dependency> trimConfigurations(Environment env,
+      TargetAndConfiguration ctgValue, OrderedSetMultimap<Attribute, Dependency> originalDeps,
       BuildConfiguration hostConfiguration, RuleClassProvider ruleClassProvider)
       throws DependencyEvaluationException {
 
@@ -450,7 +450,7 @@
     // the results in order (some results need Skyframe-evaluated configurations while others can
     // be computed trivially), we dump them all into this map, then as a final step iterate through
     // the original list and pluck out values from here for the final value.
-    Multimap<AttributeAndLabel, Dependency> trimmedDeps = ArrayListMultimap.create();
+    Multimap<AttributeAndLabel, Dependency> trimmedDeps = LinkedHashMultimap.create();
 
     for (Map.Entry<Attribute, Dependency> depsEntry : originalDeps.entries()) {
       Dependency dep = depsEntry.getValue();
@@ -576,7 +576,7 @@
 
     // Re-assemble the output map with the same value ordering (e.g. each attribute's dep labels
     // appear in the same order) as the input.
-    ListMultimap<Attribute, Dependency> result = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Dependency> result = OrderedSetMultimap.create();
     for (Map.Entry<Attribute, Dependency> depsEntry : originalDeps.entries()) {
       Collection<Dependency> trimmedAttrDeps = trimmedDeps.get(
           new AttributeAndLabel(depsEntry.getKey(), depsEntry.getValue().getLabel()));
@@ -655,11 +655,11 @@
    * combinations of aspects for a particular configured target, so it would result in a
    * combinatiorial explosion of Skyframe nodes.
    */
-  private static ListMultimap<Attribute, ConfiguredTarget> mergeAspects(
-      ListMultimap<Attribute, Dependency> depValueNames,
+  private static OrderedSetMultimap<Attribute, ConfiguredTarget> mergeAspects(
+      OrderedSetMultimap<Attribute, Dependency> depValueNames,
       Map<SkyKey, ConfiguredTarget> depConfiguredTargetMap,
-      ListMultimap<SkyKey, ConfiguredAspect> depAspectMap) {
-    ListMultimap<Attribute, ConfiguredTarget> result = ArrayListMultimap.create();
+      OrderedSetMultimap<SkyKey, ConfiguredAspect> depAspectMap) {
+    OrderedSetMultimap<Attribute, ConfiguredTarget> result = OrderedSetMultimap.create();
 
     for (Map.Entry<Attribute, Dependency> entry : depValueNames.entries()) {
       Dependency dep = entry.getValue();
@@ -679,13 +679,13 @@
    * <p>Returns null if the required aspects are not computed yet.
    */
   @Nullable
-  private static ListMultimap<SkyKey, ConfiguredAspect> resolveAspectDependencies(
+  private static OrderedSetMultimap<SkyKey, ConfiguredAspect> resolveAspectDependencies(
       Environment env,
       Map<SkyKey, ConfiguredTarget> configuredTargetMap,
       Iterable<Dependency> deps,
       NestedSetBuilder<Package> transitivePackages)
       throws AspectCreationException {
-    ListMultimap<SkyKey, ConfiguredAspect> result = ArrayListMultimap.create();
+    OrderedSetMultimap<SkyKey, ConfiguredAspect> result = OrderedSetMultimap.create();
     Set<SkyKey> aspectKeys = new HashSet<>();
     for (Dependency dep : deps) {
       for (Entry<AspectDescriptor, BuildConfiguration> depAspect
@@ -785,7 +785,7 @@
     Map<Label, ConfigMatchingProvider> configConditions = new LinkedHashMap<>();
 
     // Collect the labels of the configured targets we need to resolve.
-    ListMultimap<Attribute, Label> configLabelMap = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Label> configLabelMap = OrderedSetMultimap.create();
     RawAttributeMapper attributeMap = RawAttributeMapper.of(((Rule) target));
     for (Attribute a : ((Rule) target).getAttributes()) {
       for (Label configLabel : attributeMap.getConfigurabilityKeys(a.getName(), a.getType())) {
@@ -901,7 +901,7 @@
   @Nullable
   private ConfiguredTargetValue createConfiguredTarget(SkyframeBuildView view,
       Environment env, Target target, BuildConfiguration configuration,
-      ListMultimap<Attribute, ConfiguredTarget> depValueMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Package> transitivePackages)
       throws ConfiguredTargetFunctionException, InterruptedException {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
index 92b2678..e221ae7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
@@ -16,7 +16,6 @@
 import com.google.common.base.Function;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.Dependency;
@@ -33,6 +32,7 @@
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ConflictException;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -97,7 +97,7 @@
       return null;
     }
 
-    ListMultimap<Attribute, Dependency> deps;
+    OrderedSetMultimap<Attribute, Dependency> deps;
     try {
       BuildConfiguration hostConfiguration =
           buildViewProvider.getSkyframeBuildView().getHostConfiguration(ct.getConfiguration());
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index 556d781..546a0e2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -19,7 +19,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
@@ -64,6 +63,7 @@
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.ConfiguredValueCreationException;
 import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ConflictException;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction.SkylarkImportFailedException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.skyframe.CycleInfo;
@@ -474,7 +474,7 @@
   @Nullable
   ConfiguredTarget createConfiguredTarget(Target target, BuildConfiguration configuration,
       CachingAnalysisEnvironment analysisEnvironment,
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
     Preconditions.checkState(enableAnalysis,
         "Already in execution phase %s %s", target, configuration);
diff --git a/src/main/java/com/google/devtools/build/lib/util/OrderedSetMultimap.java b/src/main/java/com/google/devtools/build/lib/util/OrderedSetMultimap.java
new file mode 100644
index 0000000..a64ddf6
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/OrderedSetMultimap.java
@@ -0,0 +1,39 @@
+// Copyright 2016 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.util;
+
+import com.google.common.collect.ForwardingSetMultimap;
+import com.google.common.collect.LinkedHashMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.SetMultimap;
+
+/**
+ * A {@code Multimap} that cannot hold duplicate key-value pairs, returns {@code keySet},
+ * {@code keys}, and {@code asMap} collections that iterate through the keys in the order they were
+ * first added, and maintains the insertion ordering of values for a given key. See the
+ * {@link Multimap} documentation for information common to all multimaps.
+ */
+public final class OrderedSetMultimap<K, V> extends ForwardingSetMultimap<K, V> {
+  private final LinkedHashMultimap<K, V> delegate = LinkedHashMultimap.<K, V>create();
+
+  @Override
+  protected SetMultimap delegate() {
+    return delegate;
+  }
+
+  public static <K, V> OrderedSetMultimap<K, V> create() {
+    return new OrderedSetMultimap<K, V>();
+  }
+}