~
diff --git a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/project/structure/sessionFactoryHelpers.kt b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/project/structure/sessionFactoryHelpers.kt
index 8d98b7c..a4c0c8b 100644
--- a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/project/structure/sessionFactoryHelpers.kt
+++ b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/project/structure/sessionFactoryHelpers.kt
@@ -49,7 +49,7 @@
     session: FirSession,
     createSubProviders: MutableList<FirSymbolProvider>.() -> Unit
 ): FirCompositeSymbolProvider =
-    FirCompositeSymbolProvider(session, buildList(createSubProviders))
+    FirCompositeSymbolProvider(session, buildList(createSubProviders), isCliMode = false)
 
 @SessionConfiguration
 internal fun FirSession.registerCompilerPluginExtensions(project: Project, module: KtSourceModule) {
diff --git a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirModuleWithDependenciesSymbolProvider.kt b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirModuleWithDependenciesSymbolProvider.kt
index 84f7f56..a5bae38 100644
--- a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirModuleWithDependenciesSymbolProvider.kt
+++ b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirModuleWithDependenciesSymbolProvider.kt
@@ -77,6 +77,12 @@
         getPackageWithoutDependencies(fqName)
             ?: dependencyProvider.getPackage(fqName)
 
+    override fun computePackageSetWithTopLevelCallables(): Set<String>? = null
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>? = null
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name>? = null
+
 
     fun getPackageWithoutDependencies(fqName: FqName): FqName? =
         providers.firstNotNullOfOrNull { it.getPackage(fqName) }
@@ -150,6 +156,18 @@
             }
         }
 
+    override fun computePackageSetWithTopLevelCallables(): Set<String>? {
+        TODO("Not yet implemented")
+    }
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>? {
+        TODO("Not yet implemented")
+    }
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name>? {
+        TODO("Not yet implemented")
+    }
+
 
     private fun <S : FirCallableSymbol<*>> addNewSymbolsConsideringJvmFacades(
         destination: MutableList<S>,
diff --git a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirProvider.kt b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirProvider.kt
index 57828da..3c9e11d 100644
--- a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirProvider.kt
+++ b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/providers/LLFirProvider.kt
@@ -113,6 +113,12 @@
         override fun getPackage(fqName: FqName): FqName? =
             providerHelper.getPackage(fqName)
 
+        override fun computePackageSetWithTopLevelCallables(): Set<String>? = null
+
+        override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>? = null
+
+        override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name>? = null
+
         override fun getClassLikeSymbolByClassId(classId: ClassId): FirClassLikeSymbol<*>? {
             return getFirClassifierByFqName(classId)?.symbol
         }
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/FirAbstractSessionFactory.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/FirAbstractSessionFactory.kt
index 71f5268..f586d76 100644
--- a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/FirAbstractSessionFactory.kt
+++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/FirAbstractSessionFactory.kt
@@ -55,7 +55,7 @@
 
             val providers = createProviders(this, builtinsModuleData, kotlinScopeProvider)
 
-            val symbolProvider = FirCompositeSymbolProvider(this, providers)
+            val symbolProvider = FirCompositeSymbolProvider(this, providers, isCliMode = true)
             register(FirSymbolProvider::class, symbolProvider)
             register(FirProvider::class, FirLibrarySessionProvider(symbolProvider))
         }
@@ -111,10 +111,10 @@
                 dependencyProviders,
             )
 
-            register(FirSymbolProvider::class, FirCompositeSymbolProvider(this, providers))
+            register(FirSymbolProvider::class, FirCompositeSymbolProvider(this, providers, isCliMode = true))
 
             generatedSymbolsProvider?.let { register(FirSwitchableExtensionDeclarationsSymbolProvider::class, it) }
-            register(DEPENDENCIES_SYMBOL_PROVIDER_QUALIFIED_KEY, FirCompositeSymbolProvider(this, dependencyProviders))
+            register(DEPENDENCIES_SYMBOL_PROVIDER_QUALIFIED_KEY, FirCompositeSymbolProvider(this, dependencyProviders, isCliMode = true))
         }
     }
 
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/KlibBasedSymbolProvider.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/KlibBasedSymbolProvider.kt
index 03458c4..a7f566b 100644
--- a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/KlibBasedSymbolProvider.kt
+++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/session/KlibBasedSymbolProvider.kt
@@ -5,8 +5,12 @@
 
 package org.jetbrains.kotlin.fir.session
 
