🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

Questo articolo analizza il potere espressivo dei modelli a spazio di stato (SSM) utilizzando le logiche temporali, rivelando che le loro capacità spaziano dai linguaggi regolari ai linguaggi non regolari a seconda dei meccanismi di gating e della precisione aritmetica, confrontando sistematicamente tali risultati con le architetture transformer.

Autori originali: Eric Alsmann, Lowejatan Noori, Martin Lange

Pubblicato 2026-01-28

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Eric Alsmann, Lowejatan Noori, Martin Lange

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover insegnare a un robot a leggere una storia e a comprenderne la sequenza di eventi. Nel mondo dell'Intelligenza Artificiale, ci sono due tipi principali di "lettori" (architetture) che competono per il lavoro: i famosi Transformer (come quelli che alimentano gli attuali chatbot) e le stelle nascenti chiamate State Space Models (SSM).

Questo articolo è un'indagine teorica sulla "capacità cerebrale" degli SSM. Gli autori non si stanno chiedendo quanto bene questi modelli performino su un test specifico; si stanno chiedendo: "Qual è il limite assoluto di ciò che questi modelli possono comprendere, indipendentemente da quanto li addestriamo?"

Per rispondere, utilizzano un particolare "linguaggio logico" (Logica Temporale) come metro di misura. Ecco una ripartizione delle loro scoperte utilizzando analogie semplici.

1. I due tipi principali di SSM

L'articolo divide gli SSM in due gusti principali in base a come gestiscono l'informazione:

Diagonal-Gated SSMs (I "Contabili Rigidi"): Questi modelli hanno una regola secondo cui i loro "gate" interni (interruttori che controllano il flusso di informazioni) possono cambiare in base alla parola che stanno leggendo, ma devono rimanere "diagonali". Immaginalo come una calcolatrice dove puoi cambiare i numeri che stai sommando, ma non puoi mescolare le colonne tra loro.
Time-Invariant SSMs (Gli "Orologi Costanti"): Questi modelli hanno gate che non cambiano mai, indipendentemente dalla parola che stanno leggendo. Sono come un metronomo o un orologio; ticchettano allo stesso ritmo indipendentemente dalla storia che viene raccontata.

2. Il problema della precisione: Righello vs Metro

Gli autori hanno anche esaminato quanto sia "preciso" il calcolo all'interno di questi modelli.

Precisione fissa (Fixed-Precision): Immagina di usare un righello con solo 10 tacche. Non importa quanto sia lunga la storia, non puoi misurare nulla di più piccolo di quelle tacche. Questo è simile alla matematica standard dei computer (floating-point).
Precisione logaritmica (Log-Precision): Immagina di usare un metro a nastro che si allunga e diventa più dettagliato man mano che la storia si allunga. Se la storia è di 100 parole, il tuo righello ha 100 tacche; se è di 1.000 parole, ha 1.000 tacche. Questo permette di contare in modo molto più fine.

3. Cosa possono effettivamente comprendere?

I "Contabili Rigidi" (Diagonal SSMs)

Con un righello semplice (Precisione fissa): Sono bravi a comprendere l'ordine degli eventi. Possono dirti "A è accaduto prima di B" o "A è accaduto, poi B è accaduto, poi C". Tuttavia, hanno un grande punto cieco: non possono contare in cicli.
- L'analogia: Se chiedi loro di riconoscere un pattern come "un numero pari di 'a'" (ad esempio, aa, aaaa, aaaaaa), falliscono. Poiché la loro matematica è monotona (va solo verso l'alto o resta uguale), alla fine si "incastrano" e non possono distinguere tra 2 'a' e 4 'a'.
Con un metro a nastro crescente (Precisione logaritmica): Se dai loro la capacità di contare con precisione, diventano molto più intelligenti. Possono ora contare esattamente quante volte qualcosa è accaduto nel passato. Possono comprendere pattern complessi come "Il numero di 'a' è uguale al numero di 'b' uguale al numero di 'c'".

Gli "Orologi Costanti" (Time-Invariant SSMs)

