diff --git a/apex/apex.go b/apex/apex.go
index a40a753..a87187a 100644
--- a/apex/apex.go
+++ b/apex/apex.go
@@ -868,13 +868,23 @@
 	mctx.VisitDirectDeps(func(child android.Module) {
 		depName := mctx.OtherModuleName(child)
 		if am, ok := child.(android.ApexModule); ok && am.CanHaveApexVariants() &&
-			cur.DepIsInSameApex(mctx, child) {
+			(cur.DepIsInSameApex(mctx, child) || inAnySdk(child)) {
 			android.UpdateApexDependency(apexBundles, depName, directDep)
 			am.BuildForApexes(apexBundles)
 		}
 	})
 }
 
+// If a module in an APEX depends on a module from an SDK then it needs an APEX
+// specific variant created for it. Refer to sdk.sdkDepsReplaceMutator.
+func inAnySdk(module android.Module) bool {
+	if sa, ok := module.(android.SdkAware); ok {
+		return sa.IsInAnySdk()
+	}
+
+	return false
+}
+
 // Create apex variations if a module is included in APEX(s).
 func apexMutator(mctx android.BottomUpMutatorContext) {
 	if am, ok := mctx.Module().(android.ApexModule); ok && am.CanHaveApexVariants() {
@@ -1849,6 +1859,14 @@
 		apexName := ctx.ModuleName()
 		fromName := ctx.OtherModuleName(from)
 		toName := ctx.OtherModuleName(to)
+
+		// If `to` is not actually in the same APEX as `from` then it does not need apex_available and neither
+		// do any of its dependencies.
+		if am, ok := from.(android.DepIsInSameApex); ok && !am.DepIsInSameApex(ctx, to) {
+			// As soon as the dependency graph crosses the APEX boundary, don't go further.
+			return false
+		}
+
 		if to.AvailableFor(apexName) || whitelistedApexAvailable(apexName, toName) {
 			return true
 		}
diff --git a/apex/apex_test.go b/apex/apex_test.go
index a76f50d..716e263 100644
--- a/apex/apex_test.go
+++ b/apex/apex_test.go
@@ -3518,16 +3518,10 @@
 	testApexError(t, `requires "libbaz" that is not available for the APEX. Dependency path:
 .*via tag apex\.dependencyTag.*"sharedLib".*
 .*-> libfoo.*link:shared.*
-.*via tag cc\.DependencyTag.*"reuse objects".*
-.*-> libfoo.*link:static.*
-.*via tag cc\.DependencyTag.*"shared from static".*
+.*via tag cc\.DependencyTag.*"shared".*
 .*-> libbar.*link:shared.*
-.*via tag cc\.DependencyTag.*"reuse objects".*
-.*-> libbar.*link:static.*
-.*via tag cc\.DependencyTag.*"shared from static".*
-.*-> libbaz.*link:shared.*
-.*via tag cc\.DependencyTag.*"reuse objects".*
-.*-> libbaz.*link:static.*`, `
+.*via tag cc\.DependencyTag.*"shared".*
+.*-> libbaz.*link:shared.*`, `
 	apex {
 		name: "myapex",
 		key: "myapex.key",
diff --git a/java/java.go b/java/java.go
index 20e01f2..57ed29d 100644
--- a/java/java.go
+++ b/java/java.go
@@ -1764,11 +1764,6 @@
 	if staticLibTag == ctx.OtherModuleDependencyTag(dep) {
 		return true
 	}
-	// Also, a dependency to an sdk member is also considered as such. This is required because
-	// sdk members should be mutated into APEXes. Refer to sdk.sdkDepsReplaceMutator.
-	if sa, ok := dep.(android.SdkAware); ok && sa.IsInAnySdk() {
-		return true
-	}
 	return false
 }
 
@@ -2508,11 +2503,6 @@
 	if staticLibTag == ctx.OtherModuleDependencyTag(dep) {
 		return true
 	}
-	// Also, a dependency to an sdk member is also considered as such. This is required because
-	// sdk members should be mutated into APEXes. Refer to sdk.sdkDepsReplaceMutator.
-	if sa, ok := dep.(android.SdkAware); ok && sa.IsInAnySdk() {
-		return true
-	}
 	return false
 }
 
diff --git a/sdk/java_sdk_test.go b/sdk/java_sdk_test.go
index cbffb50..4a2c053 100644
--- a/sdk/java_sdk_test.go
+++ b/sdk/java_sdk_test.go
@@ -53,30 +53,18 @@
 			system_modules: "none",
 			sdk_version: "none",
 			host_supported: true,
-			apex_available: [
-				"//apex_available:platform",
-				"//apex_available:anyapex",
-			],
 		}
 
 		java_import {
 			name: "sdkmember_mysdk_1",
 			sdk_member_name: "sdkmember",
 			host_supported: true,
-			apex_available: [
-				"//apex_available:platform",
-				"//apex_available:anyapex",
-			],
 		}
 
 		java_import {
 			name: "sdkmember_mysdk_2",
 			sdk_member_name: "sdkmember",
 			host_supported: true,
-			apex_available: [
-				"//apex_available:platform",
-				"//apex_available:anyapex",
-			],
 		}
 
 		java_library {
diff --git a/sdk/sdk.go b/sdk/sdk.go
index a5709ac..cb5a605 100644
--- a/sdk/sdk.go
+++ b/sdk/sdk.go
@@ -312,7 +312,7 @@
 	ctx.BottomUp("SdkMemberInterVersion", memberInterVersionMutator).Parallel()
 }
 
-// RegisterPostDepshMutators registers post-deps mutators to support modules implementing SdkAware
+// RegisterPostDepsMutators registers post-deps mutators to support modules implementing SdkAware
 // interface and the sdk module type. This function has been made public to be called by tests
 // outside of the sdk package
 func RegisterPostDepsMutators(ctx android.RegisterMutatorsContext) {
@@ -431,7 +431,7 @@
 	}
 }
 
-// Step 6: ensure that the dependencies from outside of the APEX are all from the required SDKs
+// Step 6: ensure that the dependencies outside of the APEX are all from the required SDKs
 func sdkRequirementsMutator(mctx android.TopDownMutatorContext) {
 	if m, ok := mctx.Module().(interface {
 		android.DepIsInSameApex
@@ -442,12 +442,20 @@
 			return
 		}
 		mctx.VisitDirectDeps(func(dep android.Module) {
-			if mctx.OtherModuleDependencyTag(dep) == android.DefaultsDepTag {
+			tag := mctx.OtherModuleDependencyTag(dep)
+			if tag == android.DefaultsDepTag {
 				// dependency to defaults is always okay
 				return
 			}
 
-			// If the dep is from outside of the APEX, but is not in any of the
+			// Ignore the dependency from the unversioned member to any versioned members as an
+			// apex that depends on the unversioned member will not also be depending on a versioned
+			// member.
+			if _, ok := tag.(sdkMemberVersionedDepTag); ok {
+				return
+			}
+
+			// If the dep is outside of the APEX, but is not in any of the
 			// required SDKs, we know that the dep is a violation.
 			if sa, ok := dep.(android.SdkAware); ok {
 				if !m.DepIsInSameApex(mctx, dep) && !requiredSdks.Contains(sa.ContainingSdk()) {