4 ms·

This sounds like an interesting way to ensure accurate quotes: > To accurately generate the exact passages in the given corpus, we employ a trie-based constra

This sounds like an interesting way to ensure accurate quotes: > To accurately generate the exact passages in the given corpus, we employ a trie-based constrained decoding algorithm (Chen et al., 2020; Cao et al., 2021; Lu et al., 2021) in which the generated tokens can be constrained in the dynamic vocabulary. Specifically, instead of generating a token from the entire target vocabulary at each step, we use a prefix tree (trie) to constraint the target vocabulary and ensure that the generated content is within the corpus. During the construction of trie, we remove stop words from the initial token to improve semantic representation of the trie.

mmoskal 3y ago
This kind of low level strategies can be tried on many models using AICI, including the substring one https://github.com/microsoft/aici/blob/main/controllers/aici_abi/src/substring.rs https://github.com/microsoft/aici/blob/main/controllers/aici...
- skybrian 3y ago
  I wonder if anyone has tried giving an LLM a tool that ensures that it copies a quote from a document accurately? It seems like it would be a pretty simple way to avoid some hallucinations.
  - visarga 3y ago
    Yes, it would be good for extractive QA
  - worldsayshi 3y ago
    Do I understand it correctly if the idea here is to insert some logic into the inference loop? I might not have a clear idea how the inference loop works but it sounds like a whole host of solutions could present themselves if it was easy to plug in various types of logic at inference.
    - throwup238 3y ago
      Yes the inference loop provides a list of “logits” every loop which are possible predictions for the next token. LLM parameters like temperature and top_p configure the default logic that selects one of those logits but that logic can be replaced with anything you want. It just has to select the next token and feed it back into inference. Llama.cpp and its downstream users like ollama have long supported using BNF grammars to constrain the output that way.
      - 3abiton 3y ago
        How would this perform compared to RAG?
        potatoman22 3y ago
        I believe you'd use it with RAG. It would ensure the model properly sites the text you feed into it.
threatripper 3y ago
Is that the same method that is used to generate valid JSON by disallowing any token that would cause a syntax error?
- swsieber 3y ago
  This reminded me of that... but I also don't know enough to say 100% for sure.
- skybrian 3y ago
  Yes, it's the same principle. When it's in "quote mode" then it only allows tokens that continue or end a known quote.
mirekrusin 3y ago
Indeed. Use trie constraint for quotes. Use BNF for grammar languages (json, python etc). Projects like llama.cpp/ollama should make it automatic/dynamic, just rely on triple quote sections where you enter those constraint modes automatically. Ie. every time you enter into section starting with "```json" you automatically switch to JSON BNF. Every time you enter into "```json:Foo" you enter JSON BNF + JSON-SCHEMA for Foo object definition. "```python" for python grammar etc. "```quote:documentRef" you enter trie based constraints. "```llm:otherllm" you enter other llm. "```whatever:whatever" you enter whatever you want. If you want just json output you start output with "```json" and that's it. As its all inference time it could be plugin based, ie: 1. character based - given input (from the start of opening "```foo") it returns allowed next characters, or 2. token based - same as above but returns allowed native tokens (not sure how performance would behave here, would it be acceptable?) IMHO also very interesting area would be exploring stable AST representations for programming languages (a'la darklang I believe?) – where variable names are detached from AST itself, ie. differently named functions that otherwise have the same structure have precisely the same AST representation. This would dramatically reduce space to navigate around. ps. [0] in case somebody else is interested [0] https://github.com/ollama/ollama/issues/3019 https://github.com/ollama/ollama/issues/3019
- sroussey 3y ago
  Why have that issue on ollama instead of llama.cpp?
  - mirekrusin 3y ago
    Because it's easier to pull off and experiment with it from ollama (ollama is just go wrapper around llama.cpp). Llama.cpp could have upstream support for it but for them to consider it will have to be ironed out idea. In llama.cpp support may have some different, more low level kind of support, I don't think it makes sense to attach state logic to text input there.
kastnerkyle 3y ago
This same technique, extended can work well for detecting plagiarism from the underlying corpus as well, by tracking a trie of "good" completions in the n-gram sense, and a longer trie of "no-good" completions. This technique was (to my knowledge) first shown in [0], and particularly [1] is a really interesting video discussing these topics around max-order grams even in a Markovian setting. I used this technique a bit in symbolic music generation and was quite pleased with the results, always planned to work it into whatever next models. I think there are a lot of methods from these older Markovian setups that can be employed in the outputs samplers of modern models, as well as the inclusion of structured searches and so on. Parts of deep learning have always focused on structured output search, but historically the LLM style generative setting has not employed these approaches (though I find beam search for generative settings needs tweaking, it usually works pretty well in smaller scale problems for me). [0] Avoiding Plagiarism in Markov Sequence Generation, Papadopoulos et. al. https://axon.cs.byu.edu/Dan/673/papers/papadopoulos.pdf https://axon.cs.byu.edu/Dan/673/papers/papadopoulos.pdf [1] https://www.youtube.com/watch?v=zmDS5_w27bU https://www.youtube.com/watch?v=zmDS5_w27bU

