Tree-of-Thoughts (ToT)

Structure conceptuelle

                    [PROBLÈME]
                         │
                         ▼
              ┌──────────────────┐
              │  DÉCOMPOSITION   │
              │  Étape 1, 2, 3..│
              └─────────┬────────┘
                        │
            ┌───────────┼───────────┐
            │           │           │
            ▼           ▼           ▼
       [Pensée 1A] [Pensée 1B] [Pensée 1C]
            │           │           │
        [eval=8]    [eval=3]    [eval=6]
            │            X           │
            ▼                        ▼
      [Pensée 2A]              [Pensée 2C]
            │                        │
        [eval=9]                 [eval=4]
            │                         X
            ▼
      [SOLUTION]

L'élagage (X) supprime les branches faibles. L'algorithme peut être BFS, DFS, ou beam search.

Composants

1. Thought decomposer

Décompose le problème en étapes intermédiaires.

• Pour Game of 24 : "trouve 1 opération entre 2 nombres"
• Pour Creative Writing : "écris un plan en 4 paragraphes"
• Pour Math : "identifie la sous-expression à résoudre"

2. Thought generator

Génère plusieurs pensées candidates par étape.

• Sampling : appeler le LLM N fois avec température élevée
• Proposing : prompt "propose 5 manières différentes de continuer"

3. State evaluator

Score chaque état partiel.

• Value : LLM-as-judge "Évalue cette solution partielle de 0 à 10"
• Vote : LLM compare plusieurs branches "Laquelle est la plus prometteuse ?"
• Heuristique : règle déterministe (ex: nombre d'éléments restants)

4. Search algorithm

• BFS : explore par niveau, garde top-K à chaque niveau
• DFS : explore profondément, backtrack si dead-end
• Beam search : variant de BFS avec largeur fixe

Implémentation pseudo-code

def tree_of_thoughts(problem, max_depth=4, beam_width=3):
    initial_state = State(problem=problem, history=[])
    beam = [initial_state]

    for depth in range(max_depth):
        candidates = []
        for state in beam:
            # Generator : propose K thoughts depuis cet état
            next_thoughts = generate_thoughts(state, k=5)
            for thought in next_thoughts:
                new_state = state.extend(thought)
                # Evaluator : score
                score = evaluate(new_state)
                candidates.append((score, new_state))

        # Élagage : garde top beam_width
        candidates.sort(reverse=True)
        beam = [s for _, s in candidates[:beam_width]]

        # Termination
        if any(s.is_solved() for s in beam):
            return next(s for s in beam if s.is_solved())

    return max(beam, key=lambda s: evaluate(s))

Exemple : Game of 24 (du papier)

Trouver une expression mathématique avec les nombres [4, 9, 10, 13] qui donne 24.

[4, 9, 10, 13]
  │
  ├── Thought1: 13 - 9 = 4 → state [4, 4, 10]
  │     ├── Thought2: 10 - 4 = 6 → state [4, 6]
  │     │     └── Thought3: 4 × 6 = 24 ✓ FOUND
  │     └── Thought2: 4 × 4 = 16 → state [10, 16] eval=2
  │
  ├── Thought1: 10 - 4 = 6 → state [6, 9, 13]
  │     └── ... eval=4
  │
  └── Thought1: 9 + 13 = 22 → state [4, 10, 22]
        └── ... eval=2

Solution trouvée : (13 - 9) × (10 - 4) = 4 × 6 = 24

Quand l'utiliser

✅ Bons cas pour ToT :

• Problèmes avec espace de solutions large et discret (puzzles, planning)
• Tâches créatives avec contraintes multiples
• Math avec plusieurs voies de résolution
• Code génération avec plusieurs algorithmes possibles
• Décisions stratégiques avec trade-offs

❌ Mauvais cas (overkill) :

• Q&A factuel simple
• Lookup dans une knowledge base
• Génération texte sans contraintes fortes
• Tâches single-step
• Quand la latence est critique

Coût et latence

ToT consomme N × M × D appels LLM où :

• N = beam width
• M = thoughts générées par état
• D = profondeur

Pour beam=3, M=5, D=4 → ~60 appels LLM. À comparer avec 1 appel CoT.

Règle : si CoT atteint >70% de succès, ToT est rarement rentable.

Variantes et extensions

Frameworks

• LangGraph (LangChain) : graphes d'agents avec cycles, idéal pour ToT
• DSPy (Stanford) : optimisation auto de prompts ToT
• TogetherAI Mixture of Agents : variante combinant ToT et MoE

Anti-patterns

1. Beam width trop large (>5) → coût explose sans gain
2. Profondeur excessive (>6) → context overflow
3. Pas d'élagage → toutes les branches gardées = explosion combinatoire
4. Évaluateur incohérent (LLM-as-judge non calibré) → mauvais élagage
5. Pas de termination condition claire → arbre exploré inutilement
6. Utiliser ToT pour des tâches simples → CoT suffirait, ToT est gaspillage
7. Pas de cache → mêmes thoughts générées plusieurs fois
8. Pas de logging de l'arbre exploré → impossible de debug
9. Évaluateur = même LLM que générateur sans calibration → biais self-confirmation
10. Ignorer les coûts → factures qui explosent rapidement

Quand déléguer

• Pattern de raisonnement séquentiel simple → skill react-pattern (ce plugin)
• Auto-correction itérative → skill reflexion-pattern (ce plugin)
• Sélection prompts optimaux → agent prompt-engineer (ce plugin)
• Cost-aware execution → skill cost-aware-llm-pipeline (ce plugin)

Ressources

• Paper original : https://arxiv.org/abs/2305.10601
• Code original : https://github.com/princeton-nlp/tree-of-thought-llm
• Graph-of-Thoughts : https://arxiv.org/abs/2308.09687
• LangGraph (cycles + ToT) : https://langchain-ai.github.io/langgraph/