Terminator strings for generate()
Author: Rocketknight1
Pull request: yes

`generate()` stops when it encounters `eos_token_id`, but there are various circumstances when we want it to stop for other tokens too. The ideal situation would be to allow a set of strings that halts generation, and then include this information with the model, so model authors can set e.g. custom tokens like `
` as halting strings, even when those strings don't have a special token.

The problem with stopping for specific strings rather than tokens is that a string can be tokenized in many different ways, and the tokens that contain a string may also have overhangs on either end: `["?><", "|", "im_", "end", "|", ">>"]`. Since we have to check after each token generated by the model, we want to avoid detokenization and string comparisons, as this will cause a lot of slowdown and prevent us from compiling the generation loop.

This PR adds a `StoppingCriteria` for stop strings. It takes some time to preprocess the stop strings and the tokenizer vocabulary together and builds an embedding matrix containing the information it needs about which tokens can construct each stop string, but once that's done the entire generation-time check can be performed with only tensor operations and static, known shapes.

fixes #28801

Comments:
The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_28932). All of your documentation changes will be reflected on that endpoint. The docs are available until 30 days after the last update.

@Rocketknight1 , hey! I liked the feature, a very useful one I think. Just a couple questions, since I am not sure what was the intended behavior initially

This should be ready for review now @gante @amy! The core code is totally incomprehensible tensor operations - don't stress if you can't follow them, because I wrote them in one caffeine-fuelled afternoon and I also forget what they're doing if I look away for more than 20 minutes. We're kind of trusting in the tests.

The main problem I encountered is I don't have a clean way to get the tokenizer's vocabulary - I'm handling the two common cases of replacing `Ġ` and `▁` with spaces, but there doesn't seem to be any universal method to get the actual string each token will yield. This will probably work for most tokenizers, though, and most stop strings don't contain spaces anyway.

Nice! I'll let @gante review first to confirm it's all aligned with the current logic processors. 

Just skimming my main comment is that we need tests for the criterion's methods, in particular `get_matching_positions`.  

@amyeroberts those are purely internal methods - maybe I should just mark them as private with a leading `_` instead?

@Rocketknight1 Request for tests is to verify the logic rather than them being public or private. `test_stop_string_criteria` is good, but the logic in `get_matching_positions` is quite complex. I'd like for this to be properly covered so that: 
1) we can be certain this method is doing the right thing - not just all the pieces as a whole
2) We can modify safely it if needed. 

@amyeroberts tests for the sub-methods are in!

Quick update here: I refactored the initialization and added a small cache in case users repeatedly call `generate()`. Initialization time is down from 200ms to ~10ms in local testing. I also rewrote the core call so that all stop strings are tested in parallel - this results in a big speedup when we're testing more than 1 stop string.

We may still end up going with @amyeroberts' tokenizer-decode solution after profiling, but I wanted to make sure this method didn't have any obvious performance issues first :fist_raised:. I'll do some testing on Monday!

(also I still have a deep phobia of graph breaks from my XLA era)

:relieved:
![image](https://github.com/huggingface/transformers/assets/12866554/08d6e4fb-8665-4083-952d-a721c18da39f)


@Rocketknight1 Awesome ! Am I right in saying the profiling shows this is faster now? 

You know the next question I'm going to ask is if it correctly handles when tokenizers have different splitting behaviour e.g. preprending with `##` :) 

I'm working on that and _highly confident¹_ that a solution can be found.

¹ Not at all confident

Quick update - `tokenizer.convert_tokens_to_string()` is actually a general method that does what we want, but it has the problem that it strips prefix spaces in tokenizer classes where prepending prefix spaces is the default, and I can't figure out how to make that stop! I think we can use it, but I might need a method where I always prepend with a fixed token before calling it or something to stop that behaviour.

@zucchini-nlp The condition now returns a per-sample vector correctly. Can I be lazy and ask you to add the test for it that @amyeroberts was requesting in #29116 here? If you're too busy, don't worry, I'll get to it!

@Rocketknight1 yeah, I could add it but the PR is already merged. I hope @gante can make it clear and tell where the test goes

@zucchini-nlp you can just add the test to this PR's branch instead! 

cc @amyeroberts @gante this PR now tests per-row stopping conditions from #29116, thanks to @zucchini-nlp. Tests are passing, so the feature looks good! I ran the slow tests locally as well.

cc @amyeroberts this should be ready for re-review!

A quick summary of the changes:
- The old method of hardcoding the removal of prefixes like `##` is gone - it was way too brittle, as you mentioned. I have a new system [here](https://github.com/huggingface/transformers/pull/28932/files#diff-6e63ae0764aa864afd5bae6d512677b99b5240cb98cb210190482bdbb6a85906R322-R341) (you might havve to expand `stopping_criteria.py` to see it) that I think should be robust across all of our tokenizers, unless there's a really weird one I'm missing.
- The cache system has been reworked, and the methods that were factored out of `StopStringCriteria` to allow them to be wrapped with `lru_cache()` have been moved back in. Instead, I use a manual module-level cache, which is keyed by vocabulary and stop strings. I do it this way because the preprocessing stage requires the `tokenizer`, and I didn't want to use that as a key. Therefore, the cache assumes that we won't have two tokenizers with wildly different preprocessing methods but identical vocabularies - this seems safe to me!
- Tests have been reworked for these two changes, and should be passing now
- There's a massive docstring explaining the workings of the class - I can move this somewhere else if it makes more sense there, since it might clog up the docs as-is!
- Example of using stop strings with `generate()` added to docstring

No, thank you for all the patience fixing my horrifically verbose docstrings and incomprehensible tests, lol