Resumen Técnico: Más Allá del Frontera: Retroceso Estocástico para la Escalabilidad Eficiente en Tiempo de Ejecución

Enunciado del Problema

La escalabilidad en tiempo de ejecución (TTS) busca mejorar el razonamiento de los Modelos de Lenguaje Grande (LLM) asignando cómputo adicional durante la inferencia para explorar múltiples trayectorias de solución. Si bien los Modelos de Recompensa de Proceso (PRM) han surgido como un mecanismo estándar para guiar esta búsqueda puntuando los prefijos intermedios, los métodos actuales del estado del arte sufren una limitación crítica: búsqueda solo en el frontera.

En los enfoques solo en el frontera (por ejemplo, Búsqueda de Haz estándar, SMC), el estado de búsqueda se restringe a los hijos recién generados en cada paso. Los prefijos generados previamente se podan irreversiblemente basándose en puntuaciones ruidosas de los PRM. Esto crea un modo de fallo de "compromiso prematuro":

1. Decisiones Irreversibles: Un prefijo que es correctamente puntuado bajo debido al ruido del PRM (o una discrepancia entre la simulación de entrenamiento del PRM y el LLM base desplegado) se descarta permanentemente, incluso si admite una continuación correcta.
2. Colapso de la Diversidad: Los prefijos incorrectos sobre-puntuados dominan la búsqueda, haciendo que el sistema desperdicie cómputo en caminos improductivos mientras pierde el acceso a estados históricos potencialmente correctos.
3. Ineficiencia: La incapacidad de revisar estados históricos obliga al modelo a gastar tokens excesivos para recuperarse de errores de poda temprana.

Metodología

El artículo propone Retroceso Estocástico sobre un Pool Persistente, un marco que mantiene un pool de memoria lineal de prefijos históricos, permitiendo que la búsqueda revise y expanda estados generados previamente en lugar de estar confinada al frontera actual. Los autores instan este marco con dos algoritmos complementarios:

1. Selección de Subpool (SPS)

SPS aborda el "problema del bloqueador" en la selección codiciosa, donde los prefijos incorrectos sobre-puntuados bloquean permanentemente el acceso a prefijos históricos correctos pero de menor puntuación.

• Mecanismo: En lugar de seleccionar los $M$ mejores candidatos de todo el pool persistente (lo que favorece a los bloqueadores de alta puntuación), SPS construye un subpool aleatorio $D_t$ de tamaño $K_t$ a partir del pool histórico $P_{t-1}$.
• Selección: Luego selecciona los $M$ mejores candidatos estrictamente dentro de este subpool aleatorio.
• Ratio Adaptativo: El tamaño del subpool se determina mediante un ratio adaptativo $\rho_t$, calculado basándose en la puntuación media del PRM del pool actual. Si el pool tiene baja confianza (puntuación media baja), el subpool es más pequeño para evitar prefijos incorrectos de alta puntuación; de lo contrario, es más grande.
• Efecto: Esta muestreo estocástico da a los prefijos históricos "bloqueados" la oportunidad de ser seleccionados y expandidos, evitando la dominancia de los candidatos del frontera sobre-puntuados.

2. Power Backtrack Sequential Monte Carlo (PB-SMC)

PB-SMC extiende los métodos de Monte Carlo Secuencial (SMC) al pool persistente, permitiendo la recuperación estocástica de decisiones de poda anteriores.

• Objetivo del Pool Persistente: A diferencia del SMC estándar que restringe las partículas al frontera actual, PB-SMC mantiene un pool que contiene tanto a los hijos recién generados como a un subconjunto retenido de prefijos históricos.
• Puntuaciones PRM Potenciadas: El método aplica una potencia $\beta_t$ a las puntuaciones del PRM ($r_{PRM}(z)^{\beta_t}$) para afilar la distribución de recompensas, acentuando los prefijos de alta puntuación mientras reduce el peso de los de baja puntuación.
• Pesos Corregidos por Mezcla: El algoritmo trata la búsqueda como un problema de Muestreo de Importancia Múltiple (MIS). Define una distribución de propuesta de mezcla $q_{mix}$ que combina:
  • $q_{new}$: Hijos nuevos generados desde el paso anterior.
  • $q_{hist}$: Prefijos históricos retenidos de pasos anteriores.
• Ponderación: Deriva pesos específicos $W_t(z)$ que corrigen la propuesta de mezcla, asegurando que el estimador converja a la distribución proxy objetivo potenciada. Esto permite que el sistema remuestree estocásticamente partículas históricas que previamente habían sido podadas.

