<figure><img src="image_1.png" /></figure>

HAL
open science

# Directed Metric Structures arising in Large Language Models

Stéphane Gaubert, Yiannis Vlassopoulos

<figure><img src="image_2.png" /></figure>

## To cite this version:

Stéphane Gaubert, Yiannis Vlassopoulos. Directed Metric Structures arising in Large Language Models. 2024. hal-04582412

HAL Id: hal-04582412

https://inria.hal.science/hal-04582412

Preprint submitted on 21 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# DIRECTED METRIC STRUCTURES ARISING IN LARGE LANGUAGE MODELS

STÉPHANE GAUBERT AND YIANNIS VLASSOPOULOS

ABSTRACT. Large Language Models are transformer neural networks which are trained to produce a probability distribution on the possible next words to given texts in a corpus, in such a way that the most likely word predicted is the actual word in the training text. In this paper we find what is the mathematical structure defined by such conditional probability distributions of text extensions. Changing the view point from probabilities to -log probabilities we observe that the subtext order is completely encoded in a metric structure defined on the space of texts $\mathcal{L}$, by -log probabilities. We then construct a metric polyhedron $P(\mathcal{L})$ and an isometric embedding (called Yoneda embedding) of $\mathcal{L}$ into $P(\mathcal{L})$ such that texts map to generators of certain special extremal rays. We explain that $P(\mathcal{L})$ is a (min, +) (tropical) linear span of these extremal ray generators. The generators also satisfy a system of (min +) linear equations. We then show that $P(\mathcal{L})$ is compatible with adding more text and from this we derive an approximation of a text vector as a Boltzmann weighted linear combination of the vectors for words in that text. We then prove a duality theorem showing that texts extensions and text restrictions give isometric polyhedra (even though they look a priory very different). Moreover we prove that $P(\mathcal{L})$ is the lattice closure of (a version of) the so called, Isbell completion of $\mathcal{L}$ which turns out to be the (max, +) span of the text extremal ray generators. All constructions have interpretations in category theory but we don't use category theory explicitly. The categorical interpretations are briefly explained in an appendix. In the final appendix we describe how the syntax to semantics problem could fit in a general well known mathematical duality.

## CONTENTS

<table><tr><td>1. Overview</td><td>2</td></tr><tr><td>1.1. Acknowledgements</td><td>7</td></tr><tr><td>2. From probabilities of text extensions to distances</td><td>7</td></tr><tr><td>3. From the text metric space $\mathcal{L}$ to the polyhedra $P(\mathcal{L})$ and $Q(\mathcal{L})$</td><td>10</td></tr><tr><td>3.1. Texts define special Extremal rays of $P(\mathcal{L})$ and $Q(\mathcal{L})$</td><td>14</td></tr><tr><td>3.2. All Extremal rays correspond to connected lower sets of $\mathcal{L}$</td><td>16</td></tr><tr><td>4. The polyhedron $P(\mathcal{L})$ as a (min, +) linear space</td><td>19</td></tr><tr><td>4.1. $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ as Semantic spaces</td><td>21</td></tr><tr><td>4.2. From one word text extensions to longer extensions</td><td>22</td></tr><tr><td>5. Compatibility of $P(\mathcal{L})$ with adding more texts</td><td>23</td></tr><tr><td>5.1. Approximation of a text vector in terms of word vectors</td><td>25</td></tr><tr><td>6. Duality between text extensions and restrictions</td><td>28</td></tr><tr><td>7. Extremal Rays in terms of text vectors</td><td>34</td></tr><tr><td>8. $P^-(\mathcal{L})$ as the lattice completion of the Isbell completion</td><td>36</td></tr></table>

Date: May 20, 2024.
# DIRECTED METRIC STRUCTURES ARISING IN LARGE LANGUAGE MODELS

STÉPHANE GAUBERT AND YIANNIS VLASSOPOULOS

ABSTRACT. Large Language Models are transformer neural networks which are trained to produce a probability distribution on the possible next words to given texts in a corpus, in such a way that the most likely word predicted is the actual word in the training text. In this paper we find what is the mathematical structure defined by such conditional probability distributions of text extensions. Changing the view point from probabilities to -log probabilities we observe that the subtext order is completely encoded in a metric structure defined on the space of texts $\mathcal{L}$, by -log probabilities. We then construct a metric polyhedron $P(\mathcal{L})$ and an isometric embedding (called Yoneda embedding) of $\mathcal{L}$ into $P(\mathcal{L})$ such that texts map to generators of certain special extremal rays. We explain that $P(\mathcal{L})$ is a (min, +) (tropical) linear span of these extremal ray generators. The generators also satisfy a system of (min +) linear equations. We then show that $P(\mathcal{L})$ is compatible with adding more text and from this we derive an approximation of a text vector as a Boltzmann weighted linear combination of the vectors for words in that text. We then prove a duality theorem showing that texts extensions and text restrictions give isometric polyhedra (even though they look a priory very different). Moreover we prove that $P(\mathcal{L})$ is the lattice closure of (a version of) the so called, Isbell completion of $\mathcal{L}$ which turns out to be the (max, +) span of the text extremal ray generators. All constructions have interpretations in category theory but we don't use category theory explicitly. The categorical interpretations are briefly explained in an appendix. In the final appendix we describe how the syntax to semantics problem could fit in a general well known mathematical duality.

## CONTENTS

<table><tr><td>1. Overview</td><td>2</td></tr><tr><td>1.1. Acknowledgements</td><td>7</td></tr><tr><td>2. From probabilities of text extensions to distances</td><td>7</td></tr><tr><td>3. From the text metric space $\mathcal{L}$ to the polyhedra $P(\mathcal{L})$ and $Q(\mathcal{L})$</td><td>10</td></tr><tr><td>3.1. Texts define special Extremal rays of $P(\mathcal{L})$ and $Q(\mathcal{L})$</td><td>14</td></tr><tr><td>3.2. All Extremal rays correspond to connected lower sets of $\mathcal{L}$</td><td>16</td></tr><tr><td>4. The polyhedron $P(\mathcal{L})$ as a (min, +) linear space</td><td>19</td></tr><tr><td>4.1. $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ as Semantic spaces</td><td>21</td></tr><tr><td>4.2. From one word text extensions to longer extensions</td><td>22</td></tr><tr><td>5. Compatibility of $P(\mathcal{L})$ with adding more texts</td><td>23</td></tr><tr><td>5.1. Approximation of a text vector in terms of word vectors</td><td>25</td></tr><tr><td>6. Duality between text extensions and restrictions</td><td>28</td></tr><tr><td>7. Extremal Rays in terms of text vectors</td><td>34</td></tr><tr><td>8. $P^-(\mathcal{L})$ as the lattice completion of the Isbell completion</td><td>36</td></tr></table>

Date: May 20, 2024.
<table><tr><td>9. Some comments about Probabilistic Language Models</td><td>39</td></tr><tr><td>Appendix A. Categorical interpretation</td><td>39</td></tr><tr><td>Appendix B. Syntax to Semantics and Morita equivalence</td><td>40</td></tr><tr><td>References</td><td>41</td></tr></table>

# 1. OVERVIEW

Large Language Models (LLM) are transformer neural networks that are trained to compute the probability of the possible next words to a text in such a way that the most probable next word predicted by the network, is the actual next word in the training text [20, 15, 16, 2].

They are often characterized as “just statistical models”. In this paper, continuing the approach introduced in [1], this time without explicitly using categories<fnref n="1" />, we would like to make a proposal for what is the underlying mathematical structure these probability distributions actually encode and show the evidence and possible consequences. We find that a rich structure is revealed if we change the point of view from probabilities to negative log probabilities. While it is entirely equivalent, this point of view can be reinterpreted as an asymmetric metric on texts.

Indeed consider a set $\mathcal{L} := \{a_1, \dots, a_n\}$ whose elements are texts in the language. Equip $\mathcal{L}$ with a poset structure, where $a_i \le a_j$ if and only if $a_i$ is a subtext of $a_j$. Denote by $\text{Pr}(a_j|a_i)$ the probability of extending a text $a_i$ to a text $a_j$. The probability is 0 exactly when $a_i$ is not a subtext of $a_j$. Our main assumption is that conditional probabilities of extensions of texts multiply i.e.

$$ (1) \quad \text{if } a_i \le a_j \le a_k \text{ then } \text{Pr}(a_j|a_i) \text{Pr}(a_k|a_j) = \text{Pr}(a_k|a_i). $$

We call the triple $(\mathcal{L}, \le, \text{Pr})$ a probabilistic language model.

Next, recall the notion of a directed metric $\delta$ on a set $X$. It is defined to be a function $\delta: X \times X \to (-\infty, \infty]$ which satisfies the triangle inequality and $\delta(a, a) = 0$. Nevertheless, unless stated otherwise it does not have to be symmetric, $\delta(a, b) = 0$ does not necessarily imply $a = b$ and $\delta$ can take the value $\infty$ and can also take negative values.<fnref n="2" />

Now we notice that the probabilistic language model $(\mathcal{L}, \le, \text{Pr})$ defines a directed metric $d$ on the poset $\mathcal{L}$ by

$$ (2) \quad d(a_i, a_j) = \begin{cases} -\log \text{Pr}(a_j|a_i) & \text{if } a_i \le a_j, \\ \infty & \text{if } a_i \text{ and } a_j \text{ are not comparable.} \end{cases} $$

$(\mathcal{L}, d)$ is then a directed metric space.

Indeed

$$ (3) \quad \text{if } a_i \le a_j \le a_k \text{ then } d(a_i, a_k) = d(a_i, a_j) + d(a_j, a_k) $$

<footnote n="1">¹We note though that all constructions and theorems have a categorical interpretation. For those already familiar with categories Appendix A provides a brief categorical explanation of constructions and results in this paper.</footnote>

<footnote n="2">²We will see however that restricting to positive values is natural when the directed metric comes from probability distributions.</footnote>
<table><tr><td>9. Some comments about Probabilistic Language Models</td><td>39</td></tr><tr><td>Appendix A. Categorical interpretation</td><td>39</td></tr><tr><td>Appendix B. Syntax to Semantics and Morita equivalence</td><td>40</td></tr><tr><td>References</td><td>41</td></tr></table>

# 1. OVERVIEW

Large Language Models (LLM) are transformer neural networks that are trained to compute the probability of the possible next words to a text in such a way that the most probable next word predicted by the network, is the actual next word in the training text [20, 15, 16, 2].

They are often characterized as “just statistical models”. In this paper, continuing the approach introduced in [1], this time without explicitly using categories<fnref n="1" />, we would like to make a proposal for what is the underlying mathematical structure these probability distributions actually encode and show the evidence and possible consequences. We find that a rich structure is revealed if we change the point of view from probabilities to negative log probabilities. While it is entirely equivalent, this point of view can be reinterpreted as an asymmetric metric on texts.

Indeed consider a set $\mathcal{L} := \{a_1, \dots, a_n\}$ whose elements are texts in the language. Equip $\mathcal{L}$ with a poset structure, where $a_i \le a_j$ if and only if $a_i$ is a subtext of $a_j$. Denote by $\text{Pr}(a_j|a_i)$ the probability of extending a text $a_i$ to a text $a_j$. The probability is 0 exactly when $a_i$ is not a subtext of $a_j$. Our main assumption is that conditional probabilities of extensions of texts multiply i.e.

$$ (1) \quad \text{if } a_i \le a_j \le a_k \text{ then } \text{Pr}(a_j|a_i) \text{Pr}(a_k|a_j) = \text{Pr}(a_k|a_i). $$

We call the triple $(\mathcal{L}, \le, \text{Pr})$ a probabilistic language model.

Next, recall the notion of a directed metric $\delta$ on a set $X$. It is defined to be a function $\delta: X \times X \to (-\infty, \infty]$ which satisfies the triangle inequality and $\delta(a, a) = 0$. Nevertheless, unless stated otherwise it does not have to be symmetric, $\delta(a, b) = 0$ does not necessarily imply $a = b$ and $\delta$ can take the value $\infty$ and can also take negative values.<fnref n="2" />

Now we notice that the probabilistic language model $(\mathcal{L}, \le, \text{Pr})$ defines a directed metric $d$ on the poset $\mathcal{L}$ by

$$ (2) \quad d(a_i, a_j) = \begin{cases} -\log \text{Pr}(a_j|a_i) & \text{if } a_i \le a_j, \\ \infty & \text{if } a_i \text{ and } a_j \text{ are not comparable.} \end{cases} $$

$(\mathcal{L}, d)$ is then a directed metric space.

Indeed

$$ (3) \quad \text{if } a_i \le a_j \le a_k \text{ then } d(a_i, a_k) = d(a_i, a_j) + d(a_j, a_k) $$

<footnote n="1">¹We note though that all constructions and theorems have a categorical interpretation. For those already familiar with categories Appendix A provides a brief categorical explanation of constructions and results in this paper.</footnote>

<footnote n="2">²We will see however that restricting to positive values is natural when the directed metric comes from probability distributions.</footnote>
and otherwise the triangle inequality is satisfied with at least one side being $\infty$ (Proposition 1). We see also that the metric $d$ fully determines the poset structure on $\mathcal{L}$ (Corollary 1).

Although $d$ satisfies a rather degenerate form of the triangle inequality, it is enough to define a non trivial directed metric polyhedron $P(\mathcal{L})$ in $(\mathbb{R} \cup \{\infty\})^n$, inside which $\mathcal{L}$ is isometrically embedded as a remarkable set of extremal rays.

Indeed, in Section 3 we define

$$ (4) \qquad P(\mathcal{L}) := \{x \in (\mathbb{R} \cup \{\infty\})^n \setminus (\infty, \dots, \infty) | x_i \le x_j + d(a_i, a_j)\} $$

and thus the finite part of $P(\mathcal{L})$ is a polyhedron in $\mathbb{R}^n$. Define the Funk directed metric $D$ on $(\mathbb{R} \cup \{\infty\})^n \setminus (\infty, \dots, \infty)$ by

$$ (5) \qquad D(x, x') := \max_i \{x'_i - x_i | x_i \neq \infty\}. $$

Then $(P(\mathcal{L}), D)$ becomes a directed metric space. The Funk directed metric originates from Hilbert geometry [14].

To understand the relevance of $P(\mathcal{L})$ note first (Proposition 4) that

$$ (6) \qquad Y : (\mathcal{L}, d) \hookrightarrow (P(\mathcal{L}), D), \text{ given by } Y(a_k) := d(-, a_k), $$

is an isometric embedding (called the Yoneda embedding). Moreover, each $Y(a_k)$ is a generator of an extremal ray of $P(\mathcal{L})$ (Theorem 1).

To be precise about the term extremal ray here, consider the image $Q(\mathcal{L})$ of $P(\mathcal{L})$, under the coordinate wise map $x_i \to z_i := e^{-x_i}$, i.e.

$$ (7) \qquad Q(\mathcal{L}) := \{z := (z_1, \dots, z_n) \in [0, \infty)^n | z_i := e^{-x_i} \text{ for } x = (x_1, \dots, x_n) \in P(\mathcal{L})\} $$

We see that

$$ (8) \qquad Q(\mathcal{L}) := \{z = (z_1, \dots, z_n) \in [0, \infty)^n \setminus (0, \dots, 0) | z_i \ge \mathrm{Pr}(a_j|a_i)z_j\} $$

Denote by $e^{-Y(a_k)}$, the image of $Y(a_k)$ in $Q(\mathcal{L})$. Then (Theorem 1) $e^{-Y(a_k)}$ is a generator of a usual extremal ray in the polyhedral cone $Q(\mathcal{L})$. When we speak of extremal rays of $P(\mathcal{L})$ we always mean the subsets of $P(\mathcal{L})$ that map to extremal rays in the polyhedral cone $Q(\mathcal{L})$ by the map $(x_i) \mapsto (e^{-x_i})$.

The polyhedral cone $Q(\mathcal{L})$ is a generalization of the order polytope studied by Stanley [18]. The order polytope corresponds to the case where $\mathrm{Pr}(a_j|a_i)$ takes only the values 0 or 1 and $\mathcal{L}$ is simply a poset. Moreover, Stanley does not consider a cone, but rather the intersection of this cone with the unit box. Lam and Postnikov [10] defined an alcoved polytope to be a bounded cell of a Coxeter arrangement (of type $A_n$). The definition of $P(\mathcal{L})$ is similar, but we do not require the cell to be bounded. Alcoved polytopes have been studied in tropical geometry, in relation with metric spaces, see e.g. [9, 19].

Moving on, we prove in Proposition 5 that

$$ (9) \qquad \text{if } x = (x_1, \dots, x_n) \in P(\mathcal{L}) \text{ then } x_k = D(Y(a_k), x). $$

We now see that the defining equations for $P(\mathcal{L})$ are exactly the triangle inequalities for $D$. Indeed

$$ (10) \qquad x_i \le x_j + d(a_i, a_j) \iff D(Y(a_i), x) \le D(Y(a_j), x) + D(Y(a_i), Y(a_j)). $$

Note also (Proposition 3) that we can think of the points $x \in P(\mathcal{L})$ as functions on $\mathcal{L}$ (just as we can think of usual vectors as functions on a set). Indeed, if we
and otherwise the triangle inequality is satisfied with at least one side being $\infty$ (Proposition 1). We see also that the metric $d$ fully determines the poset structure on $\mathcal{L}$ (Corollary 1).

Although $d$ satisfies a rather degenerate form of the triangle inequality, it is enough to define a non trivial directed metric polyhedron $P(\mathcal{L})$ in $(\mathbb{R} \cup \{\infty\})^n$, inside which $\mathcal{L}$ is isometrically embedded as a remarkable set of extremal rays.

Indeed, in Section 3 we define

$$ (4) \qquad P(\mathcal{L}) := \{x \in (\mathbb{R} \cup \{\infty\})^n \setminus (\infty, \dots, \infty) | x_i \le x_j + d(a_i, a_j)\} $$

and thus the finite part of $P(\mathcal{L})$ is a polyhedron in $\mathbb{R}^n$. Define the Funk directed metric $D$ on $(\mathbb{R} \cup \{\infty\})^n \setminus (\infty, \dots, \infty)$ by

$$ (5) \qquad D(x, x') := \max_i \{x'_i - x_i | x_i \ne \infty\}. $$

Then $(P(\mathcal{L}), D)$ becomes a directed metric space. The Funk directed metric originates from Hilbert geometry [14].

To understand the relevance of $P(\mathcal{L})$ note first (Proposition 4) that

$$ (6) \qquad Y : (\mathcal{L}, d) \hookrightarrow (P(\mathcal{L}), D), \text{ given by } Y(a_k) := d(-, a_k), $$

is an isometric embedding (called the Yoneda embedding). Moreover, each $Y(a_k)$ is a generator of an extremal ray of $P(\mathcal{L})$ (Theorem 1).

To be precise about the term extremal ray here, consider the image $Q(\mathcal{L})$ of $P(\mathcal{L})$, under the coordinate wise map $x_i \to z_i := e^{-x_i}$, i.e.

$$ (7) \qquad Q(\mathcal{L}) := \{z := (z_1, \dots, z_n) \in [0, \infty)^n | z_i := e^{-x_i} \text{ for } x = (x_1, \dots, x_n) \in P(\mathcal{L})\} $$

We see that

$$ (8) \qquad Q(\mathcal{L}) := \{z = (z_1, \dots, z_n) \in [0, \infty)^n \setminus (0, \dots, 0) | z_i \ge \mathrm{Pr}(a_j | a_i) z_j\} $$

Denote by $e^{-Y(a_k)}$, the image of $Y(a_k)$ in $Q(\mathcal{L})$. Then (Theorem 1) $e^{-Y(a_k)}$ is a generator of a usual extremal ray in the polyhedral cone $Q(\mathcal{L})$. When we speak of extremal rays of $P(\mathcal{L})$ we always mean the subsets of $P(\mathcal{L})$ that map to extremal rays in the polyhedral cone $Q(\mathcal{L})$ by the map $(x_i) \mapsto (e^{-x_i})$.

The polyhedral cone $Q(\mathcal{L})$ is a generalization of the order polytope studied by Stanley [18]. The order polytope corresponds to the case where $\mathrm{Pr}(a_j|a_i)$ takes only the values 0 or 1 and $\mathcal{L}$ is simply a poset. Moreover, Stanley does not consider a cone, but rather the intersection of this cone with the unit box. Lam and Postnikov [10] defined an alcoved polytope to be a bounded cell of a Coxeter arrangement (of type $A_n$). The definition of $P(\mathcal{L})$ is similar, but we do not require the cell to be bounded. Alcoved polytopes have been studied in tropical geometry, in relation with metric spaces, see e.g. [9, 19].

Moving on, we prove in Proposition 5 that

$$ (9) \qquad \text{if } x = (x_1, \dots, x_n) \in P(\mathcal{L}) \text{ then } x_k = D(Y(a_k), x). $$

We now see that the defining equations for $P(\mathcal{L})$ are exactly the triangle inequalities for $D$. Indeed

$$ (10) \qquad x_i \le x_j + d(a_i, a_j) \iff D(Y(a_i), x) \le D(Y(a_j), x) + D(Y(a_i), Y(a_j)). $$

Note also (Proposition 3) that we can think of the points $x \in P(\mathcal{L})$ as functions on $\mathcal{L}$ (just as we can think of usual vectors as functions on a set). Indeed, if we
denote by $d_{\mathbb{R}}$ the Funk metric on $\mathbb{R} \cup \{\infty\}$, namely $d_{\mathbb{R}}(s, t) = t - s$ and $d_{\mathbb{R}}(\infty, \infty) = \max \emptyset = -\infty$ then

$$P(\mathcal{L}) = \{x : (\mathcal{L}, d^t) \to ((-\infty, \infty], d_F)|x \text{ is non-expansive.}\}$$

We then have that $x(a_i) = x_i = D(Y(a_i), x)$ (Proposition 5).

Therefore $P(\mathcal{L})$ can also be thought of as the set of maps $x : \mathcal{L} \to (-\infty, \infty]$ which satisfy the triangle inequalities for the metric $D$ with respect to all the maps $Y(a_k) := d(-, a_k) : \mathcal{L} \to (-\infty, \infty]$ for $k = 1, \dots, n$. It is therefore a kind of convex metric span of the $Y(a_k) := d(-, a_k)$.

From the point of view of language semantics now, we consider $Y(a_k) = d(-, a_k)$ to represent the meaning of a text $a_k$ in terms of all the texts it contains, (Section 4.1) in accordance with the statistical semantics principal and as was advocated in [1].

Dually, we can consider the meaning of a text $a_k$ to be given by all the texts extending $a_k$, namely $d(a_k, -)$. This is then encoded in

$$(11) \qquad \hat{P}(\mathcal{L}) = \{y \in (\mathbb{R} \cup \{\infty\})^n | y_i \le y_j + d(a_j, a_i)\}.$$

Indeed we have the isometric co-Yoneda embedding

$$(12) \qquad \hat{Y} : \mathcal{L} \hookrightarrow P(\mathcal{L}) \text{ given by } \hat{Y}(a_k) := d(a_k, -)$$

and moreover $y_i = D(\hat{Y}(a_i), y)$.

**Remark 1.** We said that $Y(a_k) := d(-, a_k)$ or $\hat{Y}(a_k) := d(a_k, -)$ represent the meaning of a text $a_k$ but it's also the “location” of these vectors in the whole space $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ respectively. In particular if $w := a_k$ is a word then $Y(w) := d(-, w)$ is supported only on $w$ so it does not seem to contain much information. However the relevant semantic information is in $D(Y(w), -)$. Moreover we will see shortly that the fact that the vector $d(-, w)$ is in $P(\mathcal{L})$ means that it satisfies a whole system of equations (Eq 19, 20, Proposition 11) with respect to other texts. We will explain this system of equations, later in this overview when we describe section 4.

We already saw that $Y(a_k)$ is an extremal ray in $P(\mathcal{L})$ but it turns out that $P(\mathcal{L})$ has generally exponentially many additional extremal rays – that are not in the image of $Y$. We explicitly characterize the extremal rays of $P(\mathcal{L})$ as corresponding to connected lower sets of $(\mathcal{L}, \leq)$ in Proposition 6 and Theorem 2. In fact, if $x$ is such an extremal ray and $l(x)$ denotes the corresponding lower set then we show that after a diagonal change of variables the new coordinates of the extremal ray give the characteristic function of the lower set $l(x)$.

What distinguishes the lower sets corresponding to elements $Y(a_i)$ is that they are principal.

Therefore $P(\mathcal{L})$ can be considered as a space parameterizing semantics in the language. However, only the extremal rays corresponding to principal lower sets of $\mathcal{L}$, correspond to texts.

Notice now that the Funk metric $D$ on $P(\mathcal{L})$ defines a metric $D_Q$ on the polyhedral cone $Q(\mathcal{L})$ where, if $z, z' \in Q(\mathcal{L})$, then

$$(13) \qquad D_Q(z, z') := \max_i \{\log(\frac{z_i}{z'_i}) | z'_i \neq 0\}.$$

<footnote n="3">³We explain later in Remark 2 that it is possible and useful in some cases to extend the values of a directed metric to $[-\infty, \infty]$ and this is one of the cases we do so.</footnote>
denote by $d_{\mathbb{R}}$ the Funk metric on $\mathbb{R} \cup \{\infty\}$, namely $d_{\mathbb{R}}(s, t) = t - s$ and $d_{\mathbb{R}}(\infty, \infty) = \max \emptyset = -\infty$ then

$$P(\mathcal{L}) = \{x : (\mathcal{L}, d^t) \to ((-\infty, \infty], d_F)|x \text{ is non-expansive.}\}$$

We then have that $x(a_i) = x_i = D(Y(a_i), x)$ (Proposition 5).

Therefore $P(\mathcal{L})$ can also be thought of as the set of maps $x : \mathcal{L} \to (-\infty, \infty]$ which satisfy the triangle inequalities for the metric $D$ with respect to all the maps $Y(a_k) := d(-, a_k) : \mathcal{L} \to (-\infty, \infty]$ for $k = 1, \dots, n$. It is therefore a kind of convex metric span of the $Y(a_k) := d(-, a_k)$.

From the point of view of language semantics now, we consider $Y(a_k) = d(-, a_k)$ to represent the meaning of a text $a_k$ in terms of all the texts it contains, (Section 4.1) in accordance with the statistical semantics principal and as was advocated in [1].

Dually, we can consider the meaning of a text $a_k$ to be given by all the texts extending $a_k$, namely $d(a_k, -)$. This is then encoded in

$$(11) \qquad \hat{P}(\mathcal{L}) = \{y \in (\mathbb{R} \cup \{\infty\})^n | y_i \le y_j + d(a_j, a_i)\}.$$

Indeed we have the isometric co-Yoneda embedding

$$(12) \qquad \hat{Y} : \mathcal{L} \hookrightarrow P(\mathcal{L}) \text{ given by } \hat{Y}(a_k) := d(a_k, -)$$

and moreover $y_i = D(\hat{Y}(a_i), y)$.

**Remark 1.** We said that $Y(a_k) := d(-, a_k)$ or $\hat{Y}(a_k) := d(a_k, -)$ represent the meaning of a text $a_k$ but it's also the “location” of these vectors in the whole space $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ respectively. In particular if $w := a_k$ is a word then $Y(w) := d(-, w)$ is supported only on $w$ so it does not seem to contain much information. However the relevant semantic information is in $D(Y(w), -)$. Moreover we will see shortly that the fact that the vector $d(-, w)$ is in $P(\mathcal{L})$ means that it satisfies a whole system of equations (Eq 19, 20, Proposition 11) with respect to other texts. We will explain this system of equations, later in this overview when we describe section 4.

We already saw that $Y(a_k)$ is an extremal ray in $P(\mathcal{L})$ but it turns out that $P(\mathcal{L})$ has generally exponentially many additional extremal rays – that are not in the image of $Y$. We explicitly characterize the extremal rays of $P(\mathcal{L})$ as corresponding to connected lower sets of $(\mathcal{L}, \leq)$ in Proposition 6 and Theorem 2. In fact, if $x$ is such an extremal ray and $l(x)$ denotes the corresponding lower set then we show that after a diagonal change of variables the new coordinates of the extremal ray give the characteristic function of the lower set $l(x)$.

What distinguishes the lower sets corresponding to elements $Y(a_i)$ is that they are principal.

Therefore $P(\mathcal{L})$ can be considered as a space parameterizing semantics in the language. However, only the extremal rays corresponding to principal lower sets of $\mathcal{L}$, correspond to texts.

Notice now that the Funk metric $D$ on $P(\mathcal{L})$ defines a metric $D_Q$ on the polyhedral cone $Q(\mathcal{L})$ where, if $z, z' \in Q(\mathcal{L})$, then

$$(13) \qquad D_Q(z, z') := \max_i \{\log(\frac{z_i}{z'_i}) | z'_i \neq 0\}.$$

<footnote n="3">³We explain later in Remark 2 that it is possible and useful in some cases to extend the values of a directed metric to $[-\infty, \infty]$ and this is one of the cases we do so.</footnote>
By definition we have $D_Q(z, z') = D(-\log z, -\log z')$ and $D(x, x') = D_Q(e^{-x}, e^{-x'})$.
Then the fact that $Y$ is an isometric embedding into $P(\mathcal{L})$ implies that

