Algorithmic reasoning in large language models and neuro-symbolic architectures

Rule-based systems from the tradition of artificial intelligence possess reliable reasoning capabilities, but struggle with flexibility and scalability. Conversely, modern deep learning-based systems have demonstrated impressive performance in a wide variety of tasks requiring ``fast thinking'', but lack robust reasoning capabilities. Motivated by the need to overcome these limitations, this thesis investigates the design of AI systems that can learn to reason systematically. Drawing from a rich tradition of AI and cognitive science, we leverage the concept of compositionality as a common thread in our research. The contributions we offer are twofold. First, we investigate the systematic reasoning capabilities of Large Language Models probing them on the simplification of nested mathematical formulas, a problem that reflects key properties of compositionality. Our experimental results on Llama 2 and GPT models reveal that while scaling LLMs brings some improvements, their systematic reasoning capabilities remain limited, even with specialized prompting methods like chain-of-thought reasoning. Second, we propose a neuro-symbolic framework designed to learn and execute convergent term rewriting systems, which can formally describe simple algorithms for the iterative simplification of nested mathematical formulas. The framework is implemented in two variants: NRS and FastNRS. We benchmark these implementations against the Neural Data Router, OpenAI’s GPT-4 and o1-preview, demonstrating the robust systematic reasoning capability of our neuro-symbolic approach, while critically assessing the impact of our design choices on efficiency and their limitations.