English · Español

03 — Grammar como FSM: por qué las implementaciones de producción precompilan

La implementación naíf (validar carácter por carácter por cada token candidato, en cada paso) es correcta pero cuadrática. Los productos reales (Outlines, lm-format-enforcer, GBNF de llama.cpp) precompilan el grammar en un autómata finito y precomputan un trie de tokens × estados. El resultado: O(1) por paso. La Fase 30 entiende la teoría y la describe, pero no la implementa.

Esta página explica la estructura de calidad de producción para que Borja pueda leer el código fuente de Outlines después y reconocerlo. Es solo teoría — ningún lab la implementa.

---

El coste ingenuo

La máscara de la Fase 30 se computa por paso iterando sobre el vocabulario y ejecutando el parser JSON carácter a carácter sobre cada token candidato. Coste por paso: O(\(|V| \cdot \bar{L} \cdot \text{paso-de-parser}\)). Con \(|V| = 512\), \(\bar{L} = 3\), paso-de-parser ≈ 10 ops: ~15k ops por paso. Despreciable a pequeña escala.

A escala LLM (\(|V| = 100\text{k}\), \(\bar{L} = 4\), paso-de-parser ≈ 100 ops): 40M ops por paso. A ritmos de decode de ~10 tokens/seg en CPU y ~100/seg en GPU, la construcción de la máscara dominaría. Producción necesita O(1) por paso.

El truco: precomputar la máscara por estado

Observa: en cualquier momento, el estado relevante del grammar es finito (a menudo muy pequeño — para nuestro JSON Schema, ~10 estados). La máscara solo depende del estado actual. Así que:

1. Enumera todos los estados de grammar alcanzables.
2. Para cada estado, para cada token del vocabulario, decide una vez si emitir ese token lleva a un estado legal. Almacena como bit-array mask[state][token].
3. En tiempo de decode, consulta mask[current_state][:] — lectura de memoria O(\(|V|\)), pero una sola — y suma a los logits.
4. Tras emitir, consulta el siguiente estado next_state[current_state][token] — O(1).

Preprocesado total: O(|estados| × \(|V| \cdot \bar{L}\)). Coste total por paso: O(\(|V|\)) (solo la suma de la máscara). El coste por paso ha pasado de O(\(|V| \cdot \bar{L}\)) a O(\(|V|\)) — el factor constante mejora en \(\bar{L}\), pero más importante aún: la lógica del parser desaparece del hot path. Con bit-packing de la máscara, puedes bajarlo aún más.

Enumeración de estados

Para un JSON Schema con n claves, el conjunto de estados es aproximadamente el producto de:

• Posición en el esqueleto JSON: object-open, expecting-key, in-key, after-key, expecting-value, in-value, after-value, comma-or-close.
• Qué claves se han emitido (subconjunto de {key_1, ..., key_n}).
• Qué clave se está valorando actualmente (una de {key_1, ..., key_n}).
• Progreso dentro del valor (depende del tipo del valor: enum, string, integer).

Ingenuamente esto son \(2^n \times n \times (\text{estados de valor})\) estados. Para nuestro esquema de conjugación de 4 claves (verb, tense, person, spanish?) con enums cerrados en tres de las cuatro claves, eso es aproximadamente \(2^4 \times 4 \times 30 \approx 2000\) estados (cota superior laxa). Tratable; para los enums cerrados de §A13 se puede recortar dramáticamente podando. La Fase 30 documenta el conteo; los labs solo construyen la implementación ingenua de validador-por-token.

Para un CFG (Nivel 4), el "estado" es un snapshot de la pila. El espacio de estados puede ser infinito (piensa en expresiones anidadas). Las implementaciones de producción manejan esto vía autómatas de pila + caching cuidadoso de transiciones del tope de la pila — un esfuerzo de implementación sustancial. La Fase 30 se queda en JSON Schema (equivalente a FSM) precisamente para evitar esto.

A nivel de token vs a nivel de carácter: por qué el trie

Un punto sutil. Las transiciones del grammar se definen sobre caracteres; el modelo emite tokens (que son secuencias de bytes). Para tender el puente hay que preguntar, para cada par (estado, token): "¿decodificar este token desde este estado lleva a un nuevo estado legal?".

Las implementaciones de producción construyen un trie a nivel de carácter del vocabulario, y lo intersectan con el FSM del grammar:

Para cada estado s del grammar:
    Para cada rama del trie del vocabulario:
        Recorre la rama un carácter a la vez, mientras avanzas el FSM desde s.
        Si en cualquier momento el FSM rechaza, poda este subárbol del trie (ningún token que empiece por este prefijo es legal en el estado s).
        Si la rama del trie termina en una frontera de token Y el FSM está en un estado legal, marca (s, token) como legal.

Esta poda es lo que hace que la precomputación sea tratable en vocabularios enormes. Sin ella, estarías comprobando \(|V|\) tokens × \(|\text{estados}|\) estados × carácter por carácter — lo que no escala.

La implementación de esto en Outlines vive en su módulo outlines.fsm.guide. Leerlo después de esta fase es un objetivo de ampliación fuertemente recomendado — es elegante y vale la pena el tiempo.

El problema del lookahead

