diff --git a/android/mutator.go b/android/mutator.go
index 738b2ba..5acd992 100644
--- a/android/mutator.go
+++ b/android/mutator.go
@@ -210,10 +210,14 @@
 type BottomUpMutatorContext interface {
 	BaseMutatorContext
 
-	// AddDependency adds a dependency to the given module.
-	// Does not affect the ordering of the current mutator pass, but will be ordered
-	// correctly for all future mutator passes.
-	AddDependency(module blueprint.Module, tag blueprint.DependencyTag, name ...string)
+	// AddDependency adds a dependency to the given module.  It returns a slice of modules for each
+	// dependency (some entries may be nil).
+	//
+	// If the mutator is parallel (see MutatorHandle.Parallel), this method will pause until the
+	// new dependencies have had the current mutator called on them.  If the mutator is not
+	// parallel this method does not affect the ordering of the current mutator pass, but will
+	// be ordered correctly for all future mutator passes.
+	AddDependency(module blueprint.Module, tag blueprint.DependencyTag, name ...string) []blueprint.Module
 
 	// AddReverseDependency adds a dependency from the destination to the given module.
 	// Does not affect the ordering of the current mutator pass, but will be ordered
@@ -253,19 +257,30 @@
 	SetDefaultDependencyVariation(*string)
 
 	// AddVariationDependencies adds deps as dependencies of the current module, but uses the variations
-	// argument to select which variant of the dependency to use.  A variant of the dependency must
-	// exist that matches the all of the non-local variations of the current module, plus the variations
-	// argument.
-	AddVariationDependencies([]blueprint.Variation, blueprint.DependencyTag, ...string)
+	// argument to select which variant of the dependency to use.  It returns a slice of modules for
+	// each dependency (some entries may be nil).  A variant of the dependency must exist that matches
+	// the all of the non-local variations of the current module, plus the variations argument.
+	//
+	// If the mutator is parallel (see MutatorHandle.Parallel), this method will pause until the
+	// new dependencies have had the current mutator called on them.  If the mutator is not
+	// parallel this method does not affect the ordering of the current mutator pass, but will
+	// be ordered correctly for all future mutator passes.
+	AddVariationDependencies([]blueprint.Variation, blueprint.DependencyTag, ...string) []blueprint.Module
 
 	// AddFarVariationDependencies adds deps as dependencies of the current module, but uses the
-	// variations argument to select which variant of the dependency to use.  A variant of the
-	// dependency must exist that matches the variations argument, but may also have other variations.
+	// variations argument to select which variant of the dependency to use.  It returns a slice of
+	// modules for each dependency (some entries may be nil).  A variant of the dependency must
+	// exist that matches the variations argument, but may also have other variations.
 	// For any unspecified variation the first variant will be used.
 	//
 	// Unlike AddVariationDependencies, the variations of the current module are ignored - the
 	// dependency only needs to match the supplied variations.
-	AddFarVariationDependencies([]blueprint.Variation, blueprint.DependencyTag, ...string)
+	//
+	// If the mutator is parallel (see MutatorHandle.Parallel), this method will pause until the
+	// new dependencies have had the current mutator called on them.  If the mutator is not
+	// parallel this method does not affect the ordering of the current mutator pass, but will
+	// be ordered correctly for all future mutator passes.
+	AddFarVariationDependencies([]blueprint.Variation, blueprint.DependencyTag, ...string) []blueprint.Module
 
 	// AddInterVariantDependency adds a dependency between two variants of the same module.  Variants are always
 	// ordered in the same orderas they were listed in CreateVariations, and AddInterVariantDependency does not change
@@ -452,8 +467,8 @@
 	b.Module().base().commonProperties.DebugName = name
 }
 
