🤖 machine learning

Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees

El artículo propone la Enumeración de Hojas Distintas (DLE), un método de decodificación determinista que mejora la eficiencia y calidad de la inferencia en tareas de razonamiento al explorar sistemáticamente ramas únicas en un árbol de decodificación truncado, evitando así la redundancia computacional inherente a los métodos de autoconsistencia estocástica.

Autores originales: Xueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, Mrinmaya Sachan, Jonas Geiping

Publicado 2026-04-23

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Xueyan Li, Johannes Zenn, Ekaterina Fadeeva, Guinan Su, Mrinmaya Sachan, Jonas Geiping

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

¡Claro que sí! Imagina que tienes un amigo muy inteligente (una Inteligencia Artificial) al que le pides que resuelva un problema difícil, como un acertijo de matemáticas o escribir un código de programación.

El Problema: "El amigo que repite lo mismo"

Normalmente, para asegurarnos de que nuestro amigo da la respuesta correcta, le pedimos que intente resolver el problema varias veces seguidas (digamos, 5 o 10 veces) y luego miramos cuál es la respuesta que más se repite. A esto se le llama Auto-consistencia.

Pero hay un truco: cuando le pedimos que lo haga varias veces, a veces se vuelve un poco "perezoso" o "predecible".

La analogía: Imagina que le pides a un chef que cocine 5 platos de pasta. Si le das las mismas instrucciones y él sigue el mismo camino mental, es muy probable que los 5 platos sean exactamente iguales.
El desperdicio: En el mundo de las computadoras, esto significa que la máquina está gastando mucha energía (tiempo y dinero) cocinando el mismo plato una y otra vez, en lugar de probar 5 recetas diferentes. En la jerga técnica, esto se llama "muestreo con reemplazo": la máquina vuelve a visitar los mismos caminos que ya conocía.

La Solución: "El Explorador Determinista" (DLE)

Los autores de este paper proponen una nueva forma de pensar llamada Enumeración de Hojas Distintas (DLE).

Imagina que el proceso de pensar de la IA es como un árbol gigante con muchas ramas.

El método antiguo (Muestreo aleatorio): Es como si lanzaras una pelota de béisbol al árbol 10 veces. A veces la pelota cae en la rama A, a veces en la B, pero muchas veces cae en la rama A otra vez porque es la más gruesa y fácil de alcanzar. Estás perdiendo tiempo revisando la rama A una y otra vez.
El método nuevo (DLE): En lugar de lanzar la pelota al azar, el DLE es como un explorador con un mapa.
1. Sube al árbol y sigue la rama más fuerte hasta el final (la respuesta más probable).
2. Luego, baja y busca la siguiente rama más fuerte que nunca haya visitado.
3. Sigue así, asegurándose de que cada vez que llega a una "hoja" (una respuesta final), sea una respuesta nueva y diferente.

¿Por qué es genial esto? (Las Metáforas)

El "Compartir el camino" (Reutilización de prefijos):
Imagina que vas a visitar 5 casas diferentes en el mismo vecindario.
- Método antiguo: Sales de tu casa, caminas hasta la primera casa, vuelves a casa, sales de nuevo, caminas hasta la segunda casa... ¡Estás caminando el mismo tramo de la calle 5 veces!
- Método DLE: Sales de tu casa, caminas hasta el cruce donde las calles se separan. Ahí, en lugar de volver a casa, tomas el camino hacia la segunda casa, luego la tercera, etc. Compartes el camino inicial y solo gastas energía en los tramos que son diferentes.
- Resultado: La computadora genera menos "palabras nuevas" (tokens) y termina el trabajo mucho más rápido.
La "Caja de herramientas" (Eficiencia):
Si tienes un presupuesto limitado de dinero (o tiempo) para investigar, el método antiguo te da 5 respuestas, pero 3 son idénticas. El método DLE te da 5 respuestas que son todas distintas, cubriendo más posibilidades reales con el mismo esfuerzo. Es como si en lugar de comprar 5 copias del mismo libro, compraras 5 libros diferentes sobre el mismo tema.

Los Resultados en la Vida Real

