Sintesi Tecnica: Comportamento e Rappresentazione nei LLM Open-Weight per l'Ottimizzazione Combinatoria

Definizione del Problema

L'ottimizzazione combinatoria (CO) si basa pesantemente su processi manuali guidati dall'esperienza per lo sviluppo e la selezione di algoritmi. Sebbene il Machine Learning (ML) abbia iniziato a integrarsi in questo dominio, le capacità rappresentazionali interne dei Large Language Models (LLM) riguardo alle strutture dei problemi di CO rimangono ampiamente inesplorate. Gli studi esistenti valutano principalmente le prestazioni funzionali degli LLM (ad esempio, la generazione di euristiche o codice) senza indagare se le loro rappresentazioni interne catturino informazioni significative sulle istanze dei problemi o sul comportamento algoritmico.

Questo studio affronta il divario tra competenza osservabile e comprensione latente negli LLM. Investiga se gli LLM open-weight, congelati, codifichino informazioni strutturali e numeriche sugli istanze di Problemi di Ottimizzazione Combinatoria (COP) che possano essere sfruttate per task a valle. Nello specifico, la ricerca distingue tra informazioni che possono essere recuperate esplicitamente attraverso il prompting diretto e informazioni che sono codificate implicitamente nei livelli nascosti, anche se non accessibili tramite generazione.

Metodologia

Gli autori propongono un framework sperimentale unificato che combina analisi di Query Diretta e di Probing su quattro benchmark: Bin Packing (BPP), Graph Coloring (GCP), Jobshop Scheduling (JSP) e Knapsack Problem (KP).

1. Configurazione Sperimentale

• Modelli: Cinque LLM open-weight con range da 3B a 120B di parametri, inclusa la famiglia Llama instruct (3B, 8B, 70B) e la famiglia di ragionamento gpt-oss (20B, 120B).
• Dati: Un sottoinsieme stratificato del 5% di istanze benchmark da precedenti studi di Instance Space Analysis (ISA), preservando la copertura tra problemi, complessità delle feature e portfolio di algoritmi.
• Rappresentazioni: Le istanze sono state presentate in tre formati: Standard (testo strutturato), Code-like (MiniZinc) e Natural Language.
• Vincoli: Non è stato eseguito alcun fine-tuning specifico per il task; i modelli sono stati utilizzati "off-the-shelf" per valutare le rappresentazioni intrinseche.

2. Direct Querying (Recupero Esplicito)

I modelli sono stati istruiti per estrarre specifiche feature dell'istanza (es. conteggio nodi, densità del grafo, peso medio) direttamente dal testo di input.

• Varianti di Prompt:
  • Standard: Richiesta diretta di un valore numerico in formato JSON.
  • Chain-of-Thought (CoT): Richiesta di una traccia di ragionamento seguita dal valore.
  • Native Reasoning (gpt-oss): Utilizzo del canale di ragionamento interno del modello tramite l'interfaccia Harmony.
• Valutazione: I valori predetti sono stati confrontati con i valori reali calcolati tramite estrattori artigianali utilizzando metriche come l'Errore Assoluto Medio (MAE) e la proporzione di predizioni entro l'1% dal valore reale.

3. Probing (Decodificabilità Implicita)

Per valutare le rappresentazioni latenti, gli autori hanno estratto le attivazioni dei livelli nascosti dall'ultimo livello dei modelli.

• Pooling: Le attivazioni sono state aggregate tramite strategie di media (mean), massimo (max) e ultimo token (last-token).
• Probes: Modelli supervisionati (regressori Ridge, MLP, LightGBM) sono stati addestrati su questi vettori aggregati per predire le feature dell'istanza (regressione) o il miglior algoritmo per un'istanza (classificazione).
• Obiettivo: Determinare se l'informazione delle feature sia decodificabile in modo lineare o non lineare dallo spazio latente, indipendentemente dall'output generativo del modello.

4. Selezione dell'Algoritmo

Il framework di probing è stato esteso a un task di selezione dell'algoritmo per singola istanza. Gli embedding derivati dagli LLM sono stati utilizzati come input per classificatori per predire l'algoritmo ottimale da un portfolio, con prestazioni confrontate contro baseline utilizzando feature artigianali e basate su ISA.

Contributi Chiave