+import org.checkerframework.checker.units.qual.K
 import org.jetbrains.kotlin.descriptors.SourceFile
 import org.jetbrains.kotlin.fir.FirSession
+import org.jetbrains.kotlin.fir.caches.FirCache
+import org.jetbrains.kotlin.fir.caches.firCachesFactory
+import org.jetbrains.kotlin.fir.caches.getValue
 import org.jetbrains.kotlin.fir.declarations.FirDeclarationOrigin
 import org.jetbrains.kotlin.fir.deserialization.*
 import org.jetbrains.kotlin.fir.isNewPlaceForBodyGeneration
@@ -14,9 +18,11 @@
 import org.jetbrains.kotlin.fir.scopes.FirKotlinScopeProvider
 import org.jetbrains.kotlin.fir.symbols.SymbolInternals
 import org.jetbrains.kotlin.library.metadata.KlibMetadataClassDataFinder
+import org.jetbrains.kotlin.library.metadata.KlibMetadataProtoBuf
 import org.jetbrains.kotlin.library.metadata.KlibMetadataSerializerProtocol
 import org.jetbrains.kotlin.library.metadata.resolver.KotlinResolvedLibrary
 import org.jetbrains.kotlin.metadata.ProtoBuf
+import org.jetbrains.kotlin.metadata.deserialization.NameResolver
 import org.jetbrains.kotlin.metadata.deserialization.NameResolverImpl
 import org.jetbrains.kotlin.name.ClassId
 import org.jetbrains.kotlin.name.FqName
@@ -24,6 +30,7 @@
 import org.jetbrains.kotlin.serialization.deserialization.IncompatibleVersionErrorData
 import org.jetbrains.kotlin.serialization.deserialization.descriptors.DeserializedContainerAbiStability
 import org.jetbrains.kotlin.serialization.deserialization.descriptors.DeserializedContainerSource
+import org.jetbrains.kotlin.serialization.deserialization.getClassId
 import org.jetbrains.kotlin.utils.SmartList
 import java.nio.file.Paths
 
@@ -99,18 +106,74 @@
 
     override fun computePackageSetWithNonClassDeclarations(): Set<String> = fragmentNamesInLibraries.keys
 
