💻 computer science

GRID: Grammar-Railed Decoding for Enterprise SQL Generation

O artigo apresenta o GRID, um mecanismo de decodificação com restrição gramatical que aproveita estados de analisador LALR(1) e caminhadas em trie de nível de byte para gerar SQL sintaticamente válido e em conformidade com políticas, com garantias comprováveis, custos de decodificação quase constantes e trilhas de auditoria à prova de adulteração, melhorando significativamente a precisão de execução em ambientes corporativos.

Autores originais: Mohsen Arjmandi

Publicado 2026-07-15

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Mohsen Arjmandi

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem um amigo robô super inteligente (um Modelo de Linguagem Grande) que adora escrever instruções de computador chamadas SQL. Este robô é ótimo em adivinhar a próxima palavra de uma frase, mas também é um pouco um sonhador caótico. Em uma conversa normal, se o robô disser algo bobo como "DELETE ALL THE TABLES" quando deveria apenas "SELECT", ninguém se machuca. Mas esse erro em um banco ou em um hospital é um desastre.

Apresentamos o GRID (Grammar-Railed Decoding — Decodificação Guiada por Gramática). Pense no GRID não como um professor que grita "Não!" depois que o robô comete um erro, mas como um trilho de trem mágico no qual o robô deve percorrer. O robô ainda pode ser criativo, mas ele fisicamente não consegue tirar o trem dos trilhos. Se o trilho não existir, o robô nem consegue pensar naquela palavra.

O Trilho de Trem Mágico

Normalmente, quando você pede a um robô para escrever código, você o deixa adivinhar a próxima palavra e, depois, verifica se a frase inteira faz sentido. Se não fizer, você a deleta e tenta novamente. Isso é lento e arriscado.

O GRID muda o jogo. Em vez de verificar a frase inteira ao final, ele verifica cada um dos passos antes mesmo de o robô ter permissão para escolher uma palavra. Ele faz isso olhando para um "mapa" da gramática (as regras da linguagem) e para a posição atual do robô nesse mapa.

O Problema com Mapas Antigos: Métodos anteriores tentavam memorizar cada frase possível que o robô poderia escrever. O artigo explica que isso é impossível. Se você tentasse listar todas as frases válidas de até um comprimento moderado, a lista seria maior que o número de átomos em todo o universo.
A Solução do GRID: Em vez de memorizar frases, o GRID memoriza configurações. Imagine o robô como um trilheiro. Os métodos antigos tentavam memorizar cada caminho possível que o trilheiro poderia seguir. O GRID apenas verifica: "O trilheiro está atualmente em uma parte válida da trilha?" Se sim, o robô pode continuar caminhando. Se não, o caminho está bloqueado. Isso mantém o sistema rápido, mesmo para frases muito longas.

As Zonas de "Proibido" (Política e Regras)

Em uma grande empresa, pessoas diferentes têm regras diferentes. Um funcionário júnior pode ter permissão apenas para olhar os dados (SELECT), enquanto um gerente pode deletá-los (DELETE).

O GRID constrói essas regras diretamente nos trilhos do trem.

Trilhos Baseados em Funções: Se o robô estiver atuando como um "Funcionário Júnior", os trilhos para "DELETE" ou "UPDATE" simplesmente não existem. O robô não consegue sequer imaginá-los. Não é que o robô esteja sendo instruído com um "Não, não faça isso"; é que a palavra "DELETE" é invisível para ele nesse modo.
Trilhos de Esquema: O robô também sabe exatamente quais tabelas e colunas existem no banco de dados. Se uma tabela não existe, o trilho para ela sumiu. O robô não pode acidentalmente digitar um nome de tabela falso.

O artigo é muito honesto sobre o que este trilho mágico não pode fazer. Ele prova que o trilho não pode impedir o robô de escolher a coluna errada para uma linha específica (como escolher "salário" quando deveria ser "nome"), porque essa decisão depende de um contexto que só aparece depraís do término da frase. Para esses casos complicados, o GRID usa um "verificador" que olha para a frase finalizada e a corrige, se necessário.

Velocidade e Segurança: O Custo "Plano"

Uma das maiores preocupações com essas verificações de segurança é a velocidade. Geralmente, quanto mais longa a frase, mais lenta se torna a verificação de segurança. O artigo chama isso de "Requisito R".

O GRID promete algo especial: o custo de verificação permanece constante (flat).