-func (b *bottomUpMutatorContext) AddDependency(module blueprint.Module, tag blueprint.DependencyTag, name ...string) {
-	b.bp.AddDependency(module, tag, name...)
+func (b *bottomUpMutatorContext) AddDependency(module blueprint.Module, tag blueprint.DependencyTag, name ...string) []blueprint.Module {
+	return b.bp.AddDependency(module, tag, name...)
 }
 
 func (b *bottomUpMutatorContext) AddReverseDependency(module blueprint.Module, tag blueprint.DependencyTag, name string) {
@@ -505,15 +520,15 @@
 }
 
 func (b *bottomUpMutatorContext) AddVariationDependencies(variations []blueprint.Variation, tag blueprint.DependencyTag,
-	names ...string) {
+	names ...string) []blueprint.Module {
 
-	b.bp.AddVariationDependencies(variations, tag, names...)
+	return b.bp.AddVariationDependencies(variations, tag, names...)
 }
 
 func (b *bottomUpMutatorContext) AddFarVariationDependencies(variations []blueprint.Variation,
-	tag blueprint.DependencyTag, names ...string) {
+	tag blueprint.DependencyTag, names ...string) []blueprint.Module {
 
-	b.bp.AddFarVariationDependencies(variations, tag, names...)
+	return b.bp.AddFarVariationDependencies(variations, tag, names...)
 }
 
 func (b *bottomUpMutatorContext) AddInterVariantDependency(tag blueprint.DependencyTag, from, to blueprint.Module) {
diff --git a/cc/binary_sdk_member.go b/cc/binary_sdk_member.go
index a1abc72..55e400e 100644
--- a/cc/binary_sdk_member.go
+++ b/cc/binary_sdk_member.go
@@ -44,7 +44,7 @@
 		for _, target := range targets {
 			name, version := StubsLibNameAndVersion(lib)
 			if version == "" {
-				version = LatestStubsVersionFor(mctx.Config(), name)
+				version = "latest"
 			}
 			variations := target.Variations()
 			if mctx.Device() {
diff --git a/cc/cc.go b/cc/cc.go
index b5a0261..6584380 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -47,7 +47,8 @@
 		ctx.BottomUp("link", LinkageMutator).Parallel()
 		ctx.BottomUp("ndk_api", NdkApiMutator).Parallel()
 		ctx.BottomUp("test_per_src", TestPerSrcMutator).Parallel()
-		ctx.BottomUp("version", VersionMutator).Parallel()
+		ctx.BottomUp("version_selector", versionSelectorMutator).Parallel()
+		ctx.BottomUp("version", versionMutator).Parallel()
 		ctx.BottomUp("begin", BeginMutator).Parallel()
 		ctx.BottomUp("sysprop_cc", SyspropMutator).Parallel()
 		ctx.BottomUp("vendor_snapshot", VendorSnapshotMutator).Parallel()
@@ -784,7 +785,28 @@
 	panic(fmt.Errorf("BuildStubs called on non-library module: %q", c.BaseModuleName()))
 }
 
-func (c *Module) SetStubsVersions(version string) {
+func (c *Module) SetAllStubsVersions(versions []string) {
+	if library, ok := c.linker.(*libraryDecorator); ok {
+		library.MutatedProperties.AllStubsVersions = versions
+		return
+	}
+	if llndk, ok := c.linker.(*llndkStubDecorator); ok {
+		llndk.libraryDecorator.MutatedProperties.AllStubsVersions = versions
+		return
+	}
+}
+
+func (c *Module) AllStubsVersions() []string {
+	if library, ok := c.linker.(*libraryDecorator); ok {
+		return library.MutatedProperties.AllStubsVersions
+	}
+	if llndk, ok := c.linker.(*llndkStubDecorator); ok {
+		return llndk.libraryDecorator.MutatedProperties.AllStubsVersions
+	}
+	return nil
+}
+
+func (c *Module) SetStubsVersion(version string) {
 	if c.linker != nil {
 		if library, ok := c.linker.(*libraryDecorator); ok {
 			library.MutatedProperties.StubsVersion = version
@@ -795,7 +817,7 @@
 			return
 		}
 	}
-	panic(fmt.Errorf("SetStubsVersions called on non-library module: %q", c.BaseModuleName()))
+	panic(fmt.Errorf("SetStubsVersion called on non-library module: %q", c.BaseModuleName()))
 }
 
 func (c *Module) StubsVersion() string {
@@ -1996,18 +2018,20 @@
 			variations = append(variations, blueprint.Variation{Mutator: "version", Variation: version})
 			depTag.explicitlyVersioned = true
 		}
-		actx.AddVariationDependencies(variations, depTag, name)
+		deps := actx.AddVariationDependencies(variations, depTag, name)
 
 		// If the version is not specified, add dependency to all stubs libraries.
 		// The stubs library will be used when the depending module is built for APEX and
 		// the dependent module is not in the same APEX.
 		if version == "" && VersionVariantAvailable(c) {
-			for _, ver := range stubsVersionsFor(actx.Config())[name] {
-				// Note that depTag.ExplicitlyVersioned is false in this case.
-				actx.AddVariationDependencies([]blueprint.Variation{
-					{Mutator: "link", Variation: "shared"},
-					{Mutator: "version", Variation: ver},
-				}, depTag, name)
+			if dep, ok := deps[0].(*Module); ok {
+				for _, ver := range dep.AllStubsVersions() {
+					// Note that depTag.ExplicitlyVersioned is false in this case.
+					ctx.AddVariationDependencies([]blueprint.Variation{
+						{Mutator: "link", Variation: "shared"},
+						{Mutator: "version", Variation: ver},
+					}, depTag, name)
+				}
 			}
 		}
 	}
@@ -2459,7 +2483,7 @@
 				if m, ok := ccDep.(*Module); ok && m.IsStubs() { // LLNDK
 					// by default, use current version of LLNDK
 					versionToUse := ""
-					versions := stubsVersionsFor(ctx.Config())[depName]
+					versions := m.AllStubsVersions()
 					if c.ApexVariationName() != "" && len(versions) > 0 {
 						// if this is for use_vendor apex && dep has stubsVersions
 						// apply the same rule of apex sdk enforcement to choose right version
diff --git a/cc/cc_test.go b/cc/cc_test.go
index a4c0677..132d091 100644
--- a/cc/cc_test.go
+++ b/cc/cc_test.go
@@ -3025,6 +3025,7 @@
 }
 
 func checkEquals(t *testing.T, message string, expected, actual interface{}) {
+	t.Helper()
 	if !reflect.DeepEqual(actual, expected) {
 		t.Errorf(message+
 			"\nactual:   %v"+
diff --git a/cc/library.go b/cc/library.go
index 92853b5..7b09b11 100644
--- a/cc/library.go
+++ b/cc/library.go
@@ -152,6 +152,8 @@
 	BuildStubs bool `blueprint:"mutated"`
 	// Version of the stubs lib
 	StubsVersion string `blueprint:"mutated"`
+	// List of all stubs versions associated with an implementation lib
+	AllStubsVersions []string `blueprint:"mutated"`
 }
 
 type FlagExporterProperties struct {
@@ -1517,26 +1519,6 @@
 	}
 }
 
-var stubVersionsKey = android.NewOnceKey("stubVersions")
-
-// maps a module name to the list of stubs versions available for the module
-func stubsVersionsFor(config android.Config) map[string][]string {
-	return config.Once(stubVersionsKey, func() interface{} {
-		return make(map[string][]string)
-	}).(map[string][]string)
-}
-
-var stubsVersionsLock sync.Mutex
-
-func LatestStubsVersionFor(config android.Config, name string) string {
-	versions, ok := stubsVersionsFor(config)[name]
-	if ok && len(versions) > 0 {
-		// the versions are alreay sorted in ascending order
-		return versions[len(versions)-1]
-	}
-	return ""
-}
-
 func normalizeVersions(ctx android.BaseModuleContext, versions []string) {
 	numVersions := make([]int, len(versions))
 	for i, v := range versions {
@@ -1556,17 +1538,22 @@
 }
 
 func createVersionVariations(mctx android.BottomUpMutatorContext, versions []string) {
-	// "" is for the non-stubs variant
-	versions = append([]string{""}, versions...)
+	// "" is for the non-stubs (implementation) variant.
+	variants := append([]string{""}, versions...)
 
-	modules := mctx.CreateLocalVariations(versions...)
+	modules := mctx.CreateLocalVariations(variants...)
 	for i, m := range modules {
-		if versions[i] != "" {
+		if variants[i] != "" {
 			m.(LinkableInterface).SetBuildStubs()
-			m.(LinkableInterface).SetStubsVersions(versions[i])
+			m.(LinkableInterface).SetStubsVersion(variants[i])
 		}
 	}
 	mctx.AliasVariation("")
+	latestVersion := ""
+	if len(versions) > 0 {
+		latestVersion = versions[len(versions)-1]
+	}
+	mctx.CreateAliasVariation("latest", latestVersion)
 }
 
 func VersionVariantAvailable(module interface {
@@ -1577,44 +1564,41 @@
 	return !module.Host() && !module.InRamdisk() && !module.InRecovery()
 }
 
-// VersionMutator splits a module into the mandatory non-stubs variant
-// (which is unnamed) and zero or more stubs variants.
-func VersionMutator(mctx android.BottomUpMutatorContext) {
+// versionSelector normalizes the versions in the Stubs.Versions property into MutatedProperties.AllStubsVersions,
+// and propagates the value from implementation libraries to llndk libraries with the same name.
+func versionSelectorMutator(mctx android.BottomUpMutatorContext) {
 	if library, ok := mctx.Module().(LinkableInterface); ok && VersionVariantAvailable(library) {
 		if library.CcLibrary() && library.BuildSharedVariant() && len(library.StubsVersions()) > 0 &&
 			!library.IsSdkVariant() {
+
 			versions := library.StubsVersions()
 			normalizeVersions(mctx, versions)
 			if mctx.Failed() {
 				return
 			}
-
-			stubsVersionsLock.Lock()
-			defer stubsVersionsLock.Unlock()
-			// save the list of versions for later use
-			stubsVersionsFor(mctx.Config())[mctx.ModuleName()] = versions
-
-			createVersionVariations(mctx, versions)
+			// Set the versions on the pre-mutated module so they can be read by any llndk modules that
+			// depend on the implementation library and haven't been mutated yet.
+			library.SetAllStubsVersions(versions)
 			return
 		}
 
 		if c, ok := library.(*Module); ok && c.IsStubs() {
-			stubsVersionsLock.Lock()
-			defer stubsVersionsLock.Unlock()
-			// For LLNDK llndk_library, we borrow stubs.versions from its implementation library.
-			// Since llndk_library has dependency to its implementation library,
-			// we can safely access stubsVersionsFor() with its baseModuleName.
-			versions := stubsVersionsFor(mctx.Config())[c.BaseModuleName()]
-			// save the list of versions for later use
-			stubsVersionsFor(mctx.Config())[mctx.ModuleName()] = versions
-
-			createVersionVariations(mctx, versions)
-			return
+			// Get the versions from the implementation module.
+			impls := mctx.GetDirectDepsWithTag(llndkImplDep)
+			if len(impls) > 1 {
+				panic(fmt.Errorf("Expected single implmenetation library, got %d", len(impls)))
+			} else if len(impls) == 1 {
+				c.SetAllStubsVersions(impls[0].(*Module).AllStubsVersions())
+			}
 		}
+	}
+}
 
-		mctx.CreateLocalVariations("")
-		mctx.AliasVariation("")
-		return
+// versionMutator splits a module into the mandatory non-stubs variant
+// (which is unnamed) and zero or more stubs variants.
+func versionMutator(mctx android.BottomUpMutatorContext) {
+	if library, ok := mctx.Module().(LinkableInterface); ok && VersionVariantAvailable(library) {
+		createVersionVariations(mctx, library.AllStubsVersions())
 	}
 }
 
diff --git a/cc/library_sdk_member.go b/cc/library_sdk_member.go
index ecfdc99..2f15544 100644
--- a/cc/library_sdk_member.go
+++ b/cc/library_sdk_member.go
@@ -80,7 +80,7 @@
 		for _, target := range targets {
 			name, version := StubsLibNameAndVersion(lib)
 			if version == "" {
-				version = LatestStubsVersionFor(mctx.Config(), name)
+				version = "latest"
 			}
 			variations := target.Variations()
 			if mctx.Device() {
diff --git a/cc/linkable.go b/cc/linkable.go
index 4c84163..6d8a4b7 100644
--- a/cc/linkable.go
+++ b/cc/linkable.go
@@ -26,8 +26,10 @@
 	StubsVersions() []string
 	BuildStubs() bool
 	SetBuildStubs()
-	SetStubsVersions(string)
+	SetStubsVersion(string)
 	StubsVersion() string
+	SetAllStubsVersions([]string)
+	AllStubsVersions() []string
 	HasStubsVariants() bool
 	SelectedStl() string
 	ApiLevel() string
diff --git a/rust/rust.go b/rust/rust.go
index e561477..d22acea 100644
--- a/rust/rust.go
+++ b/rust/rust.go
@@ -460,12 +460,20 @@
 	panic("SetBuildStubs not yet implemented for rust modules")
 }
 
-func (mod *Module) SetStubsVersions(string) {
-	panic("SetStubsVersions not yet implemented for rust modules")
+func (mod *Module) SetStubsVersion(string) {
+	panic("SetStubsVersion not yet implemented for rust modules")
 }
 
 func (mod *Module) StubsVersion() string {
-	panic("SetStubsVersions not yet implemented for rust modules")
+	panic("StubsVersion not yet implemented for rust modules")
+}
+
+func (mod *Module) SetAllStubsVersions([]string) {
+	panic("SetAllStubsVersions not yet implemented for rust modules")
+}
+
+func (mod *Module) AllStubsVersions() []string {
+	return nil
 }
 
 func (mod *Module) BuildStaticVariant() bool {