연구진은 LLM의 그래프 이론 추론 능력을 평가하는 GT Bench(Graph Theory Bench)를 공개했다. 24개 고전 그래프 문제를 44가지 과제-구조 설정, 자연어·구조화 언어·인접 리스트·인접 행렬 등 4가지 표현으로 10만 건 이상 구성했다. 8개 LLM 평가 결과 정확도는 입력 표현 방식에 크게 의존했고 최적 표현은 그래프 밀도·크기·토폴로지와 모델에 따라 달라졌으며, 이런 민감성은 최상위 추론 모델에서도 약화된 형태로 지속됐다. 이를 바탕으로 표현 선택기와 계획-분해 스캐폴딩을 프리즈된 실행 LLM에 결합한 Graph Theory Agent(GTA)를 제안, Phi-4의 성능을 쉬운 분할에서 53.5%→69.1%, 어려운 분할에서 33.0%→41.5%로 끌어올려 8개 프롬프팅·에이전트 기준선을 능가했고 재학습 없이 다른 벤치마크로도 전이됐다.

• •24개 그래프 문제, 44가지 설정, 10만 건 이상 예제로 구성된 GT Bench 공개
• •정확도가 자연어·구조화 언어·인접 리스트·인접 행렬 등 입력 표현 방식에 크게 좌우됨을 확인
• •최적 표현이 그래프 밀도·크기·토폴로지·모델별로 달라지고 강한 추론 모델에서도 민감성 지속
• •표현 선택기+계획-분해 스캐폴딩 결합한 GTA로 Phi-4 성능을 대폭 향상(쉬운 분할 53.5%→69.1%)
• •재학습 없이 GraCoRe·NLGraph 등 다른 벤치마크로 전이 성공