Branching on regenerate

Regenerate is the button that asks for a different answer to the same question, and it is close to universal in chat products because the first answer is often nearly right. What it means for storage is less obvious than what it means for a user. On a schema where a conversation is a list of messages ordered by a seq column, position 7 holds the assistant's reply to position 6, and there is nowhere for a second reply to position 6 to go. The write path resolves that by overwriting: an UPDATE on the text, a delete-and-reinsert of the message's parts, and the first reply stops having ever existed.

That is a data loss with an unusual property, which is that it is invisible in every reading of the record afterwards. The conversation does not look incomplete; it looks like a conversation in which the user asked once and was answered once.

The single slot is worth taking apart, because it is a property of the ordering and not a shortcut somebody took. A seq column places every message of a conversation in one total order, and the read path recovers the conversation by sorting on it. A total order can say that one message comes after another and it has no way to say that two messages stand in place of each other. Position 7 is one position. Two rows claiming it are either a uniqueness violation or, if the constraint is missing, a pair the read path will return in whatever order the sort happens to break the tie in.

The obvious escape is to give the second reply its own position rather than contesting the first one, and it fails for a reason worth seeing before anyone proposes it. Insert the regenerated answer at position 8 and the stored conversation now reads as one question followed by two consecutive assistant turns, which is a different conversation from the one that occurred and is a conversation the model will happily continue as though it had said both things. Push the old occupant to 8 instead and the same problem arrives reversed. The list has one relation available to it, succession, and what regenerate produces is alternation. Overwriting is the write path's only remaining option that keeps the stored order truthful, and it buys that truth by discarding one of the two things that happened.

One parent, several children, one chosen path#

Giving each message a pointer to the message it answers removes the single-slot constraint, because a parent can have any number of children:

ALTER TABLE messages
  ADD COLUMN parent_id uuid REFERENCES messages(id),
  ADD COLUMN branch_reason text
      CHECK (branch_reason IN ('initial','user_regenerate','user_edit','auto_retry'));

ALTER TABLE conversations
  ADD COLUMN head_message_id uuid REFERENCES messages(id);

CREATE INDEX messages_parent_idx ON messages (parent_id);

Nothing in that migration adds the ability to hold two replies. What it does is move the ordering off a shared value and onto a per-row edge, after which the thing that used to be contended has nobody to contend with. Position 7 was a resource two rows could both want, since there is one of it per conversation. parent_id is a statement each row makes about itself — this message answers that one — and two rows making that statement about the same parent violate no constraint, because a foreign key requires the target to exist and says nothing about how many rows may name it. The many-to-one direction of the reference is the whole of the mechanism, and it was already available in the database before anyone wanted a second reply.

The seq column disappears. Ordering within a conversation is no longer a number anyone assigns; it is the chain of parent_id links, and the conversation the user is looking at is the path from head_message_id back to the root. Everything in the message store becomes append-only, which is the invariant worth stating in one sentence and enforcing in the database: messages, parts, generations and attachments are inserted and never updated, and the only mutable value in the whole design is conversations.head_message_id.

Regenerating an assistant reply is then three statements in one transaction:

BEGIN;

INSERT INTO messages (id, conversation_id, parent_id, role, branch_reason)
SELECT $new_id, conversation_id, parent_id, 'assistant', 'user_regenerate'
FROM   messages WHERE id = $original_id;

INSERT INTO message_parts (message_id, ordinal, type, text, tool_call_id, …)
VALUES (…);                                   -- parts of the new generation

UPDATE conversations
SET    head_message_id = $new_id
WHERE  id = $conv_id AND head_message_id = $original_id;

COMMIT;

The new message copies the original's parent_id rather than pointing at the original, which is what makes it a sibling instead of a continuation. The original row and its tool parts are not touched by any statement. The UPDATE carries its own precondition in the WHERE clause, so if another tab moved the head while this generation was in flight the update affects zero rows and the transaction can be failed rather than silently clobbering — the compare-and-set from topic 2.3's sequencing discussion, applied to a single pointer instead of a version counter.

