The genius algorithm behind ChatGPT’s most powerful UI feature

Yes it’s ChatGPT, the underrated + overrated chatbot used by self-proclaimed AI experts to promote “advanced skills” like prompt engineering.

But this isn’t a ChatGPT post about AI. It’s about JavaScript and algorithms…

Message editing; a valuable feature you see in every popular chatbot:

• Edit our message: No one is perfect and we all make mistakes, or we want to branch off on a different conversation from an earlier point.
• Edit AI message: Typically by regeneration to get varying responses, especially useful for creative tasks.

But ChatGPT is currently the only chatbot that saves your earlier conversation branches whenever you edit messages.

Other chatbots avoid doing this, probably due to the added complexity involved, as we’ll see.

OpenConvo is my fork of Chatbot UI v1, and this conversation branching feature was one of the key things I added to the fork — the only reason I made the fork.

Today, let’s put ourselves in the shoes of the OpenAI developers, and see how to bring this feature into life (ChatGPT’s life).

Modify the chatbot to allow storing previous user and AI messages after editing or regeneration. Users can navigate to any message sent at any time in the chat and view the resulting conversation branch and sub-branches that resulted from that message.

Just before we start this feature we’ll probably have been storing the convo as a simple list of messages👇. It’s just an ever-growing list that keeps increasing.

The 3 main functional requirements we’re concerned with, and what they currently do in a sample React app.

• Add new message: add item to list.
• Edit message: Delete this and all succeeding messages, then Add new message with edited content.
• Display messages: Transform list to JSX array with your usual data -> UI element mapping.

But now with the conversation branching feature, we’re going have some key sub-requirements stopping us from using the same implementation

• Every message has sibling messages to left and/or right.
• Every message has parent and child message to top and/or bottom.

We can’t use simple lists to store the messages anymore; we want something that easily gives us that branching functionality without us trying to be too smart.

If you’re done a little Algo/DS you’ll instantly see that the messages are in a tree-like structure. And one great way to implement trees is with: Linked Lists.

• Every conversation message is a node. A single “head” node begins the conversation.
• Every node has 4 pointers: prevSibling, nextSibling, parent, and child (←→ ↑ ↓) . Siblings are all on the same tree level.
• Every level has an active node, representing the message the user can see at that branch.

We either branch right by editing/regenerating:

Or we branch down by entering a new message or getting a response:

The most important algorithm for this conversation branching feature is the graph transversal. Dearly needed to add and display the messages.

Here’s pseudocode for the full-depth transversal to active conversation branch’s latest message:

1. Set current node to conversation head (always the same) (level 1 node)
2. Look for the active node at current node’s level and re-set current node to it. This changes whenever the user navigates with the left/right arrows.
3. If current node has a child, re-set current node to it. Else return current node.
4. Rinse and repeat: Go to step 2.

Add new message

So when the user adds a new message we travel to the latest message and add a child to it to extend the current branch.

If it’s a new convo, then we just set the head node to this new message instead.

Edit message / regenerate response

There’s no need for transversal because we get the node from the message ID in a “message edited” event listener.

At the node we find its latest/right-most sibling and add another sibling.

Display messages

Pretty straightforward: travel down all the active nodes in the conversation and read their info for display:

In OpenConvo I added each node to a simple list to transform to JSX for display in the web app:

View previous messages

No point in this branching feature if users can’t see their previous message, is there?

To view the previous messages we simply change the active message to the left or right sibling (we’re just attending to another of our children, but we love them all equally).

With this we’ve successfully added the conversation branching feature.

Another well-known way to to represent graphs/trees is an array of lists; that may have an easier (or harder) way to implement this.