Planners-10b: Le LLM comme reducteur d’espace de recherche (side de Planners-10)

Navigation : Index | << Learning to Plan (LOOP) | [Fin de serie >>]

Neuro-Symbolic Planning, position inverse

Les notebooks 10 et 12 ont regarde le LLM et le reseau comme producteurs de plans. Ce notebook teste le positionnement inverse, formule par le moteur de recherche symbolique aicpp (Julien Livet, Apache 2.0) :

Large Language Models are most effective not as solvers, but as structural search space reducers.

Le LLM restreint l’espace (quelles primitives, quelle profondeur de composition) ; le solving reste deterministe, symbolique, inspectable. Le programme produit est une suite explicite de primitives typees, verifiee par exemples — la correction ne depend jamais du LLM.

Nous construisons un mini-DSL de 8 primitives sur des grilles colorees (format ARC-AGI), trois taches flip/color/mask, puis nous mesurons trois bras sur les memes taches :

  1. Recherche exhaustive bornee (le mur) ;
  2. LLM-direct : le modele doit rendre le programme solution ;
  3. LLM-reducteur : le modele ne rend que le sous-espace — le solveur deterministe fait le reste.

Echelle pedagogique assumee : aicpp resout 69/120 taches ARC-AGI-2 training (57,5 %) avec une architecture Neuron/Connection/Brain en C++23. Ce notebook reproduit le geste (reduire puis resoudre) sur un espace de pres de 200 millions de programmes, dont seule une fraction minuscule est traversable en session.

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez :

  1. Distinguer LLM-solver et LLM-reducteur, et ce que chaque position garantit (ou non)
  2. Construire un mini-DSL de primitives typees sur des grilles ARC-like
  3. Mesurer l’explosion combinatoire d’un espace de programmes et la borner honnetement
  4. Executer une recherche exhaustive deterministe sous budget de noeuds
  5. Comparer les trois bras (noeuds, temps, reussite) sur les memes taches
  6. Situer la these reductrice face a Learning to Plan (notebook 12) et a la veille interpretable

Prerequis

  • Avoir suivi Planners-10-LLM-Planning (prompting, limites des LLM)
  • Connaissance de base de numpy (grilles = tableaux 2D d’entiers)
  • Une cles d’API LLM (OpenRouter ou OpenAI) pour les bras 2 et 3 — les cellules verifient sa presence sans jamais l’afficher

Duree estimee : 40 minutes

1. Le positionnement inverse : reduire, pas resoudre

Le notebook 10 a montre un LLM generateur de plans : il produit la solution, avec les taux d’echec que l’on connait — plan invalide, etape inexistante, hallucination d’objet. Le notebook 12 a deplace l’apprentissage dans l’heuristique : le reseau ne rend plus un plan, il ordonne la recherche.

La these reductrice pousse le meme geste jusqu’au bout :

Position Ce que le modele rend Qui garantit la correction
LLM-solver le programme / plan final personne (on espere)
L2P (notebook 12) une heuristique apprise le solveur, en explorant
LLM-reducteur un sous-espace (primitives, profondeur) le solveur deterministe, par verification sur exemples

Le contrat est asymetrique : si le reducteur se trompe, le solveur echoue proprement (la solution n’est pas dans le sous-espace) ; s’il a raison, la solution trouvee est prouvee par exemples, independamment du modele. Le LLM n’est jamais dans la boucle de correction.

C’est exactement l’architecture d’aicpp : selection de primitives et parametrisation structurelle par LLM, puis recherche exhaustive bornee, ordonnee par cout, en C++ natif compile — 69/120 taches ARC-AGI-2 training resolues. La boucle generation-compilation-re-execution est une instance concrete du pattern plan-execute-compile discute au notebook 11.

# Imports standards
import os
import json
import time
import itertools
import numpy as np

# Client LLM (OpenRouter : agregateur compatible client OpenAI)
try:
    from openai import OpenAI
    HAS_OPENAI = True
except ImportError:
    HAS_OPENAI = False
    OpenAI = None


def load_llm_client():
    # Construit le client LLM sans jamais afficher la cles.
    # Sources essayees dans l'ordre : variable d'environnement OPENROUTER_API_KEY,
    # puis le fichier local .secrets/master.env (gitignore).
    # Retourne (client, source) ou (None, raison) si aucune cles n'est disponible.
    if not HAS_OPENAI:
        return None, "bibliotheque openai absente"
    key = os.environ.get("OPENROUTER_API_KEY")
    source = "variable d'environnement"
    if not key:
        # candidats relatifs uniquement (racine du depot ou cwd), jamais de chemin machine
        for cand in [".secrets/master.env", "../../../../.secrets/master.env"]:
            if os.path.isfile(cand):
                with open(cand, encoding="utf-8") as f:
                    for line in f:
                        if line.startswith("OPENROUTER_API_KEY="):
                            key = line.split("=", 1)[1].strip()
                            # label generique : jamais de chemin machine dans les sorties
                            source = "fichier local .secrets/master.env"
                if key:
                    break
    if not key:
        return None, "cles OPENROUTER_API_KEY introuvable"
    return OpenAI(api_key=key, base_url="https://openrouter.ai/api/v1"), source


