[Generation] Fix Transition probs
Author: patrickvonplaten
Pull request: yes

# 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 -->

Fixes #15869

This PR fixes incorrectly computed transition probabilties for beam search.
In beam search it's common to want to know the transition probability between tokens -> see: https://discuss.huggingface.co/t/generation-probabilities-how-to-compute-probabilities-of-output-scores-for-gpt2/3175/15?u=patrickvonplaten

Currently there is a bug for every beam search that ends before `max_length` as discovered by #15869 .

This PR fixes this behavior and adds a couple of tests. 

🚨 **There is a tiny breaking change** in the output format of `beam_indices`. Instead of returning a `tuple(tuple(int))` a `torch.LongTensor` is returned. Since the feature was broken before (`beam_indices` were incorrect), this is hardly a breaking change and necessary to make the functionality more userfriendly and robustu🚨

@patil-suraj @gante , it would be super nice if you could do an in-depth review here also to understand this feature.
**Note:** people do seem to be interested in output scores for generation as can be seen by the large number of views here: https://discuss.huggingface.co/t/generation-probabilities-how-to-compute-probabilities-of-output-scores-for-gpt2/3175

Feel free to drop any question in the PR if you don't understand something or something is unclear - thanks :pray:

## 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/main/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/main/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/main/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

 -->


Comments:
_The documentation is not available anymore as the PR was closed or merged._

I'll talk about this feature in more-detail in a tutorial

Hello,
Regarding the follow up to these 3 posts: https://discuss.huggingface.co/t/generation-probabilities-how-to-compute-probabilities-of-output-scores-for-gpt2/3175/23, https://discuss.huggingface.co/t/retrieving-probability-over-tokens-during-beam-search/21217, https://discuss.huggingface.co/t/get-top-k-tokens-for-each-time-step-instead-of-the-highest-probability-token/14032:

Can you show us, step by step, how to retrieve the probability for each token generated for each prediction in a `transformers.generation_utils.BeamSearchEncoderDecoderOutput`?

Much appreciated.

Hi @adamkhakhar -- it is in our plans to write a tutorial for that :) It probably won't happen in the next 1 or 2 months, but stay tuned 🙏  

Hi @patrickvonplaten and @gante; what is the perspective on the tutorial?

No news yet :)

Thanks for the quick response @gante. I will stay tuned. Can you tell me whether you can expect the first generated sequence to always have the highest probability?

@MotzWanted yeah, if you use `num_return_sequences >1` with beam search, the output sequences are sorted by their score (from highest to lowest)

But if I replicate this [showcase](https://discuss.huggingface.co/t/generation-probabilities-how-to-compute-probabilities-of-output-scores-for-gpt2/3175/26) of @patrickvonplaten to compute the sequence probabilities of the output scores, I don't get that output sequences are sorted by their probability (from highest to lowest). Can you explain to me why this is so @gante?

@MotzWanted my reply was given in the context of this thread, which is related to `beam_search`. Any call with `do_sample=True`, as in the example you linked, will lose the sorting property.

A working example:
```python
import torch
from transformers import AutoModelForCausalLM
from transformers import AutoTokenizer


gpt2 = AutoModelForCausalLM.from_pretrained("gpt2", return_dict_in_generate=True)
tokenizer = AutoTokenizer.from_pretrained("gpt2")

input_ids = tokenizer("Today is a nice day", return_tensors="pt").input_ids

generated_outputs = gpt2.generate(input_ids, num_return_sequences=3, num_beams=3, output_scores=True)
print(generated_outputs.sequences_scores)
```