diff --git a/compiler/dex/verified_method.cc b/compiler/dex/verified_method.cc
index a5979cc..fdcafe8 100644
--- a/compiler/dex/verified_method.cc
+++ b/compiler/dex/verified_method.cc
@@ -229,7 +229,21 @@
                                                               inst->VRegA_21c()));
       const verifier::RegType& cast_type =
           method_verifier->ResolveCheckedClass(dex::TypeIndex(inst->VRegB_21c()));
-      if (cast_type.IsStrictlyAssignableFrom(reg_type, method_verifier)) {
+      // Pass null for the method verifier to not record the VerifierDeps dependency
+      // if the types are not assignable.
+      if (cast_type.IsStrictlyAssignableFrom(reg_type, /* method_verifier */ nullptr)) {
+        // The types are assignable, we record that dependency in the VerifierDeps so
+        // that if this changes after OTA, we will re-verify again.
+        // We check if reg_type has a class, as the verifier may have inferred it's
+        // 'null'.
+        if (reg_type.HasClass()) {
+          DCHECK(cast_type.HasClass());
+          verifier::VerifierDeps::MaybeRecordAssignability(method_verifier->GetDexFile(),
+                                                           cast_type.GetClass(),
+                                                           reg_type.GetClass(),
+                                                           /* strict */ true,
+                                                           /* assignable */ true);
+        }
         // Verify ordering for push_back() to the sorted vector.
         DCHECK(safe_cast_set_.empty() || safe_cast_set_.back() < dex_pc);
         safe_cast_set_.push_back(dex_pc);
diff --git a/compiler/verifier_deps_test.cc b/compiler/verifier_deps_test.cc
index 52765f9..23f54d7 100644
--- a/compiler/verifier_deps_test.cc
+++ b/compiler/verifier_deps_test.cc
@@ -508,7 +508,7 @@
                                          /* src */ "LMySSLSocket;",
                                          /* is_strict */ true,
                                          /* is_assignable */ true));
-  ASSERT_TRUE(HasAssignable("Ljava/net/Socket;", "LMySSLSocket;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/net/Socket;", "Ljavax/net/ssl/SSLSocket;", true));
 }
 
 TEST_F(VerifierDepsTest, Assignable_DestinationInBoot2) {
@@ -516,7 +516,7 @@
                                          /* src */ "LMySimpleTimeZone;",
                                          /* is_strict */ true,
                                          /* is_assignable */ true));
-  ASSERT_TRUE(HasAssignable("Ljava/util/TimeZone;", "LMySimpleTimeZone;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/util/TimeZone;", "Ljava/util/SimpleTimeZone;", true));
 }
 
 TEST_F(VerifierDepsTest, Assignable_DestinationInBoot3) {
@@ -584,7 +584,7 @@
                                          /* src */ "LMySSLSocket;",
                                          /* is_strict */ true,
                                          /* is_assignable */ false));
-  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "LMySSLSocket;", false));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "Ljavax/net/ssl/SSLSocket;", false));
 }
 
 TEST_F(VerifierDepsTest, NotAssignable_DestinationInBoot2) {
@@ -592,7 +592,7 @@
                                          /* src */ "LMySimpleTimeZone;",
                                          /* is_strict */ true,
                                          /* is_assignable */ false));
-  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "LMySimpleTimeZone;", false));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "Ljava/util/SimpleTimeZone;", false));
 }
 
 TEST_F(VerifierDepsTest, NotAssignable_BothArrays) {
@@ -654,7 +654,7 @@
 
 TEST_F(VerifierDepsTest, MergeTypes_RegisterLines) {
   ASSERT_TRUE(VerifyMethod("MergeTypes_RegisterLines"));
-  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "LMySocketTimeoutException;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "Ljava/net/SocketTimeoutException;", true));
   ASSERT_TRUE(HasAssignable(
       "Ljava/lang/Exception;", "Ljava/util/concurrent/TimeoutException;", true));
 }
@@ -841,7 +841,7 @@
                        "public",
                        "Ljava/io/InterruptedIOException;"));
   ASSERT_TRUE(HasAssignable(
-      "Ljava/io/InterruptedIOException;", "LMySocketTimeoutException;", true));
+      "Ljava/io/InterruptedIOException;", "Ljava/net/SocketTimeoutException;", true));
 }
 
 TEST_F(VerifierDepsTest, InstanceField_Resolved_DeclaredInSuperclass1) {
@@ -854,7 +854,7 @@
                        "public",
                        "Ljava/io/InterruptedIOException;"));
   ASSERT_TRUE(HasAssignable(
-      "Ljava/io/InterruptedIOException;", "LMySocketTimeoutException;", true));
+      "Ljava/io/InterruptedIOException;", "Ljava/net/SocketTimeoutException;", true));
 }
 
 TEST_F(VerifierDepsTest, InstanceField_Resolved_DeclaredInSuperclass2) {
@@ -866,7 +866,7 @@
                        "public",
                        "Ljava/io/InterruptedIOException;"));
   ASSERT_TRUE(HasAssignable(
-      "Ljava/io/InterruptedIOException;", "LMySocketTimeoutException;", true));
+      "Ljava/io/InterruptedIOException;", "Ljava/net/SocketTimeoutException;", true));
 }
 
 TEST_F(VerifierDepsTest, InstanceField_Unresolved_ReferrerInBoot) {
@@ -995,7 +995,7 @@
                         "public",
                         "Ljava/lang/Throwable;"));
   // Type dependency on `this` argument.