Quer o robô esteja escrevendo a 5ª palavra ou a 16.000ª palavra, o tempo para verificar se a próxima palavra é permitida é aproximadamente o mesmo.
Os autores mediram isso em computadores poderosos (GPUs H100). Eles descobriram que, para cada token (parte de uma palavra), a verificação leva entre 3,6 e 6,7 microssegundos (isso é milionésimos de segundo) quando o sistema está aquecido e pronto.
Mesmo quando o robô encontra um novo banco de dados que nunca viu antes, o sistema lida com isso de forma graciosa. As primeiras palavras podem demorar um pouco mais (cerca de 27,3 milissegundos para configurar), mas uma vez feito isso, ele roda em velocidade total. Crucialmente, esse tempo de configuração não atrasa os outros robôs trabalhando ao mesmo tempo.

O Recibo da "Caixa Preta" (Trilha de Auditoria)

Em um banco, você precisa saber exatamente o que aconteceu. Se um robô tomou uma decisão, você precisa ser capaz de reproduzi-la mais tarde para provar que foi segura.

O GRID mantém uma trilha de auditoria encadeada por hash. Imagine um recibo digital para cada única palavra que o robô tem permissão para dizer. Este recibo é encadeado como uma corrente de clipes de papel. Se alguém tentar mudar uma única palavra no passado, toda a corrente se quebra e você saberá imediatamente que o registro foi adulterado. O artigo mostra que eles podem reproduzir 1.000 gerações dessas decisões e obter exatamente o mesmo resultado todas as vezes, com 100% de detecção de adulteração.

O Quão Bem Funciona?

O artigo não apenas afirma que funciona; eles testaram em dados reais (o conjunto de dados Spider, que possui mais de 1.000 perguntas complexas).

Para robôs menores (0,5B de parâmetros): Usar o GRID melhorou o número de respostas corretas em 13 pontos percentuais. O principal motivo? O robô parou de cometer erros bobos de gramática.
Para robôs maiores e mais inteligentes (7B de parâmetros): A verificação gramatical sozinha ajudou um pouco (cerca de +1 ponto), mas quando adicionaram o "verificador" para corrigir os erros complicados de coluna, a taxa de sucesso saltou para 94,5%.

A Verdade Honesta

Os autores são muito cuidadosos para não prometer demais. Eles admitem algumas coisas:

Não é perfeito para todas as linguagens: Funciona melhor para linguagens que seguem regras específicas (LALR(1)), como o SQL. Ainda não consegue lidar com todos os tipos de gramática do mundo.
Muda o "sabor": Ao forçar o robô a permanecer nos trilhos, isso altera ligeiramente a maneira como o robô escolhe as palavras. O artigo mediu isso e descobriu que, para robôs muito pequenos, essa mudança importa, mas para robôs grandes e inteligentes, o benefício de estar correto supera a leve mudança de estilo.
Inícios a Frio (Cold Starts): Quando um banco de dados totalmente novo chega, há uma lentidão pequena e temporária (cerca de 34% por um breve momento) enquanto o sistema constrói os novos trilhos. Mas isso só acontece uma vez por novo banco de dados, e não interrompe o trabalho dos outros robôs.

Em resumo, o GRID é como construir um sistema de trem super seguro e de alta velocidade para a IA. Ele não apenas diz à IA "não bata"; ele constrói os trilhos de modo que bater seja fisicamente impossível, mantendo o trem rápido o suficiente para ser útil no mundo real.

Resumo Técnico: GRID (Grammar-Railed Decoding for Enterprise SQL)

1. Declaração do Problema

O artigo aborda a lacuna entre LLMs gerando texto "plausível" e os requisitos rigorosos da geração de SQL empresarial. Em implantações de CRUD/RBAC (Controle de Acesso Baseado em Função) corporativas, os outputs devem ser sintaticamente válidos, aderir a políticas por função e por esquema (schema) e fornecer garantias comprováveis em vez de resultados baseados em "melhor esforço". Os autores identificam seis desafios críticos que as soluções existentes não conseguem resolver simultaneamente:

