教LLM字符串匹配、回溯与错误恢复：为组合爆炸的位运算谜题推断基与真值表

本文介绍我们在NVIDIA Nemotron模型推理挑战赛上的算法创新——聚焦位运算谜题。该任务目标是发现把输入二进制串变换为输出的隐藏逻辑规则——再应用到未见输入。大语言模型（LLM）在此出了名地吃力：传统方法强迫它们模拟复杂布尔逻辑与算术——导致幻觉。此外——位运算（移位、旋转与逻辑门的组合）的搜索空间遭受严重组合爆炸。为克服这一计算难题——我们提出全新方法：彻底放弃算术逻辑——改用字符串相似度、结构化搜索与自主错误恢复。核心贡献：1. 基与真值表形式化——把逻辑门推断重构为基选择任务——利用字符串相似度（最少位翻转）隔离原始变换（“基”）——无需复杂算术即可推断真值表。2. 回溯DFS与错误恢复——形式化测试候选基、跨示例检测逻辑碰撞、失败即回溯的搜索过程——实现稳健错误恢复。3. 位token化与交互推理SFT——强制分词器把二进制串编码为单比特token；用动态掩码模拟外部神谕反馈——训练模型原生地假设、自评与回溯。在位运算谜题上评估——我们的方法取得超96%验证准确率——为该类别最高。这些算法与训练创新最终为团队赢得比赛最佳微调方法与最佳数据/合成数据方法奖——并获总榜第7名。