Why that clause is enough is worth one more step, because a precondition checked in the application would not be. The dangerous shape is read the head, decide it is still the one you started from, then write — two statements with a gap between them, and any interleaved write lands in the gap unnoticed. Folding the expected value into the WHERE clause removes the gap by making the check part of the write: the statement matches the row, takes a lock on it, and any concurrent update of the same row waits behind that lock rather than running alongside it. The second transaction to arrive re-evaluates its predicate against the value the first one committed, finds head_message_id no longer equal to the $original_id it expected, and updates zero rows. A row count of zero is the signal, and a write path that ignores it has the same bug as the read-then-write it replaced.

The dotted edge is drawn to make a point about what abandonment means here. A1 has no children and is not on the path to the head, so it never appears in an assembled request and the model never sees it. It is still a row, still carries its tool parts, and still carries its own record of which prompt version and which resolved model produced it.

Walking that diagram by hand is the quickest way to see why the head pointer has to exist. The conversation on screen ends at A3, so the head names A3. Read that row's parent_id and it gives U2; read U2's and it gives A2; read A2's and it gives U1; U1 has no parent, so the walk stops. Reverse the four rows collected and that is the request body, in order. A1 was never reached, and it was not skipped by a filter — no row visited on the walk names it, so there was never a moment at which it was a candidate.

The reason that walk is safe to run is an asymmetry in the edges. Each message names at most one parent, so going upwards there is never a choice to make and the path from any message to the root is unique. Going downwards there is a choice at every fork: U1 has two children, A1 and A2, and nothing stored on either row says which one the conversation kept. Both are ordinary assistant messages with ordinary parents, written seconds apart. The selection is therefore not recoverable from the tree at all, which is why it lives in a column of its own on the conversation row.

Put plainly, the tree records everything that was produced and takes no position on which of it counts, and head_message_id is the position. That division is also why abandonment is not a flag on A1. Being abandoned means no path from the current head passes through you, which is a fact about where the pointer is rather than a property of the row, and it stops being true the moment the user clicks back.

Switching branches in the UI is the same UPDATE with a different target, and that symmetry is the reason the head pointer has to exist as stored state rather than being derived from timestamps. When the user clicks back to A1, the head moves to A1, and the next message they type is inserted with parent_id = A1, which grows a second path under the older sibling. Derive the head from "most recent message" instead and the conversation silently snaps back to A2 on the next read, so the user types into one thread and the model answers in another.

The derivation looks reasonable because in a conversation nobody has branched, the newest message really is the leaf you want, and it stays true for as long as the product only ever appends. What it actually computes is "what was written last", while the question the read path needs answered is "what is this user reading now". Those two agree until somebody navigates into an older branch, at which point the newest row sits on the path they just left and the derived answer names it. A stored pointer is the only form in which a navigation decision survives, since navigation writes nothing else down.

Per-user semantics have to be settled in the same column, because a shared conversation has one pointer and more than one reader. One head_message_id on the conversation row means two people viewing the same thread see the same branch and fight over it, while a conversation_views (conversation_id, user_id, head_message_id) table gives each viewer their own selected path at the cost of making "the conversation" a thing that no longer has a single reading.

The branch_reason column is small and pays for itself the first time somebody asks how often users regenerate. It also separates the two things that produce siblings for entirely different reasons: a user who did not like the answer, and an automatic retry after a 502 from the provider. An auto_retry sibling is an operational event, and counting it as a user rejection will quietly inflate whatever quality metric you build on top.

Reading a path costs more than reading a list#

The bill for this arrives on every conversation read. A flat list was one index range scan on (conversation_id, seq); a tree is a walk:

WITH RECURSIVE path AS (
    SELECT m.*, 0 AS depth
    FROM   messages m
    WHERE  m.id = (SELECT head_message_id FROM conversations WHERE id = $1)
  UNION ALL
    SELECT m.*, p.depth + 1
    FROM   messages m JOIN path p ON m.id = p.parent_id
)
SELECT * FROM path ORDER BY depth DESC;

