# Sequence graphs realizations and ambiguity in language models

arXiv: https://arxiv.org/abs/2402.08830 · HTML: https://mlsanity.com/paper/2402.08830/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 13 Feb 2024.

## Builds on (most cited first, 10 of 10)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [LSTM: A Search Space Odyssey](https://mlsanity.com/paper/1503.04069/) (2015)
- [Enhanced LSTM for Natural Language Inference](https://mlsanity.com/paper/1609.06038/) (2016)
- [word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method](https://mlsanity.com/paper/1402.3722/) (2014)
- [Formal Algorithms for Transformers](https://mlsanity.com/paper/2207.09238/) (2022)
- [word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data](https://mlsanity.com/paper/2003.12590/) (2020)
- [Invariant Language Modeling](https://mlsanity.com/paper/2110.08413/) (2021)
- [Breaking Sticks and Ambiguities with Adaptive Skip-gram](https://mlsanity.com/paper/1502.07257/) (2015)
- [Equivariant Transduction through Invariant Alignment](https://mlsanity.com/paper/2209.10926/) (2022)

## Abstract (arXiv)

Several popular language models represent local contexts in an input text x as bags of words. Such representations are naturally encoded by a sequence graph whose vertices are the distinct words occurring in x, with edges representing the (ordered) co-occurrence of two words within a sliding window of size w. However, this compressed representation is not generally bijective: some may be ambiguous, admitting several realizations as a sequence, while others may not admit any realization. In this paper, we study the realizability and ambiguity of sequence graphs from a combinatorial and algorithmic point of view. We consider the existence and enumeration of realizations of a sequence graph under multiple settings: window size w, presence/absence of graph orientation, and presence/absence of weights (multiplicities). When w=2, we provide polynomial time algorithms for realizability and enumeration in all cases except the undirected/weighted setting, where we show the #P-hardness of enumeration. For w ≥ 3, we prove the hardness of all variants, even when w is considered as a constant, with the notable exception of the undirected unweighted case for which we propose XP algorithms for both problems, tight due to a corresponding W[1]-hardness result. We conclude with an integer program formulation to solve the realizability problem, and a dynamic programming algorithm to solve the enumeration problem in instances of moderate sizes. This work leaves open the membership to NP of both problems, a non-trivial question due to the existence of minimum realizations having size exponential on the instance encoding.