How to model an AI conversation

A mathematical model for agent conversations, including message trees, internal and external state, integrity constraints, state transitions, and halting.

Introduction

From the user’s perspective, a conversation is a series of interlinked messages, forming a tree. Each message can be seen as a node, and the flow of the conversation is represented by edges connecting these nodes. It is this tree-like structure that gives users a clear and coherent view of the unfolding dialogue.

Take the JSON below as an example. It’s a conversation from ChatGPT, but with a lot of data left out:

{
  "title": "Test repetition requested",
  "create_time": 1698438998.854503,
  "update_time": 1698439032.992005,
  "mapping": {
    "52b648d0-c232-494e-a8e1-b7e1a668a8d8": {
      "id": "52b648d0-c232-494e-a8e1-b7e1a668a8d8",
      "message": {
        "id": "52b648d0-c232-494e-a8e1-b7e1a668a8d8",
        "author": { "role": "system", "metadata": {} },
        "content": { "content_type": "text", "parts": [""] }
      },
      "parent": "aaa11385-8b7f-4ff8-bbd2-6dca3ba97332",
      "children": ["aaa2ec55-09f9-4fa4-8345-3e091c396c93"]
    },
    "aaa11385-8b7f-4ff8-bbd2-6dca3ba97332": {
      "id": "aaa11385-8b7f-4ff8-bbd2-6dca3ba97332",
      "children": ["52b648d0-c232-494e-a8e1-b7e1a668a8d8"]
    },
    "aaa2ec55-09f9-4fa4-8345-3e091c396c93": {
      "id": "aaa2ec55-09f9-4fa4-8345-3e091c396c93",
      "message": {
        "id": "aaa2ec55-09f9-4fa4-8345-3e091c396c93",
        "author": { "role": "user", "metadata": {} },
        "content": {
          "content_type": "text",
          "parts": ["Node 1.\nI'm doing a test. Just repeat what I say."]
        }
      },
      "parent": "52b648d0-c232-494e-a8e1-b7e1a668a8d8",
      "children": ["5df2792d-af5b-4a6d-b94e-22ccb4e67cf8"]
    },
    "5df2792d-af5b-4a6d-b94e-22ccb4e67cf8": {
      "id": "5df2792d-af5b-4a6d-b94e-22ccb4e67cf8",
      "message": {
        "id": "5df2792d-af5b-4a6d-b94e-22ccb4e67cf8",
        "author": { "role": "assistant", "metadata": {} },
        "content": { "content_type": "text", "parts": ["Node 1."] }
      },
      "parent": "aaa2ec55-09f9-4fa4-8345-3e091c396c93",
      "children": [
        "aaa231d2-cb1a-4028-a3fb-2799cbe8633e",
        "aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da"
      ]
    },
    "aaa231d2-cb1a-4028-a3fb-2799cbe8633e": {
      "id": "aaa231d2-cb1a-4028-a3fb-2799cbe8633e",
      "message": {
        "id": "aaa231d2-cb1a-4028-a3fb-2799cbe8633e",
        "author": { "role": "user", "metadata": {} },
        "content": {
          "content_type": "text",
          "parts": ["Node 2.\nI'm doing a test. Just repeat what I say."]
        }
      },
      "parent": "5df2792d-af5b-4a6d-b94e-22ccb4e67cf8",
      "children": ["dee00795-4844-45fe-8205-f48302b73463"]
    },
    "dee00795-4844-45fe-8205-f48302b73463": {
      "id": "dee00795-4844-45fe-8205-f48302b73463",
      "message": {
        "id": "dee00795-4844-45fe-8205-f48302b73463",
        "author": { "role": "assistant", "metadata": {} },
        "content": {
          "content_type": "text",
          "parts": ["Node 2.\nI'm doing a test. Just repeat what I say."]
        }
      },
      "parent": "aaa231d2-cb1a-4028-a3fb-2799cbe8633e",
      "children": []
    },
    "aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da": {
      "id": "aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da",
      "message": {
        "id": "aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da",
        "author": { "role": "user", "metadata": {} },
        "content": {
          "content_type": "text",
          "parts": ["Node 3.\nI'm doing a test. Just repeat what I say."]
        }
      },
      "parent": "5df2792d-af5b-4a6d-b94e-22ccb4e67cf8",
      "children": ["848b706b-166e-4ad0-866c-ef5f2cf21f10"]
    },
    "848b706b-166e-4ad0-866c-ef5f2cf21f10": {
      "id": "848b706b-166e-4ad0-866c-ef5f2cf21f10",
      "message": {
        "id": "848b706b-166e-4ad0-866c-ef5f2cf21f10",
        "author": { "role": "assistant", "metadata": {} },
        "create_time": 1698439020.982715,
        "content": { "content_type": "text", "parts": ["Node 3."] }
      },
      "parent": "aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da",
      "children": ["aaa2570f-5d27-4489-a1e3-8db98dc249b6"]
    },
    "aaa2570f-5d27-4489-a1e3-8db98dc249b6": {
      "id": "aaa2570f-5d27-4489-a1e3-8db98dc249b6",
      "message": {
        "id": "aaa2570f-5d27-4489-a1e3-8db98dc249b6",
        "author": { "role": "user", "metadata": {} },
        "create_time": 1698439032.609726,
        "content": {
          "content_type": "text",
          "parts": ["Node 4.\nI'm doing a test. Just repeat what I say."]
        }
      },
      "parent": "848b706b-166e-4ad0-866c-ef5f2cf21f10",
      "children": ["17c26d4b-28a4-49e0-84cf-65752b233a5f"]
    },
    "17c26d4b-28a4-49e0-84cf-65752b233a5f": {
      "id": "17c26d4b-28a4-49e0-84cf-65752b233a5f",
      "message": {
        "id": "17c26d4b-28a4-49e0-84cf-65752b233a5f",
        "author": { "role": "assistant", "metadata": {} },
        "create_time": 1698439032.990924,
        "content": { "content_type": "text", "parts": ["Node 4."] }
      },
      "parent": "aaa2570f-5d27-4489-a1e3-8db98dc249b6",
      "children": []
    }
  },
  "moderation_results": [],
  "current_node": "17c26d4b-28a4-49e0-84cf-65752b233a5f",
  "conversation_id": "5e18bb0e-a8dc-4ebe-89ab-e3746b9782ea"
}

