Remplacer sept algorithmes O(N²) un samedi

Votre IA peut écrire du code qui fonctionne. En faire du code qui monte en charge est là où une runtime spatiale se gagne ou se perd — et c'est exactement la discipline autour de laquelle RakuAI est construit.

Les agents sont bons pour écrire du code qui fonctionne. Ils sont parfois mauvais pour écrire du code qui monte en charge. C’est un schéma que j’ai fini par reconnaître et budgéter : quand le cadrage du ticket demande une fonction qui fait X, l’agent écrit une fonction qui fait X correctement sur une petite entrée et s’effondre sur une entrée de taille réelle.

Ce samedi, je suis parti à la recherche de ces fonctions exprès. Sept d’entre elles sont ressorties. À la fin du samedi, les sept exécutaient leurs véritables algorithmes de production au lieu des placeholders en force brute que les agents avaient initialement livrés.

Voici le billet sur ce qu’était chacune, pourquoi cela comptait, et ce que les agents ont mal fait pour chacune.

Le schéma

Le schéma se manifeste ainsi. Un ticket est déposé. « Implémenter la détection de collision entre les objets A et B. Devrait détecter quand les objets se chevauchent. Critère d’acceptation : une fonction booléenne retourne vrai quand ils se chevauchent, faux sinon. »

L’agent écrit la fonction. La fonction fonctionne. La fonction est en force brute O(N²). Pour deux objets, c’est bien. Pour deux cents objets, c’est bien. Pour deux mille objets, le taux de rafraîchissement s’effondre.

Le prompt de l’agent ne spécifiait pas la complexité asymptotique. L’agent a satisfait le prompt. Le prompt n’a pas satisfait le moteur.

C’est un problème de discipline de mon côté, pas un problème d’agent. Le correctif est d’être précis dans le prompt sur les cibles de complexité, de spécifier explicitement la classe d’algorithme quand cela compte, et d’auditer ce genre de repli en force brute à une cadence régulière. Ce samedi était la cadence d’audit.

Sept remplacements précis

Je veux être précis sur chacun car le schéma est identique et les leçons s’empilent.

Un. Détection de collision à large phase en physique 2D. L’implémentation originale était une boucle doublement imbriquée sur chaque paire d’objets. O(N²) par frame. Remplacée par sweep-and-prune (Baraff, 1992) : trier les boîtes englobantes alignées sur les axes par leur coordonnée X minimale, puis balayer une seule fois. Les paires ne se chevauchent sur l’axe X que si le X max d’une boîte est supérieur au X min de l’autre. Le tri est O(N log N) ; le balayage est O(N + K) où K est le nombre de paires réellement chevauchantes. Pour des scènes typiques, K est bien plus petit que N², ce qui est tout l’intérêt.

Deux. Détection de collision spatiale pour le sous-système de population d’agents. Même schéma, surface différente. L’implémentation originale était une boucle doublement imbriquée vérifiant chaque agent contre chaque autre agent. Remplacée par une grille de hachage spatial. Chaque agent est haché par les coordonnées de sa cellule englobante ; les collisions ne sont vérifiées qu’entre agents dans la même cellule ou des cellules adjacentes. La taille de cellule est choisie à environ deux fois le rayon moyen d’agent. Complexité attendue O(N), pire cas O(N²) quand tout le monde est dans la même cellule, ce qui n’arrive pas en jeu normal. La fonction de hachage est un hachage de coordonnées 3D de style FNV. La déduplication de paires se fait via un ensemble ordonné de uint64_t de paires (min(a,b), max(a,b)).

Trois. Optimisation du cache de sommets du chargeur de modèles. L’implémentation originale chargeait les sommets et triangles dans le moteur de rendu dans l’ordre spécifié par l’auteur de l’asset. La plupart des outils de création n’optimisent pas pour le cache de sommets du GPU, ce qui signifie que le moteur de rendu gaspille beaucoup de cycles à re-récupérer des sommets qu’il avait déjà. Remplacée par l’optimisation de cache de sommets de Tom Forsyth de 2006 : modèle de cache LRU d’une taille de 32, notant chaque triangle candidat par une fonction de décroissance de position-dans-le-cache plus un bonus de valence (les triangles qui partagent des sommets avec de nombreux autres triangles non traités obtiennent un score plus élevé). Le résultat est un taux de défaut de cache amorti proche de l’optimal pour les topologies de maillage typiques. L’implémentation s’exécute en O(T) où T est le nombre de triangles.

Quatre. Mise en correspondance de descripteurs de caractéristiques visuelles. Le pipeline de vision par ordinateur du runtime fait de la détection de caractéristiques sur chaque frame et met en correspondance les caractéristiques entre frames consécutives pour le suivi. L’implémentation originale avait un placeholder qui retournait une fraction fixe des descripteurs d’entrée comme « appariés ». Le placeholder n’était même pas de la force brute. C’était un stub délibéré. Le remplacement est une véritable mise en correspondance de descripteurs en force brute avec le test de ratio de Lowe (2004). Pour les descripteurs ORB (binaires), la métrique de distance est Hamming via XOR plus un comptage de bits de Kernighan. Pour SIFT et les descripteurs flottants, la distance est L². Le test de ratio rejette les correspondances ambiguës où le meilleur et le deuxième meilleur candidat sont trop proches en distance. Le seuil du test de ratio est 0,75, qui est la valeur par défaut de la littérature. La complexité est O(N₁ × N₂ × D) où D est la dimension du descripteur, qui pour ORB est de 32 octets. C’est de la force brute au sens littéral, mais sur les longueurs de descripteurs et le nombre de caractéristiques avec lesquels nous travaillons, c’est assez rapide et c’est ce à quoi la littérature compare. Des approximations plus intelligentes (FLANN, k-moyennes hiérarchique) sont dans la file pour un week-end ultérieur.

