diff --git a/bp2build/symlink_forest.go b/bp2build/symlink_forest.go
index e3878b1..5c33308 100644
--- a/bp2build/symlink_forest.go
+++ b/bp2build/symlink_forest.go
@@ -21,6 +21,8 @@
 	"path/filepath"
 	"regexp"
 	"sort"
+	"strconv"
+	"strings"
 	"sync"
 	"sync/atomic"
 
@@ -36,6 +38,13 @@
 // 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 = 1
+
 type instructionsNode struct {
 	name     string
 	excluded bool // If false, this is just an intermediate node
@@ -231,6 +240,46 @@
 	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
+	}
+	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
+		}
+	}
+	return 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)
+	if err != nil {
+		if !os.IsNotExist(err) {
+			return err
+		}
+		err = os.WriteFile(versionFilePath, []byte(strconv.Itoa(symlinkForestVersion)+"\n"), 0666)
+		if err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
 // Recursively plants a symlink forest at forestDir. The symlink tree will
 // contain every file in buildFilesDir and srcDir excluding the files in
 // instructions. Collects every directory encountered during the traversal of
@@ -424,6 +473,12 @@
 		symlinkCount: atomic.Uint64{},
 	}
 
+	err := maybeCleanSymlinkForest(topdir, forest, verbose)
+	if err != nil {
+		fmt.Fprintln(os.Stderr, err)
+		os.Exit(1)
+	}
+
 	instructions := instructionsFromExcludePathList(exclude)
 	go func() {
 		context.wg.Add(1)
@@ -436,5 +491,11 @@
 		deps = append(deps, dep)
 	}
 
+	err = maybeWriteVersionFile(topdir, forest)
+	if err != nil {
+		fmt.Fprintln(os.Stderr, err)
+		os.Exit(1)
+	}
+
 	return deps, context.mkdirCount.Load(), context.symlinkCount.Load()
 }