PhraseConstraints apearing only directly after input or at the end of the generated sentence
### System Info

- `transformers` version: 4.22.0
- Platform: Linux-3.10.0-1160.25.1.el7.x86_64-x86_64-with-glibc2.17
- Python version: 3.9.12
- Huggingface_hub version: 0.9.1
- PyTorch version (GPU?): 1.12.1 (True)
- Tensorflow version (GPU?): not installed (NA)
- Flax version (CPU?/GPU?/TPU?): not installed (NA)
- Jax version: not installed
- JaxLib version: not installed
- Using GPU in script?: Yes
- Using distributed or parallel set-up in script?: No

### Who can help?

@patrickvonplaten @Narsil @cwkeam 

### Information

- [X] The official example scripts
- [ ] My own modified scripts

### Tasks

- [ ] An officially supported task in the `examples` folder (such as GLUE/SQuAD, ...)
- [ ] My own task or dataset (give details below)

### Reproduction

## Overview
In the [PR](https://github.com/huggingface/transformers/pull/15761) that introduced word constraints to the generation function we have an example script --> Example 2: A Mix of Strong Constraint and a Disjunctive Constraint.
Following up you see it slightly modified, but the modifications should not have an impact on the output
- I added the import for `GPT2LMHeadModel` and `GPT2Tokenizer`
- I removed the `.to(torch_device)` for me to run the script
- I redid the assertions, so we can run the script on its own --> removing  `self.....`

```py

from transformers import GPT2LMHeadModel, GPT2Tokenizer

model = GPT2LMHeadModel.from_pretrained("gpt2")
tokenizer = GPT2Tokenizer.from_pretrained("gpt2")

force_word = "scared"
force_flexible = ["scream", "screams", "screaming", "screamed"]

force_words_ids = [
    tokenizer([force_word], add_prefix_space=True, add_special_tokens=False).input_ids,
    tokenizer(force_flexible, add_prefix_space=True, add_special_tokens=False).input_ids,
]

starting_text = ["The soldiers", "The child"]

input_ids = tokenizer(starting_text, return_tensors="pt").input_ids

outputs = model.generate(
    input_ids,
    force_words_ids=force_words_ids,
    num_beams=10,
    num_return_sequences=1,
    no_repeat_ngram_size=1,
    remove_invalid_values=True,
)

generated_text = tokenizer.batch_decode(outputs, skip_special_tokens=True)

assert generated_text[0] == "The soldiers, who were all scared and screaming at each other as they tried to get out of the"
assert generated_text[1] == "The child was taken to a local hospital where she screamed and scared for her life, police said."

```
## ToDo

- [ ] run  the script on `transformers==4.20.1`it works perfectly well
- [ ] run the script on a version above `4.20.1` it will not pass the assertions



### Expected behavior

## Problem

The constraining algorithm seems to be somewhat broken in versions above `4.20.1`
For example on version `4.22`we the script generates the following the outputs:
> _The soldiers, who had been stationed at the base for more than a year before being evacuated **screaming scared**_
>  _The child was taken to a local hospital where he died.\n 'I don't think **screaming scared**_

You can see that the constraints just get added to the end of the generated sentence. In fact, when trying around with constraints, I found out, that they are either placed right after the input:
--> example is made up to show what happens...
> _The soldiers **screaming scared**, who had been stationed at the base for more than a year before being evacuated _
>  _The child **screaming scared** was taken to a local hospital where he died.\n 'I don't think_

or at the end of the generated sentence:
> _The soldiers, who had been stationed at the base for more than a year before being evacuated **screaming scared**_
>  _The child was taken to a local hospital where he died.\n 'I don't think **screaming scared**_

---

- [ ] I expect for the constraints to appear naturally within the generated sentence (like in the testing-script). On versions above `4.20.1` they are just appended in a senseless manner? 

---

- hope that helps
- pls ask me if you have further questions, through I am a beginner myself


cc @gante as well :)<|||||>Hi @JoWohlen 👋  to confirm that I got the problem correctly -- the `example 2` of the PR that introduced the feature, modified to be self-contained, no longer works on `v4.22`. However, up to `v4.20.1`, it worked fine. Is this correct?<|||||>> Hi @JoWohlen 👋 to confirm that I got the problem correctly -- the example 2 of the PR that introduced the feature, modified to be self-contained, no longer works on v4.22. However, up to v4.20.1, it worked fine. Is this correct?

Yes that is correct<|||||>Awesome, thank you for the clarification @JoWohlen 🙌 It helps to pinpoint the issue.

