Graph of Thoughts (GoT) Reasoning

Advanced multi-path reasoning beyond tree structure. Explores, combines, and synthesizes solutions.

Research Foundation

Based on: Besta et al. (2024) - "Graph of Thoughts: Solving Elaborate Problems with Large Language Models" (AAAI)

Key Insight: Tree structure limits thought combination. Graphs allow:

• Merging insights from different branches
• Feedback loops for iterative refinement
• Non-linear dependencies between thoughts
• Aggregation and distillation of multiple solutions

Performance: +62% quality improvement on synthesis tasks, +31% cost reduction via thought reuse.

GoT vs ToT vs CoT

Chain of Thought (CoT)

Problem → Step 1 → Step 2 → Step 3 → Solution
(Single linear path, fast but limited)

Tree of Thoughts (ToT)

            Problem
           /   |   \
          A    B    C    (independent branches)
         / \   |   / \
        A1 A2 B1 C1 C2  (no cross-branch combination)
         |
      Best A1

Graph of Thoughts (GoT)

            Problem
           /   |   \
          A ─── B ─── C    (branches can connect)
         / \   │   / \
        A1─┴──B1──┴─C1     (thoughts combine)
          \   │   /
           └──↓──┘
            Final       (aggregation/synthesis)

GoT Advantages:

• ✓ Combine partial solutions
• ✓ Feedback loops for refinement
• ✓ Reuse successful sub-patterns
• ✓ Synthesize novel solutions
• ✓ Multi-dimensional optimization

Core Algorithm

class GraphOfThoughts:
    """Graph-based reasoning with thought combination."""
    
    def __init__(self, num_paths=5, max_iterations=3, quality_threshold=0.85):
        self.num_paths = num_paths
        self.max_iterations = max_iterations
        self.quality_threshold = quality_threshold
        self.thought_graph = ThoughtGraph()
        self.evaluator = PathEvaluator()
    
    def reason(self, problem):
        """Main reasoning entry point."""
        
        # Phase 1: Generate multiple thought paths
        paths = self.generate_thought_paths(problem, num_paths=self.num_paths)
        
        # Phase 2: Evaluate each path independently
        evaluations = [self.evaluate_path(path) for path in paths]
        
        # Phase 3: Identify synergies between paths
        synergies = self.identify_synergies(paths, evaluations)
        
        # Phase 4: Combine promising thoughts
        combined = self.combine_thoughts(paths, synergies)
        
        # Phase 5: Evaluate combinations
        combined_evals = [self.evaluate_path(c) for c in combined]
        
        # Phase 6: Iterate with feedback loops
        refined = self.iterate_with_feedback(combined, combined_evals)
        
        # Phase 7: Aggregate final solution
        result = self.aggregate_solution(refined)
        
        # Phase 8: Execute and verify
        verified_result = self.execute_and_verify(result)
        
        return verified_result
    
    def generate_thought_paths(self, problem, num_paths):
        """Generate N diverse solution paths."""
        paths = []
        for i in range(num_paths):
            path = self.generate_diverse_path(problem, paths)
            paths.append(path)
        return paths
    
    def evaluate_path(self, path):
        """Score a thought path on multiple dimensions."""
        return {
            'feasibility': self.score_feasibility(path),
            'quality': self.score_quality(path),
            'novelty': self.score_novelty(path),
            'coverage': self.score_coverage(path),
            'confidence': self.calculate_confidence(path)
        }
    
    def identify_synergies(self, paths, evaluations):
        """Find complementary insights across paths."""
        synergies = []
        for i, path_a in enumerate(paths):
            for j, path_b in enumerate(paths):
                if i < j:
                    synergy = self.check_synergy(path_a, path_b)
                    if synergy['score'] > 0.6:
                        synergies.append(synergy)
        return synergies
    
    def combine_thoughts(self, paths, synergies):
        """Create hybrid thoughts from synergistic pairs."""
        combined = []
        for synergy in sorted(synergies, key=lambda s: s['score'], reverse=True):
            hybrid = self.create_hybrid(
                paths[synergy['path_a']], 
                paths[synergy['path_b']],
                synergy['combination_strategy']
            )
            combined.append(hybrid)
        return combined
    
    def iterate_with_feedback(self, thoughts, evaluations):
        """Refine through feedback loops."""
        refined = thoughts.copy()
        for iteration in range(self.max_iterations):
            # Identify weaknesses
            critiques = [self.critique(t, e) for t, e in zip(thoughts, evaluations)]
            
            # Generate improvements
            improvements = [self.improve(t, c) for t, c in zip(thoughts, critiques)]
            
            # Re-evaluate
            new_evals = [self.evaluate_path(imp) for imp in improvements]
            
            # Keep improvements that increased quality
            for imp, old_eval, new_eval in zip(improvements, evaluations, new_evals):
                if new_eval['quality'] > old_eval['quality']:
                    refined.append(imp)
            
            # Check if threshold met
            if max(new_evals, key=lambda e: e['quality'])['quality'] >= self.quality_threshold:
                break
                
        return refined
    
    def aggregate_solution(self, thoughts):
        """Synthesize final solution from best thoughts."""
        # Extract key insights from each thought
        insights = [self.extract_insights(t) for t in thoughts]
        
        # Find common patterns
        patterns = self.find_patterns(insights)
        
        # Synthesize unified solution
        solution = self.synthesize(patterns, insights)
        
        return solution
    
    def execute_and_verify(self, solution):
        """Execute solution and verify results."""
        result = self.execute(solution)
        verification = self.verify(result)
        
        if not verification['passed']:
            # Backtrack and try alternative
            return self.backtrack(solution, verification['issues'])
        
        return {
            'solution': solution,
            'result': result,
            'confidence': verification['confidence'],
            'verification': verification
        }