-    // Looks like it's expensive to compute the presence of a class properly for KLib
-    override fun mayHaveTopLevelClass(classId: ClassId): Boolean = true
+    private val knownTopLevelClassifierInPackage: FirCache<FqName, Set<String>, Nothing?> =
+        session.firCachesFactory.createCache { packageFqName: FqName, _: Nothing? ->
+            buildSet {
+                forEachFragmentInPackage(packageFqName) { _, fragment, nameResolver ->
+                    for (classNameId in fragment.getExtension(KlibMetadataProtoBuf.className).orEmpty()) {
+                        add(nameResolver.getClassId(classNameId).shortClassName.asString())
+                    }
+                }
+            }
+        }
+
+    override fun knownTopLevelClassesInPackage(packageFqName: FqName): Set<String> =
+        knownTopLevelClassifierInPackage.getValue(packageFqName)
 
     @OptIn(SymbolInternals::class)
     override fun extractClassMetadata(classId: ClassId, parentContext: FirDeserializationContext?): ClassMetadataFindResult? {
-        val packageStringName = classId.packageFqName.asString()
+        forEachFragmentInPackage(classId.packageFqName) { resolvedLibrary, fragment, nameResolver ->
+            val finder = KlibMetadataClassDataFinder(fragment, nameResolver)
+            val classProto = finder.findClassData(classId)?.classProto ?: return@forEachFragmentInPackage
 
-        val librariesWithFragment = fragmentNamesInLibraries[packageStringName] ?: return null
+            val libraryPath = Paths.get(resolvedLibrary.library.libraryFile.path)
+            val moduleData = moduleDataProvider.getModuleData(libraryPath) ?: return null
+
+            return ClassMetadataFindResult.NoMetadata { symbol ->
+                val source = object : DeserializedContainerSource {
+                    override val incompatibility: IncompatibleVersionErrorData<*>? = null
+                    override val isPreReleaseInvisible =
+                        deserializationConfiguration.reportErrorsOnPreReleaseDependencies &&
+                                (moduleHeaders[resolvedLibrary]!!.flags and 1) != 0
+                    override val abiStability = DeserializedContainerAbiStability.STABLE
+                    override val presentableString = "Package '${classId.packageFqName}'"
+
+                    override fun getContainingFile() = SourceFile.NO_SOURCE_FILE
+                }
+
+                deserializeClassToSymbol(
+                    classId,
+                    classProto,
+                    symbol,
+                    nameResolver,
+                    session,
+                    moduleData,
+                    annotationDeserializer,
+                    kotlinScopeProvider,
+                    KlibMetadataSerializerProtocol,
+                    parentContext,
+                    source,
+                    origin = defaultDeserializationOrigin,
+                    deserializeNestedClass = this::getClass,
+                )
+                symbol.fir.isNewPlaceForBodyGeneration = isNewPlaceForBodyGeneration(classProto)
+            }
+        }
+
+        return null
+    }
+
+    private inline fun forEachFragmentInPackage(
+        packageFqName: FqName,
+        f: (KotlinResolvedLibrary, ProtoBuf.PackageFragment, NameResolver) -> Unit
+    ) {
+        val packageStringName = packageFqName.asString()
+
+        val librariesWithFragment = fragmentNamesInLibraries[packageStringName] ?: return
 
         for (resolvedLibrary in librariesWithFragment) {
             for (packageMetadataPart in resolvedLibrary.library.packageMetadataParts(packageStringName)) {
-                val libraryPath = Paths.get(resolvedLibrary.library.libraryFile.path)
+
                 val fragment = getPackageFragment(resolvedLibrary, packageStringName, packageMetadataPart)
 
                 val nameResolver = NameResolverImpl(
@@ -118,44 +181,9 @@
                     fragment.qualifiedNames,
                 )
 
-                val finder = KlibMetadataClassDataFinder(fragment, nameResolver)
-                val classProto = finder.findClassData(classId)?.classProto ?: continue
-
-                val moduleData = moduleDataProvider.getModuleData(libraryPath) ?: return null
-
-                return ClassMetadataFindResult.NoMetadata { symbol ->
-                    val source = object : DeserializedContainerSource {
-                        override val incompatibility: IncompatibleVersionErrorData<*>? = null
-                        override val isPreReleaseInvisible =
-                            deserializationConfiguration.reportErrorsOnPreReleaseDependencies &&
-                                    (moduleHeaders[resolvedLibrary]!!.flags and 1) != 0
-                        override val abiStability = DeserializedContainerAbiStability.STABLE
-                        override val presentableString = "Package '${classId.packageFqName}'"
-
-                        override fun getContainingFile() = SourceFile.NO_SOURCE_FILE
-                    }
-
-                    deserializeClassToSymbol(
-                        classId,
-                        classProto,
-                        symbol,
-                        nameResolver,
-                        session,
-                        moduleData,
-                        annotationDeserializer,
-                        kotlinScopeProvider,
-                        KlibMetadataSerializerProtocol,
-                        parentContext,
-                        source,
-                        origin = defaultDeserializationOrigin,
-                        deserializeNestedClass = this::getClass,
-                    )
-                    symbol.fir.isNewPlaceForBodyGeneration = isNewPlaceForBodyGeneration(classProto)
-                }
+                f(resolvedLibrary, fragment, nameResolver)
             }
         }
-
-        return null
     }
 
     override fun isNewPlaceForBodyGeneration(classProto: ProtoBuf.Class) = false
diff --git a/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/deserialization/AbstractFirDeserializedSymbolProvider.kt b/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/deserialization/AbstractFirDeserializedSymbolProvider.kt
index 280c1e7..5a35404 100644
--- a/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/deserialization/AbstractFirDeserializedSymbolProvider.kt
+++ b/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/deserialization/AbstractFirDeserializedSymbolProvider.kt
@@ -114,7 +114,25 @@
     // This method should only be used for sake of optimization to avoid having too many empty-list/null values in our caches
     protected abstract fun computePackageSetWithNonClassDeclarations(): Set<String>
 
-    protected abstract fun mayHaveTopLevelClass(classId: ClassId): Boolean
+    override fun computePackageSetWithTopLevelCallables(): Set<String> = computePackageSetWithNonClassDeclarations()
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name> = allNamesByPackage.getValue(packageFqName)
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>? {
+        val classesInPackage = knownTopLevelClassesInPackage(packageFqName) ?: return null
+
+        if (packageFqName.asString() !in packageNamesForNonClassDeclarations) return classesInPackage
+
+        val typeAliasNames = typeAliasesNamesByPackage.getValue(packageFqName)
+        if (typeAliasNames.isEmpty()) return classesInPackage
+
+        return buildSet {
+            addAll(classesInPackage)
+            typeAliasNames.mapTo(this) { it.asString() }
+        }
+    }
+
+    protected abstract fun knownTopLevelClassesInPackage(packageFqName: FqName): Set<String>?
 
     protected abstract fun extractClassMetadata(
         classId: ClassId,
@@ -229,6 +247,11 @@
         return classCache.getValue(classId, parentContext)
     }
 
