Complessità e Big-O: la lingua franca dello scaling

Una notazione di fine Ottocento decide oggi quanto può essere lungo un prompt e quanto costa un agente.

Perché questo capitolo

Quasi ogni decisione di ingegneria attorno a un modello AI è una decisione di complessità. Il context window massimo di un LLM, il costo di una chiamata API, la latenza di un agente che fa dieci passi, la scelta tra HNSW e ricerca lineare nel database vettoriale, l’esistenza stessa di FlashAttention, della KV cache, di Mamba: dietro ognuna c’è una funzione di crescita che cresce troppo, e qualcuno che ha trovato il modo di farla crescere meno.

Il capitolo serve a parlare questa lingua con precisione. Non basta dire “attention scala male”. Serve sapere che scala come O(n² d), che la matrice di attention occupa O(n²) byte, che la KV cache trasforma il decoding token-per-token da O(n²) a O(n), che FlashAttention non cambia la classe asintotica ma riscrive le costanti, che Mamba cambia la classe e lo paga con una capacità di stato finita. Senza questo vocabolario ogni discussione sui “modelli sub-quadratici” o sui “costi di long-context” diventa retorica.

C’è anche un motivo più antico. La notazione asintotica nasce nel 1894 con Paul Bachmann (matematico tedesco, teoria analitica dei numeri) per maneggiare termini di errore in approssimazioni numeriche. Donald Knuth (informatico statunitense, autore di The Art of Computer Programming) la trasferisce all’analisi degli algoritmi negli anni Settanta, con un articolo del 1976 in ACM SIGACT News che fissa la convenzione moderna di O, Ω e Θ. Quasi tutto ciò che serve per ragionare sullo scaling di un Transformer era stato definito prima che esistesse l’AI.

Contesto

La complessità computazionale è il punto dove tre tradizioni si incontrano: matematica analitica (Bachmann, Landau), teoria della computazione (Cobham, Edmonds, Cook, Levin) e ingegneria degli algoritmi (Knuth, Cormen, Aho-Hopcroft-Ullman). Negli anni Sessanta Alan Cobham (1965) e Jack Edmonds (1965), indipendentemente, propongono che “efficiente” voglia dire “polinomiale”. Stephen Cook nel 1971, in “The Complexity of Theorem-Proving Procedures”, definisce NP-completezza e dimostra che SAT è il problema più difficile in NP. Leonid Levin arriva alla stessa idea, indipendentemente, in URSS nel 1973.

Per cinquant’anni la complessità asintotica è rimasta strumento dei teorici e dei progettisti di algoritmi classici. Con l’AI moderna è tornata in primo piano per ragioni operative. Il paper “Attention Is All You Need” (Vaswani et al., NeurIPS 2017) mette in Tabella 1 la complessità per layer di attenzione e ricorrenza, segnalando esplicitamente il termine n² come costo del meccanismo. Tri Dao con FlashAttention (NeurIPS 2022) mostra che il bottleneck reale non è il numero di operazioni ma il movimento di memoria. Jordan Hoffmann e DeepMind con Chinchilla (2022) trasformano lo scaling in una legge quantitativa. Albert Gu e Tri Dao con Mamba (2023) tornano al lineare grazie agli state space model.

Tutto questo capitolo presuppone solo aritmetica e qualche regola sui limiti. Il taglio è operativo: niente dimostrazioni complete, ma definizioni precise e tabelle che si possono usare in produzione.

Cosa misura davvero la complessità

Quando si parla di “complessità di un algoritmo” si misurano in realtà più cose, che vengono spesso confuse:

• Complessità temporale: numero di operazioni elementari in funzione di n. È quella che si discute più spesso.
• Complessità spaziale: byte di memoria usata. Per LLM è spesso il vincolo binding (contesto in HBM, cache nei layer, batch size).
• Complessità di comunicazione: byte trasferiti tra unità (GPU-GPU, host-device). In sistemi distribuiti domina il tempo wall-clock.
• Complessità di campionamento: per problemi statistici, numero di sample necessari per raggiungere una certa accuratezza. Le scaling laws Chinchilla sono in questa categoria.
• Complessità descrittiva (Kolmogorov): lunghezza minima di una descrizione. Diverso dominio, citato per completezza.

