LLM에 비트 조작 퍼즐의 기저 및 진리표를 추론하기 위한 문자열 매칭, 백트래킹, 오류 복구 교육

본 논문은 Bit Manipulation Puzzles에 초점을 맞춘 NVIDIA Nemotron Model Reasoning Challenge를 위한 알고리즘적 혁신을 제시합니다. 이 과제의 목표는 입력된 이진 문자열을 출력으로 변환하는 숨겨진 논리 규칙을 발견한 다음, 이를 보지 못한 입력에 적용하는 것입니다. Large Language Models (LLMs)는 여기서 악명 높게 어려움을 겪습니다. 기존 방법들은 LLM에게 복잡한 부울(boolean) 논리와 산술을 시뮬레이션하도록 강요하며, 이는 환각(hallucinations)으로 이어집니다. 더욱이, 비트 단위 연산(shifts, rotations, logic gates의 조합)의 탐색 공간은 심각한 조합적 폭발(combinatorial explosion)을 겪습니다. 이러한 계산상의 난해함을 극복하기 위해, 우리는 산술 논리를 완전히 포기하고 문자열 유사성, 구조화된 검색, 그리고 자율적인 오류 복구를 선호하는 새로운 접근 방식을 제시합니다. 우리의 핵심 기여는 다음과 같습니다: 1. 기저 및 진리표 공식화: 우리는 논리 게이트 추론을 기저 선택(base-selection) 작업으로 재구성하고, 문자열 유사성(최소 비트 플립)을 활용하여 원시적인 변환(