-  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "LMySocketTimeoutException;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/net/SocketTimeoutException;", true));
 }
 
 TEST_F(VerifierDepsTest, InvokeVirtual_Resolved_DeclaredInSuperclass1) {
@@ -1009,7 +1009,7 @@
                         "public",
                         "Ljava/lang/Throwable;"));
   // Type dependency on `this` argument.
-  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "LMySocketTimeoutException;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/net/SocketTimeoutException;", true));
 }
 
 TEST_F(VerifierDepsTest, InvokeVirtual_Resolved_DeclaredInSuperclass2) {
@@ -1123,7 +1123,7 @@
 TEST_F(VerifierDepsTest, InvokeSuper_ThisNotAssignable) {
   ASSERT_FALSE(VerifyMethod("InvokeSuper_ThisNotAssignable"));
   ASSERT_TRUE(HasClass("Ljava/lang/Integer;", true, "public final"));
-  ASSERT_TRUE(HasAssignable("Ljava/lang/Integer;", "LMain;", false));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Integer;", "Ljava/lang/Thread;", false));
   ASSERT_TRUE(HasMethod(
       "virtual", "Ljava/lang/Integer;", "intValue", "()I", true, "public", "Ljava/lang/Integer;"));
 }
diff --git a/runtime/verifier/reg_type-inl.h b/runtime/verifier/reg_type-inl.h
index 10f1be5..aa4a259 100644
--- a/runtime/verifier/reg_type-inl.h
+++ b/runtime/verifier/reg_type-inl.h
@@ -112,7 +112,8 @@
       } else if (lhs.HasClass() && rhs.HasClass()) {
         // Test assignability from the Class point-of-view.
         bool result = lhs.GetClass()->IsAssignableFrom(rhs.GetClass());
-        // Record assignability dependency. The `verifier` is null during unit tests.
+        // Record assignability dependency. The `verifier` is null during unit tests and
+        // VerifiedMethod::GenerateSafeCastSet.
         if (verifier != nullptr) {
           VerifierDeps::MaybeRecordAssignability(
               verifier->GetDexFile(), lhs.GetClass(), rhs.GetClass(), strict, result);
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index 3af7c01..4cebb7b 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -355,6 +355,12 @@
     return;
   }
 
+  if (source->IsObjectClass() && !is_assignable) {
+    // j.l.Object is trivially non-assignable to other types, don't
+    // record it.
+    return;
+  }
+
   if (destination == source ||
       destination->IsObjectClass() ||
       (!is_strict && destination->IsInterface())) {
@@ -396,6 +402,21 @@
     return;
   }
 
+  if (!IsInClassPath(source) && !source->IsInterface() && !destination->IsInterface()) {
+    // Find the super class at the classpath boundary. Only that class
+    // can change the assignability.
+    // TODO: also chase the boundary for interfaces.
+    do {
+      source = source->GetSuperClass();
+    } while (!IsInClassPath(source));
+
+    // If that class is the actual destination, no need to record it.
+    if (source == destination) {
+      return;
+    }
+  }
+
+
   // Get string IDs for both descriptors and store in the appropriate set.
   dex::StringIndex destination_id = GetClassDescriptorStringId(dex_file, destination);
   dex::StringIndex source_id = GetClassDescriptorStringId(dex_file, source);