Understanding the softmax output in Youtube's recommender
Part of the confusion comes from different prediction processes used for training and serving.

Softmax is used during training to make predictions for the 1 million video categories. The softmax makes the training of the neural networks gradients easier and works well within deep learning libraries.

Those 1 million video categories also happen to be embedded into 256-dimensional space. During serving, prediction is now a nearest neighbor search. Nearest neighbor search is faster, since it is a dot product operation and can use general purpose libraries.