  Large language models (LLMs) like transformers have impressive in-context
learning (ICL) capabilities; they can generate predictions for new queries
based on input-output sequences in prompts without parameter updates. While
many theories have attempted to explain ICL, they often focus on structured
training data similar to ICL tasks, such as regression. In practice, however,
these models are trained in an unsupervised manner on unstructured text data,
which bears little resemblance to ICL tasks. To this end, we investigate how
ICL emerges from unsupervised training on unstructured data. The key
observation is that ICL can arise simply by modeling co-occurrence information
using classical language models like continuous bag of words (CBOW), which we
theoretically prove and empirically validate. Furthermore, we establish the
necessity of positional information and noise structure to generalize ICL to
unseen data. Finally, we present instances where ICL fails and provide
theoretical explanations; they suggest that the ICL ability of LLMs to identify
certain tasks can be sensitive to the structure of the training data.