$$ (14) \qquad e^{-Y} : (\mathcal{L}, d) \to (Q(\mathcal{L}), D_Q) $$

is an isometric embedding.

In section 4 we explain the construction of $P(\mathcal{L})$ in terms of tropical or (min, +) algebra. Recall that the (min, +) semifield $\mathbb{R}_{\min}$, is defined as $((-\infty, \infty], \min, +)$. We show in Section 4 that $P(\mathcal{L})$ is generated by the vectors $Y(a_k) = d(-, a_k)$ as a (min, +) module. To see that, note first that $d$ is a directed metric if and only if it is a (min, +) projector. This is because if we let $d_{i,j} := d(a_i, a_j)$ and define

$$ (15) \qquad d_{\min}(x)_i := \min_j \{d_{i,j} + x_j\}, $$

then the triangle inequality and the fact that $d_{i,i} = 0$, are equivalent to $d_{i,k} = \min\{d_{i,j} + d_{j,k}\}$ which is equivalent to $d_{\min}^2 = d_{\min}$.

We then note that $P(\mathcal{L}) = \{x | d_{\min}x = x\}$. Indeed: $x = d_{\min}x \iff x_i = \min_j\{d_{i,j} + x_j\} \iff x \in P(\mathcal{L})$.

Introduce the notation $\mathrm{Fix}(d_{\min}) := \{x | d_{\min}x = x\}$. Since $d_{\min}$ is a projection $\mathrm{Im}(d_{\min}) = \mathrm{Fix}(d_{\min})$. Therefore

$$ (16) \qquad P(\mathcal{L}) = \mathrm{Fix}(d_{\min}) = \mathrm{Im}(d_{\min}). $$

We see that $P(\mathcal{L})$ is the (min, +) (tropical) span of the columns of the matrix $d$. Analogously, if we denote by $d^t$ the transpose of $d$, we see that $\hat{P}(\mathcal{L}) = \mathrm{Im}(d_{\min}^t) = \mathrm{Fix}(d_{\min}^t)$ and therefore $\hat{P}(\mathcal{L})$ is the (min, +) row span of $d$. We let $(u \oplus v)_i := \min\{u_i, v_i\}$ and $(\lambda \odot v)_i := \lambda + v_i$. Then for $x \in P(\mathcal{L})$ we have

$$ (17) \qquad x = \oplus_j x_j \odot d(-, a_j) = \oplus_j D(Y(a_j), x) \odot d(-, a_j) = \oplus_j D(Y(a_j), x) \odot Y(a_j). $$

and an analogous formula holds for $z \in \hat{P}(\mathcal{L}) = \mathrm{Im}(d_{\min}^t)$. From these we get that (Proposition 10)

$$ (18) \qquad Y(a_k) = d(-, a_k) = \oplus_{a_j \le a_k} d_{j,k} \odot Y(a_j) $$

and

$$ (19) \qquad \hat{Y}(a_k) = d(a_k, -) = \oplus_{a_k \le a_l} d_{k,l} \odot \hat{Y}(a_l). $$

These are the systems of equations we referred to in Remark 1.

In section 5 we study how $P(\mathcal{L})$ changes when we enlarge the language corpus $\mathcal{L}$. We prove that if a probabilistic language model $(\mathcal{L}_1, d_1)$ is extended to $(\mathcal{L}_2, d_2)$, namely if there is an isometric embedding $\phi : (\mathcal{L}_1, d_1) \hookrightarrow (\mathcal{L}_2, d_2)$ then there is an isometric embedding $\tilde{\phi} : (P(\mathcal{L}_1)), D_1) \hookrightarrow (P(\mathcal{L}_2), D_2)$ such that $\tilde{\phi}(Y_1(a)) = Y_2(\phi(a))$. Moreover there is a non-expansive, (min, +) projection $\mathcal{R} : P(\mathcal{L}_2) \to P(\mathcal{L}_2)$ such that $\mathrm{Im}(\mathcal{R}) = \tilde{\phi}(P(\mathcal{L}_1))$.

Using this we show that if $\mathcal{L}_1 := \{w_1, \dots, w_l\}$ is the set of words in the language and $b$ is a text in $\mathcal{L}$ then $\mathcal{R}(Y(b)) = \bigoplus_{w_i \le b} d_2(w_i, b) \odot Y_2(w_i)$ Introducing a temperature parameter $T$ we get

$$ (20) \qquad \mathcal{R}(Y(b)) = \lim_{T \to 0} -T \log \left( \sum_{w_i \le b} e^{-\frac{d(w_i, b)}{T}} e^{-\frac{Y(w_i)}{T}} \right) $$

$$ \text{Therefore for small } T \text{ we have } e^{-\frac{\mathcal{R}(Y(b))}{T}} \approx \sum_{w_i \le b} e^{-\frac{d(w_i, b)}{T}} e^{-\frac{Y(w_i)}{T}}. $$

Putting $v_i := e^{-Y(w_i)}$ we have
By definition we have $D_Q(z, z') = D(-\log z, -\log z')$ and $D(x, x') = D_Q(e^{-x}, e^{-x'})$.
Then the fact that $Y$ is an isometric embedding into $P(\mathcal{L})$ implies that

$$ (14) \qquad e^{-Y} : (\mathcal{L}, d) \to (Q(\mathcal{L}), D_Q) $$

is an isometric embedding.

In section 4 we explain the construction of $P(\mathcal{L})$ in terms of tropical or (min, +) algebra. Recall that the (min, +) semifield $\mathbb{R}_{\min}$, is defined as (($-\infty, \infty$], min, +). We show in Section 4 that $P(\mathcal{L})$ is generated by the vectors $Y(a_k) = d(-, a_k)$ as a (min, +) module. To see that, note first that $d$ is a directed metric if and only if it is a (min, +) projector. This is because if we let $d_{i,j} := d(a_i, a_j)$ and define

$$ (15) \qquad d_{\min}(x)_i := \min_j \{d_{i,j} + x_j\}, $$

then the triangle inequality and the fact that $d_{i,i} = 0$, are equivalent to $d_{i,k} = \min\{d_{i,j} + d_{j,k}\}$ which is equivalent to $d_{\min}^2 = d_{\min}$.

We then note that $P(\mathcal{L}) = \{x | d_{\min}x = x\}$. Indeed: $x = d_{\min}x \iff x_i = \min_j\{d_{i,j} + x_j\} \iff x \in P(\mathcal{L})$.

Introduce the notation $\text{Fix}(d_{\min}) := \{x | d_{\min}x = x\}$. Since $d_{\min}$ is a projection $\text{Im}(d_{\min}) = \text{Fix}(d_{\min})$. Therefore

$$ (16) \qquad P(\mathcal{L}) = \text{Fix}(d_{\min}) = \text{Im}(d_{\min}). $$

We see that $P(\mathcal{L})$ is the (min, +) (tropical) span of the columns of the matrix $d$. Analogously, if we denote by $d^t$ the transpose of $d$, we see that $\hat{P}(\mathcal{L}) = \text{Im}(d_{\min}^t) = \text{Fix}(d_{\min}^t)$ and therefore $\hat{P}(\mathcal{L})$ is the (min, +) row span of $d$. We let $(u \oplus v)_i := \min\{u_i, v_i\}$ and $(\lambda \odot v)_i := \lambda + v_i$. Then for $x \in P(\mathcal{L})$ we have

$$ (17) \quad x = \oplus_j x_j \odot d(-, a_j) = \oplus_j D(Y(a_j), x) \odot d(-, a_j) = \oplus_j D(Y(a_j), x) \odot Y(a_j). $$

and an analogous formula holds for $z \in \hat{P}(\mathcal{L}) = \text{Im}(d_{\min}^t)$. From these we get that (Proposition 10)

$$ (18) \qquad Y(a_k) = d(-, a_k) = \oplus_{a_j \le a_k} d_{j,k} \odot Y(a_j) $$

and

$$ (19) \qquad \hat{Y}(a_k) = d(a_k, -) = \oplus_{a_k \le a_l} d_{k,l} \odot \hat{Y}(a_l). $$

These are the systems of equations we referred to in Remark 1.

In section 5 we study how $P(\mathcal{L})$ changes when we enlarge the language corpus $\mathcal{L}$. We prove that if a probabilistic language model $(\mathcal{L}_1, d_1)$ is extended to $(\mathcal{L}_2, d_2)$, namely if there is an isometric embedding $\phi : (\mathcal{L}_1, d_1) \hookrightarrow (\mathcal{L}_2, d_2)$ then there is an isometric embedding $\tilde{\phi} : (P(\mathcal{L}_1)), D_1) \hookrightarrow (P(\mathcal{L}_2), D_2)$ such that $\tilde{\phi}(Y_1(a)) = Y_2(\phi(a))$. Moreover there is a non-expansive, (min, +) projection $\mathcal{R} : P(\mathcal{L}_2) \to P(\mathcal{L}_2)$ such that $\text{Im}(\mathcal{R}) = \tilde{\phi}(P(\mathcal{L}_1))$.

Using this we show that if $\mathcal{L}_1 := \{w_1, \dots, w_l\}$ is the set of words in the language and $b$ is a text in $\mathcal{L}$ then $\mathcal{R}(Y(b)) = \bigoplus_{w_i \le b} d_2(w_i, b) \odot Y_2(w_i)$ Introducing a temperature parameter $T$ we get

$$ (20) \qquad \mathcal{R}(Y(b)) = \lim_{T \to 0} -T \log\left(\sum_{w_i \le b} e^{-\frac{d(w_i, b)}{T}} e^{-\frac{Y(w_i)}{T}}\right) $$

$$ \text{Therefore for small } T \text{ we have } e^{-\frac{\mathcal{R}(Y(b))}{T}} \approx \sum_{w_i \le b} e^{-\frac{d(w_i, b)}{T}} e^{-\frac{Y(w_i)}{T}}. $$

Putting $v_i := e^{-Y(w_i)}$ we have
$$ (21) \qquad e^{-\frac{\mathcal{R}(Y(b))}{T}} \approx \sum_{i} e^{-d(Y(w_i),b)/T} v_i $$

This approximation of text vectors is similar to the one calculated by transformer neural networks in the self attention module.

In section 6 we describe a duality between semantics via texts extensions and text restriction. Indeed we have already seen that $P(\mathcal{L}) = \{x|d_{\min}x = x\}$ is the (min,+) column span of $d$ and $\hat{P}(\mathcal{L}) = \{x|d_{\min}^t x = x\}$ is the (min,+) row span of $d$. It is easy to see that $d_{\min}x = x \iff d_{\min}^t(-x) = -x$ (Proposition 19). Indeed it follows from the fact that $x_i \le d_{i,j} + x_j \iff -x_j \le d_{i,j} - x_i$. However this requires extending the (min,+) semifield, as well as the values of the directed metric, to $[-\infty, \infty]$. This results in the definition of extended (min,+) modules $P^-(\mathcal{L})$ and $\hat{P}^-(\mathcal{L})$.

We show that $(P^-(\mathcal{L}), D)$ and $(\hat{P}^-(\mathcal{L}), D^t)$ are isometric (and in fact tropically anti-isomorphic). We interpret this as saying that the semantic space $\hat{P}^-(\mathcal{L})$, defined by extensions of texts is isomorphic to the semantic space $P^-(\mathcal{L})$ defined by restrictions of texts. We note that this is quite a non-trivial isomorphism as $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ don't even have the same number of extremal rays in general. We give an example (Example 1) illustrating the polyhedra $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$. In fact we consider the corresponding polyhedral cones $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$. We then define

$$ (22) \qquad Q_0(\mathcal{L}) := Q(\mathcal{L}) \cap \Delta $$

to be the intersection of $Q(\mathcal{L})$ with the unit simplex $\Delta$. Points in $Q_0(\mathcal{L})$ are normalized to probability distributions. Analogously define $\hat{Q}_0(\mathcal{L})$ to be the intersection of $\hat{Q}(\mathcal{L})$ with the unit simplex. Extremal rays of $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$ define vertices of $Q_0(\mathcal{L})$ and $\hat{Q}_0(\mathcal{L})$ respectively. We show the correspondence of extremal rays to lower sets and upper sets. The example also showcases the difference between a probabilistic language model and a general directed metric space where infinite distances are approximated uniformly by a big number $M$.

Section 7 further explores the extremal rays of $P(\mathcal{L})$.

In section 8 we explore the relation with the so called Isbell completions $I(\mathcal{L})$ and $\hat{I}(\mathcal{L})$. This is similar to the duality of section 6. The Isbell adjunction is defined over the extended ring $[-\infty, \infty]$ and the fixed parts of the adjunction turn out to be $I(\mathcal{L}) = \text{Im}(d_{\max})$ where $d_{\max}(x)_i := \max_j\{d_{i,j} + x_j\}$ and $\hat{I}(\mathcal{L}) = \text{Im}(d_{\max}^t)$. In (Proposition 29) it is shown that $P(\mathcal{L})$ is the lattice completion of the so called Isbell completion.

When restricting coefficients to $[0, \infty]$, the Isbell completion has been studied by Willerton [21] where it is proven to be isomorphic to the directed tight span $DTS(\mathcal{L})$ of Hirai and Koichi [7] (inspired by the undirected tight span defined by Isbell [8] and Dress [5]). It also generalizes the Dedekind-MacNeille completion of a poset.

Informally speaking $I(\mathcal{L})$ can be though of as the minimal space in which we can isometrically embed $\mathcal{L}$. Unlike $P(\mathcal{L})$ though, it is far from being convex. A simple example is shown in section 8.

Section 9 is a collection of observations about probabilistic language models and their relation to transformers.
$$ (21) \qquad e^{-\frac{\mathcal{R}(Y(b))}{T}} \approx \sum_i e^{-d(Y(w_i),b)/T} v_i $$

This approximation of text vectors is similar to the one calculated by transformer neural networks in the self attention module.

In section 6 we describe a duality between semantics via texts extensions and text restriction. Indeed we have already seen that $P(\mathcal{L}) = \{x|d_{\min}x = x\}$ is the (min,+) column span of $d$ and $\hat{P}(\mathcal{L}) = \{x|d_{\min}^t x = x\}$ is the (min,+) row span of $d$. It is easy to see that $d_{\min}x = x \iff d_{\min}^t(-x) = -x$ (Proposition 19). Indeed it follows from the fact that $x_i \le d_{i,j} + x_j \iff -x_j \le d_{i,j} - x_i$. However this requires extending the (min,+) semifield, as well as the values of the directed metric, to $[-\infty, \infty]$. This results in the definition of extended (min,+) modules $P^-(\mathcal{L})$ and $\hat{P}^-(\mathcal{L})$.

We show that $(P^-(\mathcal{L}), D)$ and $(\hat{P}^-(\mathcal{L}), D^t)$ are isometric (and in fact tropically anti-isomorphic). We interpret this as saying that the semantic space $\hat{P}^-(\mathcal{L})$, defined by extensions of texts is isomorphic to the semantic space $P^-(\mathcal{L})$ defined by restrictions of texts. We note that this is quite a non-trivial isomorphism as $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ don't even have the same number of extremal rays in general. We give an example (Example 1) illustrating the polyhedra $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$. In fact we consider the corresponding polyhedral cones $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$. We then define

$$ (22) \qquad Q_0(\mathcal{L}) := Q(\mathcal{L}) \cap \Delta $$

to be the intersection of $Q(\mathcal{L})$ with the unit simplex $\Delta$. Points in $Q_0(\mathcal{L})$ are normalized to probability distributions. Analogously define $\hat{Q}_0(\mathcal{L})$ to be the intersection of $\hat{Q}(\mathcal{L})$ with the unit simplex. Extremal rays of $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$ define vertices of $Q_0(\mathcal{L})$ and $\hat{Q}_0(\mathcal{L})$ respectively. We show the correspondence of extremal rays to lower sets and upper sets. The example also showcases the difference between a probabilistic language model and a general directed metric space where infinite distances are approximated uniformly by a big number $M$.

Section 7 further explores the extremal rays of $P(\mathcal{L})$.

In section 8 we explore the relation with the so called Isbell completions $I(\mathcal{L})$ and $\hat{I}(\mathcal{L})$. This is similar to the duality of section 6. The Isbell adjunction is defined over the extended ring $[-\infty, \infty]$ and the fixed parts of the adjunction turn out to be $I(\mathcal{L}) = \text{Im}(d_{\max})$ where $d_{\max}(x)_i := \max_j\{d_{i,j} + x_j\}$ and $\hat{I}(\mathcal{L}) = \text{Im}(d_{\max}^t)$. In (Proposition 29) it is shown that $P(\mathcal{L})$ is the lattice completion of the so called Isbell completion.

When restricting coefficients to $[0, \infty]$, the Isbell completion has been studied by Willerton [21] where it is proven to be isomorphic to the directed tight span $DTS(\mathcal{L})$ of Hirai and Koichi [7] (inspired by the undirected tight span defined by Isbell [8] and Dress [5]). It also generalizes the Dedekind-MacNeille completion of a poset.

Informally speaking $I(\mathcal{L})$ can be though of as the minimal space in which we can isometrically embed $\mathcal{L}$. Unlike $P(\mathcal{L})$ though, it is far from being convex. A simple example is shown in section 8.

Section 9 is a collection of observations about probabilistic language models and their relation to transformers.
As mentioned already, all constructions and results in this paper have categorical interpretations and though we have avoided using categorical language in the main text we explain briefly in Appendix A, for the benefit of readers familiar with categories, these categorical interpretations.

Finally in Appendix B we present a general perspective which locates the language syntax and semantics problems in the realm of a basic duality in mathematics which in its simplest form appears as a duality between algebra and geometry. This allows us to locate future directions of research.

Experimental evidence for the semantic meaning of the (co-)Yoneda embedding vectors $\tilde{Y}(a_k)$ has been provided in [12]. There experiments based on (a slight variation of) the co-Yoneda embedding vectors, were performed using an actual Transformer LLM, by sampling over continuations of texts. Several semantic tests were conducted and the results were in general very good.

1.1. Acknowledgements. YV would like to thank Tai-Danae Bradley, Michael Douglas, Ioannis Emiris, Harris Papageorgiou, Alex Takeda, John Terilla, Matthew Trager, Maxim Kontsevich, Matilde Marcolli, Jack Morava, Stefano Soatto, and Elias Zafiris for useful conversations. He also would like to thank Anna Geneveaux for computing several useful examples of polyhedra for probabilistic language models during her internship. SG and YV thank Gleb Koshevoy and Panayotis Mertikopoulos for useful conversations. Finally YV would like to thank IHES for providing excellent working conditions.

2. FROM PROBABILITIES OF TEXT EXTENSIONS TO DISTANCES

Consider a language with a set of words $W := \{w_1, \dots, w_l\}$. Consider also a set of training texts from the language, $\mathcal{L} := \{a_0, a_1, \dots, a_n\}$ where $a_i := w_{i_1} \dots w_{i_k}$. We endow $\mathcal{L}$ with a poset structure where $a_i \le a_j$ if and only if $a_i$ is a subtext of $a_j$. We consider two possibilities for the notion of subtext. The first is

$$ (23) \qquad a_i \le a_j \iff \exists a_k \in \mathcal{L} \text{ such that } a_j = a_i a_k $$

and we refer to this as the *one sided subtext order* and the second is

$$ (24) \qquad a_i \le a_j \iff \exists a_{k_1}, a_{k_2} \in \mathcal{L} \text{ such that } a_j = a_{k_1} a_{k_2} $$

and we refer to that as the *two sided subtext order*.

We define always $a_0$ to be the empty text and $a_0$ is the only text such that $a_0 \le a_i \forall i$ in either order. (However see remark (1) below for how $a_0$ interacts with the probabilities we will soon add to the model.)

If $a_i \le a_j$ in the one sided subtext order then $a_i \le a_j$. The results and constructions that follow hold equally for both orders so we will simply write $a_i \le a_j$ and when there is need to separate the two orders we will make a special comment.

If $a_i \le a_j$ then denote by $\text{Pr}(a_j|a_i)$ the probability of extension from $a_i$ to $a_j$.

It is important to note that these probabilities are not calculated from a corpus of texts, as any probability for a sufficiently long text would be vanishingly small. Instead we are talking about the probabilities that the large language model (LLM) computes. Namely prompted with a text $a_i$ the model outputs a probability distribution $\text{Pr}(a_i w_{j_1} | a_i) \forall w_{j_1} \in W$ and this is the probabilities we are referring to, above. To continue extending to $a_i w_{j_1} w_{j_2}$ we simply have

$$ (25) \qquad \text{Pr}(a_i w_{j_1} w_{j_2} | a_i) = \text{Pr}(a_i w_{j_1} | a_i) \text{Pr}(a_i w_{j_1} w_{j_2} | a_i w_{j_1}) $$
As mentioned already, all constructions and results in this paper have categorical interpretations and though we have avoided using categorical language in the main text we explain briefly in Appendix A, for the benefit of readers familiar with categories, these categorical interpretations.

Finally in Appendix B we present a general perspective which locates the language syntax and semantics problems in the realm of a basic duality in mathematics which in its simplest form appears as a duality between algebra and geometry. This allows us to locate future directions of research.

Experimental evidence for the semantic meaning of the (co-)Yoneda embedding vectors $\tilde{Y}(a_k)$ has been provided in [12]. There experiments based on (a slight variation of) the co-Yoneda embedding vectors, were performed using an actual Transformer LLM, by sampling over continuations of texts. Several semantic tests were conducted and the results were in general very good.

1.1. Acknowledgements. YV would like to thank Tai-Danae Bradley, Michael Douglas, Ioannis Emiris, Harris Papageorgiou, Alex Takeda, John Terilla, Matthew Trager, Maxim Kontsevich, Matilde Marcolli, Jack Morava, Stefano Soatto, and Elias Zafiris for useful conversations. He also would like to thank Anna Geneveaux for computing several useful examples of polyhedra for probabilistic language models during her internship. SG and YV thank Gleb Koshevoy and Panayotis Mertikopoulos for useful conversations. Finally YV would like to thank IHES for providing excellent working conditions.

2. FROM PROBABILITIES OF TEXT EXTENSIONS TO DISTANCES

Consider a language with a set of words $W := \{w_1, \dots, w_l\}$. Consider also a set of training texts from the language, $\mathcal{L} := \{a_0, a_1, \dots, a_n\}$ where $a_i := w_{i_1} \dots w_{i_k}$. We endow $\mathcal{L}$ with a poset structure where $a_i \le a_j$ if and only if $a_i$ is a subtext of $a_j$. We consider two possibilities for the notion of subtext. The first is

$$ (23) \qquad a_i \le a_j \iff \exists a_k \in \mathcal{L} \text{ such that } a_j = a_i a_k $$

and we refer to this as the *one sided subtext order* and the second is

$$ (24) \qquad a_i \le a_j \iff \exists a_{k_1}, a_{k_2} \in \mathcal{L} \text{ such that } a_j = a_{k_1} a_{k_2} $$

and we refer to that as the *two sided subtext order*.

We define always $a_0$ to be the empty text and $a_0$ is the only text such that $a_0 \le a_i \forall i$ in either order. (However see remark (1) below for how $a_0$ interacts with the probabilities we will soon add to the model.)

If $a_i \le a_j$ in the one sided subtext order then $a_i \le a_j$. The results and constructions that follow hold equally for both orders so we will simply write $a_i \le a_j$ and when there is need to separate the two orders we will make a special comment.

If $a_i \le a_j$ then denote by $\text{Pr}(a_j|a_i)$ the probability of extension from $a_i$ to $a_j$.

It is important to note that these probabilities are not calculated from a corpus of texts, as any probability for a sufficiently long text would be vanishingly small. Instead we are talking about the probabilities that the large language model (LLM) computes. Namely prompted with a text $a_i$ the model outputs a probability distribution $\text{Pr}(a_i w_{j_1} | a_i) \forall w_{j_1} \in W$ and this is the probabilities we are referring to, above. To continue extending to $a_i w_{j_1} w_{j_2}$ we simply have

$$ (25) \qquad \text{Pr}(a_i w_{j_1} w_{j_2} | a_i) = \text{Pr}(a_i w_{j_1} | a_i) \text{Pr}(a_i w_{j_1} w_{j_2} | a_i w_{j_1}) $$
And continuing this way $\mathrm{Pr}(a_j|a_i)$ is computed. If $a_i$ is not a subtext of $a_j$ then we put $\mathrm{Pr}(a_j|a_i) = 0$.

Recall that the LLM is trained to produce the probability distribution of the next word to a text, in such a way that the most likely next word predicted by the model is the one in the training text.

As a consequence of Equation (25) we make our fundamental assumption that

$$ (26) \qquad a_i \le a_j \le a_k \implies \mathrm{Pr}(a_k|a_i) = \mathrm{Pr}(a_k|a_j) \mathrm{Pr}(a_j|a_i) $$

Note that the transformer LLM produces the probabilities for the one-sided subtext order. However in the attention layers of the transformer, two sided extensions are used in order to construct the text vector. We consider therefore the case of the two sided order as well. Indeed in section 5 we will see that the text vector we define, is expressed in terms of word vectors when we consider the two sided subtext order. We put these together in the following

**Definition 1.** A probabilistic language model is a triple $(\mathcal{L}, \leq, \mathrm{Pr})$ where, $\mathcal{L} := \{a_0, a_1, \dots, a_n\}$ is a collection of texts, $\leq$ is the subtext order and $\mathrm{Pr}: \mathcal{L} \times \mathcal{L} \to [0, 1]$ is a function such that $a_i \le a_j \le a_k \implies \mathrm{Pr}(a_k|a_i) = \mathrm{Pr}(a_k|a_j) \mathrm{Pr}(a_j|a_i)$.

Recall now the following

**Definition 2.** $(X, \delta)$ is called a directed metric space if $X$ is a set and $\delta: X \times X \to (-\infty, \infty]$ satisfies the triangle inequality

$$ (27) \qquad \delta(a, c) \le \delta(a, b) + \delta(b, c) $$

for all $a, b, c \in X$ and $\delta(a, a) = 0, \forall a \in X$

Note that this generalises usual metrics in that we don't require $\delta(a, b) = \delta(b, a)$, $\delta(a, b) = 0$ does not necessarily imply $a = b$ and moreover we allow negative values. This definition of a directed metric, in the special case of positive valued $\delta$, has appeared in [21, 11] and is also known as a generalised metric or a pseudo quasi metric.

**Remark 2.** We need the following technical specification: In three cases (proposition 3 and the duality theorems of sections 6 and 8) we will need to extend definition 2, of a directed metric to allow the value $-\infty$ so that we will have. $\delta: X \times X \to [-\infty, \infty]$. In that case the definition is the same but we need to specify that we use the convention that $+\infty$ is the absorbing element so that $s + (+\infty) = +\infty$ for all $s$ and in particular $-\infty + \infty = +\infty$. This will be needed in Proposition 2. In section 6 we will explain further that this is the so called (min, +) convention, as this is the only one compatible with the structure of (min, +) semiring; there is also a dual (max, +) convention.

We define now a directed metric space structure on the underlying poset of a probabilistic language model $(\mathcal{L}, \leq, \mathrm{Pr})$.

**Definition 3.** Given the probabilistic language model $(\mathcal{L}, \leq, \mathrm{Pr})$ where $\leq$ is the subtext order and $\mathrm{Pr}(a_j|a_i)$ are the probabilities of extension, define the directed metric $d: \mathcal{L} \times \mathcal{L} \to [0, \infty]$ by

$$ (28) \qquad d(a_i, a_j) = \begin{cases} -\log \mathrm{Pr}(a_j|a_i) & \text{if } a_i \le a_j, \\ \infty & \text{if } a_i \text{ and } a_j \text{ are not comparable.} \end{cases} $$
And continuing this way $\Pr(a_j|a_i)$ is computed. If $a_i$ is not a subtext of $a_j$ then we put $\Pr(a_j|a_i) = 0$.

Recall that the LLM is trained to produce the probability distribution of the next word to a text, in such a way that the most likely next word predicted by the model is the one in the training text.

As a consequence of Equation (25) we make our fundamental assumption that

$$ (26) \qquad a_i \le a_j \le a_k \implies \Pr(a_k|a_i) = \Pr(a_k|a_j) \Pr(a_j|a_i) $$

Note that the transformer LLM produces the probabilities for the one-sided subtext order. However in the attention layers of the transformer, two sided extensions are used in order to construct the text vector. We consider therefore the case of the two sided order as well. Indeed in section 5 we will see that the text vector we define, is expressed in terms of word vectors when we consider the two sided subtext order. We put these together in the following

**Definition 1.** A probabilistic language model is a triple $(\mathcal{L}, \leq, \Pr)$ where, $\mathcal{L} := \{a_0, a_1, \dots, a_n\}$ is a collection of texts, $\leq$ is the subtext order and $\Pr: \mathcal{L} \times \mathcal{L} \to [0, 1]$ is a function such that $a_i \le a_j \le a_k \implies \Pr(a_k|a_i) = \Pr(a_k|a_j) \Pr(a_j|a_i)$.

Recall now the following

**Definition 2.** $(X, \delta)$ is called a directed metric space if $X$ is a set and $\delta: X \times X \to (-\infty, \infty]$ satisfies the triangle inequality

$$ (27) \qquad \delta(a, c) \le \delta(a, b) + \delta(b, c) $$

for all $a, b, c \in X$ and $\delta(a, a) = 0, \forall a \in X$

