Thanks for your suggestion. I was missing a torch.cuda.synchronize() before the call to torch.multinomial(), an oversight. I added a more efficient sampling scheme described here 43, and fixed a few other inefficiencies in linear_nce() and now NCE does run a bit faster than CE on the 10K vocabulary PTB and much faster on larger vocabularies.
| epoch   1 |   200/ 1327 batches | lr 20.00 | ms/batch 11.86 | nce_loss  5.90
| epoch   1 |   400/ 1327 batches | lr 20.00 | ms/batch 10.10 | nce_loss  5.39
| epoch   1 |   600/ 1327 batches | lr 20.00 | ms/batch 10.09 | nce_loss  5.17
| epoch   1 |   800/ 1327 batches | lr 20.00 | ms/batch 10.09 | nce_loss  5.06
| epoch   1 |  1000/ 1327 batches | lr 20.00 | ms/batch 10.09 | nce_loss  4.94
| epoch   1 |  1200/ 1327 batches | lr 20.00 | ms/batch 10.12 | nce_loss  4.82
| end of epoch   1 | time: 14.59s | valid loss  6.02 | valid ppl   412.35
| epoch   2 |   200/ 1327 batches | lr 20.00 | ms/batch 10.19 | nce_loss  4.71
| epoch   2 |   400/ 1327 batches | lr 20.00 | ms/batch 10.13 | nce_loss  4.62
| epoch   2 |   600/ 1327 batches | lr 20.00 | ms/batch 10.11 | nce_loss  4.56
| epoch   2 |   800/ 1327 batches | lr 20.00 | ms/batch 10.12 | nce_loss  4.52
| epoch   2 |  1000/ 1327 batches | lr 20.00 | ms/batch 10.16 | nce_loss  4.50
| epoch   2 |  1200/ 1327 batches | lr 20.00 | ms/batch 10.12 | nce_loss  4.41
| end of epoch   2 | time: 14.30s | valid loss  5.69 | valid ppl   297.10