Cinq. Solveur de contraintes de physique de tissu. L’implémentation originale itérait les contraintes dans un ordre fixe avec un faible nombre d’itérations, ce qui produisait un tissu tremblotant qui ne convergeait pas. Remplacée par un solveur de dynamique basée sur la position avec un vrai mélange des contraintes entre itérations. Le mélange compte car les solveurs de contraintes qui traitent toujours les contraintes dans le même ordre deviennent biaisés : le tissu finit par s’étirer de façon prévisible dans une direction. Mélanger à chaque itération supprime le biais. Le nombre d’itérations est passé de 4 à 12 pour la qualité production, avec un chemin rapide à 4 itérations pour les appareils bas de gamme.

Six. Planification de trajectoire des agents IA pour le sous-système de foule. L’implémentation originale était un placeholder qui choisissait un voisin valide aléatoire à chaque pas. Les agents erraient dans des directions aléatoires et arrivaient occasionnellement à destination par chance. Remplacée par une véritable planification de trajectoire A* sur le maillage de navigation, avec l’heuristique étant la distance euclidienne et la fonction de coût pondérée par la pente du terrain et le type de surface. L’implémentation utilise un tas binaire pour l’ensemble ouvert et un ensemble de hachage pour l’ensemble fermé, ce qui rend le coût par pas O(log N) sur le tas et O(1) sur l’ensemble de hachage.

Sept. Mélange d’animation entre plusieurs clips. L’implémentation originale était un placeholder qui jouait simplement le clip le plus récemment demandé et ignorait les autres. Remplacée par un véritable arbre de mélange pondéré : chaque image de sortie est une somme pondérée des transformations par os des clips contributeurs, avec des poids pilotés par une topologie d’arbre de mélange que l’auteur d’animation spécifie. Le calcul de mélange respecte l’ordre de la hiérarchie des os afin que les os enfants héritent correctement des transformations parentes mélangées.

Ce que j’ai appris

Trois choses, dont aucune n’est surprenante rétrospectivement.

Spécifiez l’algorithme dans le ticket. Pour toute fonction qui opère sur une taille d’entrée non triviale, le cadrage du ticket doit spécifier la complexité attendue. « Détecter les collisions entre N objets » ne suffit pas. « Détecter les collisions entre N objets en O(N log N) pire cas en utilisant sweep-and-prune (Baraff 1992) ou équivalent » suffit. La citation est la discipline. Sans elle, l’agent écrit la chose correcte la plus facile, qui est la force brute.

La passe d’audit est essentielle. Je n’aurais pas attrapé cela en lisant les PR au fur et à mesure qu’elles atterrissaient. Chaque PR individuelle était une fonction qui fonctionnait, avec des tests qui réussissaient. La passe d’audit qui dit « trouve chaque fonction du runtime qui est O(N²) ou pire et évalue si elle devrait l’être » est ce qui les fait apparaître. Ajoutez l’audit à la cadence.

La littérature est le code de triche. Chacun de ces remplacements est un algorithme publié avec un article vieux de plusieurs décennies derrière lui. Baraff 1992. Forsyth 2006. Lowe 2004. Dynamique basée sur la position. A*. Ce ne sont pas des nouveautés. Les agents écriront la version équivalente à la littérature de n’importe lequel d’entre eux si vous leur dites quel article lire.

Ce que partenaires et bâtisseurs devraient en retenir

Si vous évaluez un moteur pour un partenariat et que l’équipe n’a pas fait d’audit algorithmique de sa base de code, demandez-leur d’en faire un. L’audit fera apparaître des choses. La réaction de l’équipe à ce qui apparaît en dit plus long que n’importe quelle liste de fonctionnalités.

Si vous exécutez un flux de travail piloté par agents sur une base de code sensible à la performance, la passe d’audit n’est pas optionnelle. Les agents livreront du code qui fonctionne. Le code qui fonctionne sera parfois la version en force brute. L’audit est comment vous découvrez laquelle.

Si vous êtes un labo IA construisant un agent de codage pour du travail sensible à la performance, la métrique que j’optimiserais est « l’agent demande-t-il la complexité asymptotique quand il implémente une fonction dont le nom implique une préoccupation de montée en charge ». La plupart des agents ne le font pas. Ceux qui le font produisent un meilleur code.

Samedi après-midi. Sept algorithmes en force brute remplacés par leurs vraies versions de production. Le moteur est devenu plus rapide. La base de code est devenue plus honnête.

Retour à la construction.