Constrained Decoding — Ép output theo grammar, JSON luôn valid

Production systems không chỉ cần AI thông minh — chúng cần AI có thể dự đoán được. Khi LLM của bạn chạy API thanh toán và bất chợt sinh ra {"amount": 100, rồi dừng lại, hoặc tự bịa ra trường customer_nane thay vì customer_name, ứng dụng sẽ crash ngay lập tức. Constrained Decoding không hy vọng model "tự giác" đúng, mà vật lý ngăn chặn token không hợp lệ ngay từ khi sinh ra.

Vấn đề

Autoregressive generation là quá trình "cận thị". Model chỉ nhìn context window khi dự đoán token tiếp theo, không có bộ nhớ dài hạn về "tôi đã mở ngoặc nhọn 20 token trước" hay "tôi cần đóng mảng JSON này trước khi kết thúc".

Cách tiếp cận cũ dựa vào prompt engineering ("You MUST output valid JSON") hoặc post-processing (thử lại khi parse lỗi), nhưng đó chỉ là băng dính vá tạm. Ngay cả model 70B vẫn có thể sinh trailing comma, string không đóng ngoặc, hoặc drift sang ngôn ngữ tự nhiên ("Here is the result: {...}") làm parser gãy. Với unconstrained decoding, tỷ lệ lỗi validation vẫn dao động 5-15% ngay cả với top models — con số không thể chấp nhận được cho pipeline tự động.

Ý tưởng cốt lõi

Constrained Decoding lắp "rào chắn" trực tiếp lên vô lăng. Thay vì để model tự do chọn từ 50K token vocabulary, ta động thời che chắn (set probability về -∞) mọi token vi phạm grammar ở từng bước.

Hãy tưởng tượng bạn lái xe qua thành phố (grammar) với một hành khách chỉ đường (LLM). Không có rào chắn, hành khách có thể bảo "rẽ trái" vào ngõ cụt (invalid JSON). Constrained Decoding khóa vô lăng: bạn vẫn có thể điều khiển trong làn hợp lệ, nhưng vô lăng sẽ cứng lại nếu bạn cố lái ra khỏi đường.

Aha moment: LLM vẫn cung cấp ý định ngữ nghĩa ("đi đến thư viện"), trong khi grammar cung cấp mạng lưới đường (chỉ các đường JSON hợp lệ). Model vẫn sáng tạo, nhưng trong biên giới.

Nhưng có một cái bẫy tinh vi mà hầu hết tutorial bỏ qua: Token Misalignment. LLM "nghĩ" bằng subword chunks (ví dụ ["name"] có thể tokenize thành ["nam", "e"] hoặc ["\t", "\"name\""]), trong khi grammar nghı bằng ký tự. Cách tiếp cận ngây thơ ép model sinh từng ký tự một — như ép một người nói lưu loát đánh vần từng chữ. Điều này phá vỡ flow và ép model chọn token perplexity cao.

Cách sửa hiện đại (DOMINO, XGrammar) là cho phép "bridge tokens": nếu grammar cần "name" và vocabulary có sẵn token "name": dưới dạng một token duy nhất, hãy cho phép nó! Đừng ép tách thành từng ký tự. Đó là toàn bộ trick — che chắn token xấu nhưng bảo toàn tokenization tự nhiên của model khi có thể.

Tại sao nó hoạt động

Tại mỗi bước generation, ta duy trì một state machine đại diện cho "cái gì được phép tiếp theo".

1. Compile: Parse JSON Schema hoặc Context-Free Grammar thành Deterministic Finite Automaton (DFA) cho regex, hoặc Pushdown Automaton cho cấu trúc lồng nhau.
2. Intersect: Tại bước t, giao cắt vocabulary của model với tập hợp terminal hợp lệ từ trạng thái hiện tại. Nếu grammar cần dấu " và tokenizer có các token ", \", \n", chỉ những token khớp pattern được giữ lại.
3. Mask: Set logits của token bất hợp pháp về -∞ trước softmax. Model chỉ sample từ tập hợp hợp lệ.
4. Advance: Sinh token, cập nhật state machine (ví dụ chuyển từ "đang đợi key" sang "đang đợi dấu hai chấm"), lặp lại.

Về mặt toán học, thay vì sample từ $\pi(x_t | x_{< t})$, ta sample từ $\pi(x_t | x_{< t}, G)$, với G là ràng buộc grammar. Khối lượng xác suất được phân bổ lại chỉ trên tập con hợp lệ.

Code giả lệnh (Pythonic):

# Giả lệnh logic masking
valid_tokens = grammar.valid_next_tokens(current_state)  # Tập hợp token hợp lệ
logits = model.forward(context)                          # Logits gốc từ LLM
mask = torch.full_like(logits, -inf)                     # Mặc định -inf
mask[valid_tokens] = 0                                   # Chỉ giữ lại cái hợp lệ
probs = softmax(logits + mask)                           # Normalize lại
next_token = sample(probs)

Ý nghĩa thực tế

• Độ tin cậy nhảy vọt: Llama-3-8B đạt 59.6% task accuracy với constrained JSON so với 42.5% khi unconstrained — không phải vì model thông minh hơn, mà vì nó ngừng sinh output lỗi làm parser gãy.
• Nghịch lý tốc độ: Mặc dù thêm logic DFA mỗi bước có vẻ tốn kém, hệ thống như DOMINO lại đạt ~2× speedup so với unconstrained trong một số trường hợp nhờ speculative execution — các đường hợp lệ được verify nhanh hơn là retry lỗi liên tục.
• Ai đang dùng: OpenAI (strict JSON mode), vLLM (guided decoding), SGLang, Guidance, Outlines, llama.cpp (GBNF), XGrammar. Đây đang trở thành tiêu chuẩn cho mọi production API cần structured output.
• Hạn chế:
  • Chỉ đảm bảo syntactic validity, không phải semantic (model vẫn có thể hallucinate {"date": "2025-13-45"} — JSON đúng, lịch sai).
  • Grammar phức tạp có thể làm bùng nổ state space (dù các engine hiện đại xử lý JSON Schema rất tốt).
  • Overhead từ việc intersect mỗi bước, dù kernel C++/CUDA tối ưu đã khiến điều này không đáng kể cho hầu hết use case.

Đào sâu hơn

• Paper gốc: "Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation" (DOMINO, 2024) — arXiv:2403.06988
• Paper: "Flexible and Efficient Grammar-Constrained Decoding" (2025) — arXiv:2502.05111 (17.71× faster preprocessing)

Bài liên quan TroiSinh

Cùng cụm (KV Cache & Inference):

• KV Cache — Đừng tính lại cái đã tính — Hiểu nền tảng autoregressive inference và tại sao phải tối ưu memory
• PagedAttention (vLLM) — Quản lý bộ nhớ ảo cho inference quy mô lớn, giảm waste từ 70% xuống 4%
• Speculative Decoding — Kỹ thuật tăng tốc inference khác bằng model nhỏ draft, model lớn verify

Đọc tiếp:

• Quantization INT8/INT4 — Tối ưu memory footprint cho deployment, giảm 4-8× kích thước model
• Flash Attention — Tối ưu compute attention để giải phóng bandwidth cho KV cache lớn hơn

External

• Blog: Aidan Cooper's practitioner's guide — Structured generation với SGLang và XGrammar
• Blog: Michael Brenndoerfer on token masking — Deep dive vào CFG và finite state machines