Estudo de complexidade mostra que certificar que um LLM não vaza um segredo é muito mais caro do que checar um vazamento pontual

A pergunta que motiva o artigo é operacionalmente relevante para qualquer equipe que audite um modelo de linguagem em busca de vazamento de informação sensível (segredos de sistema, dados de treinamento, credenciais embutidas em fine-tuning): quando uma auditoria não encontra nenhum vazamento, o que exatamente isso garante? Os autores respondem de forma rigorosa que existe uma assimetria fundamental entre encontrar um vazamento e provar sua ausência. Dado um exemplo concreto de execução que vaza o segredo, checá-lo é trivial e rápido (polinomial). Mas provar que nenhuma execução dentro do domínio declarado de prompts vaza o segredo é um problema muito mais difícil: os autores mostram que a existência de um vazamento é NP-completa, a certificação determinística de não-vazamento é coNP-completa, e a certificação estocástica exata (levando em conta a aleatoriedade da decodificação) é coNP^PP-completa para qualquer limiar de probabilidade fixo.

Esses resultados de complexidade não são apenas curiosidades teóricas — eles têm implicação prática direta sobre como equipes de red team e auditoria de segurança devem interpretar um resultado negativo. Se certificar não-vazamento de forma exata é computacionalmente inviável em geral, então qualquer auditoria real na prática é necessariamente uma amostragem parcial do espaço de prompts possíveis, e “não encontramos vazamento” é uma afirmação estatística fraca, não uma garantia. Os autores também identificam casos especiais onde a certificação se torna tratável — por exemplo, quando toda a aleatoriedade vem de uma tabela de probabilidade finita computada previamente, ou em modelos de atenção com janelas de dependência local curtas seguidas de uma única cabeça global, decodificação determinística e domínios de prompt representáveis por autômatos finitos — mas mostram que adicionar apenas uma segunda camada global de atenção já torna a certificação coNP-completa novamente, ilustrando o quão frágil é a fronteira entre tratável e intratável.

A parte mais concreta e alarmante do artigo é o experimento com segredos plantados: entre 30 pares de segredo/modelo que efetivamente vazam sob execução gulosa (greedy) de prompt único dentro de um domínio de 4.096 prompts, selecionar uniformemente apenas 256 avaliações para auditoria — um tamanho de amostra que muitas auditorias reais usariam por restrição de custo — deixa passar despercebido o vazamento em uma fração esperada de 41,06% dos pares. Ou seja, quase metade dos vazamentos reais escaparia de uma auditoria amostral de tamanho razoável. Os autores também encontram discordância entre checagens em lote e checagens de prompt único em um caso entre 48 pares, embora a repetição de uma mesma checagem na mesma ordem seja consistente.

Na prática, este trabalho é um alerta técnico para qualquer processo de red teaming ou auditoria de vazamento de segredos em LLMs (por exemplo, para verificar que um modelo fine-tunado não memoriza e reexpõe dados de treinamento sensíveis, ou que um agente com acesso a segredos de sistema não os revela sob nenhuma formulação de prompt): resultados negativos de auditorias por amostragem devem ser tratados como evidência parcial e limitada pelo tamanho e cobertura da amostra, nunca como prova de segurança. Isso reforça a necessidade de complementar auditorias amostrais com controles estruturais (por exemplo, impedir que o segredo esteja acessível ao modelo em primeiro lugar) sempre que o custo de um vazamento for alto, já que a certificação formal completa é, no caso geral, computacionalmente inviável.