diff --git a/.github/ci/classify-changes.py b/.github/ci/classify-changes.py
index 70b19d65..25c2a4c6 100644
--- a/.github/ci/classify-changes.py
+++ b/.github/ci/classify-changes.py
@@ -80,16 +80,28 @@ def classify_push(git, before, sha, forced):
         return True, "before-zero", []
     if forced:
         return True, "forced-push", []
-    reached = False
+    # Deepen until the GRAPH from sha connects to before, not until the before
+    # OBJECT exists. A self-hosted runner reuses its workspace, so a stale
+    # before object from an earlier run can be present while the current
+    # depth-2 history is grafted short of it (measured on kitsubito, main run
+    # 35998753683: c185326b present, 0854bbe8 grafted with no parents,
+    # is-ancestor exit 1 on a true ancestor).
+    present = connected = False
     for step in (0, *DEEPEN_STEPS):
         if step:
             git.run("fetch", "--no-tags", f"--deepen={step}", "origin", sha)
-        if git.run("cat-file", "-e", f"{before}^{{commit}}")[0] == 0:
-            reached = True
+        present = git.run("cat-file", "-e", f"{before}^{{commit}}")[0] == 0
+        connected = present and git.run("merge-base", "--is-ancestor", before, sha)[0] == 0
+        if connected:
             break
-    if not reached:
-        return True, "before-unreachable", []
-    if git.run("merge-base", "--is-ancestor", before, sha)[0] != 0:
+    if not connected:
+        if not present:
+            return True, "before-unreachable", []
+        # is-ancestor answers "no" both for a real non-ancestor and for a graph
+        # still too shallow to decide. Only a complete graph makes "no" a fact.
+        rc, out = git.run("rev-parse", "--is-shallow-repository")
+        if rc != 0 or out.strip() != "false":
+            return True, "before-undecidable", []
         return True, "before-not-ancestor", []
     files = changed_files(git, before, sha)
     if files is None:

[exited with code 0]