Substituindo Sete Algoritmos O(N²) em um Sábado

Sua IA consegue escrever código que funciona. Fazer com que seja código que escala é onde um runtime espacial se ganha ou se perde — e é exatamente a disciplina em torno da qual o RakuAI é construído.

Os agentes são bons em escrever código que funciona. Às vezes são ruins em escrever código que escala. Esse é um padrão que passei a reconhecer e para o qual passei a planejar: quando o enquadramento da issue pede uma função que faz X, o agente escreve uma função que faz X corretamente em uma entrada pequena e quebra numa de tamanho real.

Neste sábado saí procurando essas funções de propósito. Sete delas voltaram. Ao final do sábado, todas as sete estavam rodando seus algoritmos reais de produção em vez dos placeholders de força bruta que os agentes tinham originalmente integrado.

Este é o post sobre o que cada uma era, por que importava, e o que os agentes erraram em cada uma.

O padrão

O padrão aparece assim. Uma issue é registrada. “Implemente detecção de colisão entre objetos A e B. Deve detectar quando objetos se sobrepõem. Critério de aceitação: função booleana retorna verdadeiro quando eles se sobrepõem, falso caso contrário.”

O agente escreve a função. A função funciona. A função é força bruta O(N²). Para dois objetos, tudo bem. Para duzentos objetos, tudo bem. Para dois mil objetos, a taxa de quadros já era.

O prompt do agente não especificava a complexidade assintótica. O agente satisfez o prompt. O prompt não satisfez o engine.

Esse é um problema de disciplina do meu lado, não um problema do agente. A correção é ser específico no prompt sobre metas de complexidade, especificar a classe de algoritmo explicitamente quando importa, e auditar esse tipo de fallback de força bruta em uma cadência regular. Este sábado foi a cadência de auditoria.

Sete substituições específicas

Quero ser específico sobre cada uma porque o padrão é idêntico e as lições se acumulam.

Um. Detecção de colisão de fase ampla da física 2D. A implementação original era um laço duplamente aninhado sobre todo par de objetos. O(N²) por quadro. Substituída por sweep-and-prune (Baraff, 1992): ordena as caixas delimitadoras alinhadas por eixo pela sua coordenada X mínima, depois varre uma vez. Pares só se sobrepõem no eixo X se o X máximo de uma caixa for maior que o X mínimo da outra. A ordenação é O(N log N); a varredura é O(N + K) onde K é o número de pares que realmente se sobrepõem. Para cenas típicas, K é muito menor que N², que é o ponto todo.

Dois. Detecção de colisão espacial para o subsistema de população de agentes. Mesmo padrão, superfície diferente. A implementação original era um laço duplamente aninhado checando todo agente contra todo outro agente. Substituída por uma grade de hash espacial. Cada agente recebe um hash pelas coordenadas da sua célula delimitadora; colisões só são checadas entre agentes na mesma célula ou em células adjacentes. O tamanho da célula é escolhido como aproximadamente duas vezes o raio médio do agente. Complexidade esperada O(N), pior caso O(N²) quando todo mundo está na mesma célula, o que não acontece em jogo normal. A função de hash é hashing de coordenada 3D estilo FNV. A deduplicação de pares é feita via um conjunto ordenado de uint64_t de pares (min(a,b), max(a,b)).

Três. Otimização de cache de vértices do carregador de modelos. A implementação original carregava vértices e triângulos no renderizador na ordem que o autor do asset especificou. A maioria das ferramentas de autoria não otimiza para o cache de vértices da GPU, o que significa que o renderizador desperdiça muitos ciclos rebuscando vértices que já tinha. Substituída pela otimização de cache de vértices de Tom Forsyth de 2006: modelo de cache LRU com tamanho 32, pontuando cada triângulo candidato por uma função de decaimento de posição-no-cache mais um bônus de valência (triângulos que compartilham vértices com muitos outros triângulos ainda não processados pontuam mais alto). O resultado é uma taxa de cache miss amortizada quase ótima para topologias de malha típicas. A implementação roda em O(T) onde T é a contagem de triângulos.