Los autores probaron esto en tareas difíciles:

Matemáticas: Resolver problemas de lógica.
Programación: Escribir código que funcione.
Razonamiento general: Responder preguntas complejas.

El hallazgo:
El método DLE no solo es más rápido (porque no repite el trabajo), sino que es más inteligente. Al explorar caminos que la IA normalmente ignoraría (porque son un poco menos probables, pero aún así buenos), encuentra respuestas correctas que el método aleatorio se perdía.

En resumen

Piensa en la Inteligencia Artificial como un turista en una ciudad desconocida:

Antes: El turista caminaba por la calle principal, tomaba una foto, volvía al hotel, salía de nuevo, caminaba por la calle principal otra vez... y así 10 veces. Gastaba mucha energía y no veía nada nuevo.
Ahora (con DLE): El turista camina por la calle principal, llega a una esquina, y en lugar de volver, toma el primer callejón a la derecha, luego el segundo, luego el tercero. Explora todo el barrio sin dar vueltas innecesarias.

Conclusión: No se trata de que la IA piense "más", sino de que piense de una manera más ordenada y sin desperdiciar energía en repetir lo que ya sabe. ¡Es como pasar de un turista perdido a un guía turístico experto!

Resumen Técnico: Distinct Leaf Enumeration (DLE)

1. El Problema: Ineficiencia en la Autoconsistencia Estocástica

El método de autoconsistencia (self-consistency) ha demostrado mejorar el rendimiento de los Modelos de Lenguaje Grande (LLM) en tareas de razonamiento (matemáticas, código) al generar múltiples trazas de razonamiento en paralelo y votar por la respuesta más frecuente. Sin embargo, el artículo identifica una ineficiencia crítica en este enfoque, especialmente en dominios restringidos:

Muestreo con Reemplazo: La autoconsistencia estándar utiliza muestreo estocástico con reemplazo. Esto provoca que el modelo genere repetidamente los mismos prefijos de alta probabilidad y completaciones duplicadas.
Redundancia de Cálculo: En tareas como matemáticas o programación, donde las soluciones viables son un subconjunto estrecho, el modelo gasta recursos computacionales regenerando los mismos tokens iniciales y trayectorias idénticas.
Ineficiencia del Árbol de Decodificación: Visualizar las secuencias generadas como un árbol, el muestreo estocástico explora las mismas ramas tempranas repetidamente, mientras que ignora ramas prometedoras no visitadas debido a la aleatoriedad.
Limitaciones de Métodos Existentes: Los métodos de búsqueda clásicos como Beam Search sufren de degeneración (repetición de secuencias) y falta de diversidad. Otros métodos de búsqueda basados en árboles (como Tree-of-Thought) requieren llamadas adicionales al modelo para deliberación, lo que aumenta el costo computacional.

2. Metodología: Distinct Leaf Enumeration (DLE)

Los autores proponen DLE, un método de decodificación determinista que trata el muestreo truncado como la exploración sistemática de un árbol de decodificación recortado (pruned tree).

Concepto Central: En lugar de muestrear aleatoriamente del vocabulario, DLE enumera determinísticamente las hojas distintas (secuencias completas únicas) dentro de un árbol definido por una distribución de muestreo truncada (como top-k, top-p, min-p o $\epsilon$ -sampling).
Mecanismo de Funcionamiento:
1. Generación Greedy Inicial: DLE genera una secuencia greedy hasta encontrar un token de fin de secuencia (EOS), rastreando los "conjuntos activos" (tokens que superan el umbral de truncamiento) a lo largo del camino.
2. Expansión Determinista: Identifica un nodo de ramificación (donde hay múltiples tokens válidos) y elige un token alternativo del conjunto activo.
3. Completado Greedy: A partir de ese nuevo token, completa la secuencia de forma greedy hasta el EOS.
4. Repetición: Este proceso se repite, seleccionando siempre la rama con la mayor masa de probabilidad acumulada no explorada, hasta alcanzar un presupuesto de $k$ hojas o agotar las ramas.
Reutilización de Prefijos (Prefix Reuse): A diferencia de la autoconsistencia que genera cada secuencia de forma independiente, DLE explora un árbol compartido. Esto permite reutilizar las cachés KV (Key-Value) de los prefijos comunes entre diferentes ramas, eliminando la necesidad de regenerar tokens idénticos.
Parada Temprana (Early Stopping): Para evitar generar continuaciones que, aunque diverjan en un token, converjan rápidamente en el mismo sufijo (y por tanto en la misma respuesta), DLE implementa una regla de parada temprana. Si una nueva rama coincide con $n$ tokens consecutivos de una rama ya explorada, se detiene y reasigna el presupuesto.