GoT Operations

1. GENERATE Diverse Paths

Generate multiple solution approaches with diversity:

Problem: [Complex problem]

Path A: [Conservative approach]
  - Uses proven methods
  - Lower risk, moderate reward
  
Path B: [Innovative approach]
  - Novel technique
  - Higher risk, potentially higher reward
  
Path C: [Hybrid approach]
  - Combines elements from multiple domains
  - Balanced risk/reward
  
Path D: [Minimal approach]
  - Simplest possible solution
  - Low cost, may miss edge cases
  
Path E: [Comprehensive approach]
  - Addresses all aspects
  - Higher cost, thorough coverage

2. EVALUATE Paths

Multi-dimensional scoring:

3. IDENTIFY Synergies

Find complementary insights:

synergy_analysis:
  - pair: [A, B]
    synergy_type: complementary
    score: 0.85
    reasoning: "A addresses speed, B addresses accuracy"
    combination_potential: high
    
  - pair: [A, C]
    synergy_type: redundant
    score: 0.30
    reasoning: "Both focus on same dimension"
    combination_potential: low
    
  - pair: [B, D]
    synergy_type: enhancing
    score: 0.72
    reasoning: "B's innovation + D's simplicity"
    combination_potential: medium

4. COMBINE Thoughts

Create hybrid solutions:

Combination Strategy 1: Best-of-Both
├── From Path A: Performance optimization
├── From Path B: Error handling approach
└── Result: Fast + Robust solution

Combination Strategy 2: Layered
├── Base Layer: Path D (minimal viable)
├── Enhancement Layer: Path B (innovation)
└── Result: Solid foundation + innovation

Combination Strategy 3: Parallel
├── Track 1: Path A for common cases
├── Track 2: Path B for edge cases
└── Result: Comprehensive coverage

5. ITERATE with Feedback

Refinement loop:

Iteration 1:
  Input: Initial combined thought
  Critique: "Missing edge case X"
  Improvement: Add edge case handling
  Score Delta: +0.15

Iteration 2:
  Input: Improved thought
  Critique: "Performance could be better"
  Improvement: Add caching layer
  Score Delta: +0.10

Iteration 3:
  Input: Further improved
  Critique: None significant
  Improvement: Minor polish
  Score Delta: +0.02

Converged at iteration 3 (diminishing returns)

6. AGGREGATE Solution

Synthesize final answer:

Insights Extracted:
├── From A: "Caching reduces load by 60%"
├── From B: "Async processing improves UX"
├── From C: "Rate limiting prevents overload"
└── From D: "Simple API is more usable"