Una buona analisi di un sistema AI riguarda almeno le prime tre. Discutere solo i FLOPs di un Transformer e ignorare la memoria HBM è un errore tipico del 2017-2021, corretto da FlashAttention e dalla letteratura I/O-aware.

L’intuizione

Primo angolo: il fattore di scala

La domanda chiave è semplice: se raddoppio l’input, di quanto cresce il tempo? Per un algoritmo lineare il tempo raddoppia. Per uno quadratico si quadruplica. Per uno logaritmico aumenta di una costante (di un’unità in più, qualunque sia la base). Per uno esponenziale, raddoppiare l’input significa moltiplicare il tempo per la stessa quantità di prima: passare da n=20 a n=21 raddoppia il costo, e farlo dieci volte lo moltiplica per 1024.

È una regola tascabile. Senza nulla d’altro, già dice che algoritmi quadratici tollerano input fino a qualche milione, cubici fino a qualche migliaio, esponenziali fino a qualche decina. E dice perché un Transformer con context window 128k è qualitativamente diverso da uno con 2k: 64x in input significa 4096x in costo di attenzione.

Secondo angolo: scalini di crescita

Un’altra immagine utile: le classi asintotiche sono scalini. Tra O(n) e O(n log n) c’è un piccolo gradino (log n cresce così piano che spesso è “quasi una costante”). Tra O(n log n) e O(n²) c’è un salto serio. Tra O(n²) e O(2^n) c’è un baratro.

Questa è un’analogia, non una filiazione: gli scalini non hanno proprietà matematiche speciali, ma rendono visivamente l’idea che esistono soglie qualitative. Spostare un algoritmo da una classe inferiore a una superiore è quello che gli ingegneri chiamano “fare la differenza”. Ridurre le costanti dentro la stessa classe è quello che chiamano “ottimizzare”. Sono lavori diversi.

Cosa Big-O non dice

Big-O ignora costanti moltiplicative e termini di ordine inferiore. 3n² + 100n + 5000 e n²/2 sono entrambe Θ(n²). Ma se n=1000 la differenza in cicli macchina è enorme. La notazione è perfetta per ragionare sullo scaling, pessima per stimare un tempo wall-clock.

Le costanti contano. Le costanti contano davvero quando l’hardware è una GPU, dove il movimento di memoria pesa più dei FLOP, e dove un algoritmo asintoticamente migliore (Strassen, O(n^{2.807})) può perdere contro uno peggiore (matrix multiply naive O(n³)) che si vettorializza meglio.

La meccanica

Definizioni formali

Sia n la dimensione dell’input e siano f(n), g(n) due funzioni positive. Tutte le definizioni che seguono parlano di comportamento per n abbastanza grande.

Big-O (limite superiore)

f(n) = O(g(n)) significa: esistono costanti c > 0 e n₀ ≥ 0 tali che per ogni n ≥ n₀ vale f(n) ≤ c · g(n).

In termini di limiti: limsup_{n→∞} f(n)/g(n) < ∞. Cioè il rapporto resta limitato.

Big-Omega (limite inferiore)

f(n) = Ω(g(n)) sse esistono c > 0 e n₀ tali che f(n) ≥ c · g(n) definitivamente.

Big-Theta (limite stretto)

f(n) = Θ(g(n)) sse f = O(g) e f = Ω(g). Cioè c₁ g(n) ≤ f(n) ≤ c₂ g(n) per n grande.

little-o e little-omega

f(n) = o(g(n)) sse lim f(n)/g(n) = 0. Cresce strettamente più lenta. f(n) = ω(g(n)) sse lim f(n)/g(n) = ∞. Cresce strettamente più rapida.

Una nota di abuso: scrivere “f(n) = O(g(n))” è scorretto formalmente. O(g) è un insieme di funzioni, e f appartiene a quell’insieme. La convenzione ”=” è quella di Knuth e si usa universalmente.

Regole di calcolo

Tre regole coprono il novanta per cento dei casi pratici:

• Somma: O(f) + O(g) = O(max(f, g)). Il termine più rapido domina.
• Prodotto: O(f) · O(g) = O(f · g). Loop annidati moltiplicano.
• Costante: O(c · f) = O(f) per ogni c > 0. Le costanti spariscono.

Esempio: un algoritmo che fa una scansione O(n) seguita da un sort O(n log n) è O(n log n) (la somma collassa al massimo). Due loop annidati, entrambi O(n), sono O(n²) (prodotto). Cento ricerche binarie su un array di n elementi sono O(log n), non O(100 log n) — la costante sparisce.

