論文の概要: Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles

• arxiv url: http://arxiv.org/abs/2606.23672v1
• Date: Mon, 22 Jun 2026 17:57:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 17:15:05.071471
• Title: Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles
• Title（参考訳）: LLMの文字列マッチング, バックトラック, エラーリカバリを指導して, 組合せ的に爆発するビット操作パズルの基底と真理表を推定する
• Authors: Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri, Aditya Prasad, Shubham Jain,
• Abstract要約: 本稿では,NVIDIA Nemotron Model Reasoning Challengeにおけるアルゴリズムの革新について述べる。 目的は、入力バイナリ文字列を出力に変換する隠された論理規則を発見し、未知の入力に適用することである。 本稿では,文字列類似性,構造化探索,自動誤り回復に完全に有利な算術論理を放棄する手法を提案する。
• 参考スコア（独自算出の注目度）: 5.405746164698907
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: 本稿では,bit Manipulation Puzzlesに着目し,NVIDIA Nemotron Model Reasoning Challengeのアルゴリズム革新について述べる。 このタスクでは、入力バイナリ文字列を出力に変換する隠された論理規則を発見し、未知の入力に適用する。 従来の手法では、複雑なブール論理と算術をシミュレートせざるを得ず、幻覚に繋がる。 さらに、ビットワイズ演算(シフト、回転、論理ゲートの組み合わせ)の探索空間は、深刻な組合せの爆発に悩まされる。 この計算難易度を克服するために,文字列類似性,構造化探索,自律的誤り回復に完全に有利な算術論理を放棄する手法を提案する。 私たちのコアコントリビューションは次のとおりです。 1. 基底と真理表定式化: 論理ゲート推論を基本選択タスクに再設計し、文字列類似性(最小ビットフリップ)を活用してプリミティブ変換(ベース)を分離し、複雑な算術を使わずに真理表を導出する。 2. DFSとエラーリカバリのバックトラック: 候補ベースのテスト,例間の論理的衝突の検出,堅牢なエラーリカバリの失敗時のバックトラックを形式化する。 3.bit Tokenization and Interactive Reasoning SFT: トークンを個別のシングルビットトークンとしてエンコードするよう強制する。 動的マスキングを用いて外部のオラクルのフィードバックをシミュレートし、モデルを仮説化、自己評価、バックトラックをネイティブに訓練する。 提案手法はビット操作パズルに基づいて評価され,96%以上の検証精度が得られた。 これはこのカテゴリーで最高のパフォーマンスを示し、コンクールで総合7位にランクインした。

関連論文リスト

• 4OPS: Structural Difficulty Modeling in Integer Arithmetic Puzzles [0.0]
  算術パズルゲームは、数学的推論タスクの難しさを研究するための制御された設定を提供する。 我々は、到達可能な目標を列挙し、最小操作の証人を抽出し、大規模ラベリングを可能にする、正確な動的プログラミング解法を開発する。 難易度は、正確な目撃者から導かれる、解釈可能な構造的属性の小さなセットによって完全に決定されることを示す。
  論文  参考訳（メタデータ） (2026-03-26T12:01:39Z)
• Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms [10.292476979020522]
  基本的に任意の回路をフィードフォワードニューラルネットワーク(NN)に変換するシステムメタアルゴリズムを提案する。 あらゆるデジタルコンピュータ上で、我々の構成は回路を正確にエミュレートしている ― 近似がなく、丸めず、モジュラーなオーバーフローも含まない ― ニューラルネットワークの範囲を超えて推論タスクが存在しないことを実証している。
  論文  参考訳（メタデータ） (2025-08-25T21:55:37Z)
• Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks [13.351162559710124]
  無限幅限界における2層完全連結ネットワークのトレーニング力学について検討する。 このようなモデルの十分な大規模なアンサンブルが、高い確率で正確に実行するためにどのように訓練されるかを示す。 対数的に多くのトレーニングデータだけを用いて効率よく達成できることを示します。
  論文  参考訳（メタデータ） (2025-02-24T00:50:02Z)
• Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning [53.57895922042783]
  大規模言語モデル(LLM)は、チェーン・オブ・シークレット(CoT)データに基づいて訓練された場合、推論と計画が優れている。 そこで我々は,遅延離散トークンを用いて推論過程を部分的に抽象化するハイブリッド表現を提案する。
  論文  参考訳（メタデータ） (2025-02-05T15:33:00Z)
• Can Transformers Reason Logically? A Study in SAT Solving [17.15701291424892]
  本研究では,デコーダのみのトランスフォーマーの論理的推論能力について,SAT問題の観点から検討する。 我々は,デコーダのみのトランスフォーマーが,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いて,一様でない計算モデルで 3-SAT を決定できることを示す。
  論文  参考訳（メタデータ） (2024-10-09T21:01:52Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  カリキュラムベースの論理認識型チューニングフレームワークであるLACTを提案する。 具体的には、任意の一階論理クエリをバイナリツリー分解によって拡張する。 広く使われているデータセットに対する実験では、LATは高度な手法よりも大幅に改善(平均+5.5% MRRスコア)し、新しい最先端技術を実現している。
  論文  参考訳（メタデータ） (2024-05-02T18:12:08Z)
• LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers [60.009969929857704]
  論理的推論は、科学、数学、社会に潜在的影響を与える可能性のある人工知能にとって重要なタスクである。 本研究では、LINCと呼ばれるモジュール型ニューロシンボリックプログラミングのようなタスクを再構成する。 我々は,FOLIOとProofWriterのバランスの取れたサブセットに対して,ほぼすべての実験条件下で,3つの異なるモデルに対して顕著な性能向上を観察した。
  論文  参考訳（メタデータ） (2023-10-23T17:58:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。