Un asunto más espinoso: tokens que no encajan limpiamente en transiciones del grammar. Supón que el grammar espera "verb": seguido de un valor. El tokenizer podría tener ","tense":" como un solo token. Este token cerraría un par clave-valor y abriría el siguiente. La máscara ingenua dice "¿es esto legal para emitir en este estado?" — pero la pregunta es realmente "¿hay algún camino a través de estados del grammar que este token represente?".

La mayoría de implementaciones de producción manejan esto correctamente recorriendo la expansión a caracteres del token a través del FSM. Algunas con bugs no lo hacen, y obtienes el modo de fallo "el modelo a veces emite un token que localmente parece legal pero globalmente desincroniza el parser". Outlines lo maneja correctamente; algunas versiones tempranas de lm-format-enforcer no.

La implementación ingenua de la Fase 30 lo maneja correctamente porque recorre carácter por carácter por cada token candidato. La versión precomputada de calidad de producción lo maneja correctamente porque poda durante la construcción del trie. De cualquier forma, hay que pensarlo.

Por qué no implementamos esto

Tres razones:

1. Alcance pedagógico. La Fase 30 trata sobre la máscara. Añadir "y construimos un compilador de intersección con trie" duplica la superficie de la fase por una ganancia didáctica marginal.
2. Cobertura de tests. La implementación ingenua es lo suficientemente corta como para verificar por test exhaustivo (cada estado, cada token). La implementación precomputada requiere la misma verificación más "¿la precompilación produjo la tabla correcta?". Doble superficie.
3. Construir antes de abstraer. Según el §0.4 de CLAUDE.md, primero construimos la versión lenta y correcta. Si una fase posterior necesita velocidad (la Fase 33 de serving, quizá), revisitamos y añadimos el cache precomputado entonces. Hasta entonces, lento + correcto gana.

Guía de lectura: qué mirar tras la Fase 30

Si Borja quiere ver esto en código de producción, leer en este orden:

1. outlines.fsm.guide de Outlines — el algoritmo de intersección con trie en Python puro. La implementación de calidad de producción más legible.
2. grammar.cpp de llama.cpp — el parser GBNF y la computación de máscara por paso. Más bajo nivel pero instructivo.
3. La interfaz LogitsProcessor de vLLM — cómo un sistema de serving consume una fuente de máscara. La Fase 33 de este currículo toca esto.
4. El README de lm-format-enforcer — una decisión de diseño diferente (máquina de estados token a token) — contraste útil.

Las notas de esta lectura vivirían en docs/phase-30-structured-generation/notes/outlines-source.md (creado al abrir la fase si Borja hace el objetivo de ampliación).

Un apunte práctico: cachear la máscara

Incluso dentro de la implementación ingenua, puedes cachear: si el estado del grammar no ha cambiado de un paso a otro (el modelo está a mitad de un string, todavía emitiendo caracteres de un valor), la máscara es la misma. Cachea por hash de estado, consulta si hay hit. La Fase 30 puede implementar esto si Borja quiere llevar el lab más lejos; el DoD no lo requiere.

Qué significa "tiempo de compilación" para grammars

La compilación del grammar es por esquema, no por request. Compilas una vez al arrancar el servidor:

mask_table = compile_schema(conjugation_schema, tokenizer)  # pesado: minutos quizá
# ... sirve para siempre ...
for request in stream:
    masks = mask_table.run(generated_tokens)  # barato: O(1) por paso
    sampled = sample(logits, mask=masks.current())

El paso de compilación se amortiza entre todas las requests que comparten el esquema. Para frameworks de agentes donde cada herramienta tiene su propio esquema, esto significa que compilas N tablas al arrancar. Memoria: \(|V| \times |\text{estados por esquema}|\) bits por esquema. Para vocab de 100k × 100 estados, eso son 10 Mbits = 1,25 MB por esquema. Barato.

Hacia dónde conecta esto

• Fase 31 (herramientas/MCP). Los esquemas de argumentos de herramientas son JSON Schemas. conjugate(verb, tense, person), lookup_irregular_verb(verb), lookup_spanish(english_form) todos toman argumentos tipados. El constrained decoding hace que las llamadas a herramientas parseen por construcción. La Fase 31 cablea esto.
• Fase 32 (agentes). El formato de salida del tutor de gramática usa la JSONSchemaMask de la Fase 30. Cada paso que da el agente termina en una llamada de constrained decoding que emite una tripla de conjugación.
• Fase 33 (serving). Un stack de serving real expone response_format como parámetro de API. Implementar esto requiere (a) un punto de extensión LogitsProcessor en el bucle de decodificación, (b) estado de máscara por request. El diseño de la Fase 33 discute esto.

Lo que esta fase NO cubre

• Intersección precompilada token-trie × FSM. Descrito, no codificado. Outlines lo hace; leemos su fuente como objetivo de ampliación.
• Autómatas de pila para CFGs. Los grammars GBNF / lark lo necesitan; fuera de alcance.
• Ajuste fino (fine-tuning) consciente del constrained decoding. Enseñar al modelo a emitir nativamente el esquema para que \(\mathrm{KL}(p_\text{constr} \| p) \to 0\) es una idea de la Fase 28 (LoRA).

---

Hemos terminado con la teoría. A lab/00-regex-mask.md — el calentamiento.