Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformers
Yixiao Huang, Hanlin Zhu, Tianyu Guo, Jiantao Jiao, Somayeh Sojoudi, Michael Jordan, Stuart J Russell, Song Mei
Recent work found that large language models (LLMs) are able to deduce implications from learned facts during training.  For example, when seeing individuals who both live in Paris and speak French in the training data, LLM will automatically deduce that a new person speaks French if the model learns that the same person also lives in Paris. In this paper, we theoretically study how transformers learn to deduce such implications from facts. Surprisingly, we find that a one-layer attention-only transformer is enough to learn to deduce implications from learned facts -- a task typically framed as a two-hop problem that would seemingly require at least a two-layer transformer.  Our theoretical analysis on the output-value matrix parameters $(\boldsymbol{W}\_{\mathsf O},\boldsymbol{W}\_{\mathsf V})$ shows that the generalization capability can be attributed to the implicit bias of gradient descent. Specifically, gradient descent directionally converges to an SVM solution minimizing the nuclear norm of the combined parameter $\boldsymbol{W}\_{\mathsf{OV}}:= \boldsymbol{W}\_{\mathsf O}\boldsymbol{W}\_{\mathsf V}^\top$. Further analysis of this SVM solution reveals that one-layer attention-only transformers can associate facts and implications with only a few training samples, no matter whether the fact and implication are causally correlated. Finally, we empirically verify our finding in both a one-layer attention model and several real-world LLMs (e.g., Gemma-2-9B). While this sample-efficient reasoning pattern equips LLMs with strong generalization capability, it also causes LLMs to hallucinate easily by deducing false implications when two events are not causally related but only co-occur several times, which provides a possible explanation of hallucination in LLMs.