Eficiencia de Memoria y Cómputo

• Memoria Lineal: El pool persistente almacena solo estados de texto y puntuaciones del PRM, no cachés completas de Clave-Valor (KV). Las cachés KV se recalculan solo cuando un prefijo histórico es seleccionado para expansión.
• Sobrecarga: El artículo argumenta que la sobrecarga de cómputo de recalcular las cachés KV para los estados de retroceso es insignificante en comparación con las ganancias en precisión y eficiencia de tokens.

Contribuciones Clave

1. Identificación del Fallo Solo en el Frontera: El artículo identifica la selección irreversible solo en el frontera como un modo de fallo primario en TTS guiado por PRM, donde puntuaciones ruidosas conducen a la pérdida permanente de trayectorias de solución correctas.
2. Marco de Pool Persistente: Introducción de una alternativa de memoria lineal que mantiene los prefijos históricos elegibles para futura expansión, desacoplando la elegibilidad de la búsqueda del frontera inmediato.
3. Dos Algoritmos Nuevos:
   • Selección de Subpool (SPS): Una mejora en la búsqueda codiciosa que utiliza subpools aleatorios para eludir bloqueadores sobre-puntuados.
   • Power Backtrack SMC (PB-SMC): Una extensión de SMC que utiliza puntuaciones PRM potenciadas y pesos corregidos por mezcla para habilitar el retroceso estocástico.
4. Garantías Teóricas: Demostración de que PB-SMC converge en probabilidad al objetivo proxy definido por el PRM potenciado, asegurando la corrección asintótica con respecto al objetivo proxy.

Resultados Experimentales

Los métodos fueron evaluados en cuatro benchmarks de razonamiento matemático (MATH500, AMC23, AIME24, Minerva Math) utilizando tres LLMs (Qwen2.5-7B, Qwen2.5-3B, Phi-4-mini) y el Qwen2.5-Math-PRM-7B.

• Eficiencia de Tokens: Tanto SPS como PB-SMC lograron una precisión competitiva o superior utilizando solo $N=8$ candidatos por paso, mientras que las líneas base fuertes (Búsqueda de Haz, SMC, DVTS) requerían $N=32$.
  • SPS: Redujo el consumo de tokens en un 49.4% en promedio mientras mejoraba la precisión.
  • PB-SMC: Redujo el consumo de tokens en un 36.7% en promedio mientras mejoraba la precisión.
• Ganancias de Precisión:
  • En Qwen2.5-7B-Instruct, SPS logró una precisión promedio del 54.66%, superando a DVTS (51.40%) y a la Búsqueda de Haz (52.12%).
  • En Phi-4-mini-Instruct, PB-SMC logró la precisión general más alta (48.69%).
• Estudios de Ablación:
  • Retroceso: Añadir retroceso a SMC (Backtrack SMC) mejoró la precisión promedio del 49.11% al 52.27%.
  • Estocasticidad: Reemplazar la selección global codiciosa con Selección de Subpool (SPS) mejoró la precisión promedio del 51.61% al 54.66%.
• Tiempo de Ejecución: A pesar de la sobrecarga potencial de recalcular las cachés KV, los métodos fueron aproximadamente 2.5 veces más rápidos que la Búsqueda de Haz debido al tamaño reducido del conjunto de candidatos ($N=8$ frente a $N=32$), con una penalización de tiempo de ejecución insignificante (~10%) en comparación con las líneas base competitivas más cercanas.

Significado y Afirmaciones

El artículo afirma que el retroceso estocástico en pool persistente proporciona un mecanismo simple y efectivo para mejorar el compromiso entre precisión y tokens en la escalabilidad en tiempo de ejecución. El significado central radica en desplazar el enfoque de optimización de meramente puntuar prefijos a retener el acceso a ellos. Al permitir que la búsqueda revise estados históricos, los métodos mitigan los riesgos de puntuaciones ruidosas de PRM y el compromiso prematuro.

Los autores posicionan su trabajo como una solución práctica para despliegues con recursos limitados, demostrando que la escalabilidad efectiva en tiempo de ejecución no requiere aumentos masivos en cómputo, sino una asignación más inteligente del cómputo existente mediante una búsqueda consciente de la historia. Los resultados sugieren que el acceso histórico es un factor crítico, a menudo pasado por alto, para maximizar la eficiencia del razonamiento de los LLM.