The Library Theorem: How External Organization Governs Agentic Reasoning Capacity

Titolo: Il Teorema della Biblioteca: Come l'Organizzazione Esterna Governa la Capacità di Ragionamento Agente

Autore: Zachary F. Mainen (Fondazione Champalimaud, Lisbona)
Data: Marzo 2026

1. Il Problema

Gli agenti basati su trasformatori estendono le capacità dei modelli linguistici (LLM) attraverso l'uso di strumenti (tool-augmented agents), permettendo loro di eseguire catene di pensiero (Chain-of-Thought) su più passi, leggere file, interrogare database e scrivere risultati. Tuttavia, un quesito fondamentale rimaneva formalmente irrisolto: come influisce l'organizzazione dello stato esterno dell'agente sul costo computazionale del ragionamento?

Attualmente, la maggior parte degli agenti gestisce la propria storia di conversazione o i risultati intermedi come un nastro sequenziale (flat history). Per recuperare una informazione specifica in una storia di $N$ pagine, l'agente deve scansionare linearmente, rendendo il costo di recupero $\Omega(N)$. Al contrario, un sistema di file strutturato o un indice (come un albero B) permette l'accesso casuale, riducendo il costo a $O(\log_b N)$. Il paper indaga se questa differenza teorica si traduca in un vantaggio pratico reale per gli agenti LLM e come la familiarità con i contenuti influenzi questo processo.

2. Metodologia e Formalizzazione

Il Modello Teorico: La Finestra di Contesto come Pagina I/O

L'autore formalizza il contesto del trasformatore come una pagina I/O (Input/Output) di dimensione limitata $C$ token.

• Accesso Sequenziale: L'agente legge le pagine in ordine. Trovare un elemento in un archivio di $N$ pagine richiede $\Omega(N)$ letture nel caso peggiore.
• Accesso Indicizzato: L'archivio è organizzato come un albero B con fattore di diramazione $b$. La navigazione dalla radice alla foglia richiede $\lceil \log_b N \rceil$ letture di indici + 1 lettura dati.
• Teorema della Separazione: La differenza tra i due approcci è esponenziale. Su un processo di ragionamento di $T$ passi con uno stato accumulato, il costo cumulativo è:
  • Sequenziale: $\Theta(T^2)$ (costo quadratico).
  • Indicizzato: $O(T \log_b T)$ (costo log-lineare).

Esperimenti Controllati

Per validare le previsioni teoriche, è stato creato un benchmark di lookup controllato testato su due modelli (GPT-4o-mini e GPT-5.4) con tre tipi di contenuto per isolare l'effetto della familiarità:

1. Hash (Contenuto Astratto): Chiavi e valori casuali (es. interi a 4 cifre, stringhe a 4 lettere). Il modello non ha conoscenze pregresse.
2. Numerico (Contenuto Ordinato ma Astratto): Integers ordinati (es. "Item 247: 247"). Il modello potrebbe teoricamente indovinare, ma deve seguire il protocollo.
3. Enciclopedia (Contenuto Familiare): Fatti reali su parole inglesi (es. "acetylene"). Il modello possiede forte conoscenza parametrica su questi argomenti.

Condizioni di Test:

• FLAT: Storia piatta, accesso sequenziale.
• INDEXED: Accesso tramite indice (TOC) che mappa le chiavi alle pagine.
• FLAT-SORTED: Pagine ordinate, ma senza indice esplicito (testa se il modello può fare ricerca binaria autonomamente).
• DEEP-INDEXED: Indice a due livelli (Master TOC -> Section TOC -> Pagina) per gestire archivi molto grandi.

3. Contributi Chiave

1. Modello Formale: Identificazione della finestra di contesto come pagina I/O, dimostrando una separazione esponenziale tra recupero sequenziale e indicizzato.
2. Previsioni Quantitative:
   • Soglia nel contesto: Nessun ragionamento interno (senza memoria esterna) può superare un limite lineare di recupero.
   • Vantaggio Indicizzato: Gli scratchpad strutturati superano quelli piatti, con un vantaggio che scala con $N$.
   • Compounding: Il vantaggio si accumula con la profondità del ragionamento ($T$).