Classi tipiche

Dalla più lenta alla più rapida:

Classe	Nome	Algoritmi tipici
O(1)	costante	hash lookup, accesso array, KV cache hit
O(log n)	logaritmica	ricerca binaria, BST bilanciato, HNSW pratico
O(√n)	radice	alcuni algoritmi di teoria dei numeri
O(n)	lineare	scansione, ricerca lineare, decoding LLM con cache
O(n log n)	linearitmica	merge sort, FFT, sort comparison-based ottimo
O(n²)	quadratica	self-attention, naive shortest path
O(n³)	cubica	matrix multiply naive, Floyd-Warshall
O(n^k)	polinomiale	parsing CYK, regression closed-form
O(2^n)	esponenziale	brute force SAT, subset enumeration
O(n!)	fattoriale	brute force TSP, permutazioni

Il salto tra polinomiale ed esponenziale è il confine epistemico tra trattabile e intrattabile, secondo la tesi di Cobham-Edmonds.

Casi: worst, best, average, ammortizzato

Un algoritmo non ha una sola complessità. Ha diverse, a seconda di cosa misuriamo:

• Worst case: il tempo massimo su un input di dimensione n. È la garanzia.
• Best case: il tempo minimo. Spesso poco utile.
• Average case: media su una distribuzione di input. Quicksort è O(n log n) average, O(n²) worst.
• Ammortizzato: media sul tempo di una sequenza di operazioni. Il push su un dynamic array è ammortizzato O(1) anche se occasionalmente costa O(n) per il resize.

L’analisi ammortizzata è cruciale per strutture come Fibonacci heap o union-find con path compression (operazione in O(α(n)), dove α è la funzione di Ackermann inversa, costante per ogni n umano).

Master theorem

Per ricorrenze divide-and-conquer del tipo T(n) = a · T(n/b) + f(n), con a ≥ 1, b > 1, il master theorem (Bentley-Haken-Saxe 1980, popolarizzato da CLRS cap. 4) dà la soluzione asintotica confrontando f(n) con n^{log_b a}:

1. Se f(n) = O(n^{log_b a − ε}) per qualche ε > 0: T(n) = Θ(n^{log_b a}).
2. Se f(n) = Θ(n^{log_b a} · log^k n): T(n) = Θ(n^{log_b a} · log^{k+1} n).
3. Se f(n) = Ω(n^{log_b a + ε}) e regolarità: T(n) = Θ(f(n)).

Si cita come teorema senza prova; per la dimostrazione vedere CLRS.

Esempi rapidi:

• Merge sort: T(n) = 2 T(n/2) + O(n). a=2, b=2, log_b a = 1, f(n) = n. Caso 2 con k=0: T(n) = Θ(n log n).
• Strassen: T(n) = 7 T(n/2) + O(n²). log_2 7 ≈ 2.807. Caso 1: T(n) = Θ(n^{2.807}).
• Ricerca binaria: T(n) = T(n/2) + O(1). a=1, b=2, log_b a = 0. Caso 2 k=0: T(n) = Θ(log n).

P, NP, NP-completo (cenno)

• P: problemi decidibili in tempo polinomiale.
• NP: problemi le cui soluzioni candidate si verificano in tempo polinomiale.
• NP-completo: i più difficili in NP. Se uno solo si risolve in P, tutto NP collassa in P.

SAT (Cook 1971), 3-SAT, TSP, vertex cover, subset sum sono NP-completi. La domanda P = NP è uno dei sette Millennium Problems del Clay Mathematics Institute.

NP-completo non significa “impossibile”, significa “probabilmente non esiste algoritmo polinomiale”. Si attaccano con euristiche, approssimazione, SAT solver moderni che in pratica risolvono istanze enormi.

Pseudocodice di misurazione empirica

