# Reconstructing linear conversations from tree-structured dialogue data

**The most effective algorithm for extracting the active conversation path from tree-structured JSONL data is leaf-to-root backtracking**: build a UUID index in O(n), identify the active leaf (last message by file position), then walk backward via `parentUuid` pointers to root and reverse. This approach naturally ignores the ~92% of abandoned messages, requires no fork-point heuristics during traversal, and is used by every production implementation found — from ChatGPT's export parser to the `cchat` tool for Claude Code. Fork classification, compaction stitching, and abandoned branch analysis are layered on top of this core algorithm, and a rich body of prior art from email threading, chat platforms, dialogue systems research, and version control informs each layer.

## The canonical path extraction algorithm

The fundamental algorithm is simple and well-established across every system that processes tree-structured conversations. The ChatGPT export format stores an explicit `current_node` pointer to the active leaf; Claude Code's JSONL does not, so the leaf must be inferred. **The last message by file position in the JSONL is the most reliable heuristic** for identifying the active endpoint, with latest timestamp as a fallback. From there, the walk is mechanical:

```python
def extract_active_path(messages):
    by_uuid = {m['uuid']: m for m in messages}
    leaf = max(messages, key=lambda m: m.get('_line_num', 0))
    path, current = [], leaf
    while current:
        path.append(current)
        current = by_uuid.get(current.get('parentUuid'))
    return list(reversed(path))
```

This pattern appears identically in the ChatGPT community parser (walks from `current_node` via `parent` pointers, reverses), in OpenAssistant's tree dataset tools (`visit_messages_depth_first` with predicate filtering), and in the `cchat` CLI tool for Claude Code. The alternative — root-to-leaf forward traversal with child selection heuristics — is less reliable because it must make a heuristic decision at every fork point, whereas backtracking from a known endpoint produces a guaranteed single path with **O(n) index build plus O(d) traversal** where d is typically only ~8% of total messages.

For cases where the active leaf is ambiguous, three fallback heuristics exist in order of reliability: deepest leaf by path length (longest conversation is usually the active one), leaf with the latest timestamp, and leaf with the most descendants in its subtree. The topological-sort longest-path algorithm provides a mathematically sound O(V+E) solution that finds the deepest leaf without heuristics, useful when file ordering or timestamps are unreliable.

The version control analogy is precise. Git's `--first-parent` traversal solves the same problem: extracting the "mainline" from a DAG by ignoring merge history. Each conversation fork is analogous to a git branch, and the active path is analogous to following first-parent pointers from HEAD to the initial commit. Git's merge-base algorithm (finding the common ancestor of two branches) directly applies to identifying where user rewinds diverged.

## Classifying forks: three distinct patterns require different detection logic

The critical insight is that **most apparent fork points are not real conversation branches**. In Claude Code sessions, a parent assistant message that invokes multiple tools generates multiple `tool_result` children — these share the same parent but represent parallel execution, not divergent conversation paths. Real forks fall into exactly two categories: compaction events and user rewinds.

**Parallel tool events** are detected by checking whether all children of a multi-child parent are `tool_result` or progress messages with no `user`-role messages among them, and whether their timestamps cluster within seconds of each other. The `cchat` tool calls this "mechanical fan-out" and filters it explicitly. The detection logic checks content block types — if every child contains `tool_result` type content, the fork is parallel execution, not a branch.

**Compaction events** carry explicit signals: a `type: "system"` with `subtype: "compact_boundary"`, a `compactMetadata` field, content containing "This session is being continued from a previous conversation," or the presence of a `logicalParentUuid` field that links across compaction boundaries. The `cchat` tool stitches across these boundaries using `logicalParentUuid` with a positional fallback when that link is broken. Claude Code's auto-compact triggers at **75-92% context window capacity**, and the compaction summary replaces the full conversation history with a condensed version.

**User rewinds** are the residual category after eliminating parallel tools and compaction. The signal is multiple `user`-role messages sharing the same parent, or a new user message whose parent is an ancestor of (rather than the immediate predecessor of) the previous user message. These represent the user going back and trying a different approach. Kim et al. (2022) formalized this pattern as "turnback utterances" in dialogue state tracking, demonstrating that current DST models significantly degrade when users change their minds — performance only recovers when turnback scenarios are explicitly included in training data.

A documented edge case: Claude Code issue #22526 reports "phantom" `parentUuid` references pointing to non-existent UUIDs, creating orphaned messages. The Claude Context Repair Tool handles this by linking orphans to the nearest valid message by timestamp, then filtering to the primary session ID.

