LLM의 그래프 추론을 위한 벤치마크와 에이전트 개발
GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs
arXivLLM의 그래프 추론 능력을 체계적으로 평가하기 위해 'GT Bench'라는 새로운 벤치마크와 전문 에이전트 'GTA'가 개발되었습니다.
- 연구 결과, LLM의 성능은 입력 데이터 표현 방식(표현체)에 매우 민감하며, GTA 에이전트를 통해 이 문제를 효과적으로 개선할 수 있음을 입증했습니다.
- 기존의 단순 코드 생성 평가를 넘어, 실제 그래프 구조 이해와 다단계 알고리즘 추론 능력을 측정하는 새로운 기준을 제시했다는 점에서 중요합니다.
- LLM이 그래프를 다룰 때는 단순히 모델 성능만 볼 것이 아니라, 그래프의 밀도나 토폴로지 등 입력 표현 방식에 따른 민감도를 반드시 고려해야 합니다.
(LLMs)은 그래프 같은 구조화된 데이터에 대한 추론 능력이 요구되고 있으나, 기존 평가는 단순한 태스크를 작은 그래프로 다루거나 코드 생성 자체에 초점을 맞추는 경향이 있었습니다. 이에 연구진은 24개의 고전적인 그래프 문제를 44가지 태스크 구조 설정으로 포함하고, 자연어, 구조화된 언어, 인접 리스트, 인접 행렬 등 네 가지 표현 방식을 통해 10만 개 이상의 예시를 다루는 'Graph Theory Bench (GT Bench)'라는 새로운 를 제시했습니다.
평가 결과, LLM의 정확도가 입력 데이터 표현 방식에 매우 민감하며, 최적의 표현 방식이 그래프 밀도, 크기, 토폴로지 및 모델에 따라 달라진다는 점이 확인되었습니다. 이러한 관찰을 바탕으로 연구진은 'Graph Theory Agent (GTA)'를 제안했습니다. GTA는 선호도 학습 기반의 표현 선택기와 고정된 실행자 LLM 주변에 계획-분해(plan-and-decompose) 스캐폴딩을 결합한 구조입니다.
GTA 를 적용했을 때, Phi-4 모델은 벤치마크의 쉬운 분할(easy split)에서 53.5%에서 69.1%로 성능이 향상되었으며, 어려운 분할(hard split)에서는 33.0%에서 41.5%로 개선되었습니다. 이러한 결과는 GTA가 기존의 프롬프팅 및 에이전트 기반 베이스라인을 능가하는 성능을 보였고, 추가 재학습 없이 GraCoRe와 NLGraph에도 전이됨을 입증했습니다.
용어 풀이
- 대규모 언어 모델
- 방대한 글을 학습해 문장을 이해하고 만들어 내는 AI 모델. ChatGPT, Claude, Gemini가 여기에 속해요.
- 벤치마크
- 모델 성능을 같은 조건에서 비교하려고 만든 시험 문제 모음.
- 에이전트
- 목표를 받으면 스스로 계획을 세우고 도구를 써서 여러 단계의 작업을 해내는 AI.