Barreira teórica para agentes neurossimbólicos
Agentes de IA modernos, construídos sobre princípios neurossimbólicos, usam cada vez mais a infraestrutura de busca como memória externa. A cadeia de raciocínio, nesse contexto, é compilada não em um simples conjunto de palavras-chave, mas em consultas booleanas profundamente aninhadas, com negações e ramificações. Essas consultas parecem naturais para um programador, mas para um índice invertido clássico elas se tornam um sério desafio.
Um preprint recente de Amir Aavani no arXiv (2601.18747, última versão de 17 de agosto de 2026) mostra que o problema não está na preguiça dos desenvolvedores de mecanismos de busca. O autor formaliza a linguagem de consultas L_R, representada como um grafo acíclico direcionado, e prova rigorosamente: avaliar tal consulta sobre um índice é um problema P-completo. Em outras palavras, no caso geral, esse processo dificilmente poderá ser paralelizado de forma eficiente em múltiplos núcleos — a menos que as classes P e NC sejam iguais, o que a maioria dos teóricos considera extremamente improvável.
O trabalho abrange várias áreas ao mesmo tempo — recuperação de informação, inteligência artificial, teoria da complexidade, processamento de linguagem natural e bancos de dados. Isso não é por acaso: o problema está na intersecção entre IA e tecnologias clássicas de busca.
Duas abordagens tradicionais e suas fraquezas
Quando uma consulta é executada sobre um índice invertido, geralmente se usa uma de duas estratégias: processamento iterativo por documento (Document-at-a-Time) ou materialização de listas intermediárias por termo (Term-at-a-Time). Cada uma tem seu "esqueleto no armário".
- Document-at-a-Time baseia-se em iteradores com estado que avançam por listas ordenadas de documentos. Acontece que tais iteradores são estruturalmente limitados à classe de esquemas NC¹. Se na lógica da consulta houver ramos reconvergentes — ou seja, vários caminhos do grafo convergindo para um único nó —, o desdobramento ingênuo desses ramos em uma árvore leva a uma explosão exponencial: a complexidade no pior caso atinge O(2^{|Q|}), onde |Q| é o tamanho da consulta.
- Term-at-a-Time tenta resolver o problema de outra forma: cada nó da consulta é materializado como uma lista de documentos. Mas, para calcular a negação lógica, essa abordagem precisa conhecer todo o universo de documentos |U|, para entender quais documentos não entram no resultado. Surge uma penalidade de Ω(|U|) — a chamada varredura universal. Em coleções grandes, isso significa, na prática, percorrer toda a base por causa de um único "não".
Assim, cada um dos dois métodos clássicos cumpre seu papel limitado, mas em consultas DAG não monotônicas eles esbarram ou no tempo ou no espaço. Até agora, acreditava-se que esse era o preço inevitável pela expressividade.
Algoritmo ComputePN
Amir Aavani propõe uma manobra alternativa — um algoritmo determinístico chamado ComputePN, especialmente ajustado para dados esparsos. A ideia-chave é separar a negação lógica da materialização de todo o universo. Em vez de construir a lista completa de "todos os documentos que não existem", o ComputePN usa uma representação dual de cada nó: o par "positivo-negativo" armazena tanto o que entra no resultado quanto o que é garantidamente excluído dele.
Essa abordagem permite considerar apenas os documentos ativos — aqueles que realmente participam dos cálculos. Os resultados intermediários são memoizados diretamente no grafo da consulta, de modo que as mesmas subexpressões não são recalculadas várias vezes. A complexidade final é estimada como O(|Q| · |U_active|), onde U_active é o conjunto de documentos afetados, e não todo o universo.
Na prática, isso significa que os casos pesados, com negações e ramos convergentes, deixam de ser fatais. Se a coleção real é grande, mas a consulta atinge apenas uma pequena parte dela, o ComputePN permanece eficiente.
O que isso significa para mecanismos de busca e IA
A principal conclusão do trabalho não é que acelerar a varredura do índice invertido seja fundamentalmente impossível. Muito pelo contrário: o autor mostra como é possível calcular nativamente consultas P-completas, evitando as duas principais armadilhas — o desdobramento combinatório da árvore e a varredura de todos os documentos por causa da negação.
Para sistemas híbridos neurossimbólicos, esse é um sinal importante. Agentes baseados em LLM geram consultas cada vez mais sofisticadas, e o backend de busca precisa ser capaz de atendê-las sem degradação catastrófica. A P-completude teórica continua sendo um alerta para desenvolvedores de arquiteturas paralelas, mas o ComputePN mostra que uma implementação de engenharia bem-feita pode contornar os piores cenários.
No entanto, até o algoritmo chegar a sistemas de produção, ainda há muito trabalho pela frente. O esquema proposto exige um tratamento cuidadoso das representações duais e da memoização no nível de um mecanismo de busca real. Mas o fato de o problema finalmente ter recebido uma base teórica rigorosa já é importante por si só: agora os desenvolvedores pelo menos sabem com que complexidade estão lidando e quais técnicas realmente ajudam.