## Prior art spans five distinct research traditions

**Email threading** provides the most directly applicable algorithmic precedent. Jamie Zawinski's threading algorithm (1997), formalized in RFC 5256, builds parent-child trees from Message-ID and References headers in a five-step process: index by ID, link via references, find roots, prune empty containers, and group by subject as fallback. The core data structure — a container holding parent-child relationships indexed by unique identifier — is identical to the UUID/parentUuid conversation tree. The JWZ algorithm's handling of missing intermediate messages through "dummy container" nodes parallels handling broken parent chains in conversation data.

**Conversation disentanglement** is a rich academic field. Elsner and Charniak's foundational work (2008, 2010) established the paradigm of predicting reply-to links in interleaved IRC chat using discourse features — speaker identity, time gaps, content similarity, and mention patterns. Kummerfeld et al. (2019) scaled this to 77,500 annotated Ubuntu IRC messages and found that reply-structure graph annotations (each message linked to its parent) form exactly the tree/forest structure present in Claude Code transcripts. Recent advances include BERT-based approaches (DialBERT, 2020), contrastive learning methods (2022), and zero-shot approaches that eliminate the need for labeled data (Chi & Rudnicky, 2021). However, these methods solve the *inverse* problem — inferring tree structure from flat text — while the Claude Code problem starts with known structure and must select a path through it.

**Dialogue state tracking with rollbacks** directly addresses the rewind problem. Kim et al. (2022) defined four types of "turnback" situations in their "Oh My Mistake!" paper and showed that injecting turnback scenarios into MultiWOZ training data recovers the performance degradation. The S3-DST framework combines joint segmentation with state tracking for long conversations, using structured prompting with pre-analytical recollection — relevant for processing sessions that span compaction boundaries.

**Branch prediction in tree-structured conversations** is studied by Meital et al. (2024) in "The Branch Not Taken," which defines the task of predicting whether a new comment replies to a leaf (continuing linearly) or an intermediate node (creating a branch). Their GLOBS model uses DistilBERT reply-to scores combined with structural and temporal features. Key finding: **branching correlates with more participants and occurs more at earlier tree levels** — a pattern that may translate to coding sessions where early architectural decisions are more likely to spawn rewinds than late implementation details.

**Chat platform engineering** reveals a consistent industry convergence on shallow threading. Slack deliberately abandoned nested replies after extensive experimentation (2015-2017), settling on single-level parent-plus-flat-replies. Discord models threads as sub-channels. Matrix's MSC3440 implements single-level threads after the deeper MSC2836 proposal proved too complex for federation. Zulip uses topic-label threading with no parent-child linking at all. Reddit's open-sourced comment tree implementation uses the same adjacency-list pattern (`parent_id → [child_ids]`) with explicit orphan detection. The universal reconstruction pattern across all platforms is: build a lookup table, identify roots, walk the tree, select paths by score or pointer, reverse if walking bottom-up.

## Compaction boundaries demand a hybrid analysis strategy

The research strongly supports treating compaction events as **explicit segmentation boundaries while attempting partial reconstruction across them**. Three approaches exist for handling compacted segments, each with distinct tradeoffs.

**Segmented analysis** treats each inter-compaction segment independently, which is semantically honest because the AI literally had different context before and after compaction. This avoids the false precision of analyzing cross-boundary patterns with data that was summarized away. JetBrains' NeurIPS 2025 workshop paper found that **observation masking** (hiding environment outputs while preserving reasoning history) matched LLM summarization in both cost savings and problem-solving ability — suggesting that what's lost in compaction is often redundant observation data rather than critical reasoning context.

**Unified analysis** attempts to reconstruct the full session using compaction summaries as bridge context, supplemented by external artifacts (file changes, git commits, test results). Factory.ai's approach maintains "persistent, anchored summaries" rather than re-summarizing, and their key insight — **"minimize tokens per task, not per request"** — argues that over-compression forces agents to re-fetch information, actually increasing total costs. This implies that compaction summaries alone may be insufficient bridges, and external artifacts are necessary for accurate cross-boundary analysis.

**The recommended hybrid** uses segmented analysis for fine-grained metrics (error rates, correction patterns, tool usage frequency) where compaction genuinely changes the AI's available context, and unified analysis for high-level patterns (session productivity, task completion, user satisfaction trajectory) where compaction summaries provide adequate continuity. Robert Lavigne's layered compression taxonomy suggests using **distilled representations of older context, summarized versions of recent context, and full detail for the current segment** — a pattern that maps directly to how compaction creates a natural hierarchy of detail levels across a session.