Patterns Found:
├── Performance + UX focus
├── Prevention over cure
└── Simplicity as principle

Synthesized Solution:
"Implement async API with intelligent caching,
 rate limiting for protection, and minimal
 endpoint design for simplicity."

Confidence: 87%

Thought Graph Notation

Graph Structure

thought_graph:
  nodes:
    - id: T0
      type: problem
      content: "How to optimize system performance?"
      
    - id: T1
      type: thought
      content: "Add caching layer"
      parent: T0
      evaluation:
        feasibility: 9
        quality: 7
        score: 8.0
        
    - id: T2
      type: thought
      content: "Optimize database queries"
      parent: T0
      evaluation:
        feasibility: 8
        quality: 8
        score: 8.0
        
    - id: T3
      type: combined
      content: "Caching + Query optimization"
      combines: [T1, T2]
      synergy_score: 0.85
      evaluation:
        feasibility: 8
        quality: 9
        score: 8.5
        
    - id: T4
      type: critique
      content: "T3 doesn't handle cache invalidation"
      critiques: T3
      
    - id: T5
      type: refined
      content: "T3 + Smart cache invalidation"
      refines: T3
      incorporates: T4
      evaluation:
        feasibility: 8
        quality: 9.5
        score: 8.8
        
    - id: T6
      type: solution
      content: "Final architecture with caching, query optimization, and smart invalidation"
      aggregates: [T5]
      confidence: 87%

  edges:
    - from: T0
      to: [T1, T2]
      type: generates
      
    - from: T1
      to: T3
      type: combines
      
    - from: T2
      to: T3
      type: combines
      
    - from: T3
      to: T4
      type: critiques
      
    - from: T3
      to: T5
      type: refines
      
    - from: T4
      to: T5
      type: incorporates
      
    - from: T5
      to: T6
      type: aggregates

Node Types

Edge Types

Complete Process Template

## GoT Session: [Problem Name]

**Problem**: [Clear problem statement]
**Context**: [Background information]
**Constraints**: [Any limitations]
**Success Criteria**: [What defines success]

---

### Phase 1: Generate Paths (N=5)

| Path | Approach | Key Feature | Initial Score |
|------|----------|-------------|---------------|
| A | [Conservative] | Proven method | 7.2 |
| B | [Innovative] | Novel technique | 6.8 |
| C | [Hybrid] | Cross-domain | 7.5 |
| D | [Minimal] | Simplest viable | 6.5 |
| E | [Comprehensive] | Full coverage | 7.0 |

---

### Phase 2: Evaluate Paths

#### Path A Evaluation
- Feasibility: 9/10 (High confidence - proven approach)
- Quality: 7/10 (Medium confidence - standard result)
- Novelty: 5/10 (Low - common approach)
- Coverage: 8/10 (High - addresses most cases)
- Efficiency: 8/10 (High - optimized)
- **Total Score**: 7.4/10
- **Confidence**: 82%

#### Path B Evaluation
- Feasibility: 6/10 (Medium - unproven)
- Quality: 9/10 (Medium confidence - potential high)
- Novelty: 9/10 (High - innovative)
- Coverage: 7/10 (Medium - may miss some)
- Efficiency: 6/10 (Medium - unknown)
- **Total Score**: 7.4/10
- **Confidence**: 65%

[... continue for all paths ...]

---

### Phase 3: Identify Synergies

| Pair | Synergy Type | Score | Combination Potential |
|------|--------------|-------|----------------------|
| A + B | Complementary | 0.88 | HIGH - Proven + Innovative |
| A + C | Overlapping | 0.45 | LOW - Similar approaches |
| B + D | Enhancing | 0.72 | MEDIUM - Novel + Simple |
| C + E | Complementary | 0.81 | HIGH - Hybrid + Comprehensive |

**Top Synergies to Combine**:
1. A + B: Reliability + Innovation
2. C + E: Hybrid approach + Full coverage

---

### Phase 4: Combine Thoughts

#### Combination 1: A + B

From A: Take proven caching strategy

From B: Add innovative prediction layer