Note that this generalises usual metrics in that we don't require $\delta(a, b) = \delta(b, a)$, $\delta(a, b) = 0$ does not necessarily imply $a = b$ and moreover we allow negative values. This definition of a directed metric, in the special case of positive valued $\delta$, has appeared in [21, 11] and is also known as a generalised metric or a pseudo quasi metric.

**Remark 2.** We need the following technical specification: In three cases (proposition 3 and the duality theorems of sections 6 and 8) we will need to extend definition 2, of a directed metric to allow the value $-\infty$ so that we will have. $\delta: X \times X \to [-\infty, \infty]$. In that case the definition is the same but we need to specify that we use the convention that $+\infty$ is the absorbing element so that $s + (+\infty) = +\infty$ for all $s$ and in particular $-\infty + \infty = +\infty$. This will be needed in Proposition 2. In section 6 we will explain further that this is the so called (min, +) convention, as this is the only one compatible with the structure of (min, +) semiring; there is also a dual (max, +) convention.

We define now a directed metric space structure on the underlying poset of a probabilistic language model $(\mathcal{L}, \leq, \Pr)$.

**Definition 3.** Given the probabilistic language model $(\mathcal{L}, \leq, \Pr)$ where $\leq$ is the subtext order and $\Pr(a_j|a_i)$ are the probabilities of extension, define the directed metric $d: \mathcal{L} \times \mathcal{L} \to [0, \infty]$ by

$$ (28) \qquad d(a_i, a_j) = \begin{cases} -\log \Pr(a_j|a_i) & \text{if } a_i \le a_j, \\ \infty & \text{if } a_i \text{ and } a_j \text{ are not comparable.} \end{cases} $$
It is clear that $d(a_i, a_j) = 0$. To verify that $d$ is a directed metric we have the following:

**Proposition 1.** The map $d$ satisfies the triangle inequality:

$$ (29) \qquad d(a_i, a_k) \le d(a_i, a_j) + d(a_j, a_k), $$

and equality holds if and only if $a_i \le a_j \le a_k$ or $a_i \not\le a_k$.

*Proof.* Indeed, if $a_i \le a_j \le a_k$ then $a_i \le a_k$, and the equality holds in (29), since by our main assumption (the standard property of conditional probabilities), $\Pr(a_k|a_i) = \Pr(a_k|a_j)\Pr(a_j|a_i)$. If $a_i \not\le a_k$, then, $d(a_i, a_k) = \infty$, and either $a_i \not\le a_j$ or $a_j \not\le a_k$, which entails that both sides of (29) are equal to infinity. Finally, if $a_i \le a_k$ but $a_i \not\le a_j$ or $a_j \not\le a_k$, the left-hand side of (29) is finite whereas the right-hand side is $+\infty$. $\square$

We then have

**Corollary 1.** The following statements are equivalent:

(1) $a_i \le a_j \le a_k$

(2) $d(a_i, a_k) = d(a_i, a_j) + d(a_j, a_k)$ and $d(a_i, a_k) < \infty$

**Remark 3.** Note that from Proposition 1 and Corollary 1 it follows that the partial order $\le$ on $\mathcal{L}$ can be fully recovered by the directed metric $d$ or equivalently the conditional probabilities $\Pr(a_j|a_i)$, therefore we will also denote the probabilistic language model $(\mathcal{L}, \le, \Pr)$ as $(\mathcal{L}, \Pr)$ or $(\mathcal{L}, d)$.

**Remark 4.** In a Large Language model probabilities are normalized to add up to one, over all extensions of a given text by a word.

**Remark 5.** Note that the probabilistic language model $(\mathcal{L}, d)$ is a special case of a directed metric space. Whenever it is possible we will prove results for a general directed metric space and derive the language case as a corollary. Moreover, it is possible to imagine that even the main assumption $a_i \le a_j \le a_k$ $\implies$ $\Pr(a_k|a_i) = \Pr(a_k|a_j)\Pr(a_j|a_i)$ should be generalized to $\Pr(a_k|a_i) \ge \Pr(a_k|a_j)\Pr(a_j|a_i)$, namely this of a general directed metric space with $d(a_i, a_k) \le d(a_i, a_j) + d(a_j, a_k)$. This is a reasonable assumption by itself and can be interpreted a saying that the shortest path to go from $a_i$ to $a_k$ is at least as short as a path that is forced to go from $a_i$ to $a_k$ but passing through $a_j$. As we will see in what follows, the only result that requires the main assumption of conditional probabilities multiplying is Theorem 2 and all the rest are valid for general directed metric spaces. It is a matter of experimental verification to check for a given LLM if the multiplicative assumption is best or the general case.

**Remark 6.** Note that we can slightly modify the definition of the Probabilistic Language model so that instead of $\Pr$ taking values in $[0, 1]$ we put $\Pr: \mathcal{L} \times \mathcal{L} \to [0, \infty)$. Then definition 3 will again produce a directed metric space. In fact we develop most of the theory using the more general extended assumption since most results are valid for general directed metric spaces as we mentioned in the previous remark.

**Remark 7.** Since the machine produces probabilities for all possible next words it is natural to assume it is learning probabilities of extension for the free monoid generated by words. Obviously most strings of words will have vanishing probability and only those which are part of the language should have big probability.
It is clear that $d(a_i, a_j) = 0$. To verify that $d$ is a directed metric we have the following:

**Proposition 1.** The map $d$ satisfies the triangle inequality:

$$ (29) \qquad d(a_i, a_k) \le d(a_i, a_j) + d(a_j, a_k), $$

and equality holds if and only if $a_i \le a_j \le a_k$ or $a_i \not\le a_k$.

*Proof.* Indeed, if $a_i \le a_j \le a_k$ then $a_i \le a_k$, and the equality holds in (29), since by our main assumption (the standard property of conditional probabilities), $\Pr(a_k|a_i) = \Pr(a_k|a_j)\Pr(a_j|a_i)$. If $a_i \not\le a_k$, then, $d(a_i, a_k) = \infty$, and either $a_i \not\le a_j$ or $a_j \not\le a_k$, which entails that both sides of (29) are equal to infinity. Finally, if $a_i \le a_k$ but $a_i \not\le a_j$ or $a_j \not\le a_k$, the left-hand side of (29) is finite whereas the right-hand side is $+\infty$. $\square$

We then have

**Corollary 1.** The following statements are equivalent:

(1) $a_i \le a_j \le a_k$

(2) $d(a_i, a_k) = d(a_i, a_j) + d(a_j, a_k)$ and $d(a_i, a_k) < \infty$

**Remark 3.** Note that from Proposition 1 and Corollary 1 it follows that the partial order $\le$ on $\mathcal{L}$ can be fully recovered by the directed metric $d$ or equivalently the conditional probabilities $\Pr(a_j|a_i)$, therefore we will also denote the probabilistic language model $(\mathcal{L}, \le, \Pr)$ as $(\mathcal{L}, \Pr)$ or $(\mathcal{L}, d)$.

**Remark 4.** In a Large Language model probabilities are normalized to add up to one, over all extensions of a given text by a word.

**Remark 5.** Note that the probabilistic language model $(\mathcal{L}, d)$ is a special case of a directed metric space. Whenever it is possible we will prove results for a general directed metric space and derive the language case as a corollary. Moreover, it is possible to imagine that even the main assumption $a_i \le a_j \le a_k$ $\implies$ $\Pr(a_k|a_i) = \Pr(a_k|a_j)\Pr(a_j|a_i)$ should be generalized to $\Pr(a_k|a_i) \ge \Pr(a_k|a_j)\Pr(a_j|a_i)$, namely this of a general directed metric space with $d(a_i, a_k) \le d(a_i, a_j) + d(a_j, a_k)$. This is a reasonable assumption by itself and can be interpreted a saying that the shortest path to go from $a_i$ to $a_k$ is at least as short as a path that is forced to go from $a_i$ to $a_k$ but passing through $a_j$. As we will see in what follows, the only result that requires the main assumption of conditional probabilities multiplying is Theorem 2 and all the rest are valid for general directed metric spaces. It is a matter of experimental verification to check for a given LLM if the multiplicative assumption is best or the general case.

**Remark 6.** Note that we can slightly modify the definition of the Probabilistic Language model so that instead of $\Pr$ taking values in $[0, 1]$ we put $\Pr: \mathcal{L} \times \mathcal{L} \to [0, \infty)$. Then definition 3 will again produce a directed metric space. In fact we develop most of the theory using the more general extended assumption since most results are valid for general directed metric spaces as we mentioned in the previous remark.

**Remark 7.** Since the machine produces probabilities for all possible next words it is natural to assume it is learning probabilities of extension for the free monoid generated by words. Obviously most strings of words will have vanishing probability and only those which are part of the language should have big probability.
We can then consider $\mathcal{L}$ to contain the whole free monoid and it is natural to grade it by the word length of each text.

**Remark 8.** Note that if we assume that there exists $a_0$ such that $a_0 \le a_k \forall a_k \in \mathcal{L}$ then $a_i \le a_j$ implies $a_0 \le a_i \le a_j$ and therefore $d(a_0, a_j) = d(a_0, a_i) + d(a_i, a_j)$ and thus $d(a_i, a_j) = d(a_0, a_j) - d(a_0, a_i)$. This is equivalent to the statement that there is a globally defined probability distribution for absolute probabilities of texts, giving rise to all the conditional probabilities. Namely if $a_i \le a_j$ then $\text{Pr}(a_j|a_i) = \frac{\text{Pr}(a_j|a_0)}{\text{Pr}(a_i|a_0)}$. The element $a_0$ can be considered to be the empty text and from this point of view it is natural to assume it exists in $\mathcal{L}$. However the fact that it implies all conditional probabilities come from a global probability distribution shows that the inclusion of $a_0$ in the probabilistic language model, is not an entirely trivial assumption.

It would be a matter for experimental verification to see if it applies in the transformer Large Language Models. Therefore we will not assume it by default. We will specify explicitly whenever we assume $a_0 \in \mathcal{L}$.

Next, we illustrate what the main assumption implies by the following:

**Proposition 2.** Consider a probabilistic language model ($\mathcal{L}$, $\le$, $\text{Pr}$) then on every connected component $C$ of the Hasse diagram of $\mathcal{L}$, there is a function $P_C: C \to [0, \infty)$ such that if $a_i, a_j \in C$ and $a_i \le a_j$ then $\text{Pr}(a_j|a_i) = \frac{P_C(a_j)}{P_C(a_i)}$. The function $P_C$ is unique up to multiplication by a positive number.

*Proof.* The fact that ($\mathcal{L}$, $\le$, $\text{Pr}$) is a probabilistic language model means that $a_i \le a_j \le a_k$ is equivalent to $\text{Pr}(a_k|a_i) = \text{Pr}(a_k|a_j) \text{Pr}(a_j|a_i)$ and $\text{Pr}(a_k|a_i) < \infty$.

Let $G$ denote the directed graph which is the Hasse diagram of $C$. We construct a new weighted graph $\tilde{G}$ as follows: If $a_i \le a_j$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\text{Pr}(a_j|a_i)$. If $a_j \le a_i$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\text{Pr}(a_j|a_i)^{-1}$. We now choose arbitrarily an element $c \in C$. If $a_i \in C$, we define $P_C(a_i)$ to be the weight in the graph $\tilde{G}$ of an arbitrary path from the point $c$ to $a_i$. Owing to our main assumption, (1), the weight is independent of the choice of the path from $c$ to $a_i$. Moreover, for all $i, j$ such that $a_i \le a_j$, we have $P_C(a_i) \text{Pr}(a_j|a_i) P_C(a_j)^{-1} = 1$ therefore $\text{Pr}(a_j|a_i) = \frac{P_C(a_i)}{P_C(a_j)}$.

Picking a different reference element $c' \in C$ scales $P_C(a_i)$ by $P_C(c')$ therefore the ratio stays the same. $\square$

### 3. FROM THE TEXT METRIC SPACE $\mathcal{L}$ TO THE POLYHEDRA $P(\mathcal{L})$ AND $Q(\mathcal{L})$

First notice that we can also equip $\mathcal{L}$ with the transpose directed metric $d^t$ where $d^t(a_i, a_j) := d(a_j, a_i)$.

We now construct two directed metric, polyhedra $P(\mathcal{L})$ and $\tilde{P}(\mathcal{L})$ in which the directed metric space $(\mathcal{L}, d)$ is isometrically embedded as a special set of extremal rays.

To that end, we equip $\{\mathbb{R} \cup \{\infty\}\}^n \setminus \{(\infty, \dots, \infty)\}$ for $n \ge 2$, with the *Funk* metric $D$ defined by

$$ (30) \quad D(x, y) := \inf\{\lambda \in \mathbb{R} \cup \{+\infty\} \mid \lambda + x \ge y\} = \max_i\{y_i - x_i \mid x_i \ne \infty\}. $$

This is a directed metric. Note that it takes possibly negative values, and that it can also take the value $\infty$.

We also denote by $D^t$ the transpose directed metric with $D^t(x, y) := D(y, x)$.
We can then consider $\mathcal{L}$ to contain the whole free monoid and it is natural to grade it by the word length of each text.

**Remark 8.** Note that if we assume that there exists $a_0$ such that $a_0 \le a_k \forall a_k \in \mathcal{L}$ then $a_i \le a_j$ implies $a_0 \le a_i \le a_j$ and therefore $d(a_0, a_j) = d(a_0, a_i) + d(a_i, a_j)$ and thus $d(a_i, a_j) = d(a_0, a_j) - d(a_0, a_i)$. This is equivalent to the statement that there is a globally defined probability distribution for absolute probabilities of texts, giving rise to all the conditional probabilities. Namely if $a_i \le a_j$ then $\text{Pr}(a_j|a_i) = \frac{\text{Pr}(a_j|a_0)}{\text{Pr}(a_i|a_0)}$. The element $a_0$ can be considered to be the empty text and from this point of view it is natural to assume it exists in $\mathcal{L}$. However the fact that it implies all conditional probabilities come from a global probability distribution shows that the inclusion of $a_0$ in the probabilistic language model, is not an entirely trivial assumption.

It would be a matter for experimental verification to see if it applies in the transformer Large Language Models. Therefore we will not assume it by default. We will specify explicitly whenever we assume $a_0 \in \mathcal{L}$.

Next, we illustrate what the main assumption implies by the following:

**Proposition 2.** Consider a probabilistic language model ($\mathcal{L}$, $\le$, $\text{Pr}$) then on every connected component $C$ of the Hasse diagram of $\mathcal{L}$, there is a function $P_C: C \to [0, \infty)$ such that if $a_i, a_j \in C$ and $a_i \le a_j$ then $\text{Pr}(a_j|a_i) = \frac{P_C(a_j)}{P_C(a_i)}$. The function $P_C$ is unique up to multiplication by a positive number.

*Proof.* The fact that ($\mathcal{L}$, $\le$, $\text{Pr}$) is a probabilistic language model means that $a_i \le a_j \le a_k$ is equivalent to $\text{Pr}(a_k|a_i) = \text{Pr}(a_k|a_j)\text{Pr}(a_j|a_i)$ and $\text{Pr}(a_k|a_i) < \infty$.

Let $G$ denote the directed graph which is the Hasse diagram of $C$. We construct a new weighted graph $\tilde{G}$ as follows: If $a_i \le a_j$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\text{Pr}(a_j|a_i)$. If $a_j \le a_i$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\text{Pr}(a_j|a_i)^{-1}$. We now choose arbitrarily an element $c \in C$. If $a_i \in C$, we define $P_C(a_i)$ to be the weight in the graph $\tilde{G}$ of an arbitrary path from the point $c$ to $a_i$. Owing to our main assumption, (1), the weight is independent of the choice of the path from $c$ to $a_i$. Moreover, for all $i, j$ such that $a_i \le a_j$, we have $P_C(a_i)\text{Pr}(a_j|a_i)P_C(a_j)^{-1} = 1$ therefore $\text{Pr}(a_j|a_i) = \frac{P_C(a_i)}{P_C(a_j)}$.

Picking a different reference element $c' \in C$ scales $P_C(a_i)$ by $P_C(c')$ therefore the ratio stays the same. $\square$

### 3. FROM THE TEXT METRIC SPACE $\mathcal{L}$ TO THE POLYHEDRA $P(\mathcal{L})$ AND $Q(\mathcal{L})$

First notice that we can also equip $\mathcal{L}$ with the transpose directed metric $d^t$ where $d^t(a_i, a_j) := d(a_j, a_i)$.

We now construct two directed metric, polyhedra $P(\mathcal{L})$ and $\tilde{P}(\mathcal{L})$ in which the directed metric space $(\mathcal{L}, d)$ is isometrically embedded as a special set of extremal rays.

To that end, we equip $\{\mathbb{R} \cup \{\infty\}\}^n \setminus \{(\infty, \dots, \infty)\}$ for $n \ge 2$, with the *Funk* metric $D$ defined by

$$ (30) \quad D(x, y) := \inf\{\lambda \in \mathbb{R} \cup \{+\infty\} \mid \lambda + x \ge y\} = \max_i\{y_i - x_i \mid x_i \ne \infty\}. $$

This is a directed metric. Note that it takes possibly negative values, and that it can also take the value $\infty$.

We also denote by $D^t$ the transpose directed metric with $D^t(x, y) := D(y, x)$.
**Definition 4.** Let $(P(\mathcal{L}), D)$ be the directed metric polyhedron

