HookAnzuelo One bad token = broken pipeline Un mal token rompe todo el pipeline

{
  "user": "Ada",
  "score": 99,
  "tags": ["math", "logic"]
  "active": true,
}
          

Learning objectives Objetivos de aprendizaje

By the end of this class you will be able to: Al terminar esta clase podrás:

1. DefineDefinir constrained decoding and why it beats post-hoc validation. la decodificación restringida y por qué es mejor que validar después.
2. TraceTrazar how a CFG becomes a byte-level pushdown automaton. cómo una GLC se convierte en un autómata de pila a nivel de bytes.
3. DistinguishDistinguir context-independent from context-dependent tokens. tokens contexto-independientes de los contexto-dependientes.
4. DescribeDescribir the per-step runtime algorithm that produces a vocabulary-sized bitmask in microseconds. el algoritmo por paso que genera una bitmask del tamaño del vocabulario en microsegundos.
5. ExplainExplicar why XGrammar overlaps CPU mask generation with GPU inference. por qué XGrammar solapa la generación de máscara en CPU con la inferencia en GPU.

Roadmap Mapa de ruta

The decode loop, with a mask El ciclo de decodificación, con máscara

for _ in range(max_new_tokens):
    logits = model(input_ids)                   # GPU forward → (seq, |V|)
    logits[-1] += mask                          # mask only the next-token row: {0, -inf}^|V|
    probs    = softmax(logits[-1])
    next_tok = sample(probs)                    # top-k / nucleus / argmax
    input_ids.append(next_tok)
      

Adding the mask before softmax kills illegal tokens (-inf → 0 probability) and preserves the relative ranking of legal ones. The model's preferences are honored within the legal set. Sumar la máscara antes del softmax mata los tokens ilegales (-inf → 0 de probabilidad) y preserva el ranking relativo de los legales. Las preferencias del modelo se respetan dentro del conjunto legal.

The mask is a bit per token La máscara es un bit por token

Why we can't just "run the parser per token" Por qué no podemos solo "correr el parser por token"

Check #1Pregunta #1 Quick check Pregunta rápida

Why a pushdown automaton? ¿Por qué un autómata de pila?

Construction from EBNF Construcción desde EBNF

expr ::= "(" expr ")"
       | "a"
          

Stack trace on input (a) Traza de pila sobre la entrada (a)

One level of recursion. Each fragment is one byte (or one auto-pop after accept). Un nivel de recursión. Cada fragmento es un byte (o un auto-pop tras aceptación).

Parallel stacks Pilas paralelas

• Real grammars are ambiguous — multiple productions match the same prefix. Las gramáticas reales son ambiguas — varias producciones casan con el mismo prefijo.
• The matcher tracks a set of stacks, one per live parse. El matcher mantiene un conjunto de pilas, una por cada parseo vivo.
• A token is accepted if any stack accepts it. Un token se acepta si cualquiera de las pilas lo acepta.
• Masks across stacks are merged by union. Las máscaras se combinan por unión entre pilas.

Check #2Pregunta #2 Quick check Pregunta rápida

Key observation Observación clave

For most tokens, validity depends only on the stack-top node, not the rest of the stack. Para la mayoría de los tokens, la validez depende solo del nodo cima de la pila, no del resto.

• Token stays in current rule, or pushes a child rule → top-only check works. El token sigue en la regla actual o apila una regla hija → basta mirar la cima.
• Token finishes the current rule and pops → need the full stack. El token termina la regla actual y desapila → necesita toda la pila.

How rare is "context-dependent"? ¿Qué tan raros son los "contexto-dependientes"?

Compile time vs. runtime Tiempo de compilación vs. tiempo de ejecución

# Pseudo-code: one runtime step
def fill_next_token_bitmask(stacks):
    mask = empty_bitmask(|V|)
    for top in {s.top for s in stacks}:
        ci_accept, ci_reject, cd_set = cache[top]
        mask |= ci_accept
        for tok in cd_set:
            if pda_advance_ok(stacks, tok):
                mask.set(tok)
    return mask
      

"Adaptive" storage — three options Almacenamiento "adaptativo" — tres opciones

Llama-3.1 + JSON. ~350× smaller. Source: XGrammar paper §3. Llama-3.1 + JSON. ~350× más pequeño. Fuente: paper de XGrammar §3.

Worked example — classify the tokens Ejemplo guiado — clasifica los tokens

list  ::= "[" elems "]"
elems ::= digit ("," digit)*
digit ::= "0" | "1" | "2"
      

