A Conditional Mutual Information Analysis of Response Variety in Language Models

Introduction

Large language models (LLMs), with their autoregressive character, dominate text generation. Based on a “temperature” parameter, LLMs in inference/generative mode may provide a variety of responses to a given prompt. This work provides an analysis method of the variety of responses to a given prompt. It is more expressive than simply setting a temperature. The basis is a conditional version of mutual information [Cover]:

with the operational expression

In eq:1.1, $\mathbf{K}^{1}$ and $\mathbf{K}^{2}$ are phrases that pre- and post-pend $Q$; the latter thought of as a query, $q\in Q$.

We shall show that

with $H(X)$ the entropy of the vocabulary.

Without the conditionality, Eq. (1.1) simplifies to the standard mutual information (MI) between the probability of two correlated random variables (RVs) and their product, independent probabilities. Cover and Thomas’ book [Cover] also provides the conditional mutual information (CMI) version in Eq. (1.1) and various rewritings of it are used to obtain Eq. (3) and to analyze its limiting behaviors. When the CMI is maximum, one learns the most possible about $\mathbf{K}^{2}$ from knowledge of $\mathbf{K}^{1}$ (and vice versa), conditional on $Q=q$. When zero, no added information about $\mathbf{K}^{2}$ due to knowledge of $\mathbf{K}^{1}$ (and vice versa), conditional on query $Q=q$ is obtained. Based on these limits, we define three instructive classes termed: arbiter, independent (conditionally) and neutral/deterministic. Examples of each class and their application to the four topics: 1) “temperature” analysis, 2) language analysis, 3) prompt compression and 4) knowledge graphs are presented.

Derivations

General Expressions

The following relies on Cover and Thomas’ book [Cover]. For notational simplicity, use “1”, “2” and “3” for the RV names. The conditional MI in Eq. (1.1.a), by expansion of numerator and denominator, is

in terms of the corresponding entropies.

Use the entropy decomposition expression

written for $-H(1\mid23)$, in Eq. (4) to get

Now use another version of $H(123)$:

Substitute Eq. (7) in Eq. (6) to eliminate $H(3)$:

From Eq. (4),

From Eq. (8),

Eq. (9) provides a tighter bound than that from Eq. (10).

From the ‘symmetry’ of Eq. (9),

Limiting Cases

Various limiting behaviors are instructive. Throughout, assume that functional relations between given RVs are one-to-one, as is sensible for tokens.

Suppose $1=f(3)$. Then $H(1\mid23)\xrightarrow{1=f(3)}0$ because there can be only one value of RV 1 for a specified value of RV 3. Thus, from Eq. (4)

Eq. (12) maximizes Eq. (11). Note that for any vocabulary it is straightforward to evaluate the conditional entropy $H(1\mid2)$.

Suppose $3=f(2)$. Then $H(1\mid23)\xrightarrow{3=f(2)}H(1\mid2)$ because RV 3 provides no added information about RV 2, given a value of RV 2. From Eq. (4)

Lastly, as conditioning can only reduce entropy, Eq. (11) has the further limiting behavior that if e.g., the minimum in Eq. (11) is $H(1\mid2)$ then

Explicit proofs of the above two limiting cases are provided in Appendix § 6.

Limit Behavior and Terminology

With the above limit behaviors, three situations: arbiter, independent (conditionally) and neutral/deterministic can be inferred.

From Eq. (12), where $1=f(3)$, using the terminology and notation of the Introduction,

where $\{\mathrm{K}^{1},\mathrm{K}^{2},Q\}\in\mathrm{X}$, with $\mathrm{X}$ the token set of entropy $H(\mathrm{X})$. Here, one can conclude that, for a set of query words, there is a strong chance that for $\mathrm{K}^{1}$ you “know” what $\mathrm{K}^{2}$ is. Examples are given in Table 1.

$\mathrm{K}^{1}$	$\mathrm{K}^{2}$	$Q=q$
the black cat	over the moon	jumped
peanut butter	jelly	and
bread	butter	and
peaches	cream	and
I	you	love
love	all	conquers