A few things should catch our attention:

• The root node, aaa11385-8b7f-4ff8-bbd2-6dca3ba97332, does not have a parent.
• Each field in the mapping object corresponds to a node in the tree. The parent and children fields point to related nodes by their IDs.

I wrote a script to convert any such saved conversation into a Mermaid diagram:

graph TD
52b648d0-c232-494e-a8e1-b7e1a668a8d8["system: null"]
52b648d0-c232-494e-a8e1-b7e1a668a8d8 --> aaa2ec55-09f9-4fa4-8345-3e091c396c93
style aaa11385-8b7f-4ff8-bbd2-6dca3ba97332 text-align:left
aaa11385-8b7f-4ff8-bbd2-6dca3ba97332["Root Node"]
aaa11385-8b7f-4ff8-bbd2-6dca3ba97332 --> 52b648d0-c232-494e-a8e1-b7e1a668a8d8
aaa2ec55-09f9-4fa4-8345-3e091c396c93["user: Node 1.\nI'm doing a test. Just repeat what I say."]
aaa2ec55-09f9-4fa4-8345-3e091c396c93 --> 5df2792d-af5b-4a6d-b94e-22ccb4e67cf8
5df2792d-af5b-4a6d-b94e-22ccb4e67cf8["assistant: Node 1."]
5df2792d-af5b-4a6d-b94e-22ccb4e67cf8 --> aaa231d2-cb1a-4028-a3fb-2799cbe8633e
5df2792d-af5b-4a6d-b94e-22ccb4e67cf8 --> aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da
aaa231d2-cb1a-4028-a3fb-2799cbe8633e["user: Node 2.\nI'm doing a test. Just repeat what I say."]
aaa231d2-cb1a-4028-a3fb-2799cbe8633e --> dee00795-4844-45fe-8205-f48302b73463
dee00795-4844-45fe-8205-f48302b73463["assistant: Node 2.\nI'm doing a test. Just repeat what I say."]
aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da["user: Node 3.\nI'm doing a test. Just repeat what I say."]
aaa2ec28-9cc9-4b41-9f63-4dcb413ff1da --> 848b706b-166e-4ad0-866c-ef5f2cf21f10
848b706b-166e-4ad0-866c-ef5f2cf21f10["assistant: Node 3."]
848b706b-166e-4ad0-866c-ef5f2cf21f10 --> aaa2570f-5d27-4489-a1e3-8db98dc249b6
aaa2570f-5d27-4489-a1e3-8db98dc249b6["user: Node 4.\nI'm doing a test. Just repeat what I say."]
aaa2570f-5d27-4489-a1e3-8db98dc249b6 --> 17c26d4b-28a4-49e0-84cf-65752b233a5f
17c26d4b-28a4-49e0-84cf-65752b233a5f["assistant: Node 4."]

