Think-on-Graph: Deep and Responsible Reasoning of Large Language Model with Knowledge Graph

# Think-on-Graph core loop pseudo-code

def think_on_graph(question, kg_client, llm, max_depth=3, beam_width=3):
    # 1. Extract starting entities from the question
    start_entities = llm.extract_entities(question)
    
    paths = [(entity, []) for entity in start_entities]  # (current node, path)
    
    for depth in range(max_depth):
        candidates = []
        for current_node, path in paths:
            # 2. Retrieve relation candidates for the current node from KG
            relations = kg_client.get_relations(current_node)
            
            # 3. LLM selects relevant relations
            prompt = f"""
Question: {question}
Current exploration node: {current_node}
Path so far: {path}
Available relations: {relations}

From the above relations, select the ones to explore in order to answer the question.
If none are relevant, output 'none'."""
            selected_relations = llm.call(prompt)
            
            for rel in selected_relations[:beam_width]:
                next_nodes = kg_client.get_neighbors(current_node, rel)
                for node in next_nodes:
                    candidates.append((node, path + [(current_node, rel, node)]))
        
        # 4. LLM determines whether the current candidates are sufficient to answer
        answer_check_prompt = f"""
Question: {question}
Explored paths and entities: {candidates}

Can the question be answered with the current information?
If yes, provide the answer; otherwise, output 'continue'."""
        result = llm.call(answer_check_prompt)
        
        if result != 'continue':
            return result, candidates  # Return answer + supporting paths
        
        paths = candidates[:beam_width]  # Maintain beam
    
    return llm.call(f"Question: {question}\nCollected information: {paths}\nFinal answer:"), paths