How to create a multi-dimensional softmax output in Tensorflow?
You are confusing "dimensions" with "order of tensor". A softmax with 256 different categories is a 256 dimensional vector, but is also a tensor with order 1 (whilst a matrix is a tensor of order 2). The paper is using the technical terms correctly, so the 256 dimensional vector is just a normal vector with 256 scalar entries.

Therefore a 256-dimensional softmax in TensorFlow is typically an output layer that looks something like this:

y = tf.nn.softmax(tf.matmul(h, W) + b)


where h is the last hidden layer, W is the weight matrix n x 256, and b is the bias 1 x 256 vector.


  In the paper, the candidate generation neural network model outputs a softmax with 256 dimensions, which acts as an "output embedding" of each of the 1M video classes


That is a description of the training process that compresses 1M different inputs to 256-dimensional output for use as an embedding for recommendation matches. The softmax is at the output, and as far as I can see is just a normal softmax classifier output as seen in many other classifier networks (except the result is not technically being used to classify anything). I am not clear on what supervision data was used or on what the input representation was. However, I don't think it likely that 1M "classes" ever appear as e.g. 1-hot encoding, because that would not scale out usefully to the many other millions of videos - the point of the embedding is to turn disparate features of the videos into something that be used as a similarity measure, that can be run on any video stored in YouTube.