Compositional Reasoning and Planning with Foundation Models

Abstract:

Foundation models refer to large neural networks pre-trained by internet-scale data and possess vast commonsense knowledge. However, they struggle with compositional tasks in reasoning and planning. In those tasks, evidence is scattered across multiple sources and needs to be considered together simultaneously or connected in a multi-step process to solve the task. To address this issue, this thesis propose integrating appropriate compositional inductive biases (e.g., tree search or graphical models) with foundation models, which should reduce the sample complexity of learning while adapting to the problem's inherent computational complexity.

We explore various aspects of the compositionality of reasoning and planning. Specifically, we (1) leverage vision-language models (VLMs) within a graphical structure for instruction comprehension and spatial reasoning; (2) incorporate large language models as both heuristic policy and world models in Monte-Carlo Tree Search (MCTS) for large-scale, partially observable task planning; (3) employ VLMs as reward models in MCTS for constrained generation. Finally, we summarise our findings and empirical evidence and link them with the sample and computational complexity in machine learning. We show that effective reasoning requires (i) sufficient task decomposition to reduce the sample complexity, which could be quantified by low description length, and (ii) reasoning structures that are appropriate to the computational complexity of the problem (e.g., complex structures are more effective for computationally harder problems). These insights pave the way for more robust and adaptable compositional reasoning frameworks.