🚨🚨 Generate: standardize beam search behavior across frameworks
Author: gante
Pull request: yes

# What does this PR do?

Applies the discussion of #20901 into code. In a nutshell, standardizes beam search behavior across all three frameworks through `early_stopping`, keeping PT's behavior untouched for the previously accepted values of `early_stopping`. 

Changes:
1. `early_stopping` was changed from a binary variable (`True` or `False`, defaulting to `False`) to a ternary variable (`True`, `False`, or `"never"`, defaulting to `False`). 
    - `early_stopping=True` means that beam search will stop whenever `num_beam` complete candidates are obtained, ignoring all room for improvement. No changes across all frameworks;
    - `early_stopping=False` means that beam search will use a heuristic to stop. It effectively blocks minor "tail" improvements when `length_penalty` is positive (the default), while saving many beam search iterations. This was already PT's behavior for `early_stopping=False`, and is the new default for TF/FLAX;
    - `early_stopping="never"` means that beam search will only stop when it is mathematically impossible to improve. This was TF/FLAX's behavior for `early_stopping=False` (and is the canonical beam search implementation).
2. As a consequence of 1.: PT users can now run the canonical beam search with `early_stopping="never"`.
3. As a consequence of 1.: TF users will notice a significant speedup if they keep the default generation parameters, while increasing `max_new_tokens`/`max_length`. This is the default case for the Marian models, and what triggered all these changes to begin with (thanks @ydshieh #20853 ).
4. As a consequence of 1.: Flax users will get the same benefits as TF users.

Points 3. and 4. imply that there may be some minor differences in the output of `.generate()` with beam search on TF and FLAX. That difference should be very small (it has been PT's behavior all along, which is also our reference implementation) and will come with significant speedups. Still, being a numerically breaking change, it deserves a visible warning in the title (🚨).

Fixes https://github.com/huggingface/transformers/issues/18149
_______________________________________________________
Slow tests were ran across all 3 frameworks for:
- [x] BART
- [x] GPT2
- [x] T5
- [x] Marian

_______________________________________________________

Speed test script
```py
from transformers import MarianMTModel, MarianTokenizer, TFMarianMTModel
import time

model_name = "Helsinki-NLP/opus-mt-en-ROMANCE"
tokenizer = MarianTokenizer.from_pretrained(model_name)
text_in = ['>>fr<< hello']

model = MarianMTModel.from_pretrained(model_name)
batch = tokenizer(text_in, return_tensors='pt', padding=True)
start = time.time()
translated = model.generate(**batch)
end = time.time()
output = tokenizer.batch_decode(translated, skip_special_tokens=True)
print(output)
print(end - start)

model = TFMarianMTModel.from_pretrained(model_name)
batch = tokenizer(text_in, return_tensors='tf', padding=True)
start = time.time()
translated = model.generate(**batch)
end = time.time()
output = tokenizer.batch_decode(translated, skip_special_tokens=True)
print(output)
print(end - start)
```

Before the PR: same `output`, PT time = `0.084`, TF time = `50.85` (time in seconds, based on my local machine)
After the PR: same `output`, PT time = `0.084`, TF time = `0.701` (time in seconds, based on my local machine)
👉  ~70x faster, same generated text

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

> # What does this PR do?
> Applies the discussion of #20901 into code. In a nutshell, standardizes beam search behavior across all three frameworks through `early_stopping`, keeping PT's behavior untouched for the previously accepted values of `early_stopping`.
> 
> Changes:
> 
> 1. `early_stopping` was changed from a binary variable (`True` or `False`, defaulting to `False`) to a ternary variable (`True`, `False`, or `"never"`, defaulting to `False`).
>    
>    * `early_stopping=True` means that beam search will stop whenever `num_beam` complete candidates are obtained, ignoring all room for improvement. No changes across all frameworks;
>    * `early_stopping=False` means that beam search will use a heuristic to stop. It effectively blocks minor "tail" improvements when `length_penalty` is positive (the default), while saving many beam search iterations. This was already PT's behavior for `early_stopping=False`, and is the new default for TF/FLAX;
>    * `early_stopping="never"` means that beam search will only stop when it is mathematically impossible to improve. This was TF/FLAX's behavior for `early_stopping=False` (and is the canonical beam search implementation).
> 2. As a consequence of 1.: PT users can now run the canonical beam search with `early_stopping="never"`.
> 3. As a consequence of 1.: TF users will notice a significant speedup if they keep the default generation parameters, while increasing `max_new_tokens`/`max_length`. This is the default case for the Marian models, and what triggered all these changes to begin with (thanks @ydshieh [Fix TF generation (especially for `TFMarian`) #20853](https://github.com/huggingface/transformers/pull/20853) ).
> 4. As a consequence of 1.: Flax users will get the same benefits as TF users.
> 
> Points 3. and 4. imply that there may be some minor differences in the output of `.generate()` with beam search on TF and FLAX. That difference should be very small (it has been PT's behavior all along, which is also our reference implementation) and will come with significant speedups. Still, being a numerically breaking change, it deserves a visible warning in the title (🚨).
> 
> Fixes #18149
> 
> Slow tests were ran across all 3 frameworks for:
> 
> * [x]  BART
> * [x]  GPT2
> * [x]  T5
> * [x]  Marian
> 
> Speed test script
> 
> ```python
> from transformers import MarianMTModel, MarianTokenizer, TFMarianMTModel
> import time
> 
> model_name = "Helsinki-NLP/opus-mt-en-ROMANCE"
> tokenizer = MarianTokenizer.from_pretrained(model_name)
> text_in = ['>>fr<< hello']
> 
> model = MarianMTModel.from_pretrained(model_name)
> batch = tokenizer(text_in, return_tensors='pt', padding=True)
> start = time.time()
> translated = model.generate(**batch)
> end = time.time()
> output = tokenizer.batch_decode(translated, skip_special_tokens=True)
> print(output)
> print(end - start)
> 
> model = TFMarianMTModel.from_pretrained(model_name)
> batch = tokenizer(text_in, return_tensors='tf', padding=True)
> start = time.time()
> translated = model.generate(**batch)
> end = time.time()
> output = tokenizer.batch_decode(translated, skip_special_tokens=True)
> print(output)
> print(end - start)
> ```
> 
> Before the PR: same `output`, PT time = `0.084`, TF time = `50.85` (time in seconds, based on my local machine) After the PR: same `output`, PT time = `0.084`, TF time = `0.701` (time in seconds, based on my local machine) 👉 ~70x faster, same generated text

Hi @gante, thanks for solving the issue. It is still a little bit weird though, why does TF generate the same output much slower than PT (as stated: 0.084 vs 0.701)?

Hey @jamie0725 👋 TF eager mode is super slow 🙃 

If you compile the TF model (i.e. do `xla_generate = tf.function(model.generate, jit_compile=True)` then call `generate_output = xla_generate(input_ids, ...)`), you'll see that TF is probably faster than PT, depending on the hardware.