DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs

이 논문은 대규모 언어 모델의 수학적 추론 능력을 평가하기 위해 연쇄 사고 (CoT) 를 규칙 기반의 방향성 비순환 그래프 (DAG) 과정으로 모델링하고, 이를 통해 최종 정답의 정확도뿐만 아니라 추론 과정의 논리적 일관성을 측정할 수 있는 새로운 프레임워크와 벤치마크를 제안합니다.

핵심

이 논문은 **"LLM(거대 언어 모델) 이 수학 문제를 풀 때, 정말로 '생각'을 하고 있는 것인지, 아니면 단순히 '운 좋게' 정답을 맞춘 것인지"**를 구별해 내는 새로운 방법을 제안합니다.

기존에는 모델이 정답을 맞췄는지 여부만 확인했지만, 이 연구는 그 과정이 얼마나 논리적으로 탄탄한지를 평가하는 새로운 기준을 만들었습니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 문제: "정답만 맞춘 학생" vs "이해한 학생"

상상해 보세요. 수학 시험에서 두 학생이 똑같은 정답을 맞췄습니다.

• 학생 A: 문제를 풀면서 단계별로 논리적으로 계산했고, 실수 없이 결론에 도달했습니다.
• 학생 B: 중간에 엉뚱한 계산을 하거나, 필요 없는 정보를 섞어 쓰다가, 우연히 정답에 도달했습니다.

기존의 평가 방식 (PASS@k) 은 두 학생 모두 "정답을 맞췄으니 A"라고 치고 넘어갔습니다. 하지만 이 논문은 **"학생 B 는 논리적으로 틀린 길을 갔다가 운 좋게 도착한 것일 뿐, 진짜 실력이 아니다"**라고 지적합니다.

2. 해결책: "DAG-MATH" (논리 지도 그리기)

이 논문은 모델이 답을 도출하는 과정을 **하나의 '지도' (그래프)**로 그려보자는 아이디어를 제시합니다.

• 비유: 미로 찾기
  • 수학 문제를 풀 때는 여러 갈래 길이 있습니다. (예: A 방법을 쓸까? B 방법을 쓸까?)
  • **DAG(방향성 비순환 그래프)**는 이 미로의 모든 갈래를 한 장의 지도에 그려놓은 것입니다.
  • 노드 (Node): 각 단계의 결론 (예: "이 식은 x>1 이어야 해").
  • 엣지 (Edge): 그 결론에 도달한 이유 (예: "로그 함수의 정의역 때문에").

이론적으로 완벽한 수학 풀이는 시작점에서 정답까지, 모든 단계가 서로 단단하게 연결된 '논리적으로 닫힌 (Logically Closed)' 지도여야 합니다. 중간에 끊긴 길이나, 정답과 상관없는 데로 가는 길이 없어야 합니다.

3. 새로운 평가 도구: "논리적 근접도 (Logical Closeness)"

연구진은 모델이 만든 답을 이 '지도'에 대입해 봅니다.

• 완벽한 추론 (Perfect Reasoning): 지도의 모든 길이 정답으로 이어지고, 불필요한 데로 가지 않는 경우. (진짜 실력자)
• 불완전한 추론: 정답은 맞았지만, 지도에 정답과 상관없는 길 (중간 계산 실수, 엉뚱한 정보) 이 섞여 있는 경우. (운 좋게 맞춘 경우)
• 틀린 추론: 아예 정답이 틀린 경우.

기존에는 '정답률'만 봤다면, 이 논문은 **"정답에 도달하기 위해 얼마나 논리적으로 깔끔하게 길을 찾았는가?"**를 점수 (PRR, AUC) 로 매깁니다.

4. 주요 발견: "운 좋은 모델"의 진실

이 방법으로 유명한 AI 모델들 (Gemini, GPT, Qwen 등) 을 테스트한 결과 놀라운 사실이 드러났습니다.

• 겉보기엔 비슷: 정답을 맞춘 비율 (PASS@1) 은 모델마다 비슷해 보였습니다.
• 속은 다름: 하지만 '논리적 근접도'를 따져보니, 모델들 간의 차이가 매우 컸습니다.
  • 어떤 모델은 정답을 맞추기 위해 엉뚱한 길 (검색, 추측) 을 많이 돌아다녔습니다. (지도가 복잡하고 끊김이 많음)
  • 어떤 모델은 직관적이고 논리적인 길로 정답에 도달했습니다. (지도가 깔끔함)
• 생각하는 모드 (Thinking Mode) 의 효과: '생각하는' 모드를 켜면 정답률은 올라가지만, 여전히 운 좋게 정답을 맞출 확률이 높다는 것을 발견했습니다. 즉, 더 많이 생각한다고 해서 반드시 논리가 완벽해지는 건 아니라는 뜻입니다.

5. 결론: "골디락스 원칙" (적당한 균형)

이 연구는 수학 문제 해결을 평가할 때 두 가지 극단을 피하고 적당한 균형을 찾으려 합니다.