Each level of that recursion is a separate primary-key lookup, so a 40-message path is 40 index probes executed serially inside the CTE, and the join to the parts table hangs off the result. On warm Postgres that lands around 2.1 ms at p50 against roughly 0.6 ms for the equivalent range scan, and the gap grows linearly with conversation depth rather than staying flat. For an interactive turn that is invisible next to the model call. For an evaluation harness reading 50,000 conversations, or a renderer that fetches a conversation on every keystroke of a search box, it is the dominant cost.

The serialisation is forced by the query rather than chosen by the planner. The recursive term joins on m.id = p.parent_id, and p is the row the previous level returned, so the key for the next lookup does not exist until the current lookup has come back. Nothing can batch probes whose keys are not yet known. The range scan it replaced has no such dependency: (conversation_id, seq) is known in full before the first row is touched, so the index is descended once and the matching entries are read off in sequence. That is also the reason the gap grows with depth. Each additional turn adds one more probe that has to wait for the one above it, while it adds only one more adjacent entry to a scan.

Both figures are medians rather than totals, so the arithmetic that follows is an order of magnitude and not a bill. The two measure the same rows fetched two ways, which is what makes subtracting them meaningful: the walk costs about a millisecond and a half more than the scan, or roughly three and a half times the flat read. Against a model call that takes seconds, one interactive turn cannot be charged for it. Fifty thousand of them, which is the evaluation harness, is a little over a minute of database time added to a job whose useful work is happening somewhere else entirely. That minute arrives as fifty thousand short waits rather than as one contiguous stretch, so no individual query in the job looks slow enough to investigate.

There are three usual mitigations and they trade different things:

The materialised path is the one that usually wins for a chat product, because conversations are shallow enough that a uuid[] of ancestors stays under a kilobyte and the write is a single array append at insert time. The third option is worth naming mainly so that it is recognised when someone proposes it as "keeping seq for compatibility": renumbering on branch switch reintroduces mutation on message rows, which is the property the whole design exists to protect.

The materialised path works for a reason worth stating, because it looks like a cache and is not one. A message's ancestors are its parent's ancestors plus the parent itself, which is a complete definition given only the row being inserted and the row it names. The insert therefore copies one array and appends one identifier, with no walk and no second query. It stays correct without maintenance because ancestors never change: a message's parent_id is written once and the design forbids updating it, so no later branch switch, regenerate or edit can invalidate an array written months earlier. A cache would need invalidating; this needs nothing, and the only cost is that every row carries its whole ancestry, which is why the array's growth with depth is the honest part of the trade rather than a detail.

The shape is one most readers have already used without thinking about it. Email threading works this way: every message carries In-Reply-To, replies to the same message are siblings, and what a mail client shows as a thread is a rendering choice over a tree that the transport never flattened. Nobody expects a reply to overwrite the message it forked from, and nobody expects the existence of two replies to be a data-integrity problem. Conversation stores arrived at the flat list instead because the first generation of chat products had exactly one reply per turn, and seq was the cheapest thing that worked until regenerate shipped.

That comparison is worth holding to the edges and no further, because it fails on the two pieces this chapter has just spent its length on. Mail stores no selected path: every client renders the whole tree and the reader's eye picks a branch, so there is nothing in the format corresponding to head_message_id and no question a mail store can answer about which reply was the live one. And In-Reply-To is written by the sending client rather than enforced by the transport, which makes a mail thread a reconstruction that can arrive with edges missing, where parent_id under a foreign key is an invariant your database refuses to break. The comparison earns its keep on the shape of the links. It buys nothing about selection, and selection is where the failures in this chapter live.

Siblings, revisions and cost accounting#

Both siblings existing makes three previously impossible questions answerable. The support question — what did we show the customer at 14:03 — is a lookup by timestamp across siblings rather than a reconciliation against a tool log. The product question — is regeneration improving answers — becomes a comparison between siblings that share a parent, which is a controlled comparison, since the entire preceding context is identical by construction. And the attribution question is answerable because each sibling carries its own generation record, so "the second one used a different resolved model because the retry hit a fallback" is a join rather than a hypothesis.