This circumstance should be more likely for longer phrases, such as poetry/lyrics.

Regarding the inequality in Eq. (15), note that for many queries there will be $\{\mathrm{K}^{1}\}$ sets where there is no correlation with a $q$. E.g., $q=[\text{and}]$ with $\mathrm{K}^{1}$ just about any word, such as {bread, milk, cat, ....} $\to$ [and]. For these $q$’s, $I_q(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q=q)\to H(\mathbf{K}^{1})$, the maximum possible entropy, which is the entropy of the vocabulary, as $\mathbf{Q}=\mathbf{K}=\mathbf{V}=\mathbf{X}$.

2. Independent (conditionally): $I(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q=q)=0$. (2.13)

Independence results from Eq. (1.1) when $p(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q=q)=p(\mathbf{K}^{1}\mid Q=q)p(\mathbf{K}^{2}\mid Q=q)$ where, by definition, $\mathbf{K}^{2}$ is uninformative about $\mathbf{K}^{1}$. Examples, with representation $(\mathbf{K}^{1})\to[Q=q]\to(\mathbf{K}^{2})$, are:

(he, they, she,...) $\to$ [looked] $\to$ (up, down, sideways,...).

This should be a common occurrence.

3. Neutral/deterministic: $I(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q=q)=0$. (2.14)

This occurs when $\mathbf{K}^{2}=f(Q=q)$, (or $\mathbf{K}^{1}=f(Q=q)$), where there is no correlation between prefix and suffix, conditional on a query. We refer to it as neutral as nothing is learned about $\mathbf{K}^{2}$ when $\mathbf{K}^{1}$ is determined by a query $Q=q$. We refer to it as deterministic because $p(\mathbf{K}^{2}=\mathbf{k}\mid Q=q)=\delta_{\mathbf{k},\hat{\mathbf{k}}}$ (or $p(\mathbf{K}^{1}=\mathbf{k}\mid Q=q)=\delta_{\mathbf{k},\hat{\mathbf{k}}}$) with $\hat{\mathbf{k}}$ a token. This case should also be a common occurrence. It is easy to distinguish between independent (conditionally) and neutral/deterministic where, in both cases $I(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q=q)=0$, because for neutral/deterministic $p(\mathbf{K}^{2}=\mathbf{k}\mid Q=q)=\delta_{\mathbf{k},\hat{\mathbf{k}}}$ (or $p(\mathbf{K}^{1}=\mathbf{k}\mid Q=q)=\delta_{\mathbf{k},\hat{\mathbf{k}}}$).

Examples of neutral/deterministic with pattern $[Q=q]\to(\mathbf{K}^{2})$ are shown in Table 2. E.g., for [Carpe] $\to$ (Diem) – a fixed prefix for this query, [Carpe]. That is, there is only one $\mathbf{K}^{2}$ for this $Q=q$.

$[Q=q]$	$(\mathbf{K}^{2})$
Carpe	Diem
chit	chat
topsy	turvy
sink or	swim
related	to

Table 2. neutral/deterministic examples.

Of course, the last example in Table 2 is not precise because, e.g., $\mathbf{K}^{2} = (\text{with})$ is also possible.

But the others are distinctly deterministic.

Uses

Four uses of this mutual information are discussed here:

1. Temperature. Generically, the above analysis can be viewed as a more specific approach to “temperature ($T$)”. In generative mode $T$ is used to span, for low $T$, almost always the same response, to high $T$, with a greater variety of responses. Tasks such as mathematical proofs are appropriate to low $T$ while poetry would be better served by a higher $T$. (Other methods of producing a variety of responses such as “top-K” and “top-P” exist of course. [von Platen])

2. Language analysis. E.g., for a “connector” ($Q=q$) word. If a connector, $q$, is “and” then one expects $I_q(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q=q)>0$ because of phrases such as: (bread) – [and] – (butter), (peaches) – [and] – (cream), (black) – [and] – (white), etc. On the other hand, good candidates for a connector where $I_q(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q=q)=0$ because of independence could be, for examples, (he/they/she/…) – [looked] – (up/down/sideways…).

