Tree of Thoughts (ToT)는 진정한 도약이었습니다. 하나의 직선으로 추론하는 대신, 여러 갈래로 가지를 치고, 점수를 매기고, 막다른 길을 가지치기하며 최선의 경로를 탐색합니다. 따라서 단일 사고 사슬 (Chain of Thought)로는 해결할 수 없는 퍼즐도 풀 수 있게 됩니다. 하지만 트리는 그 형태 자체에 하나의 제약 사항이 내재되어 있으며, 이를 한 번 깨닫고 나면 잊을 수 없습니다. 바로 모든 노드(node)는 정확히 하나의 부모만을 가진다는 점입니다. 가지는 확장되거나 버려질 수는 있지만, 결코 다른 가지와 _결합(combined)_될 수는 없습니다.

이것은 들리는 것보다 훨씬 더 중요합니다. 실제 문제들은 분해되며, 분해될 때 서로 다른 가지들이 정답의 각 부분을 올바르게 찾아내기도 합니다. 가지 A는 전반부를 완벽하게 맞히고, 가지 B는 후반부를 완벽하게 맞히지만, 둘 중 어느 것도 단독으로는 완전히 정답이 아닙니다. 트리는 하나를 선택하고 다른 쪽의 유효한 절반을 버려야만 합니다. **Graph of Thoughts (GoT)**는 바로 그 제약을 제거합니다.

🕸️ 인터랙티브 데모 (가지치기, 병합, 정교화 과정을 거치는 실제 병합 정렬 — 실시간 검증된 점수 포함): https://dev48v.infy.uk/prompt/day21-graph-of-thoughts.html

핵심 아이디어: 사고는 그래프의 노드이다

GoT는 추론을 _그래프(graph)_를 구축하는 것으로 재정의합니다. 각 정점(vertex)은 하나의 사고 (thought), 즉 부분적인 해결책이나 중간 결과물입니다. 각 간선(edge)은 하나 또는 그 이상의 다른 사고로부터 하나의 사고를 만들어낸 **연산 (operation)**입니다. 이것은 트리가 아닌 일반적인 그래프이기 때문에, 하나의 사고는 여러 부모를 가질 수 있으며 간선은 심지어 자기 자신으로 되돌아오는 루프를 형성할 수도 있습니다.

데이터 구조에서의 이 단 한 번의 변화가 전체적인 개념적 도약입니다. 그 외의 모든 것은 이제 이 네트워크 위에서 자유롭게 실행할 수 있는 연산들에 불과합니다.

네 가지 연산

generate (branch, 생성/가지치기) — Tree of Thoughts에서 가져온 익숙한 방식입니다. 하나의 사고로부터 여러 개의 서로 다른 다음 사고들을 생성합니다. 이는 또한 _분할 (split)_이 될 수도 있습니다. 즉, 입력을 독립적인 하위 문제로 나누어 별도의 가지에서 해결하는 것입니다. 여기서 다양성이 중요합니다. 거의 중복되는 결과물은 예산(budget)을 낭비하게 됩니다.

score / rank (점수 / 순위) — 컨트롤러(controller)가 생각들을 비교할 수 있도록 각 생각(thought)을 숫자로 변환합니다. 객관적인 채점자(scorer)가 승리합니다: 검증기(validator), 테스트(test), 혹은 지표(metric)가 그 역할을 합니다. 데모에서는 채점자가 의도적으로 구체적입니다 — 리스트의 정렬 상태(sortedness), 즉 인접한 쌍들이 이미 올바른 순서로 배치된 비율을 측정하며, 1.0은 완벽하게 정렬되었음을 의미합니다.

aggregate / merge (집계 / 병합) — 트리(tree) 구조가 수행할 수 없는 동작이자, GoT가 존재하는 이유입니다. 여러 개의 생각들을 가져와 각 생각의 장점들을 유지하는 하나의 새로운 생각으로 결합합니다. 구체적으로는 두 개 이상의 부모를 가진 노드(node)를 의미합니다: 두 개의 정렬된 절반이 하나의 리스트로 병합되거나, 세 개의 부분적인 답변이 하나로 조정되거나, 여러 개의 순위가 하나의 최종 후보 명단(shortlist)으로 융합되는 식입니다. LLM을 사용할 때 프롬프트는 말 그대로 "여기 N개의 부분적인 답변이 있습니다. 각 답변의 최선의 부분을 유지하고 오류를 수정한 하나의 답변을 작성하세요"가 됩니다.

refine / loop (정제 / 루프) — 자기 루프(self-loop) 에지(edge): 생각을 모델에 다시 입력하여 개선한 다음, 점수가 더 이상 오르지 않을 때까지 반복합니다. 두 개의 부분적인 솔루션을 병합하면 종종 연결 부위에 작은 불완전함이 남게 되는데, 정제 루프(refine loop)가 이를 깔끔하게 해결합니다. 루프는 트리가 표현할 수 없는 두 번째 요소입니다.

