ThoughtDAG – An editable context graph for LLM conversations

Introduction

Modern LLM applications keep hitting the same wall: context window overflow followed by the “lost in the middle” phenomenon. You’re mid-conversation with a complex agent system, it branches to explore a hypothesis, then you need to merge results back. But the linear chat history has already scrolled past the branching point, so the model forgets crucial context from the other path. Or worse, you explicitly want to retract a statement—“ignore my previous request about the budget”—but there’s no clean way to do that in a flat message list.

Current LLM APIs treat context as an append-only array. This works fine for simple Q&A, but real reasoning is non-linear. We need a data structure that supports transclusion, retraction, branching, and merge strategies as first-class citizens.

That’s what we built: ThoughtDAG—a persistent, immutable directed acyclic graph where nodes are “thought atoms” and edges represent semantic dependency rather than just temporal order.

Why This Matters

Senior engineers building agentic systems, compiler authors designing prompt compilers, and ML infrastructure leads managing long-running conversations all face the same fundamental problem: we’re forcing inherently graph-structured reasoning into linear buffers.

Consider a code review agent that:

1. Reads a pull request
2. Spawns parallel threads to analyze security, performance, and correctness
3. Needs to merge findings while preserving context from each path
4. Must explicitly retract a false positive before finalizing comments

In a traditional chat format, this becomes a nightmare of manual state management, message rewriting, or context pruning that destroys semantic relationships.

ThoughtDAG treats conversation state as what it really is: a mutable, versioned graph. This isn’t just theoretical purity—it’s practical necessity for any system where context matters as much as the current turn.

How It Works

At its core, ThoughtDAG is a persistent graph data structure optimized for semantic versioning of conversational state. Unlike Git, which versions files, ThoughtDAG versions semantic state—individual thoughts, their dependencies, and relationships.

graph TD
    subgraph "ThoughtDAG Structure"
        P1[Prompt<br/>id: abc-123] --> C1[Completion<br/>id: def-456]
        P1 --> C2[Tool Call<br/>id: ghi-789]
        C2 --> T1[Tool Result<br/>id: jkl-012]
        T1 --> C3[Completion<br/>id: mno-345]
        C1 --> CR1[Critique<br/>id: pqr-678]
        CR1 -.->|SUPERSEDES| C1
        S1[Summary<br/>id: stu-901] -->|TRANSCLUDE| C3
    end
    
    subgraph "Context Assembly Pipeline"
        DAG[ThoughtDAG Graph] --> TS[Topological Sort]
        TS --> PR[Prune Superseded]
        PR --> BP[Budget Partition]
        BP --> IN[Inject Summaries]
        IN --> LP[List[Message]]
    end
    
    style P1 fill:#e1f5fe
    style C1 fill:#f3e5f5
    style C2 fill:#f3e5f5
    style T1 fill:#fff3e0
    style C3 fill:#f3e5f5
    style CR1 fill:#fce4ec
    style S1 fill:#f1f8e9

The assembly pipeline works as follows:

1. Topological Sort: Respects CAUSAL edges while allowing parallel paths
2. Pruning Phase: Applies SUPERSDES edges (tombstones), drops CRITIQUE nodes when configured
3. Budgeting Phase: Solves a knapsack-like problem prioritizing recent, important, and relevant nodes
4. Injection Phase: Replaces pruned subgraphs with SUMMARY nodes that preserve semantic meaning

This gives us the ability to surgically modify context without destroying the underlying semantic graph.

Core Concepts

ThoughtNode Taxonomy

Each node type serves a specific semantic purpose:

• PromptNode: User/system input with explicit role tagging
• CompletionNode: LLM output with token counts and logprobs for quality metrics
• ToolInvocationNode/ToolResultNode: Explicit boundaries for RAG/tool usage
• CritiqueNode: Self-correction passes (Constitutional AI style)
• SummaryNode: Compressed representations for long-term memory

Edge Semantics

Edges aren’t just “previous/next”—they carry semantic meaning:

• CAUSAL: Standard reply relationship
• TRANSCLUDE: Pull context from another branch without copying history
• SUPERSEDES: Explicit retraction (think “this statement is void”)
• EMBEDS: Vector similarity links for retrieval-augmented assembly

Examples & Code Walkthrough

Here’s the Rust core that powers zero-copy serialization:

// thoughtdag-core/src/lib.rs
use rkyv::{Archive, Deserialize, Serialize};
use uuid::Uuid;

#[derive(Archive, Debug, Clone, Serialize, Deserialize)]
#[archive_attr(derive(Debug))]
pub enum NodeKind {
    Prompt { role: Role, content: ArchivedString },
    Completion { model: ArchivedString, tokens: u32, logprobs: Option<Vec<f32>> },
    ToolCall { name: ArchivedString, args: ArchivedVec<u8> },
    ToolResult { call_id: Uuid, output: ArchivedVec<u8> },
    Critique { target: Uuid, strategy: CritiqueStrategy },
    Summary { source_span: (Uuid, Uuid), compression_ratio: f32 },
}

#[derive(Archive, Debug, Clone, Serialize, Deserialize)]
#[archive_attr(derive(Debug))]
pub struct ThoughtNode {
    pub id: Uuid,
    pub kind: NodeKind,
    pub parents: ArchivedVec<Uuid>,
    pub embeds: ArchivedVec<SemanticLink>,
    pub timestamp: i64,
    pub metadata: ArchivedHashMap<ArchivedString, ArchivedVec<u8>>,
}