`pseudocode fit_complexity(algorithm, sizes): times = [] for n in sizes: input = generate_input(n) t0 = clock() algorithm(input) times.append(clock() - t0) # plot log(times) vs log(sizes); la pendenza è l’esponente slope = linear_regression(log(sizes), log(times)).slope return slope

Una pendenza vicina a 1 suggerisce O(n), vicina a 2 suggerisce O(n²), 3 suggerisce O(n³). È sempre saggio confermare empiricamente l'analisi asintotica: le costanti e gli effetti cache possono nascondere termini.

## Esempi

### Esempio 1: tempi a confronto

Fissato un PC moderno che esegue circa 10⁹ operazioni al secondo, ecco quanto impiegano cinque algoritmi per input crescenti.

| f(n) | n=10 | n=100 | n=10⁴ | n=10⁶ | n=10⁹ |
|---|---|---|---|---|---|
| log n | 3 ns | 7 ns | 13 ns | 20 ns | 30 ns |
| n | 10 ns | 100 ns | 10 μs | 1 ms | 1 s |
| n log n | 33 ns | 660 ns | 130 μs | 20 ms | 30 s |
| n² | 100 ns | 10 μs | 100 ms | 17 min | 32 anni |
| 2^n | 1 μs | 4·10¹³ anni | infattibile | infattibile | infattibile |

![growth curves on log-log axes: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n)](/figures/complessita-big-o/1.svg)

La tabella spiega quasi tutto da sola. Algoritmi quadratici sono accettabili per n fino a qualche milione, oltre diventano dolorosi. Algoritmi esponenziali sono infattibili oltre n ≈ 50. Algoritmi logaritmici sono praticamente costanti.

### Esempio 2: kNN naive contro HNSW

Problema concreto: un sistema RAG cerca i 10 vettori più vicini a un embedding di query, in un indice di 10⁶ documenti vettorizzati a 768 dimensioni.

Ricerca naive: per ogni vettore nell'indice, calcola distanza con la query. Costo per query: O(n · d) = 10⁶ · 768 ≈ 8 · 10⁸ operazioni. Su un thread ottimizzato, qualche centinaio di millisecondi. Troppo per un endpoint interattivo.

HNSW (Malkov-Yashunin 2018, *IEEE TPAMI*): grafo gerarchico small-world. Costruzione O(n log n), query O(log n) pratico. Per n = 10⁶, 10⁶ → ~20 hop nel grafo, ognuno con qualche centinaio di confronti vettoriali. Latenza tipica: 1-5 ms per query, 50-100x più veloce del naive, con accuratezza recall@10 superiore a 0.95.

Pseudocodice HNSW search a livello altissimo:

`pseudocode
hnsw_search(query, k):
    entry = top_layer_entrypoint
    for layer in top..1:
        entry = greedy_search(query, entry, layer, ef=1)
    candidates = greedy_search(query, entry, 0, ef=ef_search)
    return top_k(candidates, k)

Il punto: la stessa task ha due classi asintotiche radicalmente diverse a seconda della struttura dati. Stesso problema, scelta tra O(n) e O(log n).

Esempio 3: scaling di self-attention

Self-attention per un layer ha costo O(n² d + n d²), dove n è lunghezza sequenza e d la dimensione modello. Per d = 4096 (Llama-2 7B) e diversi context window, costo per layer:

Context n	FLOPs n² d	FLOPs n d²	Memoria matrice att. (fp16)
2048	1.7 · 10¹⁰	3.4 · 10¹⁰	8 MB
8192	2.7 · 10¹¹	1.4 · 10¹¹	128 MB
32768	4.4 · 10¹²	5.5 · 10¹¹	2 GB
131072	6.7 · 10¹³	2.2 · 10¹²	32 GB
1048576	4 · 10¹⁵	1.7 · 10¹³	2 TB

Il termine n² supera n d² intorno a n ≈ d, cioè 4096. Oltre, l’attenzione domina e la FFN diventa secondaria. Per 32 layer, moltiplicare per 32. Per generare l’intera sequenza, moltiplicare ancora per il numero di token output.

Senza KV cache, generare 32k token a context pieno richiederebbe ricalcolare attention sull’intero prefisso ad ogni step: O(n³ d) totale. Con KV cache, il costo per token nuovo si riduce a O(n d), totale O(n² d). È la differenza tra 5 secondi e 5 minuti per una risposta lunga.

Esempio 4: scaling laws di Chinchilla

Un esempio di complessità non temporale ma di allocazione delle risorse. Hoffmann et al. (2022) di DeepMind, in “Training Compute-Optimal Large Language Models”, studiano la domanda: dato un budget fisso di compute C in FLOPs, come allocarlo tra parametri N e token di training D?

