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
Sequence modeling is currently dominated by two paradigms: Recurrent Neural Networks (RNNs), which are inherently sequential and difficult to parallelize, and Transformers, which parallelize well but often lack the inductive biases of recurrence. Furthermore, most generative models are strictly autoregressive, making it difficult to sample sequences that must conform to specific structural templates (e.g., "starts with A, contains B, and ends with C") without relying on inefficient rejection sampling.
This work addresses these gaps by leveraging uniform Matrix Product States (u-MPS), a type of recurrent tensor network. The u-MPS provides a model that is recurrent in nature yet mathematically structured to allow for massive parallelism and exact control over conditional distributions via formal logic.
Methodology
Parallel Evaluation
Unlike traditional RNNs (LSTMs or GRUs), the u-MPS forgoes non-linear activation functions in favor of multiplicative interactions (matrix-tensor contractions). Because matrix multiplication is associative, a sequence of length $n$ can be evaluated in $O(\log n)$ time using a tree-like parallel structure. This allows the model to maintain a recurrent hidden state without the $O(n)$ sequential bottleneck.
Probabilistic Framework and Regex Integration
To transform the tensor network into a probabilistic model, the authors utilize the "Born rule" from quantum mechanics, where the probability of a sequence is defined as $P(s) \propto |f_A(s)|^2$.
A key innovation is the development of a "dictionary" mapping regular expression (regex) operations—such as union ($|$), concatenation, and Kleene star ($*$)—to linear algebraic operations on transfer operators. This leads to the REGSAMP algorithm, which allows for direct sampling from the distribution of strings matching a given regex. Additionally, since the probability of a regex $P(R)$ is differentiable, it can be used as a regularization term during training to enforce or incentivize specific syntactic structures.
Experimental Results
Formal Language Generalization
The model was evaluated on the Tomita Grammars, a benchmark for learning formal logic. A standout finding is the u-MPS's ability to generalize logic across sequence lengths. While LSTMs and Transformers often fail when tested on sequences longer than those seen during training, the u-MPS maintains high accuracy.
As shown in the results, on the Tomita 5 grammar, the u-MPS achieved near 100% accuracy on sequences of length 30, even when trained on shorter sequences. In contrast, HMMs and LSTMs saw significant performance degradation.
Real-World Applications
In experiments using the CLAIR Fraudulent Emails dataset, the authors tested the model's ability to learn structured strings like email addresses. Incorporating "regex regularization" during training not only improved the model's perplexity but also significantly increased the syntactic correctness of generated addresses.
Discussion and Limitations
While u-MPS offers significant advantages in parallelism and structured generation, it faces challenges in computational complexity. The "bond dimension" $D$ (analogous to hidden state size) can lead to scaling costs of $O(D^3)$ or $O(D^6)$. Furthermore, while effective for small alphabets, scaling to the large vocabularies typical of modern Large Language Models remains an area for future optimization. Future work may also extend these techniques from regular languages to Context-Free Grammars (CFGs), potentially revolutionizing robust code-generation models.
Summary updated