The conversation tree

The conversation tree can be modeled using graph theory. It is a graph where nodes represent messages and directed edges represent the flow of the conversation.

Let’s define the conversation tree:

Definition

A conversation tree $T$ is defined as $T = (V, E)$ where:

• $V$ is a set of nodes, where each node represents a message.
• $E$ is a set of directed edges, where each edge represents a response or a follow-up to a message.

Nodes

Each node $v_i \in V$ can be represented by:

where:

• $ID$ is a unique identifier for the message.
• $Author$ indicates the sender of the message.
• $Content$ is the text of the message.
• $Timestamp$ is the time the message was sent.
• The tuple can include additional metadata.

Edges

Each directed edge $e_{ij} \in E$ is an ordered pair $(v_i, v_j)$ where:

• $v_i$ is the parent message.
• $v_j$ is the child message or the response to $v_i$.

Root

There is a unique node $r \in V$ such that no edges in $E$ point to $r$. This node is called the root of the tree and represents the starting point of the conversation.

Properties

• Acyclic: The graph does not contain any cycles. This ensures that the conversation has a clear flow without any looping back.
• Directed: The edges have a direction, indicating the flow of the conversation.
• Tree structure: There is exactly one path from the root to each node. This gives the conversation a hierarchical structure.

Functions

• Parent function: $P: V \setminus {r} \rightarrow V$ assigns each non-root node $v_i$ its parent $P(v_i)$.
• Children function: $C: V \rightarrow 2^V$ assigns each node $v_i$ its set of child nodes $C(v_i)$.

This mathematical formulation captures the essence of the conversation tree as presented in the JSON structure. By using graph theory, we can further analyze properties of the conversation, such as its depth, branching factor, and other relevant metrics.

Internal vs external state

The conversation tree only represents the user-facing part, or the external state, of the conversation. We call information that is part of the conversation but hidden from the user the internal state. For example, a hidden system prompt is part of the internal state.

Given the new definitions and constraints, we can refine the mathematical formulation to account for both the external and internal states of the conversation. Here’s an updated model:

Conversation state

The conversation state $\sigma$ at time $t$ is defined as:

where:

• $\sigma_E(t)$ represents the external state at time $t$.
• $\sigma_I(t)$ represents the internal state at time $t$.

Here, $\sigma$ represents the entire state at any given time. We denote the set of all possible states by $\Sigma$.

External state $\sigma_E$

The external state at time $t$, $\sigma_E(t)$, is defined as an abstract representation of the system’s observable output, represented as a set or vector. This could be the current view of the conversation, the messages exchanged, or any other output that is visible to the user.