La risposta empirica del paper: la loss minima si ottiene quando N e D crescono entrambi proporzionalmente a √C. Cioè raddoppiando il compute si dovrebbe (circa) raddoppiare sia parametri sia token, non solo i parametri.

Implicazione: GPT-3 (175B parametri, 300B token) era under-trained rispetto al regime compute-optimal. Llama-2 70B con 2T token e Llama-3 8B con 15T token sono molto più vicini al regime Chinchilla.

Costo di training in FLOPs (regola empirica): C ≈ 6 · N · D. Per Llama-3 70B con 15T token: C ≈ 6 · 7·10¹⁰ · 1.5·10¹³ ≈ 6 · 10²⁴ FLOPs. Su un cluster da 10⁴ H100 a 1 PFLOP ciascuna (in mixed precision, MFU 50%): ~14 giorni di training.

Questa è la stessa famiglia di calcoli che guida ogni decisione di pretraining e ogni budget di acquisto GPU.

Applicazioni pratiche

KV cache

Il caso più puro di trade-off spazio-tempo nell’AI moderna. Durante decoding autoregressive, ad ogni passo serve l’attenzione su tutto il prefisso. Senza cache, K e V vengono ricalcolati per ogni token già visto, generando O(n²) lavoro per token. Memorizzandoli, il calcolo per il token nuovo diventa: una proiezione di query O(d²), un prodotto query × K_cached O(n · d), un softmax O(n), una pesata su V_cached O(n · d). Totale O(n · d) per token nuovo.

Equivalenza: KV cache trasforma il decoding da O(n³) a O(n²) totale, da O(n²) a O(n) per nuovo token. Non è un’analogia: è un riarrangiamento aritmetico esatto, sostituzione di calcoli con lookup.

Costo: la cache cresce linearmente con n e con i layer. Per Llama-70B a 32k token, qualche gigabyte per sessione. È quello che limita la concorrenza in serving, ed è il motivo per cui esistono PagedAttention, vLLM, prompt caching e tecniche di KV compression.

FlashAttention

Il caso paradigmatico del “stesso O, costanti diverse”. FlashAttention (Dao et al. 2022) parte da un’osservazione: sulle GPU, la memoria HBM (slow, abbondante) e la SRAM (fast, scarsa) hanno bandwidth molto diverse. Materializzare la matrice di attention n × n in HBM costa O(n²) memoria e O(n²) read/write su HBM.

L’idea: dividere Q, K, V in blocchi che stanno in SRAM, calcolare l’attention in modo online (algoritmo di softmax streaming di Milakov-Gimelshein 2018), non materializzare mai la matrice completa. In backward, ricalcolare l’attention dai K, V invece di salvarla.

I FLOP totali restano O(n² d). La memoria HBM scende da O(n²) a O(n). L’I/O su HBM scende drasticamente. Risultato: 2-4x speedup, e context window prima impossibili (32k, 128k) diventano fattibili a parità di GPU.

Lezione: in un mondo a memoria gerarchica, O(n²) di FLOP e O(n²) di memoria HBM non sono la stessa cosa.

Sub-quadratic attention e SSM

Attaccare il problema dalla parte della classe asintotica:

• Linear attention (Katharopoulos et al. 2020): riformulando softmax(QKᵀ)V come (φ(Q) φ(K)ᵀ) V, e per associatività come φ(Q) (φ(K)ᵀ V), il prodotto interno diventa O(n d²). Trade-off: φ è una feature map approssimata, l’expressività cala.
• Performer (Choromanski et al. 2020): random feature per approssimare softmax. Costo O(n d²).
• Mamba (Gu-Dao 2023): selective state space model. Stato di dimensione fissa che evolve sequenzialmente. Inferenza autoregressiva O(n) totale, O(1) per token nuovo. Training con parallel scan O(n). Trade-off: lo stato finito limita la capacità di richiamare informazione lontana con precisione.

Tre approcci, tre punti diversi sul trade-off classe asintotica / capacità.

RAG e retrieval scaling

Per un indice di n documenti vettorializzati a dimensione d:

• Naive: O(n · d) per query.
• IVF (Inverted File Index): partiziona in cluster, cerca solo nei top-k cluster. O(√n · d) tipico.
• HNSW: O(log n) pratico.
• Product Quantization: comprime vettori, riduce memoria e accelera distanze, costanti.
• LSH: O(1) probabilistico con perdita di accuratezza.

