Fix missing `sequences_scores` in the Whisper beam search output 
Author: Nik-Kras
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.
-->

Fixed missing `sequences_scores`  in the Whisper beam search output .
Transformers v4.44.1 still has a bug with missing `sequences_scores` even when these values are explicitly requested. Below is the code snippet that you could use in the current version and get an error due to missing `sequences_scores`, while it will work fine with version 4.25.1

To reproduce the experiment, download any speech audio file, install transformers 4.44.1 and 4.25.1 and check the output.
In case you have problems with 4.25.1 due to `jax` and `jaxlib` versions, remove version checkers Exceptions and change versions in the setup.py to:
```python
"jax>=0.4",
"jaxlib>=0.4.10",
```

Audio used for this example: [link](https://datasets-server.huggingface.co/cached-assets/NikitaKras/cv_17_test_en_es_fr/--/92f162ad51a63a36d3ed1d4f55d77b2bd9b6b84c/--/default/en/8/audio/audio.mp3?Expires=1724360457&Signature=YpC9kQFkrhSElVZjOYy4hhHzb7ffmj7wEDJlFNHjNAy0h6uL9n2UB7FC~CJvxWS2WHc1D~bch~p~o2SzlTjVN9JIP9sNbgAIUPrCN1PYVV8u-uja4T9dqg69rtYczjuP2fUAs7ZwOOWEHQgAz4nCkOR23WrH73L~roW9BMXwn69DetzcqNPAmAktn5GXtbFQq36ShVJrOGPKsHQ-~NhSpYD-qw~00et6xjgM5mFJrlp8GK7z7c2F4ko9Kv7kuT1JzHKZEQHDGGnIGuEnXNUUwJsvJbhx4hspGr5EqY0eZPmUJ7ZhXJCyP-hu~jw3~2sqIrY4i6Jox3qw3RhaygYrrg__&Key-Pair-Id=K3EI6M078Z3AC3)

Code to reproduce the issue
```python
from transformers import AutoProcessor, AutoModelForSpeechSeq2Seq
import torch
import librosa

# Load the processor and model
processor = AutoProcessor.from_pretrained("openai/whisper-tiny")
model = AutoModelForSpeechSeq2Seq.from_pretrained("openai/whisper-tiny")

# Load and preprocess the audio file
audio_path = "audio.mp3"
audio, sr = librosa.load(audio_path, sr=16000)  # Ensure the sample rate is 16kHz

# Preprocess the audio to get the input features
inputs = processor(audio, sampling_rate=16000, return_tensors="pt")

# Generate the transcription using Beam Search with the model
beam_outputs = model.generate(
    inputs["input_features"],
    num_beams=5,  # Number of beams
    num_return_sequences=5,  # Number of hypotheses to return
    early_stopping=True,
    output_scores=True, 
    return_dict_in_generate=True,
)

# Decode the generated transcriptions
hypotheses = [processor.decode(output_ids, skip_special_tokens=True) for output_ids in beam_outputs.sequences]

# Print out the hypotheses
for i, hypothesis in enumerate(hypotheses):
    print(f"Hypothesis {i + 1}: {hypothesis}. Score: {beam_outputs.sequences_scores[i]}")
```

Output before the fix:
```
TypeError: 'NoneType' object is not subscriptable
```

Expected output:
```
Hypothesis 1:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495032072067261
Hypothesis 2:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495031476020813
Hypothesis 3:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495032072067261
Hypothesis 4:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495031476020813
Hypothesis 5:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495032072067261
```

Solves [#32373](https://github.com/huggingface/transformers/issues/32373) issue


## Before submitting
- [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
- [x] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md#create-a-pull-request),
      Pull Request section?
- [x] 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.

PS: I am not sure that Beam Search behaviour is working as expected. The Beam Search algorithm in Transformers version 4.25.1 looks more natural to me. At least there is more diversity in beams, and they are not just repeated. I assume there is another bug in the Beam Search algorithm in the current version. But I am not confident enough to say that. Could you please review the output of the current version above and the output of the older version below and tell me if that is an expected behaviour @patrickvonplaten, @zucchini-nlp and @gante?

Output of the same code above, but with Transformers version 4.25.1, where hypotheses are more diverse (which is expected due to topk sampling). Also, scores are less similar in comparison to Transformers version 4.44.1.
```
Hypothesis 1:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.4627407491207123
Hypothesis 2:  How is Mozilla going to handle and be with this? Thank you and Q.. Score: -0.4789799749851227
Hypothesis 3:  How is Mozilla going to handle and be with this? Thank you, and cute.. Score: -0.48414239287376404
Hypothesis 4:  How is Mozilla going to handle and be with this? Thank you and cute.. Score: -0.4972183108329773
Hypothesis 5:  How is Mozilla going to handle and be with this? Thank you, and Q.. Score: -0.5054414868354797
```

<!-- 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:

- text models: @ArthurZucker
- vision models: @amyeroberts
- speech models: @sanchit-gandhi
- graph models: @clefourrier

Library:

- flax: @sanchit-gandhi
- generate: @zucchini-nlp (visual-language models) or @gante (all others)
- pipelines: @Narsil
- tensorflow: @gante and @Rocketknight1
- tokenizers: @ArthurZucker
- trainer: @muellerzr and @SunMarc

Integrations:

- deepspeed: HF Trainer/Accelerate: @muellerzr
- ray/raytune: @richardliaw, @amogkam
- Big Model Inference: @SunMarc
- quantization (bitsandbytes, autogpt): @SunMarc

Documentation: @stevhliu

HF projects:

- accelerate: [different repo](https://github.com/huggingface/accelerate)
- datasets: [different repo](https://github.com/huggingface/datasets)
- diffusers: [different repo](https://github.com/huggingface/diffusers)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Maintained examples (not research project or legacy):

- Flax: @sanchit-gandhi
- PyTorch: See Models above and tag the person corresponding to the modality of the example.
- TensorFlow: @Rocketknight1

 -->


Comments:
@Nik-Kras Thank you for opening this issue 🤗 

Regarding beam search: the core method was untouched, except for bug fixes on edge cases. In other words, it is possible but unlikely, our integration tests should have caught noticeable differences in quality 🤗 We did change the input preparation for `generate` in Whisper, which might explain the changes you're seeing. 

If you can get us a snippet where the outputs are different between an old version and the current version, that could help us pin the potential bug! 🐛 

(passing the return questions in the issue along to @sanchit-gandhi / @kamilakesbi , as this is a Whisper-specific question :) )

> @Nik-Kras Thank you for opening this issue 🤗

Happy to contribute!

> If you can get us a snippet where the outputs are different between an old version and the current version, that could help us pin the potential bug! 🐛

Above, I attached a code snippet to generate 5 hypotheses with beam search and print them along with sequences_scores. 

Here is the output for Transformers 4.25.1
```
Hypothesis 1:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.4627407491207123
Hypothesis 2:  How is Mozilla going to handle and be with this? Thank you and Q.. Score: -0.4789799749851227
Hypothesis 3:  How is Mozilla going to handle and be with this? Thank you, and cute.. Score: -0.48414239287376404
Hypothesis 4:  How is Mozilla going to handle and be with this? Thank you and cute.. Score: -0.4972183108329773
Hypothesis 5:  How is Mozilla going to handle and be with this? Thank you, and Q.. Score: -0.5054414868354797
```

Here is the output for Transformers 4.44.1 (after my fix to return sequences_scores)
```
Hypothesis 1:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495032072067261
Hypothesis 2:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495031476020813
Hypothesis 3:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495032072067261
Hypothesis 4:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495031476020813
Hypothesis 5:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495032072067261
```

I only study this topic, but according to articles that explain Beam Search: 
- https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24
- https://huggingface.co/blog/how-to-generate

For each step, you select top `num_beams` tokens instead of a greedy selection of top-1 tokens. Therefore, you should select `num_beams` of different tokens. And while they could converge for some part of the sequence (if other sequences have too low scores), in the end, they still must be different according to the algorithm. And I am not sure the update in input data could change it.

Tell me if I misunderstood Beam Search, but I've seen @patrickvonplaten explaining it with top-k selection, which would result in different tokens. Couldn't find the source, unfortunately. 

@Nik-Kras ah, an important detail: Whisper has a more complex generation algorithm, which goes beyond the traditional beam search (i.e. it has many heuristics on top) 🤗 Have a look at the [original paper](https://arxiv.org/pdf/2212.04356), starting with Table 7

@gante Thanks for sharing! I really appreciate your assistance, as it helps me to learn more!

I was sure that even if Whisper has additional algorithms on top of Beam Search, the results over different versions of Transformers should've been similar, if not the same. 
Do you think that Whisper's deviation from the original Beam Search implementation could be a valid explanation of the behaviour above?

(I am just learning, so might be wrong)

@Nik-Kras 

> the results over different versions of Transformers should've been similar

This is a valid argument that we're trying to honor in general! The exceptions are a) bug fixes b) clear performance upgrades (quality or throughput). The changes for Whisper would fall in clear performance upgrades -- see the [original PR](https://github.com/huggingface/transformers/pull/27658) for WER upgrades.

> Do you think that Whisper's deviation from the original Beam Search implementation could be a valid explanation of the behaviour above?

Certainly! For instance, the modification to generate with a fallback suggested in the paper explicitly asks to regenerate the output in certain conditions. It also overwrites a few parameters in some conditions, including the number of beams for beam search.

@Nik-Kras  I wonder what exactly the "scores", and "sequences_scores" mean. I also wonder if I pass output_logits=True to the generate method, where can I check the specific operation process. For example,if my lable is [1,12,3],and I get the logits, how can I use logits to calculate the CrossEntropy Loss. Thanks!

I believe you are trying to find the source to help with your CrossEntropy issue; this Pull Request is quite different; it focuses on the Beam Search methodology of generating sequences. Read more about it here:
- https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24
- https://discuss.huggingface.co/t/generation-probabilities-how-to-compute-probabilities-of-output-scores-for-gpt2/3175/15?u=patrickvonplaten
- https://huggingface.co/docs/transformers/generation_strategies#beamsearch-multinomial-sampling

> @Nik-Kras I wonder what exactly the "scores", and "sequences_scores" mean.

Below is my personal reasoning
Scores are kind of logits used to select the next token for each beam in the beam search. Sequences_scores is a kind of rating of each generated sequence that helps to select the best one. It is commonly calculated by multiplying the probabilities of each selected token in the beam. So, if the generated sequence consists of low-probability words, there is probably something wrong with the sequence, and it shall not be selected. Sequence Score simplifies your selection by comparing one number to the other.

@Nik-Kras Thanks for the documents. I can get the logits but as for each timestep in beam search, I wonder which index the beam search algorithm picks (Sometimes not the largest one). I want to calculate the CrossEntropy Loss at each timestep as a "metric" and finally get the N-Best results. Or may I change my problems as: how can I get the N-best results with scores? I think it is inappropriate for me to ask questions under this pull request. Would it be better to ask such questions in issues? Thanks！！！

cc @eustlb if you have some bandwidth to take a look at this while @ylacombe is off!

Also, how long is your input audio ?

@ylacombe The audio is 7 seconds long. It is taken from Common Voice 17 and you can find it by ground truth transcription "How is Mozilla going to handle ambiguities like queue and cue?". I did put a link to the audio from HuggingFace, but it seems like it is broken. Trying again [link](https://datasets-server.huggingface.co/cached-assets/NikitaKras/cv_17_test_en_es_fr/--/92f162ad51a63a36d3ed1d4f55d77b2bd9b6b84c/--/default/en/8/audio/audio.mp3?Expires=1725485286&Signature=MEBcgycJ-RRybtkMjMgcXZix6fC5z7Z50OULb7lG3fMah8Q9No3V70fY90-01MKs~HCEuHHqBJi9Ag56-VlU88wjpKvDtn3vdtG5ySk-hymjiXcx~do~fqGGYOjyb10A8BlxdX9s2WgEmRGtEIQGRj0~6Y2zxGBLmZcfHQCGpJZnPkwPRox1oUsN3oKIfWWeJIYf5UIP9evHTo9vahsD-4RroAcern47DDFrXAxjiphc7KD49yRtbvomJdrioO0AHmRlmPjFBD9injgWshJNFyZEkChKvvHbbTAH7Tg4VmcDfILU5I13gdNqSqdr4GUsaJgbprKTndPXmMYY2PEwNw__&Key-Pair-Id=K3EI6M078Z3AC3)

I am a bit distracted by other projects at the moment, but the test should be very easy to write, I will add it soon. 
I am not so confident about [beam_indices](https://github.com/ylacombe/transformers/blob/979f4774f619e43a7c121c49b3c9cdc0b48d687a/src/transformers/generation/utils.py#L279-L280) as I remember there are several bugs / issues around it. It would take some time, so I would leave it for another PR

Hey @Nik-Kras, thanks for circling back on this!
Whisper is used by many users, so it'd be great to have the test added soon! 
If you don't have the bandwidth in the next coming days, let us know and we can supersede the PR to add the test and `beam_indices` - while keeping you as co-author of course!

@ylacombe I will allocate some time early next week, if that is fine with you

@ylacombe All done. It was an easy fix; the most time I spent was setting it up :)

However, I would want to get your attention on a side issue I found - the inconsistency of Whisper's generation over different versions. I explained the comparison above, mentioning specific versions and my observations.
To fix the beam_indicies, I compared the output with version 4.25.1
The type and shape of it is the same, but the data is **significantly different**

I see that `sequences_scores` and `beam_indicies ` are not just computed differently. I strongly believe they are computed wrong. I don't expect Whisper to give 5 identical beams due to the beam search (with identical scores as well). To perform LLM post-correction, I need transcription variants, which is a desired behaviour.

Please have a look at the changes in how the output is generated. I am unsure how to spot a bug there, but I strongly believe there is one.

@ylacombe Here are results of an experiment.
Correct transcription: "How is Mozilla going to handle ambiguities like queue and cue?"
Audio is taken from Common Voice 17 dataset

code
```python
from transformers import AutoProcessor, AutoModelForSpeechSeq2Seq
import torch
import librosa

# Load the processor and model
processor = AutoProcessor.from_pretrained("openai/whisper-tiny")
model = AutoModelForSpeechSeq2Seq.from_pretrained("openai/whisper-tiny")

# Load and preprocess the audio file
audio_path = "audio.mp3"
audio, sr = librosa.load(audio_path, sr=16000)  # Ensure the sample rate is 16kHz

# Preprocess the audio to get the input features
inputs = processor(audio, sampling_rate=16000, return_tensors="pt")

# Generate the transcription using Beam Search with the model
beam_outputs = model.generate(
    inputs["input_features"],
    num_beams=5,  # Number of beams
    num_return_sequences=5,  # Number of hypotheses to return
    early_stopping=True,
    output_scores=True, 
    return_dict_in_generate=True,
)

# Decode the generated transcriptions
hypotheses = [processor.decode(output_ids, skip_special_tokens=True) for output_ids in beam_outputs.sequences]

# Print out the hypotheses
for i, hypothesis in enumerate(hypotheses):
    print(f"Hypothesis {i + 1}: {hypothesis}. Score: {beam_outputs.sequences_scores[i]}")
```

transformers v4.25.1
```
Hypothesis 1:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.4627407491207123
Hypothesis 2:  How is Mozilla going to handle and be with this? Thank you and Q.. Score: -0.4789799749851227
Hypothesis 3:  How is Mozilla going to handle and be with this? Thank you, and cute.. Score: -0.48414239287376404
Hypothesis 4:  How is Mozilla going to handle and be with this? Thank you and cute.. Score: -0.4972183108329773
Hypothesis 5:  How is Mozilla going to handle and be with this? Thank you, and Q.. Score: -0.5054414868354797
```

transformers v4.44.1 + My Fix
```
Hypothesis 1:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495038032531738
Hypothesis 2:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495040416717529
Hypothesis 3:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495036840438843
Hypothesis 4:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495036244392395
Hypothesis 5:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495033264160156
```

transformers v4.44.1 + My Fix + Your Fix
```
Hypothesis 1:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495038032531738
Hypothesis 2:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495040416717529
Hypothesis 3:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495036840438843
Hypothesis 4:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495036244392395
Hypothesis 5:  How is Mozilla going to handle and be with this? Thank you.. Score: -0.5495033264160156
```

There is something else. The core algorithm of beam search seems incorrect. The algorithm should NOT select the same tokens for different beams, that is the point of top_k sampling in the beam search.
I guess another issue should be opened

[Nik-Kras](https://github.com/Nik-Kras), thanks for taking the time to test it. I have the same results on my side. 

I managed to identified why this is happening. It's been introduced in #30984 and is happening because `_expand_variables_for_generation` [artificially expands the batch size to `num_return_sequences`](https://github.com/huggingface/transformers/blob/516ee6adc2a6ac2f4800790cabaad66a1cb4dcf4/src/transformers/models/whisper/generation_whisper.py#L1076-L1084). When it's then passed to [`GenerationMixin.generate`](https://github.com/huggingface/transformers/blob/516ee6adc2a6ac2f4800790cabaad66a1cb4dcf4/src/transformers/models/whisper/generation_whisper.py#L834-L844) and since `batch_size=5`, the model generates `batch_size*num_beams` beams but only keeps the most probable of them for each element of the batch.

In other words, `num_return_sequences` is not compatible with short-form and long-form generation anymore. Now that I've identified the issue, I'll think about how to best solve it. Happy to get your thoughts here!
Also cc @eustlb

PS: don't forget to do `make fixup` to correct your code quality as indicated [here](https://huggingface.co/docs/transformers/en/contributing#create-a-pull-request). Otherwise, your PR won't be merged




Thanks for iterating! LGTM !

Would you like to open another issue for the problem you've identified?

The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_32970). All of your documentation changes will be reflected on that endpoint. The docs are available until 30 days after the last update.

I can still reproduce this bug with the latest transformers.

Indeed, is has not been solved yet. It's mainly due to the fact that the best sequences of beam search are ambiguous when it comes to Whisper's generation, as the underlying implementation does multiple (and possibly) independent calls to GenerationMixin's generate (the method that handles beam search). A heuristic to concatenate and sort sequences after those multiple calls should be found, or we should revert the feature has it's not compatible out of the box with Whisper. 
Nevertheless, it is the next point in the bug-fixing roadmap; thanks for your patience!! 🤗