Quatro. Correspondência de descritores de características de visão. O pipeline de visão computacional do runtime faz detecção de características em todo quadro e faz correspondência de características entre quadros consecutivos para rastreamento. A implementação original tinha um placeholder que retornava uma fração fixa dos descritores de entrada como “correspondidos.” O placeholder nem era força bruta. Era um stub deliberado. A substituição é correspondência real de descritores por força bruta com o teste de razão de Lowe (2004). Para descritores ORB (binários), a métrica de distância é Hamming via XOR mais uma contagem de bits Kernighan. Para SIFT e descritores em ponto flutuante, a distância é L². O teste de razão rejeita correspondências ambíguas onde o melhor e o segundo melhor candidato estão próximos demais em distância. O limiar para o teste de razão é 0,75, que é o padrão da literatura. A complexidade é O(N₁ × N₂ × D) onde D é a dimensão do descritor, que para ORB é 32 bytes. Isso é força bruta no sentido literal, mas nos comprimentos de descritor e contagens de características com que trabalhamos, é rápido o suficiente e é contra o que a literatura compara. Aproximações mais inteligentes (FLANN, k-means hierárquico) estão na fila para um fim de semana futuro.

Cinco. Solucionador de restrições da física de tecido. A implementação original iterava restrições em ordem fixa com uma contagem de iterações baixa, o que produzia tecido tremido que não convergia. Substituída por um solucionador de dinâmica baseada em posição com embaralhamento adequado de restrições entre iterações. O embaralhamento importa porque solucionadores de restrições que sempre processam restrições na mesma ordem ficam enviesados: o tecido acaba esticando de forma previsível em uma direção. Embaralhar cada iteração remove o viés. A contagem de iterações foi elevada de 4 para 12 para qualidade de produção, com um caminho rápido de 4 iterações para dispositivos de baixo desempenho.

Seis. Planejamento de caminho de agentes de IA para o subsistema de multidão. A implementação original era um placeholder que escolhia um vizinho válido aleatório a cada passo. Agentes vagavam em direções aleatórias e ocasionalmente chegavam a seus destinos por sorte. Substituída por planejamento de caminho A* adequado sobre a malha de navegação, com a heurística sendo distância euclidiana e a função de custo ponderada pela inclinação do terreno e tipo de superfície. A implementação usa um heap binário para o conjunto aberto e um conjunto hash para o conjunto fechado, o que torna o custo por passo O(log N) no heap e O(1) no conjunto hash.

Sete. Mistura de animação entre múltiplos clipes. A implementação original era um placeholder que apenas tocava o clipe solicitado mais recentemente e ignorava os outros. Substituída por uma árvore de mistura ponderada adequada: cada quadro de saída é uma soma ponderada das transformações por osso dos clipes contribuintes, com pesos guiados por uma topologia de árvore de mistura que o autor da animação especifica. O cálculo de mistura respeita a ordem da hierarquia de ossos para que ossos filhos herdem corretamente as transformações mescladas dos pais.

O que eu aprendi

Três coisas, nenhuma surpreendente em retrospecto.

Especifique o algoritmo na issue. Para qualquer função que opera em um tamanho de entrada não trivial, o enquadramento da issue precisa especificar a complexidade esperada. “Detecte colisões entre N objetos” não é suficiente. “Detecte colisões entre N objetos em pior caso O(N log N) usando sweep-and-prune (Baraff 1992) ou equivalente” é suficiente. A citação é a disciplina. Sem ela, o agente escreve a coisa correta mais fácil, que é força bruta.

A passagem de auditoria é essencial. Eu não teria pego essas lendo os PRs conforme eram integrados. Cada PR individual era uma função que funcionava, com testes que passavam. A passagem de auditoria que diz “encontre toda função no runtime que é O(N²) ou pior e avalie se deveria ser” é o que as revela. Adicione a auditoria à cadência.

A literatura é o código de trapaça. Cada uma dessas substituições é um algoritmo publicado com um artigo de décadas por trás. Baraff 1992. Forsyth 2006. Lowe 2004. Dinâmica baseada em posição. A*. Não são novidades. Os agentes vão escrever a versão equivalente à literatura de qualquer um deles se você disser qual artigo ler.

O que parceiros e construtores devem tirar disso

Se você está avaliando um engine para parceria e o time não fez uma auditoria algorítmica da própria base de código, peça para fazerem uma. A auditoria vai revelar coisas. A resposta do time ao que ela revela diz mais do que qualquer lista de recursos.

Se você está rodando um fluxo de trabalho orientado por agentes em uma base de código sensível a desempenho, a passagem de auditoria não é opcional. Os agentes vão integrar código que funciona. O código que funciona às vezes vai ser a versão de força bruta. A auditoria é como você descobre qual.

Se você é um laboratório de IA construindo um agente de codificação para trabalho sensível a desempenho, a métrica que eu otimizaria é “o agente pergunta sobre complexidade assintótica quando está implementando uma função cujo nome implica uma preocupação com escala.” A maioria dos agentes não pergunta. Os que perguntam produzem código melhor.

Tarde de sábado. Sete algoritmos de força bruta substituídos por suas versões reais de produção. O engine ficou mais rápido. A base de código ficou mais honesta.

De volta a construir.