Résumé technique : Les descripteurs de grille structurelle prédisent le succès des solveurs au sein d'une même tâche sur ARC-AGI

Énoncé du problème

L'article examine une question spécifique concernant l'Abstraction and Reasoning Corpus (ARC-AGI) : les propriétés structurelles des états de grille intermédiaires dans la trajectoire d'un solveur symbolique contiennent-elles des informations prédictives de la réussite de cette exécution spécifique ?

Crucialement, les auteurs présentent cela comme un problème intra-tâche (within-task), distinct de la prédiction de difficulté inter-tâches. Ils demandent si, en maintenant la tâche fixe, la structure d'une grille intermédiaire (mesurée à une fraction fixe de la trajectoire) peut séparer les exécutions réussies des échecs. Cette distinction est vitale car les signaux inter-tâches reflètent souvent simplement l'identité de la tâche (les tâches difficiles ont des grilles plus complexes et des taux de réussite plus faibles), tandis qu'un signal intra-tâche indiquerait que l'état interne du solveur porte une information pronostique sur sa propre trajectoire.

Les auteurs testent l'hypothèse que l'information mutuelle conditionnelle $I(X; Y | \text{tâche}) > 0$, où $X$ est un vecteur de descripteurs structurels mesurés à la fraction de trajectoire $\tau = 0,5$, et $Y$ est le résultat binaire de succès.

Méthodologie

Collecte de données

L'étude utilise un ensemble massif de 44 800 exécutions de solveurs sur 400 tâches ARC (incluant les ensembles d'entraînement et d'évaluation). Deux solveurs aux architectures distinctes ont été employés :

1. Recherche en faisceau / Beam Search (Solveur A) : Une recherche de type "meilleur premier" maintenant $K$ chemins parallèles. Les configurations variaient en largeur de faisceau (2–32), bruit de score et ensembles de primitives.
2. DFS Stochastique (Solveur B) : Une recherche en profondeur avec élagage par retour en arrière (backtracking) et approfondissement itératif aléatoire qui s'engage sur un chemin unique. Les configurations variaient selon les limites de profondeur et les stratégies de redémarrage.

Descripteurs structurels

À la moitié de la meilleure trajectoire ($\tau = 0,5$), 13 descripteurs structurels faits main ont été extraits de l'état de la grille. Ceux-ci incluent :

• Nombre d'objets (final, dérive, écart-type)
• Entropie de couleur (final, dérive)
• Nombre de couleurs distinctes (final, dérive)
• Nombre de composantes connexes 4-connexes (final, dérive)
• Symétrie horizontale/verticale (final)
• Fragmentation (final, dérive)

Le choix de $\tau = 0,5$ a été pré-enregistré pour éviter les biais de "saturation de score" (où les caractéristiques ne font que refléter un état proche de la solution à la fin d'une exécution) et pour permettre des décisions d'arrêt précoce exploitables.

Cadre analytique

L'analyse a privilégié un contrôle rigoureux des variables de confusion :

• AUC Intra-Tâche : La performance a été mesurée via l'Aire Sous la Courbe (AUC) calculée au sein de chaque tâche, séparant les succès des échecs. La signification a été évaluée via des tests de permutation qui ont mélangé les étiquettes à l'intérieur des tâches, préservant ainsi la structure inter-tâches.
• Transfert entre Solveurs : Pour garantir que le signal n'est pas un artefact d'un algorithme de recherche spécifique, la meilleure caractéristique a été "gelée" sur un solveur source puis évaluée de manière aveugle sur le solveur cible.
• Contrôles de Confusion : Les auteurs ont explicitement testé et écarté trois explications alternatives :
  1. Saturation de Score : Vérifié que le signal n'est pas une reformulation de la trajectoire du score (couplage faible, $R^2 \approx 0$).
  2. Identité de la Tâche : Vérifié que le signal ne suit pas simplement la difficulté de la tâche.
  3. Capacité du Solveur : Vérifié que le signal n'est pas un proxy pour le budget de calcul (en utilisant l'AUC résidualisée par configuration et la concordance sur les paires contradictoires de capacité).

Résultats Clés

1. Signal Intra-Tâche Robuste

Les descripteurs structurels discriminent avec succès les exécutions réussies des échecs au sein d'une même tâche.