The SeCom framework (ICLR 2025) provides a concrete implementation: it partitions long conversations into topically coherent segments for memory management, then uses compression-based denoising on memory units to enhance retrieval across segment boundaries. The C-DIC system treats conversations as "interleaved contextual threads" with revisable per-thread compression states, using a retrieve-revise-write-back loop for cross-turn memory sharing — a pattern directly applicable to maintaining coherence across compaction boundaries.

## Abandoned branches are an underexploited gold mine

The evidence for analyzing abandoned branches is overwhelming, drawing from three converging research programs. The Dialogue Breakdown Detection Challenge (DBDC, five iterations from 2015-2022) established that **detecting and analyzing conversation failures is both feasible and valuable**, using a three-level annotation scheme (not-a-breakdown, possible breakdown, breakdown) with 30 annotators per turn. BERT-based approaches with continued pre-training achieved state-of-the-art results, beating baselines by over 12% accuracy.

**Each branch abandonment creates a natural RLHF preference pair.** The conversation state at the fork point is the context; the path the user continued on is the "chosen" response; the abandoned branch is the "rejected" response. With 92% of messages on abandoned branches, this represents an enormous untapped dataset of implicit negative feedback. Rafailov et al.'s DPO framework can consume these pairs directly without reward model training. The depth of an abandoned branch before abandonment serves as an implicit severity signal — **short abandoned branches suggest quick user recognition of a bad approach, while long ones indicate the AI was confidently wrong for many turns**.

The "rewind distance" metric — how far back users go before trying a new approach — directly measures the AI's inability to self-correct. Lu, Zhang, and Chen (2019) demonstrated with Hindsight Experience Replay that **learning from failed dialogues improves learning rate over standard experience replay**, providing theoretical grounding for mining abandoned branches. IBM Watson's Dialog Flow Analysis provides production precedent: it visualizes where users abandon conversations, extracts keywords from abandoned paths, and uses this to identify improvement opportunities in intents, entities, and dialog implementations.

Practical analysis of abandoned branches should classify abandonment causes into a coding-session-specific taxonomy (wrong algorithmic approach, stuck in error loops, scope creep, misunderstood requirements, tooling failures), measure branch depth before abandonment, identify recurring failure patterns using dialogue breakdown detection techniques, and track the relationship between rewind distance and task complexity.

## Concrete implementation recommendations

The complete pipeline for processing Claude Code session transcripts should proceed in five phases. First, **parse and index**: load JSONL, build the `uuid → message` hash map and `parent → [children]` adjacency list, detect and repair orphaned messages using timestamp-based linking. Second, **extract the active path**: identify the active leaf by file position, backtrack to root via `parentUuid`, and stitch across compaction boundaries using `logicalParentUuid` with positional fallback. Third, **classify all fork points**: iterate the children map, classify each multi-child node as parallel tools (all children are tool_results), compaction (system boundary markers present), or user rewind (residual category), and record metadata for each fork. Fourth, **segment at compaction boundaries**: split the active path at compaction events, preserve summaries as bridge context, and flag analysis confidence levels for within-segment versus cross-segment findings. Fifth, **analyze abandoned branches**: for each fork classified as a user rewind, extract the abandoned subtree, compute depth and rewind distance metrics, classify the abandonment cause, and structure as preference pairs for downstream training.

The OpenAssistant (OASST) dataset provides the closest open-source precedent at scale: **208,584 messages in 70,642 conversation trees** with explicit `message_id`/`parent_id` structure, rank annotations at branch points, and established tooling for depth-first traversal and path extraction by rank. The `cchat` tool for Claude Code specifically handles compaction stitching, branch detection filtering of mechanical fan-out, and UUID tree resolution — making it the most directly relevant existing implementation. ChatTree provides real-time visualization of conversation trees with zoom and drag navigation, useful for debugging tree reconstruction algorithms.

## Conclusion

The tree-to-linear reconstruction problem is well-solved algorithmically — leaf-to-root backtracking is the universal approach — but **the real complexity lies in fork classification and deciding what to do with the 92% of messages that aren't on the active path**. The strongest finding from this research is that abandoned branches contain far more diagnostic value than the active path itself: they reveal failure modes, create natural preference training data, and encode implicit user feedback about AI behavior. No existing system fully exploits this signal. The compaction problem is best handled through hybrid segmented-unified analysis, treating compaction summaries as lossy bridges and supplementing with external artifacts. The most underexplored opportunity is applying RLHF preference learning frameworks to the natural chosen/rejected pairs that branch points create — a direction that connects tree-structured session data directly to model improvement pipelines.