Phase 14 - Lesson 04

Tree of Thoughts y LATS: Búsqueda Deliberada

Una única trayectoria de chain-of-thought no tiene margen para retroceder (backtrack). ToT (Yao et al., 2023) transforma el razonamiento en un árbol con autoevaluación en cada nodo. LATS (Zhou et al., 2024) unifica ToT con ReAct y Reflexion bajo Monte Carlo Tree Search. Game of 24 pasa de 4% (CoT) a 74% (ToT); LATS alcanza 92.7% de pass@1 en HumanEval.

Tipo: Build Idiomas: Python (stdlib) Prerrequisitos: Phase 14 · 01 (Agent Loop), Phase 14 · 03 (Reflexion) Tiempo: ~75 minutos

Objetivos de Aprendizaje

• Formular el razonamiento como búsqueda: los nodos son "pensamientos" (thoughts), las aristas son "expansiones" y el valor es "qué tan prometedor" es el nodo.
• Implementar una búsqueda en árbol BFS al estilo ToT utilizando solo la biblioteca estándar (stdlib) con puntuación de autoevaluación.
• Extender a un bucle MCTS LATS simplificado con las fases select / expand / simulate / backpropagate.
• Decidir cuándo la búsqueda vale el multiplicador de tokens (Game of 24, generación de código) y cuándo una sola trayectoria es suficiente (Q&A simple).

El Problema

Chain-of-thought es una trayectoria lineal. Si el primer paso es incorrecto, cada paso posterior funcionará sobre una premisa errónea. En Game of 24 (usar cuatro dígitos con + − × ÷ para obtener 24), CoT con GPT-4 alcanza un 4% de precisión. El modelo elige la subexpresión incorrecta al principio y no puede recuperarse.

Lo que el razonamiento necesita es la capacidad de proponer múltiples candidatos, evaluarlos, elegir los prometedores y retroceder cuando aparecen callejones sin salida. Eso es búsqueda. Tree of Thoughts y LATS son las dos formulaciones canónicas.

El Concepto

Tree of Thoughts (Yao et al., NeurIPS 2023)

Cada nodo es un paso intermedio coherente ("un pensamiento" o "thought"). Cada nodo puede expandirse a K pensamientos hijos. El LLM se autoevalúa en cada nodo con un prompt de puntuación. La búsqueda explora el árbol: BFS, DFS o beam search.

                     (root: "find 24 from 4 6 4 1")
                    /               |            \
           ("6 - 4 = 2")    ("4 + 1 = 5")    ("4 * 6 = 24")  <- Score: HIGH
              /   \              |                  |
          ...    ...          ...                finish

La autoevaluación es la pieza fundamental. El artículo muestra tres variantes: clasificación sure / likely / impossible, puntuación numérica de 1..10 y votación entre candidatos. Las tres superan sustancialmente a CoT en Game of 24 (4% -> 74% con GPT-4).

LATS (Zhou et al., ICML 2024)

LATS unifica ToT, ReAct y Reflexion bajo MCTS. El LLM desempeña tres roles:

• Policy: proponer candidatas a próximas acciones (estilo ReAct).
• Value function: puntuar una trayectoria parcial (autoevaluación estilo ToT).
• Self-reflector: en caso de fallo, escribir una reflexión en lenguaje natural (estilo Reflexion) y usarla para orientar futuros rollouts.

La retroalimentación del entorno (observaciones) se integra en la value function para que la búsqueda esté informada por resultados reales de herramientas, no solo por las opiniones del modelo. Resultados al momento del artículo: HumanEval pass@1 de 92.7% con GPT-4 (SOTA), promedio de WebShop de 75.9 con GPT-3.5 (cercano al ajuste fino basado en gradientes).

MCTS Simplificado

Cuatro fases por iteración:

1. Select: caminar desde la raíz hasta una hoja usando UCT (cota superior de confianza para árboles).
2. Expand: generar K hijos a través de la policy.
3. Simulate: realizar un rollout desde un hijo usando la policy, puntuar la hoja con la value function (o recompensa del entorno).
4. Backpropagate: actualizar los conteos de visitas y las estimaciones de valor a lo largo del camino.

