Tensor Networks for Language Modeling

Jacob Miller, Guillaume Rabusseau, John Terilla

Abstract

Tensor networks are a powerful modeling framework developed for computational many-body physics, which have only recently been applied within machine learning. In this work we utilize a uniform matrix product state (u-MPS) model for probabilistic modeling of sequence data. We first show that u-MPS enable sequence-level parallelism, with length-n sequences able to be evaluated in depth O(log n). We then introduce a novel generative algorithm giving trained u-MPS the ability to efficiently sample from a wide variety of conditional distributions, each one defined by a regular expression. Special cases of this algorithm correspond to autoregressive and fill-in-the-blank sampling, but more complex regular expressions permit the generation of richly structured data in a manner that has no direct analogue in neural generative models. Experiments on sequence modeling with synthetic and real text data show u-MPS outperforming a variety of baselines and effectively generalizing their predictions in the presence of limited data.

Introduction

Recurrent Neural Networks (RNNs) have long been a staple of sequence modeling, yet they suffer from a fundamental bottleneck: their sequential nature. Because each hidden state depends on the previous one, computation time for a sequence of length $n$ scales as $O(n)$. While Transformers addressed this through self-attention, they often require vast amounts of data to generalize the underlying rules of formal languages. This paper explores an alternative inspired by quantum physics: uniform Matrix Product States (u-MPS). By utilizing linear recurrence, u-MPS achieve logarithmic-time parallel evaluation and provide a unique mathematical framework for constrained generative sampling.

The u-MPS Framework

In physics, Matrix Product States describe systems of many interacting particles. In the context of language modeling, they represent a sequence of tokens. Unlike standard RNNs that rely on nonlinear activation functions (like ReLU or Tanh), u-MPS utilize linear matrix multiplications.

To convert these matrix products into valid probabilities, the model employs the Born rule from quantum mechanics, where the probability of a sequence $s$ is proportional to the square of the model's output: $P(s) \propto |f(s)|^2$. This ensures non-negative probabilities without the need for traditional softmax layers.

Parallel Evaluation and Logarithmic Depth

The defining advantage of linear recurrence is its associativity. Because the model lacks nonlinearities between steps, the product of a sequence of matrices can be grouped and calculated in parallel. This reduces the evaluation depth from $O(n)$ to $O(\log n)$.

Figure 2: Comparison of parallel and sequential evaluation strategies for u-MPS. Parallel evaluation allows for O(log n) depth by grouping matrix multiplications.

On modern hardware like GPUs, this theoretical advantage translates into significant practical speedups for long sequences. While sequential evaluation remains efficient for short strings, parallel evaluation becomes the superior method as sequence length increases, maintaining the recurrent state's benefits without the $O(n)$ time penalty.

Generative Sampling with Regular Expressions

A core innovation of this work is the integration of regular expressions (regex) directly into the generative process. The authors developed a "dictionary" that maps regex operations—such as concatenation, union, and the Kleene star—to transfer operators (linear maps on matrices).

This allows a single trained u-MPS to perform complex tasks without retraining, including:

  • Autoregressive sampling: Standard left-to-right generation.
  • Fill-in-the-blank: Generating missing tokens within a fixed structure.
  • Regex-constrained generation: Ensuring the output matches a specific pattern, such as a valid email address ([email protected]).

Because the model understands the transfer operator of the regex, it can sample directly from the constrained distribution without the overhead of rejection sampling.

Experimental Evaluation

The model was benchmarked against LSTMs, HMMs, and Transformers using the Tomita Grammars, a set of seven binary formal languages. u-MPS demonstrated superior generalization, particularly when tested on sequences longer than those seen during training.

Figure 4: Performance comparison on Tomita grammar benchmarks across different model architectures.

As shown in the results, u-MPS achieved 100% accuracy on several Tomita tasks (such as Tomita 3 and 5) even when the sample length was nearly double the training length. In contrast, LSTMs often saw performance drop to near-chance levels (~50%) under the same conditions.

Further testing on the CLAIR Fraudulent Email Dataset showed that using a "regex regularizer" during training improved both the perplexity and the syntactic correctness of generated text. For instance, the percentage of syntactically correct email addresses generated rose from 35.4% to 37.2% when the model was constrained by the underlying structure of the data.

Limitations and Future Directions

Despite its strengths, the u-MPS model faces scaling challenges related to the bond dimension ($D$), which represents the size of the hidden state. Computational costs scale as $O(D^3)$ or higher for certain operations, making large-scale deployment more expensive than traditional RNNs.

Future work aims to extend this framework to context-free languages, which are necessary for modeling nested structures like programming code or complex natural language. While this requires more intensive tensor contractions ($O(D^6)$), the mathematical foundation laid by u-MPS suggests a promising path forward for physics-inspired machine learning.

Summary updated

Abstract

Tensor networks are a powerful modeling framework developed for computational many-body physics, which have only recently been applied within machine learning. In this work we utilize a uniform matrix product state (u-MPS) model for probabilistic modeling of sequence data. We first show that u-MPS enable sequence-level parallelism, with length-n sequences able to be evaluated in depth O(log n). We then introduce a novel generative algorithm giving trained u-MPS the ability to efficiently sample from a wide variety of conditional distributions, each one defined by a regular expression. Special cases of this algorithm correspond to autoregressive and fill-in-the-blank sampling, but more complex regular expressions permit the generation of richly structured data in a manner that has no direct analogue in neural generative models. Experiments on sequence modeling with synthetic and real text data show u-MPS outperforming a variety of baselines and effectively generalizing their predictions in the presence of limited data.
BibTeX
@inproceedings{miller2021tensor,
  author = {Jacob Miller and Guillaume Rabusseau and John Terilla},
  title = {{Tensor Networks for Language Modeling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=uJF7IhA4GNs},
}
Figure