ASTRAIL: A TRAINING-FREE NEURO-SYMBOLIC KGQA WITH SMALL LANGUAGE MODELS

Large Language Models (LLMs) have improved complex reasoning, but their dependence on large parameter counts, remote infrastructure, and costly inference makes them difficult to deploy in privacy-sensitive and resource-constrained settings. Small Language Models (SLMs) are more suitable for local execution, yet they lack the parametric memory, long-context robustness, and multi-hop reasoning ability required for Knowledge Graph Question Answering (KGQA). Existing retrieval-augmented and graph-agent approaches reduce this burden, but often still leave the model responsible for interpreting noisy evidence, selecting valid graph operations, and obeying tool syntax through soft prompting. This thesis proposes ASTRaIL, a training-free neuro-symbolic framework for local KGQA with SLMs. The central idea is to treat the knowledge graph not as passive text to be serialized into the prompt, but as executable memory. ASTRaIL materializes the graph offline, anchors the query to relevant entities, restricts the runtime search space through anchor-biased graph retrieval, and ranks candidate relation paths using semantic, type-aware, and topological signals. The SLM mainly selects the next operation, while the graph and executor handle facts and traversal. ASTRaIL further introduces a state-conditioned decoding layer, Railgun, which compiles the graph operations valid in the current symbolic state into tokenizer-level constraints. This prevents malformed commands, unavailable relations, illegal directions, and invalid variable references from reaching the executor. ASTRaIL investigates how tiny, untrained language models can support structured multi-hop reasoning under local, privacy-preserving, and training-free deployment constraints.

I Large Language Models (LLMs) hanno migliorato il reasoning complesso, ma la loro dipendenza da un elevato numero di parametri, da infrastrutture remote e da un'inference costosa ne rende difficile il deployment in contesti privacy-sensitive e resource-constrained. Gli Small Language Models (SLMs) sono più adatti all'esecuzione locale, ma non dispongono della memoria parametrica, della robustezza su contesti lunghi e della capacità di reasoning multi-hop richieste dal Knowledge Graph Question Answering (KGQA). Gli approcci retrieval-augmented e graph-agent esistenti riducono questo carico, ma spesso lasciano ancora al modello la responsabilità di interpretare evidenze rumorose, selezionare operazioni valide sul grafo e rispettare la sintassi dei tool attraverso soft prompting. Questa tesi propone ASTRaIL, un framework neuro-simbolico training-free per KGQA locale con SLMs. L'idea centrale è trattare il knowledge graph non come testo passivo da serializzare nel prompt, ma come executable memory. ASTRaIL materializza il grafo offline, ancora la query a entità rilevanti, restringe lo spazio di ricerca a runtime attraverso anchor-biased graph retrieval e ordina i relation paths candidati utilizzando segnali semantici, type-aware e topologici. Lo SLM seleziona principalmente la prossima operazione, mentre il grafo e l'executor gestiscono i fatti e la traversal. ASTRaIL introduce inoltre un livello di decoding state-conditioned, Railgun, che compila le operazioni sul grafo valide nello stato simbolico corrente in vincoli a livello di tokenizer. Questo impedisce a comandi malformati, relazioni non disponibili, direzioni non ammissibili e riferimenti a variabili non validi di raggiungere l'executor. ASTRaIL investiga come language models molto piccoli e non addestrati possano supportare reasoning multi-hop strutturato sotto vincoli di deployment locale, privacy-preserving e training-free.