🚨🚨 Fix group beam search
Author: hukuda222
Pull request: yes

# What does this PR do?

Diverse beam search is a method that generates `num_beams//num_beam_groups` sentences for each group independently. However, the current code uses one BeamHypotheses shared by all groups. Therefore, group A will generate two sentences before group B outputs a sentence. So, I created BeamHypotheses for each group so that inferences can be made independently.

Changes are as follows.

inference code:
```python
from transformers import AutoTokenizer, AutoModelForSeq2SeqLM

model = AutoModelForSeq2SeqLM.from_pretrained("facebook/bart-large-xsum")
tokenizer = AutoTokenizer.from_pretrained("facebook/bart-large-xsum")
text = "The dominant sequence transduction models are based on complex recurrent or convolutional neural networks in an encoder-decoder configuration."
outputs = model.generate(
    tokenizer.encode(text, return_tensors="pt", max_length=512),
    num_beam_groups=2,
    num_beams=2,
    diversity_penalty=1000000.0,
    num_return_sequences=2,
)
print("\n".join(tokenizer.batch_decode(outputs, skip_special_tokens=True)))
```

before:
```
A number Of research projects have investigated the role of the brain's encoder and decoder in the control of the encoded sequences.
A number Of research projects have investigated the role of the brain's encoder and decoder in the control of the encoded sequences..
```

after:
```
The study of the activity of the brain's encoders and decoders has revealed a range of different models of how the brain processes information.
A number Of research projects have investigated the role of the brain's encoder and decoder in the control of the encoded sequences.
```
<!--
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 #24369


## 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#start-contributing-pull-requests),
      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.
- [x] 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?
@gante


<!-- 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 and @younesbelkada
- vision models: @amyeroberts
- speech models: @sanchit-gandhi
- graph models: @clefourrier

Library:

- flax: @sanchit-gandhi
- generate: @gante
- pipelines: @Narsil
- tensorflow: @gante and @Rocketknight1
- tokenizers: @ArthurZucker
- trainer: @sgugger

Integrations:

- deepspeed: HF Trainer/Accelerate: @pacman100
- ray/raytune: @richardliaw, @amogkam

Documentation: @sgugger, @stevhliu and @MKhalusova

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: @sgugger
- TensorFlow: @Rocketknight1

 -->



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

## Summary of the problem and corresponding fix (for the core maintainer and our future selves)

### Problem
The generation loop in `group_beam_search` is correct, and it builds `num_beam_groups` distinct groups of sequences. However, the [`beam_scorer.finalize()` step](https://github.com/huggingface/transformers/blob/8e164c5400b7b413c7b8fb32e35132001effc970/src/transformers/generation/utils.py#L3711) was not taking `num_beam_groups` into consideration and the beam selection therein, when appending the last tokens, was free to write across groups. This should not happen at all, and it could entirely flush out the diversity in the different groups (when `num_beam_groups >= num_beams/2`), as we see in the example in the PR header.

### Fix
Two different paths were possible: a) add logic to `finalize` to handle groups correctly; b) treat each group as an independent set of hypotheses. From the [paper](https://arxiv.org/pdf/1610.02424.pdf), we can read "we divide the beam budget B into G groups and greedily optimize each group using beam search", so option b), kindly implemented by @hukuda222, is closer to the reference. 

@gante 
Thanks for the review, CI now passes, and I confirmed that `RUN_SLOW=1 py.test tests/generation/test_utils.py -vv` also passes.

@sgugger [this comment](https://github.com/huggingface/transformers/pull/24407#issuecomment-1605624032) summarizes the problem and the fix

@sgugger the breaking changes here in the generated outputs from `group_beam_search`, which are inevitable due to the bug fix. The method was underperforming (measured in log scores AND beam diversity, which is the point of the method) before these changes.

Since it is a bug fix, there is no need to ensure retro compatibility, correct?