diff --git a/src/com/android/launcher3/LauncherModel.java b/src/com/android/launcher3/LauncherModel.java
index aaeb3cb..c0cf135 100644
--- a/src/com/android/launcher3/LauncherModel.java
+++ b/src/com/android/launcher3/LauncherModel.java
@@ -53,6 +53,8 @@
 import com.android.launcher3.model.ShortcutsChangedTask;
 import com.android.launcher3.model.UserLockStateChangedTask;
 import com.android.launcher3.shortcuts.DeepShortcutManager;
+import com.android.launcher3.util.IntSparseArrayMap;
+import com.android.launcher3.util.ItemInfoMatcher;
 import com.android.launcher3.util.PackageUserKey;
 import com.android.launcher3.util.Preconditions;
 import com.android.launcher3.util.Thunk;
@@ -171,6 +173,30 @@
         enqueueModelUpdateTask(new PackageUpdatedTask(op, user, packageName));
     }
 
+    public void onSessionFailure(String packageName, UserHandle user) {
+        enqueueModelUpdateTask(new BaseModelUpdateTask() {
+            @Override
+            public void execute(LauncherAppState app, BgDataModel dataModel, AllAppsList apps) {
+                final IntSparseArrayMap<Boolean> removedIds = new IntSparseArrayMap<>();
+                synchronized (dataModel) {
+                    for (ItemInfo info : dataModel.itemsIdMap) {
+                        if (info instanceof WorkspaceItemInfo
+                                && ((WorkspaceItemInfo) info).hasPromiseIconUi()
+                                && user.equals(info.user)
+                                && info.getIntent() != null
+                                && TextUtils.equals(packageName, info.getIntent().getPackage())) {
+                            removedIds.put(info.id, true /* remove */);
+                        }
+                    }
+                }
+
+                if (!removedIds.isEmpty()) {
+                    deleteAndBindComponentsRemoved(ItemInfoMatcher.ofItemIds(removedIds, false));
+                }
+            }
+        });
+    }
+
     @Override
     public void onPackageRemoved(String packageName, UserHandle user) {
         onPackagesRemoved(user, packageName);
diff --git a/src/com/android/launcher3/compat/PackageInstallerCompat.java b/src/com/android/launcher3/compat/PackageInstallerCompat.java
index 11cb1f8..55df98b 100644
--- a/src/com/android/launcher3/compat/PackageInstallerCompat.java
+++ b/src/com/android/launcher3/compat/PackageInstallerCompat.java
@@ -19,6 +19,7 @@
 import android.content.ComponentName;
 import android.content.Context;
 import android.content.pm.PackageInstaller;
+import android.content.pm.PackageInstaller.SessionInfo;
 import android.os.Process;
 import android.os.UserHandle;
 
@@ -29,6 +30,7 @@
 import androidx.annotation.NonNull;
 
 import com.android.launcher3.Utilities;
+import com.android.launcher3.util.PackageUserKey;
 
 public abstract class PackageInstallerCompat {
 
@@ -52,19 +54,19 @@
         }
     }
 
