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

Source: arXiv:2606.23672 · Published 2026-06-22 · By Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri, Aditya Prasad, Shubham Jain

TL;DR

This paper addresses the difficult problem of solving bit manipulation puzzles, where an AI must deduce a hidden logical bitwise transformation rule from a small number of input-output binary examples and generalize to unseen inputs. Traditional large language models struggle due to the combinatorial explosion of possible boolean logic formulas involving shifts, rotations, and logic gates, resulting in hallucinations and failure. To overcome this, the authors propose a novel paradigm that abandons simulating arithmetic and boolean algebra directly. Instead, they reframe the problem into a discrete string similarity and base selection task, leveraging minimal bit flips between outputs to isolate a small subset of spatial bases (bit pointers like shifts and rotations) influencing each output bit. They solve a derived Set Cover problem with a depth-first search backtracking algorithm, coupled with robust error recovery via collision detection. Finally, they embed this search logic into an LLM by fine-tuning it on synthetic reasoning traces and using a strict single-bit tokenization with interactive masking to simulate oracle feedback and teach the model to hypothesize, self-evaluate, and backtrack. Evaluated on 1,602 puzzles under real Kaggle contest constraints, the deterministic solver reached 98.63% theoretical accuracy and the fine-tuned LLM achieved over 96% validation accuracy, representing a new state-of-the-art for this class of problems. This combination of reformulating the reasoning task mathematically and teaching an LLM advanced search-with-backtracking reasoning via dynamic masking is the key innovation enabling these strong results.

Key findings

• The deterministic solver achieved 98.63% accuracy on 1,602 puzzles, with failures due to fundamental underdetermined constraints, not algorithmic limitations.
• The bit manipulation search space explodes combinatorially: 3-base rules yield over 330,000 candidate formulas with ordering and logical connections.
• Reframing puzzles as a discrete base-selection and minimal bit-flip constraint problem reduces arithmetic deduction to Set Cover search over 22 spatial bases.
• Backtracking DFS with global collision detection verified consistency across all examples, enabling robust error recovery and pruning of spurious bases.
• Strict single-bit tokenization during fine-tuning allowed the LLM to generate precise bitwise reasoning traces without tokenization artifacts.
• Interactive reasoning via dynamic masking simulating oracle feedback enabled the LLM to learn to hypothesize, detect contradictions, and backtrack logically within a single supervised fine-tuning regime.
• The Synthetic Only fine-tuned LLM reached 96.13% accuracy, nearly matching the deterministic upper bound and successfully navigating multiple backtracking steps during inference.
• Introducing the original dataset for final fine-tuning slightly degraded recall (to 94.63%) while increasing average token generation, highlighting a tradeoff in multi-task optimization.

Threat model

The adversary is the AI solver model attempting to discover a hidden logical transformation rule mapping 8-bit inputs to outputs based only on example pairs. The model must avoid hallucinations caused by the combinatorial explosion of possible logical formulas and cannot brute-force all candidates due to computational constraints. The threat model assumes no adversarial corruption of data and that the puzzle logic is a deterministic boolean function over the defined bases.

Methodology — deep read

1. Threat Model & Assumptions: The task involves deducing a hidden Boolean function mapping 8-bit input strings to output strings. The adversary is the AI model, which must find this function given 8 example input-output pairs and generalize to unseen inputs. The AI does not have explicit circuit or formula access, only examples, and must avoid hallucinations despite the huge combinatorial search space in possible logic compositions.

2. Data: The puzzle dataset comprises 1,602 bit manipulation puzzles with 8-bit inputs and outputs. Each puzzle provides 8 example input-output examples, forming a dataset of 64 input-output bit mappings (8 output bits × 8 examples). The target is to predict outputs for a novel input string per puzzle. For training the LLM, synthetic Chain-of-Thought reasoning traces were generated automatically via the deterministic solver; original contest data was used for final stage fine-tuning.

3. Architecture / Algorithm:

• The approach decomposes each output bit into a boolean function over 22 spatial bases derived from bit shifts, rotations, and the original bit. These bases serve as discrete binary features.
• Minimal bit flip differences between output zero and one examples generate Flip Traces, logical constraints representing which bases must be responsible for output changes.
• The core problem reduces to a classic Set Cover search for the minimal subset of bases covering all flip traces.
• A frequency-guided depth-first search backtracking algorithm iteratively guesses subsets of bases, verifying their validity globally by checking for collisions—cases where identical base inputs map to conflicting outputs.
• When collisions are detected, the search backtracks, ensuring robust error recovery.

4. Training Regime:

