Token healing
Author: ahmed-moubtahij
Pull request: yes

# What does this PR do?

Token healing rectifies the token boundary bias in greedy tokenization. It does this by trimming and regrowing the prompt to better align with the model's tokenizer, thus enhancing generation quality. The improvement is clearest with completion models.

Token boundary bias is a silent performance killer that doesn't seem very well known. It has clear impact on completion quality, though I'm not sure where it would fit as a transformers feature.

A more thorough explanation of the problem: [The Art of Prompt Design: Prompt Boundaries and Token Healing | by Scott Lundberg](https://towardsdatascience.com/the-art-of-prompt-design-prompt-boundaries-and-token-healing-3b2448b0be38).

### Motivation

Given a completion prompt with a partial url ending with `:`, the model might have seen the expected completion `://` as a _single_ token in training. However, the prompt's tail token `:` tells it that the next token is not `//`, and so it generates a wrong completion. Such errors compound in auto-regressive language models.


Fixes [#28346](https://github.com/huggingface/transformers/issues/28346)


## 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.
- [x] 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 

Comments:
Circleci tests seem to fail, `tests_flax` for example outputs:

> ImportError while importing test module '/home/circleci/transformers/tests/generation/test_token_healing.py'.
> Hint: make sure your test modules/packages have valid Python names.
> Traceback:
> ../.pyenv/versions/3.8.12/lib/python3.8/importlib/__init__.py:127: in import_module
>     return _bootstrap._gcd_import(name[level:], package, level)
> tests/generation/test_token_healing.py:23: in <module>
>     class TokenHealingTestCase(unittest.TestCase):
> tests/generation/test_token_healing.py:26: in TokenHealingTestCase
>     completion_model = AutoModelForCausalLM.from_pretrained(
> ../.pyenv/versions/3.8.12/lib/python3.8/site-packages/transformers/utils/import_utils.py:1304: in __getattribute__
>     requires_backends(cls, cls._backends)
> ../.pyenv/versions/3.8.12/lib/python3.8/site-packages/transformers/utils/import_utils.py:1292: in requires_backends
>     raise ImportError("".join(failed))
> E   ImportError: 
> E   AutoModelForCausalLM requires the PyTorch library but it was not found in your environment.

I don't know how to specify to the Circleci environment that it should install pytorch. This is my first PR, so I would appreciate some guidance 🙏 

> Thank you for opening this cool PR! I have written a few comments, but they should be easy to solve 🤗

Thank you for your detailed reviews and for taking the time to explain their reasons 🙏 Hopefully, they're all fixed now.

A new headscratcher shows up:
https://app.circleci.com/pipelines/github/huggingface/transformers/83383/workflows/2d8b4ca9-abb5-4be1-a5fc-163e3a0d78d7/jobs/1075117?invite=true#step-115-22

I have `pygtrie` specified here:
https://github.com/huggingface/transformers/blob/ce38ed5b9a4c5c9e456b7910caf6a7ebbec235e2/setup.py#L148
and here:
https://github.com/huggingface/transformers/blob/ce38ed5b9a4c5c9e456b7910caf6a7ebbec235e2/src/transformers/dependency_versions_table.py#L54
I tried adding `pygtrie >= 2.5.0` to `_test_requirements.txt` under `examples/{flax, pytorch, tensorflow}` but that didn't fix it. Maybe there is something I should do at `transformers/src/transformers/utils/import_utils.py`? @gante 

> Thank you for iterating 🤗
> 
> To fix the dependency issue, I believe you need to add `pygtrie` to `extras["torch"]` in `setup.py` (L262). Otherwise, `pygtrie` is not installed -- being in the list where you added the dependency is not enough to install the dependency :)

Thank you for the follow-up! I applied your suggestions. CI is still breaking on the pygtrie import unfortunately. I'll try to think about it some more this weekend.

@Ayenem hope you don't mind, moving a few minor things around to make our CI happy 🤗 

> @Ayenem hope you don't mind, moving a few minor things around to make our CI happy 🤗

Thank you for taking the time!

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

`examples_flax` is failing for reasons unrelated to this PR, I'm going to see if I can open a separate PR to fix it :)

Ok, actually, it has to be fixed in this PR: `pygtrie` has to be added to `/examples/flax/_tests_requirements.txt` :( 

As for the other failures, I recommend the following:
1. Rebase with `main`
2. run `make fixup` in the `transformers` folder
3. commit the resulting changes

If issues persist, I'll dive into the failures :)

uhmmm something has gone wrong, the diff shouldn't be 18k lines long 😅 

> uhmmm something has gone wrong, the diff shouldn't be 18k lines long 😅

Indeed...I did a `git fetch upstream` followed by `git rebase upstream/main` then solved conflicts and pushed. I suppose I misinterpreted what you meant by rebasing with main 😓 
I'll `git revert` and push to undo the last two commits, then just `git rebase main` from there.

@Ayenem That should be it: 
```
git remote add upstream https://github.com/huggingface/transformers.git
git fetch upstream
git rebase upstream/main
(handle merge conflicts)
git push origin your_branch -f
```

possibly something went wrong in the merge conflicts stage?

@Ayenem you're getting the best of CI problems, hehe

> @Ayenem you're getting the best of CI problems, hehe

Lucky me 😄 Rebase should've worked as expected now 🤞 

@Ayenem looking at the test errors, other than sorting the merge conflicts (which should fix most of the problems), the new test needs `@require_auto_gptq`. Alternatively, a smaller model like `gpt2` can be used.

> @Ayenem looking at the test errors, other than sorting the merge conflicts (which should fix most of the problems), the new test needs `@require_auto_gptq`. Alternatively, a smaller model like `gpt2` can be used.

I don't seem to have access to those conflicts locally and I don't have write access for resolving them from github 😕 I don't even know why there are conflicts on files I haven't touched tbh
![image](https://github.com/huggingface/transformers/assets/50707385/6a210a82-48d8-4d61-b263-4c8268bd4b1c)

@Ayenem I have no more suggestions as well. When this happens, it often means something unexpected happened at rebase time. Most (or even all) CI errors we're seeing here are also already solved on `main` 😞 

May I suggest to:
1. Close this PR
2. Update `main` on your fork
3. Create a new branch on your fork, past these changes, and open a new PR?

Again, apologies for all this additional work 🤗