Same sequence gets different token probabilities depending on whether it's generated from sampling or beam search
Author: hacobe
Pull request: no
Labels: name: bug

### System Info

```shell
- `transformers` version: 4.20.0.dev0
- Platform: Linux-5.4.188+-x86_64-with-Ubuntu-18.04-bionic
- Python version: 3.7.13
- Huggingface_hub version: 0.6.0
- PyTorch version (GPU?): 1.11.0+cu113 (False)
- Tensorflow version (GPU?): 2.8.0 (False)
- Flax version (CPU?/GPU?/TPU?): not installed (NA)
- Jax version: not installed
- JaxLib version: not installed
- Using GPU in script?: No
- Using distributed or parallel set-up in script?:No
```


### Who can help?

@patrickvonplaten 

### Information

- [X] The official example scripts
- [ ] My own modified scripts

### Tasks

- [X] An officially supported task in the `examples` folder (such as GLUE/SQuAD, ...)
- [ ] My own task or dataset (give details below)

### Reproduction

I first generate a sequence using beam search with T5. I then generate a sequence using sampling set to a particular seed that happens to get the same sequence as the beam search decoding. I then calculate the token probabilities for both sequences and find that they differ despite being the same sequences.

This colab reproduces the behavior:
https://colab.research.google.com/drive/1vLmUfqYdKVo1z2Ztv2V2sQ29nDCYNbFK?usp=sharing

### Expected behavior

```shell
A sequence generated from a model using beam search and the same sequence generated from the same model from sampling should have the same token probabilities provided that they have the same hyperparameters (e.g., the length penalty should be the same for both).
```


Comments:
Heey @hacobe,

I'm not sure this is a bug. Note that beam_search is very much different from sample, see: https://huggingface.co/blog/how-to-generate

Why should they give the same probabilities?

Hi @patrickvonplaten,

The probability for a token is the output of the softmax layer for that token conditioning on the sequence generated so far. The way we generate a sequence changes if we use beam search instead of sampling, but the definition of the probability does not change. The probability is a function of the model you're using and the sequence generated so far. If you're using the same model and you've happened to generate the same sequence (and hyperparameters like length penalty are the same), then the probabilities should be the same.

Take the example under the "Beam search" heading in that blog post. The top beam search sequence is ("The", "dog", "has"). It starts with the prompt "The". The token "dog" has a probability of 0.4 conditional on the sequence ("The"). The token "has" has a probability of 0.9 conditional on the sequence ("The", "dog").

Now suppose we sample from the same model starting with the prompt "The". What is the probability of the selecting the token "dog" at this step? It still has a probability of 0.4, because we're using the same model and conditioning on the same sequence ("The"). Suppose we happen to sample "dog". Then the sequence is ("The", "dog"). What is the probability of selecting the token "has" at this step? Again, the token "has" will have a probability of 0.9, because we're using the same model and conditioning on the same sequence ("The", "dog").

By the way, thanks for all your work on the token probabilities! I think it's an important feature (both OpenAI and fairseq return token probabilities in their APIs). It's a key input for uncertainty estimation and error detection.

Hey @hacobe,

Note that for beam search we sample from `current_beam_scores + log_prob_of_token` whereas for sampling we just sample from prob_of_token.

For beam search see here: 
https://github.com/huggingface/transformers/blob/5c17918fe4cda80dae5b7ec8f0b2d23a813c4a05/src/transformers/generation_utils.py#L2225

For sampling see here: 
https://github.com/huggingface/transformers/blob/5c17918fe4cda80dae5b7ec8f0b2d23a813c4a05/src/transformers/generation_utils.py#L1974

Hi @patrickvonplaten,

By "for beam search we sample from `current_beam_scores + log_prob_of_token`", do you mean that beam search selects sequences based on `current_beam_scores + log_prob_of_token`? Beam search is deterministic. It does not involve sampling. `current_beam_scores + log_prob_of_token` is the log sequence probability used to select the top k sequences at each step in beam search. I'm comparing the transition beam scores given by `compute_transition_beam_scores`, which I interpret as the log token (not sequence) probabilities, to the log token (not sequence) probabilities from sampling. If you think I'm still missing something, I can dig into the code when I get some time. Thanks for your help!

Hi @patrickvonplaten,
I didn't realize top_k is set to 50 by default. When I change top_k = 0, then I get the same probabilities as expected.