I have a similar implementation for NCE. After nvprof the training script, I found that the CUDA kernel sampleMultinomialWithReplacement (https://github.com/pytorch/pytorch/blob/0f65c9267d5ec55584b0ec65acb5374c95af9c16/torch/lib/THC/THCTensorRandom.cuh 52), i.e. torch.multinomial costs about 75% of the training time.