I've added this issue to the list of `.generate()` related issues -- I will let you know when we start looking into it!<|||||>You are welcome, and thanks for the great library!<|||||>By accident I stumbled over what probably is the cause of all this. In https://github.com/huggingface/transformers/pull/17814 a change was made to the constraint-beam-search. This change became active after v4.20.1 . Linked in the PR you can find another PR that adapts the tests to expect the faulty results (as in the issue description)<|||||>Also @boy2000-007man, maybe you have a solution to this? <|||||>@gante more generally should we maybe mark the disjunctive decoding as experimental and state that we don't actively maintain them? It's simply too time-consuming to look into this at the moment IMO<|||||>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.<|||||>Would it be possible to keep this issue open? We are trying to improve output using constrained decoding and this issue prevents that.<|||||>I am also interested to use this constrained text generation functionality which currently doesn't work anymore.<|||||>Reopened (it's still on my generate task queue, which sadly is quite long) :)<|||||>Looking forward to the solution. Btw, even using the version 4.20.1, which doesn’t have this issue, it also has the problem to use two or more words in force_word. 
for example:
force_word = "very scared because"<|||||>@gante  I would like to pick up this. Any pointers on where to start ? <|||||>Hey @raghavanone 👋 Thank you for pitching in!

I suggest opening two debugging sessions, one using v4.20 (where the output for this mode is correct) and the other using `main`. Check the internals of `.generate()` until the variables on the two sides start diverging -- after pinpointing exactly where they start diverging, the problem (and the fix) should become clear :)

This is my go-to strategy for numerical problems in `.generate()`, btw<|||||>Hello everyone,

Is there an update on this? 

> Looking forward to the solution. Btw, even using the version 4.20.1, which doesn’t have this issue, it also has the problem to use two or more words in force_word.
> for example:
> force_word = "very scared because"

Weirdly, it works well when forcing chunks of two words, but fails when forcing chunks of > words. Here is an example to play around with:

```
from transformers import GPT2LMHeadModel, GPT2Tokenizer

model = GPT2LMHeadModel.from_pretrained("gpt2")
tokenizer = GPT2Tokenizer.from_pretrained("gpt2")

words = [["scared of"], ["fire"]]
words = [["scared for their lives"], ["fire"]]

force_words_ids = [tokenizer(w, add_prefix_space=True, add_special_tokens=False).input_ids[0] for w in words]
force_flexible = ["scream", "screams", "screaming", "screamed"]

force_words_ids = [
    force_words_ids,
    tokenizer(force_flexible, add_prefix_space=True, add_special_tokens=False).input_ids,
]

starting_text = ["The soldiers", "The child"]

input_ids = tokenizer(starting_text, return_tensors="pt").input_ids

outputs = model.generate(
    input_ids,
    force_words_ids=force_words_ids,
    num_beams=32,
    num_return_sequences=1,
    no_repeat_ngram_size=1,
    max_length=60,
    remove_invalid_values=True,
)
generated_text = tokenizer.batch_decode(outputs, skip_special_tokens=True)
print(generated_text)
```
when using `words = [["scared of"], ["fire"]]`, the output is very okay. When using `words = [["scared for their lives"], ["fire"]]`, there is this annoying repetition:

`'The soldiers are scared for their life scared for their lives," he said. "They\'re screaming,` 

I think that if this could be fixed for 4.20.1, that would be an awesome next step. 

Additionally, it would be great to have the ability to define different constraints for each hypothesis in the input_ids. 

I suppose this line: https://github.com/huggingface/transformers/blob/v4.20.1/src/transformers/generation_beam_search.py#L477 should be changed so that the right constraint is returned according to the beam_idx `n`.


<|||||>Hi,I would love to work on this issue and fix the issue.<|||||>@SHUBHAPRIYA95 feel free to open a PR and tag me :)<|||||>I don't feel this is a bug. The 4.20.1 works because it inappropriately rewards constraints with `token_score` instead of `beam_score` and causes incomplete constraints repetition.
The constraints appear at EOS, because model constantly prefers `topk_beam + constraint_token` than `topk_beam2append_constraint_token + constraint_token + top1_token`.
I guess model treats adding constraint_token as a mistake and put it at EOS to only suffer one low `token_score` instead of at least two otherwise.
One potential solution deserves a try is to set up [`push_progress`](https://github.com/huggingface/transformers/blob/33aafc26ee68df65c7d9457259fc3d59f79eef4f/src/transformers/generation/beam_search.py#L715).