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

📄 arXiv: 2606.23672v1 📥 PDF

作者: Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri, Aditya Prasad, Shubham Jain

分类: cs.AI

发布日期: 2026-06-22

备注: 22 pages, 4 figures, 2 tables. 7th Place Solution for the NVIDIA Nemotron Model Reasoning Challenge (Kaggle)

💡 一句话要点

提出一种新方法解决大规模位操作谜题中的逻辑推理问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 逻辑推理 位操作 字符串相似性 错误恢复 深度学习 模型训练 自动化推理

📋 核心要点

  1. 现有方法在处理位操作谜题时，LLMs常常因复杂布尔逻辑和算术运算而产生错误推断。
  2. 我们提出了一种基于字符串相似性的方法，通过选择基础变换和真值表推导来简化逻辑推理过程。
  3. 在位操作谜题的评估中，我们的方法实现了超过96%的验证准确率，成为该类别中的最高表现，最终在比赛中获得第七名。

📝 摘要（中文）

本文介绍了我们在NVIDIA Nemotron模型推理挑战中的算法创新，重点关注位操作谜题。该任务的目标是发现将输入二进制字符串转换为输出的隐藏逻辑规则，并将其应用于未见输入。大型语言模型（LLMs）在此任务中表现不佳，传统方法迫使它们模拟复杂的布尔逻辑和算术，导致错误推断。此外，位操作的搜索空间（移位、旋转和逻辑门的组合）面临严重的组合爆炸。为克服这一计算不可行性，我们提出了一种新方法，完全放弃算术逻辑，转而采用字符串相似性、结构化搜索和自主错误恢复。

🔬 方法详解

问题定义：本文旨在解决位操作谜题中的逻辑推理问题，现有方法因复杂的布尔逻辑和算术运算而导致LLMs产生错误推断，搜索空间的组合爆炸使得计算变得不可行。

核心思路：我们的方法通过字符串相似性来重新构建逻辑门推导，将其转化为基础选择任务，从而避免复杂的算术运算。

技术框架：整体架构包括基础和真值表的构建、回溯深度优先搜索（DFS）和错误恢复机制。首先，通过字符串相似性识别基础变换，然后进行结构化搜索并在失败时进行回溯。

关键创新：最重要的创新在于放弃传统的算术逻辑，采用字符串相似性和动态掩码技术，使模型能够进行自我评估和回溯，从而提高推理的准确性和鲁棒性。

关键设计：我们将二进制字符串编码为单比特令牌，并使用动态掩码模拟外部反馈，训练模型进行假设、评估和回溯。

📊 实验亮点

在位操作谜题的实验中，我们的方法达到了超过96%的验证准确率，显著高于现有基线，展示了在逻辑推理任务中的优越性，并最终在比赛中获得第七名的佳绩。

🎯 应用场景

该研究的潜在应用领域包括自动化逻辑推理、编程语言的错误检测与修复、以及复杂系统中的决策支持。通过提高LLMs在逻辑推理任务中的表现，未来可在更多需要精确推理的领域中发挥重要作用。

📄 摘要（原文）

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.