diff --git a/commit-reach.c b/commit-reach.c
index c226ee3da4..7f4f3f7424 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -47,11 +47,15 @@ static int queue_has_nonstale(struct prio_queue *queue)
 	return 0;
 }
 
-/* all input commits in one and twos[] must have been parsed! */
+/*
+ * All input commits in twos[] must have been parsed. If
+ * one_is_at_min_generation is false, one must also have be parsed.
+ */
 static struct commit_list *paint_down_to_common(struct repository *r,
 						struct commit *one, int n,
 						struct commit **twos,
-						timestamp_t min_generation)
+						timestamp_t min_generation,
+						int one_is_at_min_generation)
 {
 	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 	struct commit_list *result = NULL;
@@ -66,7 +70,8 @@ static struct commit_list *paint_down_to_common(struct repository *r,
 		commit_list_append(one, &result);
 		return result;
 	}
-	prio_queue_put(&queue, one);
+	if (!one_is_at_min_generation)
+		prio_queue_put(&queue, one);
 
 	for (i = 0; i < n; i++) {
 		twos[i]->object.flags |= PARENT2;
@@ -97,6 +102,10 @@ static struct commit_list *paint_down_to_common(struct repository *r,
 			/* Mark parents of a found merge stale */
 			flags |= STALE;
 		}
+
+		if (commit == one && one_is_at_min_generation)
+			continue;
+
 		parents = commit->parents;
 		while (parents) {
 			struct commit *p = parents->item;
@@ -138,7 +147,7 @@ static struct commit_list *merge_bases_many(struct repository *r,
 			return NULL;
 	}
 
-	list = paint_down_to_common(r, one, n, twos, 0);
+	list = paint_down_to_common(r, one, n, twos, 0, 0);
 
 	while (list) {
 		struct commit *commit = pop_commit(&list);
@@ -187,8 +196,6 @@ static int remove_redundant_no_gen(struct repository *r,
 	redundant = xcalloc(cnt, 1);
 	ALLOC_ARRAY(filled_index, cnt - 1);
 
-	for (i = 0; i < cnt; i++)
-		repo_parse_commit(r, array[i]);
 	for (i = 0; i < cnt; i++) {
 		struct commit_list *common;
 		timestamp_t min_generation = commit_graph_generation(array[i]);
@@ -207,7 +214,7 @@ static int remove_redundant_no_gen(struct repository *r,
 				min_generation = curr_generation;
 		}
 		common = paint_down_to_common(r, array[i], filled,
-					      work, min_generation);
+					      work, min_generation, 1);
 		if (array[i]->object.flags & PARENT2)
 			redundant[i] = 1;
 		for (j = 0; j < filled; j++)
@@ -478,8 +485,6 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
 	int ret = 0, i;
 	timestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;
 
-	if (repo_parse_commit(r, commit))
-		return ret;
 	for (i = 0; i < nr_reference; i++) {
 		if (repo_parse_commit(r, reference[i]))
 			return ret;
@@ -495,7 +500,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
 
 	bases = paint_down_to_common(r, commit,
 				     nr_reference, reference,
-				     generation);
+				     generation, 1);
 	if (commit->object.flags & PARENT2)
 		ret = 1;
 	clear_commit_marks(commit, all_flags);
diff --git a/t/t5537-fetch-shallow.sh b/t/t5537-fetch-shallow.sh
index 92948de7a0..f736ccf9f5 100755
--- a/t/t5537-fetch-shallow.sh
+++ b/t/t5537-fetch-shallow.sh
@@ -136,6 +136,8 @@ test_expect_success 'fetch that requires changes in .git/shallow is filtered' '
 '
 
 test_expect_success 'fetch --update-shallow' '
+	git init a-submodule &&
+	test_commit -C a-submodule foo &&
 	(
 	cd shallow &&
 	git checkout main &&
@@ -145,10 +147,13 @@ test_expect_success 'fetch --update-shallow' '
 	) &&
 	(
 	cd notshallow &&
+	git submodule add ../a-submodule a-submodule &&
+	git commit -m "added submodule" &&
 	git fetch --update-shallow ../shallow/.git refs/heads/*:refs/remotes/shallow/* &&
 	git fsck &&
 	git for-each-ref --sort=refname --format="%(refname)" >actual.refs &&
 	cat <<-\EOF >expect.refs &&
+	refs/heads/main
 	refs/remotes/shallow/main
 	refs/remotes/shallow/no-shallow
 	refs/tags/heavy-tag
@@ -162,8 +167,6 @@ test_expect_success 'fetch --update-shallow' '
 '
 
 test_expect_success 'fetch --update-shallow into a repo with submodules' '
-	git init a-submodule &&
-	test_commit -C a-submodule foo &&
 	git init repo-with-sub &&
 	git -C repo-with-sub submodule add ../a-submodule a-submodule &&
 	git -C repo-with-sub commit -m "added submodule" &&
@@ -185,6 +188,7 @@ test_expect_success 'fetch --update-shallow (with fetch.writeCommitGraph)' '
 	git fsck &&
 	git for-each-ref --sort=refname --format="%(refname)" >actual.refs &&
 	cat <<-EOF >expect.refs &&
+	refs/heads/main
 	refs/remotes/shallow/main
 	refs/remotes/shallow/no-shallow
 	refs/tags/heavy-tag