Con un righello semplice: Questi modelli sono scarsi nel tracciare relazioni complesse di tipo "da quando" (ad esempio, "da quando abbiamo visto l'ultima volta una 'b', abbiamo visto una 'a'?"). Tuttavia, hanno un superpotere: possono contare in cerchio.
- L'analogia: Poiché il loro meccanismo interno è un ciclo costante, sono eccellenti nel sapere "Questa è la 2ª, 4ª o 6ª parola?". Possono facilmente riconoscere il pattern "numero pari di 'a'" che i Contabili Rigidi non riuscivano a comprendere.
Con un metro a nastro crescente: Possono fare entrambe le cose: contare in cerchio e contare numeri totali.

L' "Ibrido" (Mixed SSMs)

Se combini entrambi i tipi di strati (alcuni strati di Contabili Rigidi, altri di Orologi Costanti), ottieni il meglio di entrambi i mondi. Possono comprendere l'ordine, i cicli e il conteggio. L'articolo mostra che questi modelli ibridi possono riconoscere quasi ogni pattern "regolare" che si possa pensare, fino a un certo limite di complessità.

4. Come si confrontano con i Transformer?

Gli autori hanno confrontato le loro scoperte con ciò che già sappiamo dei Transformer:

I Diagonal SSMs (Precisione fissa) sono approssimativamente equivalenti ai Transformer senza indizi posizionali (conoscono l'ordine delle parole ma non la loro posizione esatta).
I Time-Invariant SSMs sono equivalenti ai Transformer con codifiche posizionali (Positional Encodings) (sanno esattamente dove si trovano nella frase).
La grande differenza: I Transformer con "attenzione globale" (come il tipo Average Hard-Attention) possono guardare l'intera storia contemporaneamente per contare le cose in avanti e all'indietro. Gli SSM, per loro natura, guardano solo al passato (ciò che hanno già letto). Pertanto, gli SSM sono strettamente meno potenti dei Transformer più avanzati quando si tratta di contare cose che accadranno successivamente nella sequenza.

5. I compiti "impossibili"

Il punto più importante da ricordare è l'elenco delle cose che questi modelli non possono fare, indipendentemente da quanto vengano addestrati:

Un Diagonal SSM a Precisione Fissa non potrà mai imparare a distinguere tra un numero pari e uno dispari di elementi ripetuti (come aa vs aaa). Questo è un limite architettonico duro, non un fallimento dell'addestramento.
Per rompere questo limite, devi o cambiare l'architettura (aggiungere strati time-invariant) o aumentare la precisione matematica (usare il metro a nastro crescente).

Riassunto

Pensa a questi modelli come a diversi tipi di bibliotecari:

Diagonale (Fisso): Bravo a leggere un libro in ordine, ma si confonde se gli viene chiesto di contare pattern specifici.
Time-Invariant: Bravo a contare le pagine (pari/dispari), ma fatica con storie complesse del tipo "da allora".
Ibrido: Il bibliotecario definitivo che può fare entrambe le cose, ma non può comunque guardare avanti al capitolo successivo per contare le cose.

L'articolo dimostra che queste limitazioni sono scritte nel DNA dell'architettura. Non puoi addestrare un bibliotecario "Diagonale a Precisione Fissa" per diventare un bibliotecario "da Conteggio"; devi dargli uno strumento migliore (precisione logaritmica) o una struttura cerebrale diversa (strati misti) per raggiungere quel risultato.

Sintesi Tecnica: Sull'Espressività dei Modelli a Spazio di Stato tramite Logiche Temporali

Definizione del Problema

I Modelli a Spazio di Stato (SSM) sono emersi come un'alternativa competitiva alle architetture Transformer per la modellazione di sequenze, in particolare nei grandi modelli linguistici. Tuttavia, mentre il progresso empirico è rapido, le fondamenta teoriche riguardanti l'espressività degli SSM rimangono poco esplorate rispetto ai Transformer. Il problema centrale affrontato è determinare quali classi di linguaggi e pattern diverse varianti di SSM possano teoricamente rappresentare, indipendentemente dalla dinamica di addestramento. Nello specifico, l'articolo investiga come due dimensioni architettoniche chiave influenzino l'espressività:

Meccanismi di Gating: La distinzione tra gate invarianti nel tempo (matrici costanti, es. S4), meccanismi a gating diagonale (matrici diagonali dipendenti dall'input, es. S6) e gate arbitrari.
Precisione Aritmetica: La distinzione tra aritmetica a larghezza fissa (bit costanti, es. floating-point standard) e aritmetica a precisione logaritmica (precisione che scala logaritmicamente con la lunghezza dell'input).

Gli autori mirano a mappare queste varianti ai frammenti della logica formale e alle classi di complessità per stabilire limiti inferiori rigorosi e identificare colli di bottiglia architettonici fondamentali.

Metodologia

Gli autori impiegano un quadro logico e della teoria della complessità per analizzare l'espressività degli SSM, rispecchiando il recente lavoro fondamentale sui Transformer (es. Strobl et al., 2024; Yang et al., 2024a).

Modello Formale: Gli SSM sono formalizzati come strati che trasformano sequenze di input tramite ricorrenze lineari ( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ) seguite da funzioni di output non lineari (modellate come reti neurali feedforward con attivazione ReLU).
Quadro Logico: L'analisi utilizza la Logica Temporale Lineare su tracce finite (LTLf), specificamente il frammento del passato puro (PLTLf). Questa logica cattura proprietà basate sull'ordinamento degli eventi senza contare.
- Estensioni: La logica è estesa con predicati modulari (per tracciare posizioni periodiche) e operatori di conteggio orientati all'indietro ( $\overleftarrow{\#}$ ) per analizzare la capacità di contare le occorrenze.
Dimostrazioni Costruttive: Gli autori forniscono dimostrazioni costruttive che mostrano come tradurre le formule logiche in architetture SSM. Dimostrano come specifici operatori temporali (es. Ieri, Precedentemente, Da quando) e meccanismi di conteggio possano essere implementati tramite specifiche strutture di gate e impostazioni aritmetiche.
Dimostrazioni di Impossibilità: Viceversa, l'articolo stabilisce risultati di non-espressività utilizzando proprietà come la monotonicità in SSM diagonali a precisione fissa per dimostrare che certi linguaggi non star-free (es. $(aa)^*$ ) non possono essere riconosciuti.

Contributi Chiave

1. Gerarchia dell'Espressività delle Varianti di SSM

L'articolo stabilisce una gerarchia dettagliata delle capacità degli SSM basata su gating e precisione:

SSM a Gating Diagonale (Precisione Fissa):
- Capacità: Riconoscere tutti i linguaggi definibili in PLTLf (equivalente ai linguaggi star-free e alla Logica del Primo Ordine con ordine, $FO[<]$).
- Limitazione: Non può riconoscere linguaggi non star-free come $(aa)^*$ a causa di una proprietà di monotonicità in cui input identici ripetuti causano la stabilizzazione dello stato.
SSM a Gating Diagonale (Precisione Logaritmica):
- Capacità: Riconoscere linguaggi in PLTLf[ $\overleftarrow{\#}$ ], estendendo l'espressività per includere linguaggi non regolari e persino non context-free (es. $\{a^n b^n c^n\}$ ) tramite il conteggio orientato all'indietro.
SSM Invariante nel Tempo (Precisione Fissa):
- Capacità: Riconoscere linguaggi in UN-PLTLf[MOD] (PLTLf Unaria con predicati modulari). Possono tracciare posizioni periodiche (es. distinguere indici pari/dispari) usando matrici di permutazione cicliche, permettendo loro di riconoscere $(aa)^*$ .
- Limitazione: Si congettura che non siano in grado di riconoscere linguaggi che richiedono l'operatore Da quando (es. $L(a \mathcal{S} b)$ ) perché mancano di gate dipendenti dall'input per combinare dinamicamente informazioni correnti e passate.
SSM Misto (Diagonale + Invariante nel Tempo):
- Capacità: Riconoscere PLTLf[MOD], catturando efficacemente l'unione delle capacità diagonali e invarianti nel tempo. Ciò corrisponde alla classe dei linguaggi regolari in $AC^0$ .
- Estensione a Precisione Logaritmica: Con la precisione logaritmica, riconoscono PLTLf[ $\overleftarrow{\#}$ , MOD].

2. La Precisione Aritmetica come Determinante Critico

L'articolo dimostra rigorosamente che la precisione logaritmica è strettamente necessaria per riconoscere linguaggi di conteggio non regolari. L'aritmetica a larghezza fissa restringe gli SSM ai linguaggi regolari (o star-free), mentre la precisione logaritmica abilita l'accumulo di conteggi necessari per linguaggi come $a^n b^n c^n$ .

3. Confronto Sistematico con i Transformer

Gli autori mappano le varianti di SSM direttamente ai risultati di espressività dei Transformer:

SSM Diagonale (Precisione Fissa) $\approx$ Unique Hard-Attention Transformers (UHAT) senza codifiche posizionali (entrambi catturano $FO[<]$).
SSM Invariante nel Tempo $\approx$ UHAT con Codifiche Posizionali (UHAT+PE) (entrambi catturano $FO[<, MOD]$).
SSM Misto (Precisione Logaritmica) $\approx$ Average Hard-Attention Transformers (AHAT) (entrambi catturano le capacità di conteggio, sebbene gli SSM siano limitati al conteggio orientato all'indietro).
Gate Arbitrari: Gli SSM con gate arbitrari possono riconoscere tutti i linguaggi regolari, eguagliando i limiti superiori di varianti di Transformer più complessi.

Risultati Chiave

Teorema 1: Gli SSM diagonali con precisione fissa riconoscono tutti i linguaggi in PLTLf.
Teorema 3: Gli SSM diagonali con precisione fissa non possono riconoscere $(aa)^*$ , dimostrando una separazione netta dai modelli invarianti nel tempo in questo senso.
Teorema 4: Gli SSM diagonali con precisione logaritmica riconoscono tutti i linguaggi in PLTLf[ $\overleftarrow{\#}$ ].
Teorema 7: Gli SSM invarianti nel tempo con precisione fissa riconoscono tutti i linguaggi in UN-PLTLf[MOD].
Corollario 8: Gli SSM misti con precisione fissa riconoscono tutti i linguaggi regolari in $AC^0$ .
Impossibilità: L'articolo fornisce dimostrazioni di impossibilità mostrando come specifiche scelte architettoniche (es. diagonale a precisione fissa) creino colli di bottiglia fondamentali che nessun dato di addestramento o ottimizzazione può superare.

Significato e Rivendicazioni

L'articolo sostiene di fornire il primo collegamento tra l'espressività degli SSM e la logica formale, offrendo garanzie strutturali su quali pattern siano teoricamente apprendibili o provabilmente impossibili per specifiche varianti di SSM.

Intuizioni Fondamentali: Delineando i compiti "impossibili" (es. pattern non monotoni per il diagonale a precisione fissa), il lavoro integra i benchmark empirici identificando i limiti architettonici indipendentemente dalle dinamiche di addestramento.
Chiarezza Architetturale: I risultati chiariscono la relazione tra SSM e Transformer, mostrando che gli SSM codificano intrinsecamente le informazioni posizionali attraverso la ricorrenza (analogamente alle codifiche posizionali nei Transformer) ma differiscono nei loro meccanismi di conteggio (orientamento all'indietro vs attenzione globale).
Allineamento della Complessità: Le scoperte suggeriscono che gli SSM ristretti (diagonale/invariante nel tempo con precisione fissa) operano probabilmente all'interno di $AC^0$ , un sottoinsieme proprio del limite superiore $TC^0$ precedentemente stabilito da Merrill et al. (2024). Ciò implica che queste architetture potrebbero non essere in grado di riconoscere la parità o altri linguaggi al di fuori di $AC^0$ senza modifiche specifiche.

Gli autori concludono che il loro lavoro stabilisce una base teorica rigorosa, rivelando che la scelta del meccanismo di gating e della precisione aritmetica determina fondamentalmente la classe di linguaggi che un SSM può modellare, indipendentemente dalla specifica procedura di addestramento utilizzata.