mmoskal 3y ago

This kind of low level strategies can be tried on many models using AICI, including the substring one https://github.com/microsoft/aici/blob/main/controllers/aici_abi/src/substring.rs https://github.com/microsoft/aici/blob/main/controllers/aici...

skybrian 3y ago
I wonder if anyone has tried giving an LLM a tool that ensures that it copies a quote from a document accurately? It seems like it would be a pretty simple way to avoid some hallucinations.
- visarga 3y ago
  Yes, it would be good for extractive QA
- worldsayshi 3y ago
  Do I understand it correctly if the idea here is to insert some logic into the inference loop? I might not have a clear idea how the inference loop works but it sounds like a whole host of solutions could present themselves if it was easy to plug in various types of logic at inference.
  - throwup238 3y ago
    Yes the inference loop provides a list of “logits” every loop which are possible predictions for the next token. LLM parameters like temperature and top_p configure the default logic that selects one of those logits but that logic can be replaced with anything you want. It just has to select the next token and feed it back into inference. Llama.cpp and its downstream users like ollama have long supported using BNF grammars to constrain the output that way.
    - 3abiton 3y ago
      How would this perform compared to RAG?
      - potatoman22 3y ago
        I believe you'd use it with RAG. It would ensure the model properly sites the text you feed into it.

threatripper 3y ago

Is that the same method that is used to generate valid JSON by disallowing any token that would cause a syntax error?

swsieber 3y ago
This reminded me of that... but I also don't know enough to say 100% for sure.
skybrian 3y ago
Yes, it's the same principle. When it's in "quote mode" then it only allows tokens that continue or end a known quote.

mirekrusin 3y ago

Indeed. Use trie constraint for quotes. Use BNF for grammar languages (json, python etc). Projects like llama.cpp/ollama should make it automatic/dynamic, just rely on triple quote sections where you enter those constraint modes automatically. Ie. every time you enter into section starting with "```json" you automatically switch to JSON BNF. Every time you enter into "```json:Foo" you enter JSON BNF + JSON-SCHEMA for Foo object definition. "```python" for python grammar etc. "```quote:documentRef" you enter trie based constraints. "```llm:otherllm" you enter other llm. "```whatever:whatever" you enter whatever you want. If you want just json output you start output with "```json" and that's it. As its all inference time it could be plugin based, ie: 1. character based - given input (from the start of opening "```foo") it returns allowed next characters, or 2. token based - same as above but returns allowed native tokens (not sure how performance would behave here, would it be acceptable?) IMHO also very interesting area would be exploring stable AST representations for programming languages (a'la darklang I believe?) – where variable names are detached from AST itself, ie. differently named functions that otherwise have the same structure have precisely the same AST representation. This would dramatically reduce space to navigate around. ps. [0] in case somebody else is interested [0] https://github.com/ollama/ollama/issues/3019 https://github.com/ollama/ollama/issues/3019

sroussey 3y ago
Why have that issue on ollama instead of llama.cpp?
- mirekrusin 3y ago
  Because it's easier to pull off and experiment with it from ollama (ollama is just go wrapper around llama.cpp). Llama.cpp could have upstream support for it but for them to consider it will have to be ironed out idea. In llama.cpp support may have some different, more low level kind of support, I don't think it makes sense to attach state logic to text input there.

kastnerkyle 3y ago

This same technique, extended can work well for detecting plagiarism from the underlying corpus as well, by tracking a trie of "good" completions in the n-gram sense, and a longer trie of "no-good" completions. This technique was (to my knowledge) first shown in [0], and particularly [1] is a really interesting video discussing these topics around max-order grams even in a Markovian setting. I used this technique a bit in symbolic music generation and was quite pleased with the results, always planned to work it into whatever next models. I think there are a lot of methods from these older Markovian setups that can be employed in the outputs samplers of modern models, as well as the inclusion of structured searches and so on. Parts of deep learning have always focused on structured output search, but historically the LLM style generative setting has not employed these approaches (though I find beam search for generative settings needs tweaking, it usually works pretty well in smaller scale problems for me). [0] Avoiding Plagiarism in Markov Sequence Generation, Papadopoulos et. al. https://axon.cs.byu.edu/Dan/673/papers/papadopoulos.pdf https://axon.cs.byu.edu/Dan/673/papers/papadopoulos.pdf [1] https://www.youtube.com/watch?v=zmDS5_w27bU https://www.youtube.com/watch?v=zmDS5_w27bU