Simple mechanisms for representing, indexing and manipulating concepts

Yuanzhi Li, Raghu Meka, Rina Panigrahy, Kulin ShahSubmission to ICLR 2024 · Rejected

TL;DR

Rather than defining concepts as black-box classifier boundaries trained via gradient descent, this paper formalizes concepts as low-dimensional algebraic manifolds captured by the null space of their moment matrices. These algebraic "concept signatures" can be composed, intersected, and stacked hierarchically, providing a theoretical foundation that maps naturally onto transformer attention layers, random-weight MLPs, and memory tables.

What Problem Does This Paper Address?

Deep learning models typically learn concepts implicitly through end-to-end classification and gradient descent. However, this approach leaves fundamental gaps:

  • What is a concept mathematically?
  • How can concepts be discovered without explicit labels?
  • How can models manipulate concepts (e.g., finding the intersection of two concepts or abstracting sub-parts into a whole)?

Existing memory-augmented models and interpretability studies suggest that feed-forward networks act as key-value stores of concepts, but they do not explain the computational mechanics of concept formation, composition, and hierarchy.

Methods

The authors formalize a concept as an algebraic manifold $\mathcal{M} = \{x : P(x) = 0\}$ defined by a set of low-degree polynomial equations.

  1. Kernel and Null-Space Signatures: Given points $X = \{x_1, \dots, x_N\}$ and a polynomial feature map $\phi(x)$, the empirical moment matrix is $M(X) = \frac{1}{N} \sum_{i} \phi(x_i)\phi(x_i)^\top$. The concept signature $T(X)$ is defined as the projection onto the null space of $M(X)$.

  2. Membership Testing: A query point $x$ belongs to $\mathcal{M}$ if and only if $S(x) \cdot T(X) = 0$, where $S(x) = \phi(x)\phi(x)^\top$.

  3. Sample Complexity: Using random projections (Johnson-Lindenstrauss-style bounds for manifolds), the required sample size and signature dimension shrink to $r^{\tilde{O}(k^2)}$, independent of the ambient dimension $d$.
  4. Concept Algebra (Intersection and Hierarchy):
  5. Intersection: If $F(U) = I - T(U)$ is the subspace projection operator, the intersection of two concepts $U_1 \cap U_2$ corresponds to alternating projection iterations: $F(U_1 \cap U_2) = (F(U_1)F(U_2))^\infty$.
  6. Signatures of Signatures: Because individual signatures of related concepts (e.g., concentric circles of different radii) themselves lie on low-dimensional manifolds, taking the null space of their moments yields higher-level abstractions (e.g., the general concept of "circle").
  7. Mapping to Transformers:
  8. Attention: Points on low-dimensional manifolds have higher cosine similarities than random points, meaning standard dot-product attention naturally clusters tokens belonging to the same concept.
  9. MLP Layers: The authors prove (Theorem 6.1) that a two-layer neural network with standard Gaussian random weights and quadratic activations $\sigma(z) = z^2$ computes $M(X)$ and powers like $M(X)^2$ via fixed linear projections, enabling power iteration to extract the null space.
  10. Concept Memory: Each layer is augmented with a signature dictionary tracking past concepts.

Datasets

The empirical validation uses synthetic 2D geometric datasets designed to test hierarchical grouping:

  • $n$-circles: Concentric circles of radii $\{1, 2, \dots, n\}$ centered at the origin.
  • $n$-circles + $n$-parabolas: A combination of $n$ concentric circles and $n$ vertically shifted parabolas ($y = x^2 + c$) with overlapping coordinate ranges, testing whether distinct concept families separate cleanly.

Evaluations were performed for $n \in \{4, 6, 8\}$ using polynomial feature expansions up to degree 2, varying memory storage sizes from 4,000 to 5,500 entries.

Key Insights and Ideas

  • Concept Discovery via Linear Algebra: Manifold identification does not require iterative gradient descent; it can be achieved directly via spectral decomposition / null-space projection of moment statistics.
  • Semantic Operations as Matrix Operations: Finding common traits across distinct entities (e.g., isolating "motion direction" from two different moving objects, or finding the shared concept of rotation) maps directly to subspace intersections.
  • Transformers as Moment Analyzers: Transformer building blocks can be viewed through an algebraic lens—attention aggregates manifold samples into empirical moments, while MLP blocks compute matrix polynomials that project onto the null space.

Key Results

  • Purity of Attended Concepts: In synthetic experiments, the attention mechanism in the concept discovery unit attended almost exclusively to signatures within the same concept family:
  • Layer 2: 96.0%–99.0% same-concept attention on $n$-circles; 96.9%–98.9% on circles + parabolas.
  • Layer 3 (Abstract concepts): 98.7%–99.7% precision across different configurations.
  • Out-of-Distribution Generalization: When presented with circles of unseen radii sampled from $[1, 10]$ outside the training set, Layer 3 representations successfully matched the generalized "circle" concept signature with 84% to 98% accuracy (improving monotonically with memory size).

Limitations and Future Work

  • Synthetic Experiments Only: Empirical evaluations are limited to 2D geometric shapes (circles and parabolas). Real-world domains (e.g., vision, natural language) are discussed theoretically (e.g., image rotation/translation manifolds) but lack experimental demonstration.
  • Curse of Dimensionality in Monomial Maps: While random projection reduces the ambient dimension, polynomial feature expansions $\phi(x)$ of degree $\ell$ scale combinatorially in manifold dimension $k$ and degree $r$, restricting practical application to low-degree, low-dimensional manifolds.
  • Architectural Scaling: The paper establishes mathematical equivalence using random Gaussian weights and quadratic activations; implementing and scaling this as an end-to-end trainable architecture on complex benchmarks remains open for future research.

Summary updated

Abstract

Deep networks typically learn concepts via classifiers, which involves setting up a model and training it via grading descent to fit the concept-labeled data. We will argue instead that learning a concept could be done by looking at its moment statistics matrix to generate a concrete representation or signature of that concept. These signatures can be used to discover structure across the set of concepts and could recursively produce higher-level concepts by learning this structure from those signatures. Concepts can be ’intersected’ to find a common theme in a number of related concepts. This process could be used to keep a dictionary of concepts so that inputs could correctly identify and be routed to the set of concepts involved in the (latent) generation of the input.
BibTeX
@misc{li2023simple,
  author = {Yuanzhi Li and Raghu Meka and Rina Panigrahy and Kulin Shah},
  title = {{Simple mechanisms for representing, indexing and manipulating concepts}},
  year = {2023},
  eprint = {2310.12143},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.12143},
}
Figure