Validade e Política Conjuntas: Os outputs devem fazer o parse sob o dialeto SQL específico enquanto aplicam estritamente restrições de verbos por função e vocabulário específico de esquema (tabelas/colunas reais) por construção, não via filtragem pós-hoc.
Garantias Comprováveis: Os sistemas devem oferecer teoremas formais de correção (soundness — nunca emitir tokens inválidos), completude (nunca bloquear continuações válidas) e terminação, verificados por testes específicos.
Custo por Token Constante (Requisito R): O custo do "trilho de segurança" (masking) deve ser amortizado em $O(1)$ por token, independente do comprimento de geração $n$ . Sistemas existentes frequentemente sofrem com custos que crescem linear ou quadraticamente com o comprimento do contexto.
Trilha de Auditoria Replicável: A conformidade exige um registro encadeado por hash e bit-idêntico de cada decisão de permissão/bloqueio para responder "o que foi permitido e por quê" a posteriori.
Servir a Realidade: Ambientes de produção envolvem requisições heterogêneas em lote. O sistema deve lidar com chegadas de "esquema frio" (novos esquemas não vistos anteriormente) sem travar requisições "quentes" co-processadas ou substituir máscaras aproximadas.
Limites Honestos: O sistema deve reconhecer explicitamente o que não pode ser imposto por uma máscara context-free da esquerda para a direita (especificamente RBAC de nível de coluna) e fornecer mecanismos para lidar com esse resíduo.

2. Metodologia: Decodificação com Trilhos de Gramática (Grammar-Railed Decoding)

O GRID introduz uma arquitetura inovadora onde tudo é indexado por configurações de parser em vez de sequências de tokens.

Ideia Arquitetural Central

Em vez de pré-computar tabelas de validade sobre sequências de tokens (que escalam combinatoriamente), o GRID indexa todos os masks, entradas de cache e registros de auditoria na configuração do parser. Uma configuração $\kappa$ é definida pelo par $(\sigma, \rho)$ :

$\sigma$ : A pilha do parser LALR(1).
$\rho$ : O estado de varredura do lexer sobre o léxico parcial atual (bytes remanescentes).

Esta configuração determina unicamente o conjunto de prefixos viáveis (continuações que podem levar a uma sentença válida).

Componentes Principais

Oráculo de Prefixo Viável: O próprio parser incremental LALR(1) atua como o oráculo. Ao simular a cadeia de redução em uma pilha virtual, o sistema determina o conjunto de terminais permitidos. Isso evita o "impasse de semântica de aceitação" onde prefixos de um único token podem ser rejeitados se o sistema apenas verificasse sentenças completas.
Ponte Token-Terminal: Como os tokens de LLM (strings de bytes) não se alinham com os léxicos da gramática, o GRID utiliza uma caminhada de trie em nível de byte.
- Tokens Independentes de Contexto (CI): Tokens que se resolvem dentro do léxico atual ou terminam exatamente em uma fronteira de terminal. Estes são cacheáveis.
- Tokens Dependentes de Contexto (CD): Tokens que cruzam uma fronteira de terminal (ex: completando uma palavra-chave e iniciando outra). Estes nunca são cacheados; eles são verificados contra a pilha viva em cada etapa para garantir a correção.
Compilação de Política:
- Projeções de Função (L2): Subconjunto das produções da gramática (ex: removendo verbos DELETE) e elimina símbolos inúteis.
- Léxicos de Esquema (L3): Restringe terminais de identificadores para permitir listas (allow-lists) derivadas do catálogo do banco de dados.
- Regra de Composição de Identificador: Em posições de identificador, a máscara é derivada estritamente da interseção da trie do token e da trie do léxico do esquema, impedindo que entradas de cache genéricas admitam identificadores proibidos.
Estratégia de Cache (OBL-KEY1): Um cache de escrita reversa de dois níveis (T1 para gramáticas específicas, T2 para famílias de gramática compartilhadas) usa chaves derivadas da configuração. O sistema impõe um "refinamento estilo Myhill–Nerode" onde quaisquer duas configurações que compartilham uma chave devem produzir máscaras de bytes idênticas.
Cadeia de Auditoria: Cada etapa anexa um registro (passo, hash de configuração, ID de entrada de máscara, token, contagem de bloqueio) encadeado via BLAKE2b. Isso permite a replicação bit-idêntica de gerações contra artefatos arquivados.

Implementação do Sistema

Kernels em Rust: O caminho crítico (trie walk, vereditos CD, avanço LALR, preenchimento de bitmask) é implementado em Rust para minimizar a latência e liberar o GIL do Python.
Contrato de Serviço (vLLM): O sistema sobrepõe o cálculo da máscara no CPU com o forward pass da GPU. Se a máscara de uma requisição de esquema frio não estiver pronta, ela é adiada por uma rodada, garantindo que requisições quentes co-processadas nunca sejam travadas.
Reparo Guiado por Checker: Para o resíduo que as máscaras não podem impor (RBAC de nível de coluna), o sistema utiliza um verificador semântico pós-parse. Se uma violação for detectada, o sistema pode guiar uma passagem de reparo para corrigir a query.

