Speed up `BeamScorer` by 1000%
Author: fzyzcjy
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 #20820

For reasons, explanations, benchmarks, etc, please have a look at the 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#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:

- text models: @ArthurZucker and @younesbelkada
- vision models: @amyeroberts and @NielsRogge
- 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: @stas00, 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:
I am really unfamiliar with huggingface CI, it errors:

```
From github.com:huggingface/transformers
 * [new ref]             refs/pull/21234/head -> origin/pull/21234
Checking out branch
fatal: reference is not a tree: 9fb13c79a72d13cdf0dd59d48762cd7c95370b29

exit status 128
```

However, looking at https://github.com/huggingface/transformers/pull/21234/files, seems I only change one file.

Do not think I can fix this :/

![image](https://user-images.githubusercontent.com/5236035/213868924-d3cec366-ed5f-4543-84fd-a2ba7a8226df.png)


The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_21234). All of your documentation changes will be reflected on that endpoint.

> Before addressing the comments, let's first make sure this change is worth merging :) We won't accept PRs that make the code harder to read (as most vectorized versions of an algorithm are) unless there are clear benefits.
I will need execution time numbers of .generate() from a model at least as big as gpt2, before and after this change, for several number of beams (e.g. 2, 4, 8, and 16). Ideally with and without GPU.

Totally understand your concerns :) I do not have much time now (you know, doing research and maintaining [my open source libs](https://github.com/fzyzcjy)), but will try to squeeze out some time when possible. Anyway, the PR in its current status may already be somehow useful for users who finds out it is too slow, since they can manually copy and tweak the `generate` function to use a custom scorer.

This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the [contributing guidelines](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md) are likely to be ignored.

This speedup is indeed useful.

@KexinFeng Thanks!

FYI we will be introducing fixed-sized caches in text generation soon (akin to our TF and JAX implementations), which will also imply a refactor (vectorization) of beam methods :)

> @gante FYI we will be introducing fixed-sized caches in text generation soon (akin to our TF and JAX implementations), which will also imply a refactor (vectorization) of beam methods :)

Hi, is there any updates? I checked latest BeamScorer and the code does not look very different.

@gante I briefly tested using latest code on `gpt-2` with num_beams=2,4,8,16, and observe 2.2x - 3.3x speedup. Thus, shall I open a new PR for this?

Code (referencing my internal modified code, but it is just a migrated version of this PR and nothing new at all):

<details>

```python
import torch
import transformers
from transformers import AutoModelForCausalLM, AutoTokenizer, GenerationConfig, BeamSearchScorer
import time
import polars as pl
import plotly.express as px
from research_mono.modified_third_party.transformers.generation.utils import generation_mixin_generate
from research_mono.modified_third_party.transformers.generation.beam_search import MyBeamSearchScorer

model = AutoModelForCausalLM.from_pretrained("gpt2")
tokenizer = AutoTokenizer.from_pretrained("gpt2")

model = model.to('cuda')

rows = []

dummy = 0.0

for num_beams in [16, 8, 4, 2]:
    times = {}
    
    for enable_fast in [True, False]:
        input_ids = torch.randint(1000, 2000, (2048 // num_beams, 8)).to(model.device)
        
        beam_search_scorer_cls = [BeamSearchScorer, MyBeamSearchScorer][enable_fast]
        
        generation_config = GenerationConfig(
            max_new_tokens=32,
            num_return_sequences=num_beams,
            pad_token_id=tokenizer.eos_token_id,
            num_beams=num_beams,
            do_sample=False,
        )

        t_start = time.time()
        with torch.autocast(device_type="cuda", dtype=torch.bfloat16):
            for _ in range(10):
                gen_tokens = generation_mixin_generate(model, beam_search_scorer_cls, input_ids=input_ids, generation_config=generation_config)
                dummy += torch.max(gen_tokens).detach().cpu().item()
        t_end = time.time()

        t_delta = t_end - t_start
        times[['time_slow', 'time_fast'][int(enable_fast)]] = t_delta

    row = dict(
        num_beams=num_beams,
        time_ratio=times['time_slow'] / times['time_fast'],
    )
    rows.append(row)

df_all = pl.DataFrame(rows)
display(df_all)

df = df_all.with_row_index()
px.line(df.to_pandas(), x='index', y='time_ratio')
```

</details>

Gives:

![image](https://github.com/huggingface/transformers/assets/5236035/7cae6f26-819d-4e26-ab5b-78e7dca73ef8)