CHAPTER 18

🔗 Graph-of-Logic

Structured Inference Graphs for LLM Reasoning

Learning Objectives:
Learn how to structure LLM reasoning as explicit inference graphs. Understand nodes (claims), edges (dependencies), and confidence propagation. Implement medical diagnosis as graph-of-logic.

Original Paper

Citation:
Alotaibi, F., Kulkarni, A., & Zhou, D. (2024, December). "Graph of Logic: Enhancing LLM Reasoning with Graphs and Symbolic Logic." In 2024 IEEE International Conference on Big Data (BigData) (pp. 5926-5935). IEEE.

DOI: 10.1109/BigData62323.2024.10825694
Conference: IEEE BigData 2024
Authors: Fatima Alotaibi, Ananya Kulkarni, Denny Zhou

From Tree-of-Thought to Graph-of-Logic

While Tree-of-Thought explores multiple reasoning paths, Graph-of-Logic adds explicit logical structure. Nodes represent claims, edges represent logical dependencies (AND, OR, NOT, IMPLIES), and confidence propagates through the graph.

Key Innovation (Alotaibi et al., 2024):
"By representing LLM reasoning as an explicit inference graph with symbolic logic operators on edges, we enable: (1) transparent reasoning paths, (2) confidence propagation, (3) conflict detection, and (4) full explainability for high-stakes decisions."

Graph-of-Logic Structure

Medical Diagnosis as Graph-of-Logic Diagnosis: Sepsis Fever conf: 0.9 Infection conf: 0.8 Low BP conf: 0.85 AND AND AND Temp: 39.5C conf: 0.95 WBC: 15K conf: 0.88 Blood culture positive: 0.92 BP: 85/50 conf: 0.90 Confidence Propagation (Bottom-Up) Evidence confidences: Temp(0.95), WBC(0.88), Culture(0.92), BP(0.90) Combined (AND): min(0.95, 0.88, 0.92, 0.90) = 0.88

Figure 1 (Alotaibi et al., 2024): Graph-of-Logic for medical diagnosis with confidence propagation

Key Components

Component Description Example
Claim Nodes Represent propositions or diagnoses "Patient has sepsis", "Fever > 38.3C"
Evidence Nodes Factual evidence supporting claims "Temp: 39.5C", "WBC: 15K", "Positive culture"
Logic Edges Operators: AND, OR, NOT, IMPLIES Fever AND Infection AND LowBP → Sepsis
Confidence 0.0-1.0 score for each node Fever: 0.9, combined diagnosis: 0.88

Confidence Propagation Rules

How confidence flows through logic operators:

# Graph-of-Logic confidence propagation
AND operator: conf(A AND B) = min(conf(A), conf(B))
  Example: min(0.9, 0.8) = 0.8 (chain is as weak as weakest link)

OR operator: conf(A OR B) = max(conf(A), conf(B))
  Example: max(0.9, 0.8) = 0.9 (at least one must be true)

NOT operator: conf(NOT A) = 1 - conf(A)
  Example: 1 - 0.7 = 0.3 (if A is 70% likely, NOT A is 30% likely)

IMPLIES: conf(A IMPLIES B) = (1 - conf(A)) + (conf(A) * conf(B))
  Example: if fever (0.9) implies sepsis, then:
           conf = (1 - 0.9) + (0.9 * 0.8) = 0.1 + 0.72 = 0.82
            

Implementation: Medical Diagnosis Graph

# Graph-of-Logic implementation for sepsis diagnosis
from anthropic import Anthropic
import json

client = Anthropic()

class GoLNode:
    def __init__(self, claim, node_type="claim"):
        self.claim = claim
        self.node_type = node_type  # "claim", "evidence"
        self.confidence = 0.0
        self.children = []  # Evidence nodes supporting this claim
        self.operator = None  # AND, OR, NOT