-    public static UserHandle getUserHandle(PackageInstaller.SessionInfo info) {
+    public static UserHandle getUserHandle(SessionInfo info) {
         return Utilities.ATLEAST_Q ? info.getUser() : Process.myUserHandle();
     }
 
     /**
      * @return a map of active installs to their progress
      */
-    public abstract HashMap<String, PackageInstaller.SessionInfo> updateAndGetActiveSessionCache();
+    public abstract HashMap<PackageUserKey, SessionInfo> updateAndGetActiveSessionCache();
 
     /**
      * @return an active SessionInfo for {@param pkg} or null if none exists.
      */
-    public abstract PackageInstaller.SessionInfo getActiveSessionInfo(UserHandle user, String pkg);
+    public abstract SessionInfo getActiveSessionInfo(UserHandle user, String pkg);
 
     public abstract void onStop();
 
@@ -75,7 +77,7 @@
         public final int progress;
         public final UserHandle user;
 
-        private PackageInstallInfo(@NonNull PackageInstaller.SessionInfo info) {
+        private PackageInstallInfo(@NonNull SessionInfo info) {
             this.state = STATUS_INSTALLING;
             this.packageName = info.getAppPackageName();
             this.componentName = new ComponentName(packageName, "");
@@ -91,7 +93,7 @@
             this.user = user;
         }
 
-        public static PackageInstallInfo fromInstallingState(PackageInstaller.SessionInfo info) {
+        public static PackageInstallInfo fromInstallingState(SessionInfo info) {
             return new PackageInstallInfo(info);
         }
 
@@ -101,7 +103,7 @@
 
     }
 
-    public abstract List<PackageInstaller.SessionInfo> getAllVerifiedSessions();
+    public abstract List<SessionInfo> getAllVerifiedSessions();
 
     /**
      * Returns true if a promise icon was already added to the home screen for {@param sessionId}.
diff --git a/src/com/android/launcher3/compat/PackageInstallerCompatVL.java b/src/com/android/launcher3/compat/PackageInstallerCompatVL.java
index 09d9310..f421f7c 100644
--- a/src/com/android/launcher3/compat/PackageInstallerCompatVL.java
+++ b/src/com/android/launcher3/compat/PackageInstallerCompatVL.java
@@ -88,12 +88,13 @@
     }
 
     @Override
-    public HashMap<String, SessionInfo> updateAndGetActiveSessionCache() {
-        HashMap<String, SessionInfo> activePackages = new HashMap<>();
+    public HashMap<PackageUserKey, SessionInfo> updateAndGetActiveSessionCache() {
+        HashMap<PackageUserKey, SessionInfo> activePackages = new HashMap<>();
         for (SessionInfo info : getAllVerifiedSessions()) {
             addSessionInfoToCache(info, getUserHandle(info));
             if (info.getAppPackageName() != null) {
-                activePackages.put(info.getAppPackageName(), info);
+                activePackages.put(new PackageUserKey(info.getAppPackageName(),
+                        getUserHandle(info)), info);
                 mActiveSessions.put(info.getSessionId(),
                         new PackageUserKey(info.getAppPackageName(), getUserHandle(info)));
             }
@@ -139,6 +140,8 @@
      * - The settings for it are enabled
      * - The user installed the app
      * - There is an app icon and label (For apps with no launching activity, no icon is provided).
+     * - The app is not already installed
+     * - A promise icon for the session has not already been created
      */
     private void tryQueuePromiseAppIcon(SessionInfo sessionInfo) {
         if (Utilities.ATLEAST_OREO && FeatureFlags.PROMISE_APPS_NEW_INSTALLS.get()
@@ -147,7 +150,9 @@
                 && sessionInfo.getInstallReason() == PackageManager.INSTALL_REASON_USER
                 && sessionInfo.getAppIcon() != null
                 && !TextUtils.isEmpty(sessionInfo.getAppLabel())
-                && !mPromiseIconIds.contains(sessionInfo.getSessionId())) {
+                && !mPromiseIconIds.contains(sessionInfo.getSessionId())
+                && mLauncherApps.getApplicationInfo(sessionInfo.getAppPackageName(), 0,
+                        getUserHandle(sessionInfo)) == null) {
             SessionCommitReceiver.queuePromiseAppIconAddition(mAppContext, sessionInfo);
             mPromiseIconIds.add(sessionInfo.getSessionId());
             updatePromiseIconPrefs();
@@ -182,12 +187,14 @@
                 sendUpdate(PackageInstallInfo.fromState(success ? STATUS_INSTALLED : STATUS_FAILED,
                         packageName, key.mUser));
 
-                if (!success && FeatureFlags.PROMISE_APPS_NEW_INSTALLS.get()) {
+                if (!success && FeatureFlags.PROMISE_APPS_NEW_INSTALLS.get()
+                        && mPromiseIconIds.contains(sessionId)) {
                     LauncherAppState appState = LauncherAppState.getInstanceNoCreate();
                     if (appState != null) {
-                        LauncherModel model = appState.getModel();
-                        model.onPackageRemoved(packageName, key.mUser);
+                        appState.getModel().onSessionFailure(packageName, key.mUser);
                     }
+                    // If it is successful, the id is removed in the the package added flow.
+                    removePromiseIconId(sessionId);
                 }
             }
         }
diff --git a/src/com/android/launcher3/model/FirstScreenBroadcast.java b/src/com/android/launcher3/model/FirstScreenBroadcast.java
index 1149b55..a0b7177 100644
--- a/src/com/android/launcher3/model/FirstScreenBroadcast.java
+++ b/src/com/android/launcher3/model/FirstScreenBroadcast.java
@@ -26,6 +26,7 @@
 import com.android.launcher3.LauncherAppWidgetInfo;
 import com.android.launcher3.LauncherSettings;
 import com.android.launcher3.util.MultiHashMap;
+import com.android.launcher3.util.PackageUserKey;
 
 import java.util.ArrayList;
 import java.util.HashMap;
@@ -34,6 +35,8 @@
 import java.util.Map;
 import java.util.Set;
 
+import static android.os.Process.myUserHandle;
+
 /**
  * Helper class to send broadcasts to package installers that have:
  * - Items on the first screen
@@ -60,7 +63,7 @@
 
     private final MultiHashMap<String, String> mPackagesForInstaller;
 
-    public FirstScreenBroadcast(HashMap<String, SessionInfo> sessionInfoForPackage) {
+    public FirstScreenBroadcast(HashMap<PackageUserKey, SessionInfo> sessionInfoForPackage) {
         mPackagesForInstaller = getPackagesForInstaller(sessionInfoForPackage);
     }
 
@@ -69,11 +72,13 @@
      *         of packages with active sessions for that installer.
      */
     private MultiHashMap<String, String> getPackagesForInstaller(
-            HashMap<String, SessionInfo> sessionInfoForPackage) {
+            HashMap<PackageUserKey, SessionInfo> sessionInfoForPackage) {
         MultiHashMap<String, String> packagesForInstaller = new MultiHashMap<>();
-        for (Map.Entry<String, SessionInfo> entry : sessionInfoForPackage.entrySet()) {
-            packagesForInstaller.addToList(entry.getValue().getInstallerPackageName(),
-                    entry.getKey());
+        for (Map.Entry<PackageUserKey, SessionInfo> entry : sessionInfoForPackage.entrySet()) {
+            if (myUserHandle().equals(entry.getKey().mUser)) {
+                packagesForInstaller.addToList(entry.getValue().getInstallerPackageName(),
+                        entry.getKey().mPackageName);
+            }
         }
         return packagesForInstaller;
     }
diff --git a/src/com/android/launcher3/model/GridSizeMigrationTask.java b/src/com/android/launcher3/model/GridSizeMigrationTask.java
index faecc06..783e908 100644
--- a/src/com/android/launcher3/model/GridSizeMigrationTask.java
+++ b/src/com/android/launcher3/model/GridSizeMigrationTask.java
@@ -34,10 +34,12 @@
 import com.android.launcher3.util.GridOccupancy;
 import com.android.launcher3.util.IntArray;
 import com.android.launcher3.util.IntSparseArrayMap;
+import com.android.launcher3.util.PackageUserKey;
 
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashSet;
+import java.util.function.Consumer;
 
 import androidx.annotation.VisibleForTesting;
 
@@ -970,8 +972,9 @@
                 .getInstalledPackages(PackageManager.GET_UNINSTALLED_PACKAGES)) {
             validPackages.add(info.packageName);
         }
-        validPackages.addAll(PackageInstallerCompat.getInstance(context)
-                .updateAndGetActiveSessionCache().keySet());
+        PackageInstallerCompat.getInstance(context)
+                .updateAndGetActiveSessionCache().keySet()
+                .forEach(packageUserKey -> validPackages.add(packageUserKey.mPackageName));
         return validPackages;
     }
 
diff --git a/src/com/android/launcher3/model/LoaderTask.java b/src/com/android/launcher3/model/LoaderTask.java
index 63b451d..c9ac685 100644
--- a/src/com/android/launcher3/model/LoaderTask.java
+++ b/src/com/android/launcher3/model/LoaderTask.java
@@ -19,6 +19,7 @@
 import static com.android.launcher3.ItemInfoWithIcon.FLAG_DISABLED_LOCKED_USER;
 import static com.android.launcher3.ItemInfoWithIcon.FLAG_DISABLED_SAFEMODE;
 import static com.android.launcher3.ItemInfoWithIcon.FLAG_DISABLED_SUSPENDED;
+import static com.android.launcher3.compat.PackageInstallerCompat.getUserHandle;
 import static com.android.launcher3.model.LoaderResults.filterCurrentWorkspaceItems;
 import static com.android.launcher3.util.Executors.MODEL_EXECUTOR;
 import static com.android.launcher3.util.PackageManagerHelper.isSystemApp;
@@ -75,6 +76,7 @@
 import com.android.launcher3.util.LooperIdleLock;
 import com.android.launcher3.util.MultiHashMap;
 import com.android.launcher3.util.PackageManagerHelper;
+import com.android.launcher3.util.PackageUserKey;
 import com.android.launcher3.util.TraceHelper;
 
 import java.util.ArrayList;
@@ -295,8 +297,9 @@
         synchronized (mBgDataModel) {
             mBgDataModel.clear();
 
-            final HashMap<String, SessionInfo> installingPkgs =
+            final HashMap<PackageUserKey, SessionInfo> installingPkgs =
                     mPackageInstaller.updateAndGetActiveSessionCache();
+            final PackageUserKey tempPackageKey = new PackageUserKey(null, null);
             mFirstScreenBroadcast = new FirstScreenBroadcast(installingPkgs);
 
             Map<ShortcutKey, ShortcutInfo> shortcutKeyToPinnedShortcuts = new HashMap<>();
@@ -433,9 +436,10 @@
                                     // installed later.
                                     FileLog.d(TAG, "package not yet restored: " + targetPkg);
 
+                                    tempPackageKey.update(targetPkg, c.user);
                                     if (c.hasRestoreFlag(WorkspaceItemInfo.FLAG_RESTORE_STARTED)) {
                                         // Restore has started once.
-                                    } else if (installingPkgs.containsKey(targetPkg)) {
+                                    } else if (installingPkgs.containsKey(tempPackageKey)) {
                                         // App restore has started. Update the flag
                                         c.restoreFlag |= WorkspaceItemInfo.FLAG_RESTORE_STARTED;
                                         c.updater().put(LauncherSettings.Favorites.RESTORED,
diff --git a/src/com/android/launcher3/util/PackageUserKey.java b/src/com/android/launcher3/util/PackageUserKey.java
index 041c708..f243ca6 100644
--- a/src/com/android/launcher3/util/PackageUserKey.java
+++ b/src/com/android/launcher3/util/PackageUserKey.java
@@ -30,7 +30,7 @@
         update(packageName, user);
     }
 
-    private void update(String packageName, UserHandle user) {
+    public void update(String packageName, UserHandle user) {
         mPackageName = packageName;
         mUser = user;
         mHashCode = Arrays.hashCode(new Object[] {packageName, user});
diff --git a/tests/src/com/android/launcher3/ui/widget/BindWidgetTest.java b/tests/src/com/android/launcher3/ui/widget/BindWidgetTest.java
index 3a7df64..e6348d9 100644
--- a/tests/src/com/android/launcher3/ui/widget/BindWidgetTest.java
+++ b/tests/src/com/android/launcher3/ui/widget/BindWidgetTest.java
@@ -44,6 +44,7 @@
 import com.android.launcher3.ui.AbstractLauncherUiTest;
 import com.android.launcher3.ui.TestViewHelpers;
 import com.android.launcher3.util.ContentWriter;
+import com.android.launcher3.util.PackageUserKey;
 import com.android.launcher3.util.rule.ShellCommandRule;
 import com.android.launcher3.widget.PendingAddWidgetInfo;
 import com.android.launcher3.widget.WidgetHostViewLoader;
@@ -54,7 +55,9 @@
 import org.junit.Test;
 import org.junit.runner.RunWith;
 
+import java.util.HashSet;
 import java.util.Set;
+import java.util.function.Consumer;
 
 /**
  * Tests for bind widget flow.
@@ -326,9 +329,12 @@
         int count = 0;
         String pkg = invalidPackage;
 
-        Set<String> activePackage = getOnUiThread(() ->
-                PackageInstallerCompat.getInstance(mTargetContext)
-                        .updateAndGetActiveSessionCache().keySet());
+        Set<String> activePackage = getOnUiThread(() -> {
+            Set<String> packages = new HashSet<>();
+            PackageInstallerCompat.getInstance(mTargetContext).updateAndGetActiveSessionCache()
+                    .keySet().forEach(packageUserKey -> packages.add(packageUserKey.mPackageName));
+            return packages;
+        });
         while(true) {
             try {
                 mTargetContext.getPackageManager().getPackageInfo(