diff --git a/bazel/aquery.go b/bazel/aquery.go
index 6829698..1d1f49c 100644
--- a/bazel/aquery.go
+++ b/bazel/aquery.go
@@ -115,6 +115,8 @@
 // A helper type for aquery processing which facilitates retrieval of path IDs from their
 // less readable Bazel structures (depset and path fragment).
 type aqueryArtifactHandler struct {
+	// Switches to true if any depset contains only `bazelToolsDependencySentinel`
+	bazelToolsDependencySentinelNeeded bool
 	// Maps depset id to AqueryDepset, a representation of depset which is
 	// post-processed for middleman artifact handling, unhandled artifact
 	// dropping, content hashing, etc.
@@ -143,6 +145,9 @@
 // The file name of py3wrapper.sh, which is used by py_binary targets.
 const py3wrapperFileName = "/py3wrapper.sh"
 
+// A file to be put into depsets that are otherwise empty
+const bazelToolsDependencySentinel = "BAZEL_TOOLS_DEPENDENCY_SENTINEL"
+
 func indexBy[K comparable, V any](values []V, keyFn func(v V) K) map[K]V {
 	m := map[K]V{}
 	for _, v := range values {
@@ -219,7 +224,9 @@
 		if depsetsToUse, isMiddleman := middlemanIdToDepsetIds[artifactId]; isMiddleman {
 			// Swap middleman artifacts with their corresponding depsets and drop the middleman artifacts.
 			transitiveDepsetIds = append(transitiveDepsetIds, depsetsToUse...)
-		} else if strings.HasSuffix(path, py3wrapperFileName) || manifestFilePattern.MatchString(path) {
+		} else if strings.HasSuffix(path, py3wrapperFileName) ||
+			manifestFilePattern.MatchString(path) ||
+			strings.HasPrefix(path, "../bazel_tools") {
 			// Drop these artifacts.
 			// See go/python-binary-host-mixed-build for more details.
 			// 1) For py3wrapper.sh, there is no action for creating py3wrapper.sh in the aquery output of
@@ -231,8 +238,9 @@
 			// since there is no build statement to create them, they should be removed from input paths.
 			// TODO(b/197135294): Clean up this custom runfiles handling logic when
 			// SourceSymlinkManifest and SymlinkTree actions are supported.
+			// 3) ../bazel_tools: they have MODIFY timestamp 10years in the future and would cause the
+			// containing depset to always be considered newer than their outputs.
 		} else {
-			// TODO(b/216194240): Filter out bazel tools.
 			directArtifactPaths = append(directArtifactPaths, path)
 		}
 	}
@@ -249,6 +257,13 @@
 		}
 		childDepsetHashes = append(childDepsetHashes, childAqueryDepset.ContentHash)
 	}
+	if len(directArtifactPaths) == 0 && len(childDepsetHashes) == 0 {
+		// We could omit this depset altogether but that requires cleanup on
+		// transitive dependents.
+		// As a simpler alternative, we use this sentinel file as a dependency.
+		directArtifactPaths = append(directArtifactPaths, bazelToolsDependencySentinel)
+		a.bazelToolsDependencySentinelNeeded = true
+	}
 	aqueryDepset := AqueryDepset{
 		ContentHash:            depsetContentHash(directArtifactPaths, childDepsetHashes),
 		DirectArtifacts:        directArtifactPaths,
@@ -317,6 +332,13 @@
 	}
 
 	var buildStatements []BuildStatement
