GraphOmakase

26년 9월 2주차 그래프 오마카세

CLAUSE: Agentic Neuro-Symbolic Knowledge Graph Reasoning via Dynamic Learnable Context Engineering

ICLR ProceedingsYang Zhao, Chengxiao Dai, Wei Zhuo, Yue Xiu, Dusit Niyato

Keywords

Agentic Resource-Aware KG Reasoning
Budget-aware Dynamic Context Engineering
Constrained Multi-Agent RL

지식그래프를 활용한 질의응답에서 중요한 문제는 더 이상 관련 지식을 찾을 수 있는가에만 머물지 않습니다. multi-hop 질문에서는 어떤 엔티티와 관계를 따라갈지, 어디까지 서브그래프를 확장할지, 그중 무엇을 최종 프롬프트에 남길지에 따라 정확도와 실행 비용이 함께 달라집니다.
고정된 k-hop 확장은 필요한 근거를 놓치지 않는 대신 불필요한 triple까지 끌어올 수 있고, 반대로 탐색 범위를 지나치게 줄이면 답을 뒷받침하는 경로 자체를 놓칠 수 있습니다. 결국 그래프에서 무엇을 찾느냐만큼, 어떤 컨텍스트를 어떤 비용으로 구성하느냐가 중요한 문제가 됩니다.
최근에는 이 과정을 정적인 retrieval rule보다 질문에 따라 달라지는 순차적 의사결정으로 다루려는 흐름이 나타나고 있습니다. Adaptive RAG는 질문의 난이도나 confidence에 따라 retrieval 여부와 빈도를 조정하고, ReAct나 KG-Agent 같은 agentic 방식은 검색과 추론을 여러 단계에 걸쳐 반복합니다.
그래프 기반 방법 역시 고정된 neighborhood를 한 번 가져오는 것에서 벗어나, 경로를 따라가거나 필요한 구조를 점진적으로 구성하는 방향으로 확장되고 있습니다. 다만 이런 유연성이 커질수록 비용도 함께 커질 수 있다는 점입니다. 더 오래 탐색하고 더 많이 숙고할수록 정확도가 좋아질 수 있지만, 그만큼 interaction step과 token도 함께 늘어날 수 있습니다.
이번 주 오마카세로 전달해드릴 논문에서 제안하는 CLAUSE는 바로 이 지점에서 출발합니다. 다음 접근은 탐색 규칙을 하나 더 만드는 것이 아니라, 컨텍스트 구조 자체를 예산이 있는 의사결정 문제로 바꾸는 것입니다.

💡

다음 한 번의 탐색이 그 비용을 지불할 만큼 가치가 있는가?

CLAUSE는 그래프를 편집하고, 경로를 탐색하고, 최종 근거를 선택하는 각각의 단계를 학습 가능한 policy로 만듭니다. 여기에 그래프 엣지 조정(Edit) & 상호작용 단계(Interaction) & 토큰 선택(selected token)의 세 자원의 예산과 가격을 함께 두어, 한 단계 더 탐색해서 얻을 정보가 그 비용을 지불할 만큼 가치 있는지를 매 순간 판단하도록 학습합니다.

실제 KGQA & GraphRAG 시스템에서는 정확도만큼이나 탐색량, 상호작용 횟수, 최종 프롬프트 크기가 중요합니다.
저자들의 문제의식은 명확합니다. 기존 방식은 hop depth, degree cap, top-k처럼 사람이 미리 정한 값에 크게 의존하는 반면, 에이전트 기반 방식은 multi-step deliberation이 길어질수록 실행 비용이 함께 증가할 수 있다는 것입니다.
CLAUSE는 이 문제를 제약적 마르코프 결정 과정(CMDP)으로 정식화합니다. 본문의 수식 1을 참고해보면 정확도(R_acc)를 최대화하되, 그래프 엣지 편집량(C_edge), 상호작용 스텝 수(C_lat), 선택된 토큰 수(C_tok)에 각각 예산을 두고 이 예산 제약 아래에서 task reward를 최대화하도록 policy를 학습합니다.
- 여기에서 C_lat은 실제 밀리초 단위의 실행 시간을 의미하는 게 아니라, 상호작용 단계 수를 이용해 지연을 대신 측정하는 값입니다. 따라서 latency budget은 실제 wallclock time의 개념과 같은 것이 아닙니다.