왜 집계(aggregation)가 순수 분기(branching)보다 뛰어난가

분기형 탐색(branching search)은 오직 단 하나의 최선인 가지(branch)만을 반환할 수 있습니다. 그 한계치는 우연히 가장 강력했던 추론 경로에 의해 결정됩니다. 집계는 그 한계치를 끌어올립니다. 병합된 생각은 여러 가지의 최선 부분들로부터 조립되기 때문에, 그것을 구성하는 데 사용된 모든 개별 가지보다 더 높은 점수를 얻을 수 있습니다.

데모는 스크립트가 아닌 실제 코드로 이를 증명합니다. [8, 3, 5, 1, 9, 2, 7, 4]를 정렬해 봅시다. 이를 두 개의 절반으로 나누면, 각 절반의 가지는 거의 올바르게 정렬되지만 숫자 하나가 제자리를 벗어나게 됩니다:

branch A: [3, 5, 1, 8]  -> 66% 정렬됨
branch B: [2, 7, 4, 9]  -> 66% 정렬됨
최선의 단일 가지      =  66%   (트리는 여기서 멈춤)

이제 그래프(graph) 방식의 동작을 수행합니다. 실제 병합(merge)을 통해 두 가지를 집계(aggregate)한 다음, 인접 요소 교환(adjacent-swap) 스윕(sweeps)을 통한 정제 루프(refine loop)를 실행합니다:

merge(A, B)  -> [2, 3, 5, 1, 7, 4, 8, 9]  -> 71%
refine x3    -> [1, 2, 3, 4, 5, 7, 8, 9]  -> 100%   완전 정렬됨 (fully sorted)

최적의 브랜치(branch)보다 +34포인트 높음 — 그리고 이 숫자들은 실제 병합(merge) 및 정제(refine) 함수에 의해 실시간으로 계산된 것이므로, 개선 사항은 서술된 것이 아니라 실제적인 것입니다. 단일 브랜치가 모든 좋은 요소들을 가졌던 적은 없었습니다. 병합(merge)이야말로 그것들을 조립하는 과정입니다.

컨트롤러(controller)와 연산 그래프(Graph of Operations)

연산들은 스스로 실행되지 않습니다. **컨트롤러(controller)**가 연산 그래프(Graph of Operations, GoO)라고 불리는 계획을 실행합니다: 입력을 분할(split)하고, 후보(candidates)를 생성(generate)하고, 점수를 매기고(score), 생존자들을 집계(aggregate)하고, 병합을 정제(refine)한 뒤, 중단합니다. 이 계획은 하드코딩된 제어 흐름(control flow)이 아니라 _데이터(data)_이므로, 동일한 생성/점수 매기기/집계/정제 프리미티브(primitives)들이 정렬, 다중 문서 요약(multi-document summarisation), 키워드 병합, 여러 출처의 사실 조정(reconciling facts) 등 서로 다른 파이프라인(pipelines)으로 재구성될 수 있습니다.

async function got(problem) {
  const [a, b] = split(problem);            // 생성 / 브랜치 (generate / branch)
  const left   = refine(await sortBranch(a));
...

주의사항, 그리고 가치가 있는 경우

추가되는 모든 기능은 모델 호출(model calls) 비용을 발생시킵니다. GoT는 생성, 점수 매기기, 집계, 그리고 반복적인 정제를 위해 LLM을 호출하며, 이는 체인(chain)의 단일 패스(single pass)나 트리(tree)의 레벨당 팬아웃(fan-out)보다 현저히 많습니다. 따라서 예산 조절 요소들이 다시 등장합니다: 분기 계수(branch factor), 각 단계별로 유지할 top-k, 정제 루프(refine loops), 엄격한 노드 상한선(hard node cap) 등입니다. 각 단계에서 가장 좋은 생각(thoughts)들만 유지하고, 기준을 통과하는 즉시 중단하십시오.

솔직한 규칙은 다음과 같습니다: chain < tree < graph — 적합한 구조 중 가장 덜 강력한 것을 사용하십시오. 작업이 진정으로 분해될 수 있고 부분적인 결과들이 더 나은 전체로 _병합(merge)_되어야 할 때에만 GoT를 사용하십시오. 문제의 형태가 그러하다면, 추가적인 토큰(tokens)은 어떤 단일 브랜치도 혼자서는 도달할 수 없었던 정답을 구매해 줄 것입니다.

데모에서 두 가지 작업을 시도해 보고, 병합 노드(merge node)가 두 개의 부모(parents)와 함께 활성화되는 것을 확인해 보세요: https://dev48v.infy.uk/prompt/day21-graph-of-thoughts.html

내일: Skeleton-of-Thought — 답변의 뼈대(Skeleton)를 먼저 작성한 다음, 모든 지점을 병렬적으로 확장합니다.