3. Prompt compression. Here, the arbiter $I(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q)=H(\mathbf{K}^{1}\mid Q)\leq H(\mathbf{K}^{1})$ for $\mathbf{K}^{2}=f(\mathbf{K}^{1})$ of Eq. (15) is most appropriate. A large CMI implies you learn about $\mathbf{K}^{2}$ from knowing $\mathbf{K}^{1}$; so, $\mathbf{K}^{1}$ can be skipped (and vice versa). For example,

(A hurricane has been announced.) – [Therefore,] – (air traffic will be disrupted.)

This $\mathbf{K}^{2}$ will, with more than random weight, be preceded by this $\mathbf{K}^{1}$. Phrases such as:

(black) –[and] –(white)

come up often in texts. The probabilities of such phrases are higher than random implying the arbiter situation.

4. Knowledge Graphs. In the context of knowledge graphs (KGs), the association of nodes (entities) with keys, $\mathbf{K}^{1}$ and $\mathbf{K}^{2}$, and edges (relationships) as queries, $Q$, is warranted. KGs [Edge] have become important to the systematization of Retrieval Augmented Generation (RAG)

[Dalimunthe, Zhao], with ongoing efforts to improve prompt design in Large Language Model inference/generation. Knowledge graphs should also fit the arbiter category because what is desired is $\mathbf{K}^{1}=f\left(\mathbf{K}^{2}\right)$ whereby $I\left(\mathbf{K}^{1},\mathbf{K}^{2}\mid Q\right)=H\left(\mathbf{K}^{1}\mid Q\right)=H\left(\mathbf{K}^{2}\mid Q\right)$. In other words, maximum CMI because, if phrases $\mathbf{K}^{2}$ and $\mathbf{K}^{1}$ are correlated, there is a lot of mutual information, conditional on $Q=q$. For example, a relationship word such as $q=[\mathrm{developed}]$ can show a strong connection between two keys as in: (Albert Einstein) $\rightarrow$ [developed] $\rightarrow$ (a theory of relativity), as further elaborated in [Dalimunthe]. Relationship words with large CMI (approximately the entropy of a key, conditional on a given query) should help create KGs in an objective manner.

Concluding Remarks

In this work, we develop a method to analyze the relationship among words and phrases based on the conditional mutual information expression given in Eq. (1.1). Various limits of it follow from the connection between the two keys, $\mathbf{K}^{1}$ and $\mathbf{K}^{2}$, or between a key, $\mathbf{K}^{1}$ or $\mathbf{K}^{2}$, and the query, $Q=q$. Expressing the conditional mutual information in terms of its constituent entropies provides various limiting expressions. From Eq. (12), it is straightforward, given a token set $\mathbf{X}$, to evaluate e.g., $H\left(\mathbf{K}^{1}\mid Q=q\right)\rightarrow H\left(\mathbf{X}\mid Q=x\right)$ because all tokens are from same alphabet. The non-negativity of this entropy provides strict bounds on the possible CMI values.

Three cases are defined: arbiter, independent (conditionally) and neutral/deterministic that achieve limiting behaviors of the conditional mutual information. They are applied to four tasks: “Temperature” analysis, language analysis, prompt compression, and knowledge graphs. The most interesting cases correspond to the arbiter situation where the CMI is close to the conditional entropy $H\left(\mathbf{X}\mid Q=x\right)$ as it relies on a strong relationship between the keys. As shown, this should be quite useful for prompt compression and knowledge graph/Retrieval Augmented Generation (KG/RAG) purposes.

Finally, with reference to Eq. (1.1), a similar analysis can be conducted for $I\left(Q,\mathbf{K}^{1}\mid\mathbf{K}^{2}\right)$ or $I\left(Q,\mathbf{K}^{2}\mid\mathbf{K}^{1}\right)$. The only distinction is which RV is fixed.

Appendix A

Eqs. (12) and (13) follow from the definitions of mutual information and entropy.

For Eq. (12), where $1=f(3)$:

For Eq. (13), where $3=f(2)$:

$\therefore H(1\mid32)\xrightarrow{3=f(2)}H(1\mid2)$