diff --git a/quickstep/src/com/android/quickstep/RecentsModel.java b/quickstep/src/com/android/quickstep/RecentsModel.java
index d7b1e8b..d9ecdcd 100644
--- a/quickstep/src/com/android/quickstep/RecentsModel.java
+++ b/quickstep/src/com/android/quickstep/RecentsModel.java
@@ -25,9 +25,12 @@
 import android.os.HandlerThread;
 import android.os.Process;
 import android.os.RemoteException;
+import android.os.UserHandle;
 import android.util.Log;
 
 import com.android.launcher3.MainThreadExecutor;
+import com.android.launcher3.compat.LauncherAppsCompat;
+import com.android.launcher3.compat.LauncherAppsCompat.OnAppsChangedCallbackCompat;
 import com.android.launcher3.util.MainThreadInitializedObject;
 import com.android.systemui.shared.recents.ISystemUiProxy;
 import com.android.systemui.shared.recents.model.Task;
@@ -71,6 +74,7 @@
         mIconCache = new TaskIconCache(context, loaderThread.getLooper());
         mThumbnailCache = new TaskThumbnailCache(context, loaderThread.getLooper());
         ActivityManagerWrapper.getInstance().registerTaskStackListener(this);
+        setupPackageListener();
     }
 
     public TaskIconCache getIconCache() {
@@ -169,6 +173,7 @@
     public void onTaskRemoved(int taskId) {
         Task.TaskKey dummyKey = new Task.TaskKey(taskId, 0, null, null, 0, 0);
         mThumbnailCache.remove(dummyKey);
+        mIconCache.onTaskRemoved(dummyKey);
     }
 
     public void setSystemUiProxy(ISystemUiProxy systemUiProxy) {
@@ -203,6 +208,21 @@
         }
     }
 
+    private void setupPackageListener() {
+        LauncherAppsCompat.getInstance(mContext)
+                .addOnAppsChangedCallback(new OnAppsChangedCallbackCompat() {
+                    @Override
+                    public void onPackageRemoved(String packageName, UserHandle user) {
+                        mIconCache.invalidatePackage(packageName);
+                    }
+
+                    @Override
+                    public void onPackageChanged(String packageName, UserHandle user) {
+                        mIconCache.invalidatePackage(packageName);
+                    }
+                });
+    }
+
     public void addThumbnailChangeListener(TaskThumbnailChangeListener listener) {
         mThumbnailChangeListeners.add(listener);
     }
diff --git a/quickstep/src/com/android/quickstep/TaskIconCache.java b/quickstep/src/com/android/quickstep/TaskIconCache.java
index 07af9b3..5e01958 100644
--- a/quickstep/src/com/android/quickstep/TaskIconCache.java
+++ b/quickstep/src/com/android/quickstep/TaskIconCache.java
@@ -31,17 +31,18 @@
 import com.android.launcher3.R;
 import com.android.launcher3.Utilities;
 import com.android.launcher3.icons.cache.HandlerRunnable;
-import com.android.launcher3.uioverrides.RecentsUiFactory;
 import com.android.launcher3.util.Preconditions;
 import com.android.systemui.shared.recents.model.Task;
+import com.android.systemui.shared.recents.model.Task.TaskKey;
 import com.android.systemui.shared.recents.model.TaskKeyLruCache;
 import com.android.systemui.shared.system.ActivityManagerWrapper;
 
+import java.util.Map;
 import java.util.function.Consumer;
 
 /**
  * Manages the caching of task icons and related data.
- * TODO: This class should later be merged into IconCache.
+ * TODO(b/138944598): This class should later be merged into IconCache.
  */
 public class TaskIconCache {
 
@@ -149,6 +150,21 @@
         return label;
     }
 
+
+    void onTaskRemoved(TaskKey taskKey) {
+        mIconCache.remove(taskKey);
+    }
+
+    void invalidatePackage(String packageName) {
+        // TODO(b/138944598): Merge this class into IconCache so we can do this at the base level
+        Map<ComponentName, ActivityInfo> activityInfoCache = mActivityInfoCache.snapshot();
+        for (ComponentName cn : activityInfoCache.keySet()) {
+            if (cn.getPackageName().equals(packageName)) {
+                mActivityInfoCache.remove(cn);
+            }
+        }
+    }
+
     public static abstract class IconLoadRequest extends HandlerRunnable {
         IconLoadRequest(Handler handler) {
             super(handler, null);
diff --git a/src/com/android/launcher3/compat/LauncherAppsCompat.java b/src/com/android/launcher3/compat/LauncherAppsCompat.java
index 58fc73d..cdb5c4d 100644
--- a/src/com/android/launcher3/compat/LauncherAppsCompat.java
+++ b/src/com/android/launcher3/compat/LauncherAppsCompat.java
@@ -27,25 +27,27 @@
 import android.os.Bundle;
 import android.os.UserHandle;
 
+import androidx.annotation.Nullable;
+
 import com.android.launcher3.Utilities;
 import com.android.launcher3.util.PackageUserKey;
 
 import java.util.List;
 
-import androidx.annotation.Nullable;
-
 public abstract class LauncherAppsCompat {
 
     public interface OnAppsChangedCallbackCompat {
-        void onPackageRemoved(String packageName, UserHandle user);
-        void onPackageAdded(String packageName, UserHandle user);
-        void onPackageChanged(String packageName, UserHandle user);
-        void onPackagesAvailable(String[] packageNames, UserHandle user, boolean replacing);
-        void onPackagesUnavailable(String[] packageNames, UserHandle user, boolean replacing);
-        void onPackagesSuspended(String[] packageNames, UserHandle user);
-        void onPackagesUnsuspended(String[] packageNames, UserHandle user);
-        void onShortcutsChanged(String packageName, List<ShortcutInfo> shortcuts,
-                UserHandle user);
+        default void onPackageRemoved(String packageName, UserHandle user) { }
+        default void onPackageAdded(String packageName, UserHandle user) { }
+        default void onPackageChanged(String packageName, UserHandle user) { }
+        default void onPackagesAvailable(String[] packageNames, UserHandle user,
+                boolean replacing) { }
+        default void onPackagesUnavailable(String[] packageNames, UserHandle user,
+                boolean replacing) { }
+        default void onPackagesSuspended(String[] packageNames, UserHandle user) { }
+        default void onPackagesUnsuspended(String[] packageNames, UserHandle user) { }
+        default void onShortcutsChanged(String packageName, List<ShortcutInfo> shortcuts,
+                UserHandle user) { }
     }
 
     protected LauncherAppsCompat() {