🚨🚨🚨 Optimize Top P Sampler and fix edge case
Author: ekagra-ranjan
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 -->

This PR does the following:
1. Fixes #18976
2. Optimizes the Top P sampler Pytorch implementation by removing the need to clone an intermediate tensor and shifting things to right.
3. Add edge case test to PT, TF, FLAX



## 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.
- [ ] 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).
- [x] Did you write any new necessary tests?


## Who can review?

@gante @patrickvonplaten 

<!-- 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._

@gante the proposed PT implementation passes the edge case. I also added the edge case locally and verified that the existing FLAX implementation passes the edge case with no change required in its implementation. 

However, the TF implementation passes the edge case when `use_xla` is True but fails when it is false in my local machine. Hence, I reverted the addition of edge case to TF and FLAX in my PR. It seems that the behavior changes when using xla for TF. 

Can you please confirm if just replacing 0.7 with 0.8 in this test succeeds in your local machine?
https://github.com/huggingface/transformers/blob/a86acb75ad832fd604a1d5b5e5089f299aae5df4/tests/generation/test_generation_tf_logits_process.py#L192

I was investigating on TF's behavior and found this:

This is the input distribution to the test:
https://github.com/huggingface/transformers/blob/a86acb75ad832fd604a1d5b5e5089f299aae5df4/tests/generation/test_generation_tf_logits_process.py#L190

The above goes to TFTopPLogitsWrapper which takes a cumsum here:
https://github.com/huggingface/transformers/blob/a86acb75ad832fd604a1d5b5e5089f299aae5df4/src/transformers/generation_tf_logits_process.py#L173

This `cumulative_probs` gets different value for `use_xla` as True or False in the unittest. 
1. When `use_xla` is True then `cumulative_probs` is [[0.5, 0.8,  0.90000004, 1.],
       [0.29999998, 0.59999996, 0.8499999 , 0.99999994]]
2. When `use_xla` is False then `cumulative_probs` is [[0.5, 0.79999995, 0.9, 1. ],
 [0.3, 0.6, 0.85, 1. ]

This is causing an extra sample to get be sampled in the 1st batch when `use_xla` is False as 0.79999995 is < 0.8.

How should we proceed forward? This issue of changing behavior is not there in PT and FLAX so should we go ahead with just PT and FLAX for this PR and raise this as a separate TF issue in transformers repo?

@ekagra-ranjan we could add an if/else depending on whether `use_xla` is True or not, and set `top_p` to `0.8` or `0.79999995` accordingly. 

However, since this edge case has such low impact in practice, it's okay if we take the simpler path and simply set `top_p` to `0.79999995`. It won't test the edge case with XLA, but at least it is tested once (with eager execution, i.e. with `use_xla=False`).

P.S.: TF's softmax is known to have these minor numerical instabilities.

@gante Thank you for your reviews! Edge case test for FLAX and TF have been added and are passing

@sgugger Sure, done.