Integrity of the external state $\sigma_E$

There is one very important constraint for how the external state should evolve. Anything that the user has already seen should not change. This means that the external state can only increase over time, and not decrease. Formally, this can be expressed as:

The external state (observable output) at time $t$ is a subset of the external state at time $t+1$, ensuring that the observable output can only be appended with new information or remain the same over time, but not altered or removed.

This constraint ensures that the integrity of the external conversation history is always preserved, while the internal state can change flexibly. In other words,

Anything about the conversation can change except what the system has already shown to the user.

This is one of the most important parts of the formulation.

Why use an abstract model?

At a basic level, this post describes a chatbot history that can track alternative user and assistant responses. Future systems can look different from conversations serialized as JSON objects. An abstract model removes infrastructure assumptions and keeps the one necessary rule: the integrity principle.

Integrity Principle

The record of actions that an agent has taken in the past cannot be changed.

I believe that the “why” is self-evident, without going into philosophy. As for the case of conversations, I represent the external state as a tree:

External state as a tree

The external state at time $t$, $\sigma_E(t)$, is defined as a tree:

where:

• $V(t)$ is a set of nodes at time $t$.
• $E(t)$ is a set of directed edges at time $t$.

As for the integrity requirement, only new nodes can be appended at any existing node, including the root node. The part of the tree from the previous step should remain the same:

• $V(t) \subseteq V(t+1)$: The set of nodes can only increase or remain the same over time.
• $E(t) \subseteq E(t+1)$: The set of edges can only increase or remain the same over time.
• Nodes and edges from previous times remain unchanged, ensuring that the conversation history is preserved.

As an example, consider the following evolution of state of a user’s interaction:

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)
    2 --> 3((V3))
    3 -.-> 4(V4)
    0 --> 5((V5))
    5 -.-> 6(V6)
    2 --> 7((V7))
    7 -.-> 8(V8)

The conversation evolved like this:

1. The user started with an empty state $\sigma_E(0)=({V_0}, \emptyset)$, that is consisting only of the root node and no edges. Think of this like landing on the chat page for the first time. (The root node is not something that the user can visibly see, but it is sent by the API.)
2. Then, they sent a message, which created a new node $V_1$.
3. The system did some processing, called the LLM, and responded with a message, resulting in a new node $V_2$.
4. The user sent another message, which resulted in a new node $V_3$, and the system responded with a message, resulting in a new node $V_4$.
5. The user then went to the beginning of the conversation and edited their first message, resulting in the creation of a branch. The original message is preserved, and a new node $V_5$ is created.
6. The system processes the edited message, which results in a new node $V_6$, serving as a response to the edited initial message $V_5$.
7. Meanwhile, the user also revisits their second message (originally resulting in $V_3$) and edits it, creating another branch in the conversation with a new node $V_7$.
8. The system processes this second edited message, leading to a new system response and the creation of node $V_8$.

The circular nodes represent user messages, and the rectangular nodes represent system messages. The full edges represent the edits to the state by the user, and the dashed edges represent the edits to the state by the assistant.

As an exercise, let’s write down and draw the external state at each step. We already described the initial state above, with only the root node:

flowchart TD
    0{V0}

The rest follow as:

flowchart TD
    0{V0} --> 1((V1))

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)
    2 --> 3((V3))

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)
    2 --> 3((V3))
    3 -.-> 4(V4)

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)
    2 --> 3((V3))
    3 -.-> 4(V4)
    0 --> 5((V5))

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)
    2 --> 3((V3))
    3 -.-> 4(V4)
    0 --> 5((V5))
    5 -.-> 6(V6)

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)
    2 --> 3((V3))
    3 -.-> 4(V4)
    0 --> 5((V5))
    5 -.-> 6(V6)
    2 --> 7((V7))