$$
(31) \quad P(\mathcal{L}) := \{x = (x_1, \dots, x_n) \in \mathbb{R} \cup \{\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} | x_i \le x_j + d_{i,j}.
$$
Moreover let $(\hat{P}(\mathcal{L}), D^t)$ be the directed metric polyhedron

$$
(32) \quad \hat{P}(\mathcal{L}) := \{y = (y_1, \dots, y_n) \in \mathbb{R} \cup \{\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} | y_i \le y_j + d_{j,i}.
$$

For the following proposition, we need to extend the Funk metric in eq. 30 to
$n = 1$. For this we will use the fact that $\max \emptyset = -\infty$. From this it follows that for
$n = 1$ the Funk metric $d_{\mathbb{R}} : (-\infty, \infty]^2 \to [-\infty, \infty]$ is given by

$$
(33) \qquad d_{\mathbb{R}}(s, t) := t - s \text{ if } s \neq \infty \text{ and } d_{\mathbb{R}}(\infty, t) = -\infty .
$$

In particular $d_{\mathbb{R}}(\infty, \infty) = -\infty$. Notice that $d_{\mathbb{R}}$ can also take the value $-\infty$ and this case of a directed metric, was explained in Remark 2.

**Proposition 3.** $P(\mathcal{L})$ is the set of non expansive maps $x : (\mathcal{L}, d^t) \to ((-\infty, \infty], d_{\mathbb{R}})$. Namely $x$ satisfies

$$
(34) \qquad d_{\mathbb{R}}(x(a_j), x(a_i)) \le d^t(a_j, a_i)
$$

Moreover $\hat{P}(\mathcal{L})$ is the set of non expansive maps $y : (\mathcal{L}, d) \to ((-\infty, \infty], d_{\mathbb{R}})$. Namely $y$ satisfies

$$
(35) \qquad d_F(y(a_j), y(a_i)) \le d(a_j, a_i)
$$

*Proof.* To see this description of $P(\mathcal{L})$, let $x_i := x(a_i)$. Then

$$
d_{\mathbb{R}}(x(a_j), x(a_i)) \le d^t(a_j, a_i) \iff x(a_i) - x(a_j) \le d(a_i, a_j) \iff x_i - x_j \le d_{i,j}.
$$

Likewise to see this description of $\hat{P}(\mathcal{L})$, let $y_i := y(a_i)$. Then

$$
d_{\mathbb{R}}(y(a_j), y(a_i)) \le d(a_j, a_i) \iff y(a_i) - y(a_j) \le d(a_j, a_i) \iff y_i - y_j \le d_{j,i}.
$$

□

**Remark 9.** Following Proposition 3 we see that we can view $P(\mathcal{L})$ as a space of functions on the metric space $\mathcal{L}$ and we will see in Section 4 that it is similar to considering real vectors as real valued functions on a set.

**Proposition 4.** The map

$$
(36) \quad Y : (\mathcal{L}, d) \hookrightarrow (P(\mathcal{L}), D) \text{ given by } Y(a_k) := d(-, a_k)
$$

is called the Yoneda embedding<fnref n="4" /> and is an isometric embedding. Moreover the
map

$$
(37) \quad \hat{Y} : (\mathcal{L}, d) \hookrightarrow (\hat{P}(\mathcal{L}), D^t) \text{ given by } \hat{Y}(a_k) := d(a_k, -)
$$

is also an isometric embedding and is called the co-Yoneda embedding.

*Proof.* First note that for any $a_k \in \mathcal{L}$ the function $Y(a_k) := d(-, a_k)$ is in $P(\mathcal{L})$ and the function $\hat{Y} := d(a_k, -) : \mathcal{L} \to [0, \infty)$ is in $\hat{P}(\mathcal{L})$.

Indeed by the triangle inequality, $d(a_i, a_k) \le d(a_i, a_j) + d(a_j, a_k)$, in other words if $x := d(-, a_k)$ and $x_i := d(a_i, a_k)$ then $x_i \le x_j + d_{i,j}$ proving that $Y(a_k) \in P(\mathcal{L})$.

Analogously $d(a_k, a_i) \le d(a_k, a_j) + d(a_j, a_i)$ and therefore if $y := d(a_k, -)$ then $y_i \le y_j + d_{j,i}$ proving that $\hat{Y}(a_k) \in \hat{P}(\mathcal{L})$.

<footnote n="4">⁴The reason for the name Yoneda embedding comes from its appearance in category theory and was explained in [1]. It is similar to the so called, Kuratowski embedding of a metric space.</footnote>
**Definition 4.** Let $(P(\mathcal{L}), D)$ be the directed metric polyhedron

$$ (31) \quad P(\mathcal{L}) := \{x = (x_1, \dots, x_n) \in \mathbb{R} \cup \{\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} | x_i \le x_j + d_{i,j}. $$

Moreover let $(\hat{P}(\mathcal{L}), D^t)$ be the directed metric polyhedron

$$ (32) \quad \hat{P}(\mathcal{L}) := \{y = (y_1, \dots, y_n) \in \mathbb{R} \cup \{\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} | y_i \le y_j + d_{j,i}. $$

For the following proposition, we need to extend the Funk metric in eq. 30 to $n=1$. For this we will use the fact that $\max \emptyset = -\infty$. From this it follows that for $n=1$ the Funk metric $d_{\mathbb{R}}: (-\infty, \infty]^2 \to [-\infty, \infty]$ is given by

$$ (33) \quad d_{\mathbb{R}}(s, t) := t - s \text{ if } s \neq \infty \text{ and } d_{\mathbb{R}}(\infty, t) = -\infty. $$

In particular $d_{\mathbb{R}}(\infty, \infty) = -\infty$. Notice that $d_{\mathbb{R}}$ can also take the value $-\infty$ and this case of a directed metric, was explained in Remark 2.

**Proposition 3.** $P(\mathcal{L})$ is the set of non expansive maps $x : (\mathcal{L}, d^t) \to ((-\infty, \infty], d_{\mathbb{R}})$. Namely $x$ satisfies

$$ (34) \quad d_{\mathbb{R}}(x(a_j), x(a_i)) \le d^t(a_j, a_i) $$

Moreover $\hat{P}(\mathcal{L})$ is the set of non expansive maps $y : (\mathcal{L}, d) \to ((-\infty, \infty], d_{\mathbb{R}})$. Namely $y$ satisfies

$$ (35) \quad d_F(y(a_j), y(a_i)) \le d(a_j, a_i) $$

*Proof.* To see this description of $P(\mathcal{L})$, let $x_i := x(a_i)$. Then

$$ d_{\mathbb{R}}(x(a_j), x(a_i)) \le d^t(a_j, a_i) \iff x(a_i) - x(a_j) \le d(a_i, a_j) \iff x_i - x_j \le d_{i,j}. $$

Likewise to see this description of $\hat{P}(\mathcal{L})$, let $y_i := y(a_i)$. Then

$$ d_{\mathbb{R}}(y(a_j), y(a_i)) \le d(a_j, a_i) \iff y(a_i) - y(a_j) \le d(a_j, a_i) \iff y_i - y_j \le d_{j,i}. $$

□

**Remark 9.** Following Proposition 3 we see that we can view $P(\mathcal{L})$ as a space of functions on the metric space $\mathcal{L}$ and we will see in Section 4 that it is similar to considering real vectors as real valued functions on a set.

**Proposition 4.** The map

$$ (36) \quad Y : (\mathcal{L}, d) \hookrightarrow (P(\mathcal{L}), D) \text{ given by } Y(a_k) := d(-, a_k) $$

is called the Yoneda embedding $^4$ and is an isometric embedding. Moreover the map

$$ (37) \quad \hat{Y} : (\mathcal{L}, d) \hookrightarrow (\hat{P}(\mathcal{L}), D^t) \text{ given by } \hat{Y}(a_k) := d(a_k, -) $$

is also an isometric embedding and is called the co-Yoneda embedding.

*Proof.* First note that for any $a_k \in \mathcal{L}$ the function $Y(a_k) := d(-, a_k)$ is in $P(\mathcal{L})$ and the function $\hat{Y} := d(a_k, -) : \mathcal{L} \to [0, \infty)$ is in $\hat{P}(\mathcal{L})$.

Indeed by the triangle inequality, $d(a_i, a_k) \le d(a_i, a_j) + d(a_j, a_k)$, in other words if $x := d(-, a_k)$ and $x_i := d(a_i, a_k)$ then $x_i \le x_j + d_{i,j}$ proving that $Y(a_k) \in P(\mathcal{L})$.

Analogously $d(a_k, a_i) \le d(a_k, a_j) + d(a_j, a_i)$ and therefore if $y := d(a_k, -)$ then $y_i \le y_j + d_{j,i}$ proving that $\hat{Y}(a_k) \in \hat{P}(\mathcal{L})$.

<footnote>$^4$The reason for the name Yoneda embedding comes from its appearance in category theory and was explained in [1]. It is similar to the so called, Kuratowski embedding of a metric space.</footnote>
Moreover, the inequality Equation (29) entails that $d(-, a_i)+d(a_i, a_j) \ge d(-, a_j)$, and so, $D(d(-, a_i), d(-, a_j)) \le d(a_i, a_j)$. On the other hand, if $x, y \in P(\mathcal{L})$ then $D(x, y) \ge y_l - x_l$ for all $l$ and thus $D(d(-, a_i), d(-, a_j) \ge d(a_i, a_j) - d(a_i, a_i) = d(a_i, a_j)$. Consequently $D(d(-, a_i), d(-, a_j)) = d(a_i, a_j)$ i.e. $a \mapsto d(-, a)$ is an isometry.

Likewise we have $d(a_j, a_i) + d(a_i, -) \ge d(a_j, -)$ and $d(a_j, -) - d(a_i, -) \le d_{j,i}$ which implies that $D(d(a_i, -), d(a_j, -)) \le d_{j,i}$.

Moreover $D(d(a_i, -), d(a_j, -)) \ge d(a_j, a_i) - d(a_i, a_i) = d(a_j, a_i)$. Thus

$$D(d(a_i, -), d(a_j, -)) = d_{j,i}.$$

□

To further understand the polyhedron $P(\mathcal{L})$ we consider the change of variables $z_i := e^{-x_i}$ and introduce the following:

**Definition 5.** Let $Q(\mathcal{L})$ be the polyhedral cone

$$ (38) \quad Q(\mathcal{L}) := \{z = (z_1, \dots, z_n) \in [0, \infty)^n \setminus \{(0, \dots, 0)\} \mid z_i \ge \mathrm{Pr}(a_j | a_i) z_j\} $$

Moreover let $\hat{Q}(\mathcal{L})$ be the polyhedral cone

$$ (39) \quad \hat{Q}(\mathcal{L}) := \{u = (u_1, \dots, u_n) \in [0, \infty)^n \setminus \{(0, \dots, 0)\} \mid u_i \ge \mathrm{Pr}(a_i | a_j) u_j\} $$

Note that if $z$ is in $Q(\mathcal{L})$ then $\lambda z \in Q(\mathcal{L})$ for $\lambda \in [0, \infty)$ therefore $Q(\mathcal{L})$ is indeed a polyhedral cone in the positive orthant and so is $\hat{Q}(\mathcal{L})$.

To simplify notation we introduce the convention that if $v = (v_1, \dots, v_n) \in \mathbb{R}^n$ then

$$ (40) \quad e^v := (e^{v_1}, \dots, e^{v_n}) \quad \text{and} \quad \log(v) := (\log(v_1), \dots, \log(v_n)) $$

We see that

$$ (41) \quad Q(\mathcal{L}) = \{z \in [0, \infty)^n \mid z := e^{-x} \text{ for } x \in P(\mathcal{L})\} $$

and

$$ (42) \quad \hat{Q}(\mathcal{L}) = \{u \in [0, \infty)^n \mid u := e^{-y} \text{ for } y \in \hat{P}(\mathcal{L})\} $$

And vice versa

$$ (43) \quad P(\mathcal{L}) = \{x \in (-\infty, \infty]^n \mid x := -\log(z) \text{ for } z \in Q(\mathcal{L})\} $$

and

$$ (44) \quad \hat{P}(\mathcal{L}) = \{y \in (-\infty, \infty]^n \mid y := -\log(u) \text{ for } u \in \hat{Q}(\mathcal{L})\}. $$

Using the map $-\log : Q(\mathcal{L}) \to P(\mathcal{L})$ we can define a directed metric $D_Q$ on $Q(\mathcal{L})$ using the Funk metric $D$ on $P(\mathcal{L})$. We put

$$ (45) \quad D_Q(z, z') := \max_i \{\log(\frac{z_i}{z'_i}) \mid z'_i \neq 0\}. $$

By definition we have

$$ (46) \quad D_Q(z, z') = D(-\log z, -\log z') \quad \text{and} \quad D(x, x') = D_Q(e^{-x}, e^{-x'}). $$

Clearly the transpose $D_Q^t$ defines a directed metric on $\hat{Q}(\mathcal{L})$.

Then Proposition 4 implies that

**Corollary 2.** The maps

$$ (47) \quad e^{-Y} : (\mathcal{L}, d) \to (Q(\mathcal{L}), D_Q) \quad \text{and} \quad e^{-\hat{Y}} : (\mathcal{L}, d) \to (\hat{Q}(\mathcal{L}), D_Q^t) $$

are isometric embeddings
Moreover, the inequality Equation (29) entails that $d(-, a_i)+d(a_i, a_j) \ge d(-, a_j)$, and so, $D(d(-, a_i), d(-, a_j)) \le d(a_i, a_j)$. On the other hand, if $x, y \in P(\mathcal{L})$ then $D(x, y) \ge y_l - x_l$ for all $l$ and thus $D(d(-, a_i), d(-, a_j) \ge d(a_i, a_j) - d(a_i, a_i) = d(a_i, a_j)$. Consequently $D(d(-, a_i), d(-, a_j)) = d(a_i, a_j)$ i.e. $a \mapsto d(-, a)$ is an isometry.

Likewise we have $d(a_j, a_i) + d(a_i, -) \ge d(a_j, -)$ and $d(a_j, -) - d(a_i, -) \le d_{j,i}$ which implies that $D(d(a_i, -), d(a_j, -)) \le d_{j,i}$.

Moreover $D(d(a_i, -), d(a_j, -)) \ge d(a_j, a_i) - d(a_i, a_i) = d(a_j, a_i)$. Thus

$$D(d(a_i, -), d(a_j, -)) = d_{j,i}.$$

□

To further understand the polyhedron $P(\mathcal{L})$ we consider the change of variables $z_i := e^{-x_i}$ and introduce the following:

**Definition 5.** Let $Q(\mathcal{L})$ be the polyhedral cone

$$ (38) \quad Q(\mathcal{L}) := \{z = (z_1, \dots, z_n) \in [0, \infty)^n \setminus \{(0, \dots, 0)\} | z_i \ge \mathrm{Pr}(a_j|a_i)z_j\} $$

Moreover let $\hat{Q}(\mathcal{L})$ be the polyhedral cone

$$ (39) \quad \hat{Q}(\mathcal{L}) := \{u = (u_1, \dots, u_n) \in [0, \infty)^n \setminus \{(0, \dots, 0)\} | u_i \ge \mathrm{Pr}(a_i|a_j)u_j\} $$

Note that if $z$ is in $Q(\mathcal{L})$ then $\lambda z \in Q(\mathcal{L})$ for $\lambda \in [0, \infty)$ therefore $Q(\mathcal{L})$ is indeed a polyhedral cone in the positive orthant and so is $\hat{Q}(\mathcal{L})$.

To simplify notation we introduce the convention that if $v = (v_1, \dots, v_n) \in \mathbb{R}^n$ then

$$ (40) \quad e^v := (e^{v_1}, \dots, e^{v_n}) \quad \text{and} \quad \log(v) := (\log(v_1), \dots, \log(v_n)) $$

We see that

$$ (41) \quad Q(\mathcal{L}) = \{z \in [0, \infty)^n | z := e^{-x} \text{ for } x \in P(\mathcal{L})\} $$

and

$$ (42) \quad \hat{Q}(\mathcal{L}) = \{u \in [0, \infty)^n | u := e^{-y} \text{ for } y \in \hat{P}(\mathcal{L})\} $$

And vice versa

$$ (43) \quad P(\mathcal{L}) = \{x \in (-\infty, \infty]^n | x := -\log(z) \text{ for } z \in Q(\mathcal{L})\} $$

and

$$ (44) \quad \hat{P}(\mathcal{L}) = \{y \in (-\infty, \infty]^n | y := -\log(u) \text{ for } u \in \hat{Q}(\mathcal{L})\}. $$

Using the map $-\log : Q(\mathcal{L}) \to P(\mathcal{L})$ we can define a directed metric $D_Q$ on $Q(\mathcal{L})$ using the Funk metric $D$ on $P(\mathcal{L})$. We put

$$ (45) \quad D_Q(z, z') := \max_i \{\log(\frac{z_i}{z'_i}) | z'_i \neq 0\}. $$

By definition we have

$$ (46) \quad D_Q(z, z') = D(-\log z, -\log z') \quad \text{and} \quad D(x, x') = D_Q(e^{-x}, e^{-x'}). $$

Clearly the transpose $D_Q^t$ defines a directed metric on $\hat{Q}(\mathcal{L})$.

Then Proposition 4 implies that

**Corollary 2.** The maps

$$ (47) \quad e^{-Y} : (\mathcal{L}, d) \to (Q(\mathcal{L}), D_Q) \quad \text{and} \quad e^{-\hat{Y}} : (\mathcal{L}, d) \to (\hat{Q}(\mathcal{L}), D_Q^t) $$

are isometric embeddings
**Proof.** It follows from Proposition 2 since

$$d(a_k, a_l) = D(Y(a_k), Y(a_l)) = D_Q(e^{-Y(a_k)}, e^{-Y(a_l)}) . \quad \square$$

We define the unit simplex

$$\Delta := \{z \in [0,1]^n | \sum_i z_i = 1\} .$$

**Definition 6.** Define the polyhedron $Q_0(\mathcal{L})$ by

$$(48) \qquad Q_0(\mathcal{L}) := Q(\mathcal{L}) \cap \Delta.$$

Then $(Q_0(\mathcal{L}), D_Q)$ is a directed metric polyhedron and points in $Q_0(\mathcal{L})$ are probability distributions.

Analogously we define the polyhedron $\hat{Q}_0(\mathcal{L})$ as the intersection of $\hat{Q}(\mathcal{L})$ with the unit simplex and $D_Q^t$ is a directed metric on it.

**Remark 10.** The polyhedra $Q_0(\mathcal{L})$ and $\hat{Q}_0(\mathcal{L})$ define a normalization to probability distributions of our probabilistic language model $\mathcal{L}$. Indeed in the definition of $(\mathcal{L}, \leq, \text{Pr})$ we only ask for the conditional probabilities multiplicative property but there is no normalization to a probability distribution.

Now if we consider the vertex of $Q_0(\mathcal{L})$, corresponding to the ray generated by $e^{-Y(a_k)}$, it will be $\frac{1}{n(a_k)}e^{-Y(a_k)}$ where

$$n(a_k) := \sum_{a_j \leq a_k} (e^{-Y(a_k)})_j = \sum_{a_j \leq a_k} \text{Pr}(a_k|a_j)$$

is the normalization factor.

While the vertex of $\hat{Q}_0(\mathcal{L})$ corresponding to the ray generated by $e^{-\hat{Y}(a_k)}$ will be $\frac{1}{\hat{n}(a_k)}e^{-Y(a_k)}$ where

$$\hat{n}(a_k) := \sum_{a_k \leq a_l} (e^{-\hat{Y}(a_k)})_j = \sum_{a_k \leq a_l} \text{Pr}(a_l|a_k)$$

is the normalization factor.

**Remark 11.** The polyhedral cone $Q(\mathcal{L})$ is a generalization of the order polytope defined by Stanley [18]. The order polytope corresponds to the case where $\text{Pr}(a_j|a_i)$ takes only the values 0 or 1, moreover, Stanley adds the “box constraint” $z_i \in [0, 1]$ which translates to $x_i \in [0, \infty]$. Up to the box constraint, $Q(\mathcal{L})$ corresponds to the order polytope of the poset $(\mathcal{L}^{\text{op}}, \leq)$ where $\mathcal{L}^{\text{op}}$ is the opposite poset.

Stanley [18] proves that vertices of an order polytope correspond to upper sets of the poset. We will prove a generalization of that result in Theorem 2 in section 3.2.

We now explain what is the geometric meaning of the coordinates of a point $x = (x_1, x_2, \dots, x_n) \in P(\mathcal{L})$ and a point $y = (y_1, y_2, \dots, y_n) \in \hat{P}(\mathcal{L})$.

**Proposition 5.** If $x \in P(\mathcal{L})$ then

$$(49) \qquad x_i = D(d(-, a_i), x) = D(Y(a_i), x).$$

Moreover if $y \in \hat{P}(\mathcal{L})$ then

$$(50) \qquad y_i = D^t(y, d(a_i, -)) = D(\hat{Y}(a_i), y).$$
**Proof.** It follows from Proposition 2 since

$$d(a_k, a_l) = D(Y(a_k), Y(a_l)) = D_Q(e^{-Y(a_k)}, e^{-Y(a_l)}). \quad \square$$

We define the unit simplex

$$\Delta := \{z \in [0,1]^n | \sum_i z_i = 1\}.$$

**Definition 6.** Define the polyhedron $Q_0(\mathcal{L})$ by

$$(48) \qquad Q_0(\mathcal{L}) := Q(\mathcal{L}) \cap \Delta.$$

Then $(Q_0(\mathcal{L}), D_Q)$ is a directed metric polyhedron and points in $Q_0(\mathcal{L})$ are probability distributions.

Analogously we define the polyhedron $\hat{Q}_0(\mathcal{L})$ as the intersection of $\hat{Q}(\mathcal{L})$ with the unit simplex and $D_Q^t$ is a directed metric on it.

**Remark 10.** The polyhedra $Q_0(\mathcal{L})$ and $\hat{Q}_0(\mathcal{L})$ define a normalization to probability distributions of our probabilistic language model $\mathcal{L}$. Indeed in the definition of $(\mathcal{L}, \leq, \text{Pr})$ we only ask for the conditional probabilities multiplicative property but there is no normalization to a probability distribution.

Now if we consider the vertex of $Q_0(\mathcal{L})$, corresponding to the ray generated by $e^{-Y(a_k)}$, it will be $\frac{1}{n(a_k)}e^{-Y(a_k)}$ where

$$n(a_k) := \sum_{a_j \leq a_k} (e^{-Y(a_k)})_j = \sum_{a_j \leq a_k} \text{Pr}(a_k|a_j)$$

is the normalization factor.

While the vertex of $\hat{Q}_0(\mathcal{L})$ corresponding to the ray generated by $e^{-\hat{Y}(a_k)}$ will be $\frac{1}{\hat{n}(a_k)}e^{-Y(a_k)}$ where

$$\hat{n}(a_k) := \sum_{a_k \leq a_l} (e^{-\hat{Y}(a_k)})_j = \sum_{a_k \leq a_l} \text{Pr}(a_l|a_k)$$

is the normalization factor.

**Remark 11.** The polyhedral cone $Q(\mathcal{L})$ is a generalization of the order polytope defined by Stanley [18]. The order polytope corresponds to the case where $\text{Pr}(a_j|a_i)$ takes only the values 0 or 1, moreover, Stanley adds the “box constraint” $z_i \in [0, 1]$ which translates to $x_i \in [0, \infty]$. Up to the box constraint, $Q(\mathcal{L})$ corresponds to the order polytope of the poset $(\mathcal{L}^{\text{op}}, \leq)$ where $\mathcal{L}^{\text{op}}$ is the opposite poset.

Stanley [18] proves that vertices of an order polytope correspond to upper sets of the poset. We will prove a generalization of that result in Theorem 2 in section 3.2.

We now explain what is the geometric meaning of the coordinates of a point $x = (x_1, x_2, \dots, x_n) \in P(\mathcal{L})$ and a point $y = (y_1, y_2, \dots, y_n) \in \hat{P}(\mathcal{L})$.

**Proposition 5.** If $x \in P(\mathcal{L})$ then

$$(49) \qquad x_i = D(d(-, a_i), x) = D(Y(a_i), x).$$

Moreover if $y \in \hat{P}(\mathcal{L})$ then

$$(50) \qquad y_i = D^t(y, d(a_i, -)) = D(\hat{Y}(a_i), y).$$
**Proof.** We have $D(d(-, a_i), x)) \ge x_i - d(a_i, a_i) = x_i$.

On the other hand $D(d(-, a_i), x)) = \max_j\{x_j - d_{j,i}\} \le x_i$ where the last inequality follows because $x \in P(\mathcal{L}) \iff x_j \le x_i + d_{j,i}$ which implies $x_j - d_{j,i} \le x_i$.

Moreover if $y \in \hat{P}(\mathcal{L})$ then $D^t(y, d(a_i, -)) \ge y_i - d(a_i, a_i) = y_i$

On the other hand

$D^t(y, d(a_i, -)) = \max_j\{y_j - d_{i,j}\} \le y_i$ since $y \in \hat{P}(\mathcal{L}) \iff y_j \le y_i + d_{i,j}$ which implies $y_j - d_{i,j} \le y_i$. $\square$

**Remark 12.** (1) We note that using the previous proposition, the defining inequalities, $x_i \le x_j + d_{i,j}$ of $P(\mathcal{L})$ become

$$ (51) \qquad D(Y(a_i), x) \le D(Y(a_i), Y(a_j)) + D(Y(a_j), x). $$

Namely they are triangle inequalities for maps $x : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$ and for the maps $Y(a_k) = d(-, a_k) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. Therefore we can think of $P(\mathcal{L})$ as the space of all maps $x = \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$ that satisfy the triangle inequalities for the metric $D$, with respect to all the maps $Y(a_k) = d(-, a_k) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. Thus $P(\mathcal{L})$ is a kind of convex metric span of the maps $Y(a_k) = d(-, a_k) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$.

(2) Analogously, the defining inequalities, $y_i \le y_j + d_{j,i}$ of $\hat{P}(\mathcal{L})$ become

$$ (52) \qquad D^t(y, \hat{Y}(a_i)) \le D^t(y, \hat{Y}(a_j)) + D^t(\hat{Y}(a_j), \hat{Y}(a_i)), $$

namely the triangle inequalities for maps $y : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. This implies that $\hat{P}(L)$ is the space of all maps $y = \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$ that satisfy the triangle inequalities for the metric $D^t$, with respect to all the maps $\hat{Y}(a_k) = d(a_k, -) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. Again we see $\hat{P}(L)$ as a kind of convex metric span of $\hat{Y}(a_k) = d(a_k, -)$

(3) A restatement of (51) is to say that the shortest path that connects $Y(a_i)$ and $x$ is at most as long as the shortest path that connects them but has to also go through $a_j$. Analogously for (52).

(4) Note that all constructions and results in this section work for a general directed metric space and not just for the special case of a probabilistic Language model

### 3.1. Texts define special Extremal rays of $P(\mathcal{L})$ and $Q(\mathcal{L})$.

**Definition 7.** An extremal ray of a polyhedral cone in $\mathbb{R}^n$ is a ray generated by a vector that cannot be expressed as a positive linear combination of two non-proportional vectors in the polyhedral cone.

Recall that a vector in a polyhedral cone in $\mathbb{R}^n$ generates an extremal ray if and only if it saturates $n-1$ linearly independent inequalities [17].

**Definition 8.** An additive extremal ray of $P(\mathcal{L})$ (respectively $\hat{P}(\mathcal{L})$) is defined to be the image under $-\log$ of a usual extremal ray of the polyhedral cone $Q(\mathcal{L})$ (respectively $\hat{Q}(\mathcal{L})$).

Note that the name additive extremal ray is chosen since a usual extremal ray in $Q(\mathcal{L})$ is invariant under scaling by $\lambda$ and therefore its image under $-\log$ is invariant under translation by $-\log \lambda$. Note that the extremal rays of $Q(\mathcal{L})$ and of $\hat{Q}(\mathcal{L})$ have generators which have in general some zero coordinates. Then, their $-\log$-images have vectors such that some of their coordinates are $\infty$, which is why we speak of
**Proof.** We have $D(d(-, a_i), x)) \ge x_i - d(a_i, a_i) = x_i$.

On the other hand $D(d(-, a_i), x)) = \max_j\{x_j - d_{j,i}\} \le x_i$ where the last inequality follows because $x \in P(\mathcal{L}) \iff x_j \le x_i + d_{j,i}$ which implies $x_j - d_{j,i} \le x_i$.

Moreover if $y \in \hat{P}(\mathcal{L})$ then $D^t(y, d(a_i, -)) \ge y_i - d(a_i, a_i) = y_i$

On the other hand

$D^t(y, d(a_i, -)) = \max_j\{y_j - d_{i,j}\} \le y_i$ since $y \in \hat{P}(\mathcal{L}) \iff y_j \le y_i + d_{i,j}$ which implies $y_j - d_{i,j} \le y_i$. $\square$

**Remark 12.** (1) We note that using the previous proposition, the defining inequalities, $x_i \le x_j + d_{i,j}$ of $P(\mathcal{L})$ become

$$ (51) \qquad D(Y(a_i), x) \le D(Y(a_i), Y(a_j)) + D(Y(a_j), x). $$

Namely they are triangle inequalities for maps $x : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$ and for the maps $Y(a_k) = d(-, a_k) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. Therefore we can think of $P(\mathcal{L})$ as the space of all maps $x = \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$ that satisfy the triangle inequalities for the metric $D$, with respect to all the maps $Y(a_k) = d(-, a_k) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. Thus $P(\mathcal{L})$ is a kind of convex metric span of the maps $Y(a_k) = d(-, a_k) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$.

(2) Analogously, the defining inequalities, $y_i \le y_j + d_{j,i}$ of $\hat{P}(\mathcal{L})$ become

$$ (52) \qquad D^t(y, \hat{Y}(a_i)) \le D^t(y, \hat{Y}(a_j)) + D^t(\hat{Y}(a_j), \hat{Y}(a_i)), $$

namely the triangle inequalities for maps $y : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. This implies that $\hat{P}(L)$ is the space of all maps $y = \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$ that satisfy the triangle inequalities for the metric $D^t$, with respect to all the maps $\hat{Y}(a_k) = d(a_k, -) : \mathcal{L} \to ((-\infty, \infty], d_{\mathbb{R}})$. Again we see $\hat{P}(L)$ as a kind of convex metric span of $\hat{Y}(a_k) = d(a_k, -)$

(3) A restatement of (51) is to say that the shortest path that connects $Y(a_i)$ and $x$ is at most as long as the shortest path that connects them but has to also go through $a_j$. Analogously for (52).

(4) Note that all constructions and results in this section work for a general directed metric space and not just for the special case of a probabilistic Language model

### 3.1. Texts define special Extremal rays of $P(\mathcal{L})$ and $Q(\mathcal{L})$.

**Definition 7.** An extremal ray of a polyhedral cone in $\mathbb{R}^n$ is a ray generated by a vector that cannot be expressed as a positive linear combination of two non-proportional vectors in the polyhedral cone.

Recall that a vector in a polyhedral cone in $\mathbb{R}^n$ generates an extremal ray if and only if it saturates $n-1$ linearly independent inequalities [17].

**Definition 8.** An additive extremal ray of $P(\mathcal{L})$ (respectively $\hat{P}(\mathcal{L})$) is defined to be the image under $-\log$ of a usual extremal ray of the polyhedral cone $Q(\mathcal{L})$ (respectively $\hat{Q}(\mathcal{L})$).

Note that the name additive extremal ray is chosen since a usual extremal ray in $Q(\mathcal{L})$ is invariant under scaling by $\lambda$ and therefore its image under $-\log$ is invariant under translation by $-\log \lambda$. Note that the extremal rays of $Q(\mathcal{L})$ and of $\hat{Q}(\mathcal{L})$ have generators which have in general some zero coordinates. Then, their $-\log$-images have vectors such that some of their coordinates are $\infty$, which is why we speak of
“additive extremal rays” of $P(\mathcal{L})$ and $\hat{P}(L)$ (they are not extremal rays in the usual sense).

From now on though we will simply refer to the additive extremal rays of $P(\mathcal{L})$ as extremal rays, when there is no chance of confusion.

We now define a directed graph associated to any point $x \in P(\mathcal{L})$ which encodes the saturated inequalities satisfied by the point $x$ and which we call its saturation graph $S(x)$.

**Definition 9.** Let $x \in P(\mathcal{L})$. Define $S(x)$, the saturation graph of $x$, to be the graph whose vertices are the elements of $\mathcal{L}$ and whose set of directed edges $E(x)$ is the set of saturated inequalities that coordinates of $x$ satisfy, namely $E(x) := \{(a_i, a_j) : x_i = x_j + d_{i,j}\}$. When $(a_i, a_j) \in E(x)$ we introduce a directed edge from $a_i$ to $a_j$.

The graph always contains trivial arcs $(a_i, a_i)$ (loops), for $i \in [n]$, since $d_{i,i} = 0$. It contains non-trivial arcs if and only if $x$ is on the boundary of $P$.

The graph $S(x)$ and in particular its support $\text{Supp}(x)$ encodes all the hyperplanes on which $x$ lies.

Note that the graph can be disconnected.

**Theorem 1.** The isometric embedding $Y : \mathcal{L} \hookrightarrow P(\mathcal{L})$, maps points of $\mathcal{L}$ to extremal rays of the polyhedron $P(\mathcal{L})$ namely $Y(a_k) = d(-, a_k)$ is an extremal ray in $P(\mathcal{L})$. Moreover the isometric embedding $\hat{Y} : \mathcal{L} \hookrightarrow \hat{P}(\mathcal{L})$, maps points of $\mathcal{L}$ to extremal rays of the polyhedron $\hat{P}(\mathcal{L})$ namely $\hat{Y}(a_k) = d(a_k, -)$ is an extremal ray in $\hat{P}(\mathcal{L})$.

*Proof.* We have $Y(a_k) := d(-, a_k)$, and therefore $Y(a_k)_i = d(a_i, a_k)$, $i = 1 \dots |\mathcal{L}|$. Define the support of $Y(a_k)$, $\text{Supp}(Y(a_k))$, to be the set of texts $a_i$ such that $Y(a_k)_i$ is finite. We recall that a vector in a cone in $\mathbb{R}^n$ defined by finitely many linear constraints generates an extreme ray of the cone if, and only if, the family of gradients of active constraints at this point is of rank $n-1$.

Let $x := Y(a_k)$, and $y \in Q(\mathcal{L})$ denote the image of $x$ by the map which applies $\exp(-\cdot)$ entrywise. Each edge $(a_i, a_j)$ of the saturation graph $S(Y(a_k))$ yields $x_i = d(a_i, a_j) + x_j$, and so the vector $y$ induces the active inequality $y_i = \text{Pr}(a_j|a_i)y_j$ with gradient $e_i - \text{Pr}(a_j|a_i)e_j$ where $e_i$ denotes the $i$th vector of the canonical basis of $\mathbb{R}^n$. Moreover, each text $a_i$ in $\mathcal{L}\text{Supp}(Y(a_k))$ yields the active inequality $y_i = 0$, with gradient $e_i$.

