LLM에 문자열 매칭, 백트래킹 및 오류 복구 기능을 적용하여 조합적으로 폭발하는 비트 조작 퍼즐의 규칙과 진리표를 추론

Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles

본 논문에서는 NVIDIA Nemotron 모델 Reasoning Challenge의 Bit Manipulation Puzzle 과제에서 사용된 알고리즘적 혁신을 제시합니다. 이 과제는 입력 바이너리 문자열을 출력으로 변환하는 숨겨진 논리 규칙을 발견하고, 이를 새로운 입력에 적용하는 것을 목표로 합니다. 기존의 대규모 언어 모델(LLM)은 복잡한 부울 논리와 산술 연산을 수행해야 하므로 성능이 저하되고 환각 현상이 발생하기 쉽습니다. 또한, 비트 연산(시프트, 회전 및 논리 게이트의 조합)의 탐색 공간은 극심한 조합적 폭발을 겪습니다. 이러한 계산적인 어려움을 해결하기 위해, 우리는 산술 논리를 완전히 배제하고 문자열 유사성, 구조화된 검색 및 자율적인 오류 복구에 중점을 둔 새로운 접근 방식을 제시합니다. 본 논문의 주요 기여는 다음과 같습니다: 1. 기본 요소 및 진리표 구성: 논리 게이트 추론을 기본 요소 선택 문제로 재구성하고, 문자열 유사성(최소 비트 반전)을 활용하여 원시적인 변환(

This paper presents our algorithmic innovations for the NVIDIA Nemotron Model Reasoning Challenge, focusing on Bit Manipulation Puzzles. In this task, the objective is to discover a hidden logical rule transforming input binary strings to outputs, then apply it to unseen inputs. Large Language Models (LLMs) notoriously struggle here; traditional methods force them to simulate complex boolean logic and arithmetic, leading to hallucinations. Furthermore, the search space of bitwise operations (combinations of shifts, rotations, and logic gates) suffers from a severe combinatorial explosion. To overcome this computational intractability, we present a novel approach that abandons arithmetic logic entirely in favor of string similarity, structured search, and autonomous error recovery. Our core contributions are: 1. Bases and Truth Table Formulation: We reframe logic-gate deduction into a base-selection task, leveraging string similarity (minimal bit flips) to isolate primitive transformations ("bases") and deduce truth tables without complex arithmetic. 2. Backtracking DFS and Error Recovery: We formalize a search process that tests candidate bases, detects logical collisions across examples, and backtracks upon failure to perform robust error recovery. 3. Bit Tokenization and Interactive Reasoning SFT: We force the tokenizer to encode binary strings as individual single-bit tokens. We use dynamic masking to simulate external oracle feedback, training the model to hypothesize, self-evaluate, and backtrack natively. Evaluated on bit manipulation puzzles, our approach achieved over 96% validation accuracy. This represents the highest performance in this category, driving our 7th Place overall finish in the contest.