3. Principais Contribuições

Framework Formal: Um framework de decodificação de restrição indexado por configuração usando um parser incremental LALR(1) como oráculo de prefixo viável, com uma ponte de nível de byte token-para-terminal e uma divisão entre contexto-independente/contexto-dependente.
Garantias Comprováveis: Quatro garantias (Correção, Completude, Terminação, Custo Flat) declaradas como proposições com precondições explícitas, acompanhadas de testes específicos para verificação.
Realização de Sistema: Um sistema pronto para produção (kernels v4–v7) apresentando um pipeline de gramática, kernels em Rust, um cache de dois níveis e um log de auditoria encadeado por hash.
Recorde de Benchmark: Avaliação abrangente incluindo latência por token, medições de inclinação do Requisito R, MaskBench (JSON Schema), precisão de execução Spider e recordes de serviço vLLM de ponta a ponta.

4. Resultados

Latência: Em um executor H100 SXM5, o GRID alcança uma latência mediana de máscara por token de 3,6–6,7 µs (p50) e 80–109 µs (p90), superando o llguidance e o XGrammar em p50 e p90 em ambos os tokenizadores gpt2 e Qwen. O llguidance mantém a cauda p99 mais plana.
Requisito R (Custo Flat): Em $n=16.000$ tokens, a inclinação do custo por token é efetivamente zero ( $\approx 0$ ), confirmando um custo amortizado de $O(1)$ . Em contraste, versões anteriores de orientação mostraram crescimento quadrático.
Precisão de Execução (Spider):
- Modelo de 0.5B: A decodificação restrita sozinha rende +13 pontos de precisão de execução (EX) sobre a geração sem restrições (29,0% vs 16,0%).
- Modelo de 7B: A máscara sozinha fornece ~+1 ponto. No entanto, adicionar uma passagem de reparo guiada por checker para violações de nível de coluna eleva a execução para 94,5% (EX +2,3 sobre o não restrito).
Overhead de Serviço: Sob vLLM com tamanho de lote 32, o overhead é de +1,51% de tempo por token de saída.
Tratamento de Cold-Start: Um esquema novo incurre em um tempo de especialização de ~27,3 ms e latência de primeiro token de ~0,7 ms. Embora isso cause uma redução temporária de ~34% na velocidade para requisições co-processadas quentes durante a janela de especialização (devido à contenção de largura de banda de CPU/memória), as requisições quentes nunca são travadas, e a requisição nova roda a 1,00× da velocidade quente após isso.
Integridade de Auditoria: 1.000 gerações foram replicadas bit-identicamente com 100% de detecção de adulteração.

5. Significância e Limites Honestos

O artigo afirma que o GRID demonstra que a decodificação restrita de nível empresarial é alcançável ao se comprometer com a decodificação indexada por configuração. Este compromisso único permite compilação de política, garantias comprováveis, custos planos e auditorias replicáveis.

Os autores são explícitos sobre as limitações e fronteiras do sistema:

Fidelidade de Distribuição: O artigo não afirma que o masking preserva a distribuição de probabilidade original $P(x | x \in L)$ ; ele renormaliza localmente. O impacto é medido via precisão de execução downstream, não neutralidade distributiva.
RBAC de Nível de Coluna: O artigo prova (Proposição 11) que restrições de nível de coluna não podem ser impostas por uma máscara CFG da esquerda para a direita porque o vínculo necessário de alias-para-tabela é desconhecido no momento da máscara de coluna. Isso é tratado via verificação e reparo pós-parse, não pela própria máscara.
Escopo de Linguagem: O sistema é limitado a linguagens LALR(1). Embora lide com dialetos SQL padrão, declara erros de compilação para construções não-LALR(1) (ex: certos padrões de JSON Schema).
Contenção de Janela de Cold-Start: A redução temporária para requisições co-processadas durante a especialização de um novo esquema é reconhecida como um problema genuíno de contenção de largura de banda de CPU/memória do host, não um defeito de software, representando um trade-off de isolamento de computação.
Terminação: Garantias de terminação total (stops reservados-completados) só ocorrem no loop de decodificação controlado pelo GRID; modos de serviço apenas de processador podem truncar.

Em resumo, o GRID fornece um framework rigoroso e de alto desempenho para geração de SQL empresarial que prioriza correção, aplicação de políticas e auditabilidade, enquanto delineia honestamente os limites do que pode ser imposto via masking de gramática.