Tutto il design di un sistema RAG a milioni di documenti gira intorno a queste classi.

flowchart LR
  Q["query embedding"] --> R["ricerca su indice ANN<br/>O(log n) HNSW"]
  R --> K["top-k candidati<br/>k ≈ 50-200"]
  K --> RR["modello reranker<br/>O(k) chiamate cross-encoder"]
  RR --> T["top-m risultati<br/>m ≈ 5-20"]
  T --> L["chiamata LLM con contesto<br/>O(T² · d) attention"]

Figura 5 — pipeline RAG annotata con la complessità dominante per stage, dalla ricerca ANN (HNSW O(log n)) al reranker cross-encoder fino alla chiamata LLM con contesto

Batch processing e parallelismo

Il batching trasforma costi: chiamare il modello su 32 prompt insieme costa meno di 32 chiamate separate, perché molte costanti (kernel launch, weight loading, ottimizzazione GEMM) sono ammortizzate sul batch. Il throughput in token/secondo cresce sublinearmente con la batch size fino a saturare la memoria o la compute, poi piatta.

Continuous batching (vLLM, TGI) decoppia ulteriormente: invece di aspettare che tutti i prompt nel batch finiscano, sostituisce dinamicamente prompt completati con nuovi. È una ottimizzazione di costanti che cambia drasticamente l’economia del serving.

Il parallelismo dentro un layer (data parallel, tensor parallel, pipeline parallel) è invece un’ottimizzazione di span: divide il lavoro per ridurre la latenza del cammino critico. Tensor parallel scompone le matmul tra GPU, pipeline parallel mette layer diversi su GPU diverse, ZeRO partiziona ottimizzatore e gradienti. Tutte tecniche di scaling al di sotto della classe asintotica.

Agent loop e budget

Un agente che esegue K passi, con contesto che cresce ad ogni step (storia + tool output), ha costo per passo O(T_t² · d) dove T_t è il contesto al passo t. Senza compaction, T_t cresce con t e il costo totale è O(K³ · d). Con compaction o sliding window: O(K · T_max² · d).

Da qui derivano scelte concrete: limitare il numero di passi, usare context compression (LLMLingua e simili), riassumere periodicamente, usare modelli più piccoli per task di routine. Ogni decisione di harness engineering è una decisione di complessità.

Dove si rompe

Le costanti contano davvero in GPU

Il modello RAM uniforme di Big-O assume che ogni accesso a memoria costi O(1). Sulle GPU questo è falso di un ordine di grandezza:

• Registri: ~1 ciclo.
• L1/L2 cache (SRAM): 10-100 cicli.
• HBM (memoria principale GPU): centinaia di cicli.
• Trasferimento host ↔ device via PCIe/NVLink: migliaia di cicli per byte.

Strassen O(n^{2.807}) per matrix multiply non è usato nelle GEMM di cuBLAS o cuDNN: il pattern di accesso memoria e la divisione in blocchi non si mappano bene ai tensor core. Il naive O(n³), vettorizzato, vince. Stesso problema, classe asintotica peggiore, performance migliori.

Modello RAM contro realtà

$$Big-O ignora memory hierarchy, cache locality, prefetching, branch prediction, TLB miss, NUMA. Esempi concreti:$$

• Linked list O(1) insert vs array O(n) insert: in pratica, su array piccoli (qualche migliaio di elementi) l’array vince per il cache-friendly layout.
• Quicksort O(n log n) average batte mergesort O(n log n) worst sui dati reali per la cache locality.
• Hash table O(1) ammortizzato peggiora drammaticamente con cattivo hashing o load factor alto.

Worst, average e mondo reale

Quicksort è O(n log n) average ma O(n²) worst, con il worst innescato da array già ordinati (se il pivot è il primo elemento). Per anni è stato un attack vector reale (algorithmic complexity attack) finché non si è diffuso lo scrambling random del pivot.

Hash table sono O(1) average ma vulnerabili a collisioni mirate. CVE storici sui parser HTTP usavano questo per DoS.

L’average case dipende dalla distribuzione di input. Se la tua distribuzione di produzione differisce dalla distribuzione assunta nell’analisi, il valore atteso non vale.

Ammortizzato non è worst-case per singola op