• The LLM tokenizer was forced to encode individual bits as atomic tokens during supervised fine-tuning via custom data scripts, avoiding natural BPE merges that destroy bit alignment.
• Dynamic masking was applied during training to simulate an external Oracle's feedback. The model only incurs loss on its own hypothesizing tokens but ignores the oracle feedback tokens, enabling learning of interactive reasoning and backtracking in one offline SFT process without costly reinforcement learning.
• The LLM was trained with approximately 1,200 steps within 30-hour GPU time constraints, checkpointing manually.

5. Evaluation Protocol:

• The deterministic solver was evaluated on 1,602 puzzles to establish the theoretical upper bound.
• The fine-tuned LLM was evaluated on the same puzzles, with accuracy measured based on correct target output predictions.
• Backtracking steps taken by the LLM during inference were tracked to measure if it learned System-2 style error recovery.
• Ablation tested synthetic-only training vs additional fine-tuning on original contest data.

6. Reproducibility:

• The deterministic solver and synthetic CoT data generation pipeline source code are publicly available on Kaggle.
• The final LLM weights and training code are not explicitly stated to be released.

Example end-to-end: Given 8 input-output examples, the bases for all bits are computed, and Flip Traces extracted by comparing outputs with minimal bit flips. The DFS backtracking searches for base subsets that cover all traces without collisions. Once found, the empirical truth table is synthesized and applied to unseen inputs to predict outputs. The LLM is fine-tuned on synthetic traces generated from this algorithm, learning to replicate the search and backtracking logic autonomously via dynamic masking of oracle feedback.

Technical innovations

• Reformulating bitwise logical rule deduction as a discrete base-selection and minimal bit-flip string matching problem, eliminating complex arithmetic logic.
• A frequency-guided depth-first search backtracking algorithm with global collision detection to robustly find minimal base subsets that satisfy all logical constraints.
• Strict single-bit tokenization during LLM fine-tuning circumventing standard BPE tokenization issues in bit-string reasoning.
• Interactive reasoning supervised fine-tuning using dynamic masking to simulate oracle feedback and train the LLM to self-hypothesize, detect errors, and backtrack without reinforcement learning.

Datasets

• NVIDIA Nemotron Bit Manipulation Puzzles — 1,602 puzzles — public Kaggle contest dataset
• Synthetic Chain-of-Thought reasoning traces — Generated by deterministic solver — public Kaggle code

Baselines vs proposed

• Deterministic solver: Accuracy = 98.63% on 1,602 puzzles (theoretical upper bound)
• LLM Synthetic Only fine-tuned: Accuracy = 96.13%, Avg Tokens = 5,039
• LLM Synthetic + Original fine-tuned: Accuracy = 94.63%, Avg Tokens = 5,126

Limitations

• Deterministic solver fails on underdetermined puzzles where provided examples cannot isolate a unique rule.
• LLM occasionally hallucinated or failed to backtrack properly, causing approximately 29 of 62 inference errors.
• Long backtracking sequences led to context window truncation, causing 30 of 62 errors due to token limits.
• Final mixed-task fine-tuning caused some degradation in specific bit manipulation accuracy.
• LLM training was limited to about 1,200 steps due to strict compute constraints, possibly limiting convergence.
• The approach requires discrete 8-bit puzzles; scalability to longer bitstrings or more complex logic is not shown.

Open questions / follow-ons

• How well does the base-selection and search approach scale to wider bit widths or longer puzzles beyond 8 bits?
• Can the interactive reasoning dynamic masking SFT paradigm be extended to teach general algorithmic backtracking in other domains?
• What are the impacts of alternative tokenization or model architectures on bitwise reasoning and error recovery?
• Could reinforcement learning integrated with dynamic masking further improve backtracking efficiency and accuracy?

Why it matters for bot defense

This work is highly relevant for designing bot-defense systems requiring precise bitlevel reasoning or logical deduction embedded within language models. By reframing complex arithmetic or boolean deductions as discrete string similarity and feature-selection problems, this approach avoids common failure modes of LLMs hallucinating arithmetic. The demonstrated integration of backtracking search and explicit error-recovery feedback simulated via dynamic masking offers a promising technique to teach models robust algorithmic reasoning within constrained compute. For CAPTCHA or bot-defense engineers, this suggests a strategy to incorporate structured search with supervised fine-tuning to improve solver reliability on puzzles or challenges that require exact, non-ambiguous logical operations rather than heuristic guesswork. However, the approach may require careful engineering to address context window constraints and to tune tokenization for precise bitwise alignment.

Cite

@article{arxiv2606_23672,
  title={ Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles },
  author={ Prateek Agnihotri and Sanchit Jain and Prabhat Agnihotri and Aditya Prasad and Shubham Jain },
  journal={arXiv preprint arXiv:2606.23672},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.23672}
}

Read the full paper

• arXiv:2606.23672 (abstract)
• arXiv:2606.23672 (PDF)