VEGAS: Valid Extraction via Guaranteed Atomic Selection

What happens in Vegas stays in Vegas
The Problem Root
The problem root is a feature, not a bug - tokenizer “universality”. To be able to encode arbitrary sequences tokenizers contain all atomic symbols (or all bytes) in their vocabulary. This way, even the rarest sequences can in the worst case still be represented by one token per char (byte): "hjq" -> ["h", "j", "q"].
This has the side effect that one human readable word can have many possible tokenizations.
TODO: examples Hallo tokenization
Constrained Generation
Many LLM inference frameworks have constrained generation backends, such as guidance, llguidance, xgrammar. The interface for humans to write constraints is in string space, for those familiar with regex we may write constraints such as
The weather today is (sunny|cloudy|stormy).
The constrained generation backends can be seen as intermediate layers that take a constraint in string space, as well as a vocabulary of a tokenizer and translate the constraint into the LLM world. This is done by building a discrete finite automaton (DFA) of the constraint, a system that records all allowed transitions through the constraint.
Logit Extraction
When we are interested in extracting some knowledge from an LLM together with the logits for each answer option, we want to get the LLM into a setting where it can provide some
VEGAS Methodology
Building Regex Constraints
Anything can happen within Vegas
Want to learn how Haidy can make a difference in your practice?
Get in touch now →