Una struttura dati ammortizzata O(1) può avere singole operazioni O(n). Per un sistema interattivo questo importa: il p99 di latenza è dominato dalle operazioni costose ammortizzate via, non dalla media. Resize di un dynamic array, rehash di una hash map, garbage collection in linguaggi managed: tutti casi dove l’analisi ammortizzata ottimista nasconde uno spike.

Per gli LLM, le costanti dominano spesso il termine asintotico

Per un Transformer, costo attention per layer = O(n² d + n d²). Quando n ≈ d (qualche migliaio di token, dimensione modello qualche migliaio), i due termini sono dello stesso ordine. La FFN ha costo O(n · d²) e con d_ff = 4d nel feed-forward (SwiGLU triplica), in pratica la FFN è il termine dominante per context “normali” (≤ 4k). Solo oltre il punto di pareggio l’attention diventa il bottleneck.

Risultato: ottimizzare la FFN (MoE, sparsità, quantization) ha effetto immediato per la maggior parte dei workload. Ottimizzare l’attention (FlashAttention, sub-quadratic) ha effetto su long-context. Capire quale dei due termini domina richiede di guardare le costanti, non solo la classe asintotica.

Quantization e MoE non cambiano la classe

Quantization (int8, int4, GPTQ, AWQ) e Mixture of Experts (un sottoinsieme di esperti attivo per token) sono ottimizzazioni potenti, ma vivono dentro la stessa classe asintotica. Quantization a int8 rispetto a fp16 non cambia O(FLOPs); cambia il throughput per FLOP del 2x circa, e dimezza l’occupazione di memoria. MoE con 8 esperti e 2 attivi non riduce O(seq · d²); riduce la costante di un fattore 4.

Sono ingegneria delle costanti, non cambio di scala. Per cambi di scala servono modifiche all’algoritmo (FlashAttention sulla memoria, sub-quadratic attention sui FLOP).

Distinguere “ottimizzazione di costanti” da “cambio di classe asintotica” è un esercizio di lettura tecnica utile ogni volta che esce un paper o un benchmark con claim di speedup.

Concurrency aggiunge dimensioni

Big-O classica è single-thread. Algoritmi paralleli si misurano con due quantità: work (totale di operazioni, come Big-O classica) e span (cammino critico, lunghezza minima di esecuzione con infiniti core). Un algoritmo è scalabile sse span è O(log n) o O(n^ε). Merge sort parallelo: work O(n log n), span O(log² n). Self-attention è altamente parallelizzabile (matmul si parallelizza bene), ma la dipendenza autoregressive nel decoding linearizza tutto.

Distribuzione di input nel mondo reale

L’analisi worst case assume input avversariale, l’average case assume una distribuzione uniforme o random. La produzione ha una sua distribuzione, spesso pesantemente skewed.

Esempio: un parser di documenti che vede in produzione il 95% di file da 1-10 MB e il 5% da 100 MB-1 GB. Un algoritmo O(n²) accettabile sul worst-case del 95% genera timeout sistematici sul 5% restante. La metrica utile non è il valore atteso ma p95, p99, p999 della latenza.

Lo stesso vale per il context length nei sistemi LLM. Un endpoint dimensionato per “context medio 4k” si rompe quando un utente carica un PDF da 200 pagine. Le scelte di rate limiting, queueing, model routing, fallback sono tutte gestione della coda di destra della distribuzione.

Lower bound aperti e algoritmi galattici

Per molte classi di problemi non sappiamo se l’algoritmo migliore sia ottimale. Matrix multiplication è O(n^{2.371…}) con i risultati più recenti (Williams 2024, ricalibrazione di Coppersmith-Winograd). Il lower bound noto è Ω(n²). C’è un gap pluri-decennale tra teoria e pratica.

Alcuni algoritmi con classe asintotica strepitosa hanno costanti talmente grandi da essere inutili in pratica: si chiamano galactic algorithms. Servono a stabilire upper bound teorici, non per essere implementati. La distinzione tra “esiste un algoritmo asintoticamente ottimo” e “esiste un algoritmo praticamente usabile” è centrale.

Benchmark empirici contro analisi asintotica

L’analisi asintotica è un orizzonte. Per workload di produzione serve sempre la misurazione: profiling, benchmark, distribuzione reale di input. Un algoritmo asintoticamente ottimo può essere lento per le n di interesse. Un algoritmo “peggiore” può essere più veloce con costanti migliori. Per le matrici che effettivamente girano su una GPU di un datacenter, il numero da misurare è il throughput di token al secondo, non un esponente.

