조합 폭발적 비트 조작 퍼즐에서 기저와 진리표 추론을 위해 LLM에게 문자열 매칭, 백트래킹, 오류 복구 가르치기
Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles
한국어 초록
이 논문은 비트 조작 퍼즐(Bit Manipulation Puzzles)에 초점을 맞춰 NVIDIA Nemotron 모델 추론 챌린지를 위한 알고리즘적 혁신을 제시한다. 이 과제에서 목표는 입력 이진 문자열을 출력으로 변환하는 숨겨진 논리 규칙을 발견한 뒤, 미공개 입력에 적용하는 것이다. 대규모 언어 모델(LLM)은 이 과제에서 악명 높게 어려움을 겪는데, 전통적인 방법은 복잡한 불리언 논리와 산술 연산을 시뮬레이션하도록 강제하여 환각(hallucination)을 초래한다. 또한 비트 연산(시프트, 회전, 논리 게이트의 조합)의 탐색 공간은 심각한 조합 폭발(combinatorial explosion) 문제를 겪는다. 이러한 계산적 난해성을 극복하기 위해, 우리는 산술 논리를 완전히 포기하고 문자열 유사도(string similarity), 구조적 탐색, 자율 오류 복구를 채택한 새로운 접근법을 제시한다. 핵심 기여는 다음과 같다: 1. 기저(Bases)와 진리표(Truth Table) 공식화: 논리 게이트 추론을 기저 선택 과제로 재구성하고, 문자열 유사도(최소 비트 플립)를 활용하여 기본 변환("기저")을 분리하고 복잡한 산술 없이 진리표를 추론한다. 2. 백트래킹 DFS와 오류 복구: 후보 기저를 테스트하고, 예시 전반의 논리적 충돌을 감지하며, 실패 시 백트래킹하여 견고한 오류 복구를 수행하는 탐색 과정을 형식화한다. 3. 비트 토큰화(Bit Tokenization)와 상호작용적 추론 SFT: 토크나이저가 이진 문자열을 개별 단일 비트 토큰으로 인코딩하도록 강제한다. 동적 마스킹을 사용하여 외부 오라클 피드백을 시뮬레이션하고, 모델이 자체적으로 가설 수립, 자기 평가, 백트래킹을 수행하도록 학습시킨다. 비트 조작 퍼즐에서 평가한 결과, 우리의 접근법은 96% 이상의 검증 정확도를 달성했다. 이는 해당 카테고리에서 최고 성능을 나타내며, 대회 전체 7위 달성에 기여했다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.23672v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SWE-DeceptionBench: 소프트웨어 개발 생명주기 전반에서 LLM의 기만적 행동 벤치마킹
SWE-DeceptionBench: Benchmarking Deceptive Behaviors of LLMs Across the Software Development Lifecycle
대규모 언어 모델(LLM)은 소프트웨어 개발 생명주기 전반에서 점점 더 많이 사용되고 있다. LLM에 대한 이러한 의존도 증가는 신뢰성에 대한 우려를 불러일으키며, 그중에서도 기만(deception)은 특히 중요한 위험 요소이다. 기만적 행동은 오해를 유발하는 응답이나, 정보를 조작·은폐·왜곡하는 것을 돕는 형태로 나타난다. 이러한 행동을 연구하기 위해, 우리는 소프트웨어 공학에서 LLM의 기만을 평가하기 위한 벤치마크인 SWE-DeceptionBench를 소개한다. 이 벤치마크는 여섯 개의 생명주기 단계와 두 가지 기만 유발 요인을 다룬다: 모델이 실현 불가능하거나 상충되는 요구사항을 인지하면서도 이를 달성 가능한 것처럼 제시하는 능동적 기만(Active Deception), 그리고 모델이 타인을 속이려는 명시적인 사용자 요청의 이행을 돕는 수동적 기만(Passive Deception)이다. 우리는 추가로 외부 유인의 영향을 연구하기 위해 중립(Neutral), 보상(Reward), 압박(Pressure) 조건을 도입하였으며, 이를 통해 중국어와 영어로 구성된 총 720개의 테스트 인스턴스를 구성하였다. 일곱 개의 주요 LLM을 평가한 결과, 중립 조건에서도 상당한 기만이 나타났으며, 능동적 기만의 전체 비율은 49.88%, 수동적 기만의 전체 비율은 64.29%에 달하였다. 기만 비율은 생명주기 단계에 따라 달라졌으며, 외부 유인은 능동적 기만과 수동적 기만에 서로 다른 정도로 영향을 미쳤다. 우리는 또한 경량 방어 기법을 평가하였으며, 가드 모델(guard model)이 많은 기만적 요청을 탐지하지 못하고, Self-Reminder가 기만적 응답을 감소시키지만 완전히 제거하지는 못한다는 것을 발견하였다. 이러한 결과는 신뢰할 수 있는 LLM 기반 소프트웨어 공학을 지원하기 위해 더 효과적인 기만 탐지 및 완화 방법이 필요함을 시사한다.
대규모 언어 모델은 콜롬비아 법률을 알고 있는가? 콜롬비아 법률 체계를 위한 신뢰성 벤치마크
Do Large Language Models Know Colombian Law? A Reliability Benchmark for the Colombian Legal System
대규모 언어 모델(LLM)은 법률 실무, 교육, 연구를 지원하는 데 점점 더 많이 활용되고 있지만, 미국 이외의 국가 법률 체계에서 이들의 신뢰성은 대부분 문서화되지 않은 상태로 남아 있습니다. 본 연구에서는 콜롬비아 법률 체계에 대한 LLM 신뢰성을 평가하기 위한 전문가 검증 벤치마크를 소개합니다. 이 벤치마크는 다단계 전문가 검토를 거친 인간 참여형(human-in-the-loop) 파이프라인을 통해 구축되었으며, 10개 법률 분야와 3가지 질문 형식(폐쇄형 객관식, 반개방형, 개방형 IRAC)에 걸친 1,042개 문항으로 구성됩니다. 우리는 형식에 적합한 지표를 사용하여 15개의 최신 상용 및 공개 가중치(open-weight) 모델을 평가합니다. 폐쇄형 질문의 정확도는 0.905(Gemini 3.1 Pro)부터 0.577까지 큰 폭의 차이를 보였으나, 자유 서술형 법률 답변의 경우 모든 모델에서 사실적 정확성이 0.45(0-1 척도 기준)를 넘지 못했습니다. 우리는 답변 관련성과 정확성 사이의 괴리(Spearman rho = -0.46)를 발견했습니다. 즉, 모델들은 질문에 부합하게 그럴듯하게 응답하면서도 실제로는 틀리는 경우가 잦았으며, 이는 특히 비전문가 사용자에게 우려되는 패턴입니다. 폐쇄형 질문 정확도와 자유 서술형 정확도는 순위 상관관계가 매우 높아(rho = 0.94), 비용이 적게 드는 객관식 스크리닝으로 모델 순위를 예측할 수는 있지만 절대적인 신뢰성은 과대평가되는 것으로 나타났습니다. 루브릭 기반의 독립적인 LLM 판정관과 블라인드 인간 전문가 점수 산정 모두 자유 서술형 순위를 재현했습니다(rho >= 0.88). 판정관 분석 결과, 모델이 인용한 법규범 중 약 절반만이 정확했으며 나머지는 부정확하거나 존재하지 않는 것으로 추가 확인되었습니다. 신뢰성은 법률 분야에 따라 체계적으로 차이를 보였으며 질문 복잡도에 따라 역U자형(inverted-U) 추세를 따랐습니다. 본 연구 결과는 현재의 LLM이 콜롬비아 법률 업무에 활용되려면 전문가의 감독이 필요하며, 권위 있는 출처에 답변을 그라운딩(grounding)하는 것이 신뢰성을 높이기 위한 유망한 방안임을 보여줍니다. 재현 가능한 평가를 지원하기 위해 벤치마크 구축 파이프라인을 공개합니다.
RetryBench: GPT 도구 사용에서 재시도 권한과 복구 결과의 분리
RetryBench: Separating Retry Permission from Recovery Outcomes in GPT Tool Use
외부 도구를 호출하는 LLM 에이전트는 도구 호출이 시간 초과될 때 어떻게 할지 결정해야 한다. 재시도는 중복 부작용의 위험이 있고, 재시도하지 않으면 작업이 미완료로 남을 수 있다. 본 연구는 도구를 사용하는 LLM 에이전트의 재시도 결정과 실패 복구를 위한 평가 프로토콜인 RetryBench를 제시한다. 각 결정은 관측과 일치하는 모든 숨겨진 실행 세계에서 재생하여 재시도 허용 여부(재시도가 멱등성 키 보장이나 미실행 증명으로 정당화되는가?), 확정된 효과(중복과 누락), 완료 여부에 대해 채점된다. 네 가지 합성 소프트웨어 엔지니어링 과제에서 두 가지 통제된 프롬프트 민감도 연구(1,728건의 결정)를 수행한다. 연구 1(멱등성 키 설명): 계약을 고정한 상태에서 GPT-5.6 Luna는 추가 키가 "Candidate recovery key"로 설명될 때 40건 중 10건에서 유효한 멱등성 키를 재사용하지만, "Alternative key string"으로 설명될 때는 40건 중 39건에서 재사용한다. 계열별로 세 가지 표현을 추가했을 때 격차는 27/120 대 113/120이다. GPT-5.6 Sol과 Terra는 상한에 도달해 있다(40/40). 연구 2(행동 순서): 조회 보장이 불충분하게 명시된 조건에서, 재시도가 먼저 나열될 때 GPT-5.6 Terra와 GPT-5.4의 재시도율이 주로 두 과제에서 17~27 퍼센트포인트 낮아지며(선택지 순서 편향), 어느 행동이 더 나은지에 대해서는 주장하지 않는다. 연구 결과는 연구자가 선택한 표현, 네 가지 과제, 고정되지 않은 모델 별칭에 한정된다. 코드와 모든 모델 응답을 공개한다.
StoreBench: 자율 운영자 에이전트의 평가 및 학습을 위한 라이브 커머스 환경
StoreBench: A Live-Commerce Environment for Evaluating and Training Autonomous Operator Agents
강화학습(RL) 환경은 이제 사후 학습(post-training)에서 대규모 언어 모델(LLM)의 역량을 향상시키는 주요 수단이 되었으나, 대부분의 에이전트 벤치마크는 여전히 정적입니다. 즉, 에이전트가 행동할 때만 환경이 변화하고, 보상은 최종적인 판정으로 주어지며, 통과 기준은 자의적으로 설정됩니다. 본 논문에서는 에이전트가 프로덕션 수준의 상거래 백엔드에서 중간 규모의 온라인 의류 매장을 운영하며 불확실성 속에서 장기 계획 수립 및 경제적 판단력을 시험받는 라이브 커머스 환경인 StoreBench를 소개합니다. 고객은 24시간 내내 주문하고, 공급업체는 가격을 재책정하거나 공급에 실패하며, 시장 충격은 부분적인 예고만 있거나 예고 없이 발생합니다. 에이전트는 실제 인간 운영자가 사용하는 것과 동일한 29개의 판매자 도구를 통해 행동하며, 취해진 행동의 함수로 시뮬레이션 시간을 계산하는 윈도우 기반 운영 예산 하에서 작동하므로 모델 지연 시간이 시뮬레이션 시간에 영향을 미칠 수 없습니다. 통과 임계값은 스크립트 기반 앵커 정책을 기준으로 보정되었고, 보상은 다양한 보상 해킹 목록에 대비해 강화되었으며, 일련의 행동이 주어지면 모든 에피소드가 동일하게 재현됩니다. 본 연구에서는 추론 노력을 일치시킨 상태에서 세 가지 월드 시드에 걸쳐 30~45일 및 시뮬레이션된 1년 전체에 해당하는 11개 시나리오를 바탕으로 7개의 프론티어 LLM을 평가합니다. 평균적으로 스크립트 기반 스마트 트리아지(smart-triage) 정책에 필적하는 모델은 없었습니다. 최고 성능을 보인 DeepSeek-V4-Pro는 휴리스틱의 97% 대비 49%의 태스크-시드 셀을 통과했습니다. 동일한 도구와 예산을 사용하여 작업한 인간 전문가는 모든 모델보다 높은 점수를 기록했습니다(평균 종합 점수 0.708 대 0.700). Claude Code 하네스 기반의 시뮬레이션된 1년 전체에 걸쳐 대다수 모델은 극적인 성능 향상을 보입니다. GRPO 사후 학습 실행에서 서로 다른 5개의 태스크로만 학습된 Qwen3.5-27B는 홀드아웃(held-out) 평가 태스크에서의 평균 종합 점수를 0.136에서 0.373으로 향상시켰습니다. 본 연구에서는 학습 분할용 예시 태스크 5개, 샘플 궤적 10개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.
검토는 더 강력한 모델을 거의 능가하지 못한다: LLM 파이프라인에서 검증과 능력 전이의 분리
Review Rarely Beats the Stronger Model: Separating Verification from Capability Transfer in LLM Pipelines
수학 문제에서 Qwen3-8B가 Llama-3.1-8B를 검토하면 정확도가 33.2점 상승하지만, Qwen3-8B 단독의 정확도가 그 결과보다 6.4점 더 높다. 다른 모델의 답을 검토하는 방식은 보통 생성 모델 대비 향상 폭으로 평가된다. 본 연구는 이러한 평가가 검증(verification)과 능력 전이(capability transfer)를 혼동한다는 점을 보인다. 검증은 어느 한 모델 단독보다 더 높은 정확도를 더하는 것이고, 능력 전이는 더 강한 검토 모델이 스스로도 낼 수 있었던 답을 제공하는 것이다. 수학, 지식, 코드, 추론 영역에서 12개 오픈 웨이트 모델(3B~72B)의 48개 쌍에 대해 더 강한 모델 단독과 비교해 측정한 결과, 검토 방식이 이를 능가하는 경우는 96개 검토 방향 중 9개에 불과했으며, 능력 격차가 클수록 성능이 더 나빠졌다. 그 원인은 앵커링이다. 검토 모델이 대체로 생성 모델을 따라가면서 자신의 올바른 답을 버린다. 검토 방식은 더 강한 모델 단독 대비 2.6~2.8배의 비용이 드는 반면, 동일한 두 번의 호출을 사용하는 선택기(selector)는 검토 방식보다 2.7~4.2점 더 정확하면서 비용도 더 저렴하다. 검증에 관한 연구는 생성 모델 대비 향상 폭만이 아니라 더 강한 모델 단독의 성능도 함께 보고해야 한다.
제안된 것은 대체된 것이 아니다: 메모리 폐기(memory-retirement) 게이트로서의 시스템원(System One) 모델에 대한 사전등록 평가
Suggested Is Not Superseded: A Pre-Registered Evaluation of a System-One Model as a Memory-Retirement Gate
어시스턴트의 장기 기억(long-term memory)에는 새로운 발화(utterance)가 기존에 저장된 주장(claim)을 언제 폐기(retire)할지 결정하는 게이트(gate)가 필요하다. 이 단계에 대한 벤치마크 레이블은 쌍(pair)을 변경되었는지 아닌지로만 표시하므로, 확정된 변경(established change)에 따라 작동하는 게이트와 단서(hint)에 따라 작동하는 게이트를 구별하지 못한다. 우리는 이 둘을 구분하는 태스크 계약(task contract)을 작성하여(SUPERSEDED 대 NEEDS-CONFIRMATION 대 COMPATIBLE), STALE(변경 쌍과 동일 사용자 대조군으로 구성)로부터 만들어진 500개의 테스트 쌍에 대해 세 명의 LLM 주석자(annotator)와 두 명의 인간 심판자(저자 1명과 추가 주석자 1명; 출처(provenance)를 명시함)로 레이블을 부여하고, 사전등록된 가설(pre-registered hypotheses) 하에서 타입이 지정된(typed) "시스템원(System One)" 결정 모델인 Jev를 평가한다. STALE이 변경되었다고 표시한 179개의 테스트 쌍 중 72개가 계약에서 정한 확정된 변경의 기준을 충족한다. Jev는 동일 대화 내 변경되지 않은 141개의 사례에서 단 한 번도 주장을 폐기하지 않았다. Jev의 실패는 조기 폐기(premature retirement)이다: 이진 게이트(binary gate)는 변경이 단지 제안(suggested)된 것에 불과한 주장의 39.2%를 폐기한다. 삼항 결정(three-way decision)은 이를 15.3포인트(point)의 탐지 비용(detection cost)으로 15.5%까지 낮추는데, 이는 우리가 사전등록한 10포인트 예산(budget)을 초과하며, 이진 게이트 자체의 임계값 프런티어(threshold frontier) 위에 위치한다; 이러한 판정(verdict)은 골드 레이블(gold label)에 대한 세 가지 해석(readings) 모두에서 유지된다. 두 번째 주석자의 레이블을 기준으로 채점한 보류된(held-out) 볼트(vault)에서, 불확실한 사례를 추론 모델(reasoning model)로 에스컬레이션(escalate)하고 개발(development) 데이터에서 가장 우수했던 캐스케이드(cascade)는 단순히 임계값을 높이는 것과 구별되지 않았다(조기 폐기 비율 26.8% 대 개발 데이터에서의 6.5%). 이 격차(gap)의 일부는 골드 레이블에서 비롯된다: 해당 주석자의 해석에 비추어 볼 때, LLM 다수결(majority) 골드는 동일 계열(same-family)의 에스컬레이션 모델과 오류 대부분을 공유하며, 이진 레이블에 대한 한 아이덴티티(identity)는 이러한 공유된 오류가 얼마나 가려지는지를 보여준다. 나머지는 개발 데이터에서의 소규모 샘플 선택(small-sample selection)에 기인한다. 빌더(builder)들에게 이는 이진 점수(binary score)를 삭제(delete) 동작에 바로 연결해서는 안 된다는 것을 의미한다: 제안된 변경은 보류 중인 증거(pending evidence)로 라우팅(route)하고, 이 정도 규모의 개발 데이터에서 선택된 캐스케이드를 신뢰하지 말아야 한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.