1. Framework Unificato: Introduzione di una metodologia per valutare congiuntamente l'estrazione esplicita di feature (querying) e l'analisi della rappresentazione latente (probing) per la CO.
2. Analisi della Scala e del Ragionamento: Validazione del framework attraverso cinque modelli (3B–120B) e analisi dell'impatto del prompting Chain-of-Thought, rivelando la sua forte dipendenza dalla scala del modello.
3. Dissociazione dei Segnali: Fornitura della prima prova su larga scala che il recupero esplicito e la codifica latente sono proprietà distinte; i modelli possono fallire nel generare un valore corretto pur codificando tale informazione negli stati nascosti.
4. Descrittori Surrogati: Dimostrazione che le rappresentazioni dei livelli nascosti degli LLM possono fungere da efficaci descrittori surrogati per la selezione dell'algoritmo, raggiungendo una capacità predittiva comparabile alle tradizionali feature artigianali.
5. Riproducibilità: Rilascio del dataset, del codice e dei prompt per favorire ulteriori ricerche all'intersezione tra LLM e ottimizzazione.

Risultati Chiave

Prestazioni di Direct Querying

• Complessità delle Feature: I modelli recuperano in modo affidabile le feature semplici e direttamente estraibili (es. conteggi), ma faticano significativamente con le feature che richiedono computazioni strutturate o aggregazioni (es. medie, rapporti).
• Scala del Modello: La scalabilità migliora le prestazioni per le feature a bassa complessità, ma offre rendimenti decrescenti per le feature ad alta complessità.
• Chain-of-Thought (CoT): L'effetto di CoT è non monotono e dipendente dalla scala. Degrada le prestazioni sui modelli piccoli (3B), offre benefici selettivi sui modelli intermedi (8B) e migliora costantemente le prestazioni sui modelli grandi (70B). Tuttavia, aumenta sempre il costo computazionale.
• Modalità di Fallimento: I modelli orientati al ragionamento (gpt-oss) esibiscono un "astensione calibrata", restituendo frequentemente null quando il calcolo non è affidabile, mentre i modelli Llama tendono a produrre "allucinazioni eccessivamente sicure" (numeri errati ma dall'aspetto plausibile).

Probing e Codifica Latente

• Latente vs Esplicito: Esiste un divario costante tra il recupero esplicito e la decodificabilità latente. Il probing raggiunge spesso un'accuratezza superiore rispetto al direct querying, specialmente per le feature complesse, indicando che l'informazione rilevante è presente negli stati nascosti ma non accessibile tramite generazione.
• Robustezza della Rappresentazione: Il segnale predittivo nelle rappresentazioni latenti è robusto alle variazioni nella rappresentazione dell'input (Standard vs Natural Language vs Code-like) e nelle strategie di pooling.

Selezione dell'Algoritmo

• Parità Predittiva: Gli embedding derivati dagli LLM hanno raggiunto un'accuratezza predittiva nella selezione dell'algoritmo comparabile alle tradizionali feature artigianali e basate su ISA in tutti i cinque modelli.
• Dipendenza dal Classificatore: La scelta del classificatore a valle (es. LightGBM vs Logistic Regression) ha avuto un impatto sulla performance più significativo rispetto alla specifica origine della rappresentazione (LLM vs Handcrafted).
• Nessun Vantaggio Sistematico: Non è stata trovata alcuna prova robusta che le feature basate su ISA superino sistematicamente le rappresentazioni derivate dagli LLM, né viceversa.

Significato e Rivendicazioni

L'articolo sostiene che gli LLM possiedano un'asimmetria funzionale tra le loro capacità di ragionamento esplicito e le loro rappresentazioni interne. Sebbene gli LLM non siano ancora sostituti affidabili per gli estrattori di feature esatti e artigianali a causa degli alti costi computazionali e dell'inaffidabilità nel calcolo strutturato, le loro rappresentazioni latenti contengono regolarità statistiche sufficienti per agire come efficaci descrittori surrogati.

Gli autori sostengono che le rappresentazioni derivate dagli LLM siano più preziose in scenari in cui:

1. L'ingegneria delle feature artigianali non è disponibile o è troppo costosa da progettare.
2. Le istanze arrivano in formati eterogenei o non standard.
3. È necessario un descrittore di istanza agnostico rispetto al problema prima che sia possibile una specifica ingegneria delle feature.

Lo studio conclude che, sebbene gli LLM non "computino" attualmente le feature nel senso deterministico richiesto dalle pipeline di ottimizzazione esatte, i loro stati interni codificano un segnale che è altamente predittivo delle prestazioni algoritmiche, colmando il divario tra i dati grezzi dell'istanza e la selezione dell'algoritmo senza la necessità di un design manuale delle feature.