diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index c571d5e..d30e677 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -2456,6 +2456,9 @@
       if (appView.definitionFor(methodToKeep.method) == null) {
         clazz.appendVirtualMethod(methodToKeep);
         appView.appInfo().invalidateTypeCacheFor(methodToKeep.method.holder);
+        // The addition of a bridge method can lead to a change of resolution, thus the cached
+        // resolution targets are invalid.
+        virtualTargetsMarkedAsReachable.remove(methodToKeep.method);
       }
     }
     action.getAction().accept(builder);