+    private fun mayHaveTopLevelClass(topLevelClassId: ClassId): Boolean {
+        val knownClassNames = knownTopLevelClassifiersInPackage(topLevelClassId.packageFqName) ?: return true
+        return topLevelClassId.shortClassName.asString() in knownClassNames
+    }
+
     private fun getTypeAlias(classId: ClassId): FirTypeAliasSymbol? {
         if (!classId.relativeClassName.isOneSegmentFQN()) return null
 
diff --git a/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirBuiltinSymbolProvider.kt b/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirBuiltinSymbolProvider.kt
index 054d7c2..a8ac9d0 100644
--- a/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirBuiltinSymbolProvider.kt
+++ b/compiler/fir/fir-deserialization/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirBuiltinSymbolProvider.kt
@@ -77,6 +77,18 @@
         } ?: syntheticFunctionalInterfaceCache.tryGetSyntheticFunctionalInterface(classId)
     }
 
+    override fun computePackageSetWithTopLevelCallables(): Set<String> =
+        allPackageFragments.keys.mapTo(mutableSetOf()) { it.asString() }
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String> =
+        allPackageFragments[packageFqName]?.flatMapTo(mutableSetOf()) { fragment ->
+            fragment.classDataFinder.allClassIds.map { it.shortClassName.asString() }
+        }.orEmpty()
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name> =
+        allPackageFragments[packageFqName]?.flatMapTo(mutableSetOf()) {
+            it.getTopLevelCallableNames()
+        }.orEmpty()
 
     @FirSymbolProviderInternals
     override fun getTopLevelCallableSymbolsTo(destination: MutableList<FirCallableSymbol<*>>, packageFqName: FqName, name: Name) {
@@ -154,6 +166,9 @@
             return getTopLevelFunctionSymbols(name)
         }
 