The saturation graph $S(Y(a_k))$ has a connected component which is a directed tree with $a_k$ as its root since $Y(a_k)_i = Y(a_k)_j + d_{i,j} \iff d(a_i, a_k) = d(a_i, a_j) + d(a_j, a_k)$ and from corollary 1 it follows that $a_i \le a_j \le a_k$, namely $a_j$ extends $a_i$ and $a_k$ extends $a_j$. It has also trivial connected components, reduced to loops at the vertices $a_i$ such that $a_i \notin \text{Supp}(Y(a_k))$. Using the fact that the non-trivial connected component of $S(Y(a_k)$ is a tree, we see that any vector $z$ satisfying the saturated equalities is uniquely defined by its value on the root of the tree. Hence, the space orthogonal to the family $e_i - \text{Pr}(a_j|a_i)e_i$ with $(i,j) \in S(y_k)$ and $e_l$ with $a_l \in \mathcal{L} \setminus \text{Supp}(Y(a_k))$ is of dimension one, which entails that this family is of rank $|\mathcal{L}| - 1$, showing that $y$ is an extreme ray of $Q(\mathcal{L})$.

Likewise let $\hat{Y}(a_k) := d(a_k, -)$ and $\hat{Y}(a_k)_i = d(a_k, a_i)$. If $a_k \le a_i \le a_j$ then $d(a_k, a_j) = d(a_k, a_i) + d(a_i, a_j)$, i.e. $\hat{Y}(a_k)_j = \hat{Y}(a_k)_i + d_{i,j}$.

The saturation graph for $\hat{Y}(a_k)$ is the same as for $Y(a_k)$ with all arrow reversed. Therefore the same proof applies. □
“additive extremal rays” of $P(\mathcal{L})$ and $\hat{P}(L)$ (they are not extremal rays in the usual sense).

*From now on though we will simply refer to the additive extremal rays of P($\mathcal{L}$) as extremal rays, when there is no chance of confusion.*

We now define a directed graph associated to any point $x \in P(\mathcal{L})$ which encodes
the saturated inequalities satisfied by the point $x$ and which we call its saturation
graph $S(x)$.

**Definition 9.** Let $x \in P(\mathcal{L})$. Define $S(x)$, the saturation graph of $x$, to be the graph whose vertices are the elements of $\mathcal{L}$ and whose set of directed edges $E(x)$ is the set of saturated inequalities that coordinates of $x$ satisfy, namely $E(x) := \{(a_i, a_j) : x_i = x_j + d_{i,j}\}$. When $(a_i, a_j) \in E(x)$ we introduce a directed edge from $a_i$ to $a_j$.

The graph always contains trivial arcs $(a_i, a_i)$ (loops), for $i \in [n]$, since $d_{i,i} = 0$. It contains non-trivial arcs if and only if $x$ is on the boundary of $P$.

The graph $S(x)$ and in particular its support $\text{Supp}(x)$ encodes all the hyperplanes
on which $x$ lies.

Note that the graph can be disconnected.

**Theorem 1.** The isometric embedding $Y : \mathcal{L} \hookrightarrow P(\mathcal{L})$, maps points of $\mathcal{L}$ to extremal rays of the polyhedron $P(\mathcal{L})$ namely $Y(a_k) = d(-, a_k)$ is an extremal ray in $P(\mathcal{L})$. Moreover the isometric embedding $\hat{Y} : \mathcal{L} \hookrightarrow \hat{P}(\mathcal{L})$, maps points of $\mathcal{L}$ to extremal rays of the polyhedron $\hat{P}(\mathcal{L})$ namely $\hat{Y}(a_k) = d(a_k, -)$ is an extremal ray in $\hat{P}(\mathcal{L})$.

*Proof.* We have $Y(a_k) := d(-, a_k)$, and therefore $Y(a_k)_i = d(a_i, a_k)$, $i = 1 \dots |\mathcal{L}|$. Define the support of $Y(a_k)$, $\text{Supp}(Y(a_k))$, to be the set of texts $a_i$ such that $Y(a_k)_i$ is finite. We recall that a vector in a cone in $\mathbb{R}^n$ defined by finitely many linear constraints generates an extreme ray of the cone if, and only if, the family of gradients of active constraints at this point is of rank $n-1$.

Let $x := Y(a_k)$, and $y \in Q(\mathcal{L})$ denote the image of $x$ by the map which applies $\exp(-\cdot)$ entrywise. Each edge $(a_i, a_j)$ of the saturation graph $S(Y(a_k))$ yields $x_i = d(a_i, a_j) + x_j$, and so the vector $y$ induces the active inequality $y_i = \text{Pr}(a_j|a_i)y_j$ with gradient $e_i - \text{Pr}(a_j|a_i)e_j$ where $e_i$ denotes the $i$th vector of the canonical basis of $\mathbb{R}^n$. Moreover, each text $a_i$ in $\mathcal{L}\setminus\text{Supp}(Y(a_k))$ yields the active inequality $y_i = 0$, with gradient $e_i$.

The saturation graph $S(Y(a_k))$ has a connected component which is a directed tree with $a_k$ as its root since $Y(a_k)_i = Y(a_k)_j + d_{i,j} \iff d(a_i, a_k) = d(a_i, a_j) + d(a_j, a_k)$ and from corollary 1 it follows that $a_i \le a_j \le a_k$, namely $a_j$ extends $a_i$ and $a_k$ extends $a_j$. It has also trivial connected components, reduced to loops at the vertices $a_i$ such that $a_i \notin \text{Supp}(Y(a_k))$. Using the fact that the non-trivial connected component of $S(Y(a_k)$ is a tree, we see that any vector $z$ satisfying the saturated equalities is uniquely defined by its value on the root of the tree. Hence, the space orthogonal to the family $e_i - \text{Pr}(a_j|a_i)e_i$ with $(i,j) \in S(y_k)$ and $e_l$ with $a_l \in \mathcal{L} \setminus \text{Supp}(Y(a_k))$ is of dimension one, which entails that this family is of rank $|\mathcal{L}| - 1$, showing that $y$ is an extreme ray of $Q(\mathcal{L})$.

Likewise let $\hat{Y}(a_k) := d(a_k, -)$ and $\hat{Y}(a_k)_i = d(a_k, a_i)$. If $a_k \le a_i \le a_j$ then $d(a_k, a_j) = d(a_k, a_i) + d(a_i, a_j)$, i.e. $\hat{Y}(a_k)_j = \hat{Y}(a_k)_i + d_{i,j}$.

The saturation graph for $\hat{Y}(a_k)$ is the same as for $Y(a_k)$ with all arrow reversed.
Therefore the same proof applies. □
It follows from Theorem 1, that we can identify the texts in $\mathcal{L}$ with some of the extremal rays of $P(\mathcal{L})$ and also with some of the extremal rays in $\hat{P}(\mathcal{L})$.

However there are many other extremal rays of $P(\mathcal{L})$, which we next characterize.

**3.2. All Extremal rays correspond to connected lower sets of $\mathcal{L}$**. Consider the equations $y_i \ge \mathrm{Pr}(a_j|a_i)y_j$ which define $Q(\mathcal{L})$. We denote $P_{i,j} := \mathrm{Pr}(a_j|a_i)$. If we assume that $a_0 \in \mathcal{L}$ is the empty text, we have $a_0 \le a_i \le a_j$ for any $a_i \le a_j$, and then $\mathrm{Pr}(a_j|a_0) = \mathrm{Pr}(a_i|a_0)\mathrm{Pr}(a_j|a_i)$.

$$ (53) \qquad \text{Define } P_i := \mathrm{Pr}(a_i|a_0) \text{ then } P_{i,j} = \frac{P_j}{P_i}. $$

Therefore $y_i \ge P_{i,j}y_j$ becomes $P_iy_i \ge P_jy_j$.

$$ (54) \qquad \text{Define } \tilde{y} = (\tilde{y}_1, \dots, \tilde{y}_n) \text{ where } \tilde{y}_i := P_i y_i. $$

Notice that this change of coordinates maps extremal rays to extremal rays. We get then a new polyhedral cone

$$ (55) \quad \tilde{Q}(\mathcal{L}) := \{\tilde{y} = (\tilde{y}_1, \dots, \tilde{y}_n) \in [0, \infty)^n \setminus \{(0, \dots, 0)\} \mid \tilde{y}_i \ge \tilde{y}_j \text{ whenever } a_i \le a_j\}. $$

Therefore $\tilde{Q}(\mathcal{L}) := \{\tilde{y} | y \in Q(\mathcal{L})\}$.

$\tilde{Q}(\mathcal{L})$ is a polyhedral cone variant of Stanley's order polytope for the opposite poset $\mathcal{L}^{\mathrm{op}}$ – the latter is the intersection of $\tilde{Q}(\mathcal{L})$ with the box $[0, 1]^n$ [18].

The change of variables mapping $Q(\mathcal{L})$ to $\tilde{Q}(\mathcal{L})$ can be also done under our more general assumption of a Probabilistic language model without assuming the existence of a global minimum $a_0 \in \mathcal{L}$. Indeed

**Proposition 6.** Let $(\mathcal{L}, \le, \mathrm{Pr})$ be a probabilistic language model then there is a diagonal change of variables mapping $Q(\mathcal{L})$ to $\tilde{Q}(\mathcal{L})$.

*Proof.* The fact that $(\mathcal{L}, \le, \mathrm{Pr})$ is a probabilistic language model means that
$$ a_i \le a_j \le a_k \text{ is equivalent to } \mathrm{Pr}(a_k|a_i) = \mathrm{Pr}(a_k|a_j)\mathrm{Pr}(a_j|a_i) \text{ and } \mathrm{Pr}(a_k|a_i) < \infty. $$

We define the directed graph $G$ whose nodes are the texts $a_1, \dots, a_n$. If $a_i \le a_j$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\mathrm{Pr}(a_j|a_i)$. If $a_j \le a_i$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\mathrm{Pr}(a_j|a_i)^{-1}$. Consider the Hasse diagram of $\mathcal{L}$. We make use of the observation in Proposition 2. For every connected component $C_m$, let us select arbitrarily an element $c_m$. If $a_i \in C_m$, we define $w_i$ to be the weight in the graph $G$ of an arbitrary path from the point $c_m$ to $a_i$. Owing to our main assumption, (1), the weight is independent of the choice of the path from $c_m$ to $a_i$. Moreover, for all $i, j$ such that $a_i \le a_j$, we have $w_i \mathrm{Pr}(a_j|a_i)w_j^{-1} = 1$. Setting $\tilde{y}_i = w_iy_i$, we rewrite the constraint $y_i \ge \mathrm{Pr}(a_j|a_i)y_j$ as $\tilde{y}_i \ge \tilde{y}_j$.

In this way, we transformed $Q(\mathcal{L})$ to $\tilde{Q}(\mathcal{L})$ by a diagonal scaling. $\square$

We then have the following

**Theorem 2.** The vector $\tilde{y} := (\tilde{y}_1, \dots, \tilde{y}_n) \in \tilde{Q}(\mathcal{L})$ generates an extremal ray of $\tilde{Q}(\mathcal{L})$ if and only if the function $a_i \mapsto \tilde{y}(a_i) := y_i$ is a positive scalar multiple of the characteristic function of a lower set in $\mathcal{L}$ whose Hasse diagram is connected.

*Proof.* Let $\{\lambda_1, \dots, \lambda_s\}$ be the distinct values taken by $\tilde{y}_i$, ordered so that $0 \le \lambda_1 < \lambda_2 < \dots < \lambda_s$. Let $\mathcal{L}_m = \{i | \tilde{y}_i = \lambda_m\}$.
It follows from Theorem 1, that we can identify the texts in $\mathcal{L}$ with some of the extremal rays of $P(\mathcal{L})$ and also with some of the extremal rays in $\hat{P}(\mathcal{L})$.

However there are many other extremal rays of $P(\mathcal{L})$, which we next characterize.

**3.2. All Extremal rays correspond to connected lower sets of $\mathcal{L}$**. Consider the equations $y_i \ge \mathrm{Pr}(a_j|a_i)y_j$ which define $Q(\mathcal{L})$. We denote $P_{i,j} := \mathrm{Pr}(a_j|a_i)$. If we assume that $a_0 \in \mathcal{L}$ is the empty text, we have $a_0 \le a_i \le a_j$ for any $a_i \le a_j$, and then $\mathrm{Pr}(a_j|a_0) = \mathrm{Pr}(a_i|a_0)\mathrm{Pr}(a_j|a_i)$.

$$ (53) \qquad \text{Define } P_i := \mathrm{Pr}(a_i|a_0) \text{ then } P_{i,j} = \frac{P_j}{P_i}. $$

Therefore $y_i \ge P_{i,j}y_j$ becomes $P_iy_i \ge P_jy_j$.

$$ (54) \qquad \text{Define } \tilde{y} = (\tilde{y}_1, \dots, \tilde{y}_n) \text{ where } \tilde{y}_i := P_i y_i. $$

Notice that this change of coordinates maps extremal rays to extremal rays. We get then a new polyhedral cone

$$ (55) \quad \tilde{Q}(\mathcal{L}) := \{\tilde{y} = (\tilde{y}_1, \dots, \tilde{y}_n) \in [0, \infty)^n \setminus \{(0, \dots, 0)\} \mid \tilde{y}_i \ge \tilde{y}_j \text{ whenever } a_i \le a_j\}. $$

Therefore $\tilde{Q}(\mathcal{L}) := \{\tilde{y} | y \in Q(\mathcal{L})\}$.

$\tilde{Q}(\mathcal{L})$ is a polyhedral cone variant of Stanley's order polytope for the opposite poset $\mathcal{L}^{\mathrm{op}}$ – the latter is the intersection of $\tilde{Q}(\mathcal{L})$ with the box $[0, 1]^n$ [18].

The change of variables mapping $Q(\mathcal{L})$ to $\tilde{Q}(\mathcal{L})$ can be also done under our more general assumption of a Probabilistic language model without assuming the existence of a global minimum $a_0 \in \mathcal{L}$. Indeed

**Proposition 6.** Let $(\mathcal{L}, \le, \mathrm{Pr})$ be a probabilistic language model then there is a diagonal change of variables mapping $Q(\mathcal{L})$ to $\tilde{Q}(\mathcal{L})$.

*Proof.* The fact that $(\mathcal{L}, \le, \mathrm{Pr})$ is a probabilistic language model means that
$$ a_i \le a_j \le a_k \text{ is equivalent to } \mathrm{Pr}(a_k|a_i) = \mathrm{Pr}(a_k|a_j)\mathrm{Pr}(a_j|a_i) \text{ and } \mathrm{Pr}(a_k|a_i) < \infty. $$

We define the directed graph $G$ whose nodes are the texts $a_1, \dots, a_n$. If $a_i \le a_j$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\mathrm{Pr}(a_j|a_i)$. If $a_j \le a_i$, we draw an arrow from node $a_i$ to node $a_j$ with weight $\mathrm{Pr}(a_j|a_i)^{-1}$. Consider the Hasse diagram of $\mathcal{L}$. We make use of the observation in Proposition 2. For every connected component $C_m$, let us select arbitrarily an element $c_m$. If $a_i \in C_m$, we define $w_i$ to be the weight in the graph $G$ of an arbitrary path from the point $c_m$ to $a_i$. Owing to our main assumption, (1), the weight is independent of the choice of the path from $c_m$ to $a_i$. Moreover, for all $i, j$ such that $a_i \le a_j$, we have $w_i \mathrm{Pr}(a_j|a_i)w_j^{-1} = 1$. Setting $\tilde{y}_i = w_iy_i$, we rewrite the constraint $y_i \ge \mathrm{Pr}(a_j|a_i)y_j$ as $\tilde{y}_i \ge \tilde{y}_j$.

In this way, we transformed $Q(\mathcal{L})$ to $\tilde{Q}(\mathcal{L})$ by a diagonal scaling. $\square$

We then have the following

**Theorem 2.** The vector $\tilde{y} := (\tilde{y}_1, \dots, \tilde{y}_n) \in \tilde{Q}(\mathcal{L})$ generates an extremal ray of $\tilde{Q}(\mathcal{L})$ if and only if the function $a_i \mapsto \tilde{y}(a_i) := y_i$ is a positive scalar multiple of the characteristic function of a lower set in $\mathcal{L}$ whose Hasse diagram is connected.

*Proof.* Let $\{\lambda_1, \dots, \lambda_s\}$ be the distinct values taken by $\tilde{y}_i$, ordered so that $0 \le \lambda_1 < \lambda_2 < \dots < \lambda_s$. Let $\mathcal{L}_m = \{i | \tilde{y}_i = \lambda_m\}$.
We define the rank of a family of affine inequalities to be the rank of the family of gradients of the affine forms defining these inequalities. For $\tilde{y}$ to be an extremal ray it has to saturate a family of inequalities of rank $n-1$, where $|\mathcal{L}| = n$, see [17].

Let us first assume $\lambda_1 = 0$. The rank of the family of saturated constraints given by $\mathcal{L}_1$ is then $r_1 = |\mathcal{L}_1|$ since we get equations of the form $\tilde{y}_i = 0$ which is a hyperplane normal to $e_i$ for $i \in \mathcal{L}_1$.

Moreover, we claim that the rank $r_k$ of the family of saturated constraints given by any $\mathcal{L}_k$ for $k \neq 1$ given by $r_k = |\mathcal{L}_k| - c_k$ where $c_k$ is the number of connected components of the Hasse diagram of $(\mathcal{L}_k, \leq)$. To see this, it suffices to observe that a solution $h \in \mathbb{R}^{\mathcal{L}_k}$ of the system of saturated inequalities $h_i = h_j$ for $a_i \leq a_j$ and $a_i, a_j \in \mathcal{L}_k$ is uniquely determined by fixing precisely one coordinate of $h$ on every connected component of the Hasse diagram (in other words, we have $c_k$ degrees of freedom for the choice of $h$).

Therefore the rank of the family of saturated constraints at the point $\tilde{y}$ is less than or equal to $|\mathcal{L}_1| + |\mathcal{L}_2| - 1 + \cdots + |\mathcal{L}_s| - 1$. We also have that $|\mathcal{L}_1| + |\mathcal{L}_2| + \cdots + |\mathcal{L}_s| = n$. We know though that $\tilde{y}$ is an extremal ray if and only if the rank of the family of saturated constraints is $n-1$. Therefore we must have $n-1 \leq |\mathcal{L}_1| + (|\mathcal{L}_2| - 1) + \cdots + (|\mathcal{L}_s| - 1) = n-s+1$.

This is only possible if $s \leq 2$ but, for $\tilde{y}$ to generate an extremal ray, not all coordinates of $\tilde{y}$ can be 0, and then our assumption $\lambda_1 = 0$ excludes the case $s = 1$. This entails that $s \geq 2$ and therefore $s = 2$. We then have $n-1 = |\mathcal{L}_1| + |\mathcal{L}_2| - 1$. In that case $\tilde{y}_i = 0$ for $i \in \mathcal{L}_1$ and $\tilde{y}_j = \lambda_2$ for $j \in \mathcal{L}_2$. We then scale $\tilde{y}$ by $\frac{1}{\lambda_2}$ so as to get a representative vector of the same the ray with $\tilde{y}_i = 0$ for $i \in \mathcal{L}_1$ and $\tilde{y}_j = 1$ for $j \in \mathcal{L}_2$. Therefore $\tilde{y}$ is the characteristic function of $\mathcal{L}_2$.

Moreover $\mathcal{L}_2$ is a lower set. Indeed if $a_j \in \mathcal{L}_2$ and $a_i \leq a_j$ then $a_i \in \mathcal{L}_2$. This holds because $a_j \in \mathcal{L}_2$ implies $\tilde{y}(a_j) = 1$ and $a_i \leq a_j$ implies $\tilde{y}(a_i) = \tilde{y}(a_j) = 1$ therefore $a_i \in \mathcal{L}_2$.

If now $\lambda_1 > 0$ then $n-1 \leq (|\mathcal{L}_1| - 1) + (|\mathcal{L}_2| - 1) + \cdots + (|\mathcal{L}_s| - 1) = n-s$ therefore $s \leq 1$ which implies $s = 1$ and $|\mathcal{L}_1| = n$. In that case we have a single extremal ray $\tilde{y} = (1, 1, \dots, 1)$ which is the characteristic function of the maximal lower set $\mathcal{L}_1 = \mathcal{L}$.

Conversely let $C$ be a lower set in $\mathcal{L}$ and let $\tilde{y} : \mathcal{L} \to \{0, 1\}$ be the characteristic function of $U$. Consider $a_j \in U$ then $\tilde{y}(a_j) = 1$. Now if $a_i \leq a_j$ then $a_i \in U$ and therefore $\tilde{y}(a_i) = 1$ which means $\tilde{y}(a_j) = \tilde{y}(a_i)$.

□

**Remark 13.** Note that if $\mathcal{L}$ admits a bottom element $a_0$ then any lower set is connected since it must include $a_0$, and the Hasse diagram of $\mathcal{L}$ contains a path from $a_0$ to every element of $\mathcal{L}$.

Notice that Stanley in [18] has proven that vertices of his order polytope correspond to upper sets. In contrast, rays of $Q(\mathcal{L})$ correspond only to *connected* lower sets. Notwithstanding the order reversal, there is a discrepancy which arises because Stanley considers the intersection of $Q(\mathcal{L})$ with a box, with creates additional vertices, not associated to rays of $Q(\mathcal{L})$.

**Remark 14.** Note that a vector $Y(a_k) \in P(\mathcal{L})$ corresponds to the principal lower set generated by $a_k$. We will therefore call the extremal rays generated by images of the Yoneda embedding, *principal extremal rays*.
We define the rank of a family of affine inequalities to be the rank of the family of gradients of the affine forms defining these inequalities. For $\tilde{y}$ to be an extremal ray it has to saturate a family of inequalities of rank $n-1$, where $|\mathcal{L}| = n$, see [17].

Let us first assume $\lambda_1 = 0$. The rank of the family of saturated constraints given by $\mathcal{L}_1$ is then $r_1 = |\mathcal{L}_1|$ since we get equations of the form $\tilde{y}_i = 0$ which is a hyperplane normal to $e_i$ for $i \in \mathcal{L}_1$.

Moreover, we claim that the rank $r_k$ of the family of saturated constraints given by any $\mathcal{L}_k$ for $k \neq 1$ given by $r_k = |\mathcal{L}_k| - c_k$ where $c_k$ is the number of connected components of the Hasse diagram of $(\mathcal{L}_k, \leq)$. To see this, it suffices to observe that a solution $h \in \mathbb{R}^{\mathcal{L}_k}$ of the system of saturated inequalities $h_i = h_j$ for $a_i \leq a_j$ and $a_i, a_j \in \mathcal{L}_k$ is uniquely determined by fixing precisely one coordinate of $h$ on every connected component of the Hasse diagram (in other words, we have $c_k$ degrees of freedom for the choice of $h$).

Therefore the rank of the family of saturated constraints at the point $\tilde{y}$ is less than or equal to $|\mathcal{L}_1| + |\mathcal{L}_2| - 1 + \dots + |\mathcal{L}_s| - 1$. We also have that $|\mathcal{L}_1| + |\mathcal{L}_2| + \dots + |\mathcal{L}_s| = n$. We know though that $\tilde{y}$ is an extremal ray if and only if the rank of the family of saturated constraints is $n-1$. Therefore we must have $n-1 \leq |\mathcal{L}_1| + (|\mathcal{L}_2| - 1) + \dots + (|\mathcal{L}_s| - 1) = n-s+1$.

This is only possible if $s \leq 2$ but, for $\tilde{y}$ to generate an extremal ray, not all coordinates of $\tilde{y}$ can be 0, and then our assumption $\lambda_1 = 0$ excludes the case $s = 1$. This entails that $s \geq 2$ and therefore $s = 2$. We then have $n-1 = |\mathcal{L}_1| + |\mathcal{L}_2| - 1$. In that case $\tilde{y}_i = 0$ for $i \in \mathcal{L}_1$ and $\tilde{y}_j = \lambda_2$ for $j \in \mathcal{L}_2$. We then scale $\tilde{y}$ by $\frac{1}{\lambda_2}$ so as to get a representative vector of the same the ray with $\tilde{y}_i = 0$ for $i \in \mathcal{L}_1$ and $\tilde{y}_j = 1$ for $j \in \mathcal{L}_2$. Therefore $\tilde{y}$ is the characteristic function of $\mathcal{L}_2$.

Moreover $\mathcal{L}_2$ is a lower set. Indeed if $a_j \in \mathcal{L}_2$ and $a_i \leq a_j$ then $a_i \in \mathcal{L}_2$. This holds because $a_j \in \mathcal{L}_2$ implies $\tilde{y}(a_j) = 1$ and $a_i \leq a_j$ implies $\tilde{y}(a_i) = \tilde{y}(a_j) = 1$ therefore $a_i \in \mathcal{L}_2$.

If now $\lambda_1 > 0$ then $n-1 \leq (|\mathcal{L}_1| - 1) + (|\mathcal{L}_2| - 1) + \dots + (|\mathcal{L}_s| - 1) = n-s$ therefore $s \leq 1$ which implies $s = 1$ and $|\mathcal{L}_1| = n$. In that case we have a single extremal ray $\tilde{y} = (1, 1, \dots, 1)$ which is the characteristic function of the maximal lower set $\mathcal{L}_1 = \mathcal{L}$.

Conversely let $C$ be a lower set in $\mathcal{L}$ and let $\tilde{y} : \mathcal{L} \to \{0, 1\}$ be the characteristic function of $U$. Consider $a_j \in U$ then $\tilde{y}(a_j) = 1$. Now if $a_i \leq a_j$ then $a_i \in U$ and therefore $\tilde{y}(a_i) = 1$ which means $\tilde{y}(a_j) = \tilde{y}(a_i)$.

□

**Remark 13.** Note that if $\mathcal{L}$ admits a bottom element $a_0$ then any lower set is connected since it must include $a_0$, and the Hasse diagram of $\mathcal{L}$ contains a path from $a_0$ to every element of $\mathcal{L}$.

Notice that Stanley in [18] has proven that vertices of his order polytope correspond to upper sets. In contrast, rays of $Q(\mathcal{L})$ correspond only to *connected* lower sets. Notwithstanding the order reversal, there is a discrepancy which arises because Stanley considers the intersection of $Q(\mathcal{L})$ with a box, with creates additional vertices, not associated to rays of $Q(\mathcal{L})$.

**Remark 14.** Note that a vector $Y(a_k) \in P(\mathcal{L})$ corresponds to the principal lower set generated by $a_k$. We will therefore call the extremal rays generated by images of the Yoneda embedding, *principal extremal rays*.
**Corollary 3.** Assume $\mathcal{L}$ includes the bottom element $a_0$ and recall from (53) that $P_i := \text{Pr}(a_i|a_0)$. If $C$ is a lower set, the extremal ray corresponding to $C$ is generated by $y$ in $Q(\mathcal{L})$ with coordinates

$$ (56) \qquad y_i = \begin{cases} \frac{1}{P_i} & \text{if } a_i \in C, \\ 0 & \text{if } a_i \text{ not in } C. \end{cases} $$

*Proof.* It follows from Theorem 2 and the change of coordinates $\tilde{y}_i = P_i y_i$ in eq (53). $\square$

**Remark 15.** Notice that Corollary 3 is consistent with the coordinates of an extremal ray $y$ in $Q(\mathcal{L})$, corresponding to a text $a_j \in \mathcal{L}$. Indeed according to corollary 2, any element $y$ on the extremal ray has $y_i = \frac{\lambda}{P_i}$ for $\lambda \in [0, \infty)$. We also have $y_j = \text{Pr}(a_j|a_j) = 1$, therefore $\lambda = P_j$. This implies $y_i = \frac{P_j}{P_i} = \text{Pr}(a_j|a_i)$

$$ (57) \qquad y_i = \begin{cases} \text{Pr}(a_j|a_i) & \text{if } a_i \le a_j, \\ 0 & \text{if } a_i \text{ not a subtext of } a_j. \end{cases} $$

Now we want a general version of the Corollary 3.

For any subset $C$ of $\mathcal{L}$, selecting an element $c \in C$, for every element $a_i$ in the connected component of $C$ in the graph induced by the Hasse diagram of $\mathcal{L}$, we denote by $w_i^c$ the weight of any path from $c$ to $a_i$ in the directed graph constructed in the proof of Proposition 6.

**Proposition 7.** Let $C$ be a connected lower set of the Hasse diagram of $(\mathcal{L}, \le)$. Let $c$ denote any element of $C$. Then, the vector

$$ (58) \qquad y_i = \frac{1}{w_i^c}, \quad \text{for } a_i \in C, \quad y_i = 0 \text{ for } a_i \in \mathcal{L} \setminus \{C\} $$

generates an extreme ray of $Q(\mathcal{L})$, and all the extreme rays arise in this way.

*Proof.* We showed in Theorem 2 that $\tilde{y}$ is a positive scalar multiple of the characteristic function of $C$. If $a_i$ belongs to $C$, we have $y_i = (w_i^c)^{-1}\tilde{y}_i$, from which (58) follows. We note that a change of the reference point $c$ in $C$ only modifies the vector $w^c$ by a positive scalar multiple. Indeed, for all $c$ and $c' \in C$, we have $w^c = \mu w^{c'}$ where $\mu$ is the weight of any path from $c$ to $c'$ in the directed graph $G$. $\square$

**Proposition 8.** If $y$ generates an extremal ray of $Q(\mathcal{L})$ corresponding to a lower set $C$ in $\mathcal{L}$ then the saturation graph of $y$ has an edge from $a_i$ to $a_j$ if and only if $a_i \le a_j$ for $a_i, a_j \in C$.

*Proof.* This follows from (58), using the main assumption (1). Indeed if $a_i \le a_j$ in $C$ then we have $y_i = \frac{1}{w_i^c}$ and $y_j = \frac{1}{w_j^c}$. Therefore $y_i = \frac{w_i^c}{w_i^c}y_j$ and therefore $y_i = \text{Pr}(a_j|a_i)y_j$ which means that there is an edge from $a_i$ to $a_j$ in the saturation graph of $y$. $\square$

**Corollary 4.** Extremal rays of $\hat{Q}(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ correspond to connected upper sets of $\mathcal{L}$.

*Proof.* We have $\hat{Q}(\mathcal{L}) = Q(\mathcal{L}^{\text{op}})$ and upper sets of $\mathcal{L}$ correspond to lower sets of $\mathcal{L}^{\text{op}}$ therefore the result follows from Proposition 7. $\square$
**Corollary 3.** Assume $\mathcal{L}$ includes the bottom element $a_0$ and recall from (53) that $P_i := \text{Pr}(a_i|a_0)$. If $C$ is a lower set, the extremal ray corresponding to $C$ is generated by $y$ in $Q(\mathcal{L})$ with coordinates

$$ (56) \qquad y_i = \begin{cases} \frac{1}{P_i} & \text{if } a_i \in C, \\ 0 & \text{if } a_i \text{ not in } C. \end{cases} $$

*Proof.* It follows from Theorem 2 and the change of coordinates $\tilde{y}_i = P_i y_i$ in eq (53). $\square$

**Remark 15.** Notice that Corollary 3 is consistent with the coordinates of an extremal ray $y$ in $Q(\mathcal{L})$, corresponding to a text $a_j \in \mathcal{L}$. Indeed according to corollary 2, any element $y$ on the extremal ray has $y_i = \frac{\lambda}{P_i}$ for $\lambda \in [0, \infty)$. We also have $y_j = \text{Pr}(a_j|a_j) = 1$, therefore $\lambda = P_j$. This implies $y_i = \frac{P_j}{P_i} = \text{Pr}(a_j|a_i)$

$$ (57) \qquad y_i = \begin{cases} \text{Pr}(a_j|a_i) & \text{if } a_i \le a_j, \\ 0 & \text{if } a_i \text{ not a subtext of } a_j. \end{cases} $$

Now we want a general version of the Corollary 3.

For any subset $C$ of $\mathcal{L}$, selecting an element $c \in C$, for every element $a_i$ in the connected component of $C$ in the graph induced by the Hasse diagram of $\mathcal{L}$, we denote by $w_i^c$ the weight of any path from $c$ to $a_i$ in the directed graph constructed in the proof of Proposition 6.

**Proposition 7.** Let $C$ be a connected lower set of the Hasse diagram of $(\mathcal{L}, \le)$. Let $c$ denote any element of $C$. Then, the vector

$$ (58) \qquad y_i = \frac{1}{w_i^c}, \quad \text{for } a_i \in C, \quad y_i = 0 \text{ for } a_i \in \mathcal{L} \setminus \{C\} $$

generates an extreme ray of $Q(\mathcal{L})$, and all the extreme rays arise in this way.

*Proof.* We showed in Theorem 2 that $\tilde{y}$ is a positive scalar multiple of the characteristic function of $C$. If $a_i$ belongs to $C$, we have $y_i = (w_i^c)^{-1}\tilde{y}_i$, from which (58) follows. We note that a change of the reference point $c$ in $C$ only modifies the vector $w^c$ by a positive scalar multiple. Indeed, for all $c$ and $c' \in C$, we have $w^c = \mu w^{c'}$ where $\mu$ is the weight of any path from $c$ to $c'$ in the directed graph $G$. $\square$

**Proposition 8.** If $y$ generates an extremal ray of $Q(\mathcal{L})$ corresponding to a lower set $C$ in $\mathcal{L}$ then the saturation graph of $y$ has an edge from $a_i$ to $a_j$ if and only if $a_i \le a_j$ for $a_i, a_j \in C$.

*Proof.* This follows from (58), using the main assumption (1). Indeed if $a_i \le a_j$ in $C$ then we have $y_i = \frac{1}{w_i^c}$ and $y_j = \frac{1}{w_j^c}$. Therefore $y_i = \frac{w_i^c}{w_i^c}y_j$ and therefore $y_i = \text{Pr}(a_j|a_i)y_j$ which means that there is an edge from $a_i$ to $a_j$ in the saturation graph of $y$. $\square$

**Corollary 4.** Extremal rays of $\hat{Q}(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ correspond to connected upper sets of $\mathcal{L}$.

*Proof.* We have $\hat{Q}(\mathcal{L}) = Q(\mathcal{L}^{\text{op}})$ and upper sets of $\mathcal{L}$ correspond to lower sets of $\mathcal{L}^{\text{op}}$ therefore the result follows from Proposition 7. $\square$
**Remark 16.** Note that Proposition 6, and Theorem 2 are only valid for a probabilistic language model and not for general directed metric space. In the latter case there will still be exponentially many extremal rays not coming from the Yoneda embedding, but we the characterization in terms of connected lower sets no longer holds.

**Corollary 5.** If the empty text $a_0$ is in $\mathcal{L}$ then the set $P^0(\mathcal{L})$ of extremal rays of $P(\mathcal{L})$ is identified with the lower set completion of the poset $\mathcal{L}$.

*Proof.* Since $a_0 \in \mathcal{L}$, every lower set of $\mathcal{L}$ is connected so $P^0(\mathcal{L})$ is identified with the set of lower sets of $\mathcal{L}$.

□

**Remark 17.** Note that having explicit equations for the polyhedral cone $Q(\mathcal{L})$, the extremal rays of $Q(\mathcal{L})$ can be computed, for instance by the double description method [6].

### 4. THE POLYHEDRON $P(\mathcal{L})$ AS A $(\min, +)$ LINEAR SPACE

To further understand the polyhedra $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ we need to consider their description in terms of tropical algebra.

Consider the metric space $(\mathcal{L}, d)$. Recall the $(\min, +)$ (tropical) semifield $\mathbb{R}_{\min}$ defined as $\mathbb{R}_{\min} := ((-\infty, \infty], \oplus_{\min}, \odot)$ where for $s, t \in (-\infty, \infty]$,

$$ (59) \qquad s \oplus_{\min} t := \min\{s, t\} \quad \text{and} \quad s \odot t := s + t. $$

We denote by $d_{\min}: \mathbb{R}^n \to \mathbb{R}^n$ the $(\min, +)$ linear operator defined by

$$ (60) \qquad d_{\min}(x)_i := \min_j \{d_{i,j} + x_j\} $$

**Proposition 9.** $(\mathcal{L}, d)$ is a directed metric if and only if $d_{\min}^2 = d_{\min}$, namely $d_{\min}$ is a $(\min, +)$ projector.

*Proof.* We have $d_{\min}^2 = d_{\min} \iff d_{i,k} = \min_j \{d_{i,j} + d_{j,k}\}$ which is the same as the triangle inequality $d_{i,k} \le d_{i,j} + d_{j,k}$. □

Let us denote $\text{Im}(d_{\min})$, the image of $d_{\min}$, namely the $(\min, +)$ column span of $d$.

**Lemma 1.** We have $\text{Im}(d_{\min}) = \text{Fix}(d_{\min})$, where $\text{Fix}(d_{\min})$ is the $(\min, +)$ module $\text{Fix}(d_{\min}) := \{x : d_{\min}(x) = x\}$.

*Proof.* It follows from $d_{\min}^2 = d_{\min}$. □

We note now that there is a very natural description of our polyhedra as follows:

**Proposition 10.** The polyhedron $P(\mathcal{L})$ is equal to $\text{Im}(d_{\min}) = \text{Fix}(d_{\min})$ and the polyhedron $\hat{P}(\mathcal{L})$ is equal to $\text{Im}(d_{\min}^t) = \text{Fix}(d_{\min}^t)$.

*Proof.* Since $d_{\min}^2 = d_{\min}$ we have that $x \in \text{Im}(d_{\min}) \iff d_{\min}x = x$ which means that $x_i = \min_j \{d_{i,j} + x_j\}$ and thus $x_i \le x_j + d_{i,j}$. Likewise for $\text{Im}(d_{\min}^t)$ we get $x_i \le x_j + d_{j,i}$. □

Since we use much more often the $(\min, +)$ semifield than the $(\max, +)$ that will appear later on, to simplify notation we denote $\oplus_{\min}$ by $\oplus$.

In particular we introduce the notation, for $u, v \in \mathbb{R}^n$, $(u \oplus v)_i := \min\{u_i, v_i\}$. We then have
**Remark 16.** Note that Proposition 6, and Theorem 2 are only valid for a probabilistic language model and not for general directed metric space. In the latter case there will still be exponentially many extremal rays not coming from the Yoneda embedding, but we the characterization in terms of connected lower sets no longer holds.

**Corollary 5.** If the empty text $a_0$ is in $\mathcal{L}$ then the set $P^0(\mathcal{L})$ of extremal rays of $P(\mathcal{L})$ is identified with the lower set completion of the poset $\mathcal{L}$.

*Proof.* Since $a_0 \in \mathcal{L}$, every lower set of $\mathcal{L}$ is connected so $P^0(\mathcal{L})$ is identified with the set of lower sets of $\mathcal{L}$.

<figure><img src="image_4.png" /></figure>

**Remark 17.** Note that having explicit equations for the polyhedral cone $Q(\mathcal{L})$, the extremal rays of $Q(\mathcal{L})$ can be computed, for instance by the double description method [6].

### 4. THE POLYHEDRON $P(\mathcal{L})$ AS A $(\min, +)$ LINEAR SPACE

To further understand the polyhedra $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ we need to consider their description in terms of tropical algebra.

Consider the metric space $(\mathcal{L}, d)$. Recall the $(\min, +)$ (tropical) semifield $\mathbb{R}_{\min}$ defined as $\mathbb{R}_{\min} := ((-\infty, \infty], \oplus_{\min}, \odot)$ where for $s, t \in (-\infty, \infty]$,

$$ (59) \qquad s \oplus_{\min} t := \min\{s, t\} \quad \text{and} \quad s \odot t := s + t. $$

We denote by $d_{\min} : \mathbb{R}^n \to \mathbb{R}^n$ the $(\min, +)$ linear operator defined by

$$ (60) \qquad d_{\min}(x)_i := \min_j \{d_{i,j} + x_j\} $$

**Proposition 9.** $(\mathcal{L}, d)$ is a directed metric if and only if $d_{\min}^2 = d_{\min}$, namely $d_{\min}$ is a $(\min, +)$ projector.

*Proof.* We have $d_{\min}^2 = d_{\min} \iff d_{i,k} = \min_j \{d_{i,j} + d_{j,k}\}$ which is the same as the triangle inequality $d_{i,k} \le d_{i,j} + d_{j,k}$. $\square$

<figure><img src="image_5.png" /></figure>

Let us denote $\text{Im}(d_{\min})$, the image of $d_{\min}$, namely the $(\min, +)$ column span of $d$.

**Lemma 1.** We have $\text{Im}(d_{\min}) = \text{Fix}(d_{\min})$, where $\text{Fix}(d_{\min})$ is the $(\min, +)$ module $\text{Fix}(d_{\min}) := \{x : d_{\min}(x) = x\}$.

*Proof.* It follows from $d_{\min}^2 = d_{\min}$. $\square$

<figure><img src="image_6.png" /></figure>

We note now that there is a very natural description of our polyhedra as follows:

**Proposition 10.** The polyhedron $P(\mathcal{L})$ is equal to $\text{Im}(d_{\min}) = \text{Fix}(d_{\min})$ and the polyhedron $\hat{P}(\mathcal{L})$ is equal to $\text{Im}(d_{\min}^t) = \text{Fix}(d_{\min}^t)$.

*Proof.* Since $d_{\min}^2 = d_{\min}$ we have that $x \in \text{Im}(d_{\min}) \iff d_{\min}x = x$ which means that $x_i = \min_j \{d_{i,j} + x_j\}$ and thus $x_i \le x_j + d_{i,j}$. Likewise for $\text{Im}(d_{\min}^t)$ we get $x_i \le x_j + d_{j,i}$. $\square$

<figure><img src="image_7.png" /></figure>

Since we use much more often the $(\min, +)$ semifield than the $(\max, +)$ that will appear later on, to simplify notation we denote $\oplus_{\min}$ by $\oplus$.

In particular we introduce the notation, for $u, v \in \mathbb{R}^n$, $(u \oplus v)_i := \min\{u_i, v_i\}$. We then have
**Corollary 6.** If $x \in P(\mathcal{L})$ then

$$ (61) \qquad x = \bigoplus_j D(Y(a_j), x) \odot Y(a_j). $$

*Proof.* From Proposition 10, $x \in P(\mathcal{L}) = \text{Im}(d_{\min}) = \text{Fix}(d_{\min}) \iff d_{\min}(x) = x$. Therefore we have the $(\min, +)$ linear expression for $x$ in terms of the columns of $d$:

$$ x = \bigoplus_j x_j \odot d(-, a_j) = \bigoplus_j x_j \odot Y(a_j) = \bigoplus_j D(Y(a_j), x) \odot Y(a_j). \quad \square $$

It is known that an order polytope, and more generally, an alcoved polytope (of $A_n$ type) is closed under min and max, (61) expresses this fact for our metric case for min. In Proposition 29 we will see that $P(\mathcal{L})$ is also closed under max.

**Proposition 11.** We have

$$ (62) \qquad Y(a_k) = \bigoplus_{a_j \le a_k} d_{j,k} \odot Y(a_j) $$

and

$$ (63) \qquad \hat{Y}(a_k) = \bigoplus_{a_k \le a_l} d_{k,l} \odot \hat{Y}(a_l) $$

*Proof.* The fact that $d_{\min}^2 = d_{\min}$ is equivalent to

$$ (64) \qquad d_{i,k} = \min_j \{d_{i,j} + d_{j,k}\}. $$

We have $Y(a_k) := d(-, a_k)$ and $Y(a_j) := d(-, a_j)$ therefore eq. 64 implies

$$ Y(a_k)_i = \bigoplus_j d_{j,k} \odot Y(a_j)_i $$

which means

$$ Y(a_k) = \bigoplus_j d_{j,k} \odot Y(a_j) $$

Since $d_{j,k} = \infty$ unless $a_j \le a_k$ we have

$$ Y(a_k) = \bigoplus_{a_j \le a_k} d_{j,k} \odot Y(a_j) $$

Analogously for $d^t$ we have $d_{i,k}^t = \min_l \{d_{i,l}^t + d_{l,k}^t\} \iff d_{k,i} = \min_l \{d_{k,l} + d_{l,i}\}$. Recall that $\hat{Y}(a_k) := d(a_k, -)$ and $\hat{Y}(a_l) := d(a_l, -)$. This implies

$$ \hat{Y}(a_k) = \bigoplus_l d_{k,l} \odot \hat{Y}(a_l). $$

Since $d_{k,l} = \infty$ unless $a_k \le a_l$ we have

$$ \hat{Y}(a_k) = \bigoplus_{a_k \le a_l} d_{k,l} \odot \hat{Y}(a_l). \quad \square $$

Finally we have the following

**Proposition 12.** The Funk metric $D(x, y) := \max_i\{y_i - x_i|x_i \ne \infty\}$ has the property that $D(-, w)$ is tropically antilinear, namely

$$ (65) \qquad D(\lambda_1 \odot x \oplus_{\min} \lambda_2 \odot y, z) = -\lambda_1 \odot D(x, z) \oplus_{\max} -\lambda_2 \odot D(y, z) $$

while $D(w, -)$ is linear, namely

$$ (66) \qquad D(x, \lambda_1 \odot y \oplus_{\max} \lambda_2 \odot z) = \lambda_1 \odot D(x, z) \oplus_{\max} \lambda_2 \odot D(y, z). $$
**Corollary 6.** If $x \in P(\mathcal{L})$ then

$$ (61) \qquad x = \bigoplus_j D(Y(a_j), x) \odot Y(a_j). $$

*Proof.* From Proposition 10, $x \in P(\mathcal{L}) = \text{Im}(d_{\min}) = \text{Fix}(d_{\min}) \iff d_{\min}(x) = x$. Therefore we have the $(\min, +)$ linear expression for $x$ in terms of the columns of $d$:

$$ x = \bigoplus_j x_j \odot d(-, a_j) = \bigoplus_j x_j \odot Y(a_j) = \bigoplus_j D(Y(a_j), x) \odot Y(a_j). \quad \square $$

It is known that an order polytope, and more generally, an alcoved polytope (of $A_n$ type) is closed under min and max, (61) expresses this fact for our metric case for min. In Proposition 29 we will see that $P(\mathcal{L})$ is also closed under max.

**Proposition 11.** We have

$$ (62) \qquad Y(a_k) = \bigoplus_{a_j \le a_k} d_{j,k} \odot Y(a_j) $$

and

$$ (63) \qquad \hat{Y}(a_k) = \bigoplus_{a_k \le a_l} d_{k,l} \odot \hat{Y}(a_l) $$

*Proof.* The fact that $d_{\min}^2 = d_{\min}$ is equivalent to

$$ (64) \qquad d_{i,k} = \min_j \{d_{i,j} + d_{j,k}\}. $$

We have $Y(a_k) := d(-, a_k)$ and $Y(a_j) := d(-, a_j)$ therefore eq. 64 implies

$$ Y(a_k)_i = \bigoplus_j d_{j,k} \odot Y(a_j)_i $$

which means

$$ Y(a_k) = \bigoplus_j d_{j,k} \odot Y(a_j) $$

Since $d_{j,k} = \infty$ unless $a_j \le a_k$ we have

$$ Y(a_k) = \bigoplus_{a_j \le a_k} d_{j,k} \odot Y(a_j) $$

Analogously for $d^t$ we have $d_{i,k}^t = \min_l \{d_{i,l}^t + d_{l,k}^t\} \iff d_{k,i} = \min_l \{d_{k,l} + d_{l,i}\}$. Recall that $\hat{Y}(a_k) := d(a_k, -)$ and $\hat{Y}(a_l) := d(a_l, -)$. This implies

$$ \hat{Y}(a_k) = \bigoplus_l d_{k,l} \odot \hat{Y}(a_l). $$

Since $d_{k,l} = \infty$ unless $a_k \le a_l$ we have

$$ \hat{Y}(a_k) = \bigoplus_{a_k \le a_l} d_{k,l} \odot \hat{Y}(a_l). \quad \square $$

Finally we have the following

**Proposition 12.** The Funk metric $D(x, y) := \max_i\{y_i - x_i|x_i \ne \infty\}$ has the property that $D(-, w)$ is tropically antilinear, namely

$$ (65) \qquad D(\lambda_1 \odot x \oplus_{\min} \lambda_2 \odot y, z) = -\lambda_1 \odot D(x, z) \oplus_{\max} -\lambda_2 \odot D(y, z) $$

while $D(w, -)$ is linear, namely

$$ (66) \qquad D(x, \lambda_1 \odot y \oplus_{\max} \lambda_2 \odot z) = \lambda_1 \odot D(x, z) \oplus_{\max} \lambda_2 \odot D(y, z). $$
**Proof.** We have $D(\lambda \odot x, y) = \max_i\{y_i - \lambda - x_i\} = D(x, y) - \lambda$.

We calculate $D(x \oplus_{\min} y, z) = \max_i\{z_i - \min\{x_i, y_i\}\} = \max_i\{z_i + \max_i\{-x_i, -y_i\}\} = \max\{\max_i\{z_i - x_i\}, \max_i\{z_i - y_i\}\} = D(x, z) \oplus_{\max} D(y, z)$.

Moreover $D(x, \lambda \odot y) = \max_i\{\lambda + y_i - x_i\} = \lambda - D(x, y)$.

Finally, $D(x, y \oplus_{\max} z) = D(x, \max\{y, z\}) = \max_i\{\max\{y_i, z_i\} - x_i\} = \max_i\{\max\{y_i - x_i\}, \max\{z_i - x_i\}\} = \max\{\max_i\{y_i - x_i\}, \max_i\{z_i - x_i\}\} = D(x, y) \oplus_{\max} D(x, z) \quad \square$

This means that we can think of $D$ as a tropical inner product.

**Remark 18.** All the results in this section hold for a general directed metric space.

4.1. $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ as Semantic spaces. We already mentioned in the overview that we consider $Y(a_k) := d(-, a_k)$ as well as $\hat{Y}(a_k) := d(a_k, -)$ as encoding the meanings of text $a_k$ in accordance with the statistical semantics principal namely that texts that appear in similar contexts have similar meaning. The function $d(a_k, -)$ is supported on extensions of $a_k$ while $d(-, a_k)$ is supported on restrictions of $a_k$.

However it is also the position of these vectors in $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ that contains semantic information since for example, $Y(a_k) = d(-, a_k)$ for $a_k$ a word is supported only on that word while $D(Y(a_k), -)$ is supported on all extensions of $a_k$.

Therefore more generally, we think of $(P(\mathcal{L}), D)$ and $(\hat{P}(\mathcal{L}), D^t)$ as “semantic spaces” giving mathematical substance to the statistical semantics hypothesis. This point if view was advocated in [1].

We further explain our view about the syntax to semantics problem in Appendix B and show that it is located in the realm of a deep and general duality in mathematics which in some cases appears as a duality between algebra and geometry.

It is interesting that even though the whole space $P(\mathcal{L})$ (or $Q(\mathcal{L})$) and $\hat{P}(\mathcal{L})$ (or $\hat{Q}(\mathcal{L})$) appear as spaces of meanings, texts appear only as special extremal rays. They are the “observable” variables while other points of $P(\mathcal{L})$ are like “hidden” variables.

The systems of equations Proposition 11 Equation (62), Equation (63) express the (min, +) linear relations satisfied by the Yoneda and co-Yoneda embedding text vectors. They are reminiscent of vector equations between word vectors as appeared first in [13].

Another way to think about them is as equations that implement the constraints imposed by the probabilities of extension. It is common to consider constraints giving rise to equations defining a geometric object and here we have something analogous but in (min, +) algebra.

Moreover we note that any (min, +) linear combination can be transformed into a Boltzmann weighted usual linear combination using a small temperature parameter and the identity Equation (91)

$$ \lim_{T \to 0} -T \log(e^{-y/T} + e^{-z/T}) = \min\{y, z\}. $$

Using this we will also show in Corollary 9, Equation (90) that $e^{-Y(a_k)}$ can be approximated by a Boltzmann weighted linear combinations of word vectors for the words that make up that text. We note the similarity of this with the expression of a value vector for a text in terms of word vectors, in the attention layer of a transformer.
**Proof.** We have $D(\lambda \odot x, y) = \max_i\{y_i - \lambda - x_i\} = D(x, y) - \lambda$.

We calculate $D(x \oplus_{\min} y, z) = \max_i\{z_i - \min\{x_i, y_i\}\} = \max_i\{z_i + \max_i\{-x_i, -y_i\}\} = \max\{\max_i\{z_i - x_i\}, \max_i\{z_i - y_i\}\} = D(x, z) \oplus_{\max} D(y, z)$.

Moreover $D(x, \lambda \odot y) = \max_i\{\lambda + y_i - x_i\} = \lambda - D(x, y)$.

Finally, $D(x, y \oplus_{\max} z) = D(x, \max\{y, z\}) = \max_i\{\max\{y_i, z_i\} - x_i\} = \max_i\{\max\{y_i - x_i\}, \max\{z_i - x_i\}\} = \max\{\max_i\{y_i - x_i\}, \max_i\{z_i - x_i\}\} = D(x, y) \oplus_{\max} D(x, z) \quad \square$

This means that we can think of $D$ as a tropical inner product.

**Remark 18.** All the results in this section hold for a general directed metric space.

4.1. $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ as Semantic spaces. We already mentioned in the overview that we consider $Y(a_k) := d(-, a_k)$ as well as $\hat{Y}(a_k) := d(a_k, -)$ as encoding the meanings of text $a_k$ in accordance with the statistical semantics principal namely that texts that appear in similar contexts have similar meaning. The function $d(a_k, -)$ is supported on extensions of $a_k$ while $d(-, a_k)$ is supported on restrictions of $a_k$.

However it is also the position of these vectors in $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ that contains semantic information since for example, $Y(a_k) = d(-, a_k)$ for $a_k$ a word is supported only on that word while $D(Y(a_k), -)$ is supported on all extensions of $a_k$.

Therefore more generally, we think of $(P(\mathcal{L}), D)$ and $(\hat{P}(\mathcal{L}), D^t)$ as “semantic spaces” giving mathematical substance to the statistical semantics hypothesis. This point if view was advocated in [1].

We further explain our view about the syntax to semantics problem in Appendix B and show that it is located in the realm of a deep and general duality in mathematics which in some cases appears as a duality between algebra and geometry.

It is interesting that even though the whole space $P(\mathcal{L})$ (or $Q(\mathcal{L})$) and $\hat{P}(\mathcal{L})$ (or $\hat{Q}(\mathcal{L})$) appear as spaces of meanings, texts appear only as special extremal rays. They are the “observable” variables while other points of $P(\mathcal{L})$ are like “hidden” variables.

The systems of equations Proposition 11 Equation (62), Equation (63) express the (min, +) linear relations satisfied by the Yoneda and co-Yoneda embedding text vectors. They are reminiscent of vector equations between word vectors as appeared first in [13].

Another way to think about them is as equations that implement the constraints imposed by the probabilities of extension. It is common to consider constraints giving rise to equations defining a geometric object and here we have something analogous but in (min, +) algebra.

Moreover we note that any (min, +) linear combination can be transformed into a Boltzmann weighted usual linear combination using a small temperature parameter and the identity Equation (91)

$$ \lim_{T \to 0} -T \log(e^{-y/T} + e^{-z/T}) = \min\{y, z\}. $$

Using this we will also show in Corollary 9, Equation (90) that $e^{-Y(a_k)}$ can be approximated by a Boltzmann weighted linear combinations of word vectors for the words that make up that text. We note the similarity of this with the expression of a value vector for a text in terms of word vectors, in the attention layer of a transformer.
Notice also that from the formulation of probabilistic language models, vectors arise naturally, first in the (min, +) context but later in Boltzmann weighted usual linear combinations (section 5.1).

Moreover we will show in Section 6 that there is a duality relating $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ as well as $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$ (they are isometric and tropically anti-isomorphic). This shows that given a corpus, the semantic information given by extensions of texts is equivalent to that given by restrictions.

We note that if the transformer is computing an approximation to $\hat{P}(\mathcal{L})$ then the fact that it is a convex space could explain why the gradient descent during training converges nicely.

Since the transformer computes probabilities for all possible next words to a text it is natural to think that the corresponding probabilistic language model $(\mathcal{L}, \leq, \text{Pr})$ contains the whole free monoid generated by words and all texts appear as extremal rays of $P(\mathcal{L})$ corresponding to principal upper sets. Wrong texts are very far away from correct texts as they are very unlikely.

In that case the neural network should then learn an effective representation of $\hat{P}(\mathcal{L})$, which a priori has a huge dimension. How the neural network is able to construct an effective approximation of such a huge dimensional space is not clear to us.

From another point of view we see that if we consider that the transformer neural network is learning $\hat{P}(\mathcal{L})$ then we can think of training the transformer as finding a solution to the huge (min, +) system of Equation (63), Proposition 11, given the coefficients $d_{j,k}$.

We will see a small example of the polyhedra $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$ as well as the dualities, in section 6.

Further evidence for these spaces as semantic spaces is provided by the fact that they have a Heyting algebra structure (which is a generalization of a Boolean algebra) as explained in [1].

As already mentioned, experiments using (a slight variant of) the co-Yoneda vectors $d(-, a_k)$ were performed in [12] where an actual transformer neural network was used to sample continuations of texts and construct the co Yoneda vectors. The authors tested these vectors on several semantic tasks and obtained very good results.

## 4.2. From one word text extensions to longer extensions.
We now explain how to go from one word extension probabilities to the metric $d$.

However $d$ constructed in this way does not satisfy the main assumption of probabilistic language model $\text{Pr}(a_k|a_i) = \text{Pr}(a_j|a_i) \text{Pr}(a_k|a_j)$. It does satisfy that $d$ is a directed metric and therefore $d$ is a (min, +) projector.

Indeed, let $C$ be the matrix of one word extensions. Namely for texts $a_i$ and $a_j$ we put

$$ (67) \qquad C(a_i, a_j) = \begin{cases} -\log \text{Pr}(a_j|a_i) & \text{if } a_i \le a_j \text{ and } a_j \text{ extends } a_i \text{ by a single word,} \\ \infty & \text{if } a_i \le a_j \text{ and } a_j \text{ extends } a_i \text{ by more than a single word,} \\ \infty & \text{if } a_i \text{ and } a_j \text{ are not comparable.} \end{cases} $$
Notice also that from the formulation of probabilistic language models, vectors arise naturally, first in the (min, +) context but later in Boltzmann weighted usual linear combinations (section 5.1).

Moreover we will show in Section 6 that there is a duality relating $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$ as well as $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$ (they are isometric and tropically anti-isomorphic). This shows that given a corpus, the semantic information given by extensions of texts is equivalent to that given by restrictions.

We note that if the transformer is computing an approximation to $\hat{P}(\mathcal{L})$ then the fact that it is a convex space could explain why the gradient descent during training converges nicely.

Since the transformer computes probabilities for all possible next words to a text it is natural to think that the corresponding probabilistic language model $(\mathcal{L}, \leq, \text{Pr})$ contains the whole free monoid generated by words and all texts appear as extremal rays of $P(\mathcal{L})$ corresponding to principal upper sets. Wrong texts are very far away from correct texts as they are very unlikely.

In that case the neural network should then learn an effective representation of $\hat{P}(\mathcal{L})$, which a priori has a huge dimension. How the neural network is able to construct an effective approximation of such a huge dimensional space is not clear to us.

From another point of view we see that if we consider that the transformer neural network is learning $\hat{P}(\mathcal{L})$ then we can think of training the transformer as finding a solution to the huge (min, +) system of Equation (63), Proposition 11, given the coefficients $d_{j,k}$.

We will see a small example of the polyhedra $Q(\mathcal{L})$ and $\hat{Q}(\mathcal{L})$ as well as the dualities, in section 6.

Further evidence for these spaces as semantic spaces is provided by the fact that they have a Heyting algebra structure (which is a generalization of a Boolean algebra) as explained in [1].

As already mentioned, experiments using (a slight variant of) the co-Yoneda vectors $d(-, a_k)$ were performed in [12] where an actual transformer neural network was used to sample continuations of texts and construct the co Yoneda vectors. The authors tested these vectors on several semantic tasks and obtained very good results.

## 4.2. From one word text extensions to longer extensions.
We now explain how to go from one word extension probabilities to the metric $d$.

However $d$ constructed in this way does not satisfy the main assumption of probabilistic language model $\text{Pr}(a_k|a_i) = \text{Pr}(a_j|a_i) \text{Pr}(a_k|a_j)$. It does satisfy that $d$ is a directed metric and therefore $d$ is a (min, +) projector.

Indeed, let $C$ be the matrix of one word extensions. Namely for texts $a_i$ and $a_j$ we put

$$ (67) \qquad C(a_i, a_j) = \begin{cases} -\log \text{Pr}(a_j|a_i) & \text{if } a_i \le a_j \text{ and } a_j \text{ extends } a_i \text{ by a single word,} \\ \infty & \text{if } a_i \le a_j \text{ and } a_j \text{ extends } a_i \text{ by more than a single word,} \\ \infty & \text{if } a_i \text{ and } a_j \text{ are not comparable.} \end{cases} $$
Let $\mathrm{Id}$ denote the matrix with $\mathrm{Id}_{i,i} = 0$ and $\mathrm{Id}_{i,j} = \infty$ for $i \neq j$. $\mathrm{Id}$ is the identity matrix in the $(\min, +)$ matrix semiring. Indeed $C\mathrm{Id} = \mathrm{Id}C = C$. We note that $C_{i,i} = 0$ and therefore $C \oplus \mathrm{Id} = C$.

In that case the tropical power $C^l$ computes distances for up to $l$ word extensions.

If we bound the number of words in the extension to say $k$ then $C^k = C^{k+1}$ and $d = C^k$ is our metric.

**Proposition 13.** Let $C$ be such that $C_{i,i} = 0$. If $d = C^k = C^{k+1}$ then

$$ (68) \qquad x = dx \iff x = Cx $$

*Proof.* If $x = dx = C^k x$ then $Cx = C^{k+1}x = C^k x = dx = x$ therefore solutions of $x = dx$ are also solutions of $x = Cx$.

On the other hand if $x = Cx$ then $C^k x = x$ i.e. $dx = x$. $\square$

Since the diagonal entries of $d$, and $C$, are equal to 0, the equations $x = dx$ and $x = Cx$ are equivalent to $x \ge dx$ and $x \ge Cx$, respectively. These two systems of inequalities describe the same polyhedron.

## 5. COMPATIBILITY OF $P(\mathcal{L})$ WITH ADDING MORE TEXTS

When training the neural network to learn by predicting continuations of texts we add more and more text. Moreover we have already mentioned in Remark 7 that it is natural to grade $\mathcal{L}$ by word length of texts. It is therefore important to understand how $P(\mathcal{L})$ changes as we add more and more text.

We have the following:

**Proposition 14.** If a probabilistic language model $(\mathcal{L}_1, d_1)$ is extended to $(\mathcal{L}_2, d_2)$, namely if there is an isometric embedding $\phi : (\mathcal{L}_1, d_1) \hookrightarrow (\mathcal{L}_2, d_2)$ then there is an isometric embedding $\tilde{\phi} : (P(\mathcal{L}_1), D_1) \hookrightarrow (P(\mathcal{L}_2), D_2)$ such that $\tilde{\phi}(Y_1(a)) = Y_2(\phi(a))$. Moreover $\tilde{\phi}(P(\mathcal{L}_1))$ is a retraction (i.e. a non-expansive $(\min, +)$ projection) of $P(\mathcal{L}_2)$

We will prove this in full generality and derive the probabilistic language model case as a special case.

**Theorem 3.** Let $\phi : (X_1, \delta_1) \hookrightarrow (X_2, \delta_2)$ be an isometric embedding of discrete, finite, directed metric spaces, then there is an isometric embedding $\tilde{\phi} : (P(X_1), \Delta_1) \hookrightarrow (P(X_2), \Delta_2)$ compatible with the Yoneda isometric embeddings $Y_1 : X_1 \to P(X_1)$ and $Y_2 : X_2 \to P(X_2)$, namely $\tilde{\phi}(Y_1(a)) = Y_2(\phi(a))$. Moreover $\tilde{\phi}(P(X_1))$ is a retraction (i.e. a non-expansive $(\min, +)$ projection) of $P(X_2)$.

*Proof.* Say $X_1 := \{a_1 \dots a_n\}$ and $X_2 := \{b_1 \dots b_n, b_{n+1}, \dots b_{n+k}\}$, where $b_j = \phi(a_j)$ for $j = 1 \dots n$. Recall that we have $P(X_1) = \mathrm{Im}(\delta_1)$ is the span of $Y_1(a_j) := \delta_1(-, a_j)$ and $P(X_2) = \mathrm{Im}(\delta_2)$ is the span of $Y_2(b_j) := \delta_2(-, b_j)$.

Let $e_m := (\infty, \dots, 0, \dots, \infty)$ for $m = 1, \dots, n$, so that $e_1, \dots, e_n$ is a basis (free and generating family) of the module $(\mathbb{R}_{\min})^n$ of the $(\min, +)$ semifield $\mathbb{R}_{\min}$. We define

$$ \tilde{\phi}(\bigoplus_{m=1}^n x_m \odot e_m) := \bigoplus_{m=1}^n x_m \odot \delta_2(-, b_m) $$

We now show that

$$ \tilde{\phi}(\delta_1(-, a_i)) = \delta_2(-, b_i). $$

for $i = 1, \dots, n$. Indeed,

$$ \tilde{\phi}(\delta_1(-, a_i)) = \tilde{\phi}(\bigoplus_{j=1}^n \delta_1(a_j, a_i) \odot e_j) = \bigoplus_{j=1}^n \delta_1(a_j, a_i) \delta_2(-, b_j) = \delta_2(-, b_i). $$
Let $\mathrm{Id}$ denote the matrix with $\mathrm{Id}_{i,i} = 0$ and $\mathrm{Id}_{i,j} = \infty$ for $i \neq j$. $\mathrm{Id}$ is the identity matrix in the $(\min, +)$ matrix semiring. Indeed $C\mathrm{Id} = \mathrm{Id}C = C$. We note that $C_{i,i} = 0$ and therefore $C \oplus \mathrm{Id} = C$.

In that case the tropical power $C^l$ computes distances for up to $l$ word extensions.

If we bound the number of words in the extension to say $k$ then $C^k = C^{k+1}$ and $d = C^k$ is our metric.

**Proposition 13.** Let $C$ be such that $C_{i,i} = 0$. If $d = C^k = C^{k+1}$ then

$$ (68) \qquad x = dx \iff x = Cx $$

*Proof.* If $x = dx = C^k x$ then $Cx = C^{k+1}x = C^k x = dx = x$ therefore solutions of $x = dx$ are also solutions of $x = Cx$.

On the other hand if $x = Cx$ then $C^k x = x$ i.e. $dx = x$. $\square$

Since the diagonal entries of $d$, and $C$, are equal to 0, the equations $x = dx$ and $x = Cx$ are equivalent to $x \ge dx$ and $x \ge Cx$, respectively. These two systems of inequalities describe the same polyhedron.

## 5. COMPATIBILITY OF $P(\mathcal{L})$ WITH ADDING MORE TEXTS

When training the neural network to learn by predicting continuations of texts we add more and more text. Moreover we have already mentioned in Remark 7 that it is natural to grade $\mathcal{L}$ by word length of texts. It is therefore important to understand how $P(\mathcal{L})$ changes as we add more and more text.

We have the following:

**Proposition 14.** If a probabilistic language model $(\mathcal{L}_1, d_1)$ is extended to $(\mathcal{L}_2, d_2)$, namely if there is an isometric embedding $\phi : (\mathcal{L}_1, d_1) \hookrightarrow (\mathcal{L}_2, d_2)$ then there is an isometric embedding $\tilde{\phi} : (P(\mathcal{L}_1), D_1) \hookrightarrow (P(\mathcal{L}_2), D_2)$ such that $\tilde{\phi}(Y_1(a)) = Y_2(\phi(a))$. Moreover $\tilde{\phi}(P(\mathcal{L}_1))$ is a retraction (i.e. a non-expansive $(\min, +)$ projection) of $P(\mathcal{L}_2)$

We will prove this in full generality and derive the probabilistic language model case as a special case.

**Theorem 3.** Let $\phi : (X_1, \delta_1) \hookrightarrow (X_2, \delta_2)$ be an isometric embedding of discrete, finite, directed metric spaces, then there is an isometric embedding $\tilde{\phi} : (P(X_1), \Delta_1) \hookrightarrow (P(X_2), \Delta_2)$ compatible with the Yoneda isometric embeddings $Y_1 : X_1 \to P(X_1)$ and $Y_2 : X_2 \to P(X_2)$, namely $\tilde{\phi}(Y_1(a)) = Y_2(\phi(a))$. Moreover $\tilde{\phi}(P(X_1))$ is a retraction (i.e. a non-expansive $(\min, +)$ projection) of $P(X_2)$.

*Proof.* Say $X_1 := \{a_1 \dots a_n\}$ and $X_2 := \{b_1 \dots b_n, b_{n+1}, \dots b_{n+k}\}$, where $b_j = \phi(a_j)$ for $j = 1 \dots n$. Recall that we have $P(X_1) = \mathrm{Im}(\delta_1)$ is the span of $Y_1(a_j) := \delta_1(-, a_j)$ and $P(X_2) = \mathrm{Im}(\delta_2)$ is the span of $Y_2(b_j) := \delta_2(-, b_j)$.

Let $e_m := (\infty, \dots, 0, \dots, \infty)$ for $m = 1, \dots, n$, so that $e_1, \dots, e_n$ is a basis (free and generating family) of the module $(\mathbb{R}_{\min})^n$ of the $(\min, +)$ semifield $\mathbb{R}_{\min}$. We define

$$ \tilde{\phi}(\bigoplus_{m=1}^n x_m \odot e_m) := \bigoplus_{m=1}^n x_m \odot \delta_2(-, b_m) $$

We now show that

$$ \tilde{\phi}(\delta_1(-, a_i)) = \delta_2(-, b_i). $$

for $i = 1, \dots, n$. Indeed,

$$ \tilde{\phi}(\delta_1(-, a_i)) = \tilde{\phi}(\bigoplus_{j=1}^n \delta_1(a_j, a_i) \odot e_j) = \bigoplus_{j=1}^n \delta_1(a_j, a_i) \delta_2(-, b_j) = \delta_2(-, b_i). $$
Indeed, the last equality holds since

$$ \bigoplus_{j=1}^{n} \delta_1(a_j, a_i) \odot \delta_2(b_l, b_j) = \bigoplus_{j=1}^{n} \delta_2(b_j, b_i) \odot \delta_2(b_l, b_j) = \delta_2(b_l, b_i), $$

in which the last equality follows from the fact that $\delta_2$ is a (min,+)-idempotent.

Note that $\tilde{\phi}$ is well defined since any $x \in (\mathbb{R}_{\min})^n$ has a unique expression in the basis $e_k, k = 1, \dots, n$. If we attempted to define it directly on the (min,+) module spanned by the vectors $\delta_1(-, a_i)$ we would have to deal with the complication that $x \in \mathbb{R}^n$ does not always have a unique expression as a (min,+) combination of these vectors. In fact, one can show that only vectors in the interior of $P(\mathcal{L}_1)$ would have such unique expressions.

We now check that $\tilde{\phi}$ is an isometric embedding. We want to check that

$$ (69) \qquad \Delta_2(\tilde{\phi}(x), \tilde{\phi}(y)) = \Delta_1(x, y) $$

Recall that $\Delta_1(x, y) = \max_{j=1}^n \{y_j - x_j | x_j \neq \infty\}$. Moreover $\Delta_2(\tilde{\phi}(x), \tilde{\phi}(y)) = \max_{j=1}^{n+k} \{\tilde{y}_j - \tilde{x}_j | x_j \neq \infty\}$.

From the definition of the $\tilde{x}_j$ the result follows.

Finally we define the retraction $\mathcal{R} : P(X_2) \to P(X_2)$ by

$$ (70) \qquad \mathcal{R} := \bigoplus_{j=1}^{n} \Delta_2(-, Y(b_j)) \odot \Delta_2(Y(b_j), -) $$

Note that as a matrix

$$ (71) \qquad \mathcal{R}_{i,k} = R(Y(b_i), Y(b_k)) = \bigoplus_{j=1}^{n} \delta_2(b_i, b_j) \odot \delta_2(b_j, b_k) . $$

We need to check that $\mathcal{R}^2 = \mathcal{R}$, $\mathrm{Im}(\mathcal{R}) = \tilde{\phi}(P(X_1))$ and $\mathcal{R}$ is non-expansive. Let us check first that $\mathcal{R}^2 = \mathcal{R}$:

$$ \begin{aligned} \mathcal{R}^2(Y_2(b_k), Y_2(b_l)) = \bigoplus_{m=1}^n \mathcal{R}(Y_2(b_k), Y_2(b_m)) \odot \mathcal{R}(Y_2(b_m), Y_2(b_l)) = & \\ & \bigoplus_{m,j_1,j_2=1}^n \delta_2(b_k.b_{j_1}) + \delta_2(b_{j_1}.b_m) + \delta_2(b_m.b_{j_2}) + \delta_2(b_m.b_{j_2}) + \delta_2(b_{j_2}, b_l) = & \\ & \delta_2(b_k, b_l) = \mathcal{R}(b_k, b_l). \end{aligned} $$

Where we have used the fact that

$$ \bigoplus_{l=1}^{n} \delta_2(b_k, b_l) + \delta_2(b_l, b_m) = \bigoplus_{l=1}^{n} \delta_1(a_k, a_l) + \delta_1(a_l, a_m) = \delta_1(a_k, a_m) = \delta_2(b_k, b_m). $$

Next notice that clearly $\mathrm{Im}(\mathcal{R}) \subset \mathrm{Span}_{j=1}^n \{\delta_2(-, b_j)\} = \tilde{\phi}(P(\mathcal{L}_1))$. Moreover we claim that

$$ \mathcal{R}(\delta_2(-, b_k)) = \delta_2(-, b_k) $$

Indeed

$$ \mathcal{R}(\delta_1(-, b_k)) = \bigoplus_{j=1}^{n} \delta_2(b_j, b_k) \odot \delta_2(-, b_j). $$

and thus

$$ \mathcal{R}(\delta_1(b_l, b_k)) = \bigoplus_{j=1}^{n} \delta_2(b_j, b_k) + \delta_2(b_l, b_j) = \delta_2(b_l, b_k), $$

proving the claim.

Therefore $\mathrm{Span}_{j=1}^n \{\delta_2(-, b_j)\} \subset \tilde{\phi}(P(\mathcal{L}_1)) \subset \mathrm{Im}(\mathcal{R})$ showing that $\mathrm{Im}(\mathcal{R}) = \tilde{\phi}(P(\mathcal{L}_1))$.

Finally we check that $\mathcal{R}$ is non-expansive, namely that

$$ \Delta_2(\mathcal{R}(x), \mathcal{R}(y)) \le \Delta_2(x, y) $$
Indeed, the last equality holds since

$$ \bigoplus_{j=1}^{n} \delta_1(a_j, a_i) \odot \delta_2(b_l, b_j) = \bigoplus_{j=1}^{n} \delta_2(b_j, b_i) \odot \delta_2(b_l, b_j) = \delta_2(b_l, b_i), $$

in which the last equality follows from the fact that $\delta_2$ is a (min,+)-idempotent.

Note that $\tilde{\phi}$ is well defined since any $x \in (\mathbb{R}_{\min})^n$ has a unique expression in the basis $e_k, k = 1, \dots, n$. If we attempted to define it directly on the (min,+) module spanned by the vectors $\delta_1(-, a_i)$ we would have to deal with the complication that $x \in \mathbb{R}^n$ does not always have a unique expression as a (min,+) combination of these vectors. In fact, one can show that only vectors in the interior of $P(\mathcal{L}_1)$ would have such unique expressions.

We now check that $\tilde{\phi}$ is an isometric embedding. We want to check that

$$ (69) \qquad \Delta_2(\tilde{\phi}(x), \tilde{\phi}(y)) = \Delta_1(x, y) $$

Recall that $\Delta_1(x, y) = \max_{j=1}^n \{y_j - x_j | x_j \neq \infty\}$. Moreover $\Delta_2(\tilde{\phi}(x), \tilde{\phi}(y)) = \max_{j=1}^{n+k} \{\tilde{y}_j - \tilde{x}_j | x_j \neq \infty\}$.

From the definition of the $\tilde{x}_j$ the result follows.

Finally we define the retraction $\mathcal{R} : P(X_2) \to P(X_2)$ by

$$ (70) \qquad \mathcal{R} := \bigoplus_{j=1}^{n} \Delta_2(-, Y(b_j)) \odot \Delta_2(Y(b_j), -) $$

Note that as a matrix

$$ (71) \qquad \mathcal{R}_{i,k} = R(Y(b_i), Y(b_k)) = \bigoplus_{j=1}^{n} \delta_2(b_i, b_j) \odot \delta_2(b_j, b_k). $$

We need to check that $\mathcal{R}^2 = \mathcal{R}$, $\mathrm{Im}(\mathcal{R}) = \tilde{\phi}(P(X_1))$ and $\mathcal{R}$ is non-expansive. Let us check first that $\mathcal{R}^2 = \mathcal{R}$:

$$ \begin{aligned} \mathcal{R}^2(Y_2(b_k), Y_2(b_l)) &= \bigoplus_{m=1}^{n} \mathcal{R}(Y_2(b_k), Y_2(b_m)) \odot \mathcal{R}(Y_2(b_m), Y_2(b_l)) = \\ & \bigoplus_{m,j_1,j_2=1}^{n} \delta_2(b_k.b_{j_1}) + \delta_2(b_{j_1}.b_m) + \delta_2(b_m.b_{j_2}) + \delta_2(b_m.b_{j_2}) + \delta_2(b_{j_2}, b_l) = \\ & \delta_2(b_k, b_l) = \mathcal{R}(b_k, b_l). \end{aligned} $$

Where we have used the fact that

$$ \bigoplus_{l=1}^{n} \delta_2(b_k, b_l) + \delta_2(b_l, b_m) = \bigoplus_{l=1}^{n} \delta_1(a_k, a_l) + \delta_1(a_l, a_m) = \delta_1(a_k, a_m) = \delta_2(b_k, b_m). $$

Next notice that clearly $\mathrm{Im}(\mathcal{R}) \subset \mathrm{Span}_{j=1}^n \{\delta_2(-, b_j)\} = \tilde{\phi}(P(\mathcal{L}_1))$. Moreover we claim that

$$ \mathcal{R}(\delta_2(-, b_k)) = \delta_2(-, b_k) $$

Indeed

$$ \mathcal{R}(\delta_1(-, b_k)) = \bigoplus_{j=1}^{n} \delta_2(b_j, b_k) \odot \delta_2(-, b_j). $$

and thus

$$ \mathcal{R}(\delta_1(b_l, b_k)) = \bigoplus_{j=1}^{n} \delta_2(b_j, b_k) + \delta_2(b_l, b_j) = \delta_2(b_l, b_k), $$

proving the claim.

Therefore $\mathrm{Span}_{j=1}^n \{\delta_2(-, b_j)\} \subset \tilde{\phi}(P(\mathcal{L}_1)) \subset \mathrm{Im}(\mathcal{R})$ showing that $\mathrm{Im}(\mathcal{R}) = \tilde{\phi}(P(\mathcal{L}_1))$.

Finally we check that $\mathcal{R}$ is non-expansive, namely that

$$ \Delta_2(\mathcal{R}(x), \mathcal{R}(y)) \le \Delta_2(x, y) $$
To that end note that $\mathcal{R}$ is order preserving and also $\mathcal{R}(\alpha \odot x) = \alpha \odot \mathcal{R}(x)$. Indeed both of these statements follow from the (min, +) linearity of $\mathcal{R}$.

In particular $x \le y \iff x \oplus y = x$ which implies that $\mathcal{R}(x \oplus y) = \mathcal{R}(x)$ and therefore $\mathcal{R}(x) \oplus \mathcal{R}(y) = \mathcal{R}(x)$ which means $\mathcal{R}(x) \le \mathcal{R}(y)$.

Recall now that $\Delta_2(x, y) = \inf\{\lambda : x \le \lambda \odot y\} = \max_i\{y_i - x_i | x_i \ne \infty\}$. Then

$$x \le \Delta_2(x, y) \odot y \implies \mathcal{R}(x) \le \mathcal{R}(\Delta_2(x, y) \odot y) \implies \mathcal{R}(x) \le \Delta_2(x, y) \odot \mathcal{R}(y)$$

therefore $\Delta_2(\mathcal{R}(x), \mathcal{R}(y)) \le \Delta_2(x, y)$

□

**Remark 19.** Since $\tilde{\phi}(Y_1(a_j)) := Y_2(\phi(a_j))$ we have, if $x := \bigoplus_{j=1}^n x_j \odot Y_1(a_j)$,

$$\tilde{\phi}(x) := \bigoplus_{j=1}^{n} x_j \odot Y_2(\phi(a_j)) = \bigoplus_{j=1}^{n} x_j \odot Y_2(b_j) = \bigoplus_{j=1}^{n+k} \tilde{x}_j \odot Y_2(b_j),$$

where $\tilde{x}_j := x_j$ for $j = 1, \dots, n$ and $\tilde{x}_j = \infty$ for $j = n+1, \dots, n+k$. So in these coordinates $P(X_1)$ is cut out inside $P(X_2)$ by the equations $\tilde{x}_j = \infty$ for $j = n+1, \dots, n+k$. In this sense, it constitutes a “face” of $P(X_2)$ of (projective) dimension $|X_1| - 1$.

**Remark 20.** Note that if $x \in P(\mathcal{L}_2)$ where $x : \mathcal{L}_2 \to (-\infty, \infty]$ and $x_i := x(b_i)$ then

$$(72) \qquad \mathcal{R}(x) = \bigoplus_{j=1}^{n} \Delta_2(Y_2(b_j), x) \odot \Delta_2(-, Y(b_j)) : \mathcal{L}_2 \to (-\infty, \infty]$$

and for $i = 1, \dots, n+l$

$$(73) \qquad \mathcal{R}(x)_i := \mathcal{R}(x)(b_i) = \bigoplus_{j=1}^{n} \Delta_2(Y_2(b_i), Y_2(b_j)) \odot \Delta_2(Y_2(b_j), x) = \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot x_j$$

Therefore

$$\mathcal{R}(x) = \bigoplus_{i=1}^{n+l} \mathcal{R}(x)_i \odot Y_2(b_i) = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot x_j \odot Y_2(b_i)$$

$$(74) \qquad = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot \Delta_2(Y(b_j), x) \odot Y_2(b_i)$$

**5.1. Approximation of a text vector in terms of word vectors.** Let us see how Theorem 3 applies to the probabilistic language model case.

**Corollary 7.** Let $\mathcal{L}_1 := \{a_1 \dots a_n\}$ and $\mathcal{L}_2 := \{b_1 \dots b_n, b_{n+1}, \dots b_{n+l}\}$, be probabilistic language models and $\phi : \mathcal{L}_1 \to \mathcal{L}_2$ an isometric embedding where $b_j = \phi(a_j)$ for $j = 1 \dots n$. Let $Y_1 : (\mathcal{L}_1, d_1) \to (P(\mathcal{L}_1), D_1)$ and $Y_2 : (\mathcal{L}_2, d_2) \to (P(\mathcal{L}_2), D_2)$ be the Yoneda isometric embeddings.

Let $\mathcal{R} : P(\mathcal{L}_2) \to P(\mathcal{L}_2)$ be the non-expansive projection of Theorem 3 given by

$$(75) \qquad \mathcal{R} := \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot D_2(Y_2(b_j), -).$$

Then for $i, k = 1, \dots, n+l$

$$(76) \qquad \mathcal{R}(Y_2(b_k))_i = \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k)$$
To that end note that $\mathcal{R}$ is order preserving and also $\mathcal{R}(\alpha \odot x) = \alpha \odot \mathcal{R}(x)$. Indeed both of these statements follow from the (min, +) linearity of $\mathcal{R}$.

In particular $x \le y \iff x \oplus y = x$ which implies that $\mathcal{R}(x \oplus y) = \mathcal{R}(x)$ and therefore $\mathcal{R}(x) \oplus \mathcal{R}(y) = \mathcal{R}(x)$ which means $\mathcal{R}(x) \le \mathcal{R}(y)$.

Recall now that $\Delta_2(x, y) = \inf\{\lambda : x \le \lambda \odot y\} = \max_i\{y_i - x_i | x_i \ne \infty\}$. Then

$$x \le \Delta_2(x, y) \odot y \implies \mathcal{R}(x) \le \mathcal{R}(\Delta_2(x, y) \odot y) \implies \mathcal{R}(x) \le \Delta_2(x, y) \odot \mathcal{R}(y)$$

therefore $\Delta_2(\mathcal{R}(x), \mathcal{R}(y)) \le \Delta_2(x, y)$

□

**Remark 19.** Since $\tilde{\phi}(Y_1(a_j)) := Y_2(\phi(a_j))$ we have, if $x := \bigoplus_{j=1}^n x_j \odot Y_1(a_j)$,

$$\tilde{\phi}(x) := \bigoplus_{j=1}^{n} x_j \odot Y_2(\phi(a_j)) = \bigoplus_{j=1}^{n} x_j \odot Y_2(b_j) = \bigoplus_{j=1}^{n+k} \tilde{x}_j \odot Y_2(b_j),$$

where $\tilde{x}_j := x_j$ for $j = 1, \dots, n$ and $\tilde{x}_j = \infty$ for $j = n+1, \dots, n+k$. So in these coordinates $P(X_1)$ is cut out inside $P(X_2)$ by the equations $\tilde{x}_j = \infty$ for $j = n+1, \dots, n+k$. In this sense, it constitutes a “face” of $P(X_2)$ of (projective) dimension $|X_1| - 1$.

**Remark 20.** Note that if $x \in P(\mathcal{L}_2)$ where $x : \mathcal{L}_2 \to (-\infty, \infty]$ and $x_i := x(b_i)$ then

$$(72) \qquad \mathcal{R}(x) = \bigoplus_{j=1}^{n} \Delta_2(Y_2(b_j), x) \odot \Delta_2(-, Y(b_j)) : \mathcal{L}_2 \to (-\infty, \infty]$$

and for $i = 1, \dots, n+l$

$$(73) \qquad \mathcal{R}(x)_i := \mathcal{R}(x)(b_i) = \bigoplus_{j=1}^{n} \Delta_2(Y_2(b_i), Y_2(b_j)) \odot \Delta_2(Y_2(b_j), x) = \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot x_j$$

Therefore

$$\mathcal{R}(x) = \bigoplus_{i=1}^{n+l} \mathcal{R}(x)_i \odot Y_2(b_i) = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot x_j \odot Y_2(b_i)$$

$$(74) \qquad = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot \Delta_2(Y(b_j), x) \odot Y_2(b_i)$$

**5.1. Approximation of a text vector in terms of word vectors.** Let us see how Theorem 3 applies to the probabilistic language model case.

**Corollary 7.** Let $\mathcal{L}_1 := \{a_1 \dots a_n\}$ and $\mathcal{L}_2 := \{b_1 \dots b_n, b_{n+1}, \dots b_{n+l}\}$, be probabilistic language models and $\phi : \mathcal{L}_1 \to \mathcal{L}_2$ an isometric embedding where $b_j = \phi(a_j)$ for $j = 1 \dots n$. Let $Y_1 : (\mathcal{L}_1, d_1) \to (P(\mathcal{L}_1), D_1)$ and $Y_2 : (\mathcal{L}_2, d_2) \to (P(\mathcal{L}_2), D_2)$ be the Yoneda isometric embeddings.

Let $\mathcal{R} : P(\mathcal{L}_2) \to P(\mathcal{L}_2)$ be the non-expansive projection of Theorem 3 given by

$$(75) \qquad \mathcal{R} := \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot D_2(Y_2(b_j), -).$$

Then for $i, k = 1, \dots, n+l$

$$(76) \qquad \mathcal{R}(Y_2(b_k))_i = \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k)$$
and