+	if aqueryHandler.bazelToolsDependencySentinelNeeded {
+		buildStatements = append(buildStatements, BuildStatement{
+			Command:     fmt.Sprintf("touch '%s'", bazelToolsDependencySentinel),
+			OutputPaths: []string{bazelToolsDependencySentinel},
+			Mnemonic:    bazelToolsDependencySentinel,
+		})
+	}
 
 	for _, actionEntry := range aqueryResult.Actions {
 		if shouldSkipAction(actionEntry) {
@@ -445,7 +467,7 @@
 	}
 	command := strings.Join(proptools.ShellEscapeListIncludingSpaces(actionEntry.Arguments), " ")
 	inputPaths, command = removePy3wrapperScript(inputPaths, command)
-	command = addCommandForPyBinaryRunfilesDir(command, inputPaths[0], outputPaths[0])
+	command = addCommandForPyBinaryRunfilesDir(command, outputPaths[0])
 	// Add the python zip file as input of the corresponding python binary stub script in Ninja build statements.
 	// In Ninja build statements, the outputs of dependents of a python binary have python binary stub script as input,
 	// which is not sufficient without the python zip file from which runfiles directory is created for py_binary.
@@ -601,7 +623,7 @@
 // TODO(b/205879240) remove this after py3wrapper.sh could be created in the mixed build mode.
 func removePy3wrapperScript(inputPaths []string, command string) (newInputPaths []string, newCommand string) {
 	// Remove from inputs
-	filteredInputPaths := []string{}
+	var filteredInputPaths []string
 	for _, path := range inputPaths {
 		if !strings.HasSuffix(path, py3wrapperFileName) {
 			filteredInputPaths = append(filteredInputPaths, path)
@@ -622,10 +644,10 @@
 // so MANIFEST file could not be created, which also blocks the creation of runfiles directory.
 // See go/python-binary-host-mixed-build for more details.
 // TODO(b/197135294) create runfiles directory from MANIFEST file once it can be created from SourceSymlinkManifest action.
-func addCommandForPyBinaryRunfilesDir(oldCommand string, zipperCommandPath, zipFilePath string) string {
+func addCommandForPyBinaryRunfilesDir(oldCommand string, zipFilePath string) string {
 	// Unzip the zip file, zipFilePath looks like <python_binary>.zip
 	runfilesDirName := zipFilePath[0:len(zipFilePath)-4] + ".runfiles"
-	command := fmt.Sprintf("%s x %s -d %s", zipperCommandPath, zipFilePath, runfilesDirName)
+	command := fmt.Sprintf("%s x %s -d %s", "../bazel_tools/tools/zip/zipper/zipper", zipFilePath, runfilesDirName)
 	// Create a symbolic link in <python_binary>.runfiles/, which is the expected structure
 	// when running the python binary stub script.
 	command += fmt.Sprintf(" && ln -sf runfiles/__main__ %s", runfilesDirName)
diff --git a/bazel/aquery_test.go b/bazel/aquery_test.go
index 1da6340..9cd8d45 100644
--- a/bazel/aquery_test.go
+++ b/bazel/aquery_test.go
@@ -246,7 +246,6 @@
 	expectedFlattenedInputs := []string{
 		"../sourceroot/bionic/libc/SYSCALLS.TXT",
 		"../sourceroot/bionic/libc/tools/gensyscalls.py",
-		"../bazel_tools/tools/genrule/genrule-setup.sh",
 	}
 	// In this example, each depset should have the same expected inputs.
 	for _, actualDepset := range actualDepsets {
@@ -772,6 +771,92 @@
 	}
 }
 
+func TestBazelOutRemovalFromInputDepsets(t *testing.T) {
+	const inputString = `{
+  "artifacts": [{
+    "id": 1,
+    "pathFragmentId": 10
+  }, {
+    "id": 2,
+    "pathFragmentId": 20
+  }, {
+    "id": 3,
+    "pathFragmentId": 30
+  }, {
+    "id": 4,
+    "pathFragmentId": 40
+  }],
+  "depSetOfFiles": [{
+    "id": 1111,
+    "directArtifactIds": [3 , 4]
+  }],
+  "actions": [{
+    "targetId": 100,
+    "actionKey": "x",
+    "inputDepSetIds": [1111],
+    "mnemonic": "x",
+    "arguments": ["bogus", "command"],
+    "outputIds": [2],
+    "primaryOutputId": 1
+  }],
+  "pathFragments": [{
+    "id": 10,
+    "label": "input"
+  }, {
+    "id": 20,
+    "label": "output"
+  }, {
+    "id": 30,
+    "label": "dep1",
+    "parentId": 50
+  }, {
+    "id": 40,
+    "label": "dep2",
+    "parentId": 60
+  }, {
+    "id": 50,
+    "label": "bazel_tools",
+    "parentId": 60
+  }, {
+    "id": 60,
+    "label": ".."
+  }]
+}`
+	actualBuildStatements, actualDepsets, _ := AqueryBuildStatements([]byte(inputString))
+	if len(actualDepsets) != 1 {
+		t.Errorf("expected 1 depset but found %#v", actualDepsets)
+		return
+	}
+	dep2Found := false
+	for _, dep := range flattenDepsets([]string{actualDepsets[0].ContentHash}, actualDepsets) {
+		if dep == "../bazel_tools/dep1" {
+			t.Errorf("dependency %s expected to be removed but still exists", dep)
+		} else if dep == "../dep2" {
+			dep2Found = true
+		}
+	}
+	if !dep2Found {
+		t.Errorf("dependency ../dep2 expected but not found")
+	}
+
+	expectedBuildStatement := BuildStatement{
+		Command:     "bogus command",
+		OutputPaths: []string{"output"},
+		Mnemonic:    "x",
+	}
+	buildStatementFound := false
+	for _, actualBuildStatement := range actualBuildStatements {
+		if buildStatementEquals(actualBuildStatement, expectedBuildStatement) == "" {
+			buildStatementFound = true
+			break
+		}
+	}
+	if !buildStatementFound {
+		t.Errorf("expected but missing %#v in %#v", expectedBuildStatement, actualBuildStatements)
+		return
+	}
+}
+
 func TestMiddlemenAction(t *testing.T) {
 	const inputString = `
 {
@@ -1332,7 +1417,7 @@
 			Command: "../bazel_tools/tools/zip/zipper/zipper cC python_binary.zip __main__.py=bazel-out/k8-fastbuild/bin/python_binary.temp " +
 				"__init__.py= runfiles/__main__/__init__.py= runfiles/__main__/python_binary.py=python_binary.py  && " +
 				"../bazel_tools/tools/zip/zipper/zipper x python_binary.zip -d python_binary.runfiles && ln -sf runfiles/__main__ python_binary.runfiles",
-			InputPaths:  []string{"../bazel_tools/tools/zip/zipper/zipper", "python_binary.py"},
+			InputPaths:  []string{"python_binary.py"},
 			OutputPaths: []string{"python_binary.zip"},
 			Mnemonic:    "PythonZipper",
 		},
@@ -1464,7 +1549,7 @@
   }]
 }`
 	_, _, err := AqueryBuildStatements([]byte(inputString))
-	assertError(t, err, `Expect 1+ input and 1 output to python zipper action, got: input ["../bazel_tools/tools/zip/zipper/zipper" "python_binary.py"], output []`)
+	assertError(t, err, `Expect 1+ input and 1 output to python zipper action, got: input ["python_binary.py"], output []`)
 }
 
 func assertError(t *testing.T, err error, expected string) {
@@ -1497,7 +1582,7 @@
 		expectedStatement := expected[i]
 		if differingField := buildStatementEquals(actualStatement, expectedStatement); differingField != "" {
 			t.Errorf("%s differs\nunexpected build statement %#v.\nexpected: %#v",
-				differingField, actualStatement, expected)
+				differingField, actualStatement, expectedStatement)
 			return
 		}
 	}