Building Anticipation: Markov Chains & AI/LLM Search Spaces

“To aim at.”

If you look at the etymology (word origin) of the word “stochastic” you will find many interpretations and among them you’ll find the interpretation of “guess” or “aim” — “conjecture” is what we might call that in the mathematics world.

The term these days is used often in AI/LLM search spaces – loosely representing the randomness of the output/responses.

Personally, I like the “to aim at” interpretation better, as it gives us a better sense of control – something that can feel slippery as AI/LLM search spaces and responses continue to evolve outside our usual control mechanisms in search.

One can think of an archer – bow in hand – slowly pulling back an arrow at a distant target.

Any small change in angle, release point, wind speed and other surrounding context around the moment of release can change the trajectory of the arrow through the air as it makes its way toward a desired location on the target.

All of that surrounding context accumulates all the way to the moment of release – each contributing in its own way – regardless of what state those pieces of context were in prior to release, whatever state they were in at the instantaneous point of release matters to the eventual end state of the arrow (outcome).

It didn’t matter (effectively) when the arrow was placed on the bow, it didn’t matter what the wind was like when the arrow was pulled back, it didn’t matter what angle the bow was in the moments before the release — only the state those items were in at the time the arrow transitioned from being pulled back to being released.

As anticipation builds towards release, that split second contained a compressed memory of all of those contextual elements that ultimately dictates how the arrow’s trajectory – or path – will take on its way towards a desired target.

While Markov chains are often referred to as “memorylessness” (as you’ll see below, “compressed memory” may be nice/better way to describe things in our world), this analogy can loosely describe their fundamental mechanism as a stochastic process, essentially.

A (Semi) Formal View Of Markov Chains

You can think of Markov chains as a sequence of events.

The probability of one event occurring is only dependent on the event that happened immediately prior to that event – thus the “memorylessness” description mentioned above.

A rough example of this is in poker and placing bets.

For most poker players, placing bets (or not placing a bet) is ultimately determined on the hand you currently are holding – not any previous hands you may have had.

Given any round of betting, you don’t base your betting decision on cards you had three turns ago, essentially – because they can’t be played during the current turn.

You may accumulate some context about others’ betting behaviors and bets placed ahead of you ( the “compressed memory” I mentioned earlier ) “to aim at” winning the hand, but ultimately at the moment of betting, those cards you have in your hand ultimately decide your betting maneuver – not any previous hands.

(I can feel the mathematicians in the room itching to correct me here, but hang tight.)

States & Transitions

“State” here refers to the description of an event – the “state” it’s in. The possible states collectively describes the state space of the Markov chain (or process).

A move or change from one state to another is called a transition, each transition associated with a probability.

The collection of probabilities can be assembled into matrix form – called the transition matrix, a square matrix with each entry – i, j – telling the probability of state i moving to state j, and so on.

Markov Chains & Graph Theory

For those following along, a few weeks ago I wrote about walks in my graph theory (brief) primer – and how the adjacency matrix tells you which nodes are connected ( an entry of 1 in the entry i,j if nodes i and j are connected and 0 if they are not ).

Building off the adjacency matrix intuition, transition matrices share a common thread – both are square matrices but instead of entries representing connections between nodes, entries represent probabilities between states.

It’s why it’s common to see Markov chains displayed in graph form — nodes are events and (weighted) edges represent the transitions between those events.

The depth, intricacies and different flavors of Markov chains and processes here are beyond the scope of a post like this, but this connection to graph theory is important to remember (context).

Connection To The Search Space

Without going into too many details here, but going back to the graph theory post you can see how web pages – and the links between them – form the nodes and edges in representational “graph of the web”, so to speak.

While an adjacency matrix tells you how those pages are connected — replacing those entries with probabilities that a user navigates from one page to another creates its associated transition matrix (more or less). Calculating those probabilities is done any number of ways – and is left to the reader to explore.

Where Markov chains come in, predicting if a user navigating from one page to another doesn’t require any previous knowledge of prior navigating steps – thus having the required Markov property.

Over time, a user will “walk” through some pages at a more frequent rate depending the structure and makeup of the underlying graph – a clue that that page may be more important to that particular user (and, perhaps, change that user’s transition matrix accordingly).

Regardless of importance, the only things that inform a navigation event is what page the user is currently on, along with the associated transition matrix indicating the probability of moving to particular “next pages”.

Compressed Memory & Markov Chain Encapsulation In AI/LLM Search

Referring back to that post on graph theory again, in my mind – and mental model – I see each output/response as a series of steps along a graph — each word a node and each edge connecting either the words, meanings or other concepts in those responses.

As each word is added to the response (in a way I like to think of these steps as recursive searches on dynamically created graphs), the accumulated context of the previous words and other pieces of context shape that “next word”.

This is where the mathematicians would likely argue that the connection to Markov Chains hits a wall — but look a bit more closely.

Just like our arrow and poker examples above, there’s some accumulation of context around the transition from one state to another as each word is search for and selected from a space of candidates in the vocabulary.

While the selection of the next word relies on knowledge of the previous words selected (and surrounding context), all of that knowledge is compressed as an input in the moment of selection – just like our arrow release and poker bets. And the selection of the next word also carries a transition matrix – that holds probabilities for selecting the next word based on that compressed input.

This is actually where a lot of the constraint happens an AI/LLM search — because of the need to compress and carry that knowledge efficiently to produce better outputs. There is no previous step to consider, essentially – all of it is contained in that compressed context step.

Markovian Ghosts & Transition Tendencies

Where things get interesting is how those “walks” (output responses) – and associated transition matrices – change over time and at each step – and for each user.

Evaluating responses like this – as walks – very well can (and feels) like we’re seeing the “Markovian Ghosts” of the web we in the search industry have come to know.

Just like users navigating in a web space can reveal the importance of web pages (and update/reveal associated transition matrices and tendencies – something that can be pulled from non-classical measurements), it’s not hard to see these same patterns in output responses – if you look closely enough.

To hit a target we need better ideas on how and what we’re “aiming at” – and we already have all the tools we need in the search world (with a little help from the non-classical world) to do just that.

Many more notes in the weeks to come.