Constant factors in floating point

Un dettaglio finale: nelle moderne accelerator architecture le diverse precisioni hanno throughput diversi. Su una H100, fp32 fa circa 67 TFLOPs, bf16/fp16 circa 990 TFLOPs (con tensor core), fp8 ~2000 TFLOPs, int8 simile. Un cambio di precisione che lascia invariata l’O dell’algoritmo cambia il throughput di un fattore 30. Questo è puro factor di costante che, in pratica, fa la differenza tra un training fattibile e uno no.

Ignorare questi fattori usando solo Big-O porta a stime di costo sbagliate di un ordine di grandezza. Non è un difetto della notazione: è il prezzo di un’astrazione che è progettata per ignorare le costanti, applicata a un mondo in cui le costanti dominano.

Collegamenti

Questo capitolo si appoggia su alcuni capitoli precedenti e prepara molti capitoli successivi.

• vettori e spazi: le complessità su vettori (kNN, distanze) presuppongono il vocabolario di vettori e dimensione.
• norme e distanze: i costi di una similarity search dipendono dalla metrica scelta; cosine vs L2 cambia poco la classe ma cambia le costanti.
• matrici e trasformazioni: il costo cubico O(n³) di matrix multiply naive è la radice della maggior parte dei costi in deep learning.
• autovalori e autovettori: SVD ha complessità O(n³) e questo limita la sua applicabilità diretta a matrici grandi.
• curse della dimensionalità: la complessità di kNN naive O(n d) e i limiti di indici metrici in alta dimensione si toccano direttamente.
• bias-varianza: la complessità di un modello (non temporale, ma di capacità) è connessa al rischio di overfitting; sono due lenti diverse della parola “complessità”.
• attention-intuizione (in preparazione): la Tabella 1 di Vaswani et al. 2017 vive su questo capitolo.
• flash-attention (in preparazione): è il caso di studio prototipo di “stesso O, costanti diverse”.
• kv-cache (in preparazione): è il caso di studio prototipo di “trade-off spazio-tempo in produzione”.
• ann-hnsw (in preparazione): la pratica di O(log n) per nearest neighbor.
• ssm-mamba (in preparazione): il ritorno del lineare via state space model.
• rag-base (in preparazione): l’architettura retrieval-augmented dipende interamente dalla complessità della similarity search.

Lessico minimo da portare via

Un breve glossario operativo dei termini usati sopra, da tenere a portata:

• Asintotico: comportamento per n abbastanza grande. Non dice niente su n piccoli.
• Worst case: garanzia su qualsiasi input. Quello che si scrive nei contratti SLA.
• Average case: valore atteso su una distribuzione assunta. Sempre da specificare quale.
• Ammortizzato: media temporale su una sequenza di operazioni. Va distinto dall’average sulle operazioni singole.
• FLOP: floating-point operation. Un’addizione o una moltiplicazione fp.
• HBM: high-bandwidth memory, la memoria principale di una GPU moderna. Contrapposto a SRAM on-chip.
• MFU (model FLOPs utilization): rapporto tra FLOPs effettivamente usati e picco teorico dell’hardware. Tipicamente 30-50% in training; valori sopra 60% sono eccellenti.
• Compute-optimal: allocazione di parametri e dati che minimizza loss a budget di compute fissato.

Questi otto termini, più la notazione O/Ω/Θ, coprono il novanta per cento delle conversazioni tecniche su scaling.

Per andare oltre

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (MIT Press, 3rd ed., 2009). Cap. 3 per le definizioni asintotiche, cap. 4 per il master theorem, cap. 17 per l’analisi ammortizzata. Riferimento standard universale.
• Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (Addison-Wesley, 3rd ed., 1997). Sezione 1.2.11 sulla notazione asintotica, livello di rigore matematico massimo.
• Sipser, Introduction to the Theory of Computation (Cengage, 3rd ed., 2012). Cap. 7 per P, NP, NP-completeness in modo introduttivo ma rigoroso.
• Vaswani et al., “Attention Is All You Need”, NeurIPS 2017. La Tabella 1 è il riferimento più citato per la complessità del Transformer.
• Dao et al., “FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness”, NeurIPS 2022. Lettura obbligata per capire perché le costanti contano in GPU.