Adding new parameter to `generate`:  `max_time`.
Author: Narsil
Pull request: yes

Generation by tokens number is sometimes a bit clunky because we don't
know how many tokens are good enough or even how many tokens are in
the payload (for pipelines users for instance). This leads to hard
to understand behavior.

This PR proposes a new argument `max_time` which is a float of seconds
for the allowed time for `generate` to run on.
Ideally combinations of `max_tokens=None`, `max_time=2` could be used to
generate as many tokens as possible within time budget.

NB: Another possible approach consists of passing a callback to `generate`
  putting the caller in charge of the actual decision of when to stop
  generating tokens. It opens the door to 'which args should we pass'
  to this callback. It's hard to imagine other use-cases for this
  early stopping behavior than time (that are not already covered by
  parameters of generate)


# 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 -->


## 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/master/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [ ] 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/master/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/master/docs#writing-source-documentation).
- [x] Did you write any new necessary tests?


## Who can review?

@patrickvonplaten @LysandreJik
@jplu 

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors which may be interested in your PR.

<!-- 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:

- albert, bert, xlm: @LysandreJik
- blenderbot, bart, marian, pegasus, encoderdecoder,  t5: @patrickvonplaten, @patil-suraj
- longformer, reformer, transfoxl, xlnet: @patrickvonplaten
- fsmt: @stas00
- funnel: @sgugger
- gpt2: @patrickvonplaten, @LysandreJik
- rag: @patrickvonplaten, @lhoestq
- tensorflow: @jplu

Library:

- benchmarks: @patrickvonplaten
- deepspeed: @stas00
- ray/raytune: @richardliaw, @amogkam
- text generation: @patrickvonplaten
- tokenizers: @n1t0, @LysandreJik
- trainer: @sgugger
- pipelines: @LysandreJik

Documentation: @sgugger

HF projects:

