Learning Partitions from Context

Simon BuchholzNeurIPS 2024 · OpenReview

In modern artificial intelligence, discrete entities—such as words, pixels, or user IDs—are typically represented as continuous vectors known as embeddings. A fascinating phenomenon observed in models like Large Language Models (LLMs) is that, after training, these embeddings naturally organize into meaningful semantic clusters. For instance, words representing animals group together, and complex relational structures emerge.

But why and how does this happen? If we have a set of $N$ tokens belonging to a few hidden categories, and we only observe sparse, indirect interactions between them (e.g., "Token A and Token B appear together in this context"), can we theoretically guarantee that a neural network will discover these underlying categories? This paper provides a theoretical bridge between the discrete world of categories and the continuous world of machine learning embeddings, exploring how simple gradient-based training can uncover hidden structural partitions.

The Problem: Discovering Hidden Partitions

The core challenge is learning discrete partitions from sparse, high-dimensional interaction data. The authors model this by assuming tokens can be partitioned into a small number of classes. A real-valued function $f$ captures the interactions between tokens across different "slots" or contexts, depending entirely on the class memberships of its arguments. The goal is to recover the exact class memberships of all tokens from a finite number of samples of $f$.

Illustration of tokens partitioned into classes across different interaction slots.

Theoretical Framework

The paper approaches this partition recovery problem through three distinct mathematical lenses:

  1. Complexity Theory: The general problem of finding the optimal partition to explain a set of interactions is proven to be NP-complete (via reduction to the 3SAT problem). This establishes that no universally fast algorithm exists for every possible worst-case scenario.
  2. Information Theory: Despite the worst-case hardness, the author calculates the absolute minimum data required for random instances. For $N$ tokens, roughly $O(N \ln N)$ samples are sufficient to uniquely identify the hidden structure. This implies that even if interactions are incredibly sparse, the underlying "logic" of the categories can still emerge.
  3. Gradient Dynamics: The heart of the paper analyzes the "gradient flow" (the continuous analog of gradient descent) of token embeddings. Focusing on slot-wise linear functions—a mathematical class mimicking the linearized attention mechanisms in Transformers—the author uses Taylor expansions of the loss function to track how embeddings gravitate toward their respective "class centers" during training.

Key Insights and Results

The theoretical findings are supported by mathematical simulations demonstrating how token embeddings behave over time.

Simulated trajectories of token embeddings converging into distinct clusters during gradient descent.
  • The Power of Sparsity: You do not need to observe every possible combination of tokens to understand the underlying rules. The $O(N \ln N)$ bound confirms that highly sparse data is sufficient for partition recovery.
  • Curvature and Clustering: The "shape" or curvature of the interaction function typically pushes similar tokens apart. However, by utilizing slot-wise linear functions, this repulsive force is minimized. This allows tokens belonging to the same class to successfully converge to the same point in the embedding space.
  • Gradient Recovery and Stability: The research proves that if initial embeddings are reasonably positioned, gradient descent forces all tokens of the same class to converge. Furthermore, once these clusters form, the dynamics become stable. The clusters resist being broken apart by subsequent training, provided the sample size is on the order of $O(N^2 \ln^2 N)$.

Limitations and Future Directions

While providing a strong theoretical foundation, the paper notes several limitations that pave the way for future research:

  • The "Platypus" Problem: The current model assumes tokens within a class behave identically. Real-world categories often have exceptions, noisy memberships, or overlapping boundaries, which the current theory does not yet accommodate.
  • Dimensionality Constraints: The mathematical proofs require the embedding dimension to be relatively small. In practice, LLMs utilize massive, high-dimensional spaces. Investigating how high dimensionality impacts this clustering process is a crucial next step.
  • Initialization Assumptions: The stability results currently rely on a specific initialization close to the global minimum. Future work will need to explore whether standard random initialization techniques (like Xavier or Kaiming) naturally lead to these same convergence guarantees.

Summary updated

Abstract

In this paper, we study the problem of learning the structure of a discrete set of $N$ tokens based on their interactions with other tokens. We focus on a setting where the tokens can be partitioned into a small number of classes, and there exists a real-valued function $f$ defined on certain sets of tokens. This function, which captures the interactions between tokens, depends only on the class memberships of its arguments. The goal is to recover the class memberships of all tokens from a finite number of samples of $f$. We begin by analyzing this problem from both complexity-theoretic and information-theoretic viewpoints. We prove that it is NP-complete in general, and for random instances, we show that on the order of $N\ln(N)$ samples, implying very sparse interactions, suffice to identify the partition. We then investigate the conditions under which gradient flow dynamics of token embeddings can reveal the class structure, finding that this is achievable in certain settings when given on the order of $N^2\ln^2(N)$ samples.
BibTeX
@inproceedings{buchholz2024learning,
  author = {Simon Buchholz},
  title = {{Learning Partitions from Context}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=pRSgf5VdD0},
}
Figure