• Performance : L'AUC de la meilleure caractéristique moyenne sur les tâches diverses et fiables est de 0,885 pour le Beam Search et de 0,872 pour le DFS Stochastique ($p < 0,001$).
• Géométrie de l'espace des caractéristiques : L'espace des descripteurs à 13 dimensions est effectivement de rang 1 ($d_{eff} = 1,069$). La première composante principale explique 96,7 % de la variance. Le signal prédictif est presque entièrement piloté par un axe unique de complexité de la grille (spécifiquement le nombre d'objets et les composantes connexes), plutôt que par une famille diversifiée de caractéristiques.

2. Généralisation Inter-Solveurs (Résultat Principal)

Le signal se transfère entre des solveurs aux architectures distinctes, confirmant qu'il ne s'agit pas d'une particularité d'un algorithme de recherche spécifique.

• Performance de transfert : Les caractéristiques gelées sur un solveur prédisent le succès sur l'autre avec des AUC allant de 0,747 à 0,762 ($p < 0,001$) dans les quatre directions de transfert.
• Principaux prédicteurs : Les caractéristiques transférables sont principalement des comptages de complexité : obj count final et color entropy final.

3. Réplication sur Données de Test (Held-out)

Sur un ensemble de test pré-enregistré de 41 tâches diverses et fiables (caractéristique gelée : n components final), le modèle a atteint une AUC de 0,765 (IC 95 % [0,717, 0,810]). Ce résultat s'est maintenu lors de l'utilisation de bootstrapping groupé par tâches et lorsque les tâches partagées ont été fusionnées ou supprimées, confirmant que le signal n'est pas un artefact du comptage d'échantillons.

4. Insight Mécaniste : Écart de Couverture du DSL

Les auteurs ont identifié un mode de défaillance spécifique dans le DFS Stochastique : sur 229 des 400 tâches d'évaluation, le solveur produit des trajectoires à 0 étape (exécutions dégénérées) où aucune transition valide ne peut être générée à partir de la grille d'entrée.

• Cet échec est invariant au budget (se produit même avec des limites de nœuds élevées) et universel (le Beam Search échoue également à 100 % sur ces tâches).
• Les auteurs attribuent cela à un écart de couverture du DSL : la bibliothèque de primitives ne peut produire aucune transition valide pour ces grilles d'entrée spécifiques. Détecter ces exécutions "NaN-feature" permet un arrêt précoce sans coût supplémentaire.

Applications et Limites

Application d'Arrêt Précoce (Early-Stopping)

Les auteurs ont démontré une application pratique : utiliser le descripteur structurel pour interrompre les exécutions vouées à l'échec.

• Beam Search : Arrêter les exécutions prédites comme échouant à $\tau = 0,5$ permet d'économiser 33,6 % de calcul tout en conservant 98,9 % du taux de résolution. C'est environ dix fois mieux qu'un arrêt aléatoire.
• DFS Stochastique : La détection des trajectoires dégénérées à 0 étape permet d'économiser 65,3 % de calcul sans aucun coût sur le taux de résolution.

Revendications Modestes sur le Taux de Résolution

L'article ne prétend pas que ce signal améliore le taux de résolution global de l'ARC.

• Les auteurs ont testé si la réallocation du budget de calcul économisé vers des redémarrages supplémentaires sur les tâches non résolues augmentait le nombre total de tâches résolues.
• Résultat : La réallocation guidée par le descripteur n'a pas battu la réallocation aléatoire (moyenne de +0,2 résolution contre -1,0 pour l'aléatoire).
• Conclusion : Bien que le signal réduise le coût de la recherche (économies de calcul), il ne permet pas d'augmenter la quantité de solutions dans ce cadre. Le signal est informatif sur les résultats individuels des exécutions, mais ne fournit pas de mécanisme pour résoudre des tâches plus difficiles.

Signification et Revendications

La contribution primaire de cet article est une caractérisation empirique de la dynamique de recherche symbolique sur ARC. Il établit que :

1. La structure de la grille intermédiaire porte des informations transférables et intra-tâches sur le succès du solveur.
2. Cette information n'est pas liée à un algorithme de recherche spécifique (elle se généralise entre le Beam Search et le DFS Stochastique).
3. Le signal est robuste face aux biais d'identité de tâche, de capacité de solveur et de trajectoire de score.
4. Le contenu prédictif est étonnamment simple, se réduisant à un seul axe de complexité de la grille.

Les auteurs positionnent ce travail comme une étape fondamentale : identifier un signal peu coûteux et interprétable qui prédit l'issue des exécutions. Cependant, ils restent modestes, notant que si ce signal permet des économies de calcul (arrêt précoce), il ne se traduit pas actuellement par une meilleure généralisation ou un taux de résolution plus élevé, suggérant que le "fossé" entre savoir qu'une exécution va échouer et réellement résoudre plus de tâches reste un défi ouvert.