diff --git a/android/bazel_handler.go b/android/bazel_handler.go
index 4a495f0..ac4ced8 100644
--- a/android/bazel_handler.go
+++ b/android/bazel_handler.go
@@ -1135,10 +1135,11 @@
 		// the 'bazel' package, which cannot depend on 'android' package where ctx is defined,
 		// because this would cause circular dependency. So, until we move aquery processing
 		// to the 'android' package, we need to handle special cases here.
-		if buildStatement.Mnemonic == "FileWrite" || buildStatement.Mnemonic == "SourceSymlinkManifest" {
+		switch buildStatement.Mnemonic {
+		case "FileWrite", "SourceSymlinkManifest":
 			out := PathForBazelOut(ctx, buildStatement.OutputPaths[0])
 			WriteFileRuleVerbatim(ctx, out, buildStatement.FileContents)
-		} else if buildStatement.Mnemonic == "SymlinkTree" {
+		case "SymlinkTree":
 			// build-runfiles arguments are the manifest file and the target directory
 			// where it creates the symlink tree according to this manifest (and then
 			// writes the MANIFEST file to it).
@@ -1157,7 +1158,7 @@
 					"outDir": outDir,
 				},
 			})
-		} else {
+		default:
 			panic(fmt.Sprintf("unhandled build statement: %v", buildStatement))
 		}
 	}
diff --git a/bazel/aquery.go b/bazel/aquery.go
index bc823b3..80cf70a 100644
--- a/bazel/aquery.go
+++ b/bazel/aquery.go
@@ -118,12 +118,11 @@
 // 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.
 	depsetIdToAqueryDepset map[depsetId]AqueryDepset
+	emptyDepsetIds         map[depsetId]struct{}
 	// Maps content hash to AqueryDepset.
 	depsetHashToAqueryDepset map[string]AqueryDepset
 
@@ -145,9 +144,6 @@
 // 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 {
@@ -192,6 +188,7 @@
 		depsetIdToAqueryDepset:         map[depsetId]AqueryDepset{},
 		depsetHashToAqueryDepset:       map[string]AqueryDepset{},
 		depsetHashToArtifactPathsCache: map[string][]string{},
+		emptyDepsetIds:                 make(map[depsetId]struct{}, 0),
 		artifactIdToPath:               artifactIdToPath,
 	}
 
@@ -208,16 +205,16 @@
 
 // Ensures that the handler's depsetIdToAqueryDepset map contains an entry for the given
 // depset.