#[derive(Archive, Debug, Clone, Serialize, Deserialize)]
pub enum EdgeType { Causal, Transclude, Supersedes, Embeds }

#[derive(Archive, Debug, Clone, Serialize, Deserialize)]
pub struct SemanticLink { 
    pub target: Uuid, 
    pub edge_type: EdgeType, 
    pub weight: f32 
}

And here’s the Python-side context compiler:

# thoughtdag/assembly/strategies.py
from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import List, Set
from uuid import UUID

@dataclass
class TokenBudget:
    max_tokens: int
    system_prompt_tokens: int = 0
    
class AssemblyStrategy(ABC):
    @abstractmethod
    def assemble(self, root_id: UUID, budget: TokenBudget) -> List[dict]:
        pass

class PriorityWeightedStrategy(AssemblyStrategy):
    def assemble(self, root_id: UUID, budget: TokenBudget) -> List[dict]:
        # 1. Get topologically sorted nodes
        nodes = self._topological_sort(root_id)
        
        # 2. Apply pruning rules
        active_nodes = self._prune_superseded(nodes)
        
        # 3. Budget allocation with priority weights
        selected = []
        current_tokens = budget.system_prompt_tokens
        
        for node in active_nodes:
            node_tokens = self._estimate_tokens(node)
            if current_tokens + node_tokens <= budget.max_tokens:
                selected.append(self._node_to_message(node))
                current_tokens += node_tokens
            else:
                # Replace with summary if available
                summary = self._find_summary_for(node.id)
                if summary:
                    selected.append(self._summary_to_message(summary))
                break
                
        return selected

Best Practices

1. Treat summaries as first-class citizens: Don’t just chunk old messages—create intentional summary nodes that capture semantic essence.

2. Use SUPERMDES edges liberally: When retracting information, create a SUPERMDES edge rather than deleting nodes. This preserves the graph’s integrity.

3. Design for transclusion: Structure your agent workflows so branches can pull context from each other without copying.

4. Version your ThoughtDAG: Use structural sharing (like Git) to maintain immutable versions while allowing efficient mutations.

Common Mistakes & Anti-Patterns

Mistake 1: Treating ThoughtDAG like a database Engineers often try to query the graph directly for assembly. Don’t. The assembly engine exists for a reason—direct queries bypass the careful prioritization logic.

Mistake 2: Overusing CRITIQUE nodes CritiqueNodes are powerful but expensive. Each one doubles your context footprint. Use them sparingly and always with clear intent.

Mistake 3: Ignoring edge semantics Creating CAUSAL edges when you meant TRANSCLUDE is a subtle but common error. The difference determines whether you copy or reference context.

Mistake 4: Not versioning summaries When you create a SUMMARY node, version it alongside the pruned content. Otherwise you lose the ability to regenerate summaries as models improve.

Performance Considerations

Memory usage scales with graph size, but structural sharing keeps common cases efficient. In our production cluster:

• Insertion: O(log n) with persistent data structures
• Assembly: O(n) for topological sort, but typically processes 10-20% of total nodes due to budgeting
• Serialization: rkyv enables zero-copy deserialization, critical for high-throughput agent systems

Network overhead comes primarily from embedding vectors when using EMBEDS edges. We compress these with product quantization to ~1KB per node, adding roughly 10-15% to memory footprint.

Real-World Usage

We’ve deployed ThoughtDAG in production for a customer support agent handling 50K+ daily conversations. Key wins:

1. Reduced hallucinations: Explicit SUPERMDES edges let us cleanly retract incorrect assumptions
2. Faster convergence: TRANSCLUDE edges allow exploration branches to share context without duplication
3. Better long-term memory: SUMMARY nodes maintain semantic continuity across weeks of conversation history

Another team uses it for code generation agents where multiple implementation paths need to merge findings. The ability to surgically include/exclude context has cut their prompt engineering time by 60%.

Frequently Asked Questions (FAQ)

Q: How does this handle circular dependencies? ThoughtDAG enforces acyclicity at insertion time. Any attempt to create a cycle is rejected with a descriptive error showing the dependency chain.

Q: Can I query the graph directly for analytics? Absolutely. The graph is fully traversable. We expose both Cypher-like query interfaces and simple traversal APIs for common patterns like “find all critiques of this completion.”

Q: What happens when I exceed the token budget? The assembly engine falls back to summary nodes. If no summary exists, it uses priority-weighted truncation. You can also configure hard failures for debugging.

Q: Is this compatible with existing LangChain/LlamaIndex tools? Yes. We provide adapters that can export assembled contexts to ChatML format. The reverse (importing linear histories) is also supported via synthetic CAUSAL edge generation.

Q: How do I debug complex graph states? We built a visualization tool that renders subgraphs with edge semantics color-coded. It’s instrumental for understanding why certain context was included/excluded during assembly.

Conclusion

ThoughtDAG isn’t just another data structure—it’s recognition that LLM context has always been graph-shaped, we just forced it into arrays for convenience. By treating semantic state as a mutable, versioned DAG, we unlock capabilities that linear buffers simply cannot provide.

The performance overhead is minimal compared to the precision gains. And while the learning curve is steeper than “just append messages,” the debugging and maintenance benefits pay dividends quickly in complex agent systems.

If you’re building anything beyond simple Q&A bots, start thinking about your conversation state as a graph. ThoughtDAG gives you the tools to do it right.