CLAUSE는 세 개의 에이전트가 순차적으로 협업하는 구조입니다.
- Subgraph Architect (anchor & edit): 질문과 관련된 후보 엔티티에서 출발해 어떤 edge를 그래프에 추가하거나 제거할지 결정합니다. ADD/DELETE/STOP을 결정하며 작업 서브그래프를 편집합니다.
- Path Navigator (traverse): 현재 서브그래프 위에서 어떤 경로를 계속 따라갈지 판단합니다. CONTINUE/BACKTRACK/STOP으로 추론 경로를 탐색합니다.
- Context Curator (curate): 지금까지 모인 후보 근거 중 실제 reader LLM에 전달할 근거 스니펫을 고릅니다. 후보 풀에서 SELECT/STOP을 반복하며 최종 컨텍스를 만듭니다.
다음 구조에서 중요한 건 단순히 에이전트를 세 가지로 세분화했다는 것 보다, edit → edge cost, traverse → interaction-step cost, curate → token cost처럼 각 단계에서 발생하는 비용의 출처를 분리한다는 것입니다.
세 단계의 공통점은 엣지 하나를 더 추가하고, 1 hop을 더 이동하고, 스니펫 하나를 더 선택할 가치가 있는가를 학습된 STOP policy가 판단한다는 것입니다.
- 기존에는 사람이 미리 정한 h-hop, top-k 의 값으로 처리하는 경우가 많았습니다. 하지만 CLAUSE는 실제 탐색량과 종료 시점을 질문마다 다르게 판단하도록 그 policy를 학습하였습니다.
- 여기에서 학습된 STOP policy가 모든 고정값 설정을 없앴다는 의미는 아니라는 점입니다. Appendix D에서 설명하듯, 기본 설정에서 traversal & reranker & curator & fallback & token 등을 제안하고 데이터셋(HotpotQA)에 따라 더 고정시켜둔 부분도 있습니다.
따라서 CLAUSE가 학습하는 것은 무한한 검색 공간에서 어디까지 갈 것인가가 아니라, 미리 주어진 검색 공간과 상한 안에서 실제로 얼마나 사용할 것인가에 가깝습니다. 그로부터 왜 비용이 증가하였는지에 대해 어느 단계의 행동 때문인지 추적하고 구분할 수 있게 됩니다.

비용을 패널티가 아닌 가격으로 다루는 방법

위의 세 에이전트를 조율하는 학습 알고리즘으로 본 논문의 핵심인 LC-MAPPO (Lagrangian-Constrained Multi-Agent PPO)를 제안합니다.
LC-MAPPO 알고리즘은 계속 탐색해나갈 이득이 그 자원의 현재 가격보다 큰지를 물어보면서 엣지 편집 수, 상호작용 스텝 수, 그리고 선택된 토큰 수라는 세 자원에 각각 가격을 매기는 파라미터 λ를 둡니다.
- 본문의 수식 2를 참고해보면, 정확도 보상에서 각 행동이 소비한 자원의 가격을 차감한 값을 policy 학습에 사용합니다. 여기에서 각 자원의 λ는 고정된 penalty가 아니라 학습 중 평균 자원 사용량이 해당 예산을 넘으면 커지고, 예산보다 낮으면 작아지는 방향으로 점진적 최적화해나가는 projected dual ascent를 수행합니다.
- 직관적으로는 정답을 잘 맞히면 보상을 받지만 그래프, 탐색 단계, 토큰을 사용하는 만큼 비용도 함께 부과되는 구조입니다. 특정 자원을 예산보다 자주 많이 사용하면 그 자원의 가격을 높이고, 이후에는 정책이 그 자원을 추가로 사용하는 행동을 더 신중하게 선택하도록 학습합니다.
더 나아가 Appendix G에서는 다음 가격에 한계가치라는 개념으로 해석합니다. 표준적인 조건이 성립하는 최적점 λ* 에 대해 특정 예산을 조금 더 늘렸을 때 성능이 얼마나 더 좋아질 여지가 있는지로 바라봅니다.
- 즉, 현재 최적점과 예산 설정 근처에서 해당 비용이 상대적으로 크다면 그 예산을 조금 더 허용시켰을 때 얻을 수 있는 성능적 이득이 크다고 볼 수 있다는 것입니다.
- 다만 이 해석은 논문에서 설정한 regulariy/KKT 조건 하의 해석입니다. 학습 도중의 임의의 λ 값이 항상 이런 의미를 갖는 것은 아닙니다.