3. Contribuciones Clave

Propuesta de DLE: Un método de decodificación libre de repeticiones que actúa como un reemplazo determinista para el muestreo estocástico. Es compatible con diversos samplers (top-p, min-p, $\epsilon$ -sampling).
Beneficio Algorítmico (Mayor Cobertura): DLE logra una mayor cobertura del espacio de búsqueda truncado bajo un presupuesto fijo de tokens. Al explorar sistemáticamente ramas de alta probabilidad no visitadas, encuentra trazas de razonamiento de mayor calidad que el muestreo aleatorio.
Beneficio Sistémico (Eficiencia de Tokens): Al evitar la regeneración de prefijos compartidos, DLE es significativamente más eficiente en términos de tokens generados. Esto se traduce en una menor latencia de inferencia, especialmente en entornos con restricciones de memoria o en sistemas que soportan caché de prefijos (como vLLM o SGLang).

4. Resultados Experimentales

Los experimentos se realizaron en modelos Qwen2.5 y Llama3.2 sobre tareas de razonamiento matemático (GSM8K), generación de código (HumanEval) y razonamiento general (MMLU-Pro).

Rendimiento Superior: DLE supera consistentemente a la autoconsistencia estocástica.
- En GSM8K, las mejoras oscilan entre un 3% y un 9% en métricas de precisión (maj@k).
- En HumanEval, las mejoras son del 4% al 7% en pass@k.
- En MMLU-Pro, se observa una mejora consistente en la precisión.
Eficiencia de Tokens: DLE alcanza el mismo nivel de precisión que la autoconsistencia estocástica utilizando mucho menos tokens nuevos. Por ejemplo, para lograr una precisión del ~34% en GSM8K, la autoconsistencia con $\epsilon$ -sampling genera >150 tokens, mientras que DLE necesita <20 tokens nuevos por pregunta en promedio.
Velocidad de Inferencia: Gracias a la reutilización de prefijos, DLE reduce significativamente el tiempo de ejecución, especialmente en tamaños de lote pequeños (batch size 1 o 2) donde la paralelización estándar no es tan efectiva.
Cobertura vs. Precisión: Se demostró una correlación positiva entre la cobertura del espacio de probabilidad y el rendimiento final. DLE logra una cobertura mayor que la autoconsistencia para el mismo número de secuencias generadas.

5. Significado e Impacto

El trabajo de DLE es significativo porque cambia el paradigma de la escalabilidad en tiempo de prueba (test-time scaling):

De "Más Muestras" a "Muestras Mejor Distribuidas": Demuestra que no se trata solo de generar más muestras, sino de asignar el presupuesto computacional de manera más eficiente para explorar el espacio de soluciones plausibles sin desperdiciar recursos en duplicados.
Optimización para Sistemas de Inferencia: DLE está diseñado para aprovechar las optimizaciones modernas de hardware y software (como la caché de prefijos en vLLM y SGLang), ofreciendo mejoras prácticas inmediatas en la latencia y el costo de inferencia.
Generalidad: Al ser independiente de la distribución de muestreo truncado específica, DLE puede integrarse fácilmente en flujos de trabajo existentes que utilizan top-p, min-p u otros métodos de truncamiento.

En conclusión, Distinct Leaf Enumeration ofrece una solución elegante y eficiente al problema de la redundancia en la inferencia de LLMs, logrando mejores resultados de razonamiento con menos recursos computacionales mediante una exploración determinista y estructurada del árbol de decodificación.