Could you compare your code and shapes to this:
x = torch.randn(128, 10000, requires_grad=True)
output = F.log_softmax(x, dim=1)
target = torch.randint(0, 10000, (128, ))
criterion = nn.NLLLoss()
loss = criterion(output, target)

output is torch.Size([128, 10000]), while target is torch.Size([128]).