학습 때는 같이, 실제 실행은 각자 판단하는 규칙

세 에이전트를 완전히 따로 학습시키는 것도 아닙니다. 학습 단계에서는 하나의 centralized critic이 세 에이전트의 행동을 함께 보면서 task 성능, edge 사용량, step 사용량, 그리고 token 사용량을 각각 평가합니다.
그리고 특정 에이전트의 행동이 전체 결과에 얼마나 기여했는지도 분리해서 추정합니다. 직관적으로 하나의 에이전트가 독단적인 다른 선택을 했다면 어떻게 결과가 달라지는지를 보고자 합니다. 논문에서는 이를 COMA(Counterfactual Multi-Agent Policy Gradients) 스타일의 counterfactual advantage로 구현합니다.
반면 실제 추론 단계에서는 centralized critic가 필요하지 않고, CTDE (Centralized Training with Decentralized Execution) 방식을 따라 각 에이전트가 학습된 자신의 정책에 따라 움직입니다.
여기에 예산의 상한을 두는 cap mode와 그 가격에 상대적으로 더 많은 자원을 투입할지를 비교하고 결정하는 price mode로 나누어 체크포인트를 추론하도록 합니다.

실험은 세 벤치마크 (HotpotQA, MetaQA, FactKG)에서 진행하였습니다. 논문에서 특히 강조하는 MetaQA-2hop 결과를 확인해보면, CLAUSE는 GraphRAG보다 EM@1이 39.3점 높으면서, normalized latency는 약 18.6%, edge growth는 약 40.9% 낮았습니다.

정확도 뿐만 아니라 실제로 예산을 잘 지키는지도 실험으로 비교하였습니다. MetaQA의 한 설정(edge budget 0.5, latency budget 0.7)에서 MAPPO, Fixed-Penalty PPO, RCPO, LC-MAPPO의 feasibility rate를 비교한 결과를 보여줍니다.
1번째 플롯에서 해당 rate는 MAPPO의 0.117에서 .340으로 약 191% 증가하였습니다. 2번째 플롯의 Latency violation에서도 0.880에서 0.577로 분명한 개선을 보여줍니다. 하지만 LC-MAPPO의 feasibility가 0.340 즉 34%라는 부분도 주목해야 합니다.
즉, 기존 방식보다 큰 개선은 보여주었으나, 모든 쿼리에서 학습된 policy 자체가 예산을 만족한다는 의미는 아닙니다. 실제 배포에서 확실한 상한이 필요하다면 별도의 mode가 수행하는 역할과 구분해서 볼 필요가 있음을 알 수 있습니다.

세 에이전트 중 하나를 제거하면서 그 기여도를 분석한 ablation 실험에서, Subgraph Architect를 제거하면 EM은 87.3에서 74.8로 떨어지고 edge usage는 1.44배 증가합니다. 마찬가지로 path navigator를 제거한 경우에도 정확도가 떨어지고 lattency 및 edge 사용량이 증가하며, context curator를 제거했을 때도 동일한 패턴이 관찰되었고, 기존의 MAPPO 및 고정된 λ를 사용한 경우에도 성능과 예산 측면이 함께 약화됩니다.
적어도 다음 실험 설정에서는 서브그래프 구성 – 경로 탐색 – 근거 선택이라는 3단계의 공동 제어와 자원 가격을 학습 중에 조절하는 방식이 각각 정확도/효율성 측면에서 trade-off라는 근거로 볼 수 있습니다. 다만 이것이 Subgraph Architect가 모든 환경에서 가장 중요한 에이전트라는 해석은 강할 수 있습니다.

마지막 case study에서도 질문 쿼리에 대한 CLAUSE의 세 에이전트 역할을 직관적으로 확인해볼 수 있습니다. 하지만 논문에서 상세히 제공되는 경로가 비교적 단순한 2-hop 쿼리라는 부분에서 더 긴 경우나 노이즈 엣지 등이 섞였을 때 해당 policy가 어떻게 실패하고 어떻게 회복하는지를 보여주진 않습니다.

💡

다음 한 번의 탐색이 그 비용만큼 가치 있는지를 학습하고 판단하는 시스템이 CLAUSE의 핵심.

CLAUSE가 흥미로운 지점은 GraphRAG에 강화학습을 붙였다는 사실 자체보다, 컨텍스트 구조를 하나의 예산이 있는 의사결정 문제로 다시 정의했다는 데 있습니다. hop 길이나 top k와 같은 제한을 cap으로 남겨두고 그 안에서 얼마나 그래프를 확장할지, 몇 단계 더 탐색할지, 어떤 근거를 최종 컨텍스트에 넣으면서 멈출지 등을 policy가 학습하도록 역할을 분담합니다.
또한 자원을 많이 쓰면 그 자원을 더 비싸게 만들어 비용적인 측면에서 사용을 줄이는 방식을 구현하여, 실제 GraphRAG 시스템에서 정확도뿐 아니라 탐색량과 프롬프트 비용까지 함께 관리해야 한다면, 컨텍스트에도 가격을 매긴다는 관점은 충분히 참고할 만합니다.
몇 가지 한계점도 구분해보면,
- 학습 구조가 세 agent와 여러 cost head, 중앙 critic, 자원별 가격 조정까지 함께 학습해야 하기때문에 단순 RAG보다 복잡합니다. Appendix F에서 에이전트 개수와 계산량이 비례하지 않는다고 분석하나, 주로 복잡도 분석과 스케일링 augment 관점입니다.
- 또한 GraphRAG나 KG-Agent 같은 주요 baseline과 비교한 실제 wallclock time 결과와 수렴성에 대한 지표는 제시되지 않았으며, 일정한 조건 하 수렴한다고 분석하였으나 여러가지 가정이 따라붙고 있습니다. 따라서 실제 MARL (멀티에이전트 강화학습) 환경에서 무조건 수렴한다는 보장은 없습니다.
- Reader LLM (Qwen3-32B, LLaMA3.3-70B, GTP-OSS-120B)의 추가실험에서 일관된 성능 우위가 관찰되어 reader backbone 변화에 대한 일정 수준의 robustness는 확인되지만 배포 환경까지의 안정성까지 보장하는 것은 아닙니다.
정리하면, CLAUSE는 GraphRAG의 검색을 고정된 hop이나 top-k의 문제가 아니라, 매 단계에서 얻을 정보와 그 비용을 비교하는 의사결정 문제로 다시 바라봅니다. 앞으로 복잡한 질의와 실제 서비스 환경에서도 이 방식의 안정성이 확인된다면, GraphRAG 역시 탐색 성능뿐 아니라 그 성능을 얻기 위해 지불한 비용까지 함께 평가하는 방향으로도 확장될 수 있을 것 같습니다.