The controlled part of that comparison rests on the uniqueness of the upward walk. Two siblings share a parent, the request body for either one is the path from that parent to the root, and that path is the same path because a message has one parent and the walk never branches. So the prefix the model saw is identical for both by construction rather than by anybody's care. What is not controlled is everything the generation record carries — the prompt version, the resolved model, the sampling settings — and the value of storing those per sibling is that a difference there shows up as a column rather than as a plausible story told afterwards.

It is worth being precise about what a sibling is not. It is not a diff or a revision in the version-control sense; there is no merge, no common ancestor computation beyond the shared parent, and no notion that one sibling supersedes another except by which one the head points through. Modelling it as a revision counter on the message row — revision = 2, updated in place — looks like the same idea and is the original bug with extra bookkeeping, because the previous revision's content is still gone.

The other belief worth naming is that the tool's own log makes the message store redundant, and it is tempting for an honest reason: the log really does contain both calls, timestamped, on the right conversation. What it cannot contain is which of them was shown, because nobody told the pricing service anything about display. It received two requests and answered both, correctly, and a record written downstream of a decision can show that a decision was made without showing which way it went. Recovering "this is the quote the customer saw" needs a row asserting that the reply existed and was the live one, and that row is the thing an overwrite removes. A revision counter fails the same test for the same reason, one layer up.

Nor does the tree, by itself, keep a regenerated turn honest about cost. Both siblings were billed, both consumed input tokens over the identical prefix, and a naive "tokens per conversation" query that walks only the selected path will under-report spend by exactly the abandoned branches. The generation rows are attached to messages rather than to the path, so the correct cost query groups by conversation_id across all messages and the correct context-length query walks the path — two different traversals over the same rows, and picking the wrong one reads as a 15% billing discrepancy on a product where users regenerate often.

The word "exactly" in that sentence is doing arithmetic rather than emphasis. Every generation is billed once and is recorded against the message it produced, so the true spend for a conversation is the sum over all of its messages. The path is a subset of those messages, and summing over a subset leaves out its complement, which here is precisely the set of messages no path from the head reaches. So the shortfall is not an estimate that drifts — it is the cost of the abandoned siblings, whatever that happens to be. Its size is set by how often users regenerate rather than by how long conversations get, since a longer conversation adds messages to both the path and the total in equal measure while a regenerate adds one to the total alone.

The tree also does not decide what the user sees, and that is deliberate. Most products render the branch as a "2 / 3" control with arrows, some show only the selected path and expose the alternatives in an admin view, and a few surface nothing at all. All three read the same rows; the difference is entirely in whether the client is given the siblings of each message on the path. Keeping that a presentation decision means the retention of the alternative does not depend on a product opinion that may change.

There is a broader version of this argument in circulation that is worth knowing about even though it goes further than most products need. Arcade's Chats are the wrong abstraction for agentic context makes the case that a linear message log is a poor container for agent work in general, and that what agents actually accumulate is a set of artefacts and facts with their own identities, of which the transcript is one projection. The tree described here is a modest step in that direction: it keeps the transcript as the primary structure and only admits that a position in it can hold more than one thing. If your product is an agent that runs for hours and produces documents, the stronger position deserves a look; if it is a chat with a regenerate button, the tree is the whole of what is needed.

A parent pointer and a head pointer are a small change to a schema and a large change to what the schema is capable of asserting. A flat list can only say what the conversation is now; a tree says what it is now and what it was, which is the difference between a record that supports an investigation and one that quietly contradicts the customer. The price is a recursive read on every conversation load, a mitigation to apply when that read stops being free, and an append-only discipline that has to hold across every write path anybody adds later.

Two things it genuinely leaves open are worth flagging now. Abandoned branches accumulate content that is never shown to anyone and never garbage-collected by any user action, which makes them easy to forget when someone asks where a user's data is. And the £3,890 quote was not only a message that was overwritten; if that pricing call had reserved inventory, issued a credit, or sent an email, the branch that officially never happened would have left a mark on the world that the head pointer has no authority over. That second one stops being a footnote as soon as a product ships an edit-and-resend button, because editing a message three turns back does not orphan one reply — it orphans everything after it, tool calls included.