$$ (77) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{n+l} \mathcal{R}(Y_2(b_k))_i \odot Y_2(b_i) = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). $$

or equivalently

$$ (78) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{b_i \le b_j \le b_k} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). $$

*Proof.* We have

$$ \mathcal{R} = \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot D_2(Y_2(b_j), -), $$

Applying to $Y_2(b_k)$ for $k=1, \dots, n+l$ we get

$$ \mathcal{R}(Y_2(b_k)) = \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot D_2(Y_2(b_j), Y_2(b_k)). $$

Since $Y_2$ is an isometric embedding we have

$$ \mathcal{R}(Y_2(b_k)) = \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot d_2(b_j, b_k) : \mathcal{L}_2 \to (-\infty, \infty]. $$

Therefore for $i=1, \dots, n+l$

$$ \mathcal{R}(Y_2(b_k))_i = \mathcal{R}(Y_2(b_k))(b_i) = \bigoplus_{j=1}^{n} D_2(Y_2(b_i), Y(b_j)) \odot d_2(b_j, b_k) $$

$$ (79) \quad = \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k) $$

Consequently

$$ (80) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{n+l} \mathcal{R}(Y_2(b_k))_j \odot Y(b_i) = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). $$

or equivalently

$$ (81) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{b_i \le b_j \le b_k} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). \quad \square $$

