비트 퍼즐을 산술이 아닌 문자열 유사도로 푼 LLM, 추론 설계의 발상 전환

산술을 버리고 문자열로 옮긴 발상

비트 조작 퍼즐은 겉보기에 단순하다. 입력 이진 문자열을 출력으로 바꾸는 숨은 논리 규칙이 있고, 그 규칙을 알아낸 뒤 처음 보는 입력에 적용하면 된다. 그러나 이 과제는 대규모 언어 모델에게 악명 높은 난제로 꼽힌다. 시프트와 회전, 그리고 여러 논리 게이트의 조합이 만들어내는 후보 변환의 공간이 조합적으로 폭발하기 때문이다. 기존 방식은 모델에게 불 대수와 자릿수 산술을 머릿속으로 시뮬레이션하라고 강요하는데, 언어 모델은 본래 다음 토큰의 확률을 추정하는 장치이지 비트 단위 계산기가 아니다. 결과적으로 그럴듯하지만 틀린 답, 즉 환각이 쏟아진다.

NVIDIA Nemotron 모델 추론 챌린지에 출전한 이 연구팀의 출발점은 문제를 푸는 방법이 아니라 문제를 바라보는 틀 자체를 바꾸는 데 있었다. 이들은 산술 논리를 통째로 포기하고, 대신 문자열 유사도라는 전혀 다른 도구를 끌어들였다. 핵심 아이디어는 논리 게이트를 추론하는 작업을 '기저(base) 선택' 문제로 다시 쓰는 것이다. 입력과 출력 사이에 몇 개의 비트만 뒤집히는지를 세는 최소 비트 반전이라는 단순한 거리 척도로, 가장 원초적인 변환들을 분리해낸다. 이렇게 골라낸 기본 변환들을 조합하면 복잡한 산술을 거치지 않고도 진리표를 역으로 추론할 수 있다. 계산을 패턴 매칭으로 환원한 셈이다.

탐색과 오류 복구를 모델 안으로

두 번째 기여는 이 기저 선택 과정을 체계적인 탐색으로 형식화한 점이다. 후보 기저를 하나씩 시험하고, 여러 예시에 걸쳐 논리적 충돌이 발생하는지를 검사하며, 실패하면 되돌아가 다른 가지를 탐색하는 깊이 우선 백트래킹 구조다. 충돌 감지와 백트래킹이 결합되면서 한 번의 잘못된 가정이 전체 추론을 무너뜨리지 않고, 모델이 스스로 오류에서 회복하는 견고한 절차가 만들어진다. 흥미로운 것은 이 탐색이 단지 외부 알고리즘으로만 돌아가는 것이 아니라, 모델 자신의 추론 능력으로 흡수되도록 학습이 설계됐다는 점이다.

그 열쇠가 비트 토크나이제이션과 상호작용형 추론 미세조정이다. 연구팀은 토크나이저가 이진 문자열을 한 비트씩 개별 토큰으로 인코딩하도록 강제했다. 여러 비트가 하나의 토큰으로 뭉뚱그려지면 모델은 자릿값을 정확히 분간하기 어려운데, 비트를 낱개로 쪼개면 위치와 값을 또렷하게 다룰 수 있다. 여기에 동적 마스킹으로 외부 오라클의 피드백을 흉내 내, 모델이 가설을 세우고 스스로 평가한 뒤 필요하면 되돌아가는 과정을 학습 단계에서 직접 체득하게 했다. 즉 백트래킹을 외부 도구로 빌려 쓰는 것이 아니라, 모델이 본래부터 그렇게 사고하도록 훈련한 것이다.

의미와 남은 질문

이 접근은 비트 조작 부문에서 96%가 넘는 검증 정확도로 해당 부문 최고 성적을 기록했고, 대회 종합 7위를 견인했다. 숫자 자체보다 주목할 것은 그 뒤에 깔린 철학이다. 언어 모델에게 정밀한 계산을 요구하는 대신, 계산이 필요 없도록 문제를 재표현하고, 모델이 잘하는 패턴 인식과 탐색으로 길을 우회한다는 발상은 비트 퍼즐을 넘어 일반화될 여지가 크다. 모델이 한 번에 정답을 내놓길 기대하기보다, 가설과 검증과 후퇴를 반복하는 탐색적 사고를 학습 단계에서 내재화한다는 방향은 최근 추론 모델 연구의 흐름과도 맞닿아 있다.

물론 이 방법이 만능은 아니다. 기저로 분해되는 구조를 가진 비트 퍼즐에 특화된 설계인 만큼, 문자열 유사도라는 거리 척도가 의미를 갖지 않는 다른 종류의 기호 추론으로 그대로 옮겨갈 수 있을지는 별개의 문제다. 그럼에도 '계산하는 모델'이 아니라 '탐색하고 회복하는 모델'을 만든다는 관점의 전환은, 언어 모델의 추론 한계를 공학적으로 우회하는 한 가지 설득력 있는 방법을 보여준다.