+        fun getTopLevelCallableNames(): Collection<Name> =
+            packageProto.`package`.functionList.map { nameResolver.getName(it.name) }
+
         fun getTopLevelFunctionSymbols(name: Name): List<FirNamedFunctionSymbol> {
             return packageProto.`package`.functionList.filter { nameResolver.getName(it.name) == name }.map {
                 memberDeserializer.loadFunction(it).symbol
diff --git a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/FirJavaFacade.kt b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/FirJavaFacade.kt
index b1f0262..5f2dd41 100644
--- a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/FirJavaFacade.kt
+++ b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/FirJavaFacade.kt
@@ -92,6 +92,8 @@
         return classId.relativeClassName.topLevelName() in knownNames
     }
 
+    fun knownClassNamesInPackage(packageFqName: FqName): Set<String>? = knownClassNamesInPackage.getValue(packageFqName)
+
     abstract fun getModuleDataForClass(javaClass: JavaClass): FirModuleData
 
     private fun JavaTypeParameter.toFirTypeParameter(
diff --git a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/JavaSymbolProvider.kt b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/JavaSymbolProvider.kt
index c3467ce..3563d16 100644
--- a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/JavaSymbolProvider.kt
+++ b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/JavaSymbolProvider.kt
@@ -45,6 +45,12 @@
     override fun getClassLikeSymbolByClassId(classId: ClassId): FirRegularClassSymbol? =
         if (javaFacade.hasTopLevelClassOf(classId)) getFirJavaClass(classId) else null
 
+    override fun computePackageSetWithTopLevelCallables(): Set<String> = emptySet()
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>? = javaFacade.knownClassNamesInPackage(packageFqName)
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name> = emptySet()
+
     private fun getFirJavaClass(classId: ClassId): FirRegularClassSymbol? =
         classCache.getValue(classId, classId.outerClassId?.let { getFirJavaClass(it) })
 
diff --git a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/JvmClassFileBasedSymbolProvider.kt b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/JvmClassFileBasedSymbolProvider.kt
index 1bad1a7..8483e3e 100644
--- a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/JvmClassFileBasedSymbolProvider.kt
+++ b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/JvmClassFileBasedSymbolProvider.kt
@@ -93,7 +93,7 @@
 
     override fun computePackageSetWithNonClassDeclarations(): Set<String> = packagePartProvider.computePackageSetWithNonClassDeclarations()
 
-    override fun mayHaveTopLevelClass(classId: ClassId): Boolean = javaFacade.hasTopLevelClassOf(classId)
+    override fun knownTopLevelClassesInPackage(packageFqName: FqName): Set<String>? = javaFacade.knownClassNamesInPackage(packageFqName)
 
     private val KotlinJvmBinaryClass.incompatibility: IncompatibleVersionErrorData<JvmMetadataVersion>?
         get() {
diff --git a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/OptionalAnnotationClassesProvider.kt b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/OptionalAnnotationClassesProvider.kt
index 2ca555c..2b59592 100644
--- a/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/OptionalAnnotationClassesProvider.kt
+++ b/compiler/fir/java/src/org/jetbrains/kotlin/fir/java/deserialization/OptionalAnnotationClassesProvider.kt
@@ -45,13 +45,22 @@
         return@lazy Pair(optionalAnnotationClasses, optionalAnnotationPackages)
     }
 
+    private val optionalAnnotationClassNamesByPackage: Map<FqName, Set<String>> by lazy(LazyThreadSafetyMode.PUBLICATION) {
+        buildMap<FqName, MutableSet<String>> {
+            for (classId in optionalAnnotationClassesAndPackages.first.keys) {
+                getOrPut(classId.packageFqName, ::mutableSetOf).add(classId.shortClassName.asString())
+            }
+        }
+    }
+
     override fun computePackagePartsInfos(packageFqName: FqName): List<PackagePartsCacheData> {
         return emptyList()
     }
 
     override fun computePackageSetWithNonClassDeclarations(): Set<String> = optionalAnnotationClassesAndPackages.second
 
-    override fun mayHaveTopLevelClass(classId: ClassId): Boolean = classId in optionalAnnotationClassesAndPackages.first
+    override fun knownTopLevelClassesInPackage(packageFqName: FqName): Set<String> =
+        optionalAnnotationClassNamesByPackage[packageFqName] ?: emptySet()
 
     override fun extractClassMetadata(
         classId: ClassId,
diff --git a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirExtensionDeclarationsSymbolProvider.kt b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirExtensionDeclarationsSymbolProvider.kt
index 3aa8108..570adc6 100644
--- a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirExtensionDeclarationsSymbolProvider.kt
+++ b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirExtensionDeclarationsSymbolProvider.kt
@@ -54,6 +54,35 @@
         hasPackage(packageFqName)
     }
 
+    private val callableNamesInPackageCache: FirLazyValue<Map<FqName, Set<Name>>, Nothing?> =
+        cachesFactory.createLazyValue {
+            computeNamesGroupedByPackage(
+                FirDeclarationGenerationExtension::getTopLevelCallableIds,
+                CallableId::packageName, CallableId::callableName
+            )
+        }
+
+    private val classNamesInPackageCache: FirLazyValue<Map<FqName, Set<String>>, Nothing?> =
+        cachesFactory.createLazyValue {
+            computeNamesGroupedByPackage(
+                FirDeclarationGenerationExtension::getTopLevelClassIds,
+                ClassId::getPackageFqName
+            ) { it.shortClassName.asString() }
+        }
+
+    private fun <I, N> computeNamesGroupedByPackage(
+        ids: FirDeclarationGenerationExtension.() -> Collection<I>,
+        packageFqName: (I) -> FqName,
+        shortName: (I) -> N,
+    ): Map<FqName, Set<N>> =
+        buildMap<FqName, MutableSet<N>> {
+            for (extension in extensions) {
+                for (id in extension.ids()) {
+                    getOrPut(packageFqName(id)) { mutableSetOf() }.add(shortName(id))
+                }
+            }
+        }
+
     private val extensionsByTopLevelClassId: FirLazyValue<Map<ClassId, List<FirDeclarationGenerationExtension>>, Nothing?> =
         session.firCachesFactory.createLazyValue {
             extensions.flatGroupBy { it.topLevelClassIdsCache.getValue() }
@@ -138,4 +167,15 @@
     override fun getPackage(fqName: FqName): FqName? {
         return fqName.takeIf { packageCache.getValue(fqName, null) }
     }
+
+    override fun computePackageSetWithTopLevelCallables(): Set<String> =
+        extensions.flatMapTo(mutableSetOf()) { extension ->
+            extension.topLevelCallableIdsCache.getValue(null).map { it.packageName.asString() }
+        }
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String> =
+        classNamesInPackageCache.getValue()[packageFqName] ?: emptySet()
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name> =
+        callableNamesInPackageCache.getValue()[packageFqName].orEmpty()
 }
diff --git a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirSwitchableExtensionDeclarationsSymbolProvider.kt b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirSwitchableExtensionDeclarationsSymbolProvider.kt
index 9c7f7be..399ff10 100644
--- a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirSwitchableExtensionDeclarationsSymbolProvider.kt
+++ b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/extensions/FirSwitchableExtensionDeclarationsSymbolProvider.kt
@@ -71,6 +71,16 @@
     fun enable() {
         disabled = false
     }
+
+    override fun computePackageSetWithTopLevelCallables(): Set<String>? =
+        delegate.computePackageSetWithTopLevelCallables()
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>? =
+        delegate.knownTopLevelClassifiersInPackage(packageFqName)
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name>? =
+        delegate.computeCallableNamesInPackage(packageFqName)
+
 }
 
 val FirSession.generatedDeclarationsSymbolProvider: FirSwitchableExtensionDeclarationsSymbolProvider? by FirSession.nullableSessionComponentAccessor()
diff --git a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/FirSymbolProvider.kt b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/FirSymbolProvider.kt
index 67b9621..be65c6f 100644
--- a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/FirSymbolProvider.kt
+++ b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/FirSymbolProvider.kt
@@ -55,8 +55,29 @@
     abstract fun getTopLevelPropertySymbolsTo(destination: MutableList<FirPropertySymbol>, packageFqName: FqName, name: Name)
 
     abstract fun getPackage(fqName: FqName): FqName? // TODO: Replace to symbol sometime
+    /**
+     * @returns full package names that might be not empty (have some non-class declarations) in this provider
+     *
+     * In JVM, it's expensive to compute all the packages that might contain a Java class among dependencies.
+     * But, as we have all the metadata, we may be sure about top-level callables and type aliases.
+     * This method should only be used for sake of optimization to avoid having too many empty-list/null values in our caches.
+     */
+    abstract fun computePackageSetWithTopLevelCallables(): Set<String>?
+
+    /**
+     * TODO
+     */
+    abstract fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>?
+
+    abstract fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name>?
 }
 
