Les cycles de Claude [PDF]

 (www-cs-faculty.stanford.edu)
4 points par GN⁺ 2026-03-04 | 1 commentaires | Partager sur WhatsApp
  • Claude Opus 4.6 d’Anthropic a résolu le problème de décomposition en cycles hamiltoniens orientés sur lequel Donald Knuth travaillait depuis plusieurs semaines
  • Le problème consiste à trouver une décomposition en trois cycles hamiltoniens d’un graphe orienté ayant (m^3) sommets, et Claude l’a résolu de manière complète pour les m impairs
  • Claude a procédé par étapes en combinant diverses stratégies d’exploration, notamment la décomposition en fibres, des motifs serpentin 3D, la recherche en profondeur (DFS) et le recuit simulé
  • Il a finalement dérivé une solution générale sous la forme d’un programme Python, que Filip Stappers a vérifiée pour les m impairs de 3 à 101, confirmant une décomposition complète
  • Knuth considère ce résultat comme une avancée majeure du raisonnement automatisé et de la résolution créative de problèmes, tout en précisant que le cas des m pairs reste non résolu

Contexte et définition du problème

  • Le sujet de recherche porte sur les cycles hamiltoniens orientés et doit figurer dans un futur volume de The Art of Computer Programming de Knuth
  • Le graphe est composé de (m^3) sommets (ijk), avec trois arêtes sortantes depuis chaque sommet : (i+jk), (ij+k), (ijk+)
  • L’objectif est de trouver, pour tout (m>2), une solution générale permettant de décomposer ces arêtes en trois cycles orientés de longueur (m^3)

Processus d’exploration de Claude

  • Claude Opus 4.6 est le modèle de raisonnement hybride d’Anthropic ; Filip Stappers lui a soumis le problème et lui a demandé de documenter son cheminement
  • Dans un premier temps, Claude a reformulé le problème comme un graphe fonctionnel et un problème d’affectation de permutations, puis a tenté des approches linéaires et quadratiques sans succès
  • Il a ensuite expérimenté successivement une exploration DFS, l’analyse de motifs serpentins 2D et des motifs fondés sur le code Gray en 3D
  • En introduisant l’approche de décomposition en fibres, il a analysé une structure stratifiée selon (s = (i+j+k) \mod m) et découvert des solutions partielles via le recuit simulé (SA)

Découverte et vérification de la solution

  • À l’étape 31 de l’exploration, Claude a généré un programme Python fondé sur une règle dépendant d’une seule coordonnée par fibre
  • Ce programme produit trois cycles hamiltoniens complets pour m=3,5,7,9,11
  • Filip Stappers l’a ensuite testé pour tous les m impairs de 3 à 101, confirmant une décomposition complète
  • Knuth l’a simplifié en code C, puis a démontré mathématiquement que chaque cycle est bien de longueur (m^3)

Généralisation et analyse mathématique

  • Il a été confirmé que certains cycles hamiltoniens pour (m=3) peuvent être généralisés à tous les m impairs
    • Parmi les 11 502 cycles pour (m=3), 1 012 se généralisent à (m=5), et 996 jusqu’à (m=7)
    • Ces 996 cycles sont généralisables à tout m impair > 1
  • Une décomposition de type « Claude-like » est définie par des règles simples ne dépendant que des valeurs limites de i, j et s (0 ou m−1)
  • Théorème : pour qu’une décomposition « Claude-like » soit valide pour tout m impair > 1, les trois cycles pour m=3 doivent être des cycles hamiltoniens généralisables
  • Les calculs montrent que 760 décompositions « Claude-like » sont valides pour tous les m impairs

Cas non résolu des m pairs et conclusion

  • Le cas des m pairs reste ouvert
    • L’impossibilité pour (m=2) a déjà été démontrée dans des travaux antérieurs
    • Claude a trouvé des solutions partielles pour (m=4,6,8), sans parvenir à les généraliser
  • Lors de l’exploration du cas pair, Claude a montré des erreurs et des comportements anormaux, ce qui a conduit à l’arrêt de la recherche
  • Knuth y voit une réalisation historique du raisonnement automatisé fondé sur l’IA, et une avancée digne du nom de Claude Shannon