**Remark 21.** We see from eq 78, $\mathcal{R}(Y_2(b_k))_i = \bigoplus_{j=1}^n d_2(b_i, b_j) \odot d_2(b_j, b_k)$, that only summands such that $b_i \le b_j \le b_k$, will be finite.

**Remark 22.** Recall that, according to Theorem 3, $\mathcal{R}$ is a non-expansive map therefore

$$ (82) \quad D(\mathcal{R}(Y(b_k)), \mathcal{R}(Y(b_l))) \le D(Y(b_k), Y(b_l)). $$

We can use the previous proposition in order to approximate a text vector by the vectors corresponding to words making up that text.
and

$$ (77) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{n+l} \mathcal{R}(Y_2(b_k))_i \odot Y_2(b_i) = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). $$

or equivalently

$$ (78) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{b_i \le b_j \le b_k} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). $$

*Proof.* We have

$$ \mathcal{R} = \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot D_2(Y_2(b_j), -), $$

Applying to $Y_2(b_k)$ for $k=1, \dots, n+l$ we get

$$ \mathcal{R}(Y_2(b_k)) = \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot D_2(Y_2(b_j), Y_2(b_k)). $$

Since $Y_2$ is an isometric embedding we have

$$ \mathcal{R}(Y_2(b_k)) = \bigoplus_{j=1}^{n} D_2(-, Y_2(b_j)) \odot d_2(b_j, b_k) : \mathcal{L}_2 \to (-\infty, \infty]. $$

Therefore for $i=1, \dots, n+l$

$$ \mathcal{R}(Y_2(b_k))_i = \mathcal{R}(Y_2(b_k))(b_i) = \bigoplus_{j=1}^{n} D_2(Y_2(b_i), Y(b_j)) \odot d_2(b_j, b_k) $$

$$ (79) \quad = \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k) $$

Consequently

$$ (80) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{n+l} \mathcal{R}(Y_2(b_k))_j \odot Y(b_i) = \bigoplus_{i=1}^{n+l} \bigoplus_{j=1}^{n} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). $$

or equivalently

$$ (81) \quad \mathcal{R}(Y_2(b_k)) = \bigoplus_{b_i \le b_j \le b_k} d_2(b_i, b_j) \odot d_2(b_j, b_k) \odot Y_2(b_i). \quad \square $$

**Remark 21.** We see from eq 78, $\mathcal{R}(Y_2(b_k))_i = \bigoplus_{j=1}^n d_2(b_i, b_j) \odot d_2(b_j, b_k)$, that only summands such that $b_i \le b_j \le b_k$, will be finite.

**Remark 22.** Recall that, according to Theorem 3, $\mathcal{R}$ is a non-expansive map therefore

$$ (82) \quad D(\mathcal{R}(Y(b_k)), \mathcal{R}(Y(b_l))) \le D(Y(b_k), Y(b_l)). $$

We can use the previous proposition in order to approximate a text vector by the vectors corresponding to words making up that text.
**Corollary 8.** Let $\mathcal{L} := \{b_1, \dots, b_N\}$ be a probabilistic language model and let $W := \{w_1, \dots, w_m\}$ be the set of words identified with $b_1, \dots, b_m$ and considered as a probabilistic language model with all pairwise distances equal to infinity. Let $Y : \mathcal{L} \to P(\mathcal{L})$ be the Yoneda embedding. Let $\mathcal{R} : P(\mathcal{L}) \to P(\mathcal{L})$ be the non-expansive projection given by

$$ (83) \qquad \mathcal{R} := \bigoplus_{j=1}^{m} D(-, Y(w_j)) \odot D(Y(w_j), -). $$

Consider $Y(b_k) \in P(\mathcal{L})$, then for $i, k = 1, \dots, N$

$$ (84) \qquad \mathcal{R}(Y_2(b_k))_i = d_2(w_i, b_k) $$

and

$$ (85) \qquad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{N} d_2(w_i, b_k) \odot Y_2(w_i) = \bigoplus_{w_i \le b_k} d_2(w_i, b_k) \odot Y_2(w_i) $$

*Proof.* Consider the projection $\mathcal{R} : P(\mathcal{L}) \to P(\mathcal{L})$ given

$$ \mathcal{R} = \bigoplus_{j=1}^{m} D(-, Y(w_j)) \odot D(Y(w_j), -), $$

