graph-of-thoughts

What this skill does

# 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

```python
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:

| Dimension | Weight | Description |
|-----------|--------|-------------|
| Feasibility | 0.25 | Can this be implemented? |
| Quality | 0.25 | How good is the solution? |
| Novelty | 0.15 | Is this innovative? |
| Coverage | 0.20 | Does it address all aspects? |
| Efficiency | 0.15 | Resource usage |

### 3. IDENTIFY Synergies

Find complementary insights:

```yaml
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
    reason