Resumen Técnico: Comportamiento y Representación en LLMs de Pesos Abiertos para la Optimización Combinatoria

Planteamiento del Problema

La Optimización Combinatoria (CO) depende en gran medida de procesos manuales impulsados por la experiencia para el desarrollo y la selección de algoritmos. Si bien el Aprendizaje Automático (ML) ha comenzado a integrarse en este dominio, las capacidades de representación interna de los Modelos de Lenguaje de Gran Escala (LLMs) con respecto a las estructuras de los problemas de CO permanece mayormente inexplorada. Los estudios existentes evalúan principalmente el rendimiento funcional de los LLMs (por ejemplo, la generación de heurísticas o código) sin investigar si sus representaciones internas capturan información significativa sobre las instancias de los problemas.

Este estudio aborda la brecha entre la competencia observable y la comprensión latente en los LLMs. Investiga si los LLMs de pesos abiertos y congelados codifican información estructural y numérica sobre los Problemas de Optimización Combinatoria (COPs) que pueda ser aprovechada para tareas posteriores. Específicamente, la investigación distingue entre la información que puede ser recuperada explícitamente mediante consultas directas y la información que está codificada implícitamente dentro de las capas ocultas, incluso si no es accesible mediante la generación.

Metodología

Los autores proponen un marco experimental unificado que combina análisis de Consulta Directa (Direct Querying) y de Sondeo (Probing) a través de cuatro problemas de referencia: Bin Packing (BPP), Graph Coloring (GCP), Jobshop Scheduling (JSP) y Knapsack Problem (KP).

1. Configuración Experimental

• Modelos: Cinco LLMs de pesos abiertos que oscilan entre 3B y 120B de parámetros, incluyendo la familia Llama instruct (3B, 8B, 70B) y la familia de razonamiento gpt-oss (20B, 120B).
• Datos: Un subconjunto estratificado del 5% de las instancias de referencia de estudios previos de Análisis de Espacio de Instancias (ISA), preservando la cobertura en términos de problemas, complejidades de características y carteras de algoritmos.
• Representaciones: Las instancias se presentaron en tres formatos: Estándar (texto estructurado), tipo Código (MiniZinc) y Lenguaje Natural.
• Restricciones: No se realizó ajuste fino (fine-tuning) específico para la tarea; los modelos se utilizaron "tal cual" (off-the-shelf) para evaluar las representaciones intrínsecas.

2. Consulta Directa (Recuperación Explícita)

Se solicitó a los modelos extraer características específicas de la instancia (por ejemplo, conteo de nodos, densidad de grafos, peso promedio) directamente del texto de entrada.

• Variantes de Prompt:
  • Estándar: Solicitud directa de un valor numérico en formato JSON.
  • Cadena de Pensamiento (CoT): Solicitud de un rastro de razonamiento seguido del valor.
  • Razonamiento Nativo (gpt-oss): Utilización del canal de razonamiento interno del modelo a través de la interfaz Harmony.
• Evaluación: Los valores predichos se compararon contra los valores reales computados mediante extractores diseñados a mano utilizando métricas como el Error Absoluto Medio (MAE) y la proporción de predicciones dentro del 1% del valor real.

3. Sondeo (Decodificabilidad Implícita)

Para evaluar las representaciones latentes, los autores extrajeron activaciones de las capas ocultas de la última capa de los modelos.

• Agrupación (Pooling): Las activaciones se agruparon utilizando estrategias de media (mean), máximo (max) y último token (last-token).
• Sondas (Probes): Se entrenaron modelos supervisados (regresores Ridge, MLPs, LightGBM) sobre estos vectores agrupados para predecir características de la instancia (regresión) o el mejor algoritmo para una instancia (clasificación).
• Objetivo: Determinar si la información de las características es decodificable de forma lineal o no lineal desde el espacio latente, independientemente de la salida generativa del modelo.

4. Selección de Algoritmos

El marco de sondeo se extendió a una tarea de selección de algoritmos por instancia. Los embeddings derivados de los LLM se utilizaron como entradas para clasificadores para predecir el algoritmo óptimo de una cartera, comparando su rendimiento contra bases de datos utilizando características diseñadas a mano y basadas en ISA.

Principales Contribuciones