- nlp datasets: [different repo](https://github.com/huggingface/nlp)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Examples:

- maintained examples (not research project or legacy): @sgugger, @patil-suraj
- research_projects/bert-loses-patience: @JetRunner
- research_projects/distillation: @VictorSanh

 -->

Comments:
Continuing a bit the discussion we had offline for others to chime in.

After quite some discussion and thinking, I see the following problem:

- I don't want to clutter `generate()` with if-statements anymore as it's done a bit in this PR, but rather make use of tools like `LogitsProcessor`. Now @Narsil you gave me some very good arguments to why just adding a `LogitsProcessor` that forces to generate EOS is not good enough (Some models don't have the EOS token & we don't always want to have EOS at the end of the sentence). So I would propose the following solution that we should then also use to deprecate `max_length` from the "lower" generate methods like `greedy_search`, `sample`, ...

Analogs to `LogitsProcessor` and `LogitsProcessorList`, we create a new logit called `StoppingCriteria` and `StoppingCriteriaList` which would look as follows: 

```python
class StoppingCriteriaList(list):
    def __call__(self, input_ids: torch.LongTensor, scores: torch.FloatTensor, **kwargs) -> torch.FloatTensor:
        stopping = False
        for criteria in self:
           stopping = stopping or criteria(input_ids, scores)
        return stopping
```

and a `MaxTimeStopping` class as follows:

```python
class MaxTimeStopping(StoppingCriteria):
    def __init__(self, max_time):
        self.start_time = time.time()
        self.max_time = max_time

    def __call__(self, *args):
        if time.time() - self.start_time > self.max_time:
            return True
       return False
```

The same way we can create a `MaxLengthStopping` class as follows:

```python
class MaxLengthStopping(StoppingCriteria):
    def __init__(self, max_length):
        self.start_time = time.time()
        self.max_length = max_length

    def __call__(self, input_ids, *args):
       if input_ids.shape[-1] > self.max_length:
           return True
       return False
```

Then we can add create a `stopping_criteria` list object in generate along side creating the `logits_processor` list object and pass it to the submodules. In each submodule we would then do something like 

```
if stopping_criteria(input_ids, scores):
    break;
```

I would then also deprecate the `max_length` as an input parameter to `greedy_search` etc and add a `stopping_criteria` list object instead. 

This new approach would open the way for more fancy stopping criteria. E.g. at the moment `max_length` defines the number of total tokens (passed tokens + generated tokens) instead of just the generated tokens which is very hard to change in terms of backwards compatibility. Lots of people have complained about that. With this approach, one could easily make a new `MaxGeneratedTokenStopping` class that would then take over.

Another positive effect of this function is that we can easily test & optimize those classes as we've already seen it for the `LogitsProcessor` classes.

This will require a rather big change, so I'd be very glad if @LysandreJik and @sgugger you can give your opinion here before proceeding.

Thanks for the thoughtful explanation, this makes a lot of sense. I'm very down to continue the modular approach we have with processors, the new `StoppingCriteria` you propose seems like the way to go. It's good that it keeps the extensibility of the generation methods while not complexifying the generate method itself.

Agreed with both of you, this `StoppingCriteria` class seems like a good idea!

@patrickvonplaten @LysandreJik 
Do you mind a second review ?

I think this PR is actually ready.

The TF code (which was my main concern) doesn't seem to use LogitsProcessor nor to be tested, so I figured leaving `max_time` is ok. I could also simply remove it to make sure I don't break things.

> Great! Thanks a lot for tackling this PR!
> 
> I'm quite happy with the design :-)
> 
> Can we:
> 
>     1. Add some docstring for the classes and add those classes to the docs? Give it a new section in `docs/source/internal/generation_utils.rst`

Done, I also added the import statements within `src/transformers/__init__.py`. Is there any other place I should think of ?

> 
>     2. Deprecate the `max_length` function input argument for all `greedy_search`, `beam_search` and update the docstring and tests using the new `StoppingCriteriaList` instead

This is something harder to do because of some other usages of `max_length`. (see other comment). I think it should belong in another PR, because this one is already a bit large. And it would require other kinds of care (regarding performance at least).

What do you think ?

> 
>     3. Change the `class StoppingCriteria` to an abstract class so keep the design as close as possible to the one in `LogitsProcessor...`

Done. shouldn't they actually contain `@abstractmethod` ?

> 
>     4. Delete the functionality for TF. If it would be ok for you, I'd like to just add this functionality for PyTorch for now since TF needs a big refactor before adding more features IMO

Ok.



@Narsil, sorry for being so slow on this one! After thinking a bit more, I think you're right that `max_time` should not be part of the config. One last thing that we'll have to do IMO is to ensure backwards compatibility for the "sub"-generation methods. See comment above. Please let me know, if this doesn't make sense or if I misunderstood something

T5 Also passed, but had a OOM crash on my local machine.
```
================================================================================================================================== test session starts ===================================================================================================================================
platform linux -- Python 3.8.5, pytest-6.1.1, py-1.9.0, pluggy-0.13.1
rootdir: /home/nicolas/src/transformers
plugins: forked-1.3.0, xdist-2.1.0
collected 114 items                                                                                                                                                                                                                                                                      

tests/test_modeling_bart.py ........................................ssss.......................^[[A..............................ssss............. [100%]

============================================================= warnings summary =============================================================
.venv/lib/python3.8/site-packages/tensorflow/python/autograph/utils/testing.py:21
  /home/nicolas/src/transformers/.venv/lib/python3.8/site-packages/tensorflow/python/autograph/utils/testing.py:21: DeprecationWarning: the imp module is deprecated in favour of importlib; see the module's documentation for alternative uses
    import imp

tests/test_modeling_bart.py::BartModelTest::test_torchscript
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
  /home/nicolas/src/transformers/.venv/lib/python3.8/site-packages/torch/nn/functional.py:1897: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
    assert padding_idx < weight.size(0), "Padding_idx must be within num_embeddings"

tests/test_modeling_bart.py::BartModelTest::test_torchscript
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
  /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:213: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
    assert attn_weights.size() == (

tests/test_modeling_bart.py::BartModelTest::test_torchscript
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
  /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:220: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
    assert attention_mask.size() == (

tests/test_modeling_bart.py::BartModelTest::test_torchscript
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
  /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:252: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
    assert attn_output.size() == (

tests/test_modeling_bart.py::BartModelTest::test_torchscript
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
  /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:856: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
    if input_shape[-1] > 1:

-- Docs: https://docs.pytest.org/en/stable/warnings.html
========================================= 106 passed, 8 skipped, 28 warnings in 562.15s (0:09:22) ==========================================
```

> T5 Also passed, but had a OOM crash on my local machine.
> 
> ```
> ================================================================================================================================== test session starts ===================================================================================================================================
> platform linux -- Python 3.8.5, pytest-6.1.1, py-1.9.0, pluggy-0.13.1
> rootdir: /home/nicolas/src/transformers
> plugins: forked-1.3.0, xdist-2.1.0
> collected 114 items                                                                                                                                                                                                                                                                      
> 
> tests/test_modeling_bart.py ........................................ssss.......................^[[A..............................ssss............. [100%]
> 
> ============================================================= warnings summary =============================================================
> .venv/lib/python3.8/site-packages/tensorflow/python/autograph/utils/testing.py:21
>   /home/nicolas/src/transformers/.venv/lib/python3.8/site-packages/tensorflow/python/autograph/utils/testing.py:21: DeprecationWarning: the imp module is deprecated in favour of importlib; see the module's documentation for alternative uses
>     import imp
> 
> tests/test_modeling_bart.py::BartModelTest::test_torchscript
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
>   /home/nicolas/src/transformers/.venv/lib/python3.8/site-packages/torch/nn/functional.py:1897: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
>     assert padding_idx < weight.size(0), "Padding_idx must be within num_embeddings"
> 
> tests/test_modeling_bart.py::BartModelTest::test_torchscript
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
>   /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:213: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
>     assert attn_weights.size() == (
> 
> tests/test_modeling_bart.py::BartModelTest::test_torchscript
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
>   /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:220: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
>     assert attention_mask.size() == (
> 
> tests/test_modeling_bart.py::BartModelTest::test_torchscript
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
>   /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:252: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
>     assert attn_output.size() == (
> 
> tests/test_modeling_bart.py::BartModelTest::test_torchscript
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartModelTest::test_torchscript_output_hidden_state
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_attentions
> tests/test_modeling_bart.py::BartStandaloneDecoderModelTest::test_torchscript_output_hidden_state
>   /home/nicolas/src/transformers/src/transformers/models/bart/modeling_bart.py:856: TracerWarning: Converting a tensor to a Python boolean might cause the trace to be incorrect. We can't record the data flow of Python values, so this value will be treated as a constant in the future. This means that the trace might not generalize to other inputs!
>     if input_shape[-1] > 1:
> 
> -- Docs: https://docs.pytest.org/en/stable/warnings.html
> ========================================= 106 passed, 8 skipped, 28 warnings in 562.15s (0:09:22) ==========================================
> ```

Ok for me then! If T5 tests pass this is good enough.