LLM_MODEL = "openai/gpt-5"
llm_client, llm_source = load_llm_client()
if llm_client:
    print(f"Client LLM pret (cles : {llm_source}) | modele : {LLM_MODEL}")
else:
    print(f"Client LLM INDISPONIBLE ({llm_source}) : bras 2 et 3 en mode constat")
Client LLM pret (cles : variable d'environnement) | modele : openai/gpt-5

2. Le mini-DSL : huit primitives typees sur des grilles

Une grille ARC est un tableau 2D d’entiers 0-9 (0 = fond, 1-9 = couleurs). Chaque primitive est une fonction totale Grid -> Grid :

Primitive Instances Effet
flipud 1 miroir vertical
fliplr 1 miroir horizontal
rot90 1 rotation d’un quart de tour (horaire)
transpose 1 transposition principale
crop_content 1 cadre sur les cases non nulles
recolor(c1, c2) 90 (c1 != c2 dans 0-9) remplace c1 par c2
mask_keep(c) 10 garde uniquement c, le reste a 0
mask_drop(c) 10 passe c a 0

Un programme est une suite (eventuellement vide) d’instances appliquees en sequence. Compter l’espace est immediat : 115 instances par slot, profondeur au plus 4.

Grid = np.ndarray  # tableau 2D d'entiers 0-9


def flipud(g): return np.flipud(g)
def fliplr(g): return np.fliplr(g)
def rot90(g): return np.rot90(g, k=-1)          # quart de tour horaire
def transpose(g): return g.T
def crop_content(g):
    nz = np.argwhere(g != 0)
    if nz.size == 0:
        return g
    r0, c0 = nz.min(axis=0); r1, c1 = nz.max(axis=0)
    return g[r0:r1 + 1, c0:c1 + 1]


def make_recolor(c1, c2):
    def recolor(g):
        out = g.copy(); out[out == c1] = c2; return out
    return recolor


def make_mask_keep(c):
    def mask_keep(g):
        out = g.copy(); out[out != c] = 0; return out
    return mask_keep


def make_mask_drop(c):
    def mask_drop(g):
        out = g.copy(); out[out == c] = 0; return out
    return mask_drop


# Registre : nom canonique -> (arite d'arguments, factory)
DSL = {
    "flipud": (0, lambda: flipud),
    "fliplr": (0, lambda: fliplr),
    "rot90": (0, lambda: rot90),
    "transpose": (0, lambda: transpose),
    "crop_content": (0, lambda: crop_content),
    "recolor": (2, make_recolor),
    "mask_keep": (1, make_mask_keep),
    "mask_drop": (1, lambda c: make_mask_drop(c)),
}

COLORS = range(10)


def all_instances():
    # Enumere toutes les instances du DSL sous forme (nom_lisible, fonction).
    inst = []
    for name, (arity, factory) in DSL.items():
        if arity == 0:
            inst.append((name, factory()))
        elif name == "recolor":
            for c1, c2 in itertools.permutations(COLORS, 2):
                inst.append((f"recolor:{c1}:{c2}", factory(c1, c2)))
        else:
            for c in COLORS:
                inst.append((f"{name}:{c}", factory(c)))
    return sorted(inst, key=lambda t: t[0])


INSTANCES = all_instances()
INSTANCE_LOOKUP = dict(INSTANCES)
print(f"Primitives : {len(DSL)} | Instances par slot : {len(INSTANCES)}")
n = len(INSTANCES)
MAX_DEPTH = 4
print(f"Espace total (profondeur <= {MAX_DEPTH}) : "
      f"{n} + {n}**2 + {n}**3 + {n}**4 = "
      f"{sum(n ** d for d in range(1, MAX_DEPTH + 1)):,} programmes")
Primitives : 8 | Instances par slot : 115
Espace total (profondeur <= 4) : 115 + 115**2 + 115**3 + 115**4 = 176,434,840 programmes

La definition est compacte mais elle porte un engagement fort : huit primitives, et un espace de programmes qui croit vite. Le sanity de la cellule suivante ne teste pas des cas d’usage — il verifie des invariants structurels : les symetries (flipud, fliplr, rot90, transpose) doivent composer vers l’identite, et les filtres (recolor, mask_keep) doivent etre sans effet hors de leur domaine. C’est le genre de propriete qu’un solveur exploitera comme heuristique de coupe, et qu’un test unitaire capture mieux qu’un exemple.

# Sanity du DSL : fonctions totales Grid -> Grid, involutivites connues
g = np.array([[1, 2, 0], [3, 0, 2], [0, 1, 5], [3, 3, 0]])
checks = {
    "flipud x2 = id": np.array_equal(flipud(flipud(g)), g),
    "fliplr x2 = id": np.array_equal(fliplr(fliplr(g)), g),
    "rot90 x4 = id": np.array_equal(rot90(rot90(rot90(rot90(g)))), g),
    "transpose x2 = id": np.array_equal(transpose(transpose(g)), g),
    "recolor sans effet si c absent": np.array_equal(make_recolor(8, 9)(g), g),
    "mask_keep(c) ne garde que c": set(np.unique(make_mask_keep(2)(g))) <= {0, 2},
}
for k, v in checks.items():
    print(("OK  " if v else "FAIL"), k)
OK   flipud x2 = id
OK   fliplr x2 = id
OK   rot90 x4 = id
OK   transpose x2 = id
OK   recolor sans effet si c absent
OK   mask_keep(c) ne garde que c

Les six lignes OK ne sont pas triviales : elles prouvent que le DSL est ferme — chaque primitive est une fonction totale Grid -> Grid, et les involutions (x2 = id, x4 = id) sont vraies pour toute grille, pas seulement les exemples. Une primitive qui violerait ces invariants ferait degenerer la recherche en espace infini. Cette fermeture est la condition de possibilite du comptage d’espace qui suit : sans elle, le nombre de programmes serait un mensonge, car des programmes divergents échapperaient au recensement.

3. Trois taches ARC-like : flip, isolation, composition

Chaque tache fournit deux exemples d’entrainement (la solution doit reproduire les deux sorties) et une grille de test (generalisation). Les solutions attendues montent en profondeur :

  • T1 Miroir teinte : flipud puis recolor(3, 5) — profondeur 2, mais l’instance recolor:3:5 est une aiguille dans 90 bottes de foin ;
  • T2 Isoler la forme : mask_keep(4) puis crop_content — profondeur 2 ;
  • T3 Retourner, isoler, cadrer : flipud puis mask_keep(4) puis crop_content — profondeur 3. Trois effets independants (geometrique, masque, cadrage) qu’aucune primitive ne combine : la solution la plus courte possible fait 3 etapes. C’est la tache du mur.

Remarque de conception : les grilles sont non carrees — sur une grille carree, des compositions du groupe des symetries du carre se reduisent a un simple flip (par exemple transpose apres rot90 redonne flipud), et la tache “profondeur 3” n’en serait pas une. Les grilles rectangulaires ecartent ces equivalents.

def grid(*rows):
    return np.array(rows, dtype=int)


def show(g):
    return "\n".join(" ".join(str(v) for v in row) for row in g)


TASKS = {}

# --- T1 : miroir vertical, puis la couleur 3 devient 5 -----------------------
t1a_in = grid([3, 0, 2], [1, 3, 0], [0, 2, 3], [3, 3, 1])
t1a_out = make_recolor(3, 5)(flipud(t1a_in))
t1b_in = grid([3, 2, 2, 0], [0, 3, 1, 3], [2, 0, 3, 0])
t1b_out = make_recolor(3, 5)(flipud(t1b_in))
t1_test = grid([3, 1, 0, 3], [2, 3, 3, 0], [0, 0, 3, 2], [1, 3, 2, 3], [3, 3, 0, 1])
TASKS["T1 miroir teinte"] = {
    "train": [(t1a_in, t1a_out), (t1b_in, t1b_out)], "test": t1_test,
    "solution": ["flipud", "recolor:3:5"]}

# --- T2 : garder la couleur 4, puis cadrer sur le contenu --------------------
# (les 4 strictement interieurs : le cadrage n'est pas un no-op,
#  et du contenu non-4 hors de la boite des 4 rend l'ordre masque->cadre obligatoire)
t2a_in = grid([1, 0, 7, 0], [0, 4, 0, 4], [0, 0, 4, 0], [2, 0, 0, 0])
t2a_out = crop_content(make_mask_keep(4)(t2a_in))
t2b_in = grid([9, 0, 0, 0, 8], [0, 4, 0, 0, 0], [0, 0, 4, 4, 0])
t2b_out = crop_content(make_mask_keep(4)(t2b_in))
t2_test = grid([5, 0, 0, 0], [0, 4, 0, 4], [0, 0, 4, 0], [6, 0, 0, 0])
TASKS["T2 isoler la forme"] = {
    "train": [(t2a_in, t2a_out), (t2b_in, t2b_out)], "test": t2_test,
    "solution": ["mask_keep:4", "crop_content"]}

# --- T3 : retourner, isoler les 4, cadrer (profondeur 3 exacte) --------------
t3a_in = grid([0, 4, 0, 2], [7, 0, 4, 0], [0, 4, 0, 0], [2, 0, 0, 4])
t3a_out = crop_content(make_mask_keep(4)(flipud(t3a_in)))
t3b_in = grid([4, 9, 0, 4, 0], [0, 0, 4, 0, 1], [6, 4, 0, 0, 0])
t3b_out = crop_content(make_mask_keep(4)(flipud(t3b_in)))
t3_test = grid([0, 4, 0, 8], [4, 0, 4, 0], [3, 0, 0, 0], [0, 4, 5, 4])
TASKS["T3 retourner-isoler-cadrer"] = {
    "train": [(t3a_in, t3a_out), (t3b_in, t3b_out)], "test": t3_test,
    "solution": ["flipud", "mask_keep:4", "crop_content"]}

for name, t in TASKS.items():
    print(f"--- {name} | solution attendue : {' >> '.join(t['solution'])}")
--- T1 miroir teinte | solution attendue : flipud >> recolor:3:5
--- T2 isoler la forme | solution attendue : mask_keep:4 >> crop_content
--- T3 retourner-isoler-cadrer | solution attendue : flipud >> mask_keep:4 >> crop_content

Les trois taches sont des transformations de grille a solution courte : deux ou trois primitives suffisent. Ce choix n’est pas gratuit — une tache dont la solution exigerait huit primitives rendrait la comparaison des trois bras moins lisible, car chaque bras aurait un espace de recherche different. La cellule suivante verifie que la solution attendue est bien correcte : elle sert d’oracle pour les trois bras, car un solveur qui annonce TROUVE ne peut etre cru que si sa solution passe cette verification.

# Verification : chaque tache est bien resolue par sa solution attendue
import functools


def compose(prog, gin):
    return functools.reduce(lambda acc, f: f(acc),
                            [INSTANCE_LOOKUP[s] for s in prog], gin)


for name, t in TASKS.items():
    ok = all(np.array_equal(compose(t["solution"], gin), gout)
             for gin, gout in t["train"])
    print(("OK  " if ok else "FAIL"), name, "->", " >> ".join(t["solution"]))
OK   T1 miroir teinte -> flipud >> recolor:3:5
OK   T2 isoler la forme -> mask_keep:4 >> crop_content
OK   T3 retourner-isoler-cadrer -> flipud >> mask_keep:4 >> crop_content

Le verdict OK confirme l’oracle : pour chaque tache, la solution attendue produit bien la grille cible. C’est le point de reference qui rend les trois bras comparables. Sans cet oracle, TROUVE serait un verdict non falsifiable — n’importe quel programme serait un succes et la these du reducteur s’effondrerait. La verification est donc le socle methodologique du reste du notebook, pas une formalite.

4. Bras 1 — la recherche exhaustive bornee (le mur)

Le solveur enumere les programmes par profondeur croissante, ordre lexicographique des instances — completement deterministe. Il s’arrete au premier programme qui reproduit tous les exemples d’entrainement. Le budget de 15 000 noeuds (une fraction infime de l’espace) encode le mur : au-dela, echec mesure, pas attente opaque.

Trois quantites separent honnetement ce qui est mesure de ce qui est extrapole :

  • noeuds explores, temps, verdict : mesures ;
  • temps total de l’espace complet : extrapolation depuis le debit mesure (noeuds/seconde), jamais execute.
BUDGET_NODES = 15_000


def apply_program(prog_names, g):
    for step in prog_names:
        g = INSTANCE_LOOKUP[step](g)
    return g


def solves(prog_names, task):
    return all(np.array_equal(apply_program(prog_names, gin), gout)
               for gin, gout in task["train"])


def exhaustive_solve(task, instances=None, max_depth=MAX_DEPTH,
                     budget=BUDGET_NODES, time_budget_s=120):
    # DFS par profondeur croissante. Rend (verdict, programme, noeuds, secondes).
    if instances is None:
        instances = INSTANCES
    t0 = time.perf_counter()
    nodes = 0
    for depth in range(1, max_depth + 1):
        for combo in itertools.product(instances, repeat=depth):
            nodes += 1
            if nodes > budget or (time.perf_counter() - t0) > time_budget_s:
                return ("BUDGET_DEPASSE", None, nodes, time.perf_counter() - t0)
            names = [n_ for n_, _ in combo]
            if solves(names, task):
                return ("TROUVE", names, nodes, time.perf_counter() - t0)
    return ("INTROUVABLE_DEPTH", None, nodes, time.perf_counter() - t0)


results_b1 = {}
for name, task in TASKS.items():
    verdict, prog, nodes, secs = exhaustive_solve(task)
    results_b1[name] = (verdict, prog, nodes, secs)
    print(f"{name:26s} {verdict:16s} noeuds={nodes:7,d} temps={secs:6.3f}s prog={prog}")
T1 miroir teinte           TROUVE           noeuds=    400 temps= 0.003s prog=['flipud', 'recolor:3:5']
T2 isoler la forme         TROUVE           noeuds=  2,071 temps= 0.009s prog=['mask_keep:4', 'crop_content']
T3 retourner-isoler-cadrer BUDGET_DEPASSE   noeuds= 15,001 temps= 0.080s prog=None

Le bras 1 est le mur. T1 et T2 sont resolus en quelques milliers de noeuds, mais T3 depasse le budget de 15,000 noeuds sans solution. Ce n’est pas un echec du solveur — c’est la geometrie de l’espace : apres 15,001 noeuds, la recherche exhaustive a couvert une fraction negligeable des 176 millions de programmes, et toute solution situee plus loin est structurellement hors d’atteinte. Le temps de 0.080s pour 15,001 noeuds montre que le solveur n’est pas lent : c’est l’espace qui est immense.

# Debit mesure -> extrapolation honnete du mur (jamais execute en entier)
rate = np.mean([results_b1[n_][3] / max(results_b1[n_][2], 1) for n_ in TASKS])
n = len(INSTANCES)
total_space = sum(n ** d for d in range(1, MAX_DEPTH + 1))
print(f"Debit mesure : {1 / rate:,.0f} noeuds/seconde (moyenne des taches executees)")
print(f"Espace complet : {total_space:,} programmes")
print(f"Temps total extrapole : {total_space * rate:,.0f} s "
      f"= {total_space * rate / 3600:,.1f} heures")
print()
print(f"Le budget de {BUDGET_NODES:,} noeuds couvre ~{100 * BUDGET_NODES / total_space:.1f} % de l'espace.")
print("Une solution situee apres le budget est INACCESSIBLE au bras 1 : c'est le mur a reduire.")
Debit mesure : 169,038 noeuds/seconde (moyenne des taches executees)
Espace complet : 176,434,840 programmes
Temps total extrapole : 1,044 s = 0.3 heures

Le budget de 15,000 noeuds couvre ~0.0 % de l'espace.
Une solution situee apres le budget est INACCESSIBLE au bras 1 : c'est le mur a reduire.

L’extrapolation est le chiffre qui porte la these. A 169,038 noeuds/seconde, explorer l’espace complet prendrait 1,044 secondes — soit environ 0.3 heures de calcul continu. Mais le budget de la cellule precedente ne couvre que ~0.0 % de cet espace. La consequence est brute : une solution qui vit dans la zone non exploree est inaccessible au bras 1, non par lenteur mais par budget. C’est exactement le mur que les bras 2 et 3 vont tenter de reduire — et c’est pour cela que la reduction est la vraie question, pas la vitesse.

5. Bras 2 — LLM-direct : solver ou illusion ?

Le modele recoit la documentation du DSL et les exemples d’entrainement serialises, et doit rendre le programme solution en JSON strict. Rien ne guide sa reponse : soit il inferere la transformation, soit non. On mesure la reussite verifiee sur les exemples — une reponse qui ne matche pas les exemples compte echec, meme si elle ressemble a une solution. Une relance unique est accordee si la reponse est illisible (les modeles raisonneurs consomment parfois tout leur budget de tokens en raisonnement interne) ; elle est mesuree et rapportee dans les sorties.

SYSTEM_PROMPT = (
    "Tu es un solveur de puzzles de grilles. Tu disposes d'un DSL de primitives "
    "sur des grilles d'entiers 0-9 : flipud, fliplr, rot90 (quart de tour horaire), "
    "transpose, crop_content (cadre sur les cases non nulles), recolor:c1:c2 "
    "(c1 devient c2), mask_keep:c (garde uniquement c), mask_drop:c (passe c a 0). "
    "Un programme est une liste d'instances appliquees en sequence. "
    "Reponds UNIQUEMENT en JSON : {\"program\": [\"primitive(:args)\", ...]}. "
    "Le programme doit transformer chaque entree en sa sortie. Programmes courts d'abord."
)

REDUCER_PROMPT = (
    "Tu es un ANALYSTE d'espace de recherche, PAS un solveur. Observe les exemples "
    "et ne rends PAS la solution : rends UNIQUEMENT le sous-espace de recherche "
    "plausible. Reponds en JSON strict : "
    "{\"primitives\": [au plus 3 noms parmi flipud, fliplr, rot90, transpose, "
    "crop_content, recolor, mask_keep, mask_drop], \"max_depth\": 1, 2 ou 3}. "
    "recolor/mask_keep/mask_drop comptent pour UNE primitive (leurs arguments restent libres). "
    "Choisis le sous-espace MINIMAL dans lequel la solution semble vivre."
)


def serialize_task(task):
    parts = []
    for i, (gin, gout) in enumerate(task["train"]):
        parts.append(f"exemple {i + 1} entree:\n{show(gin)}\n"
                     f"exemple {i + 1} sortie:\n{show(gout)}")
    return "\n\n".join(parts)


def call_llm(system, user, max_completion_tokens=8000):
    # Les modeles raisonneurs ne supportent ni temperature ni seed :
    # deux executions peuvent differer (le solveur, lui, reste deterministe).
    # Budget large : le raisonnement interne consomme les tokens avant la reponse.
    resp = llm_client.chat.completions.create(
        model=LLM_MODEL,
        messages=[{"role": "system", "content": system},
                  {"role": "user", "content": user}],
        max_completion_tokens=max_completion_tokens)
    return resp.choices[0].message.content or ""


def call_llm_json(system, user):
    # Un appel + AU PLUS une relance si la reponse est illisible.
    # Rend (parsed, essais). La relance est mesuree et rapportee.
    for attempt in (1, 2):
        raw = call_llm(system, user)
        parsed = parse_json_block(raw)
        if parsed is not None:
            return parsed, attempt
    return None, 2


def parse_json_block(text):
    # Extrait le premier objet JSON d'une reponse (tolere les fences markdown).
    text = text.strip()
    if "```" in text:
        for block in text.split("```"):
            block = block.removeprefix("json").strip()
            if block.startswith("{"):
                text = block
                break
    start, end = text.find("{"), text.rfind("}")
    if start == -1 or end <= start:
        return None
    try:
        return json.loads(text[start:end + 1])
    except json.JSONDecodeError:
        return None


print("Helpers prets. Client :", "OK" if llm_client else "ABSENT")
Helpers prets. Client : OK

Ce bras change de contrat : au lieu d’explorer l’espace, on demande au LLM de produire directement le programme. Il n’y a pas de comptage de noeuds ici — la question est celle du verdict immediat : le programme rendu est-il correct selon l’oracle ? La cellule suivante applique ce verdict a chaque tache, et c’est ce qui distingue un vrai solver d’une illusion de solver.

# Bras 2 : le LLM rend directement le programme — verdict VERIFIE sur les exemples
results_b2 = {}
if llm_client:
    for name, task in TASKS.items():
        try:
            parsed, essais = call_llm_json(SYSTEM_PROMPT, serialize_task(task))
            prog = parsed.get("program") if isinstance(parsed, dict) else None
            if isinstance(prog, list) and prog and solves(prog, task):
                verdict, kept = "TROUVE", prog
            elif isinstance(prog, list) and prog:
                verdict, kept = "NE_MATCH_PAS", prog
            else:
                verdict, kept = "PARSE_FAIL", None
        except Exception as e:
            verdict, kept, essais = f"ERREUR_API ({type(e).__name__})", None, 1
        results_b2[name] = (verdict, kept)
        print(f"{name:26s} {verdict:14s} essais={essais} prog={kept}")
else:
    print("Client LLM absent : bras 2 non execute (constat affiche, pas de substitution).")
T1 miroir teinte           TROUVE         essais=1 prog=['recolor:3:5', 'flipud']
T2 isoler la forme         TROUVE         essais=1 prog=['mask_keep:4', 'crop_content']
T3 retourner-isoler-cadrer TROUVE         essais=1 prog=['mask_keep:4', 'crop_content', 'flipud']

Le verdict est honnete : le LLM trouve les trois solutions en un seul essai. Mais ce n’est pas une preuve de capacite generale — c’est un resultat sur trois taches a solution courte, dans un DSL de huit primitives. Le bras 2 repond vite, mais il ne garantit rien sur le reste de l’espace : il peut se tromper hors de ces trois cas, et il ne produit aucun comptage de noeuds ni certificat de correction. C’est la faiblesse que le bras 3 adresse : garder la vitesse du LLM, mais lui faire reduire au lieu de trancher.

6. Bras 3 — le LLM comme reducteur d’espace

Le meme modele, un prompt system different : il ne rend ni programme ni solution, seulement un sous-espace — au plus 3 primitives et une borne de profondeur. Le solveur deterministe du bras 1 tourne a l’identique dans ce sous-espace restreint : ce sont les instances candidates qui changent, pas l’algorithme ni la verification.

Deux issues possibles, toutes deux informatives :

  • la solution vit dans le sous-espace : le solveur la trouve, prouvee par exemples ;
  • elle n’y vit pas : echec propre du bras 3 — le reducteur s’est trompe, et personne n’a pretendu le contraire.

C’est le contrat de la these : la reduction n’achete pas la correction, elle achete la traversabilite.

# Bras 3 : reduction LLM -> sous-espace -> MEME solveur deterministe
results_b3 = {}
if llm_client:
    for name, task in TASKS.items():
        try:
            parsed, essais = call_llm_json(REDUCER_PROMPT, serialize_task(task))
            prim_sel = parsed.get("primitives") if isinstance(parsed, dict) else None
            depth = parsed.get("max_depth") if isinstance(parsed, dict) else None
            if not (isinstance(prim_sel, list) and prim_sel
                    and isinstance(depth, int) and 1 <= depth <= 3):
                results_b3[name] = ("PARSE_FAIL", None, None, None, None)
                print(f"{name:26s} PARSE_FAIL (essais={essais})")
                continue
            base = lambda s: s.split(":")[0]
            sub = [(nm, f) for nm, f in INSTANCES if base(nm) in prim_sel]
            sub_size = sum(len(sub) ** d for d in range(1, depth + 1))
            verdict, prog, nodes, secs = exhaustive_solve(
                task, instances=sub, max_depth=depth, budget=BUDGET_NODES)
            results_b3[name] = (verdict, prog, nodes, secs,
                                (prim_sel, depth, sub_size))
            print(f"{name:26s} {verdict:16s} sous-espace={sub_size:6,d} "
                  f"noeuds={nodes:6,d} temps={secs:5.3f}s essais={essais} "
                  f"sel={prim_sel} depth={depth} prog={prog}")
        except Exception as e:
            results_b3[name] = (f"ERREUR_API ({type(e).__name__})", None, None, None, None)
            print(f"{name:26s} ERREUR_API ({type(e).__name__})")
else:
    print("Client LLM absent : bras 3 non execute (constat affiche, pas de substitution).")
T1 miroir teinte           TROUVE           sous-espace= 8,372 noeuds=   124 temps=0.001s essais=1 sel=['flipud', 'recolor'] depth=2 prog=['flipud', 'recolor:3:5']
T2 isoler la forme         TROUVE           sous-espace=   132 noeuds=    67 temps=0.000s essais=1 sel=['mask_keep', 'crop_content'] depth=2 prog=['mask_keep:4', 'crop_content']
T3 retourner-isoler-cadrer TROUVE           sous-espace= 1,884 noeuds=   373 temps=0.003s essais=1 sel=['mask_keep', 'crop_content', 'flipud'] depth=3 prog=['flipud', 'mask_keep:4', 'crop_content']

La mesure de reduction est le coeur de la these. Pour T2, le sous-espace propose par le LLM ne contient que 132 programmes contre 176,434,840 au depart : une reduction d’un facteur 1,336,628. Le solveur deterministe ne parcourt alors que 67 noeuds — contre 2,071 a l’exhaustif. T3, inaccessible au bras 1, est trouve en 373 noeuds dans un sous-espace de 1,884. Le LLM ne resout pas ici : il digine l’espace, et le solveur fait le reste. La reduction, pas la magie, est le mecanisme.

7. Comparaison honnete des trois bras

Les trois bras ont affronte les memes taches. La table finale rassemble les mesures brutes : noeuds explores, temps, verdict verifie. Les echecs sont des donnees — un LLM-direct qui se trompe ou un reducteur trop etroit sont des resultats, pas des accidents a maquiller.

# Table finale : 3 taches x 3 bras
header = (f"{'Tache':26s} | {'Bras 1 exhaustif':36s} | "
          f"{'Bras 2 LLM-direct':30s} | {'Bras 3 LLM-reducteur':44s}")
print(header)
print("-" * len(header))
for name in TASKS:
    v1, p1, n1, s1 = results_b1[name]
    b1 = f"{v1} ({n1:,} nds, {s1:.1f}s)"
    if name in results_b2:
        v2, p2 = results_b2[name]
        b2 = f"{v2} {' '.join(p2) if p2 else ''}"[:30]
    else:
        b2 = "non execute"
    r3 = results_b3.get(name)
    if r3 and r3[4] is not None:
        v3, p3, n3, s3, (sel, d3, sub) = r3
        b3 = f"{v3} ({n3:,}/{sub:,} nds, {s3:.1f}s)"[:44]
    else:
        b3 = "non execute"
    print(f"{name:26s} | {b1:36s} | {b2:30s} | {b3:44s}")

# Espace total vs sous-espaces : le rapport de reduction, mesure
n = len(INSTANCES)
total = sum(n ** d for d in range(1, MAX_DEPTH + 1))
reductions = [(nm, r[4]) for nm in TASKS
              if (r := results_b3.get(nm)) is not None and r[4] is not None]
if reductions:
    print()
    for name, (sel, d3, sub) in reductions:
        print(f"{name:26s} reduction x{total / sub:,.0f} "
              f"({total:,} -> {sub:,} programmes, profondeur <= {d3})")
Tache                      | Bras 1 exhaustif                     | Bras 2 LLM-direct              | Bras 3 LLM-reducteur                        
-------------------------------------------------------------------------------------------------------------------------------------------------
T1 miroir teinte           | TROUVE (400 nds, 0.0s)               | TROUVE recolor:3:5 flipud      | TROUVE (124/8,372 nds, 0.0s)                
T2 isoler la forme         | TROUVE (2,071 nds, 0.0s)             | TROUVE mask_keep:4 crop_conten | TROUVE (67/132 nds, 0.0s)                   
T3 retourner-isoler-cadrer | BUDGET_DEPASSE (15,001 nds, 0.1s)    | TROUVE mask_keep:4 crop_conten | TROUVE (373/1,884 nds, 0.0s)                

T1 miroir teinte           reduction x21,074 (176,434,840 -> 8,372 programmes, profondeur <= 2)
T2 isoler la forme         reduction x1,336,628 (176,434,840 -> 132 programmes, profondeur <= 2)
T3 retourner-isoler-cadrer reduction x93,649 (176,434,840 -> 1,884 programmes, profondeur <= 3)

Lecture : ce que la these dit, et ce qu’elle ne dit pas

Trois enseignements se lisent sur les chiffres ci-dessus :

  1. Le mur est reel mais pas uniforme : les taches de profondeur 2 tombent en centaines ou milliers de noeuds ; la profondeur 3 plonge la solution au coeur d’un espace de pres de 200 millions de programmes — hors budget. L’ordre lexicographique determine si elle tombe avant ou apres la coupe.
  2. LLM-direct est sans garantie : meme reussi, le programme rendu n’est accepte qu’apres verification par exemples — c’est le solveur qui certifie, jamais le modele. Un echec de parse ou de match est un resultat normal de cette position, pas un bug.
  3. Le reducteur deplace le mur : le sous-espace selectionne traverse en une fraction du budget. Si la selection rate une primitive necessaire, l’echec est propre et diagnostique (INTROUVABLE dans un petit espace, pas un timeout opaque). La correction reste entierement cote solveur.

Deux precautions honnetes : les appels LLM ne fixent ni temperature ni seed (non supportes par les modeles raisonneurs) — deux executions du notebook peuvent differer sur les bras 2 et 3, jamais sur le bras 1 ; et chaque appel a un cout. En production de recherche, aicpp pousse ce contrat jusqu’a la boucle compilee C++ et aux 69/120 taches ARC-AGI-2 training ; ce notebook en reste au geste, volontairement inspectable ligne a ligne.

8. Ponts et precautions

  • Planners-10 : le LLM generateur de plans — la position que la these reductrice remet en cause, avec les memes symptomes (hallucination d’etapes, plans invalides).
  • Planners-11 : la boucle plan-execute-compile d’aicpp (C++ genere, recompile, reexecute) est une instance concrete du pattern unifie.
  • Planners-12 : Learning to Plan apprend la representation ; le reducteur LLM la demande. Deux facons de ne pas laisser le modele resoudre.
  • Serie SymbolicLearning : les primitives typees et la memoire structurelle d’aicpp resonnent avec le library learning interpretable (compressibilite par abstractions reutilisables).
  • Taxonomie Argumentum : la reduction d’espace se rejoue sur l’arbre de sophismes de la serie Argument_Analysis ; scripts/fallacy_detection/argumentum_taxonomy_explorer.py --reduction-measure y mesure les bornes structurelles de la descente guidee (lecture systematique contre chemin cible, guide aveugle en controle negatif) — le pendant deterministe du bras 3, sans appel LLM.
  • ARC-AGI : ce benchmark fait ici une apparition miniaturisee, sur le sous-ensemble flip/color/mask des transformations.

Precautions sur la source : aicpp (Julien Livet, Apache 2.0) est un depot jeune et actif (cree janvier 2026) ; toute execution du moteur reel doit figer un commit precis. Les auteurs le presentent eux-memes comme non-production ARC solver — exploration de recherche, pas produit. Ce notebook cite et s’inspire du positionnement ; il ne porte pas leur code.

9. Resume

Concept En une phrase
LLM-solver le modele rend la solution ; rien ne la garantit
LLM-reducteur le modele restreint l’espace ; le solveur deterministe garantit la solution
Budget de noeuds le mur rendu mesurable : echec propre au-dela, pas d’attente opaque
Verification par exemples la seule source de correction, toujours cote solveur
Echec de reduction une donnee diagnostiquee (INTROUVABLE en petit espace), pas une faute du solveur

Fil conducteur de la serie : du LLM prompte (10) a l’interface unifiee (11), du plan appris (12) a l’espace reduit (13) — l’agent qui cherche change, la structure symbolique persiste.

Exercice 1 : etendre le DSL d’une primitive

Ajoutez swap_colors(c1, c2) (echange deux couleurs) au registre, puis construisez une tache dont la solution est swap_colors:2:7 suivi de flipud. Montrez — en executant le solveur du bras 1 sur votre tache — que le solveur n’a pas change d’une ligne : seule l’enumeration des instances s’est enrichie. C’est la propriete qui fait la valeur d’un DSL.

# Exercice 1 : TODO etudiant
# 1. Definissez make_swap_colors(c1, c2) sur le modele de make_recolor
# 2. Ajoutez "swap_colors" au registre DSL (arite 2)
# 3. Reconstruisez INSTANCES et verifiez le nouveau total
# 4. Construisez une tache a solution ["swap_colors:2:7", "flipud"]
# 5. Lancez exhaustive_solve dessus et rapportez noeuds/temps
def make_swap_colors(c1, c2):
    # TODO etudiant : renvoyer la grille avec c1 et c2 echanges
    return None
print("Exercice a completer")
Exercice a completer

Exercice 2 : construire une tache qui resiste au reducteur

Construisez une tache dont la solution exige mask_drop — une primitive que le reducteur LLM a peu de chances de placer dans son top-3 pour un puzzle de couleurs. Executez le bras 3 : attendez-vous a un INTROUVABLE propre dans le sous-espace. C’est le cout structurel de la reduction : un sous-espace faux est muet sur ce qui lui manque.

# Exercice 2 : TODO etudiant
# 1. Construisez une tache (2 exemples + test) a solution ["mask_drop:9", "fliplr"]
# 2. Verifiez que le bras 1 la trouve (profondeur 2)
# 3. Simulez un reducteur qui selectionne ["flipud", "recolor", "crop_content"]
#    et lancez exhaustive_solve dans ce sous-espace : constatez l'echec propre
print("Exercice a completer")
Exercice a completer

Exercice 3 : reduire sans LLM — l’heuristique de longueur de description

Implementez un reducteur deterministe MDL-lite : pour chaque primitive, mesurez si elle rapproche l’entree de la sortie (nombre de cellules differentes apres application, moyenne sur les exemples) et gardez les 3 meilleures. Comparez son sous-espace a celui du LLM sur les trois taches : les deux reductions selectionnent-elles les memes primitives ?

# Exercice 3 : TODO etudiant
# 1. Score(primitive) = nombre de cellules differentes entre entree et sortie,
#    moyenne sur les exemples (une primitive utile rapproche la sortie)
# 2. Gardez les 3 primitives au meilleur score, profondeur 2
# 3. Lancez le solveur dans ce sous-espace et comparez aux results_b3
print("Exercice a completer")
Exercice a completer
Retour au sommet