diff --git a/quickstep/src/com/android/quickstep/RecentTasksList.java b/quickstep/src/com/android/quickstep/RecentTasksList.java
index 71ce32b..9b647b8 100644
--- a/quickstep/src/com/android/quickstep/RecentTasksList.java
+++ b/quickstep/src/com/android/quickstep/RecentTasksList.java
@@ -119,12 +119,8 @@
     }
 
     @Override
-    public synchronized void onTaskStackChanged() {
+    public void onRecentTaskListUpdated() {
         mChangeId++;
-    }
-
-    @Override
-    public void onTaskRemoved(int taskId) {
         mTasks = loadTasksInBackground(Integer.MAX_VALUE, false);
     }
 
diff --git a/quickstep/src/com/android/quickstep/RecentsModel.java b/quickstep/src/com/android/quickstep/RecentsModel.java
index 650169c..ede56b6 100644
--- a/quickstep/src/com/android/quickstep/RecentsModel.java
+++ b/quickstep/src/com/android/quickstep/RecentsModel.java
@@ -16,15 +16,12 @@
 package com.android.quickstep;
 
 import static com.android.quickstep.TaskUtils.checkCurrentOrManagedUserId;
-import static com.android.systemui.shared.system.QuickStepContract.KEY_EXTRA_SUPPORTS_WINDOW_CORNERS;
-import static com.android.systemui.shared.system.QuickStepContract.KEY_EXTRA_WINDOW_CORNER_RADIUS;
 
 import android.annotation.TargetApi;
 import android.app.ActivityManager;
 import android.content.ComponentCallbacks2;
 import android.content.Context;
 import android.os.Build;
-import android.os.Bundle;
 import android.os.HandlerThread;
 import android.os.Process;
 import android.os.RemoteException;
@@ -36,12 +33,11 @@
 import com.android.systemui.shared.recents.model.Task;
 import com.android.systemui.shared.recents.model.ThumbnailData;
 import com.android.systemui.shared.system.ActivityManagerWrapper;
-import com.android.systemui.shared.system.BackgroundExecutor;
 import com.android.systemui.shared.system.KeyguardManagerCompat;
-import com.android.systemui.shared.system.QuickStepContract;
 import com.android.systemui.shared.system.TaskStackChangeListener;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 import java.util.function.Consumer;
 
@@ -132,7 +128,7 @@
     }
 
     @Override
-    public void onTaskStackChangedBackground() {
+    public void onRecentTaskListUpdated() {
         if (!mThumbnailCache.isPreloadingEnabled()) {
             // Skip if we aren't preloading
             return;
@@ -147,7 +143,11 @@
         // Keep the cache up to date with the latest thumbnails
         int runningTaskId = RecentsModel.getRunningTaskId();
         mTaskList.getTaskKeys(mThumbnailCache.getCacheSize(), tasks -> {
+            Collection<Task.TaskKey> currentKeys = mThumbnailCache.getTaskKeys();
+            List<Task.TaskKey> newKeys = new ArrayList<>(currentKeys.size());
+
             for (Task task : tasks) {
+                newKeys.add(task.key);
                 if (task.key.id == runningTaskId) {
                     // Skip the running task, it's not going to have an up-to-date snapshot by the
                     // time the user next enters overview
@@ -155,6 +155,13 @@
                 }
                 mThumbnailCache.updateThumbnailInCache(task);
             }
+
+            // Remove all keys we had before but no longer are in recents now
+            currentKeys.removeAll(newKeys);
+            for (Task.TaskKey tk : currentKeys) {
+                mThumbnailCache.remove(tk);
+            }
+
         });
     }
 
@@ -170,12 +177,6 @@
         }
     }
 
-    @Override
-    public void onTaskRemoved(int taskId) {
-        Task.TaskKey dummyKey = new Task.TaskKey(taskId, 0, null, null, 0, 0);
-        mThumbnailCache.remove(dummyKey);
-    }
-
     public void setSystemUiProxy(ISystemUiProxy systemUiProxy) {
         mSystemUiProxy = systemUiProxy;
     }
diff --git a/quickstep/src/com/android/quickstep/TaskThumbnailCache.java b/quickstep/src/com/android/quickstep/TaskThumbnailCache.java
index 57c5a27..c7c44ae 100644
--- a/quickstep/src/com/android/quickstep/TaskThumbnailCache.java
+++ b/quickstep/src/com/android/quickstep/TaskThumbnailCache.java
@@ -31,6 +31,7 @@
 import com.android.systemui.shared.recents.model.ThumbnailData;
 import com.android.systemui.shared.system.ActivityManagerWrapper;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.function.Consumer;
 
 public class TaskThumbnailCache {
@@ -179,6 +180,10 @@
         return request;
     }
 
+    public Collection<TaskKey> getTaskKeys() {
+        return mCache.getValues();
+    }
+
     /**
      * Clears the cache.
      */