Support for context-free-grammars (CFG) to constrain model output
Author: jvhoffbauer
Pull request: no
Labels: name: Feature request

### Feature request

It would be nice to constrain the model output with a CFG directly when calling `model.generate`.

This is already done by llama.cpp [grammars](https://github.com/ggerganov/llama.cpp#constrained-output-with-grammars)

An example is in this [repo](https://github.com/r2d4/rellm). 

```
prompt = "ReLLM, the best way to get structured data out of LLMs, is an acronym for "
pattern = regex.compile(r'Re[a-z]+ L[a-z]+ L[a-z]+ M[a-z]+')
output = complete_re(model=model, 
                     prompt=prompt,
                     pattern=pattern)
```
```
> Realized Logistic Logistics Model
```


Is such a parameter on the roadmap for transformers? 

### Motivation

This can be super useful to make model output parseable within architectures that process the output of an LLM using classical methods. E.g. it can be used to make a model generate valid JSON in every case. 

### Your contribution

Happy to build this with CFGs if it helps! 😄 

Comments:
I think something like this is planned cc @gante 🤗 

@gante @ArthurZucker can I help with this somehow? Happy to set up a PR over the weekend! 

Hey @jvhoffbauer 👋 

This feature seems very similar to Microsoft's [`guidance`](https://github.com/guidance-ai/guidance) project, which is compatible with `transformers`. 

Is there some use case that you see `guidance` not solving that this one would solve? :)

Hey @gante 

I think guidance is a very feature-rich framework to query LLMs. It, however, does not provide 

- support for context-free grammars, only regex (that is my understanding so far!)
- beam search
- a lightweight approach to perform inference that can potentially be embedded in training pipelines

Using transformers would be more convenient for my specific use case (generating markdown). Do you think that this justifies integrating it? I also would be curious if others need such a feature. 

@jvhoffbauer you're the first one requesting it :D 

Since this requires non-trivial code (that we have to maintain in the future) and our bandwidth is quite limited at the moment, I'll do my usual pact: if this comment reaches `10` reactions, I'll greenlight its inclusion in `transformers` :) (Whoever does the 10th react, please tag me in a comment!)

That way, we know for sure that there is demand for the feature, and that our team's bandwidth is being put to the best use in favor of the community 🤗 

Makes sense! 

@gante It's even 11 now! 

I am super happy to prepare a PR. Can you provide guidance on how to go about discussions on the interface and architecture? Should I just draft something out or is there a better way? 

+1 for this. It would be very interesting to use BNF as a built-in LogitsProcessor in transformers.

Thanks all for your interest! @gante, leading generation, is on leave for the coming few weeks, but we'll make sure to attend to this issue when he's back. 

@jvhoffbauer, if you're motivated to open a PR with a draft of what you have in mind, please go ahead!

> Thanks all for your interest! @gante, leading generation, is on leave for the coming few weeks, but we'll make sure to attend to this issue when he's back.
> 
> @jvhoffbauer, if you're motivated to open a PR with a draft of what you have in mind, please go ahead!

Super cool! Yes, I will create a draft this week! 

I see that @Saibo-creator already created a draft in #27557 which is exactly what was discussed! 

In addition to that, I am starting a research project in Uni working on syntax-error-free text generation which will explore applications of CFG-based text generation. Potentially describing further use-cases in that area in a community blog post might be interesting! 

@jvhoffbauer  Happy to see that you are also working on research project related to grammar-constrained decoding! I'm also working on a research project related to GCD, would you mind us having a zoom chat at some time? It may spark  new ideas!     :) 
here is my email saibo.geng@epfl.ch

By the way, Microsoft's guidance repo has CFG decoding now, although it doesn't seem like you can easily define the CFG as a text file (i.e. not defining the grammar itself programmatically).

@jvhoffbauer @Saibo-creator: By the way, you might want to review [Picard](https://arxiv.org/abs/2109.05093) and [Synchromesh](https://openreview.net/forum?id=KmtVD97J43e), as they both use CFG decoding to improve the generation of code.

@shermansiu 
Thanks for pointing out the two papers, yes I know both papers. They are important works in this technique 

While this is being worked on, you might also consider using https://github.com/r2d4/parserllm (thank @elo-siema for finding it)

+1 on this, would really love to use it on hugging face models

Hello @AlbertMarashi, the transformers team mentioned they lack the capacity to support this feature, so I've transferred it here https://github.com/epfl-dlab/transformers-CFG

It's functioning quite effectively :)


OpenAI announced support for this. This is a hugely valuable idea.

Hi everyone 👋 

A reminder that we are intentionally not working on this feature, as there is a thriving community of `transformers`-compatible projects 🤗 

Examples:
- [outlines](https://github.com/dottxt-ai/outlines) (the one OpenAI uses)
- [transformers-CFG](https://github.com/epfl-dlab/transformers-CFG)
- [syncode](https://github.com/structuredllm/syncode)

I'll make a draft PR to add `outlines` directly to help maybe!