Sequential-Parallel Duality in Prefix Scannable Models

Each language version is independently generated for its own context, not a direct translation.

Immagina di dover organizzare una festa enorme con migliaia di ospiti. Hai due modi per gestire la lista degli invitati e preparare i piatti:

Il metodo "Vecchio Ritratto" (RNN): Chiedi a una sola persona di preparare tutto. Deve prendere il primo invitato, cucinare per lui, poi il secondo, e così via. È lento, ma richiede pochissimo spazio in cucina.
Il metodo "Grande Cucina" (Transformer): Assumi mille chef. Tutti cucinano contemporaneamente per tutti gli ospiti. È velocissimo per preparare il pasto, ma la cucina diventa un caos: ti servono mille pentole, mille fornelli e mille tavoli (memoria) per tenere traccia di chi ha mangiato cosa. Più ospiti ci sono, più la cucina esplode.

La domanda a cui risponde questo paper è: Esiste un modo per avere la velocità della cucina gigante, ma lo spazio ordinato della cucina singola?

La risposta è sì, e la chiamano PSM (Modelli Scansionabili in Prefisso).

Ecco come funziona, spiegato con analogie semplici:

1. Il Problema: La "Doppia Faccia"

I modelli moderni (come i Transformer che usano ChatGPT) sono bravissimi a imparare (addestramento) perché possono fare tutto in parallelo, come un esercito di chef. Ma quando devono "pensare" (inferenza) per rispondere a una domanda, devono rileggere tutto il passato, occupando tanta memoria.
I vecchi modelli (come le RNN) sono efficienti in memoria, ma lenti a imparare perché devono lavorare uno alla volta.

2. La Soluzione: La "Scala a Pioli" (Prefix Scan)

Gli autori dicono: "E se dividessimo la festa in gruppi (chunk) e usassimo un trucco matematico chiamato Prefix Scan?"

Immagina di dover sommare una lista lunghissima di numeri.

Metodo lento: Somma il primo col secondo, poi il risultato col terzo, poi col quarto... (Lento).
Metodo parallelo (Scan): Dividi i numeri in coppie. Somma le coppie contemporaneamente. Poi somma i risultati delle coppie. Poi somma i risultati di quelli. È come una scala a pioli che sale velocemente.

Questo trucco permette di calcolare tutto velocemente in parallelo (per l'addestramento) ma di mantenere solo i "riassunti" dei gruppi (per l'inferenza), risparmiando spazio.

3. La Grande Innovazione: "Non serve essere perfetti"

Fino a poco tempo fa, questo trucco funzionava solo se l'operazione che facevamo era "associativa" (cioè se l'ordine in cui raggruppavi le cose non cambiava il risultato, come fare $2+3+4$).

Il paper dice: "E se usassimo un'operazione più complicata, come l'attenzione Softmax (quella che usa i Transformer per decidere cosa è importante)?"
Di solito, l'ordine conta in queste operazioni. Ma gli autori hanno scoperto un modo per forzare un ordine fisso (come una ricetta precisa) usando un contatore binario.

L'analogia del Contatore Binario:
Immagina di avere una serie di scatole. Ogni volta che arriva un nuovo gruppo di ospiti, lo metti in una scatola.

Se la scatola è vuota, ci metti dentro il gruppo.
Se la scatola è piena, la chiudi e la metti in una scatola più grande (che contiene due gruppi).
Se anche quella è piena, la metti in una scatola ancora più grande.

In questo modo, non devi mai tenere in memoria tutti gli ospiti, solo i "riassunti" delle scatole chiuse. E il bello è che puoi calcolare il risultato finale seguendo un ordine preciso, anche se l'operazione è complessa.

4. Il Risultato: Il "Transformer-PSM"

Hanno creato un nuovo modello chiamato Transformer-PSM.

Durante l'apprendimento: Funziona come un Transformer, usando tutti i chef contemporaneamente (veloce).
Durante l'uso (inferenza): Funziona come un RNN, tenendo in memoria solo i "riassunti" delle scatole (poco spazio).

Perché è importante?
Hanno provato questo modello su compiti difficili (come ricordare dove si trova un oggetto in una storia lunga o prevedere la prossima parola).