3. Scoperta della "Competizione della Memoria Parametrica": Identificazione di un fallimento critico quando il contenuto è familiare: il modello ignora il protocollo di recupero per generare risposte dalla sua memoria interna, fallendo catastroficamente.
4. Principio di Progettazione: Separazione dei compiti: usare i LLM per la costruzione dell'indice (dove la comprensione semantica aiuta) e algoritmi deterministici per la navigazione dell'indice (dove la semantica è dannosa).

4. Risultati Sperimentali

Contenuto Astratto (Hash e Numerico)

• Conferma Teorica: L'agente indicizzato ha mantenuto una lettura mediana di 1 pagina indipendentemente dalla dimensione dell'archivio (fino a 5.000 item), confermando la previsione $O(1)$ per il recupero.
• Costo dei Token: Il costo token per l'agente FLAT è cresciuto quadraticamente (da 174K a 914K token raddoppiando gli item), mentre per l'agente INDICIZZATO è cresciuto linearmente (da 842 a 5.950 token). Il rapporto di separazione è arrivato a 153x.
• Limiti della Ricerca Binaria Interna: Anche il modello più potente (GPT-5.4) ha fallito nel mantenere una ricerca binaria efficace su pagine ordinate senza indice esplicito a scale elevate, mentre l'indice esplicito ha funzionato perfettamente.

Contenuto Familiare (Enciclopedia)

• Fallimento Catastrofico: Nonostante l'indice fosse correttamente costruito, l'accuratezza è crollata (dal 90% al 27% per M=200).
• Meccanismo: Il modello, riconoscendo l'argomento, ha bypassato il protocollo di recupero (tool call) generando risposte dalla sua memoria parametrica. Questo ha portato a loop di allucinazione e esaurimento del budget token (fino a 100k token per tentativo).
• Conclusione: La familiarità semantica crea un percorso competitivo che disabilita la disciplina necessaria per seguire il protocollo di navigazione.

5. Significato e Implicazioni

Il "Teorema della Biblioteca" ha profonde implicazioni per l'architettura degli agenti AI:

1. Necessità Computazionale, non Solo Comodità: L'organizzazione della memoria non è un optional, ma una necessità computazionale per scalare il ragionamento. Senza indicizzazione, il costo del ragionamento diventa quadratico, rendendo i task a lungo termine proibitivi.
2. Separazione dei Compiti (Construction vs. Traversal):
   • Costruzione dell'Indice: I LLM sono eccellenti per capire il contenuto e decidere come organizzarlo (naming, categorizzazione).
   • Navigazione dell'Indice: I LLM sono pessimi nel seguire protocolli di navigazione rigidi quando la familiarità semantica li tenta a fare scorciatoie. La navigazione deve essere affidata ad algoritmi deterministici (es. script che leggono l'indice e chiamano gli strumenti specifici senza generazione di testo intermedia).
3. Cognizione Estesa: Il paper supporta la tesi della "cognizione estesa": un agente con un sistema di file indicizzato non è solo un modello con uno strumento, ma un sistema cognitivo diverso con capacità di ragionamento esponenzialmente superiori, a patto che il vincolo di disciplina (non bypassare l'indice) sia mantenuto.
4. Architettura Futura: Gli agenti attuali dovrebbero evolvere da una memoria "piatta" (chat history) a una gerarchia di memoria indicizzata (file system strutturato), ma con un'interfaccia di navigazione che isola il modello dalle tentazioni semantiche durante il recupero dei dati.

In sintesi, il paper dimostra che mentre i LLM possono capire come organizzare la conoscenza, non possono affidarsi a se stessi per recuperarla in modo efficiente su larga scala senza un'architettura esterna che imponga un accesso deterministico e indicizzato.