You are at the PDA node right after consuming [. Classify: Estás en el nodo del APD justo después de consumir [. Clasifica:

Tokens (left→right): Tokens (izq→der): [ ] 0 1 2 , [0 0] 00 X

• Accepted CI:CI aceptados: 0 1 2 — advance within digit — avanzan dentro de digit
• Rejected CI:CI rechazados: [ ] , [0 00 X — no valid transition from this node — sin transición válida desde este nodo
• Context-dependent:Contexto-dependiente: 0] — second byte triggers a pop into the parent list rule — el segundo byte dispara un pop hacia la regla padre list

Check #3Pregunta #3 Quick check Pregunta rápida

Persistent execution stack Pila de ejecución persistente

We test ~120 CD tokens per step. Naïvely copying the stack each time → quadratic. Probamos ~120 tokens CD por paso. Copiar la pila cada vez de forma ingenua → cuadrático.

TrickTruco (Driscoll, Sarnak, Sleator, Tarjan, 1989): store all stacks as a tree. A "stack" is just a pointer to a tree node; the path to the root reconstructs the stack. (Driscoll, Sarnak, Sleator, Tarjan, 1989): guardar todas las pilas como un árbol. Una "pila" es solo un puntero a un nodo del árbol; el camino a la raíz reconstruye la pila.

The CPU / GPU swimlane Los carriles CPU / GPU

Impact in practice Impacto en la práctica

Default backend in vLLM, SGLang, TensorRT-LLM, and MLC-LLM. Backend por defecto en vLLM, SGLang, TensorRT-LLM y MLC-LLM.

Five takeaways Cinco ideas para llevar

1. Constrained decoding = mask the logits before softmax. 100% structural correctness, no model surgery. Decodificación restringida = enmascarar los logits antes del softmax. 100% de corrección estructural, sin tocar el modelo.
2. A byte-level PDA handles CFGs and BPE tokens cleanly. Un APD a nivel de bytes maneja GLCs y tokens BPE de forma limpia.
3. ~99% of tokens at any PDA node are context-independent and can be cached. El ~99% de los tokens en cualquier nodo del APD son contexto-independientes y pueden cachearse.
4. Adaptive storage (smaller of accepted/rejected) shrinks the cache by ~350×. El almacenamiento adaptativo (el menor entre aceptados/rechazados) reduce la caché ~350×.
5. Persistent stacks + CPU/GPU overlap hide the remaining cost behind the forward pass. Las pilas persistentes + el solapamiento CPU/GPU esconden el costo restante tras el forward.

Exit ticket Ticket de salida

1. Define context-independent vs context-dependent tokens in one sentence each. Define en una oración cada uno: tokens contexto-independientes vs contexto-dependientes.
2. In the example grammar, after consuming [0, is , accepted, rejected, or context-dependent? Justify. En la gramática del ejemplo, tras consumir [0, ¿el token , es aceptado, rechazado o contexto-dependiente? Justifica.
3. In two sentences, why doesn't CPU mask generation add latency to the decode loop in practice? En dos oraciones, ¿por qué la generación de máscara en CPU no añade latencia al ciclo de decodificación en la práctica?

Hand in on an index card on your way out. Entrega en una tarjeta al salir.

References Referencias

• Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models. arXiv:2411.15100
• MLC blog (Nov 2024). Achieving Efficient, Flexible, and Portable Structured Generation with XGrammar. blog.mlc.ai
• XGrammar docs — Workflow: Docs de XGrammar — Workflow: xgrammar.mlc.ai/docs
• GitHub: mlc-ai/xgrammar
• Driscoll, Sarnak, Sleator, Tarjan (1989). Making Data Structures Persistent.

Companion lesson plan: Plan de clase complementario: xgrammar_lesson_plan_90min.md

Meet the tools you'll see Conoce las herramientas que verás

A 30-second intro to each. All four use XGrammar under the hood. Una intro de 30 segundos a cada una. Las cuatro usan XGrammar por debajo.

💡 Tip: any dotted-underlined word like softmax opens a definition. 💡 Tip: cualquier palabra subrayada como softmax abre una definición.

The public API in one slide La API pública en una diapositiva

Four classes for compile time, one for runtime — exactly mirroring Block E. Cuatro clases para compilación, una para ejecución — espejo exacto del bloque E.

Grammar              # WHAT you want    (JSON, JSON schema, regex, EBNF)
TokenizerInfo        # WHO you serve    (vocab + chat template)
GrammarCompiler      # the COMPILE step (builds PDA + adaptive cache)
CompiledGrammar      # the RESULT       (pickleable, reusable)
GrammarMatcher       # the RUNTIME      (accept_token, fill_next_token_bitmask)
      

The easy path: HuggingFace Transformers El camino fácil: HuggingFace Transformers

pip install "xgrammar>=0.1.30" transformers torch pydantic
      

import xgrammar as xgr
import torch
from transformers import AutoModelForCausalLM, AutoTokenizer, AutoConfig

model_name = "meta-llama/Llama-3.2-1B-Instruct"
model = AutoModelForCausalLM.from_pretrained(model_name, device_map="auto")
tokenizer = AutoTokenizer.from_pretrained(model_name)
config = AutoConfig.from_pretrained(model_name)

tokenizer_info = xgr.TokenizerInfo.from_huggingface(tokenizer, vocab_size=config.vocab_size)
compiler = xgr.GrammarCompiler(tokenizer_info)
compiled = compiler.compile_builtin_json_grammar()  # or .compile_json_schema(...)

logits_processor = xgr.contrib.hf.LogitsProcessor(compiled)
out = model.generate(**inputs, max_new_tokens=256, logits_processor=[logits_processor])
print(tokenizer.decode(out[0], skip_special_tokens=True))
      

The mask + apply happens invisibly inside LogitsProcessor. Compile once, reuse forever. El cálculo y la aplicación de la máscara ocurren invisiblemente dentro de LogitsProcessor. Compila una vez, reutiliza siempre.

The transparent path: the manual matcher loop El camino transparente: el loop manual del matcher

Same algorithm as Block E slide 19 — now in real Python. El mismo algoritmo de la diapositiva 19 del bloque E — ahora en Python real.

matcher = xgr.GrammarMatcher(compiled)
token_bitmask = xgr.allocate_token_bitmask(1, tokenizer_info.vocab_size)

while not matcher.is_terminated():
    logits = model(torch.tensor([input_ids], device=model.device)).logits
    matcher.fill_next_token_bitmask(token_bitmask)            # cache lookup + CD check
    xgr.apply_token_bitmask_inplace(logits[0, -1, :], token_bitmask.to(logits.device))
    next_id = torch.argmax(torch.softmax(logits[0, -1, :], dim=-1)).item()
    matcher.accept_token(next_id)                              # advances persistent stack
    input_ids.append(next_id)
      

Production serving: vLLM Serving en producción: vLLM

from vllm import LLM, SamplingParams
from vllm.sampling_params import GuidedDecodingParams

llm = LLM(model="meta-llama/Llama-3.2-1B-Instruct")

guided = GuidedDecodingParams(
    json=schema, backend="xgrammar"
)
sp = SamplingParams(
    temperature=0.7, max_tokens=128,
    guided_decoding=guided,
)
out = llm.generate(["Describe Ada as JSON."], sp)
print(out[0].outputs[0].text)
          

vllm serve meta-llama/Llama-3.2-1B-Instruct \
  --guided-decoding-backend xgrammar
          

from openai import OpenAI
client = OpenAI(base_url="http://localhost:8000/v1",
                api_key="-")

resp = client.chat.completions.create(
    model="meta-llama/Llama-3.2-1B-Instruct",
    messages=[{"role": "user",
               "content": "Ada as JSON."}],
    extra_body={
        "guided_json": schema,
        "guided_decoding_backend": "xgrammar",
    },
)
          

Keys: guided_json, guided_regex, guided_choice, guided_grammar (full EBNF — even SQL). Claves: guided_json, guided_regex, guided_choice, guided_grammar (EBNF completo — hasta SQL).

SGLang

import sglang as sgl, json
from pydantic import BaseModel

class Capital(BaseModel):
    name: str; population: int

llm = sgl.Engine(model_path="meta-llama/Meta-Llama-3.1-8B-Instruct",
                 grammar_backend="xgrammar")  # default anyway

sampling_params = {
    "temperature": 0.1, "top_p": 0.95,
    "json_schema": json.dumps(Capital.model_json_schema()),
    # or: "regex": "(France|England)"
    # or: "ebnf": "root ::= 'yes' | 'no'"
}
outputs = llm.generate(["Capital of France, JSON please."], sampling_params)
print(outputs[0]["text"])
      

MLC-LLM — Apple Silicon & browser MLC-LLM — Apple Silicon y navegador

from mlc_llm import MLCEngine

engine = MLCEngine("HF://mlc-ai/Llama-3.2-1B-Instruct-q4f16_1-MLC")

resp = engine.chat.completions.create(
    messages=[{"role": "user", "content": "Describe Ada as JSON."}],
    response_format={"type": "json_object", "schema": schema},
)
print(resp.choices[0].message.content)
engine.terminate()
      

• Same authors as XGrammar — tightest integration. Mismos autores que XGrammar — la integración más estrecha.
• Only engine in this list that runs in-browser via WebLLM. El único motor de esta lista que corre en el navegador vía WebLLM.
• Pick this for offline-first or mobile apps. Elígelo para apps offline-first o móviles.

Which engine when? ¿Qué motor cuándo?