English · Español

04 — CFG vs Regex vs JSON Schema: cuándo es cada máscara correcta¶

Tres maneras de restringir lo que un modelo puede emitir: un grammar libre de contexto (CFG), una expresión regular, o una máscara derivada de un JSON Schema. Las tres reducen el espacio de salida, pero no son intercambiables. Aquí derivamos cuál es matemáticamente correcta para cada caso y por qué.

Anclajes: theory/01-jsonmode-vs-grammar.md, theory/02-logit-masks.md, theory/03-grammar-as-dfa.md.

Las tres familias de máscaras¶

Una máscara de decodificación es una función mask: (state) → set[token] que devuelve el conjunto de tokens permitidos en el estado de decodificación actual. Fuera de ese conjunto, los logits se ponen a -inf antes del softmax.

Las tres familias difieren en qué estado siguen:

Familia	Estado	Expresividad	Coste de compilación	Coste en tiempo de ejecución
Regex	índice de estado del FSM `q ∈ Q` (un solo entero)	lenguajes regulares	NFA→DFA: O(2^	R
CFG	pila del parser + regla actual	lenguajes libres de contexto	LL(k) / Earley: O(	G
JSON Schema	estado estructural de JSON parcial (object/array/value) + posición en el esquema	estructuralmente libre de contexto pero tipado	precompilar el autómata JSON al cargar el esquema	O(1)-O(log d) por token, d = profundidad JSON

La taxonomía es real: regex es un subconjunto estricto de CFG, que es un subconjunto estricto de los lenguajes sensibles al contexto. JSON Schema no es libre de contexto en general (la resolución de $ref y los esquemas recursivos necesitan una pila-de-pilas), pero la mayoría de los esquemas de producción sí lo son.

Cuándo cada uno es correcto¶

Caso 1: "el modelo debe emitir un código postal de 5 dígitos"¶

El grammar es [0-9]{5}. Esto es regular — un FSM de 6 estados acepta exactamente este lenguaje.

Regex → ✅ correcto, rápido.
CFG → también correcto pero estás pagando por el sobrecoste de la pila del parser que nunca se usa. Desperdicio.
JSON Schema → solo correcto si el código postal está dentro de un objeto JSON ({"zip": "12345"}). Para una emisión cruda de stream de tokens, JSON Schema es la herramienta equivocada.

Caso 2: "el modelo debe emitir una expresión de paréntesis balanceados"¶

Expr → "(" Expr* ")" | "atom". Esto es libre de contexto, no regular — el lenguaje es "todos los strings balanceados", que el lema de bombeo prueba que un regex no puede coincidir.

Regex → ❌ incorrecto. No hay FSM que acepte paréntesis balanceados anidados arbitrariamente. Un regex limitado a profundidad-d funciona, pero ya no es el mismo lenguaje.
CFG → ✅ correcto.
JSON Schema → herramienta equivocada; no es una estructura JSON.

Caso 3: "el modelo debe emitir un objeto JSON que coincida con `{type: object, properties: {verb: {type: string, enum: [...]}, ...}}`"¶

El lenguaje es "JSON estructuralmente válido conforme al esquema X". Esto es estructuralmente libre de contexto — en cualquier punto el decoder debe saber "¿estoy esperando una clave, un valor, una coma, una llave de cierre?".

Regex → ❌ incorrecto. El balanceo de corchetes de JSON no es regular. Un regex puede validar fragmentos, no el documento entero.
CFG → ✅ correcto, pero escribir el CFG a mano para cada variante de JSON Schema es tedioso.
Máscara derivada de JSON Schema → ✅ correcto y conveniente. El esquema es la estructura; la máscara se genera a partir del esquema. Las librerías de producción (Outlines, lm-format-enforcer, Guidance) toman este camino.

Caso 4: "el modelo debe emitir `<input>verb_form</input>` donde verb_form es una de 600 formas conjugadas"¶

Un regex con 600 alternaciones es correcto pero explota el FSM. Un CFG con un único terminal "verb_form" que referencia una tabla de búsqueda es más limpio. Un JSON Schema con enum: [...600 strings...] funciona si el padre es JSON. Para nuestro tutor de gramática §A13, este es el patrón exacto.

Por qué la expresividad importa incluso para casos no patológicos¶

Un error común en producción: usar un regex cuando necesitabas un CFG. El síntoma es "el modelo emite salida inválida el 5% de las veces" — ese 5% son los casos que el regex no pudo restringir (p. ej., objetos anidados truncados). El regex pasa en el caso típico; falla en el caso de frontera estructural. La máscara CFG lo habría pillado.

A la inversa, un error común de sobre-ingeniería: un CFG completo cuando un regex basta. El enum de 600 strings en el caso 4 de arriba — si cada forma es un string fijo, un regex plano verb_1|verb_2|...|verb_600 es técnicamente regular y la máquina de estados FSM funciona bien. El CFG no te compra nada.

La integración del decoder: misma interfaz de máscara de logits¶

Las tres familias se enchufan en el mismo bucle de decoder por paso. Pseudocódigo (theory/02-logit-masks.md lo deriva formalmente):

def constrained_decode(model, mask_engine, prompt):
    state = mask_engine.start_state()
    tokens = list(tokenize(prompt))
    while not state.is_terminal():
        logits = model.forward(tokens)[-1]          # (vocab_size,)
        allowed = mask_engine.allowed_tokens(state) # set[int]
        logits[~mask_for(allowed)] = -inf
        next_token = sample(logits)
        state = mask_engine.advance(state, next_token)
        tokens.append(next_token)
    return decode(tokens)

Lo único que cambia entre familias de máscaras es mask_engine. El decoder es invariante. Esta es la abstracción que hace que las librerías de constrained decoding sean portables a través de formatos de grammar.

Cuándo cada uno es rápido¶

Para decodificación de Mini-GPT a ~250 tok/s, el presupuesto de construcción de máscara por token es ~4 ms. Mediciones en el i5-8250U de Borja (predichas, por confirmar en lab/03-mask-overhead.md):

Familia de máscara	Coste de máscara por token	Sobrecoste vs decode no enmascarado
FSM regex precompilado	≈ 0,01 ms	< 1%
Parser CFG LL(1)	≈ 0,5 ms	≈ 10%
JSON Schema (FSM precompilado)	≈ 0,05 ms	≈ 1%
JSON Schema (rederivado por token)	≈ 5 ms	≈ 200% (domina)

El eje "precompilado vs por token" importa más que la familia. lm-format-enforcer y Outlines ambos precompilan el esquema una vez al cargar y cachean el FSM. Una implementación ingenua que reevalúa el esquema en cada paso es la implementación equivocada, independientemente de la familia de máscara.

La elección correcta para el tutor de gramática §A13¶

El tutor de gramática de la Fase 32 emite correcciones estructuradas en JSON:

{
  "original": "He goed to school",
  "verb": "go",
  "tense": "past simple",
  "person": "3rd singular",
  "correct_form": "went",
  "spanish": "fue"
}

Este es el hogar natural de JSON Schema. El esquema:

{
  "type": "object",
  "required": ["original", "verb", "tense", "person", "correct_form", "spanish"],
  "properties": {
    "verb":         {"enum": ["work", "play", "walk", "talk", "listen", "watch",
                              "study", "finish", "start", "look", "want", "like",
                              "be", "have", "do", "go", "come", "see", "eat", "write"]},
    "tense":        {"enum": ["infinitive", "present simple", "past simple",
                              "past participle", "simple future"]},
    "person":       {"enum": ["1st singular", "2nd singular", "3rd singular"]},
    "correct_form": {"type": "string", "maxLength": 30},
    "original":     {"type": "string", "maxLength": 200},
    "spanish":      {"type": "string", "maxLength": 30}
  }
}

Las restricciones enum llevan la garantía de alcance microscópico de §A13 dentro de la máscara. El modelo no puede emitir "running" como valor de verb — no está en el enum, la máscara bloquea el prefijo que llevaría allí.

Esta es la razón que carga el peso de por qué la generación estructurada importa para nuestro agente. Sin la máscara de esquema, el tutor de la Fase 32 ocasionalmente alucinaría un verbo fuera de §A13 ("she dranked the water") y perdería el invariante §A13. Con la máscara, eso es mecánicamente imposible.

Resumen de los trade-offs¶

Rasgo	Regex	CFG	JSON Schema
Techo de expresividad	regular	libre de contexto	JSON estructural (efectivamente CFG con $ref)
Mejor para	tokens planos, enums, IDs	DSLs anidadas no-JSON	argumentos de llamada a herramienta, salida estructurada
Coste de compilación	una vez, pequeño	una vez, moderado	una vez, moderado
Coste en tiempo de ejecución (precompilado)	O(1)	O(profundidad de pila del parser)	O(1) por token, O(d) por transición de estado
Ejemplos de librerías	`re`, `flashtext`	grammars de Outlines, Lark, Guidance	lm-format-enforcer, Outlines (modo JSON), grammars de llama.cpp
Modo de fallo	acepta entradas patológicas fuera del fragmento regular del objetivo	sobre-ingeniería para datos planos	herramienta equivocada cuando la salida no es JSON

Citas¶

Willard & Louf, Efficient Guided Generation for Large Language Models (artículo de Outlines), 2023. arXiv:2307.09702 — la pipeline de compilación regex/CFG a FSM.
Beurer-Kellner, Fischer, Vechev, lm-format-enforcer (GitHub) — el autómata de prefijo dirigido por JSON Schema.
Hopcroft, Motwani, Ullman, Introduction to Automata Theory (3ª ed.) — la jerarquía de Chomsky como anclaje formal.

Recapitulación en un párrafo¶

Las máscaras regex son correctas para salidas regulares (códigos postales, enums planos); las máscaras CFG son correctas para salidas libres de contexto (DSLs anidadas, delimitadores balanceados); las máscaras JSON Schema son correctas para salidas de JSON tipado y son la elección natural para argumentos de llamada a herramienta. Las tres se enchufan en el mismo decoder vía una interfaz de máscara de logits; el diferenciador es qué autómata sigue el estado de parseo. Elige por la expresividad necesaria, no por lo que es más fácil de escribir — usar un regex en un lenguaje libre de contexto es una máscara silenciosamente-incorrecta que falla en casos de frontera estructural. Para el tutor de gramática §A13, JSON Schema con restricciones enum lleva el invariante de alcance microscópico al bucle de decodificación de forma mecánica.

Siguiente: lab/02-end-to-end-conjugate.md para cablear la máscara JSON Schema en Mini-GPT.