▲

클로드의 순환들 [PDF]

 (www-cs-faculty.stanford.edu)
1P by GN⁺ 5시간전 | ★ favorite | 댓글 1개
  • Anthropic의 모델 Claude Opus 4.6이 Donald Knuth가 몇 주간 연구하던 방향성 해밀토니안 순환 분해 문제를 해결함
  • 문제는 (m^3)개의 꼭짓점을 가진 방향 그래프의 세 개의 해밀토니안 순환으로의 분해를 찾는 것이며, Claude는 이를 odd m(홀수 m) 에 대해 완전하게 해결함
  • Claude는 “섬유(fiber) 분해”, “3D 뱀형(serpentine) 패턴”, 심층 탐색(DFS), 시뮬레이티드 어닐링 등 다양한 탐색 전략을 단계적으로 수행함
  • 최종적으로 Python 프로그램 형태의 일반 해법을 도출하고, Filip Stappers가 m=3부터 101까지의 홀수 m에 대해 검증하여 완전한 분해를 확인함
  • Knuth는 이 결과를 자동 추론과 창의적 문제 해결의 획기적 진전으로 평가하며, 짝수 m의 경우는 여전히 미해결로 남아 있음을 명시함

문제의 배경과 정의

  • 연구 주제는 방향성 해밀토니안 순환(directed Hamiltonian cycles) 에 관한 것으로, Knuth의 저서 The Art of Computer Programming의 향후 권에 포함될 예정
  • 그래프는 (m^3)개의 꼭짓점 (ijk)로 구성되며, 각 꼭짓점에서 세 개의 간선이 존재: (i+jk), (ij+k), (ijk+)
  • 목표는 모든 (m>2)에 대해 이 간선들을 세 개의 방향성 (m^3)-순환으로 분해하는 일반 해법을 찾는 것

Claude의 탐색 과정

  • Claude Opus 4.6은 Anthropic의 혼합 추론(hybrid reasoning) 모델로, Filip Stappers가 문제를 제시하고 진행 과정을 문서화하도록 지시함
  • 초기 단계에서 Claude는 문제를 함수적 그래프와 순열 할당 문제로 재정의하고, 선형 및 2차 함수형 접근을 시도했으나 실패
  • 이후 DFS 탐색, 2D 뱀형 패턴 분석, 3D Gray 코드 기반 패턴 등을 차례로 실험
  • “섬유(fiber) 분해” 접근을 도입하여, (s = (i+j+k) \mod m)을 기준으로 층화된 구조를 분석하고, 시뮬레이티드 어닐링(SA) 을 통해 부분적 해를 발견

해법의 발견과 검증

  • 탐색 31단계에서 Claude는 섬유별 단일 좌표 의존 규칙을 이용한 Python 프로그램을 생성
  • 이 프로그램은 m=3,5,7,9,11에서 완전한 세 개의 해밀토니안 순환을 생성
  • Filip Stappers는 이를 m=3~101의 모든 홀수 m에 대해 테스트하여 완전한 분해를 확인
  • Knuth는 이를 C 코드로 단순화하여 제시하고, 각 순환이 실제로 길이 (m^3) 임을 수학적으로 증명

일반화와 수학적 분석

  • (m=3)의 해밀토니안 순환 중 일부가 모든 홀수 m에 대해 일반화 가능함을 확인
    • (m=3)에서 11,502개의 순환 중 1,012개가 (m=5)로 일반화되고, 996개는 (m=7)까지 일반화됨
    • 이 996개는 모든 홀수 m>1에 대해 일반화 가능
  • “Claude-like” 분해는 i, j, s의 경계값(0 또는 m−1) 에만 의존하는 단순 규칙으로 정의됨
  • 정리: “Claude-like” 분해가 모든 홀수 m>1에서 유효하려면, m=3에서의 세 순환이 일반화 가능한 해밀토니안 순환이어야 함
  • 계산 결과, 760개의 Claude-like 분해가 모든 홀수 m에서 유효함

짝수 m의 미해결성과 결론

  • 짝수 m의 경우는 여전히 미해결(open) 상태
    • (m=2)는 불가능함이 기존 연구에서 증명됨
    • Claude는 (m=4,6,8)에서 부분적 해를 찾았으나 일반화 실패
  • Claude는 짝수 m 탐색 중 오류와 비정상 동작을 보여 탐색이 중단됨
  • Knuth는 이를 AI 기반 자동 추론의 역사적 성취로 평가하며, Claude Shannon의 이름에 걸맞은 진보라고 언급

