Constrained Beam Search outputs duplication and weird results
Author: boy2000-007man
Pull request: no
Labels: name: bug

### System Info

```shell
- `transformers` version: 4.20.1
- Platform: Windows-10-10.0.19044-SP0
- Python version: 3.8.12
- Huggingface_hub version: 0.4.0
- PyTorch version (GPU?): 1.11.0 (True)
- Tensorflow version (GPU?): 2.8.0 (True)
- Flax version (CPU?/GPU?/TPU?): not installed (NA)
- Jax version: not installed
- JaxLib version: not installed
- Using GPU in script?: no
- Using distributed or parallel set-up in script?: no
```


### Who can help?

@patrickvonplaten

### Information

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

### Tasks

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

### Reproduction

1. duplication case: the outputs should not contain the same sequence.

```python3
>>> from transformers import GPT2LMHeadModel, GPT2Tokenizer

>>> model = GPT2LMHeadModel.from_pretrained("gpt2")
>>> tokenizer = GPT2Tokenizer.from_pretrained("gpt2")

>>> force_word = "are"

>>> force_words_ids = [
>>>     tokenizer([force_word], add_prefix_space=True, add_special_tokens=False).input_ids,
>>> ]

>>> starting_text = ["The soldiers"]

>>> input_ids = tokenizer(starting_text, return_tensors="pt").input_ids

>>> outputs = model.generate(
>>>     input_ids,
>>>     max_new_tokens=3,
>>>     force_words_ids=force_words_ids,
>>>     num_beams=10,
>>>     num_return_sequences=10,
>>>     no_repeat_ngram_size=1,
>>>     remove_invalid_values=True,
>>> )

>>> outputs = outputs[:, input_ids.shape[-1]:]
>>> print("Output:\n" + 100 * '-')
>>> for s in tokenizer.batch_decode(outputs, skip_special_tokens=True):
>>>   print(s)
>>> import collections
>>> print(collections.Counter(map(tuple, outputs.tolist())).most_common(1))
Output:
----------------------------------------------------------------------------------------------------
, who are
, who were
 who are in
, who had
, who are
 who are fighting
 who are still
 who are killed
 who are not
 who are on
[((11, 508, 389), 2)]
```

2. weird case: the output looks weird, repeat progressing constraints with unreasonable tokens

```python3
>>> from transformers import GPT2LMHeadModel, GPT2Tokenizer

>>> model = GPT2LMHeadModel.from_pretrained("gpt2")
>>> tokenizer = GPT2Tokenizer.from_pretrained("gpt2")

>>> force_word = "were not allowed"

>>> force_words_ids = [
>>>     tokenizer([force_word], add_prefix_space=True, add_special_tokens=False).input_ids,
>>> ]

>>> starting_text = ["The soldiers"]

>>> 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=10,
>>>     no_repeat_ngram_size=1,
>>>     remove_invalid_values=True,
>>> )

>>> print("Output:\n" + 100 * '-')
>>> for s in tokenizer.batch_decode(outputs, skip_special_tokens=True):
>>>   print(s)
Output:
----------------------------------------------------------------------------------------------------
The soldiers, who were wearing were not in were not allowed to leave the barracks. The commander of
The soldiers, who were wearing were not in were not allowed to leave the barracks. The military said
The soldiers, who were wearing were not in were not allowed to enter the building. The military said
The soldiers, who were wearing were not in were not allowed to enter the building. The police said
The soldiers, who were wearing were not in were not allowed to leave the barracks. The commander said
The soldiers, who were wearing were not in were not allowed to enter the building. The police had
The soldiers, who were wearing were not in were not allowed to leave the barracks. The army said
The soldiers, who were wearing were not in were not allowed to enter the building. The police then
The soldiers, who were wearing were not in were not allowed to leave the barracks. The commander told
The soldiers, who were wearing were not in were not allowed to enter the building. The police and
```

### Expected behavior

```shell
1. I believe the bug is due to the insufficient initialization of [`track_new["new_seqs"]`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_beam_search.py#L658).
It appears if the top-k hypothesis also advances the constraints.
Then this hypothesis may appear multiple times in the beam as the example output.
The fix is one line in-place.
Updated to `track_new = {"new_seqs": full_hypotheses.tolist(), "new_states": [], "new_indices": [], "new_tokens": [], "new_scores": []}`

2. I believe the bug is due to the incorrect value assignment of [`scores_for_all_vocab`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_utils.py#L3223),
what stores the next **token scores**.
`scores_for_all_vocab` is first passed to [`constrained_beam_scorer.process()`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_utils.py#L3262), and later passed to [`constrained_beam_scorer.step_sentence_constraint()`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_beam_search.py#L596) as `vocab_scores`.
Within its scope, `vocab_scores` is sliced to [`this_batch_token_scores`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_beam_search.py#L654).
`this_batch_token_scores` is finally added to [`track_new["new_scores"]`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_beam_search.py#L686).
However, the derived [`new_scores`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_beam_search.py#L727) is concated with [`sent_beam_scores`](https://github.com/huggingface/transformers/blob/3b00b623b7cad9e1b7c71c97fff24a0286b37045/src/transformers/generation_beam_search.py#L731),
reveal it should represent **beam scores**.
The **token scores** is larger than the expected **beam scores** as ignoring past token scores.
So the unfulfilled hypothesis will advance with an unexpected higher score, and dominate the beam as the example output.
The fix is also straightforward in-place.


# scores_for_all_vocab = next_token_scores_processed.clone()

next_token_scores = next_token_scores_processed + beam_scores[:, None].expand_as(next_token_scores)

scores_for_all_vocab = next_token_scores.clone()
```


Comments: