Understanding Youtube recommender (candidate generation step)
$v_j$ is the learned vector of weights (dimension 256) that connect the last hidden layer (dimension 256) to the corresponding output node for video class $j$. The last hidden layer is the user embedding vector $u$.

The paper uses a vocabulary $V$ of 1M video classes so the deep neural net learns 1M vectors of weights that connect the last hidden layer to each class: $[v_1, \ldots, v_{1M}]$. Negative sampling is used to train such a model with so many classes.

Below softmax function on page 2 section 3.1 with vj and $u$.

$$P(w_t=i|U,C) = \frac{e^{v_i u}}{\sum_{j \in V e^{v_{j}u}}}$$

I believe $v_j$ is "thought of as a separate output video embedding" because $v_j$ can be interpreted as a compressed representation of video j in a 256 dimensional vector space.

Since $e^x$ is monotonically increasing, we just care about the dot product $v_iu$ in the numerator of equation above. This is why "the scoring problem reduces to a nearest neighbor search in the dot product space" where we simply find the nearest neighbors $v$ to $u$.