I vecchi modelli "efficienti" (come Mamba) erano bravi a ricordare lo stato, ma non a fare ragionamenti complessi.
I Transformer erano bravi a ragionare, ma diventavano lenti e pesanti con testi lunghi.
Il Transformer-PSM è il "best of both worlds": è veloce, occupa poca memoria, e riesce a ricordare cose molto meglio dei modelli precedenti, anche quando la storia diventa lunghissima.

In sintesi

Gli autori hanno scoperto un "ponte" matematico che permette di unire la potenza dei Transformer con l'efficienza dei vecchi modelli ricorrenti. È come se avessero trovato un modo per avere una cucina gigante che, però, quando non serve, si ripiega in una piccola scatola portatile, senza perdere la capacità di cucinare piatti complessi.

Each language version is independently generated for its own context, not a direct translation.

Ecco una sintesi tecnica dettagliata del paper "Sequential-Parallel Duality in Prefix-Scannable Models", pubblicata come articolo di conferenza all'ICLR 2026.

1. Il Problema

I modelli di sequenza moderni devono soddisfare un duplice requisito spesso conflittuale:

Addestramento parallelo: Necessario per scalare su grandi dataset (come fanno i Transformer).
Inferenza sequenziale efficiente: Necessaria per l'uso in produzione, dove la complessità temporale deve essere lineare ( $O(N)$ ) e quella spaziale costante o logaritmica rispetto alla lunghezza della sequenza $N$ .

