Models to deal with huge possible outputs
There is something called "sampled softmax" (e.g. tensorflow's implementation), which simply partitions the output space and at each training step only takes into account one of the partitions (see section 3 from this article to learn the math). Sampled softmax is only meant to speed up training for very large output spaces; at inference time you use normal softmax.

Also, if your output is of hierarchical nature, you can use hierarchical softmax. See this blog post for a review of different methods to handle very large categorical space.