+/**
+ * Works almost as regular flatMap, but returns a set and returns null if any lambda call returned null
+ */
+inline fun <T, R> Iterable<T>.flatMapToNullableSet(transform: (T) -> Iterable<R>?): Set<R>? =
+    flatMapTo(mutableSetOf()) { transform(it) ?: return null }
+
 private fun FirSymbolProvider.getClassDeclaredMemberScope(classId: ClassId): FirScope? {
     val classSymbol = getClassLikeSymbolByClassId(classId) as? FirRegularClassSymbol ?: return null
     return session.declaredMemberScope(classSymbol.fir)
diff --git a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCompositeSymbolProvider.kt b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCompositeSymbolProvider.kt
index 24df3ec..065e4f1 100644
--- a/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCompositeSymbolProvider.kt
+++ b/compiler/fir/providers/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCompositeSymbolProvider.kt
@@ -5,13 +5,16 @@
 
 package org.jetbrains.kotlin.fir.resolve.providers.impl
 
+import org.jetbrains.kotlin.builtins.functions.FunctionClassKind
 import org.jetbrains.kotlin.fir.FirSession
 import org.jetbrains.kotlin.fir.NoMutableState
+import org.jetbrains.kotlin.fir.caches.FirCache
 import org.jetbrains.kotlin.fir.caches.createCache
 import org.jetbrains.kotlin.fir.caches.firCachesFactory
 import org.jetbrains.kotlin.fir.caches.getValue
 import org.jetbrains.kotlin.fir.resolve.providers.FirSymbolProvider
 import org.jetbrains.kotlin.fir.resolve.providers.FirSymbolProviderInternals
+import org.jetbrains.kotlin.fir.resolve.providers.flatMapToNullableSet
 import org.jetbrains.kotlin.fir.symbols.impl.FirCallableSymbol
 import org.jetbrains.kotlin.fir.symbols.impl.FirClassLikeSymbol
 import org.jetbrains.kotlin.fir.symbols.impl.FirNamedFunctionSymbol
@@ -22,17 +25,45 @@
 import org.jetbrains.kotlin.name.Name
 
 @NoMutableState
-class FirCompositeSymbolProvider(session: FirSession, val providers: List<FirSymbolProvider>) : FirSymbolProvider(session) {
-    private val classCache = session.firCachesFactory.createCache(::computeClass)
+class FirCompositeSymbolProvider(
+    session: FirSession,
+    val providers: List<FirSymbolProvider>,
+    private val isCliMode: Boolean,
+) : FirSymbolProvider(session) {
+
+    private val classLikeCache = session.firCachesFactory.createCache(::computeClass)
     private val topLevelCallableCache = session.firCachesFactory.createCache(::computeTopLevelCallables)
     private val topLevelFunctionCache = session.firCachesFactory.createCache(::computeTopLevelFunctions)
     private val topLevelPropertyCache = session.firCachesFactory.createCache(::computeTopLevelProperties)
     private val packageCache = session.firCachesFactory.createCache(::computePackage)
 
+    private val callablePackageSet: Set<String>? by lazy(LazyThreadSafetyMode.PUBLICATION) {
+        computePackageSetWithTopLevelCallables()
+    }
+
+    private val knownTopLevelClassesByPackage: FirCache<FqName, Set<String>?, Nothing?> =
+        session.firCachesFactory.createCache(::knownTopLevelClassifiersInPackage)
+
+    private val callableNamesInPackage: FirCache<FqName, Set<Name>?, Nothing?> =
+        session.firCachesFactory.createCache(::computeCallableNamesInPackage)
+
+    private fun ensureNotNullForCli(v: Any?) {
+        require(!isCliMode || v != null) {
+            ""
+        }
+    }
+
     override fun getTopLevelCallableSymbols(packageFqName: FqName, name: Name): List<FirCallableSymbol<*>> {
+        if (!mayHaveTopLevelCallablesInPackage(packageFqName, name)) return emptyList()
         return topLevelCallableCache.getValue(CallableId(packageFqName, name))
     }
 
+    private fun mayHaveTopLevelCallablesInPackage(packageFqName: FqName, name: Name): Boolean {
+        if (callablePackageSet != null && packageFqName.asString() !in callablePackageSet!!) return false
+        val callableNamesInPackage = callableNamesInPackage.getValue(packageFqName) ?: return true
+        return name in callableNamesInPackage
+    }
+
     @FirSymbolProviderInternals
     override fun getTopLevelCallableSymbolsTo(destination: MutableList<FirCallableSymbol<*>>, packageFqName: FqName, name: Name) {
         destination += getTopLevelCallableSymbols(packageFqName, name)
@@ -40,11 +71,13 @@
 
     @FirSymbolProviderInternals
     override fun getTopLevelFunctionSymbolsTo(destination: MutableList<FirNamedFunctionSymbol>, packageFqName: FqName, name: Name) {
+        if (!mayHaveTopLevelCallablesInPackage(packageFqName, name)) return
         destination += topLevelFunctionCache.getValue(CallableId(packageFqName, name))
     }
 
     @FirSymbolProviderInternals
     override fun getTopLevelPropertySymbolsTo(destination: MutableList<FirPropertySymbol>, packageFqName: FqName, name: Name) {
+        if (!mayHaveTopLevelCallablesInPackage(packageFqName, name)) return
         destination += topLevelPropertyCache.getValue(CallableId(packageFqName, name))
     }
 
@@ -53,7 +86,18 @@
     }
 
     override fun getClassLikeSymbolByClassId(classId: ClassId): FirClassLikeSymbol<*>? {
-        return classCache.getValue(classId)
+        val knownClassifierNames = knownTopLevelClassesByPackage.getValue(classId.packageFqName)
+        if (knownClassifierNames != null && !isNameForFunctionClass(classId)) {
+            val outerClassId = classId.outerClassId
+            if (outerClassId == null && classId.shortClassName.asString() !in knownClassifierNames) return null
+            if (outerClassId != null && classId.outermostClassId.shortClassName.asString() !in knownClassifierNames) return null
+        }
+
+        return classLikeCache.getValue(classId)
+    }
+
+    private fun isNameForFunctionClass(classId: ClassId): Boolean {
+        return FunctionClassKind.byClassNamePrefix(classId.packageFqName, classId.shortClassName.asString()) != null
     }
 
     @OptIn(FirSymbolProviderInternals::class)
@@ -76,4 +120,13 @@
 
     private fun computeClass(classId: ClassId): FirClassLikeSymbol<*>? =
         providers.firstNotNullOfOrNull { provider -> provider.getClassLikeSymbolByClassId(classId) }
+
+    override fun computePackageSetWithTopLevelCallables(): Set<String>? =
+        providers.flatMapToNullableSet { it.computePackageSetWithTopLevelCallables() }
+
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String>? =
+        providers.flatMapToNullableSet { it.knownTopLevelClassifiersInPackage(packageFqName) }
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name>? =
+        providers.flatMapToNullableSet { it.computeCallableNamesInPackage(packageFqName) }
 }
diff --git a/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCloneableSymbolProvider.kt b/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCloneableSymbolProvider.kt
index 9901e81..e050490 100644
--- a/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCloneableSymbolProvider.kt
+++ b/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirCloneableSymbolProvider.kt
@@ -77,4 +77,13 @@
     override fun getPackage(fqName: FqName): FqName? {
         return null
     }
+
+    override fun computePackageSetWithTopLevelCallables(): Set<String> = emptySet()
+    override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String> =
+        if (packageFqName == StandardClassIds.Cloneable.packageFqName)
+            setOf(StandardClassIds.Cloneable.shortClassName.asString())
+        else
+            emptySet()
+
+    override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name> = emptySet()
 }
diff --git a/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirProviderImpl.kt b/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirProviderImpl.kt
index 110f052..f91b57a 100644
--- a/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirProviderImpl.kt
+++ b/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/providers/impl/FirProviderImpl.kt
@@ -75,6 +75,26 @@
             if (fqName in state.allSubPackages) return fqName
             return null
         }
