Association rule learning for multi-classification suggestions
Assuming there are many repetitions of each attribute and class, an embedding space can be learned. Attributes and classes that co-occur together will be projected into nearby space. One example is affinity weighted embedding.

Then prediction becomes approximate nearest neighbor search. For a given set of attributes, find the nearest class(es). One example is locality-sensitive hashing.

The strategy of combining learned embedding spaces and approximate nearest neighbor search scales very well for prediction. Search time can remain constant if you are willing to accept a looser definition of "approximate" as the data grows.