def gol_medical_diagnosis(patient_symptoms):
    """Diagnose using Graph-of-Logic reasoning"""

    # Step 1: Extract symptoms and evidence
    prompt = f"""
Patient presentation: {patient_symptoms}

Identify EVIDENCE NODES (factual observations):
- Format: "Observation: [description], confidence: 0.X"
- Example: "Fever: 39.5C, confidence: 0.95"

List all evidence nodes with confidence scores."""

    evidence_response = client.messages.create(
        model="claude-3-5-sonnet-20241022",
        max_tokens=400,
        messages=[{"role": "user", "content": prompt}]
    )
    evidence_nodes = evidence_response.content[0].text

    # Step 2: Build claim hierarchy
    claim_prompt = f"""
Given these evidence nodes:
{evidence_nodes}

What are the possible DIAGNOSES (claim nodes)?
For each diagnosis, specify:
1. The claim (e.g., "Sepsis")
2. Required evidence (e.g., "Fever AND Positive Culture AND Low BP")
3. Logic operator combining evidence (AND/OR)
4. Expected confidence

Format:
DIAGNOSIS: [name]
EVIDENCE_LOGIC: [claim logic]
OPERATOR: [AND/OR]
"""

    claims_response = client.messages.create(
        model="claude-3-5-sonnet-20241022",
        max_tokens=500,
        messages=[{"role": "user", "content": claim_prompt}]
    )
    claims = claims_response.content[0].text

    # Step 3: Propagate confidence through graph
    propagation_prompt = f"""
Given the evidence and claims:

Evidence: {evidence_nodes}
Claims: {claims}

For EACH diagnosis:
1. List supporting evidence
2. Calculate confidence using logic operators:
   - AND: min(conf1, conf2, conf3...)
   - OR: max(conf1, conf2)
3. Determine final diagnosis confidence

Output as JSON:
{
  "diagnosis": "Sepsis",
  "evidence": ["Fever: 0.95", "Low BP: 0.90", "Positive culture: 0.92"],
  "logic": "AND",
  "confidence": 0.90,
  "clinical_severity": "CRITICAL"
}
"""

    propagation_response = client.messages.create(
        model="claude-3-5-sonnet-20241022",
        max_tokens=600,
        messages=[{"role": "user", "content": propagation_prompt}]
    )
    final_diagnosis = propagation_response.content[0].text

    return {
        "evidence": evidence_nodes,
        "claims": claims,
        "final_diagnosis": final_diagnosis
    }


# Example usage
result = gol_medical_diagnosis(
    patient_symptoms="""
    65-year-old admitted with fever 39.5C, hypotensive (BP 85/50),
    tachycardic (HR 110), elevated WBC 15K, positive blood culture,
    altered mental status, severe malaise.
    """
)

print("GRAPH-OF-LOGIC DIAGNOSIS")
print("=" * 60)
print(result["final_diagnosis"])
            

Advantages Over Other Methods

Method Transparency Logic Handling Explainability
Chain-of-Thought Step-by-step text Implicit in language High but informal
Logic-LM Symbolic formulas Explicit, provably correct Very high, formal
Graph-of-Logic Graph structure + semantics Explicit logic operators Very high, visual + formal

When to Use Graph-of-Logic

Perfect For:

  • ✓ Multi-factor diagnosis (medical, forensic, criminal investigation)
  • ✓ Reasoning with multiple competing hypotheses
  • ✓ Situations requiring confidence tracking through complex logic
  • ✓ High-stakes decisions needing full auditability
  • ✓ Cases where you need to show "confidence in the overall conclusion"
Compared to Competitors:
vs CoT: More structured, explicit logic operators instead of natural language reasoning
vs Logic-LM: Focuses on multi-path reasoning and confidence propagation, not hard constraints
vs CoVe: Adds structural reasoning in addition to verification

Key Takeaways

  • Graph-of-Logic = nodes (claims/evidence) + edges (logic operators) + confidence
  • Explicit logic: AND, OR, NOT, IMPLIES operators on edges
  • Confidence propagation: Bottom-up aggregation using min/max rules
  • Multi-hypothesis reasoning: Explore multiple diagnoses simultaneously
  • Fully explainable: Show exactly which evidence supports which diagnosis
  • Perfect for medical AI: Complex multi-factor diagnostics with confidence
Original Paper:
Alotaibi, F., Kulkarni, A., & Zhou, D. (2024, December). "Graph of Logic: Enhancing LLM Reasoning with Graphs and Symbolic Logic." In 2024 IEEE International Conference on Big Data (BigData) (pp. 5926-5935).
Available via IEEE: https://doi.org/10.1109/BigData62323.2024.10825694

🎯 Ready for Assessment?

10 Questions
~10 mins
70% to Pass
Take Quiz Now →