• 너무 자유로운 글쓰기: 논리 구조를 파악하기 어렵습니다.
• 너무 딱딱한 증명 언어 (LEAN 등): 일반인이 쓰기 어렵고 준비가 너무 많습니다.

이 논문이 제안한 DAG-MATH는 자연어 (사람이 쓰는 말) 의 유연함과, 수학 증명 (논리적 엄밀함) 의 정확함을 적절히 섞은 **'중용의 길'**입니다.

요약

이 논문은 **"AI 가 정답을 맞췄다고 해서 다 똑똑한 건 아니다"**라고 말합니다. 대신, AI 가 그 정답에 도달하는 과정이 얼마나 논리적으로 깔끔한지 '지도'를 그려서 평가해야 진짜 지능을 알 수 있다고 주장합니다. 이는 앞으로 더 똑똑하고 신뢰할 수 있는 AI 를 만드는 데 중요한 나침반이 될 것입니다.

기술 요약

1. 문제 정의 (Problem Definition)

대규모 언어 모델 (LLM) 은 체인 오브 씽킹 (Chain-of-Thought, CoT) 프롬프팅을 통해 수학 문제 해결에서 뛰어난 성능을 보여주고 있습니다. 그러나 이러한 성공이 **실제 논리적 추론 (logical inference)**에 기반한 것인지, 아니면 **무작위 탐색 (search)**이나 **암기된 절차 (rote procedures)**에 의한 것인지는 명확하지 않습니다.

기존의 평가 방식인 PASS@k(정답 여부만 확인) 는 모델이 최종 정답을 맞췄는지만 판단할 뿐, 그 과정이 논리적으로 일관성이 있는지, 혹은 불필요한 탐색을 통해 우연히 정답을 얻었는지는 파악하지 못합니다. 또한, 기존 그래프 기반 연구들은 CoT 를 결정론적 서브그래프 매칭이나 단순한 트리로 모델링하여, 다양한 샘플링의 이점이나 장거리 의존성, 목표 지향적 (goal-directed) 인 흡수 상태 (absorbing state) 특성을 제대로 포착하지 못했습니다.

2. 방법론 (Methodology)

이 논문은 CoT 를 **유방향 비순환 그래프 (DAG) 상의 규칙 기반 확률 과정 (rule-based stochastic process)**으로 모델링하는 새로운 프레임워크를 제안합니다.

2.1 DAG 기반 CoT 프레임워크

• 단계별 (Step-Level) 모델링: 토큰 수준이 아닌 추론 단계 (step) 단위로 CoT 를 분석합니다.
• 2 단계 워크플로우:
  1. 태스크 특화 DAG 구축 (Phase 1): 주어진 문제 (Prompt) 에 대해 잠재적인 추론 상태 (노드) 와 논리적 의존성 (간선) 을 포함하는 DAG 를 정의합니다. 노드는 중간 결론을, 간선은 추론 규칙을 나타냅니다.
  2. 확률적 경로 샘플링 (Phase 2): LLM 이 이 DAG 위에서 확률적 전이 규칙에 따라 CoT 경로를 생성합니다. 이 과정은 최종 정답 (Sink Node) 에 도달할 때까지 진행됩니다.
• 구조적 정의:
  • 노드 (Node): 문제 문장이나 이전 단계에서 도출된 결론.
  • 간선 (Edge): 결론을 도출하기 위해 적용된 논리적 근거 (Justification).
  • 흡수 상태 (Absorbing State): 최종 정답 또는 오답 노드로, 도달하면 경로가 종료됨.

2.2 논리적 근접성 (Logical Closeness) 및 평가 지표

기존의 정답률만 보는 방식의 한계를 극복하기 위해 새로운 지표를 도입했습니다.

• 논리적 근접성 (Logical Closeness): 생성된 CoT 경로가 DAG 구조 내에서 논리적으로 '닫혀 있는지 (Logically Closed)'를 판단합니다. 즉, 모든 중간 단계가 후속 단계에 의해 사용되어 최종 결론으로 이어지는지 확인합니다. 불필요한 탐색이나 무관한 단계가 포함되면 '논리적으로 닫히지 않은' 것으로 간주됩니다.
• 완벽한 추론률 (Perfect Reasoning Rate, PRR): 생성된 경로가 논리적으로 닫혀 있고 (Logical Closeness) 동시에 **정답 (Correct Sink)**에 도달했을 때의 비율입니다.
• AUC 점수: 논리적 근접성의 비율을 0% 에서 100% 까지 변화시키며 정확도를 측정하여, 모델이 얼마나 엄격한 논리성을 유지하면서 정답을 찾는지 종합적으로 평가합니다.

2.3 DAG-MATH 벤치마크 구축