부록: 다른 두 순환의 규칙

  • 두 번째 순환(c=1):
    • (s=0)이면 j 증가, (0<s<m−1)이면 i 증가, (s=m−1)일 때 i>0이면 k 증가, i=0이면 j 증가
  • 세 번째 순환(c=2):
    • (s=0)에서 j<m−1이면 i 증가, j=m−1이면 k 증가
    • (0<s<m−1)에서 i<m−1이면 k 증가, i=m−1이면 j 증가
    • (s=m−1)이면 i 증가
  • 각 순환의 s=0에서의 꼭짓점 순서가 명시되어 있으며, 이를 통해 전체 순환의 구조를 증명 가능
▲
GN⁺ 5시간전  [-]
Hacker News 의견들

  • RL 확장성이 적용 가능한 문제 영역을 생각해보면 흥미로움
    예전에는 인간의 인지에 의존해야 했지만, 이제는 이런 패턴이 확률 분포 안에 녹아 있어서 누구나 접근 가능해짐
    다만, 과학의 경계가 계속 확장될 때 모델이 이를 따라잡을 수 있을지가 의문임
    2030년에 Anthropic이 Claude를 최신 상태로 유지하려면 (a) 고정 모델의 지속 학습이나 (b) 지속 훈련이 필요할 텐데, 둘 다 쉽지 않음

    • 오픈 가중치 모델은 일종의 타임캡슐 같음
      지식 컷오프 시점 이후로는 그 시점에 영원히 머무르게 됨
    • 데이터 공유가 허용된다면, 오늘의 추론 결과가 내일의 학습 데이터가 될 수 있음
      연구자에게 무료 추론을 제공하는 대신, 그 사고 과정(trace) 을 학습 데이터로 쓰는 모델도 상상 가능함
    • 최근 연구자들의 말을 들어보면, 앞으로는 컨텍스트 윈도우를 대폭 확장하는 방향으로 모델 아키텍처가 발전할 것 같음
      Qwen3-next, Qwen3.5, Nemotron 3 Nano 같은 모델은 하이브리드 어텐션으로 메모리 비용을 줄이며 백만 토큰 윈도우를 지원함
    • 대부분의 연구와 학습이 이미 LLM과 코딩 에이전트를 통해 이루어지고 있음
      인간의 검증과 코드 실행, 검색을 통한 실시간 피드백 루프가 모델 학습 신호로 작용함
    • 2030년에는 오히려 Claude가 Anthropic을 최신 상태로 유지하게 될지도 모름
      반은 농담이지만, 완전히 불가능한 얘기는 아님

  • 예전에 있었던 Wolfram과 Knuth의 GPT-4 대화가 떠오름
    Knuth는 그때는 회의적이었지만, 최근 Opus 4.6 같은 모델을 보고 태도가 누그러진 듯함
    새로운 증거에 따라 생각을 바꾸는 태도는 멋진 일임
    관련 대화는 여기서 볼 수 있음

    • 새로운 증거에 따라 사전 확률(prior) 을 갱신하는 게 바로 베이지안 통계의 매력임
      과학적 사고의 핵심이기도 함

  • Knuth의 글 도입부가 다소 오해의 소지가 있다고 느낌
    마치 Claude가 문제를 직접 푼 것처럼 보이지만, 실제로는 Claude가 예시를 만들고 Knuth가 이를 일반화해 증명으로 만든 것임

    • 나도 Claude로 비슷한 실험을 해봤는데, 인간과 LLM의 시너지가 정말 큼
      LLM은 방향 설정에는 약하지만, 일단 방향이 주어지면 깊은 탐색을 잘함
      혼자 두면 엉뚱한 데로 가지만, 사람이 리드하면 훌륭한 파트너가 됨
    • Knuth가 과대평가한 건 아니라고 생각함
      Claude가 문제의 핵심을 뚫고 들어간 역할을 했고, 인간은 그걸 다듬은 것뿐임
    • Claude가 Knuth가 말하는 ‘해결’을 한 것으로 볼 수도 있음
      증명 정리는 부차적인 작업일 뿐임
    • 이전 시도로 돌아가서 반성하고 수정하는 능력은 분명한 지능의 징후로 보임

  • Claude가 짝수 케이스에서 멈췄다는 부분이 흥미로움
    아마 claude.ai나 claude code 중 하나를 썼을 텐데, 컨텍스트 초과(dumb zone) 에 들어간 듯함

    • 이 dumb zone을 시각화할 수 있다면 좋겠음
      Copilot처럼 컨텍스트 사용률 그래프를 보여주는 식으로, 사용자가 인지할 수 있게 하면 유용할 듯함
    • 결국 컨텍스트 압축(compacting) 을 하지 않으면 결과가 엉망이 됨
    • ‘plan document’를 언급한 걸 보니, 세션 관리 문서를 쓴 듯함
    • dumb zone이 뭔지 궁금해하는 사람도 있었음

  • Arthur C. Clarke가 유명하게 만든 펜토미노 퍼즐을 Claude에게 풀게 해봤음
    64비트 정수로 보드와 조각을 표현하자 C# 프로그램을 만들어 빠르게 풀었지만, 20x3 케이스에서 잘못된 매핑으로 오답을 냄
    인간이 할 법한 실수라 흥미로움

  • 요약하자면, Knuth가 문제를 제시하고 친구가 Claude로 30여 번의 탐색을 수행함
    Claude가 홀수 케이스를 해결하는 Python 프로그램을 만들고, Knuth가 그 접근을 증명함
    짝수 케이스는 여전히 미해결 문제로 남음

    • 하지만 Knuth가 말한 “careful human guidance”는 과장된 표현 같음
      실제로는 Claude가 자주 멈추거나 오류를 내서, 사람이 가끔 리마인드해주는 수준이었음
    • Knuth가 강조한 건, 공식 증명은 여전히 인간의 몫이라는 점 같음
      핵심 아이디어가 누구에게서 나왔는지는 불분명함

  • 요즘은 미해결 문제를 다루는 게 정말 즐거운 시기임
    10년 전 연구를 다시 Claude와 함께 탐구해보고 싶다는 생각이 듦

  • LLM의 강점은 세 가지로 보임: 방대한 지식, 연결 능력, 지치지 않는 시행착오
    이 세 가지가 합쳐지면 가끔 놀라운 결과가 나옴
    어쩌면 P≠NP 증명도 인간이 보지 못한 희미한 연결고리에 있을지도 모름

    • 마지막 항목은 사실 LLM 자체의 특성이라기보다 에이전트 루프의 특성일 수도 있음
      LLM은 그 안의 한 구성 요소일 뿐임
    • 그래도 지치지 않는 반복 탐색은 인간보다 큰 장점임
      다른 조건이 같다면 이게 결정적 차이임
    • 세 가지를 합치면 멋진 결과가 나온다는 말에 전적으로 공감함
    • 하지만 이런 능력이 감시 시스템에 쓰일 수 있다는 점은 무섭게 느껴짐
    • ‘연결 능력’은 사실 훈련 데이터에 이미 존재하는 연결에 한정된 것 같음
      완전히 새로운 연결을 만드는 건 아직 어려움

  • “LLM은 다음 단어를 예측하는 기계일 뿐”이라는 말이 맞는지 의문임
    그렇다면 이런 문제 해결은 어떻게 설명할 수 있을까? 이게 ‘생각’인가?

    • 만약 아인슈타인이 다음에 말할 단어를 완벽히 예측할 수 있다면, 그건 이미 지능을 구현한 것임
      “가장 확률 높은 단어”라는 표현은 지나치게 단순화된 설명임
    • 그 설명은 베이스 모델에는 맞지만, Opus 4.6 같은 모델은 그 위에 RLHF와 추가 훈련이 얹혀 있음
      결국 “다음에 일어날 일을 잘 예측하는 능력” 자체가 지능의 정의일 수도 있음
    • 베이스 모델은 웹의 “Answer:” 패턴을 학습하면서 자연스럽게 문제 해결 패턴을 익히게 됨
      RLHF 덕분에 단순 예측이 아니라 도움이 되는 답변을 하도록 보상받음
      그래서 “delve” 같은 표현이 과도하게 자주 등장함
      관련 내용은 AI SIGNS 문서 참고
    • 결국 여전히 확률 분포에서 단어를 뽑는 것이지만, 그 분포 자체가 지능의 핵심임
      LLM은 그 분포를 학습하고 있음
    • “가장 확률 높은 단어”라는 단순한 메커니즘이 인류 전체 지식과 결합되면 엄청난 힘을 가짐
      이를 단순화해 비꼬는 건 기술의 본질을 놓치는 태도임

  • Knuth 본인의 보고서라니 흥미로움
    LLM 도움 없이 직접 읽고 이해할 시간임

    • 시간이 없어 대신 누군가 만든 요약 링크를 찾아봤음
답변달기