diff --git a/bp2build/symlink_forest.go b/bp2build/symlink_forest.go
index 966b94a..15a6df0 100644
--- a/bp2build/symlink_forest.go
+++ b/bp2build/symlink_forest.go
@@ -22,7 +22,6 @@
 	"regexp"
 	"sort"
 	"strconv"
-	"strings"
 	"sync"
 	"sync/atomic"
 
@@ -32,19 +31,12 @@
 )
 
 // A tree structure that describes what to do at each directory in the created
-// symlink tree. Currently it is used to enumerate which files/directories
+// symlink tree. Currently, it is used to enumerate which files/directories
 // should be excluded from symlinking. Each instance of "node" represents a file
 // or a directory. If excluded is true, then that file/directory should be
 // excluded from symlinking. Otherwise, the node is not excluded, but one of its
 // descendants is (otherwise the node in question would not exist)
 
-// This is a version int written to a file called symlink_forest_version at the root of the
-// symlink forest. If the version here does not match the version in the file, then we'll
-// clean the whole symlink forest and recreate it. This number can be bumped whenever there's
-// an incompatible change to the forest layout or a bug in incrementality that needs to be fixed
-// on machines that may still have the bug present in their forest.
-const symlinkForestVersion = 2
-
 type instructionsNode struct {
 	name     string
 	excluded bool // If false, this is just an intermediate node
@@ -193,7 +185,7 @@
 	srcPath := shared.JoinPath(topdir, src)
 	dstPath := shared.JoinPath(topdir, dst)
 
-	// Check if a symlink already exists.
+	// Check whether a symlink already exists.
 	if dstInfo, err := os.Lstat(dstPath); err != nil {
 		if !os.IsNotExist(err) {
 			fmt.Fprintf(os.Stderr, "Failed to lstat '%s': %s", dst, err)
@@ -240,44 +232,49 @@
 	return false
 }
 
-// maybeCleanSymlinkForest will remove the whole symlink forest directory if the version recorded
-// in the symlink_forest_version file is not equal to symlinkForestVersion.
-func maybeCleanSymlinkForest(topdir, forest string, verbose bool) error {
-	versionFilePath := shared.JoinPath(topdir, forest, "symlink_forest_version")
-	versionFileContents, err := os.ReadFile(versionFilePath)
-	if err != nil && !os.IsNotExist(err) {
-		return err
+// Returns the mtime of the soong_build binary to determine whether we should
+// force symlink_forest to re-execute
+func getSoongBuildMTime() (int64, error) {
+	binaryPath, err := os.Executable()
+	if err != nil {
+		return 0, err
 	}
-	versionFileString := strings.TrimSpace(string(versionFileContents))
-	symlinkForestVersionString := strconv.Itoa(symlinkForestVersion)
-	if err != nil || versionFileString != symlinkForestVersionString {
-		if verbose {
-			fmt.Fprintf(os.Stderr, "Old symlink_forest_version was %q, current is %q. Cleaning symlink forest before recreating...\n", versionFileString, symlinkForestVersionString)
-		}
-		err = os.RemoveAll(shared.JoinPath(topdir, forest))
-		if err != nil {
-			return err
-		}
+
+	info, err := os.Stat(binaryPath)
+	if err != nil {
+		return 0, err
 	}
-	return nil
+
+	return info.ModTime().UnixMilli(), nil
 }
 
-// maybeWriteVersionFile will write the symlink_forest_version file containing symlinkForestVersion
-// if it doesn't exist already. If it exists we know it must contain symlinkForestVersion because
-// we checked for that already in maybeCleanSymlinkForest
-func maybeWriteVersionFile(topdir, forest string) error {
-	versionFilePath := shared.JoinPath(topdir, forest, "symlink_forest_version")
-	_, err := os.Stat(versionFilePath)
+// cleanSymlinkForest will remove the whole symlink forest directory
+func cleanSymlinkForest(topdir, forest string) error {
+	return os.RemoveAll(shared.JoinPath(topdir, forest))
+}
+
+// This returns whether symlink forest should clean and replant symlinks.
+// It compares the mtime of this executable with the mtime of the last-run
+// soong_build binary. If they differ, then we should clean and replant.
+func shouldCleanSymlinkForest(topdir string, forest string, soongBuildMTime int64) (bool, error) {
+	mtimeFilePath := shared.JoinPath(topdir, forest, "soong_build_mtime")
+	mtimeFileContents, err := os.ReadFile(mtimeFilePath)
 	if err != nil {
-		if !os.IsNotExist(err) {
-			return err
-		}
-		err = os.WriteFile(versionFilePath, []byte(strconv.Itoa(symlinkForestVersion)+"\n"), 0666)
-		if err != nil {
-			return err
+		if os.IsNotExist(err) {
+			// This is likely the first time this has run with this functionality - clean away!
+			return true, nil
+		} else {
+			return false, err
 		}
 	}
-	return nil
+	return strconv.FormatInt(soongBuildMTime, 10) != string(mtimeFileContents), nil
+}
+
+func writeSoongBuildMTimeFile(topdir, forest string, mtime int64) error {
+	mtimeFilePath := shared.JoinPath(topdir, forest, "soong_build_mtime")
+	contents := []byte(strconv.FormatInt(mtime, 10))
+
+	return os.WriteFile(mtimeFilePath, contents, 0666)
 }
 
 // Recursively plants a symlink forest at forestDir. The symlink tree will
@@ -473,12 +470,26 @@
 		symlinkCount: atomic.Uint64{},
 	}
 
-	err := maybeCleanSymlinkForest(topdir, forest, verbose)
+	// Check whether soong_build has been modified since the last run
+	soongBuildMTime, err := getSoongBuildMTime()
 	if err != nil {
 		fmt.Fprintln(os.Stderr, err)
 		os.Exit(1)
 	}
 
+	shouldClean, err := shouldCleanSymlinkForest(topdir, forest, soongBuildMTime)
+
+	if err != nil {
+		fmt.Fprintln(os.Stderr, err)
+		os.Exit(1)
+	} else if shouldClean {
+		err = cleanSymlinkForest(topdir, forest)
+		if err != nil {
+			fmt.Fprintln(os.Stderr, err)
+			os.Exit(1)
+		}
+	}
+
 	instructions := instructionsFromExcludePathList(exclude)
 	go func() {
 		context.wg.Add(1)
@@ -491,11 +502,10 @@
 		deps = append(deps, dep)
 	}
 
-	err = maybeWriteVersionFile(topdir, forest)
+	err = writeSoongBuildMTimeFile(topdir, forest, soongBuildMTime)
 	if err != nil {
 		fmt.Fprintln(os.Stderr, err)
 		os.Exit(1)
 	}
-
 	return deps, context.mkdirCount.Load(), context.symlinkCount.Load()
 }
diff --git a/tests/run_integration_tests.sh b/tests/run_integration_tests.sh
index 223baa4..8045591 100755
--- a/tests/run_integration_tests.sh
+++ b/tests/run_integration_tests.sh
@@ -10,6 +10,7 @@
 "$TOP/build/soong/tests/persistent_bazel_test.sh"
 "$TOP/build/soong/tests/soong_test.sh"
 "$TOP/build/soong/tests/stale_metrics_files_test.sh"
+"$TOP/build/soong/tests/symlink_forest_rerun_test.sh"
 "$TOP/prebuilts/build-tools/linux-x86/bin/py3-cmd" "$TOP/build/bazel/ci/rbc_dashboard.py" aosp_arm64-userdebug
 
 # The following tests build against the full source tree and don't rely on the
diff --git a/tests/symlink_forest_rerun_test.sh b/tests/symlink_forest_rerun_test.sh
new file mode 100755
index 0000000..74e779e
--- /dev/null
+++ b/tests/symlink_forest_rerun_test.sh
@@ -0,0 +1,43 @@
+#!/bin/bash -eu
+
+set -o pipefail
+
+# Tests that symlink forest will replant if soong_build has changed
+# Any change to the build system should trigger a rerun
+
+source "$(dirname "$0")/lib.sh"
+
+function test_symlink_forest_reruns {
+  setup
+
+  mkdir -p a
+  touch a/g.txt
+  cat > a/Android.bp <<'EOF'
+filegroup {
+    name: "g",
+    srcs: ["g.txt"],
+  }
+EOF
+
+  run_soong g
+
+  mtime=`cat out/soong/workspace/soong_build_mtime`
+  # rerun with no changes - ensure that it hasn't changed
+  run_soong g
+  newmtime=`cat out/soong/workspace/soong_build_mtime`
+  if [[ ! "$mtime" == "$mtime" ]]; then
+     fail "symlink forest reran when it shouldn't have"
+  fi
+
+  # change exit codes to force a soong_build rebuild.
+  sed -i 's/os.Exit(1)/os.Exit(2)/g' build/soong/bp2build/symlink_forest.go
+
+  run_soong g
+  newmtime=`cat out/soong/workspace/soong_build_mtime`
+  if [[ "$mtime" == "$newmtime" ]]; then
+     fail "symlink forest did not rerun when it should have"
+  fi
+
+}
+
+scan_and_run_tests