+
+        override fun computePackageSetWithTopLevelCallables(): Set<String> =
+            state.allSubPackages.mapTo(mutableSetOf()) { it.asString() }
+
+        override fun knownTopLevelClassifiersInPackage(packageFqName: FqName): Set<String> =
+            state.classifierInPackage[packageFqName].orEmpty().mapTo(mutableSetOf()) { it.asString() }
+
+        override fun computeCallableNamesInPackage(packageFqName: FqName): Set<Name> = buildSet {
+            for (key in state.functionMap.keys) {
+                if (key.packageName == packageFqName) {
+                    add(key.callableName)
+                }
+            }
+
+            for (key in state.propertyMap.keys) {
+                if (key.packageName == packageFqName) {
+                    add(key.callableName)
+                }
+            }
+        }
     }
 
     private val FirDeclaration.file: FirFile
@@ -109,6 +129,7 @@
 
             if (!classId.isNestedClass && !classId.isLocal) {
                 data.state.classesInPackage.getOrPut(classId.packageFqName, ::mutableSetOf).add(classId.shortClassName)
+                data.state.classifierInPackage.getOrPut(classId.packageFqName, ::mutableSetOf).add(classId.shortClassName)
             }
 
             regularClass.acceptChildren(this, data)
@@ -120,6 +141,8 @@
             data.state.classifierMap.put(classId, typeAlias)?.let {
                 data.nameConflictsTracker?.registerClassifierRedeclaration(classId, typeAlias.symbol, data.file, it.symbol, prevFile)
             }