Result: "Smart caching with predictive prefetching"

Score: 8.5/10 (+1.1 from best individual)

#### Combination 2: C + E

From C: Take hybrid architecture

From E: Add comprehensive error handling

Result: "Hybrid architecture with full error coverage"

Score: 8.2/10 (+0.7 from best individual)

---

### Phase 5: Iterate with Feedback

#### Iteration 1
**Input**: Combination 1 (Smart caching)
**Critique**: "What about cache invalidation?"
**Improvement**: Add event-based invalidation
**New Score**: 8.8/10

#### Iteration 2
**Input**: Improved C1
**Critique**: "Memory usage could spike"
**Improvement**: Add LRU eviction policy
**New Score**: 9.0/10

#### Iteration 3
**Input**: Further improved
**Critique**: None significant
**Improvement**: Minor polish
**New Score**: 9.1/10

**Converged**: Diminishing returns after iteration 3

---

### Phase 6: Aggregate Final Solution

**Key Insights from All Paths**:
- Caching dramatically improves performance (A, C)
- Predictive loading reduces latency (B)
- Error handling prevents cascading failures (E)
- Simplicity improves maintainability (D)

**Patterns Identified**:
1. Performance through caching + prediction
2. Reliability through error handling
3. Maintainability through simplicity

**Synthesized Solution**:

Implement a smart caching layer with:

1. Event-based invalidation (from feedback)
2. Predictive prefetching (from B)
3. LRU eviction (from feedback)
4. Comprehensive error handling (from E)
5. Simple API design (from D)

Architecture: [Detailed design]

**Confidence**: 87%

---

### Phase 7: Verification

**Verification Checklist**:
- [ ] Addresses original problem
- [ ] Meets success criteria
- [ ] Within constraints
- [ ] No major gaps identified
- [ ] Confidence > 80%

**Result**: ✅ PASSED

---

### Summary

| Metric | Value |
|--------|-------|
| Paths Generated | 5 |
| Combinations Created | 2 |
| Feedback Iterations | 3 |
| Final Score | 9.1/10 |
| Confidence | 87% |
| Improvement over best individual | +1.9 points |

**Selected Solution**: [Final synthesized solution]

Quick Actions

• got [problem] - Run full GoT reasoning
• got-quick [problem] - Fast GoT (3 paths, 1 iteration)
• combine [thoughts] - Combine multiple thoughts
• synergy [paths] - Find synergies between paths
• feedback [solution] - Create feedback loop
• aggregate [thoughts] - Distill to essence
• got-graph - Visualize current thought graph

When to Use GoT

Use GoT When:

• ✅ Problem has multiple dimensions to optimize
• ✅ Partial solutions exist in different branches
• ✅ Combination could create better solution
• ✅ Feedback loops would improve quality
• ✅ More complex than simple decision
• ✅ Synthesis of ideas needed
• ✅ Quality > Speed

Use ToT When:

• ✅ Simple decision with discrete options
• ✅ Paths are truly independent
• ✅ Tree structure sufficient
• ✅ Faster decision needed
• ✅ Clear evaluation criteria

Use CoT When:

• ✅ Straightforward problem
• ✅ Single clear solution path
• ✅ Speed is priority
• ✅ Simple reasoning sufficient

Integration with Other Skills

GoT + Tree of Thoughts

Use ToT for initial exploration
Convert to GoT when synergies detected
Combine best of both structures

GoT + Self-Consistency

Run GoT multiple times
Vote on synthesized solutions
Higher confidence through consensus

GoT + Error Recovery

When GoT solution fails:
1. Add failure as critique node
2. Generate recovery thoughts
3. Combine with original solution
4. Re-aggregate

GoT + Self-Criticism

Use self-criticism as feedback loop:
1. Generate GoT solution
2. Apply 7-step criticism
3. Add critiques as nodes
4. Refine and re-aggregate

GoT + Meta-Reasoning

Meta-reasoning decides:
- Should I use GoT or ToT?
- How many paths to generate?
- How many iterations?
- When to stop refining?

Examples

Example 1: Architecture Decision

## GoT: API Architecture Design

**Problem**: Design API architecture for high-traffic service

### Generated Paths