Fórmula de UCT: Q(s, a) + c * sqrt(ln N(s) / N(s, a)). El primer término es explotación; el segundo es exploración. Ajuste c por tarea.

La Realidad de los Costos

La búsqueda consume una cantidad explosiva de tokens. ToT en Game of 24 utiliza de 100 a 1000 veces más tokens que CoT. LATS es similar. Esto no es gratuito; reserve la búsqueda para:

• Tareas en las que una sola trayectoria es demostrablemente insuficiente (Game of 24, código complejo).
• Tareas en las que el tiempo de ejecución es menos importante que la precisión.
• Tareas con una value function económica y confiable (pruebas unitarias para código, objetivo explícito para matemáticas).

Si su tarea tiene una única respuesta correcta y un evaluador con ruido, la búsqueda a menudo empeora las cosas: encuentra una respuesta incorrecta con una "buena puntuación".

Posicionamiento en 2026

La mayoría de los agentes en producción no ejecutan LATS. Utilizan ReAct con verificación basada en herramientas (CRITIC, Lesson 05). La búsqueda aparece en nichos especializados:

• Agentes de codificación que ejecutan pruebas como value function (estilo HumanEval).
• Agentes de investigación profunda (deep-research) que exploran múltiples rutas de consulta.
• Flujos de trabajo con gran carga de planificación dentro de subgráficos de LangGraph.

AlphaEvolve (Lesson 11) es el extremo de 2025: búsqueda evolutiva sobre código, aptitud (fitness) verificable por máquina y ganancias de frontera (primera mejora en multiplicación de matrices de 4x4 en 56 años).

Build It

code/main.py implementa:

• Un BFS ToT minúsculo en una tarea estilizada de "selección de operaciones aritméticas".
• Un bucle MCTS LATS simplificado en la misma tarea (Select / Expand / Simulate / Backpropagate) con selección UCT.
• Una value function que compone una puntuación simbólica más una puntuación de autoevaluación.

Run it:

python3 code/main.py

El trace muestra a ToT expandiendo tres candidatos por nodo con BFS, en comparación con LATS convergiendo en el mejor rollout a través de MCTS. Se muestran los conteos de tokens para ambos.

Use It

LangGraph ofrece exploración al estilo ToT como patrones de subgráficos; el blog del equipo de LangChain sobre LATS (mayo de 2024) es el tutorial de referencia. LlamaIndex ofrece un agente TreeOfThoughts. Para la mayoría de los agentes de producción de 2026, este patrón vive detrás de una condicional if task_complexity > threshold: use_search() — vea el patrón evaluador-optimizador en la Lesson 05.

Ship It

outputs/skill-search-policy.md selecciona entre ReAct lineal, ToT, LATS y búsqueda evolutiva según la forma de la tarea, el presupuesto y la fidelidad del evaluador.

Ejercicios

1. Ejecute el LATS simplificado con UCT c=0.1 frente a c=2.0. ¿Qué cambia en el trace?
2. Reemplace la value function por un puntuador con más ruido (agregue una variación aleatoria). ¿Sigue encontrando MCTS la mejor hoja? ¿Cuál es la relación señal-ruido mínima que tolera?
3. Implemente ToT con beam search (mantenga los mejores k en cada nivel) y compárelo con BFS. ¿Cuál es mejor con un presupuesto de tokens limitado?
4. Lea la Sección 5.1 de LATS. Reproduzca el recuento de trayectoria de HumanEval: ¿cuántos rollouts se necesitan para alcanzar el pass@1 reportado?
5. Lea la discusión del artículo de LATS sobre "cuándo LATS ayuda menos". Escriba una regla de decisión de un párrafo que mapee la forma de la tarea con la estrategia de búsqueda.

Términos Clave

Lecturas Adicionales

• Yao et al., Tree of Thoughts (arXiv:2305.10601) — the canonical paper
• Zhou et al., LATS (arXiv:2310.04406) — MCTS with Reflexion feedback
• LangGraph overview — subgraph patterns for search
• AlphaEvolve (arXiv:2506.13131) — evolutionary search with programmatic evaluators