Think-on-Graph: Knowledge Graph를 활용한 LLM의 깊고 책임감 있는 추론

# Think-on-Graph 핵심 루프 pseudo-code

def think_on_graph(question, kg_client, llm, max_depth=3, beam_width=3):
    # 1. 질문에서 시작 엔티티 추출
    start_entities = llm.extract_entities(question)
    
    paths = [(entity, []) for entity in start_entities]  # (현재노드, 경로)
    
    for depth in range(max_depth):
        candidates = []
        for current_node, path in paths:
            # 2. KG에서 현재 노드의 관계 후보 조회
            relations = kg_client.get_relations(current_node)
            
            # 3. LLM이 관련 관계 선택
            prompt = f"""
질문: {question}
현재 탐색 노드: {current_node}
현재까지 경로: {path}
사용 가능한 관계들: {relations}

위 관계들 중 질문에 답하기 위해 탐색해야 할 관계를 선택하세요.
관련 없으면 '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이 현재 후보들로 답 가능한지 판단
        answer_check_prompt = f"""
질문: {question}
탐색된 경로와 엔티티들: {candidates}

현재 정보로 질문에 답할 수 있나요? 
답할 수 있으면 답변을 제시하고, 없으면 'continue'를 출력하세요."""
        result = llm.call(answer_check_prompt)
        
        if result != 'continue':
            return result, candidates  # 답변 + 근거 경로 반환
        
        paths = candidates[:beam_width]  # beam 유지
    
    return llm.call(f"질문: {question}\n수집된 정보: {paths}\n최종 답변:"), paths