| Path | Approach | Score |
|------|----------|-------|
| A | REST with caching | 7.5 |
| B | GraphQL with dataloader | 7.2 |
| C | gRPC for internal, REST for external | 8.0 |
| D | Event-driven with CQRS | 6.8 |
| E | Simple REST, optimize later | 6.5 |

### Top Synergies

**A + C**: REST caching + gRPC internal
- Score: 8.7
- Rationale: Best of both protocols

**B + D**: GraphQL + Event sourcing
- Score: 7.8
- Rationale: Real-time + flexible queries

### Combination: A + C (Selected)

External API: REST with intelligent caching

Internal API: gRPC for performance

Bridge: API Gateway for translation

### Feedback Loop

**Critique**: "Caching strategy unclear for gRPC"
**Improvement**: Add gRPC response caching
**New Score**: 9.0

### Final Solution

Hybrid architecture:
- REST for external consumers (caching)
- gRPC for internal services (performance)
- Unified API Gateway
- Smart caching at both layers

**Confidence**: 85%

Example 2: Algorithm Optimization

## GoT: Search Algorithm Optimization

**Problem**: Improve search performance for large dataset

### Generated Paths

| Path | Approach | Score |
|------|----------|-------|
| A | Inverted index | 8.2 |
| B | Trie structure | 7.5 |
| C | Vector embeddings | 7.8 |
| D | Simple caching | 6.5 |
| E | Distributed search | 7.0 |

### Synergies Found

**A + C**: Inverted index + Vector similarity
- Score: 9.0
- Hybrid: Keyword + semantic search

**A + D**: Index + Caching
- Score: 8.5
- Fast repeated queries

### Combination: A + C

Primary: Inverted index for exact matches

Secondary: Vector embeddings for similarity

Ranking: Combine both scores

### Feedback Iterations

1. Critique: "Vector search slow for large scale"
   Fix: Add approximate nearest neighbor
   Score: 9.2

2. Critique: "Memory usage high"
   Fix: Quantize vectors
   Score: 9.3

### Final Solution

Hybrid search with:
- Inverted index (exact)
- ANN vector search (semantic)
- Quantized embeddings (memory)
- Combined ranking

**Confidence**: 88%

Metrics & Evaluation

GoT Session Metrics

Quality Indicators

✅ Good GoT Session:

• Multiple synergies found
• Combinations improve on individuals
• Feedback loop converges
• High confidence final solution

❌ Poor GoT Session:

• No synergies found
• Combinations don't improve
• Feedback doesn't converge
• Low confidence

Best Practices

1. Generate diverse paths - Different approaches, not variations
2. Look for synergies early - Identify combination potential
3. Combine thoughtfully - Not all combinations are good
4. Iterate with purpose - Stop when diminishing returns
5. Aggregate carefully - Don't lose key insights
6. Verify the solution - Check against original problem
7. Document the graph - Future reference and learning

Troubleshooting

Problem: No synergies found

Cause: Paths too similar

Solution: Generate more diverse initial paths

Problem: Combinations worse than individuals

Cause: Forced combination of incompatible thoughts

Solution: Be more selective about which to combine

Problem: Feedback loop doesn't converge

Cause: Critiques not actionable

Solution: Make critiques specific and fixable

Problem: Final solution too complex

Cause: Over-aggregation

Solution: Prioritize, keep only essential elements

Remember: The power of GoT is in COMBINATION and SYNTHESIS, not just exploration. Find synergies, merge insights, create solutions greater than the sum of parts.

v2.0 Optimizations (FoT-Enhanced)

Parallel Execution

Execute multiple thought paths concurrently for 2-4x speedup:

class ParallelGraphOfThoughts(GraphOfThoughts):
    """GoT with parallel path execution."""
    
    async def reason_async(self, problem):
        """Parallel reasoning entry point."""
        
        # Phase 1: Generate paths in parallel
        paths = await asyncio.gather(*[
            self.generate_diverse_path_async(problem, exclude=paths[:i])
            for i in range(self.num_paths)
        ])
        
        # Phase 2: Evaluate all paths in parallel
        evaluations = await asyncio.gather(*[
            self.evaluate_path_async(path) for path in paths
        ])
        
        # Phase 3: Parallel synergy detection
        synergy_tasks = []
        for i in range(len(paths)):
            for j in range(i+1, len(paths)):
                synergy_tasks.append(
                    self.check_synergy_async(paths[i], paths[j])
                )
        synergies = await asyncio.gather(*synergy_tasks)
        synergies = [s for s in synergies if s['score'] > 0.6]
        
        # Phase 4: Parallel combination
        combined = await asyncio.gather(*[
            self.create_hybrid_async(
                paths[s['path_a']], 
                paths[s['path_b']]
            )
            for s in sorted(synergies, key=lambda x: x['score'], reverse=True)[:3]
        ])
        
        # Phase 5: Parallel evaluation of combinations
        combined_evals = await asyncio.gather(*[
            self.evaluate_path_async(c) for c in combined
        ])
        
        # Phase 6: Iterate with feedback (can be parallel for independent refinements)
        refined = await self.iterate_with_feedback_async(combined, combined_evals)
        
        # Phase 7: Aggregate final solution
        result = self.aggregate_solution(refined)
        
        return result

Performance Improvement:

Intelligent Caching

Cache intermediate results for reuse across similar problems:

class CachedGraphOfThoughts(GraphOfThoughts):
    """GoT with intelligent caching."""
    
    def __init__(self, cache_ttl=3600):
        super().__init__()
        self.cache = ThoughtCache(ttl=cache_ttl)
    
    def get_cached_or_generate(self, problem, cache_key=None):
        """Return cached result or generate new."""
        if cache_key is None:
            cache_key = self.compute_similarity_key(problem)
        
        cached = self.cache.get(cache_key)
        if cached:
            return cached, True  # Cache hit
        
        result = self.generate_thought_paths(problem)
        self.cache.set(cache_key, result)
        return result, False  # Cache miss
    
    def compute_similarity_key(self, problem):
        """Create semantic hash for problem similarity."""
        # Extract key concepts
        concepts = self.extract_concepts(problem)
        # Create normalized key
        return hash(frozenset(concepts))
    
    def evaluate_path(self, path):
        """Cached path evaluation."""
        cache_key = hash(str(path))
        
        cached_eval = self.cache.get(f"eval:{cache_key}")
        if cached_eval:
            return cached_eval
        
        eval_result = super().evaluate_path(path)
        self.cache.set(f"eval:{cache_key}", eval_result)
        return eval_result

Cache Benefits:

• Similar problems reuse thought paths
• Evaluation results cached per path
• Synergy analysis cached per pair
• 40-60% reduction in redundant computation

Combined Parallel + Cached

class OptimizedGraphOfThoughts(ParallelGraphOfThoughts, CachedGraphOfThoughts):
    """Best of both: parallel + cached."""
    
    async def reason_optimized(self, problem):
        """Fully optimized reasoning."""
        
        # Try cache first
        cache_key = self.compute_similarity_key(problem)
        cached_result = self.cache.get(cache_key)
        if cached_result:
            return cached_result
        
        # Parallel execution with caching
        paths = await self.generate_paths_parallel_cached(problem)
        evaluations = await self.evaluate_paths_parallel_cached(paths)
        synergies = await self.find_synergies_parallel_cached(paths, evaluations)
        
        # Continue with cached intermediate results
        combined = await self.combine_parallel_cached(paths, synergies)
        refined = await self.iterate_parallel_cached(combined)
        result = self.aggregate_solution(refined)
        
        # Cache final result
        self.cache.set(cache_key, result)
        
        return result

Command Flags

got [problem]                    # Standard GoT
got [problem] --parallel         # Parallel execution (2-4x faster)
got [problem] --cached           # Use cache (40-60% reduction)
got [problem] --optimized        # Both parallel + cached
got [problem] --sequential       # Force sequential (debugging)
got [problem] --no-cache         # Skip cache (fresh analysis)

Performance Summary (v2.0)

v2.0 Changelog:

• Added parallel execution for all phases (3-4x faster)
• Added intelligent caching for similar problems (40-60% reduction)
• Combined optimized mode for best performance
• New CLI flags for execution control