Generate: add DeepMind's Speculative sampling in assisted_generation
Author: domgri
Pull request: yes

# What does this PR do?

Implements #27186. Still a draft, work in progress.

Implementation inspired from original [paper](https://arxiv.org/abs/2302.01318) and these[[1](https://github.com/feifeibear/LLMSpeculativeSampling/tree/main)][[2](https://github.com/jaymody/speculative-sampling)] existing implementations.

Next steps:
* Solve raised Todos in code `TODO for speculative decoding:`
* Verify implementation
* Then adhere to possible changes and fix them

Possible changes of PR:
* modifies implementation of `assisted_generation` with `do_sample=True`
* will possibly affect [this](https://huggingface.co/blog/assisted-generation) blog post
* will possibly affect `assisted_generation` documentation



## 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. -> #27186
- [ ] 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?



Comments:
cc @gante 

Hey @domgri 👋 

Thank you for opening the PR! Let me know when you'd like a review 💪 

Sure, absolutely. Sorry for not responding sooner, got some unexpected workload, hope to comeback to finish implementation in a week🤞

Hey, so I gave a couple of tries to finish implementation, although with little to no success 😕. 

A couple of takeaways that might be useful for anyone continuing or trying to work on this implementation:
* [Initial PR](https://github.com/huggingface/transformers/pull/27270/commits/dfc2612d7d270c276b5d2e53f71682aa2c415b3d) might be useful for overall vision, how this feature could be implemented (TODOs how potential places for modifications).
* Sampling cases ([1](https://github.com/huggingface/transformers/pull/27270/files#diff-26783ca033d92b4ce2e01eb691dbf5b05dd972b0cbfdc69fc726cf77a9dcb011R4579-R4581), [2](https://github.com/huggingface/transformers/pull/27270/files#diff-26783ca033d92b4ce2e01eb691dbf5b05dd972b0cbfdc69fc726cf77a9dcb011R4579-R4581)) could be improved with something more sophisticated (and possibly already existing functionalities).
* From second iteration, main model `model_inputs.input_ids` would not match up with `candidate_input_ids` (usually would be shorter and containing only several last tokens from `candidate_input_ids`. I suspect something with cache and/or `**candidate_kwargs` had an effect on that, though, could not  figure out exactly how and what. https://github.com/huggingface/transformers/blob/85fde09c97213bf7e8625f83096bb2a9e183f987/src/transformers/generation/utils.py#L4646
* `tmp_result = tmp_max / tmp_max_sum` was returning array of nan rather instead of 0's. Possibly related to [max_fn](https://github.com/huggingface/transformers/pull/27270/files#diff-26783ca033d92b4ce2e01eb691dbf5b05dd972b0cbfdc69fc726cf77a9dcb011R4568-R4571) implementation that migh be faulty.

I will close this PR since I am out of capacity right now to continue working on it. Feel free to use this PR as an inspiration for actual implementation. Thanks for enthusiastic welcome @amyeroberts @gante, my apologies for not really delivering much value and hope to see someone else step up and contribute more meaningfully 😊.

@domgri no worries! Thank you for giving it a shot 🤗