flowchart TD
    0{V0} --> 1((V1))
    1 -.-> 2(V2)
    2 --> 3((V3))
    3 -.-> 4(V4)
    0 --> 5((V5))
    5 -.-> 6(V6)
    2 --> 7((V7))
    7 -.-> 8(V8)

In each step, the external state $\sigma_E(t)$ is expanded to include new nodes and edges, adhering to the principle of “Integrity of the External State,” where previous nodes and edges remain unchanged.

An implementation should:

• Keep track of the external state reliably.
• Switch between branches efficiently.
• Limit the amount of data stored and sent to the client.
• Handle multiple users and conversations at scale.
• Handle conversations that can contain hundreds of messages.

Internal state $\sigma_I$

Similar to the external state, we represent the internal state at time $t$, $\sigma_I(t)$, as a set or vector capturing the system’s internal parameters, context, or any other hidden variables. It evolves over time based on system logic, user interactions, prompt engineering, tool calls and potentially other factors.

where:

• $H(t)$ represents hidden variables or parameters at time $t$.

–>

We don’t define a specific constraint on how $\sigma_I(t)$ should evolve. It can change based on the system’s internal machinery and requirements.

State transition

A transition function defines how a system moves from one state to another based on its inputs. Here, it defines how the visible conversation tree and internal state evolve over time.

Given $\sigma(t)$, the next conversation state $\sigma(t+1)$ is a function of both the current external and internal states:

The transition function $\Delta$ must obey the constraints we defined earlier:

• The external state $\sigma_E$ transitions by only appending nodes and edges, and not modifying previous nodes or edges.
• The internal state $\sigma_I$ transitions according to the system’s requirements and logic.

Here, $\Delta$ is a general transition function that does not distinguish between changes made by the user and changes made by the assistant. The next section makes that distinction.

User and assistant transitions

The system combines a user and an assistant. The user provides an input, and the assistant works on it until a halting condition is fulfilled. For example, the assistant can stop after it completes the user’s task.

To this end, we introduce a user transition function $u:\Sigma_E\to\Sigma_E$ and an assistant transition function $\delta: \Sigma\to\Sigma$.

The user transition function formalizes changes that the user can make to the conversation state, such as sending or editing a message. An edit creates a new branch in the conversation tree. By definition, the user cannot see or modify the internal state, so the function only operates on the external state:

The assistant can modify both the external and internal state:

For example, the assistant could query a knowledge base, save the results to the internal state, generate a response with an LLM, and send a message to the user. The assistant transition function $\delta$ would then update both the external and internal state.

The user and assistant transition the state in rounds. In this model, the user can only send a message when the assistant is done processing the previous message. As a mental model, you can think that there is a human behind the user function $u$, and there is something resembling a Turing machine behind the assistant function $\delta$, that does arbitrary computation on the state until it decides to stop. Whether the assistant can stop is formalized by the halting condition $H$:

For example, at the end of each state transition, the assistant could feed the LLM its entire output in the current round and ask

Is the user’s request fulfilled?

If the answer is yes, the halting condition is fulfilled and the assistant stops. If the answer is no, the assistant continues to work on the user’s request. One can also imagine that the assistant should stop after a maximum number of steps, preventing the assistant from going into an infinite loop.

We can now put all of our definitions together to define the main transition function $\Delta$:

Together with the integrity constraint, this box summarizes how the conversation state evolves over time. For example, call_assistant can be a recursive function whose input is the current state and whose output is the first state that meets the halting condition:

def call_assistant(state):
    """
    Assistant transitions as a recursive function
    """
    new_state = delta(state)

    if halting_condition(new_state):
        return new_state
    else:
        return call_assistant(new_state)

At the end of each round, this function checks whether the halting condition is fulfilled. If it is not, the function calls itself again with the next state.

We could alternatively use a while loop:

def call_assistant(state):
    """
    Assistant transitions as a while loop
    """
    while True:
        new_state = delta(state)

        if halting_condition(new_state):
            return new_state

        state = new_state