1. Marco Unificado: Introdujo una metodología para evaluar conjuntamente la extracción de características explícitas (consulta) y el análisis de representación latente (sondeo) para CO.
2. Análisis de Escala y Razonamiento: Validó el marco a través de cinco modelos (3B–120B) y analizó el impacto del prompting de Cadena de Pensamiento (CoT), revelando su fuerte dependencia de la escala del modelo.
3. Disociación de Señales: Proporcionó la primera evidencia a gran escala de que la recuperación explícita y la codificación latente son propiedades distintas; los modelos pueden fallar al generar un valor correcto pero seguir codificando dicha información en sus estados ocultos.
4. Descriptores Sustitutos: Demostró que las representaciones de las capas ocultas de los LLM pueden servir como descriptores sustitutos efectivos para la selección de algoritmos, logrando un poder predictivo comparable al de las características tradicionales diseñadas a mano.
5. Reproducibilidad: Publicación del conjunto de datos, código y prompts para fomentar la investigación futura en la intersección de los LLMs y la optimización.

Resultados Clave

Rendimiento de la Consulta Directa

• Complejidad de Características: Los modelos recuperan de manera confiable características simples y directamente extraíbles (ej. conteos), pero tienen dificultades significativas con características que requieren computación estructurada o agregación (ej. promedios, razones).
• Escala del Modelo: El escalamiento mejora el rendimiento para características de baja complejidad, pero ofrece rendimientos decrecientes para características de alta complejidad.
• Cadena de Pensamiento (CoT): El efecto de CoT es no monotónico y dependiente de la escala. Degrada el rendimiento en modelos pequeños (3B), ofrece beneficios selectivos en modelos intermedios (8B) y mejora consistentemente el rendimiento en modelos grandes (70B). Sin embargo, siempre aumenta el costo computacional.
• Modos de Fallo: Los modelos orientados al razonamiento (gpt-oss) exhiben una "abstinencia calibrada", devolviendo frecuentemente null cuando la computación no es fiable, mientras que los modelos Llama tienden a producir "alucinaciones excesivamente seguras" (números incorrectos pero con apariencia de válidos).

Sondeo y Codificación Latente

• Latente vs. Explícito: Existe una brecha constante entre la recuperación explícita y la decodificabilidad latente. El sondeo suele lograr una mayor precisión que la consulta directa, particularmente para características complejas, lo que indica que la información relevante está presente en los estados ocultos pero no es accesible vía generación.
• Robustez de la Representación: La señal predictiva en las representaciones latentes es robusta a las variaciones en la representación de entrada (Estándar vs. Lenguaje Natural vs. Tipo Código) y a las estrategias de agrupación.

Selección de Algoritmos

• Paridad Predictiva: Los embeddings derivados de LLM alcanzaron una precisión predictiva en la selección de algoritmos comparable a las características tradicionales diseñadas a mano y basadas en ISA en todos los cinco modelos.
• Dependencia del Clasificador: La elección del clasificador posterior (ej. LightGBM vs. Regresión Logística) tuvo un impacto más significativo en el rendimiento que la fuente específica de la representación (LLM vs. Diseñada a Mano).
• Sin Ventaja Sistemática: No se encontró evidencia robusta de que las características basadas en ISA superen sistemáticamente a las representaciones derivadas de LLM, ni viceversa.

Significado y Afirmaciones

El artículo afirma que los LLM poseen una asimetría funcional entre sus capacidades de razonamiento explícito y sus representaciones internas. Si bien los LLM aún no son reemplazos fiables para los extractores de características exactos y diseñados a mano debido a sus altos costos computacionales y falta de fiabilidad en la computación estructurada, sus representaciones latentes contienen suficientes regularidades estadísticas para actuar como descriptores sustitutos efectivos.

Los autores argumentan que las representaciones derivadas de LLM son más valiosas en escenarios donde:

1. La ingeniería de características diseñada a mano no está disponible o es demasiado costosa de diseñar.
2. Las instancias llegan en formatos heterogéneos o no estandarizados.
3. Se necesita un descriptor de instancia agnóstico al problema antes de que sea posible realizar una ingeniería de características específica.

El estudio concluye que, aunque los LLM no "computan" actualmente las características en el sentido determinista requerido para las canalizaciones de optimización exacta, sus estados internos codifican una señal que es altamente predictiva del rendimiento algorítmico, cerrando la brecha entre los datos brutos de la instancia y la selección de algoritmos sin necesidad de un diseño manual de características.