• DAG-MATH 포맷: LLM 이 생성한 CoT 를 구조화된 JSON 형식 (Edge -> Parents -> Node) 으로 출력하도록 프롬프팅하여, 그래프 구조를 명확히 추출할 수 있게 했습니다.
• 데이터셋: Omni-MATH 데이터셋을 기반으로 3 단계 프롬프팅 전략 (노드 생성 -> 의존성 분석 -> 간선 논리화) 을 통해 2,894 개의 '골드 스탠더드 (Gold-Standard)' DAG-MATH 데이터를 구축했습니다.
• 검증: SymPy 및 인간 평가를 통해 논리적 일관성과 정답 정확도를 검증했습니다.

3. 주요 기여 (Key Contributions)

1. 엄격한 프레임워크 제안: CoT 를 DAG 기반의 확률적 과정으로 공식화하여, LLM 의 수학 추론 메커니즘을 체계적으로 분석할 수 있는 이론적 기반을 마련했습니다.
2. 새로운 평가 지표 개발: 단순 정답 여부를 넘어 '논리적 일관성'을 정량화하는 PRR과 AUC 지표를 도입했습니다. 이는 모델이 탐색 (Search) 을 통해 정답을 찾았는지, 아니면 논리적 추론을 통해 찾았는지를 구분합니다.
3. DAG-MATH 벤치마크: 구조화된 추론 데이터를 포함하는 대규모 벤치마크를 공개하여, 추론 능력 평가의 표준을 제시했습니다.
4. 실증적 발견: 다양한 LLM 패밀리 (Gemini, GPT, Qwen 등) 에 대한 평가를 통해, 최종 정답률 (PASS@1) 은 비슷하더라도 완벽한 추론 능력 (PRR) 은 모델 간에 통계적으로 유의미한 차이가 있음을 발견했습니다.

4. 실험 결과 (Results)

• 탐색 (Search) vs 추론 (Reasoning):
  • 많은 모델이 PASS@1 (정답률) 은 높게 나오지만, PRR (완벽한 추론률) 은 현저히 낮았습니다. 이는 모델이 다양한 탐색 경로를 시도하여 우연히 정답을 맞히는 경우가 많음을 의미합니다.
  • 예를 들어, Gemini-2.5-Flash 의 경우 PASS@1은 52.4% 였으나 PRR은 17.0% 로, 약 35.4%p 의 격차가 발생했습니다.
• 그래프 구조 분석:
  • 문제 난이도: 문제가 어려워질수록 DAG 는 더 크고 희소하며 (sparse), 분기 (branching) 가 복잡해집니다.
  • 정답 유형별 차이:
    • Perfect (완벽한 추론): 그래프가 작고 밀도가 높으며, 불필요한 분기가 적습니다.
    • Correct (정답만 맞춘 경우): 유용한 탐색 단계를 포함하지만, Perfect 보다 그래프가 크고 희소합니다.
    • Incorrect (오답): 과도한 탐색 (speculative branching) 으로 인해 그래프가 매우 크고 분기가 심합니다.
• 모델 비교: 모델 간 PASS@1 차이는 크지만, PRR과 AUC 곡선은 상대적으로 유사한 경향을 보였습니다. 이는 모델들의 '본질적인 추론 능력'은 비슷하지만, '탐색 전략'의 효율성 차이가 성능 격차로 이어짐을 시사합니다.
• 생각 모드 (Thinking Mode) 의 영향: DeepSeek-R1 과 같은 생각 모드를 가진 모델은 PASS@1과 PRR 모두를 향상시켰으나, 여전히 탐색과 논리적 일관성 사이의 간극은 존재했습니다.

5. 의의 및 결론 (Significance)

• 평가 패러다임의 전환: LLM 의 수학 추론 능력을 평가할 때, 단순히 "정답을 맞췄는가"가 아니라 "논리적으로 타당한 과정을 거쳤는가"를 평가해야 함을 강조합니다.
• Goldilocks 원리: 자연어의 유연성과 LEAN 같은 형식 증명 시스템의 엄격함 사이의 균형을 이루는 평가 프레임워크를 제공합니다.
• 향후 연구 방향:
  • 검색 정책 개선: 논리적 근접성을 보상 함수로 활용하여 Monte Carlo Tree Search (MCTS) 등의 알고리즘을 더 효율적으로 유도할 수 있습니다.
  • RL 기반 학습: AUC 곡선을 기반으로 논리적 엄격성을 점진적으로 높이는 커리큘럼 학습 전략을 제안합니다.
  • 일반화 이론: LLM 의 추론 능력을 '과적합 (Over-reasoning)'과 '과소적합 (Under-reasoning)'의 관점에서 재정의하여, 지도학습의 일반화 이론과 유사한 수학적 정의를 시도합니다.

이 논문은 LLM 이 수학 문제를 해결할 때 발생하는 '정답과 논리 사이의 괴리'를 드러내고, 이를 해결하기 위한 새로운 평가 기준과 프레임워크를 제시함으로써, 더 신뢰할 수 있고 해석 가능한 AI 추론 시스템 개발의 기초를 마련했다는 점에서 의의가 큽니다.