I Transformer eccellono nell'addestramento parallelo ma soffrono di complessità quadratica ( $O(N^2)$ ) sia in tempo che in memoria durante l'inferenza (a causa della cache KV e dell'attenzione completa). I RNN classici e i moderni State Space Models (SSM) come Mamba offrono inferenza efficiente ( $O(1)$ memoria, $O(1)$ tempo per token), ma spesso sacrificano l'espressività o la capacità di catturare dipendenze a lungo raggio complesse rispetto ai Transformer.

La domanda centrale è: Esiste una classe unificata di modelli che possa essere valutata in parallelo con profondità quasi costante e in sequenza con spazio quasi costante, mantenendo al contempo l'espressività dei Transformer?

2. Metodologia e Definizione Teorica

Gli autori introducono una nuova famiglia di modelli chiamata Prefix-Scannable Models (PSM), basata sull'algoritmo classico del Parallel Prefix Scan (o scan di Blelloch).

A. Dualità Sequenziale-Parallela (SPD)

Il paper definisce formalmente la Sequential-Parallel Duality (SPD) come la proprietà di un modello che soddisfa due condizioni:

Addestramento Parallelo: I calcoli possono essere eseguiti in un circuito di profondità $\tilde{O}(1)$ (quasi costante).
Inferenza Sequenziale: L'aggiornamento dello stato e la previsione possono essere eseguiti con memoria di lavoro $O(\log N)$ o $O(1)$ e tempo ammortizzato $O(1)$ .

B. I Prefix-Scannable Models (PSM)

I PSM generalizzano i modelli esistenti (come Mamba, GLA, RetNet) permettendo di calcolare gli stati tramite uno scan parallelo su "chunk" di token.

Struttura: Una sequenza di token viene divisa in chunk di dimensione $c$ . Ogni chunk viene codificato ( $Enc$ ), e gli stati dei chunk vengono aggregati tramite un operatore binario ( $Agg$ ).
Algoritmo di Training (Static Scan): Utilizza lo scan di Blelloch (upsweep/downsweep) su una struttura ad albero binario per calcolare tutti gli stati prefix in $O(N)$ lavoro e profondità $O(\log N)$ .
Algoritmo di Inferenza (Online Scan): Utilizza un contatore binario online (Algorithm 2 nel paper). Man mano che arrivano nuovi chunk, l'algoritmo mantiene una struttura di "mini-alberi" (radici) che vengono fuse dinamicamente. Questo permette di calcolare lo stato corrente mantenendo solo $O(\log N)$ stati intermedi in memoria.

C. Generalizzazione oltre l'Affinità

Un contributo teorico cruciale è la distinzione tra:

Aggregatori Associativi: Modelli come Mamba e Linear Attention usano operatori associativi (es. trasformazioni affini). Per questi, lo scan parallelo produce esattamente lo stesso risultato dello scan sequenziale. La complessità è $SPD-(N, 1)$ .
Aggregatori Non-Associativi: I PSM permettono operatori non-associativi, come l'attenzione softmax. Poiché l'associazione non vale, l'ordine di raggruppamento (parentesi) cambia il risultato. I PSM risolvono questo fissando una parentesi unica determinata dalla struttura dell'albero di Blelloch.
- Questo permette di creare modelli ibridi che combinano la potenza dell'attenzione (non associativa) con l'efficienza dello scan, ottenendo una complessità $SPD-(N, \log N)$ .

3. Contributi Chiave

Unificazione Teorica: Gli autori dimostrano che molte architetture recenti (Mamba, GLA, DeltaNet, mLSTM) sono istanze specifiche di modelli con aggiornamenti dello stato calcolabili tramite scan di prefisso con operatori associativi.
Definizione dei PSM: Introduzione di una classe più ampia che include operatori non associativi (come l'attenzione softmax), permettendo di progettare modelli con costi di inferenza $O(1)$ ammortizzati e memoria $O(\log N)$ .
Transformer-PSM: Progettazione e implementazione di un nuovo modello, il Transformer-PSM, che utilizza blocchi Transformer bidirezionali per l'aggregazione ( $Agg$ ) e unidirezionali per l'inferenza ( $Inf$ ) su chunk. Questo modello supera i limiti dei modelli lineari pur mantenendo l'efficienza.
Analisi della Generalizzazione: Dimostrazione teorica e sperimentale che variando la dimensione del "chunk" ( $c$ ), si può spostare il comportamento asintotico del modello da simile agli SSM (chunk piccoli) a simile ai Transformer (chunk grandi).

4. Risultati Sperimentali

I modelli sono stati valutati su tre task principali:

Tracking di Stato (S5 Task): Un task algoritmico che richiede di tracciare permutazioni complesse (completo in $NC^1$ $N C^{1}$ ).
- Risultato: Il Transformer-PSM mostra una generalizzazione alla lunghezza eccezionale. Addestrato su sequenze di lunghezza 18, riesce a generalizzare perfettamente fino a 160+ token, superando significativamente sia i Transformer standard che Mamba, che falliscono su sequenze più lunghe.
Ricerca Associativa (MQAR - Multi Query Associative Recall): Un task che richiede di recuperare valori associati a chiavi precedenti in una sequenza.
- Risultato: Con una dimensione di chunk di 64, il Transformer-PSM raggiunge la precisione perfetta, paragonabile a un Transformer a contesto completo, mentre riduce la memoria. Mamba fallisce in questo setting specifico (query uniformi), evidenziando i limiti dei modelli lineari puri.
Modellazione del Linguaggio (WikiText-103):
- Risultato: Variando la dimensione del chunk, la perplessità migliora gradualmente avvicinandosi a quella di un GPT-2 standard (22.28 vs 22.45 per chunk=256).
- Efficienza: L'inferenza del Transformer-PSM mantiene un tempo per token costante e basso (~0.008s) anche su sequenze lunghe (40k token), a differenza del GPT-2 il cui tempo di inferenza cresce linearmente con la lunghezza del contesto (fino a ~0.04s).

5. Significato e Implicazioni

Il lavoro offre una unificazione concettuale fondamentale per il campo dei modelli di sequenza efficienti:

Superamento dei compromessi: I PSM dimostrano che non è necessario scegliere tra l'espressività dei Transformer e l'efficienza degli SSM. È possibile ottenere entrambe le proprietà definendo correttamente l'operatore di aggregazione e la struttura di parentesi.
Nuovo spazio di progettazione: La possibilità di usare operatori non associativi (come l'attenzione) all'interno di uno schema di scan apre la strada a nuove architetture ibride.
Scalabilità: La capacità di mantenere una memoria logaritmica ( $O(\log N)$ ) durante l'inferenza, pur utilizzando meccanismi di attenzione complessi, risolve uno dei principali colli di bottiglia per l'uso di modelli di grandi dimensioni su contesti lunghi.

In sintesi, il paper stabilisce che la "dualità sequenziale-parallela" non è una proprietà esclusiva di pochi modelli, ma una caratteristica di una vasta classe di modelli (PSM) che possono essere progettati sistematicamente per bilanciare efficienza computazionale e capacità di modellazione.