[Beam Search] Correct returned beam scores
# What does this PR do?

<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

<!-- Remove if not applicable -->

**🚨 🚨 🚨 BREAKING CHANGE: This PR is a breaking change to the values of the generate output `scores` 🚨 🚨 🚨**

It concerns the following use cases:

```python
num_beams =  # > 2 enabling beam search, beam sample or group beam search
generate_outputs = generate(...., num_beams=num_beams, return_dict_in_output=True, output_scores=True)
scores = generate_outputs.scores
```

After multiple issues and discussions, which are best summarized here:
- https://discuss.huggingface.co/t/generation-probabilities-how-to-compute-probabilities-of-output-scores-for-gpt2/3175/15?u=patrickvonplaten
- https://github.com/huggingface/transformers/issues/14612
- https://github.com/huggingface/transformers/issues/14065
- https://github.com/huggingface/transformers/issues/14086

it seems like the best solution here is to do a breaking change in that the output beam scores of generate now correspond better to the transition scores.

The added tests to this PR should explain nicely how one can retrieve all the relevant information from the beam scores in combination with newly added beam_indices.

Very curious to also hear your thoughts on this PR:
- @felix-schneider
- @hacobe
- @qqaatw

## Before submitting
- [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
- [ ] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/master/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [ ] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? Please add a link
      to it if that's the case.
- [ ] Did you make sure to update the documentation with your changes? Here are the
      [documentation guidelines](https://github.com/huggingface/transformers/tree/master/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/master/docs#writing-source-documentation).
- [ ] Did you write any new necessary tests?


## Who can review?

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors who may be interested in your PR.

<!-- Your PR will be replied to more quickly if you can figure out the right person to tag with @

 If you know how to use git blame, that is the easiest way, otherwise, here is a rough guide of **who to tag**.
 Please tag fewer than 3 people.

Models:

- albert, bert, xlm: @LysandreJik
- blenderbot, bart, marian, pegasus, encoderdecoder,  t5: @patrickvonplaten, @patil-suraj
- longformer, reformer, transfoxl, xlnet: @patrickvonplaten
- fsmt: @stas00
- funnel: @sgugger
- gpt2: @patrickvonplaten, @LysandreJik
- rag: @patrickvonplaten, @lhoestq
- tensorflow: @LysandreJik

Library:

- benchmarks: @patrickvonplaten
- deepspeed: @stas00
- ray/raytune: @richardliaw, @amogkam
- text generation: @patrickvonplaten
- tokenizers: @n1t0, @LysandreJik
- trainer: @sgugger
- pipelines: @LysandreJik

Documentation: @sgugger

HF projects:

- datasets: [different repo](https://github.com/huggingface/datasets)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Examples:

- maintained examples (not research project or legacy): @sgugger, @patil-suraj
- research_projects/bert-loses-patience: @JetRunner
- research_projects/distillation: @VictorSanh

 -->

Other related PR maybe : https://github.com/huggingface/transformers/issues/14921<|||||>Thanks a lot for your feedback here guys and sorry to only pick up the PR again.

@Narsil @felix-schneider,

I see that you guys would like to make it easier for the user to directly get the transition probabilities of the generated tokens. 

First, let's clarify a couple of things:
@Narsil, this PR is breaking in that the `scores` output is now different in terms of it's values (the shape stays the same). We have only ever tested for the shape to be correct, but never whether the output values or "correct" (which is a bit weird as it would be similar to testing whether the values of the attention matrices correspond to some hardcoded values. Nevertheless, we verify this now in the test added here. 

So this is indeed a big breaking change (it's somewhat equal to changing the output values of the attention matrices when setting `output_attentions=True`), but given that `scores` output has been an experimental feature and is quite complex for generation, I think we can make an exception here, given all the issues above. Also cc @LysandreJik @sgugger @patil-suraj here - no need to understand the change in-detail, but maybe just so that you're aware that this PR is a big breaking change for people doing `model.generate(...., return_dict_in_generate=True, output_scores=True)`.

Second, @felix-schneider, I do understand your point of view in that outputting the raw `scores` doesn't add much value. However, it is important to keep the following in mind:

1. On of the philosophies of `transformers` is the following:
```
Expose the models’ internals as consistently as possible:

We give access, using a single API, to the full hidden-states and attention weights.
Tokenizer and base model’s API are standardized to easily switch between mode
``` 
(see https://huggingface.co/docs/transformers/philosophy)

This does very well apply here as well. We are simply outputting the raw scores that are used to sample the next token in generation which is in my opinion quite consistent with "expose the models' internals". 

2. The library is heavily used by researchers who do whatsoever with the model internals for analysis, complex algorithms etc...in my experience, there are always a lot of use cases that one doesn't take into account when trying to design an API that "makes most sense for the end user" meaning that often one thinks there is only one use case and that only this use case should be implemented. 
So far the approach of exposing the model's internals worked well IMO (e.g. many people like the fact that the attention mask is that easily available), but as you pointed out it does have the downside to make it more complex and potentially more difficult (especially for development/production oriented users). So it's always a trade-off when deciding what values should be exposed and how.

3. It's **very very** important that we keep backward compatibility. While this PR already breaks Backward comp in some sense, we should definitely not fully remove the `scores` output - all users that have used `scores` before would then have no way to use `transformers` for their use case anymore -> so this cannot be done.

4. We have to be careful to not make maintenance explode here. The less "bare bone" the output is, *i.e.* the more specific, the more prone it is to have errors and the costlier is the maintenance


As a conclusion, I do like @Narsil idea of adding the functionality of computing the transition probabilites as a function to the output classes (or to the model itself). This way, it's very easy for the user to compute the transition scores (just pass `scores` and `beam_indices` into `model.compute_transition_probabilities(scores, beam_indices)`) this way adding a single line would be enough for the user. 
I agree with @felix-schneider that we should not sum up the probs and we should probably also allow the user to pass an `attention_mask` so that the final values are correctly masked. 

I will adapt the PR according to this. It would be great if you could then take a second look whether it fits your needs <|||||>I see your point, @patrickvonplaten. My suggestion though would be to have the `compute_transition_probabilities` method live with the object returned by `generate`, rather than the model, as this object already has access to all required values: `scores`, `beam_indices` and `attention_mask`.

Putting it with the model implies the ability for different models to modify this behaviour. I'm not sure that this is actually possible as getting transition scores from model outputs is done by beam search and not customizable by models.<|||||>> I see your point, @patrickvonplaten. My suggestion though would be to have the `compute_transition_probabilities` method live with the object returned by `generate`, rather than the model, as this object already has access to all required values: `scores`, `beam_indices` and `attention_mask`.
> 
> Putting it with the model implies the ability for different models to modify this behaviour. I'm not sure that this is actually possible as getting transition scores from model outputs is done by beam search and not customizable by models.

I see your point! We could add the function (also as @Narsil suggested) to the `BeamSearchEncoderDecoderOutput` class as you rightly say it's pretty "generation function"-specific. I'm still leaning against it though because, we've never done this kind of design in `transformers` and I'm not sure it's very intuitive for our users as the workflow would look as follows:

```python 
sequence_outputs = model.generate(..., output_scores=True, return_dict_in_generate=True)
transition_scores = sequence_outputs.compute_transition_scores(vocab_size=model.config.vocab_size)   # not that it's also a a bit tedious to get the vocab size here (we might though actually retrieve that from the shape of some outputs (not trivial though)
```

I think there are three possible designs we could do here:

- 1. The one shown above
- 2. What's implemented now:
```python
sequence_outputs = model.generate(..., output_scores=True, return_dict_in_generate=True)
transition_scores = model.compute_transition_scores(sequence_outputs.sequences, sequence_outputs.scores, sequence_outputs.beam_indices)
```
- 3. Just compute it when scores should be returned:
```python
sequence_outputs = model.generate(..., output_scores=True, return_dict_in_generate=True)
sequence_outputs.transition_scores
```

While 3 is the nicest for the end-user, it is a **very** specific (it creates the transition scores of only the generated sequence ids). Also, it creates quite some maintenance which I would like to avoid a bit.

To summarize, I think 2 is the best way to go because it's general in a sense that people can create the transition probs of any possible sequence of ids (not just the generated ones). 

Keen to hear your final thoughts<|||||>I agree with `2.` It's easier to upgrade later, than downgrade `3.` later (if maintenance becomes hard).<|||||>I like the `3.` more than `2.` if the maintenance cost would not become too heavy as IMO it looks more intuitive to users to get the transition scores that most users are looking for (I think). We could also keep `model.compute_transition_scores` in case users want to calculate their own scores.<|||||>Ok seems like we need some votes here for 2. vs 3. haha. 

@patil-suraj @LysandreJik @sgugger what do you think?<|||||>I don't have enough context in terms of what "the burden of maintenance" entails for option 3 there, but it would be the most elegant in my opinion. But as a propriety to only be computed when asked for, not as a regular attribute that would be computed all the time (if that's possible, if not we should fall back to option 2).

I'm also okay with option 2.<|||||>Taking everything into account, I'm going for option 2. now (which is the one implemented here). Given that:
    - we can always go from 2. to 3. (but not the other way around because of backward comp), 
    - 2. is more general than 3. at lower maintenance - I see many use cases of computing the scores of not generated ids, but almost generated ids
    - and the fact that this is a very researchy feature in general where some knowledge about `generate` can be expected

2 is the better option here. Let's see in the coming month how much this feature is used. I'll also try to make an updated blog post about `generate` in general where I'll include this feature<|||||>hi @patrickvonplaten,
It seems that your PR is not available yet in transformers =4.18.0 . My first attempt as many people :)  is to try to match between the `scores` and the sequnces using softmax until I see your discussion. Is this will cover `T5ForConditionalGeneration`  ? I am interested to get the `logit` or `score` for each token in the `sequences`