Annexe : règles des deux autres cycles

  • Deuxième cycle (c=1) :
    • si (s=0), alors j augmente ; si (0<s<m−1), alors i augmente ; si (s=m−1), alors si i>0, k augmente, et si i=0, j augmente
  • Troisième cycle (c=2) :
    • pour (s=0), si j<m−1, alors i augmente, et si j=m−1, alors k augmente
    • pour (0<s<m−1), si i<m−1, alors k augmente, et si i=m−1, alors j augmente
    • si (s=m−1), alors i augmente
  • L’ordre des sommets pour s=0 dans chaque cycle est explicitement donné, ce qui permet de démontrer la structure de l’ensemble des cycles

À lire aussi

1 commentaires

 
GN⁺ 2026-03-04
Commentaires sur Hacker News

  • Il est intéressant de réfléchir aux domaines de problèmes où l’évolutivité du RL peut s’appliquer
    Autrefois, il fallait dépendre de la cognition humaine, mais désormais ces schémas sont intégrés dans une distribution de probabilités, ce qui les rend accessibles à tous
    On peut toutefois se demander si les modèles pourront suivre le rythme à mesure que la frontière de la science continue de s’étendre
    En 2030, pour qu’Anthropic maintienne Claude à jour, il faudra soit (a) de l’apprentissage continu sur un modèle figé, soit (b) un entraînement continu, et aucune de ces deux options n’est simple

    • Les modèles à poids ouverts ressemblent à une sorte de capsule temporelle
      Après la date de coupure des connaissances, ils restent figés à jamais à cet instant
    • Si le partage des données est autorisé, les résultats de raisonnement d’aujourd’hui pourraient devenir les données d’entraînement de demain
      On peut même imaginer un modèle qui fournit de l’inférence gratuite aux chercheurs en échange de leurs traces de raisonnement (trace) comme données d’entraînement
    • À écouter les chercheurs ces derniers temps, l’architecture des modèles semble évoluer vers une forte extension de la fenêtre de contexte
      Des modèles comme Qwen3-next, Qwen3.5 et Nemotron 3 Nano prennent en charge des fenêtres d’un million de tokens en réduisant le coût mémoire grâce à une attention hybride
    • La plupart de la recherche et de l’apprentissage se font déjà via des LLM et des agents de code
      Les boucles de rétroaction en temps réel issues de la vérification humaine, de l’exécution de code et de la recherche servent de signal d’apprentissage pour les modèles
    • En 2030, il se pourrait même que Claude maintienne Anthropic à jour
      C’est à moitié une blague, mais ce n’est pas totalement impossible

  • Cela rappelle l’ancienne conversation entre Wolfram et Knuth sur GPT-4
    Knuth était sceptique à l’époque, mais il semble avoir adouci sa position après avoir vu des modèles récents comme Opus 4.6
    Il est admirable de changer d’avis à la lumière de nouvelles preuves
    La discussion en question peut être consultée ici

    • Mettre à jour sa probabilité a priori (prior) à partir de nouveaux éléments, c’est précisément tout l’intérêt des statistiques bayésiennes
      C’est aussi au cœur de la pensée scientifique

  • J’ai l’impression que l’introduction du texte de Knuth est quelque peu ambiguë
    On dirait que Claude a résolu le problème directement, alors qu’en réalité Claude a produit des exemples et Knuth les a généralisés pour en faire une démonstration

    • J’ai moi aussi fait une expérience similaire avec Claude, et la synergie entre humain et LLM est vraiment forte
      Les LLM sont faibles pour définir une direction, mais une fois la direction donnée, ils excellent dans l’exploration approfondie
      Livrés à eux-mêmes, ils partent facilement dans tous les sens, mais avec un humain à la barre, ils deviennent d’excellents partenaires
    • Je ne pense pas que Knuth l’ait surestimé
      Claude a joué le rôle de percée au cœur du problème, et l’humain n’a fait qu’affiner ensuite
    • On peut aussi considérer que Claude a bien produit la « résolution » au sens où l’entend Knuth
      La mise en forme de la démonstration n’était qu’un travail secondaire
    • La capacité à revenir sur des tentatives précédentes pour réfléchir et corriger ressemble clairement à un signe d’intelligence

  • Le fait que Claude se soit arrêté sur le cas pair est intéressant
    Il a probablement utilisé soit claude.ai, soit claude code, et semble être entré dans une zone stupide (dumb zone) à cause d’un dépassement de contexte

    • Ce serait bien de pouvoir visualiser cette dumb zone
      Par exemple en affichant un graphique d’utilisation du contexte comme Copilot, afin que l’utilisateur puisse s’en rendre compte
    • Au final, sans compression du contexte (compacting), les résultats deviennent médiocres
    • Le fait qu’il mentionne un « plan document » laisse penser qu’il utilisait un document de gestion de session
    • Certaines personnes se demandaient aussi ce qu’était exactement cette dumb zone

  • Quelqu’un a fait résoudre à Claude le célèbre puzzle des pentominos popularisé par Arthur C. Clarke
    En représentant le plateau et les pièces avec des entiers 64 bits, Claude a produit un programme C# qui l’a résolu rapidement, mais il a donné une mauvaise réponse pour le cas 20x3 à cause d’un mapping incorrect
    C’est intéressant, car c’est le genre d’erreur qu’un humain pourrait faire

  • En résumé, Knuth a posé le problème et un ami a mené une trentaine d’explorations avec Claude
    Claude a créé un programme Python qui résout les cas impairs, et Knuth a démontré cette approche
    Le cas pair reste toujours un problème non résolu

    • Mais l’expression « careful human guidance » utilisée par Knuth semble exagérée
      En pratique, Claude s’arrêtait souvent ou faisait des erreurs, et l’humain ne faisait qu’un rappel occasionnel
    • Ce que Knuth voulait surtout souligner, semble-t-il, c’est que la preuve formelle reste du ressort des humains
      On ne sait pas clairement de qui venait l’idée centrale

  • En ce moment, c’est vraiment une période passionnante pour travailler sur des problèmes non résolus
    Cela donne envie de reprendre des recherches d’il y a dix ans et de les explorer de nouveau avec Claude

  • Les forces des LLM semblent être au nombre de trois : une connaissance immense, une capacité à faire des liens et des essais-erreurs infatigables
    Lorsque ces trois éléments se combinent, on obtient parfois des résultats étonnants
    Peut-être que la preuve de P≠NP se cache dans un lien ténu que les humains n’ont pas encore vu

    • Le dernier point est peut-être en réalité moins une propriété du LLM lui-même qu’une caractéristique de la boucle d’agent
      Le LLM n’en est qu’un composant parmi d’autres
    • Malgré tout, l’exploration itérative inlassable reste un avantage majeur sur l’humain
      Toutes choses égales par ailleurs, c’est une différence décisive
    • Je suis tout à fait d’accord avec l’idée que ces trois éléments, combinés, peuvent produire de très beaux résultats
    • Mais il est inquiétant de penser que ce type de capacité puisse être utilisé dans des systèmes de surveillance
    • La « capacité à faire des liens » semble en réalité limitée aux liens déjà présents dans les données d’entraînement
      Produire des liens complètement nouveaux reste encore difficile

  • Je me demande si l’affirmation « les LLM ne sont que des machines à prédire le mot suivant » est vraiment juste
    Si c’est le cas, comment expliquer ce type de résolution de problème ? Est-ce cela, penser ?

    • Si l’on pouvait prédire parfaitement le prochain mot qu’Einstein allait prononcer, on aurait déjà implémenté une forme d’intelligence
      L’expression « le mot le plus probable » est une simplification excessive
    • Cette description convient aux modèles de base, mais des modèles comme Opus 4.6 ont en plus du RLHF et un entraînement supplémentaire
      Au fond, la capacité à bien prédire ce qui va se passer ensuite pourrait être elle-même une définition de l’intelligence
    • Les modèles de base apprennent naturellement des schémas de résolution de problèmes en assimilant sur le web des structures du type « Answer: »
      Grâce au RLHF, ils sont récompensés non pas pour une simple prédiction, mais pour des réponses utiles
      C’est pour cela que des mots comme « delve » apparaissent de manière exagérément fréquente
      Voir à ce sujet le document AI SIGNS
    • Au final, il s’agit toujours de tirer des mots depuis une distribution de probabilités, mais cette distribution elle-même est au cœur de l’intelligence
      Les LLM apprennent justement cette distribution
    • Le simple mécanisme du « mot le plus probable », combiné à l’ensemble des connaissances humaines, acquiert une puissance considérable
      Le tourner en dérision par une simplification excessive revient à passer à côté de l’essence de la technologie

  • Intéressant que ce soit un rapport de Knuth lui-même
    Il est temps de le lire et de le comprendre sans l’aide d’un LLM

    • Je n’avais pas le temps, alors j’ai trouvé à la place un lien de résumé fait par quelqu’un d’autre