[WIP] Generate: implement prefilling
Author: tom-p-reichel
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 #27449


## 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).
- [ ] 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.

@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: @muellerzr and @pacman100

Integrations:

- deepspeed: HF Trainer/Accelerate: @pacman100
- ray/raytune: @richardliaw, @amogkam
- Big Model Inference: @SunMarc
- quantization (bitsandbytes, autogpt): @SunMarc and @younesbelkada

Documentation: @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: See Models above and tag the person corresponding to the modality of the example.
- TensorFlow: @Rocketknight1

 -->


Comments:
Current issues:
- I forgot to handle an edge case where 1 or 0 length `input_ids` are passed in, fixable by refusing to prefill those sequences.
- Contrastive search broke because it works with past_key_values and expects to expand them itself.
- By passing in caches, I think I have changed the output size of the hidden states or some other part of a ModelOutput, which breaks tests that compare entire ModelOutputs.
- All encoder-decoder models broken-- temporarily resolved by just not prefilling for these models.

More work & doc reading soon.

@tom-p-reichel ping me when you're stuck or when it's ready for review 🤗 

@gante Down to only 6 failing tests in test_torch!

As far as I can tell, all of the remaining failing tests here are due to the fact that prefilling currently changes the length of returned `past_key_values`, attentions, etc. returned from calls to `generate`-- the search functions don't know they're taking a prefilled input and don't make any considerations towards appending prefilled `past_key_values` or attentions to the output they generate. This seems messy to fix because we would have to edit the return values or possibly logic of multiple search algorithms.

Alternatively, maybe prefilling should be opt-in through a keyword arg to generate and simply shouldn't be enabled for those tests?

I'm a graduate student, so I am now facing final exams for a while, so I figure now is a good time to look at this and tell me if I'm on the right track. I could also use advice on addressing the last remaining failed tests.

I also checked that as of now this PR still produces a speedup in the example from my original issue on this topic.

Thanks in advance!

Hey @tom-p-reichel! In general, the PR looks in a good direction.

I'm not fully aware of the details of the problem -- I would have to dig into the code. I might be able to do it next week :)

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.