diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
index 987ed28..06513ac 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
@@ -111,8 +111,8 @@
   private static final Interner<ImmutableSortedMap<Class<? extends Fragment>, Fragment>>
       fragmentsInterner = BlazeInterners.newWeakInterner();
 
-  private static final Interner<ImmutableMap<String, String>>
-      executionInfoInterner = BlazeInterners.newWeakInterner();
+  private static final Interner<ImmutableSortedMap<String, String>> executionInfoInterner =
+      BlazeInterners.newWeakInterner();
 
   /** Compute the default shell environment for actions from the command line options. */
   public interface ActionEnvironmentProvider {
@@ -1823,9 +1823,9 @@
     if (!options.executionInfoModifier.matches(mnemonic)) {
       return executionInfo;
     }
-    LinkedHashMap<String, String> mutableCopy = new LinkedHashMap<>(executionInfo);
+    Map<String, String> mutableCopy = new HashMap<>(executionInfo);
     modifyExecutionInfo(mutableCopy, mnemonic);
-    return executionInfoInterner.intern(ImmutableMap.copyOf(mutableCopy));
+    return executionInfoInterner.intern(ImmutableSortedMap.copyOf(mutableCopy));
   }
 
   /** Applies {@code executionInfoModifiers} to the given {@code executionInfo}. */
diff --git a/src/test/shell/integration/modify_execution_info_test.sh b/src/test/shell/integration/modify_execution_info_test.sh
index 20eb058..db91d47 100755
--- a/src/test/shell/integration/modify_execution_info_test.sh
+++ b/src/test/shell/integration/modify_execution_info_test.sh
@@ -248,4 +248,54 @@
   fi
 }
 
+# Regression test for b/127874955. We use --output=textproto since --output=text
+# sorts the execution info.
+function test_modify_execution_info_deterministic_order() {
+  local pkg="${FUNCNAME[0]}"
+  mkdir -p "$pkg/x" "$pkg/y" || fail "mkdir failed"
+  touch "$pkg/BUILD"
+  cat > "$pkg/build_defs.bzl" <<'EOF' || fail "Couldn't cat"
+def _rule_x_impl(ctx):
+    output = ctx.outputs.out
+    ctx.actions.run_shell(
+        outputs = [output],
+        command = "touch %s" % output.path,
+        mnemonic = "RuleX",
+        execution_requirements = {"requires-x": ""},
+    )
+
+rule_x = rule(outputs = {"out": "%{name}.out"}, implementation = _rule_x_impl)
+
+def _rule_y_impl(ctx):
+    output = ctx.outputs.out
+    ctx.actions.run_shell(
+        outputs = [output],
+        command = "touch %s" % output.path,
+        mnemonic = "RuleY",
+        execution_requirements = {"requires-y": ""},
+    )
+
+rule_y = rule(outputs = {"out": "%{name}.out"}, implementation = _rule_y_impl)
+EOF
+  echo "load('//$pkg:build_defs.bzl', 'rule_x')" > "$pkg/x/BUILD"
+  echo 'rule_x(name = "x")' >> "$pkg/x/BUILD"
+  echo "load('//$pkg:build_defs.bzl', 'rule_y')" > "$pkg/y/BUILD"
+  echo 'rule_y(name = "y")' >> "$pkg/y/BUILD"
+
+  mod='Rule(X|Y)=+requires-x,Rule(X|Y)=+requires-y'
+
+  bazel aquery "//$pkg/x" --output=textproto --modify_execution_info="$mod" \
+    > output1 2> "$TEST_log" || fail "Expected success"
+
+  bazel shutdown >& "$TEST_log" || fail "Couldn't shutdown"
+
+  bazel aquery "//$pkg/y" --modify_execution_info="$mod" \
+    >& "$TEST_log" || fail "Expected success"
+
+  bazel aquery "//$pkg/x" --output=textproto --modify_execution_info="$mod" \
+    > output2 2> "$TEST_log" || fail "Expected success"
+
+  assert_equals "$(cat output1)" "$(cat output2)"
+}
+
 run_suite "Integration tests of the --modify_execution_info option."