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

Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri, Shubham Jain · 2026

Read Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles by Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri, Shubham Jain (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-23672.txt.

Introduction

Agnihotri and colleagues report how their team taught language models to crack bit manipulation puzzles, in a 2026 paper from a model reasoning competition. The puzzles show a few examples of an eight bit binary string transformed by a hidden rule, then ask for the output on a new input. The rules combine shifts, rotations, and logic gates in arbitrary ways, so the search space explodes and models simulating the arithmetic tend to hallucinate.

The team abandoned arithmetic in favor of string similarity. Their method reframes rule finding as choosing primitive transformations, called bases, by counting bit flips between outputs, then deducing each base's truth table. A depth first search tests candidate bases, detects contradictions across examples, and backtracks to recover from errors. The approach topped the category with validation accuracy above ninety six percent.

Catalog record

CREATORPrateek Agnihotri, Sanchit Jain, Prabhat Agnihotri, Shubham Jain
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.23672

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri, Shubham Jain Abstract This paper presents the key ideas and algorithmic innovations developed during our participation in the NVIDIA Nemotron Model Reasoning Challenge, focusing specifically on the Bit Manipulation Puzzles, which was widely considered one of the most challenging tasks to fully solve. In this task, the objective is to discover a hidden logical rule that transforms a given set of input binary strings into outputs, and then accurately apply that rule to a new, unseen input. Large Language Models (LLMs) notoriously struggle with this; traditional methods force them to simulate complex boolean logic and arithmetic in their heads, which frequently leads to hallucinations. Furthermore, the search space of possible bitwise operations—comprising arbitrary combinations of shifts, rotations, and logic gates—suffers from a severe combinatorial explosion. Because this makes traditional logic-gate deduction computationally intractable for LLMs, 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: • Bases and Truth Table Formulation: We reframe logic-gate deduction into a base-selection task, leveraging string similarity (minimal bit flips) between outputs to isolate primitive transformations (“bases”) and deduce their truth tables without complex arithmetic. • Backtracking DFS and Error Recovery: We formalize a search process that tests candidate bases, detects logical collisions across examples in a puzzle, and backtracks upon failure to perform robust error recovery. • Bit Tokenization and Interactive Reasoning SFT: We force the tokenizer to encode binary strings as individual, single-bit tokens, and 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 > 96 % >\!96\% validation accuracy—representing the highest performance in this category by any participating team and driving our 7th Place overall finish in the contest. † † footnotetext: The complete Python source code for our deterministic Set Cover solver and synthetic Chain-of-Thought (CoT) data generation pipeline is publicly available at: https://www.kaggle.com/code/prateekagnihotri/bit-manipulation-cot-bit-flip-s-original 1 Introduction Modern Artificial Intelligence excels at generating fluent text and heuristic reasoning, but exact, deterministic algorithmic logic remains one of its most difficult frontiers. A rigorous benchmark for this capability is the “Bit Manipulation” puzzle, featured as a core category in the NVIDIA Nemotron Model Reasoning Challenge. In these puzzles, an AI system must reverse-engineer a hidden mathematical formula simply by observing a few examples of how one 8-bit binary string transforms into another. To solve the puzzle, the model must deduce the exact sequence of operations applied to the inputs and accurately predict the output for a novel, unseen binary string. Example Problem: The Bit Manipulation Puzzle In Alice’s Wonderland, a secret bit manipulation rule transforms 8-bit binary numbers using operations like bit shifts, rotations, XOR, AND, OR, NOT, and majority or choice functions. Deduce the underlying rule to predict the target output. • Example 1: 10100011 \longrightarrow 11011001 • Example 2: 01100110 \longrightarrow 10001101 • Example 3: 11110110 \longrightarrow 11011011 • Target: 01001010 \longrightarrow ???????? Traditional methodologies approach this sequence-to-sequence translation by prompting the Large Language Model (LLM) to reverse-engineer an abstract syntax tree of boolean logic gates (e.g., AND , OR , XOR ) and spatial operators (e.g., left shifts, right shifts, circular rotations). However, this approach collides directly with the mathematical reality of the problem: the search space of possible operations is astronomically large. To illustrate this intractability, consider the full feature space of 22 possible base transformations (the original bit x , plus 7 left shifts, 7 right shifts, and 7 circular rotations). If a hidden rule relies on exactly three of these bases, there are \binom{22}{3}=1,540 unique base combinations. However, to form an executable mathematical rule, these three bases must be ordered into a syntax tree and connected using the allowed operations ( XOR , AND , OR , NOT , as well as majority or choice functions). For any three selected bases, there are 3!=6 ways to order them. If we connect them using two sequential binary gates (including their negated variants, yielding 6 options per gate), we generate 3!\times 6\times 6=216 distinct structural equations per subset. Thus, even for a rudimentary three-variable rule, an LLM attempting to brute-force the formula would have to evaluate a search space exceeding 330,000 unique combinations ( 1,540\times 216 ). Because this search space expands exponentially with each additional logical step, standard heuristic guessing or structured arithmetic search quickly becomes intractable. Auto-Regressive architectures lack the internal working memory to mentally simulate shifted binary arrays and evaluate complex boolean algebra simultaneously across thousands of theoretical paths. Consequently, forcing LLMs down this arithmetic deduction route invariably results in severe hallucinations and logical dead-ends. To overcome this fundamental computational barrier, we present a paradigm shift in how bitwise reasoning is handled. Rather than forcing the model to perform arithmetic deduction, we reformulate the entire puzzle into a discrete feature-selection and string-matching problem. We decompose the input space into a finite set of spatial pointers (“Bases”) and leverage string similarity metrics—specifically, tracking minimal bitflips between varying outputs—to directly isolate the exact variables driving the state changes. Furthermore, we recognize that a robust reasoning system must possess the ability to hypothesize, verify against an external ground truth, and recover from logical collisions. To instill this System-2 capability, we introduce a novel Supervised Fine-Tuning (SFT) methodology: Interactive Reasoning SFT via Dynamic Masking . By coupling strict single-bit tokenization with masked environmental feedback, we successfully train the LLM to act as an autonomous agent that navigates a Depth-First Search (DFS) tree, deduces empirical truth tables, and backtracks natively when its logic fails. Paper Organization: The remainder of this paper is organized as follows: Section 2 establishes our core conceptual framework, detailing the deconstruction of bit sequences into spatial bases, empirical truth tables, and the isolation of output-influencing bases via minimal bitflips. Section 3 formalizes our deterministic solver, showcasing our backtracking Depth-First Search (DFS) and global collision verification. Section 4 presents our machine learning methodologies, including token-alignment strategies and interactive reasoning via dynamic masking. Finally, Section 5 evaluates our empirical results and details our error analysis under strict hardware constraints. 2 Preliminaries and Core Concepts To understand why our approach abandons traditional logic-gate simulation, it is first necessary to establish the conceptual framework we use to analyze bit manipulation. Instead of viewing the problem through the lens of complex logic gates and bitwise arithmetic, we transformed the sequence-to-sequence translation into a discrete base-selection and string-matching problem. This requires understanding three foundational concepts: Bases, Empirical Truth Tables, and Isolating Output-Influencing Bases via Minimal Bitflips. 2.1 Bases \longrightarrow 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1. Right Shifts (R1-R7) 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 R1 R2 R3 R4 R5 R6 R7 2. Circular Shifts (C1-C7) 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 C1 C2 C3 C4 C5 C6 C7 3. Left Shifts (L1-L7) 1 0 1 0 0 0 1 1 0 0 0 0 0

Read the complete text