궤적 보상을 넘어: 그래프 모델링을 통한 에이전틱 검색(Agentic Search)의 단계별 신용 할당

에이전틱 검색(Agentic Search)에서 궤적 수준(trajectory-level)의 결과 보상은 개별 단계의 행동 기여도를 정량화하는 데 실패하며, 기존의 단계별(step-level) 보상 방법들은 일반적으로 비용이 많이 드는 트리 샘플링(tree sampling)에 의존합니다. 우리는 세상의 지식을 잠재적 세계 그래프(latent world graph)로 보고, 각 정보 검색(IS) 태스크를 잠재적 태스크 그래프(latent task graph) 내에서의 검색으로 간주하며, 여기서 효과적인 단계는 정답 노드(answer node)를 향해 그래프 상의 진전을 이루어야 합니다. 이러한 사전 지식을 바탕으로, 우리는 그래프 거리 기여 보상(Graph-Distance Contribution Reward, GDCR)을 제안합니다. 이는 학습 시점의 개체-관계(Entity-Relation, ER) 그래프에서 정답 노드까지의 거리를 기준으로 새로 검색되거나 새로 인용된 개체(entity)에 점수를 부여하는 단계별 프로세스 보상(process reward)입니다. 나아가 우리는 GDCR을 단계별 이점(step-level advantages)으로 변환하고 이를 궤적 수준의 결과 이점(trajectory-level outcome advantages)과 결합하는 단계별 이점 정책 최적화(Step Advantage Policy Optimization, SAPO)를 제안합니다. 네 가지 도전적인 벤치마크에 대한 실험을 통해 우리 방법의 효과를 검증합니다.