+
+            data.state.classifierInPackage.getOrPut(classId.packageFqName, ::mutableSetOf).add(classId.shortClassName)
         }
 
         override fun visitPropertyAccessor(
@@ -166,10 +189,11 @@
     private val state = State()
 
     private class State {
-        val fileMap = mutableMapOf<FqName, List<FirFile>>()
+        val fileMap: MutableMap<FqName, List<FirFile>> = mutableMapOf<FqName, List<FirFile>>()
         val allSubPackages = mutableSetOf<FqName>()
         val classifierMap = mutableMapOf<ClassId, FirClassLikeDeclaration>()
         val classifierContainerFileMap = mutableMapOf<ClassId, FirFile>()
+        val classifierInPackage = mutableMapOf<FqName, MutableSet<Name>>()
         val classesInPackage = mutableMapOf<FqName, MutableSet<Name>>()
         val functionMap = mutableMapOf<CallableId, List<FirNamedFunctionSymbol>>()
         val propertyMap = mutableMapOf<CallableId, List<FirPropertySymbol>>()
@@ -195,6 +219,7 @@
             constructorMap.putAll(other.constructorMap)
             callableContainerMap.putAll(other.callableContainerMap)
             classesInPackage.putAll(other.classesInPackage)
+            classifierInPackage.putAll(other.classifierInPackage)
         }
     }