-func (a *aqueryArtifactHandler) populateDepsetMaps(depset depSetOfFiles, middlemanIdToDepsetIds map[artifactId][]depsetId, depsetIdToDepset map[depsetId]depSetOfFiles) (AqueryDepset, error) {
+func (a *aqueryArtifactHandler) populateDepsetMaps(depset depSetOfFiles, middlemanIdToDepsetIds map[artifactId][]depsetId, depsetIdToDepset map[depsetId]depSetOfFiles) (*AqueryDepset, error) {
 	if aqueryDepset, containsDepset := a.depsetIdToAqueryDepset[depset.Id]; containsDepset {
-		return aqueryDepset, nil
+		return &aqueryDepset, nil
 	}
 	transitiveDepsetIds := depset.TransitiveDepSetIds
 	var directArtifactPaths []string
 	for _, artifactId := range depset.DirectArtifactIds {
 		path, pathExists := a.artifactIdToPath[artifactId]
 		if !pathExists {
-			return AqueryDepset{}, fmt.Errorf("undefined input artifactId %d", artifactId)
+			return nil, fmt.Errorf("undefined input artifactId %d", artifactId)
 		}
 		// Filter out any inputs which are universally dropped, and swap middleman
 		// artifacts with their corresponding depsets.
@@ -226,6 +223,7 @@
 			transitiveDepsetIds = append(transitiveDepsetIds, depsetsToUse...)
 		} else if strings.HasSuffix(path, py3wrapperFileName) ||
 			strings.HasPrefix(path, "../bazel_tools") {
+			continue
 			// Drop these artifacts.
 			// See go/python-binary-host-mixed-build for more details.
 			// 1) Drop py3wrapper.sh, just use python binary, the launcher script generated by the
@@ -241,20 +239,23 @@
 	for _, childDepsetId := range transitiveDepsetIds {
 		childDepset, exists := depsetIdToDepset[childDepsetId]
 		if !exists {
-			return AqueryDepset{}, fmt.Errorf("undefined input depsetId %d (referenced by depsetId %d)", childDepsetId, depset.Id)
+			if _, empty := a.emptyDepsetIds[childDepsetId]; empty {
+				continue
+			} else {
+				return nil, fmt.Errorf("undefined input depsetId %d (referenced by depsetId %d)", childDepsetId, depset.Id)
+			}
 		}
-		childAqueryDepset, err := a.populateDepsetMaps(childDepset, middlemanIdToDepsetIds, depsetIdToDepset)
-		if err != nil {
-			return AqueryDepset{}, err
+		if childAqueryDepset, err := a.populateDepsetMaps(childDepset, middlemanIdToDepsetIds, depsetIdToDepset); err != nil {
+			return nil, err
+		} else if childAqueryDepset == nil {
+			continue
+		} else {
+			childDepsetHashes = append(childDepsetHashes, childAqueryDepset.ContentHash)
 		}
-		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
+		a.emptyDepsetIds[depset.Id] = struct{}{}
+		return nil, nil
 	}
 	aqueryDepset := AqueryDepset{
 		ContentHash:            depsetContentHash(directArtifactPaths, childDepsetHashes),
@@ -263,7 +264,7 @@
 	}
 	a.depsetIdToAqueryDepset[depset.Id] = aqueryDepset
 	a.depsetHashToAqueryDepset[aqueryDepset.ContentHash] = aqueryDepset
-	return aqueryDepset, nil
+	return &aqueryDepset, nil
 }
 
 // getInputPaths flattens the depsets of the given IDs and returns all transitive
@@ -392,14 +393,6 @@
 	}
 
 	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) {
 			continue
@@ -484,7 +477,9 @@
 	var hashes []string
 	for _, depsetId := range inputDepsetIds {
 		if aqueryDepset, exists := a.depsetIdToAqueryDepset[depsetId]; !exists {
-			return nil, fmt.Errorf("undefined input depsetId %d", depsetId)
+			if _, empty := a.emptyDepsetIds[depsetId]; !empty {
+				return nil, fmt.Errorf("undefined (not even empty) input depsetId %d", depsetId)
+			}
 		} else {
 			hashes = append(hashes, aqueryDepset.ContentHash)
 		}
diff --git a/bazel/aquery_test.go b/bazel/aquery_test.go
index 2eacafa..4d1503e 100644
--- a/bazel/aquery_test.go
+++ b/bazel/aquery_test.go
@@ -227,7 +227,7 @@
 		return
 	}
 	_, _, err = AqueryBuildStatements(data)
-	assertError(t, err, "undefined input depsetId 2")
+	assertError(t, err, "undefined (not even empty) input depsetId 2")
 }
 
 func TestInvalidInputDepsetIdFromDepset(t *testing.T) {
@@ -584,13 +584,18 @@
    { "id": 60, "label": ".."}
  ]
 }`
+	/* depsets
+	       1111  2222
+	       /  \   |
+	../dep2    ../bazel_tools/dep1
+	*/
 	data, err := JsonToActionGraphContainer(inputString)
 	if err != nil {
 		t.Error(err)
 		return
 	}
 	actualBuildStatements, actualDepsets, _ := AqueryBuildStatements(data)
-	if len(actualDepsets) != 2 {
+	if len(actualDepsets) != 1 {
 		t.Errorf("expected 1 depset but found %#v", actualDepsets)
 		return
 	}
@@ -624,6 +629,82 @@
 	}
 }
 
+func TestBazelOutRemovalFromTransitiveInputDepsets(t *testing.T) {
+	const inputString = `{
+ "artifacts": [
+   { "id": 1, "path_fragment_id": 10 },
+   { "id": 2, "path_fragment_id": 20 },
+   { "id": 3, "path_fragment_id": 30 }],
+ "dep_set_of_files": [{
+   "id": 1111,
+   "transitive_dep_set_ids": [2222]
+ }, {
+   "id": 2222,
+   "direct_artifact_ids": [3]
+ }, {
+   "id": 3333,
+   "direct_artifact_ids": [3]
+ }, {
+   "id": 4444,
+   "transitive_dep_set_ids": [3333]
+ }],
+ "actions": [{
+   "target_id": 100,
+   "action_key": "x",
+   "input_dep_set_ids": [1111, 4444],
+   "mnemonic": "x",
+   "arguments": ["bogus", "command"],
+   "output_ids": [2],
+   "primary_output_id": 1
+ }],
+ "path_fragments": [
+   { "id": 10, "label": "input" },
+   { "id": 20, "label": "output" },
+   { "id": 30, "label": "dep", "parent_id": 50 },
+   { "id": 50, "label": "bazel_tools", "parent_id": 60 },
+   { "id": 60, "label": ".."}
+ ]
+}`
+	/* depsets
+	    1111    4444
+	     ||      ||
+	    2222    3333
+	      |      |
+	../bazel_tools/dep
+	Note: in dep_set_of_files:
+	  1111 appears BEFORE its dependency,2222 while
+	  4444 appears AFTER its dependency 3333
+	and this test shows that that order doesn't affect empty depset pruning
+	*/
+	data, err := JsonToActionGraphContainer(inputString)
+	if err != nil {
+		t.Error(err)
+		return
+	}
+	actualBuildStatements, actualDepsets, _ := AqueryBuildStatements(data)
+	if len(actualDepsets) != 0 {
+		t.Errorf("expected 0 depsets but found %#v", actualDepsets)
+		return
+	}
+
+	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 = `
 {