where $\mathrm{Im}(\mathcal{R}) = \tilde{\phi}(P(W))$.

We have identified $b_j$ with $w_j$ for $j = 1, \dots, m$ therefore from corollary 5 we have for $i, k = 1, \dots, N$

$$ (86) \qquad \mathcal{R}(Y_2(b_k))_i = \bigoplus_{j=1}^{l} d_2(b_i, w_j) \odot d_2(w_j, b_k). $$

However $d_2(b_i, w_j)$ is finite only of $j=i$ and $w_j = b_i$. In that case $d_2(b_i, w_i) = 0$. Therefore for $i = 1, \dots, N$

$$ (87) \qquad \mathcal{R}(Y_2(b_k))_i = d(w_i, b_k). $$

Consequently

$$ (88) \qquad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{N} d_2(w_i, b_k) \odot Y_2(w_i) = \bigoplus_{w_i \le b_k} d_2(w_i, b_k) \odot Y_2(w_i) . \qquad \square $$

**Corollary 9.** Let $\mathcal{L} := \{b_1, \dots, b_N\}$ be a probabilistic language model and let $W := \{w_1, \dots, w_m\}$ be the set of words identified with $b_1, \dots, b_m$ and considered as a probabilistic language model with all pairwise distances equal to infinity. Let $Y : \mathcal{L} \to P(\mathcal{L})$ be the Yoneda embedding. Let $T \ge 0$ be a parameter (which is usually called temperature), then we have

$$ (89) \qquad \mathcal{R}(Y(b_k)) = \lim_{T \to 0} -T \log\left(\sum_{w_i \le b_k} e^{-\frac{d(w_i, b_k)}{T}} e^{-\frac{Y(w_i)}{T}}\right) $$
**Corollary 8.** Let $\mathcal{L} := \{b_1, \dots, b_N\}$ be a probabilistic language model and let $W := \{w_1, \dots, w_m\}$ be the set of words identified with $b_1, \dots, b_m$ and considered as a probabilistic language model with all pairwise distances equal to infinity. Let $Y : \mathcal{L} \to P(\mathcal{L})$ be the Yoneda embedding. Let $\mathcal{R} : P(\mathcal{L}) \to P(\mathcal{L})$ be the non-expansive projection given by

$$ (83) \qquad \mathcal{R} := \bigoplus_{j=1}^{m} D(-, Y(w_j)) \odot D(Y(w_j), -). $$

Consider $Y(b_k) \in P(\mathcal{L})$, then for $i, k = 1, \dots, N$

$$ (84) \qquad \mathcal{R}(Y_2(b_k))_i = d_2(w_i, b_k) $$

and

$$ (85) \qquad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{N} d_2(w_i, b_k) \odot Y_2(w_i) = \bigoplus_{w_i \le b_k} d_2(w_i, b_k) \odot Y_2(w_i) $$

*Proof.* Consider the projection $\mathcal{R} : P(\mathcal{L}) \to P(\mathcal{L})$ given

$$ \mathcal{R} = \bigoplus_{j=1}^{m} D(-, Y(w_j)) \odot D(Y(w_j), -), $$

where $\mathrm{Im}(\mathcal{R}) = \tilde{\phi}(P(W))$.

We have identified $b_j$ with $w_j$ for $j = 1, \dots, m$ therefore from corollary 5 we have for $i, k = 1, \dots, N$

$$ (86) \qquad \mathcal{R}(Y_2(b_k))_i = \bigoplus_{j=1}^{l} d_2(b_i, w_j) \odot d_2(w_j, b_k). $$

However $d_2(b_i, w_j)$ is finite only of $j=i$ and $w_j = b_i$. In that case $d_2(b_i, w_i) = 0$. Therefore for $i = 1, \dots, N$

$$ (87) \qquad \mathcal{R}(Y_2(b_k))_i = d(w_i, b_k). $$

Consequently

$$ (88) \qquad \mathcal{R}(Y_2(b_k)) = \bigoplus_{i=1}^{N} d_2(w_i, b_k) \odot Y_2(w_i) = \bigoplus_{w_i \le b_k} d_2(w_i, b_k) \odot Y_2(w_i) . \qquad \square $$

**Corollary 9.** Let $\mathcal{L} := \{b_1, \dots, b_N\}$ be a probabilistic language model and let $W := \{w_1, \dots, w_m\}$ be the set of words identified with $b_1, \dots, b_m$ and considered as a probabilistic language model with all pairwise distances equal to infinity. Let $Y : \mathcal{L} \to P(\mathcal{L})$ be the Yoneda embedding. Let $T \ge 0$ be a parameter (which is usually called temperature), then we have

$$ (89) \qquad \mathcal{R}(Y(b_k)) = \lim_{T \to 0} -T \log\left(\sum_{w_i \le b_k} e^{-\frac{d(w_i, b_k)}{T}} e^{-\frac{Y(w_i)}{T}}\right) $$
Therefore for small $T$ we have

$$ (90) \qquad e^{-\frac{\mathcal{R}(Y(b_k))}{T}} \approx \sum_{w_i \le b_k} e^{-\frac{d(w_i, b_k)}{T}} e^{-\frac{Y(w_i)}{T}} $$

*Proof.* Recall the identity

$$ (91) \qquad \lim_{T \to 0} -T \log(e^{-y/T} + e^{-z/T}) = \min\{y, z\}. $$

Then eq. (88) implies the result. $\square$

<figure><img src="image_1.png" /></figure>

**Remark 23.** Equation (90) is similar to the expression for a text value vector in terms of word value vectors as computed in the attention module of a transformer.

**Remark 24.** As already mentioned, it is natural to filter the probabilistic language $\mathcal{L}$ by the word length of texts. Define $\mathcal{L}_k$ to be the set of texts on $\mathcal{L}$ that have word length up to $k$. $\mathcal{L}_1$ will be the set of words. Each $\mathcal{L}_k$ inherits the structure of a probabilistic language model from $\mathcal{L}$. The inclusions define isometric embeddings $\phi_k: \mathcal{L}_k \to \mathcal{L}_{k+1}$. Then we can consider the non-expansive projections $\mathcal{R}_k: P(\mathcal{L}_{k+1}) \to P(\mathcal{L}_{k+1})$ where $\mathrm{Im}(\mathcal{R}_{k+1}) = \tilde{\phi}_k(P(\mathcal{L}_k))$.

## 6. DUALITY BETWEEN TEXT EXTENSIONS AND RESTRICTIONS

We have already considered the $(\min, +)$ semifield $\mathbb{R}_{\min} := ((-\infty, +\infty], \oplus_{\min}, \odot)$. To express duality results though, it will be convenient to work with the completed $(\min, +)$ semiring $\mathbb{R}_{\min} := ([-\infty, +\infty], \oplus_{\min}, \odot)$ where as before $s \oplus_{\min} t := \min\{s, t\}$ and $s \odot t := s + t$ but we need to further determine how $-\infty$ and $\infty$ interact.

Indeed we specify that the element $+\infty$ remains absorbing, so $+\infty + s = +\infty$ holds for all element $s$, and in particular $(+\infty) + (-\infty) = +\infty$. The definition of $d_{\min}$ in (60) extends to this semiring. We also need to extend definitions of $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$:

**Definition 10.** Let $P^-(\mathcal{L}), D)$ be the directed metric polyhedron
(92)

$$ P^-(\mathcal{L}) := \{x = (x_1, \dots, x_n) \in \{\mathbb{R} \cup \{\infty, -\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} \mid x_i \le x_j + d_{i,j}\}. $$

Moreover let $\hat{P}^-(\mathcal{L}), D^t)$ be the directed metric polyhedron

$$ (93) \qquad \hat{P}^-(\mathcal{L}) := \{y = (y_1, \dots, y_n) \in \{\mathbb{R} \cup \{\infty, -\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} \mid y_i \le y_j + d_{j,i}\}. $$

**Remark 25.** Recall that we added the case of a directed metric which can also take the value $-\infty$ in Remark 1 and now $D$ is such a metric. Moreover we specified that $+\infty$ is absorbing in $\mathbb{R}_{\min}$. However the Funk metric $D$ is defined using max so we have to specify further our convention to cover expressions that contain both min and max. For that, we simply use the relation $\max(s, t) = -\min\{-s, -t\}$ to transform any max in the expression to min so that we end up with an expression containing only min. Then we compute using the $(\min, +)$ convention that $+\infty$ is absorbing.

Equivalently we can use the same relation to transform any expression to one that contains only max. Then using $-\infty$ as the absorbing element gives the same answer.

Now, analogously to Proposition 10, if we consider $d_{\min}$ and $d_{\min}^t$ acting on $\{\mathbb{R} \cup \{\infty, -\infty\}\}^n \setminus \{(\infty, \dots, \infty)\}$ then we have
Therefore for small $T$ we have

$$ (90) \qquad e^{-\frac{\mathcal{R}(Y(b_k))}{T}} \approx \sum_{w_i \le b_k} e^{-\frac{d(w_i, b_k)}{T}} e^{-\frac{Y(w_i)}{T}} $$

*Proof.* Recall the identity

$$ (91) \qquad \lim_{T \to 0} -T \log(e^{-y/T} + e^{-z/T}) = \min\{y, z\}. $$

Then eq. (88) implies the result. □

<figure><img src="image_8.png" /></figure>

**Remark 23.** Equation (90) is similar to the expression for a text value vector in terms of word value vectors as computed in the attention module of a transformer.

**Remark 24.** As already mentioned, it is natural to filter the probabilistic language $\mathcal{L}$ by the word length of texts. Define $\mathcal{L}_k$ to be the set of texts on $\mathcal{L}$ that have word length up to $k$. $\mathcal{L}_1$ will be the set of words. Each $\mathcal{L}_k$ inherits the structure of a probabilistic language model from $\mathcal{L}$. The inclusions define isometric embeddings $\phi_k: \mathcal{L}_k \to \mathcal{L}_{k+1}$. Then we can consider the non-expansive projections $\mathcal{R}_k: P(\mathcal{L}_{k+1}) \to P(\mathcal{L}_{k+1})$ where $\mathrm{Im}(\mathcal{R}_{k+1}) = \tilde{\phi}_k(P(\mathcal{L}_k))$.

## 6. DUALITY BETWEEN TEXT EXTENSIONS AND RESTRICTIONS

We have already considered the $(\min, +)$ semifield $\mathbb{R}_{\min} := ((-\infty, +\infty], \oplus_{\min}, \odot)$. To express duality results though, it will be convenient to work with the completed $(\min, +)$ semiring $\mathbb{R}_{\min} := ([-\infty, +\infty], \oplus_{\min}, \odot)$ where as before $s \oplus_{\min} t := \min\{s, t\}$ and $s \odot t := s + t$ but we need to further determine how $-\infty$ and $\infty$ interact.

Indeed we specify that the element $+\infty$ remains absorbing, so $+\infty + s = +\infty$ holds for all element $s$, and in particular $(+\infty) + (-\infty) = +\infty$. The definition of $d_{\min}$ in (60) extends to this semiring. We also need to extend definitions of $P(\mathcal{L})$ and $\hat{P}(\mathcal{L})$:

**Definition 10.** Let $P^-(\mathcal{L}), D)$ be the directed metric polyhedron
(92)

$$ P^-(\mathcal{L}) := \{x = (x_1, \dots, x_n) \in \{\mathbb{R} \cup \{\infty, -\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} \mid x_i \le x_j + d_{i,j}\}. $$

Moreover let $\hat{P}^-(\mathcal{L}), D^t)$ be the directed metric polyhedron

$$ (93) \qquad \hat{P}^-(\mathcal{L}) := \{y = (y_1, \dots, y_n) \in \{\mathbb{R} \cup \{\infty, -\infty\}\}^n \setminus \{(\infty, \dots, \infty)\} \mid y_i \le y_j + d_{j,i}\}. $$

**Remark 25.** Recall that we added the case of a directed metric which can also take the value $-\infty$ in Remark 1 and now $D$ is such a metric. Moreover we specified that $+\infty$ is absorbing in $\mathbb{R}_{\min}$. However the Funk metric $D$ is defined using max so we have to specify further our convention to cover expressions that contain both min and max. For that, we simply use the relation $\max(s, t) = -\min\{-s, -t\}$ to transform any max in the expression to min so that we end up with an expression containing only min. Then we compute using the $(\min, +)$ convention that $+\infty$ is absorbing.

Equivalently we can use the same relation to transform any expression to one that contains only max. Then using $-\infty$ as the absorbing element gives the same answer.

Now, analogously to Proposition 10, if we consider $d_{\min}$ and $d_{\min}^t$ acting on $\{\mathbb{R} \cup \{\infty, -\infty\}\}^n \setminus \{(\infty, \dots, \infty)\}$ then we have
**Proposition 15.** The polyhedron $P^-(\mathcal{L})$ is equal to $\mathrm{Im}(d_{\mathrm{min}}) = \mathrm{Fix}(d_{\mathrm{min}})$ and the polyhedron $\hat{P}^-(\mathcal{L})$ is equal to $\mathrm{Im}(d_{\mathrm{min}}^t) = \mathrm{Fix}(d_{\mathrm{min}}^t)$.

**Definition 11.** Define the pair of maps $(A, B)$ as follows. If $y : \mathcal{L} \to [-\infty, \infty]$ and $x : \mathcal{L} \to [-\infty, \infty]$ then

$$ (94) \qquad A(y) := d_{\mathrm{min}}(-y), B(x) := d_{\mathrm{min}}^t(-x) $$

Or in coordinates

$$ (95) \qquad A(y)_i := \min_j\{d_{i,j} - y_j\}, B(x)_j := \min_i\{d_{i,j} - x_i\} $$

We also denote by $D^t$ the transpose metric with $D^t(x, y) := D(y, x)$.

In fact we will see that $A$ and $B$ on non-expansive maps with respect to these metrics.

The pair $(A, B)$ forms an adjunction in the categorical or metric sense:

**Proposition 16.** If $x : \mathcal{L} \to [-\infty, \infty]$ and $y : \mathcal{L} \to [-\infty, \infty]$ then we have

$$ (96) \qquad D(Ay, x) = D^t(y, Bx) $$

*Proof.* $D(Ay, x) = \max_i\{x_i - \min_j\{d_{i,j} - y_j\}\} = -\min_i\{\min_j\{d_{i,j} - y_j\} - x_i\} = -\min_j\{\min_i\{d_{i,j} - x_i\} - y_j\} = \max\{y_j - \min_i\{d_{i,j} - x_i\}\} = D(Bx, y) = D^t(y, Bx). \quad \square$

<figure><img src="image_2.png" /></figure>

**Remark 26.** (1) Note the resemblance of the pair of adjoint maps $(A, B)$ with the Legendre-Fenchel transform where the metric is replaced by the inner product of a vector space.

(2) We note, for purposes of developing intuition, that the pair of adjoint maps $(A, B)$ is similar to a pair of adjoint linear maps $(A, A^*)$ on a vector space with inner product $\langle - , - \rangle$. Indeed in the usual linear algebra case $\langle Au, v \rangle = \langle u, A^*v \rangle$. Moreover we have already seen in Proposition 24 that $D$ is a kind of tropical inner product. There is a crucial difference though that $\langle v, v \rangle = |v|^2$ while $D(x, x) = 0$. This reflects the fact that to go from usual algebra to tropical algebra we apply $-\log$.

We now have the following

**Proposition 17.** We have $ABA = A$ and $BAB = B$ which implies that $AB$ and $BA$ are idempotent.

*Proof.* This follows from the fact that $D(Ay, x) = D^t(y, Bx)$.

Indeed $D(ABAy, Ay) = D^t(BAy, BAy) = 0$

and $D(Ay, ABAy) = D^t(BAy, BAy) = 0$. Therefore $ABAx = Ax$. The equality $BAB = B$ is shown analogously. $\square$

<figure><img src="image_3.png" /></figure>

Let us now compute the fixed parts of the adjunction $\mathrm{Fix}(AB)$ and $\mathrm{Fix}(BA)$.

**Proposition 18.** We have $\mathrm{Fix}(AB) = \mathrm{Im}(A) = \mathrm{Im}(d_{\mathrm{min}})$ and $\mathrm{Fix}(BA) = \mathrm{Im}(B) = \mathrm{Im}(d_{\mathrm{min}}^t)$.

*Proof.* This follows from the fact that $ABA = A$. Indeed clearly $\mathrm{Im}(A) \subset \mathrm{Fix}(AB)$. Moreover $\mathrm{Fix}(AB) \subset \mathrm{Im}(A)$ since $AB(x) = x$ says that $x \in \mathrm{Im}(A)$. Analogously for $BA$. $\square$

<figure><img src="image_4.png" /></figure>

In this case, due to the fact that $d_{\mathrm{min}}$ is an idempotent we can more explicitly compute the maps $A$ and $B$.
**Proposition 15.** The polyhedron $P^-(\mathcal{L})$ is equal to $\mathrm{Im}(d_{\mathrm{min}}) = \mathrm{Fix}(d_{\mathrm{min}})$ and the polyhedron $\hat{P}^-(\mathcal{L})$ is equal to $\mathrm{Im}(d_{\mathrm{min}}^t) = \mathrm{Fix}(d_{\mathrm{min}}^t)$.

**Definition 11.** Define the pair of maps $(A, B)$ as follows. If $y : \mathcal{L} \to [-\infty, \infty]$ and $x : \mathcal{L} \to [-\infty, \infty]$ then

$$ (94) \qquad A(y) := d_{\mathrm{min}}(-y), B(x) := d_{\mathrm{min}}^t(-x) $$

Or in coordinates

$$ (95) \qquad A(y)_i := \min_j \{d_{i,j} - y_j\}, B(x)_j := \min_i \{d_{i,j} - x_i\} $$

We also denote by $D^t$ the transpose metric with $D^t(x, y) := D(y, x)$.

In fact we will see that $A$ and $B$ on non-expansive maps with respect to these metrics.

The pair $(A, B)$ forms an adjunction in the categorical or metric sense:

**Proposition 16.** If $x : \mathcal{L} \to [-\infty, \infty]$ and $y : \mathcal{L} \to [-\infty, \infty]$ then we have

$$ (96) \qquad D(Ay, x) = D^t(y, Bx) $$

*Proof.* $D(Ay, x) = \max_i\{x_i - \min_j\{d_{i,j} - y_j\}\} = -\min_i\{\min_j\{d_{i,j} - y_j\} - x_i\} = -\min_j\{\min_i\{d_{i,j} - x_i\} - y_j\} = \max\{y_j - \min_i\{d_{i,j} - x_i\}\} = D(Bx, y) = D^t(y, Bx). \quad \square$

<figure><img src="image_9.png" /></figure>

**Remark 26.** (1) Note the resemblance of the pair of adjoint maps $(A, B)$ with the Legendre-Fenchel transform where the metric is replaced by the inner product of a vector space.

(2) We note, for purposes of developing intuition, that the pair of adjoint maps $(A, B)$ is similar to a pair of adjoint linear maps $(A, A^*)$ on a vector space with inner product $\langle - , - \rangle$. Indeed in the usual linear algebra case $\langle Au, v \rangle = \langle u, A^*v \rangle$. Moreover we have already seen in Proposition 24 that $D$ is a kind of tropical inner product. There is a crucial difference though that $\langle v, v \rangle = |v|^2$ while $D(x, x) = 0$. This reflects the fact that to go from usual algebra to tropical algebra we apply $-\log$.

We now have the following

**Proposition 17.** We have $ABA = A$ and $BAB = B$ which implies that $AB$ and $BA$ are idempotent.

*Proof.* This follows from the fact that $D(Ay, x) = D^t(y, Bx)$.

Indeed $D(ABAy, Ay) = D^t(BAy, BAy) = 0$

and $D(Ay, ABAy) = D^t(BAy, BAy) = 0$. Therefore $ABAx = Ax$. The equality $BAB = B$ is shown analogously. $\square$

<figure><img src="image_10.png" /></figure>

Let us now compute the fixed parts of the adjunction $\mathrm{Fix}(AB)$ and $\mathrm{Fix}(BA)$.

**Proposition 18.** We have $\mathrm{Fix}(AB) = \mathrm{Im}(A) = \mathrm{Im}(d_{\mathrm{min}})$ and $\mathrm{Fix}(BA) = \mathrm{Im}(B) = \mathrm{Im}(d_{\mathrm{min}}^t)$.

*Proof.* This follows from the fact that $ABA = A$. Indeed clearly $\mathrm{Im}(A) \subset \mathrm{Fix}(AB)$. Moreover $\mathrm{Fix}(AB) \subset \mathrm{Im}(A)$ since $AB(x) = x$ says that $x \in \mathrm{Im}(A)$. Analogously for $BA$. $\square$

<figure><img src="image_11.png" /></figure>

In this case, due to the fact that $d_{\mathrm{min}}$ is an idempotent we can more explicitly compute the maps $A$ and $B$.
**Proposition 19.** We have that

(97) $A : \operatorname{Im}(d_{\min}^t) = \hat{P}^{-}(\mathcal{L}) \rightarrow \operatorname{Im}(d_{\min}) = P^{-}(\mathcal{L})$ is given by $A(y) = -y$
and

(98) $B : \operatorname{Im}(d_{\min}) = P^{-}(\mathcal{L}) \rightarrow \operatorname{Im}(d_{\min}^{t}) = \hat{P}^{-}(\mathcal{L})$ is given by $B(x) = -x$.

*Proof.* Consider $x \in \operatorname{Im}(d_{\min}) = \operatorname{Fix}(d_{\min})$. We have $d_{\min}(x) = x \iff x_i = \min_j\{d_{i,j} + x_j\} \iff -x_j = \min_j\{d_{i,j} - x_i\} \iff d_{\min}^{t}(-x) = -x$. Therefore $B(y) = d_{\min}^{t}(-x) = -x$.

Analogously consider $y \in \operatorname{Im}(d_{\min}^t)$. We have $d_{\min}^t(y) = y \iff d_{\min}(-y) = -y$. Therefore $A(y) = d_{\min}(-y) = -y$. $\square$

**Remark 27.** Note that we can directly check the adjunction of Proposition 16 using our explicit formula from Proposition 19. Indeed $D(Ax, y) = D(-x, y) = \max_i\{y_i + x_i | x_i \neq -\infty\}$. Moreover $D^t(x, By) = D(-y, x) = \max_i\{x_i + y_i | y_i \neq -\infty\}$. Since we have a max expression, $-\infty$ is absorbing (see Remark 25) and consequently if $x_i = -\infty$ of if $y_i = -\infty$ then $x_i + y_i = -\infty$ therefore both these conditions can be ignored for taking the max and we get $D(-x, y) = D(-y, x)$.

The following theorem has been proved in [4] and [3] from different points of view and in different generalities. Another approach using category theory was used in Willerton [21].

Here we take advantage of the explicit computation in Proposition 19 which is true because $d_{\min}^2 = d_{\min}$.

**Theorem 4.** We have that

$A : \operatorname{Fix}(BA) = \operatorname{Im}(B) = \operatorname{Im}(d_{\min}^t) = \hat{P}^{-}(\mathcal{L}) \rightarrow \operatorname{Fix}(AB) = \operatorname{Im}(A) = \operatorname{Im}(d_{\min}) = P(\mathcal{L})$
and

$B : \operatorname{Fix}(AB) = \operatorname{Im}(A) = \operatorname{Im}(d_{\min}) = P(\mathcal{L}) \rightarrow \operatorname{Fix}(BA) = \operatorname{Im}(B) = \operatorname{Im}(d_{\min}^t) = \hat{P}^{-}(\mathcal{L})$
are anti-isomorphisms. In other words they are one to one and onto and inverses.
They are isometries, namely $D(Ay, Ay') = D^t(y, y')$. Finally we have

(99) $A(\lambda \odot y) = -\lambda \odot A(y)$,

(100) $A(y \oplus_{\min} y') = A(y) \oplus_{\max} A(y')$

and

(101) $A(y \oplus_{\max} y') = A(y) \oplus_{\min} A(y')$

and similarly for B.

*Proof.* From Proposition 16

(102) $A : \operatorname{Im}(d_{\min}^t) = \hat{P}(\mathcal{L}) \rightarrow \operatorname{Im}(d_{\min}) = P(\mathcal{L})$ is given by $A(y) = -y$
and

(103) $B : \operatorname{Im}(d_{\min}) = P(\mathcal{L}) \rightarrow \operatorname{Im}(d_{\min}^t) = \hat{P}(\mathcal{L})$ is given by $B(x) = -x$.

therefore A and B are one on one and onto and inverses.

Moreover $D(Ay, Ay') = D(-y, -y') = \max_i\{y'_i - y_i\} = D((y', y) = D^t(y, y')$.
Furthermore, $A(\lambda \odot y)_i = -(\lambda + y_i) = -\lambda \odot A(y)_i$

$$A(y \oplus_{\max} y')_i = - \max\{y_i, y'_i\} = \min\{-y_i, -y'_i\} = A(y)_i \oplus_{\min} A(y')_i.$$

$$A(y \oplus_{\min} y')_i = - \min\{y_i, y'_i\} = \max\{-y_i, -y'_i\} = A(y)_i \oplus_{\max} A(y')_i.$$
**Proposition 19.** We have that

$$ (97) \quad A : \operatorname{Im}(d_{\min}^t) = \hat{P}^{-}(\mathcal{L}) \to \operatorname{Im}(d_{\min}) = P^{-}(\mathcal{L}) \text{ is given by } A(y) = -y $$
and

$$ (98) \quad B : \operatorname{Im}(d_{\min}) = P^{-}(\mathcal{L}) \to \operatorname{Im}(d_{\min}^{t}) = \hat{P}^{-}(\mathcal{L}) \text{ is given by } B(x) = -x. $$

*Proof.* Consider $x \in \operatorname{Im}(d_{\min}) = \operatorname{Fix}(d_{\min})$. We have $d_{\min}(x) = x \iff x_i = \min_j\{d_{i,j} + x_j\} \iff -x_j = \min_j\{d_{i,j} - x_i\} \iff d_{\min}^{t}(-x) = -x$. Therefore $B(y) = d_{\min}^{t}(-x) = -x$.

Analogously consider $y \in \operatorname{Im}(d_{\min}^t)$. We have $d_{\min}^t(y) = y \iff d_{\min}(-y) = -y$. Therefore $A(y) = d_{\min}(-y) = -y$. $\square$

**Remark 27.** Note that we can directly check the adjunction of Proposition 16 using our explicit formula from Proposition 19. Indeed $D(Ax, y) = D(-x, y) = \max_i\{y_i + x_i|y_i \neq -\infty\}$. Moreover $D^t(x, By) = D(-y, x) = \max_i\{x_i + y_i|y_i \neq -\infty\}$. Since we have a max expression, $-\infty$ is absorbing (see Remark 25) and consequently if $x_i = -\infty$ of if $y_i = -\infty$ then $x_i + y_i = -\infty$ therefore both these conditions can be ignored for taking the max and we get $D(-x, y) = D(-y, x)$.

The following theorem has been proved in [4] and [3] from different points of view and in different generalities. Another approach using category theory was used in Willerton [21].

Here we take advantage of the explicit computation in Proposition 19 which is true because $d_{\min}^2 = d_{\min}$.

**Theorem 4.** We have that

$$ A : \operatorname{Fix}(BA) = \operatorname{Im}(B) = \operatorname{Im}(d_{\min}^t) = \hat{P}^{-}(\mathcal{L}) \to \operatorname{Fix}(AB) = \operatorname{Im}(A) = \operatorname{Im}(d_{\min}) = P(\mathcal{L}) $$
and

$$ B : \operatorname{Fix}(AB) = \operatorname{Im}(A) = \operatorname{Im}(d_{\min}) = P(\mathcal{L}) \to \operatorname{Fix}(BA) = \operatorname{Im}(B) = \operatorname{Im}(d_{\min}^{t}) = \hat{P}^{-}(\mathcal{L}) $$
are anti-isomorphisms. In other words they are one to one and onto and inverses.
They are isometries, namely $D(Ay, Ay') = D^t(y, y')$. Finally we have

$$ (99) \qquad A(\lambda \odot y) = -\lambda \odot A(y), $$

$$ (100) \qquad A(y \oplus_{\min} y') = A(y) \oplus_{\max} A(y') $$

and

$$ (101) \qquad A(y \oplus_{\max} y') = A(y) \oplus_{\min} A(y') $$

and similarly for B.

*Proof.* From Proposition 16

$$ (102) \quad A : \operatorname{Im}(d_{\min}^t) = \hat{P}(\mathcal{L}) \to \operatorname{Im}(d_{\min}) = P(\mathcal{L}) \text{ is given by } A(y) = -y $$
and

$$ (103) \quad B : \operatorname{Im}(d_{\min}) = P(\mathcal{L}) \to \operatorname{Im}(d_{\min}^{t}) = \hat{P}(\mathcal{L}) \text{ is given by } B(x) = -x. $$

therefore A and B are one on one and onto and inverses.

$$ \text{Moreover, } A(\lambda \odot y)_i = -(\lambda + y_i) = -\lambda \odot A(y)_i \\ \text{Furthermore, } A(y \oplus_{\max} y')_i = -\max\{y_i, y'_i\} = \min\{-y_i, -y'_i\} = A(y)_i \oplus_{\min} A(y')_i. $$