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:

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:

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

Type	Description	Example
problem	Initial problem statement	"Optimize performance"
thought	Single solution approach	"Add caching"
combined	Merged from multiple thoughts	"Caching + Indexes"
critique	Identifies weaknesses	"Missing invalidation"
refined	Improved based on critique	"Add smart invalidation"
solution	Final synthesized answer	"Complete architecture"

Edge Types

Type	Description
generates	Creates new thought
combines	Merges thoughts
critiques	Identifies issues
incorporates	Includes feedback
refines	Improves thought
aggregates	Synthesizes solution
backtracks	Returns from dead end

---

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

Metric	Description	Target
Paths Generated	Number of initial paths	5-7
Synergies Found	Complementary pairs	2-4
Combinations Created	Hybrid solutions	2-3
Feedback Iterations	Refinement rounds	2-4
Final Score	Quality of solution	>8.5
Confidence	Certainty level	>80%
Improvement	Over best individual	>1.0

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:

Operation	Sequential	Parallel	Speedup
Generate 5 paths	5.0s	1.2s	4.2x
Evaluate 5 paths	5.0s	1.0s	5.0x
Synergy check (10 pairs)	10.0s	2.0s	5.0x
Total (typical session)	25.0s	6.5s	3.8x

Intelligent Caching

Cache intermediate results for reuse across similar problems: