기술 요약: HiGram – 경로 수준 국소화 및 재작성을 통한 LLM 에이전트용 계층적 그래프 메모리

문제 정의

장기 추론 에이전트는 새로운 사실, 수정 사항, 외부 피드백이 도착함에 따라 효율적으로 업데이트될 수 있는 메모리 시스템을 필요로 합니다. 최근의 그래프 기반 메모리 접근 방식들은 멀티홉(multi-hop) 검색을 위한 구조적 조직화를 제공하지만, 다음과 같은 두 가지 결정적인 한계에 직면해 있습니다:

1. 평면 구조에서의 비효율적인 검색: 기존 방식은 흔히 평면적인 그래프에 메모리를 저장합니다. 역사적 메모리가 축적됨에 따라 관련 증거를 검색하려면 전체 그래프를 탐색해야 하며, 이는 상당한 양의 무관한 컨텍스트를 도입하고 증거 선택 비용을 증가시킵니다.
2. 비효효율적인 독립적 업데이트: 현재의 방식은 일반적으로 메모리 단위를 독립적으로 업데이트합니다. 그러나 답변은 고립된 사실보다는 서로 연결된 증거 경로들에 의해 뒷받침되는 경우가 많습니다. 독립적인 단위별 업데이트는 관련 증거를 누락하거나 오래된 의존 관계를 그대로 남겨둘 수 있으며, 이는 과도한 토큰 소비와 업데이트 효율성 저하를 초래하는 반복적인 전역 재작성을 필요로 합니다.

식별된 핵심 문제는 메모리 조직/업데이트의 입도(granularity)와 추론에 필요한 증거 구조의 입도 사이의 불일치입니다.

방법론: HiGram

저자들은 세 가지 통합된 단계를 통해 이러한 문제를 해결하기 위해 설계된 진화하는 계층적 그래프 메모리 프레임워크인 HiGram을 제안합니다.

1. 계층적 그래프 메모리 조직

HiGram은 메모리를 coarse-to-fine(조대-미세) 아키텍처($G_t = (V_t, E_t)$)로 구조화합니다:

• 상위 레벨 노드(Upper-level Nodes): 이들은 주체 노드(subject nodes), 객체 카테기 노드(object-category nodes), 컨텍스트 노드(context nodes)를 포함합니다. 이들은 세부적인 상세 정보를 저장하지 않고 역할에 따라 사실적 메모리를 조직하는 추상화 계층 역할을 합니다.
• 메모리 유닛(MemoryUnits, $M_t$): 이 노드들은 미세한 사실 정보(주체, 관계, 객체, 타임스탬프, 신뢰도, 상태 등)를 저장합니다.
• 에지(Edges): 상위 레벨 노드와 메모리 유닛 사이의 연결뿐만 아니라, 증거 체인을 나타내기 위해 메모리 유닛들을 연결하는 명시적인 의존성 에지($E_{dep}$)가 존재합니다.
• 이점: 이러한 분리는 시스템이 특정 메모리 유닛에 접근하기 전에 상위 레벨 노드를 통해 관련 영역을 식별할 수 있게 하여, 전체 그래프를 불필요하게 탐색하는 것을 줄여줍니다.

2. MicroGraph 기반 경로 수준 국소화

재작성하기 전에, HiGram은 검색 공간을 특정 국소 영역으로 좁힙니다:

• MicroGraph 구축: 글로벌 그래프는 주체 노드와 객체 카테고리 노드의 쌍으로 정의되는 MicroGraph($B_{t,j}$)들로 분할됩니다. 이는 특정 메모리 유닛, 컨텍스트 노드 및 의존성 에지를 포함하는 국소 영역 역할을 합니다.
• 앵커 추출(Anchor Extraction): 쿼리와 업데이트가 주어지면, 시스템은 임시 메모리 유닛을 구축하고 앵커(주체 및 객체 카테고리 노드)를 추출하여 후보 MicroGraph를 식별합니다.
• 지원 서브그래프(Support Subgraph): 상위 $K_g$개의 관련 MicroGraph가 선택되어 지원 서브그래프($G_{S,t}$)를 형성합니다.
• 경로 식별(Path Identification): 이 서브그래프 내에서 시스템은 후보 증거 경로($P_{cand}$)를 열거하고, 속성 일치, 의존성 일관성, 시간적 유효성을 고려하여 이들의 관련성을 점수화합니다. 가장 높은 점수를 받은 경로($\hat{P}_t$)가 **재작성 영역(rewrite region)**으로 선택됩니다.

3. 협응된 재작성(Coordinated Rewriting)

증거 경로가 국소화되면, HiGram은 고립된 단위 수정 대신 협응된 업데이트를 수행합니다:

• 단위 내 재작성(Intra-unit Rewriting): 새로운 증거를 바탕으로 영향을 받는 메모리 유닛들의 내부 상태(예: 상태, 유효 시간)를 업데이트합니다. 새로운 사실은 활성 상태로 커밋되며, 기존 사실은 일관성을 위해 수정됩니다.
• 단위 간 재작성(Inter-unit Rewriting): 업데이트된 메모리 유닛과 연결된 의존성 구조를 검사합니다. 만약 업데이트된 유닛이 더 이상 하위 결론을 뒷받침하지 않는다면, 해당 의존 메모리 유닛은 '오래된 것(outdated)'으로 표시됩니다. 이는 증거 구조가 유효하게 유지되도록 보장하며, 지원되지 않는 파생 결론이 지속되는 것을 방지합니다.
• 결과: 프레임워크는 제한된 영역 내에서 메모리 상태와 의 dependency 구조를 동시에 업데이트하여, 반복적인 전역 검색을 피합니다.

주요 기여

1. 계층적 그래프 프레임워크: 축적된 역사적 메모리로 인해 발생하는 무관한 컨텍스트와 국소화 비용을 줄이는 coarse-to-fine 메모리 조직을 제안합니다.
2. MicroGraph 기반 경로 수준 국소화: 수정이 일어나기 전에 지원 서브그래프와 구체적으로 영향을 받는 증거 경로를 식별하여, 좁혀진 명시적 재작성 영역을 결정하는 방법을 도입합니다.
3. 협응된 재작성 메커니즘: 국소화된 영역 내에서 메모리 유닛의 내부 상태와 유닛 간 의존성을 공동으로 수정하도록 설계하여, 일관된 메모리 진화를 보장합니다.

실험 결과

저자들은 두 가지 벤치마크인 LoCoMo(장기 대화형 QA)와 MemConflict(갈등 인식 메모리 평가)에서 HiGram을 평가했습니다.

• LoCoMo 성능: HiGram은 GPT-5.4 및 GPT-4o 백본 모두에서 평균 F1, BLEU, LLM-as-Judge 점수에서 최첨단(SOTA) 성능을 달립다. 특히, GPT-5.4 환경에서 전체 컨텍스트 베이스라인이 소비하는 토큰의 약 7.2%만을 사용하면서도 더 높은 답변 품질을 유지하며 탁월한 토큰 효율성을 입증했습니다. 시간적(Temporal) 및 적대적(Adversarial) 질문 카테고리에서 특히 강점을 보였습니다.
• MemConflict 성능: HiGram은 전체 정확도 및 증거 선택 지표(SEH@3, SRS)에서 베이스라인(A-MEM, Mem0, LangMem 포함)을 능가했습니다. 동적 갈등에 대해 가장 높은 **업데이트 순서 일관성 점수(UOCS)**를 기록했으며, 정적 갈등에 대해 가장 높은 **갈등 인식 점수(CRS)**를 달성했습니다.
• 절제 연구(Ablation Studies): MicroGraph 조직을 제거하면 토큰 사용량이 크게 증가하고 추론 품질이 저하되어, 조대 수준 인덱싱의 가치를 확인했습니다. 지원 서브그래프를 제거하면 모든 카테고리에서 성능이 저하되었으며, 이는 검색 과정에서 의존성과 시간적 관계를 보존하는 것의 필요성을 강조합니다.
• 업데이트 전략: "Append-only(추가 전용)" 및 "Relation-level(관계 수준)" 업데이트 전략과 비교했을 때, HiGram의 협응된 접근 방식은 다른 방법들이 보이는 트레이드오프 없이 동적 및 정적 갈등 시나리오 모두에서 최고의 균형을 제공하며 높은 정확도를 달성했습니다.

의의 및 주장

본 논문은 HiGram이 메모리 업데이트의 입도와 추론에 필요한 증거 구조 사이의 근본적인 불일치를 해결한다고 주장합니다. 경로 수준의 재작성 영역을 국소화하고 상태 변화를 의존성 업데이트와 협응함으로써, 이 방법은 다음을 실현합니다:

• 토큰 소비 감소: 평면 그래프를 탐색하고 반복적인 전역 재작성을 수행하는 비용을 피합니다.
• 답변 품질 향상: 유효하고 국소화된 증거만이 추론에 사용되도록 보장하여, 오래되거나 무관한 컨텍스트를 필터링합니다.
• 일관성 강화: 의존적 결론의 유효성을 명시적으로 관리함으로써 동적, 정적 및 조건부 갈등 상황에서도 일관된 증거 구조를 유지합니다.

저자들은 구조화되고 국소화된 증거를 선택하는 것이 LLM을 거대하고 구조화되지 않은 역사적 컨텍스트에 노출시키는 것보다 더 효과적이며, 진화하는 메모리 시스템에서 유효한 의존성 구조를 유지하기 위해서는 협응된 재작성이 필수적이라고 결론짓습니다.