2511.11712
Model: gemini-2.0-flash
# Reasoning: From Reflection to Solution How Operator-Based Architectures Solve What Autoregressive Models Cannot
**Authors**:
- Zixi Li (Noesis Lab (Independent Research Group))
Abstract
What is reasoning? This fundamental question drives our investigation into why state-of-the-art language models achieve 0% on systematic search tasks, while a learnable operator-based architecture achieves 76%.
We present three interconnected contributions: (1) OpenXOR âan adversarial benchmark exposing the complete failure of autoregressive LLMs on constraint satisfaction problems; (2) OpenOperator âa unified theoretical framework formalizing reasoning as fixed-point iteration in operator state spaces; and (3) OpenLM âa neural architecture that learns discrete operator policies and achieves 76% accuracy where GPT-OSS-20B and DeepSeek-R1 achieve 0%.
The Problem: OpenXOR
We design a deceptively simple task: compute XOR operations over 2048-bit sequences with adversarial checkpoint constraints. The problem involves only two operations (XOR, NOP)âunderstandable in 30 secondsâyet transforms into an NP-hard exponential search space ( $2^{2048}$ ). SOTA LLMs achieve 0% task completion rate: they refuse to answer (37-42%), hit context limits (28-31%), or hallucinate constraints (18-22%). This is not poor performance; it is categorical failure.
The Theory: OpenOperator
We formalize reasoning as finding fixed points $x^{*}=\mathcal{O}(x^{*})$ through iterative operator application. This framework unifies dynamic programming, graph algorithms, and systematic search under a single principle: reasoning is state space iteration with convergence detection. We provide theoretical guarantees via Banach fixed-point theorem and prove OpenXOR requires $\Omega(2^{k})$ time for $k$ checkpoints.
The Solution: OpenLM
Guided by OpenOperator theory, we design a neural architecture that replaces autoregressive tokens with explicit operator sequences ( $\{\textsc{XOR},\textsc{NOP}\}$ ) and hidden states with interpretable state representations (accumulator, position). Trained via supervised learning on 1,000 instances, OpenLM achieves:
- 76% exact accuracy on test set with $n=2048$ , $kâ 20$
- 100% task completion (vs. 0% for LLMs)
- Learnable systematic search through operator policy networks
The Insight
The gap is not about scale, training data, or promptingâit is about architectural alignment. Autoregressive generation is fundamentally incompatible with backtracking and constraint satisfaction. Operator-based architectures provide the right inductive bias for systematic reasoning.
This work shifts the narrative from âLLMs cannot reasonâ to âautoregressive architectures are misaligned with search problems.â We provide both the diagnosis (OpenXOR benchmark, 0% LLM performance) and the cure (OpenOperator theory, OpenLM achieving 76%). The path forward is not bigger transformers, but architecturally diverse AI systems matching computational structures to problem structures.
1 Introduction: Refl ecting on Reasoning Itself
1.1 The Fundamental Question
What is reasoning? This question has driven centuries of philosophical inquiry, from Aristotleâs syllogisms to modern computational complexity theory. In the age of large language models achieving superhuman performance on benchmarks like GSM8K (95% accuracy) and HumanEval (90% pass@1), we must ask: have these systems learned to reason, or have they learned to pattern-match over reasoning traces?
This paper argues for a specific answer: reasoning is iterative operator application in state spaces, converging to fixed points. This definition is not merely philosophicalâit has concrete architectural implications that explain both the failures of current systems and the path to genuine reasoning capabilities.
Our investigation begins with a puzzle (OpenXOR), progresses through theory (OpenOperator), and culminates in a working solution (OpenLM) that achieves 76% accuracy where state-of-the-art LLMs achieve 0%. This is not about criticizing existing systems, but about understanding what reasoning requires and building architectures that provide it.
1.2 A Constructive Perspective on AI Limitations
Recent work has documented failures of LLMs on reasoning benchmarks like ARC-AGI [1]. The prevailing narrative is pessimistic: âLLMs cannot reason,â âthe reasoning capability is an illusion,â âwe need fundamentally different approaches.â
We propose a different framing: LLMs excel at what they were designed for (language modeling), but reasoning requires different computational structures. Just as CNNs are better than RNNs for image recognition (not because RNNs âcannot see,â but because convolution aligns with visual structure), operator-based architectures are better than autoregressive models for systematic search (not because transformers âcannot think,â but because fixed-point iteration aligns with reasoning structure).
This reframing is not merely semantic. It shifts our focus from what fails to why it fails and how to fix it. We show that:
1. Diagnosis: OpenXOR exposes the specific failure mode (0% completion on constraint satisfaction)
1. Understanding: OpenOperator theory explains the mismatch (autoregressive $â $ backtracking)
1. Solution: OpenLM demonstrates that neural networks can learn systematic reasoning when given the right architectural inductive bias (76% accuracy)
1.3 Three Interconnected Contributions
Contribution 1: OpenXOR Benchmark
We design an adversarial evaluation that isolates systematic search capability from language understanding and domain knowledge. The problem involves only two operations (XOR, NOP) over 2048-bit sequences, but adversarial checkpoints create an exponential search space ( $2^{2048}$ ).
Key result: SOTA LLMs achieve 0% task completionânot because they perform poorly, but because they refuse to attempt the task (37-42% explicit refusals) or collapse (28-31% context overflow). This is categorical architectural failure.
Contribution 2: OpenOperator Theory
We formalize reasoning as finding fixed points in operator state spaces:
$$
x^{*}=\mathcal{O}(x^{*}),\quad\text{reached via iteration: }x_{t+1}=\mathcal{O}(x_{t}) \tag{1}
$$
This framework unifies:
- Dynamic programming: $\text{dp}[i]=f(\text{dp}[i-1],\text{dp}[i-2])$
- Graph algorithms: $\text{dist}[v]=\min(\text{dist}[v],\text{dist}[u]+w(u,v))$
- Systematic search: state expansion with backtracking
We provide theoretical guarantees (Banach fixed-point theorem) and complexity bounds ( $\Omega(2^{k})$ for OpenXOR).
Contribution 3: OpenLM Architecture
Guided by OpenOperator theory, we design a learnable system that:
- Replaces tokens with operators: $\{\textsc{XOR},\textsc{NOP}\}$ instead of vocabulary embeddings
- Replaces hidden states with explicit state: (accumulator, position, remaining bits)
- Learns operator policies: $\pi(op\mid state)$ via supervised learning
Key result: OpenLM achieves 76% exact accuracy on OpenXOR test set (100 instances, $n=2048$ , $kâ 20$ ), compared to 0% for GPT-OSS-20B and DeepSeek-R1. This proves neural networks can learn systematic search when architecturally aligned.
1.4 Roadmap and Paper Structure
The remainder of this paper proceeds as follows:
- Section 2 (Related Work): Positions our work relative to existing benchmarks and reasoning frameworks
- Section 3 (OpenXOR Problem): Formalizes the benchmark, proves NP-hardness, analyzes search complexity
- Section 4 (Theoretical Analysis): Proves lower bounds and explains LLM failures
- Section 5 (OpenOperator Theory): Introduces the unified framework for algorithm design
- Section 6 (OpenLM Architecture): Describes the operator-based neural architecture
- Section 7 (Experiments): Presents the 76% vs 0% result and ablation studies
- Section 8 (Discussion): Reflects on implications for AI research
- Section 9 (Conclusion): Summarizes contributions and future directions
Our goal is not to claim âwe solved reasoningââOpenLMâs 76% is far from perfect. Rather, we aim to demonstrate a proof of principle: when neural architectures are designed with the right computational structure, they can learn systematic reasoning. The path forward is not abandoning neural approaches, but matching architectural inductive biases to problem structures.
2 Related Work
2.1 LLM Reasoning Benchmarks
Mathematical Reasoning
GSM8K [3] tests grade-school math word problems, where GPT-4 achieves $>$ 90% accuracy. MATH [4] contains competition-level problems requiring multi-step derivations. However, these benchmarks conflate mathematical knowledge (e.g., knowing the quadratic formula) with search ability. LLMs can memorize solution templates without genuinely reasoning about problem structure.
Code Generation
HumanEval [2] measures function-level code synthesis, where models like GPT-4 achieve 90% pass@1. APPS [5] contains competitive programming problems. Yet most solutions involve standard algorithmic patterns (sorting, dynamic programming templates) that appear frequently in training data. These benchmarks do not test whether models can design novel algorithms for unfamiliar problem structures.
Logical Reasoning
BIG-Bench [6] includes logical reasoning subtasks, and LogiQA [7] tests deductive inference. But these problems have small search spaces or can be solved via pattern matching over natural language. They do not induce the combinatorial explosion characteristic of genuine constraint satisfaction.
2.2 Adversarial Evaluation: ARC-AGI
The closest related work is Cholletâs ARC-AGI (Abstract Reasoning Corpus) [1], which shares our motivation:
- Test fluid intelligence, not memorization: ARC uses visual grid transformations intentionally outside training distributions.
- Minimize prior knowledge requirements: Simple geometric operations, no domain expertise needed.
- Measure generalization: Models must induce rules from few-shot examples.
ARC-AGI has successfully exposed LLM limitationsâSOTA models perform near random chance. However, there are key differences:
| Problem domain | Visual pattern recognition | Sequence operations |
| --- | --- | --- |
| DSL complexity | Medium (grid operations) | Minimal (XOR/NOP only) |
| Search space | Small ( $3Ă 3$ to $30Ă 30$ grids) | Exponential ( $2^{2048}$ ) |
| Constraints | Implicit (infer from examples) | Explicit (hard checkpoints) |
| Theoretical guarantees | None (human intuition) | Formal (info theory + NP-hard) |
| LLM performance | Near random | Near random |
Table 1: Comparison: ARC-AGI tests pattern induction; OpenXOR tests systematic search.
Key distinction: ARCâs difficulty stems from inductive reasoning âinferring rules from limited data. OpenXORâs difficulty stems from combinatorial explosion âthe rules are fully specified, but the solution space is exponentially large. This isolates a different failure mode: even with complete problem specifications, LLMs cannot execute systematic search.
2.3 Program Synthesis
Neural program synthesis aims to generate code satisfying input-output specifications [9, 10]. AlphaCode [8] uses large-scale sampling (millions of candidates) + filtering to solve competitive programming problems. Rosette [11] employs symbolic execution and SMT solvers.
However, these approaches rely on:
1. Large beam sizes ( $B=100$ to $1{,}000{,}000$ ): sampling many candidates and filtering.
1. Symbolic backends: offloading constraint solving to SAT/SMT solvers.
OpenXOR demonstrates that neural-guided search fails when beam size $B\ll 2^{k}$ (Section 4.3). This exposes a fundamental limitation: LLMs cannot efficiently navigate exponential search spaces without symbolic assistance.
2.4 Constraint Satisfaction and SAT Solving
The SAT problem (Boolean satisfiability) is the canonical NP-complete problem. Modern SAT solvers like MiniSat [12] use systematic DPLL-based search with conflict-driven clause learning. Our NP-hardness reduction (Section 3.3) shows OpenXOR is at least as hard as 3-SAT.
SATNet [13] attempts to make SAT differentiable for end-to-end learning, but requires problem-specific architecture design. OpenXOR highlights that general-purpose LLMs lack the built-in backtracking mechanisms of SAT solvers.
2.5 What Existing Work Misses
Current benchmarks fail to isolate search capability from:
- Domain knowledge (MATH, MMLU)
- Programming syntax (HumanEval)
- Pattern induction (ARC-AGI)
- Natural language understanding (GSM8K)
OpenXOR is the first benchmark with:
1. Provable exponential hardness: Information-theoretic and computational lower bounds.
1. Minimal confounds: Trivial DSL eliminates knowledge/syntax as variables.
1. Controlled difficulty tuning: Checkpoint count $k$ directly controls hardness.
This enables us to make a definitive claim: LLMs fundamentally cannot perform systematic search, independent of scale, training data, or prompt engineering.
3 Problem Formalization
3.1 OpenXOR Problem Definition
**Definition 1 (OpenXOR Instance)**
*An OpenXOR instance is a tuple $(\mathbf{b},t,\mathcal{C})$ where:
- $\mathbf{b}=[b_{1},b_{2},...,b_{n}]â\{0,1\}^{n}$ : input bit sequence (typically $n=2048$ )
- $tâ\{0,1\}$ : target output
- $\mathcal{C}=\{(p_{1},v_{1}),...,(p_{k},v_{k})\}$ : checkpoint constraints where $p_{i}â\{1,...,n\}$ and $v_{i}â\{0,1\}$*
**Definition 2 (Valid Solution)**
*A valid solution is an operation sequence $\mathbf{o}=[o_{1},o_{2},...,o_{n}]$ where $o_{i}â\{\textsc{XOR},\textsc{NOP}\}$ such that:
1. Checkpoint constraints satisfied: $â(p,v)â\mathcal{C}:\text{acc}_{p}=v$
1. Target output achieved: $\text{acc}_{n}=t$
where the accumulator evolves according to:
$$
\displaystyle\text{acc}_{0} \displaystyle=0 \displaystyle\text{acc}_{i} \displaystyle=\begin{cases}\text{acc}_{i-1}\oplus b_{i},&\text{if }o_{i}=\textsc{XOR}\\
\text{acc}_{i-1},&\text{if }o_{i}=\textsc{NOP}\end{cases} \tag{2}
$$*
3.2 Example Walkthrough $b_{1}$ =0 XOR 0 $b_{2}$ =1 XOR 1 $b_{3}$ =1 NOP 1 $b_{4}$ =1 NOP 1 $b_{5}$ =1 XOR 0 $b_{6}$ =0 NOP 0 $b_{7}$ =1 XOR 1 0 Checkpoint Input: Ops: Acc:
Figure 1: OpenXOR execution trace for a 7-bit sequence. Checkpoint at position 4 requires $\text{acc}_{4}=1$ . The solution satisfies this constraint and reaches target $t=1$ .
Consider the instance:
| | $\displaystyle\mathbf{b}$ | $\displaystyle=[0,1,1,1,1,0,1]$ | |
| --- | --- | --- | --- |
A valid solution is $\mathbf{o}=[\textsc{XOR},\textsc{XOR},\textsc{NOP},\textsc{NOP},\textsc{XOR},\textsc{NOP},\textsc{XOR}]$ (see Figure 1).
3.3 NP-Hardness Proof
**Theorem 1 (OpenXOR is NP-Hard)**
*The decision problem âDoes there exist a valid solution $\mathbf{o}$ for instance $(\mathbf{b},t,\mathcal{C})$ ?â is NP-hard.*
* Proof Sketch*
We reduce 3-SAT to OpenXOR. Given a 3-SAT instance with variables $x_{1},...,x_{m}$ and clauses $C_{1},...,C_{\ell}$ : Variable encoding: For each variable $x_{i}$ , allocate a segment $[b_{3i-2},b_{3i-1},b_{3i}]=[1,0,1]$ . Define:
- $x_{i}=\textsc{True}$ iff operations $[o_{3i-2},o_{3i-1},o_{3i}]=[\textsc{XOR},\textsc{NOP},\textsc{XOR}]$ (accumulator flips)
- $x_{i}=\textsc{False}$ iff all operations are NOP (accumulator unchanged) Clause encoding: For each clause $C_{j}=(\ell_{1}\vee\ell_{2}\vee\ell_{3})$ , place a checkpoint $(p_{j},v_{j})$ after the variable segments. The value $v_{j}$ is set such that the checkpoint is satisfied iff at least one literal is true. Correctness: A satisfying assignment for 3-SAT corresponds bijectively to a valid OpenXOR solution. Since 3-SAT is NP-complete, OpenXOR is NP-hard. â
3.4 Search Space Analysis
**Proposition 2 (Exponential Search Space)**
*The size of the search space is:
$$
|\Omega|=2^{n} \tag{4}
$$
For $n=2048$ : $|\Omega|â 10^{616}$ âexceeding the number of atoms in the observable universe by hundreds of orders of magnitude.*
**Proposition 3 (Solution Density)**
*Let $\mathcal{S}âeq\Omega$ denote the set of valid solutions. Under mild independence assumptions, the expected fraction of valid solutions is:
$$
\frac{|\mathcal{S}|}{|\Omega|}\approx 2^{-k} \tag{5}
$$
where $k$ is the number of checkpoints.*
* Intuition*
Each checkpoint imposes a binary constraint (accumulator must equal 0 or 1 at a specific position). If accumulator values are approximately uniformly distributed (reasonable under random bit sequences), each checkpoint is satisfied with probability $1/2$ independently. Thus:
$$
\mathbb{P}(\text{all checkpoints satisfied})\approx\left(\frac{1}{2}\right)^{k}=2^{-k} \tag{12}
$$
â
For typical test instances ( $n=2048,k=20$ ):
$$
\frac{|\mathcal{S}|}{|\Omega|}\approx 2^{-20}\approx 9.5\times 10^{-7} \tag{7}
$$
Implication: Random search requires on average $\sim 10^{6}$ trials to find a valid solution.
3.5 Dataset Generation Methodology
Challenge: How to ensure generated instances are satisfiable (have at least one solution)?
Solution: Reverse construction
1. Randomly generate $\mathbf{b}â\{0,1\}^{n}$ and $\mathbf{o}â\{\textsc{XOR},\textsc{NOP}\}^{n}$
1. Execute forward simulation to compute accumulator trace $[\text{acc}_{0},\text{acc}_{1},...,\text{acc}_{n}]$
1. Randomly sample $k$ positions $\{p_{1},...,p_{k}\}$ and set checkpoint values $v_{i}=\text{acc}_{p_{i}}$
1. Set target $t=\text{acc}_{n}$
Properties:
- Guarantees existence of at least one solution (the generated $\mathbf{o}$ )
- Solutions are generally non-unique (exponentially many other valid paths may exist)
- Checkpoints are adversarial: they do not âhelpâ solve the problem, but rather constrain the search space
Dataset statistics:
- Training set: 1,000 instances, $n=512$ , checkpoint density 1%
- Test set: 100 instances, $n=2048$ , checkpoint density 1% ( $â$ 20 checkpoints)
- Each instance includes 3â5 few-shot examples (short sequences for demonstration)
4 Theoretical Analysis
4.1 Lower Bound: Random Strategies
**Theorem 4 (Random Strategy Lower Bound)**
*For any strategy that does not exploit problem structure (i.e., generates operations uniformly at random), the success probability satisfies:
$$
\mathbb{P}(\text{success})\leq\left(\frac{1}{2}\right)^{k} \tag{12}
$$
where $k$ is the number of checkpoints.*
* Proof*
Consider a random strategy that generates $\mathbf{o}\sim\text{Uniform}(\{\textsc{XOR},\textsc{NOP}\}^{n})$ . For checkpoint $(p_{i},v_{i})$ , the accumulator value $\text{acc}_{p_{i}}$ depends on the XOR of all bits where the operation was XOR in positions $1,...,p_{i}$ . Under random operations, this is a XOR of a random subset of bits, which is uniformly distributed:
$$
\mathbb{P}(\text{acc}_{p_{i}}=v_{i})=\frac{1}{2} \tag{9}
$$ If checkpoints are sufficiently separated (spacing $â„\log n$ ), the random variables $\{\text{acc}_{p_{i}}\}$ are approximately independent. Thus:
$$
\mathbb{P}\left(\bigcap_{i=1}^{k}\text{acc}_{p_{i}}=v_{i}\right)\approx\prod_{i=1}^{k}\frac{1}{2}=\left(\frac{1}{2}\right)^{k} \tag{12}
$$
â
**Corollary 5**
*For $k=20$ checkpoints:
$$
\mathbb{P}(\text{success})\leq 2^{-20}\approx 9.5\times 10^{-7} \tag{11}
$$*
Interpretation: If LLMs employ a strategy resembling stochastic sampling (as suggested by softmax token generation), their success rate is bounded by one-in-a-million. This matches our empirical observations.
4.2 Greedy Algorithms Fail
**Theorem 6 (No Greedy Algorithm Succeeds)**
*There does not exist a deterministic greedy algorithm (making decisions based only on the current state and prefix history) that achieves $>50\%$ accuracy on adversarially constructed OpenXOR instances.*
* Adversarial Construction*
Given any deterministic greedy algorithm $\mathcal{A}$ : 1. Execute $\mathcal{A}$ on the first $n/2$ steps, recording decisions $\mathbf{o}_{1:n/2}$
1. Compute accumulator state $\text{acc}_{n/2}$
1. Construct the second half adversarially:
- Choose checkpoint position $pâ[n/2,n]$
- If $\mathcal{A}$ tends to choose XOR (e.g., $>60\%$ of the time in experiments), set $v=\text{acc}_{n/2}$ (forcing NOP)
- Otherwise, set $v=\text{acc}_{n/2}\oplus 1$ (forcing XOR) The greedy algorithm cannot âforeseeâ future constraints, so it commits to a decision path that is invalidated by later checkpoints. Since greedy strategies prohibit backtracking, the algorithm fails. â
Implication: Autoregressive token generation (as in GPT) is inherently greedyâonce a token is generated, it cannot be undone (without explicit beam search). This theorem shows why LLMs fundamentally struggle with OpenXOR.
4.3 Beam Search Limitations
**Theorem 7 (Beam Search Upper Bound)**
*For beam search with beam size $B<2^{k}$ , the success probability satisfies:
$$
\mathbb{P}(\text{success})\leq\frac{B}{2^{k}} \tag{12}
$$*
* Proof*
Beam search maintains the top- $B$ candidate paths at each step. When a checkpoint is encountered:
1. Paths violating the constraint are pruned
1. The beam is refilled with the next-best candidates If valid solutions are uniformly distributed among the $2^{k}$ possible checkpoint-satisfying paths, the probability that at least one valid path remains in the beam is at most:
$$
\mathbb{P}(\text{beam contains solution})\leq\frac{B}{2^{k}} \tag{13}
$$
â
**Corollary 8 (AlphaCode-Scale Beam Search Fails)**
*AlphaCode uses $B=100$ beam size. For $k=20$ :
$$
\mathbb{P}(\text{success})\leq\frac{100}{2^{20}}\approx 9.5\times 10^{-5} \tag{14}
$$*
This explains why state-of-the-art neural program synthesis fails on OpenXOR.
4.4 Optimal Algorithm Complexity
**Theorem 9 (Exponential Lower Bound)**
*Any algorithm that correctly solves all OpenXOR instances requires $\Omega(2^{k})$ time in the worst case.*
* Proof*
From the NP-hardness reduction (Theorem 1) and the exponential time hypothesis (ETH), no polynomial-time algorithm can solve all instances (unless P=NP, which is widely believed false). For adversarial instances where:
- Checkpoints are uniformly spaced
- Checkpoint values are randomly chosen
- Solutions are unique (or exponentially rare)
any algorithm must explore at least $\Omega(2^{k})$ candidate paths to guarantee finding a solution. â
Empirical validation: Our backtracking solver explores on average $10^{4}$ â $10^{6}$ nodes for $n=2048,k=20$ instances, taking 0.1â10 seconds. This is orders of magnitude more computation than LLM inference ( $<1$ second).
4.5 Why LLMs Fundamentally Cannot Solve OpenXOR
We synthesize the above results into a comprehensive impossibility argument: LLM Architecture Information-theoretic: Parameters $\sim 10^{12}$ cannot cover search space $2^{2048}$ Computational: Autoregressive generation $â $ tree search with backtracking Optimization: Softmax + cross-entropy $â $ hard constraint satisfaction Conclusion: Architectural mismatch, not training deficiency
Figure 2: Three perspectives explaining why LLMs cannot solve OpenXOR.
Information-Theoretic Perspective
GPT-4 has $\sim 1.8Ă 10^{12}$ parameters, encoding roughly $2^{40}$ bits of information. OpenXORâs search space is $2^{2048}$ . Even if the model memorized every training instance, it could only cover a $2^{-2008}$ fraction of the spaceâa negligible amount.
Computational Model Perspective
Transformer architectures implement constant-depth circuits (each layer processes in parallel). OpenXOR requires depth- $O(k)$ decision trees with backtracking. This is an architectural mismatch: autoregressive generation is fundamentally incompatible with tree search.
Optimization Objective Perspective
LLMs are trained via maximum likelihood: $\max\mathbb{P}(o_{i}\mid o_{<i},\mathbf{b})$ . This encourages sampling likely sequences under the data distribution. OpenXOR requires hard constraint satisfaction: $\text{acc}_{p}=v$ (a discrete 0/1 decision with no gradient signal). The optimization objectives are fundamentally misaligned.
Conclusion: OpenXOR is not a problem LLMs can solve through âmore trainingâ or âbetter prompts.â It exposes an inherent architectural limitation. Addressing this requires hybrid systems combining neural components with symbolic search.
5 OpenOperator: A Unified Framework for Reasoning
Having diagnosed the failure mode (Section 4), we now present the theoretical foundation for our solution: OpenOperator âa unified framework that formalizes reasoning as fixed-point iteration in operator state spaces.
5.1 Core Formalization
**Definition 3 (OpenOperator System)**
*An OpenOperator system is a triple $(\mathcal{X},\mathcal{O},\varepsilon)$ where:
- $\mathcal{X}$ : State space (e.g., arrays, graphs, dictionaries)
- $\mathcal{O}:\mathcal{X}â\mathcal{X}$ : Iterative operator (state update rule)
- $\varepsilonâ„ 0$ : Convergence threshold*
**Definition 4 (Fixed-Point Execution)**
*Algorithm execution proceeds via iteration:
$$
\displaystyle x_{0} \displaystyle\in\mathcal{X}\quad\text{(initial state)} \displaystyle x_{t+1} \displaystyle=\mathcal{O}(x_{t})\quad\text{(operator application)} \displaystyle\|x_{t+1}-x_{t}\|\leq\varepsilon\quad\text{(convergence)} \tag{15}
$$
The solution is the fixed point $x^{*}=\lim_{tââ}x_{t}$ where $x^{*}=\mathcal{O}(x^{*})$ .*
5.2 Unifying Classical Algorithms
OpenOperator reveals that seemingly disparate algorithms share a common structure:
Dynamic Programming
Stair-climbing problem: âIn how many ways can you climb $n$ steps if you can take 1 or 2 steps at a time?â
- State: $\mathcal{X}=\mathbb{Z}^{n}$ (array of step counts)
- Operator: $\mathcal{O}(\mathbf{f})_{i}=\begin{cases}1&i†1\\
f_{i-1}+f_{i-2}&iâ„ 2\end{cases}$
- Convergence: Discrete DP converges exactly ( $\varepsilon=0$ ) in $O(n)$ iterations
Graph Algorithms
Shortest path (Bellman-Ford relaxation):
- State: $\mathcal{X}=\mathbb{R}^{|V|}$ (distance vector)
- Operator: $\mathcal{O}(\mathbf{d})_{v}=\min\left(d_{v},\min_{uâ\text{neighbors}(v)}d_{u}+w(u,v)\right)$
- Convergence: $\|d_{t+1}-d_{t}\|_{â}â€\varepsilon$ or fixed-point reached
Systematic Search
BFS reachability:
- State: $\mathcal{X}=2^{V}$ (set of reachable nodes)
- Operator: $\mathcal{O}(S)=S\cup\{v:â uâ S,(u,v)â E\}$ (expand frontier)
- Convergence: $S_{t+1}=S_{t}$ (no new nodes discovered)
5.3 Theoretical Guarantees
**Theorem 10 (Convergence via Banach Fixed-Point Theorem)**
*If $\mathcal{O}:\mathcal{X}â\mathcal{X}$ is a contraction mapping (i.e., $â\lambdaâ[0,1):\|\mathcal{O}(x)-\mathcal{O}(y)\|â€\lambda\|x-y\|$ ), then:
1. There exists a unique fixed point $x^{*}â\mathcal{X}$ with $\mathcal{O}(x^{*})=x^{*}$
1. Iteration converges exponentially: $\|x_{t}-x^{*}\|â€\lambda^{t}\|x_{0}-x^{*}\|$*
For non-contractive operators (e.g., discrete DP), convergence is guaranteed by:
- Finite state spaces: Iteration reaches exact fixed point in finite steps
- Monotonicity: If $\mathcal{O}$ is monotone and bounded, iteration converges to least/greatest fixed point
5.4 Connection to OpenXOR
OpenXOR fits naturally into the OpenOperator framework:
- State: $\mathcal{X}=\{\textsc{XOR},\textsc{NOP}\}^{n}$ (operation sequences)
- Operator: $\mathcal{O}$ extends partial sequences by trying both operators at next position
- Convergence: Valid solution found (all checkpoints + target satisfied) or exhaustive search completes
Key insight: Traditional backtracking is explicit state-space iteration with pruning. The question is: can neural networks learn to approximate $\mathcal{O}$ and navigate this space efficiently?
6 OpenLM: Learning Operator Policies
Guided by OpenOperator theory, we design OpenLM âa neural architecture that learns to apply discrete operators iteratively, converging to valid solutions.
6.1 Architectural Design
Key Departures from Autoregressive LLMs
| Component Output space State representation | Autoregressive LLM Tokens ( $\sim$ 50k vocab) Hidden vectors (opaque) | OpenLM Operators ({XOR, NOP}) Explicit (acc, pos, bits) |
| --- | --- | --- |
| Generation | $p(token_{t}\mid\text{history})$ | $\pi(op_{t}\mid state_{t})$ |
| Architecture | Transformer (attention) | Operator policy network |
| Training | Next-token prediction | Supervised operator sequences |
| Interpretability | Low (hidden states) | High (explicit state) |
Table 2: Architectural comparison: OpenLM vs autoregressive LLMs.
Explicit State Representation
**Definition 5 (Operator State)**
*An operator state is a tuple $(acc,pos,\mathbf{b})$ where:
- $accâ\{0,1\}$ : Current XOR accumulator value
- $posâ\{0,...,n\}$ : Current position in bit sequence
- $\mathbf{b}â\{0,1\}^{n}$ : Remaining input bits*
State transitions follow operator semantics:
$$
\displaystyle\textsc{Apply}(\textsc{XOR},(acc,pos,\mathbf{b})) \displaystyle=(acc\oplus b_{pos},pos+1,\mathbf{b}) \displaystyle\textsc{Apply}(\textsc{NOP},(acc,pos,\mathbf{b})) \displaystyle=(acc,pos+1,\mathbf{b}) \tag{18}
$$
Operator Policy Network State $(acc,pos,\mathbf{b})$ State Embedding $\phi(state)â\mathbb{R}^{d}$ Policy Network $\pi_{\theta}(op\mid state)$ Sample Operator $op\sim\pi_{\theta}$ State Transition $state^{\prime}=\textsc{Apply}(op,state)$
Figure 3: OpenLM architecture: Iterative operator application until convergence.
The policy network $\pi_{\theta}:\mathcal{X}â\Delta(\{\textsc{XOR},\textsc{NOP}\})$ is implemented as:
$$
\displaystyle\phi(state) \displaystyle=\text{Embed}(acc,pos,\mathbf{b}_{pos:pos+5})\in\mathbb{R}^{d} \displaystyle=\text{MLP}(\phi(state))\in\mathbb{R}^{2} \displaystyle\pi_{\theta}(op\mid state) \displaystyle=\text{Softmax}(\text{logits}) \tag{20}
$$
6.2 Training Procedure
Supervised Learning
We train OpenLM using ground-truth operator sequences generated via backtracking:
Algorithm 1 OpenLM Training
1: Input: Dataset $\mathcal{D}=\{(\mathbf{b}_{i},t_{i},\mathcal{C}_{i},\mathbf{o}_{i}^{*})\}_{i=1}^{N}$
2: Initialize policy network $\pi_{\theta}$
3: for epoch $=1$ to $E$ do
4: for $(\mathbf{b},t,\mathcal{C},\mathbf{o}^{*})$ in $\mathcal{D}$ do
5: $stateâ(0,0,\mathbf{b})$ // Initial state
6: $\mathcal{L}â 0$ // Cumulative loss
7: for $j=1$ to $|\mathbf{o}^{*}|$ do
8: Compute $\pi_{\theta}(op\mid state)$
9: $\mathcal{L}â\mathcal{L}+\text{CrossEntropy}(\pi_{\theta},o_{j}^{*})$ // Ground truth
10: $stateâ\textsc{Apply}(o_{j}^{*},state)$ // Teacher forcing
11: end for
12: Update $\theta$ via $â_{\theta}\mathcal{L}$
13: end for
14: end for
Key Training Details
- Dataset: 1,000 training instances ( $n=512$ , $kâ 5$ ), 100 test instances ( $n=2048$ , $kâ 20$ )
- Model size: $\sim$ 100k parameters (state embedding: 64d, hidden layers: 128d)
- Optimizer: AdamW with learning rate $10^{-3}$ , weight decay $0.01$
- Training time: $\sim$ 5 epochs, $\sim$ 3 minutes on CPU
6.3 Inference: Iterative Operator Application
At test time, OpenLM generates operator sequences autoregressively (but in operator space, not token space):
Algorithm 2 OpenLM Inference
1: Input: Bit sequence $\mathbf{b}$ , target $t$ , checkpoints $\mathcal{C}$
2: $stateâ(0,0,\mathbf{b})$
3: $\mathbf{o}â[]$ // Generated operations
4: while $state.pos<n$ do
5: Sample $op\sim\pi_{\theta}(·\mid state)$
6: Append $op$ to $\mathbf{o}$
7: $stateâ\textsc{Apply}(op,state)$
8: if $(state.pos,v)â\mathcal{C}$ and $state.accâ v$ then
9: return Failure // Checkpoint violated
10: end if
11: end while
12: return $\mathbf{o}$ if $state.acc=t$ else Failure
6.4 Why OpenLM Works: Architectural Alignment
OpenLM succeeds where autoregressive LLMs fail because of architectural alignment:
1. Explicit state management: Unlike opaque hidden vectors, OpenLMâs state $(acc,pos)$ directly corresponds to problem structure
1. Operator semantics: The network learns what XOR and NOP do, not just what tokens follow what
1. Constrained action space: 2 operators vs. 50k tokens reduces search complexity
1. Compositional generalization: Operator sequences compose like functions, enabling systematic exploration
Key insight: By matching the neural architecture to the problemâs computational structure (operator iteration), we enable learning of systematic reasoning that autoregressive token generation cannot achieve.
7 Experiments: 76% vs 0%
7.1 Experimental Setup
Models Tested
1. GPT-OSS-20B (Open-source 20B parameter baseline model)
1. DeepSeek-R1 (Reasoning-focused commercial model, 2024 release)
Baselines
1. Random: Uniformly sample operations
1. Greedy: Simple heuristic (prefer XOR if target parity mismatches current accumulator)
1. Backtracking: Depth-first search with constraint propagation
Evaluation Metrics
- Task Completion Rate: Percentage of instances where model provides a solution attempt (not NA/refusal/context overflow)
- Exact Accuracy: Percentage of instances where all constraints satisfied
- Checkpoint Accuracy: Average fraction of checkpoints satisfied per instance
- Target Accuracy: Percentage where only the final output is correct (ignoring checkpoints)
- Execution Time: Wall-clock time per instance
Test Set
100 instances with $n=2048$ bits, $kâ 20$ checkpoints (1% density). Each instance includes 3â5 few-shot examples demonstrating the format.
7.2 Main Results: The 76% vs 0% Gap
| Method Random Greedy | Completion 100% 100% | Exact Acc. 0% 0% | Ckpt Acc. 50.2% 51.3% | Target Acc. 50.1% 52.7% | Time (s) $<$ 0.01 $<$ 0.01 |
| --- | --- | --- | --- | --- | --- |
| GPT-OSS-20B | 0% | 0% | N/A | N/A | 2.3 |
| DeepSeek-R1 | 0% | 0% | N/A | N/A | 3.1 |
| OpenLM (Ours) | 100% | 76% | 84.2% | 89.0% | 0.8 |
| Backtracking (Symbolic) | 100% | 100% | 100% | 100% | 3.4 |
Table 3: Main result: OpenLM achieves 76% exact accuracy vs. 0% for SOTA LLMs. On 100 test instances ( $n=2048,kâ 20$ ), autoregressive LLMs (GPT-OSS-20B, DeepSeek-R1) achieve 0% task completionâthey refuse, crash, or hallucinate. OpenLM, trained on only 1,000 examples with $\sim$ 100k parameters, achieves 76% exact accuracy (all checkpoints + target satisfied), 84.2% checkpoint accuracy, and 100% task completion. This demonstrates that architectural alignment enables learnable systematic reasoning.
Key observations:
1. Categorical LLM failure: Both SOTA LLMs achieve 0% completionâthey refuse to attempt the task (37-42%), hit context limits (28-31%), or hallucinate constraints (18-22%)
1. OpenLM breakthrough: Achieves 76% exact accuracy with 100% task completion, proving neural networks can learn systematic search when architecturally aligned
1. Efficiency: OpenLM ( $\sim$ 100k parameters, 0.8s/instance) vastly outperforms autoregressive LLMs (20B parameters, 2-3s/instance but 0% accuracy)
1. Room for improvement: 76% vs. 100% symbolic baseline suggests hybrid approaches combining learned policies with symbolic verification Random Greedy GPT-OSS DeepSeek OpenLM Symbolic $0$ $20$ $40$ $60$ $80$ $100$ The 76% Gap: Architectural Alignment $0$ $0$ $0$ $0$ $76$ $100$ Method Exact Accuracy (%)
Figure 4: The 76% vs 0% result: OpenLM bridges the gap between categorical LLM failure (0%) and perfect symbolic solutions (100%). This proves that neural networks can learn systematic reasoning when provided with operator-based architectures aligned to problem structure.
Failure Mode Breakdown (manual analysis of 100 instances):
| Refusal to answer (explicit) | 37% | 42% |
| --- | --- | --- |
| Maximum sequence length reached | 28% | 31% |
| Context collapse (hallucinated constraints) | 22% | 18% |
| Output format error (unparseable) | 13% | 9% |
| Valid solution attempts | 0% | 0% |
Table 4: Breakdown of catastrophic failure modes across 100 test instances. Models do not merely perform poorlyâthey cannot even attempt the task. The most common failure is explicit refusal (37-42%), followed by context overflow (28-31%) and constraint hallucination (22-18%). Random Greedy GPT-OSS DeepSeek Backtrack $0$ $20$ $40$ $60$ $80$ $100$ $100$ $100$ $0$ $0$ $100$ Method Task Completion Rate (%)
Figure 5: Task completion rate comparison. LLMs achieve 0% completion (cannot produce valid outputs), while random/greedy baselines and backtracking all complete 100% of instances. This is worse than random guessingâmodels refuse or crash rather than attempt solutions.
7.3 Qualitative Analysis: Catastrophic Failure Modes
We manually inspect all 100 failed responses from both models. Representative examples:
Example 1: Explicit Refusal (GPT-OSS-20B, 37% of failures)
Instance ID: 042 User prompt: [2048-bit sequence with 20 checkpoints + 3 examples] Model response: "I apologize, but this problem requires systematic search over an exponentially large space. I cannot provide a valid solution through autoregressive generation. A backtracking algorithm would be needed to explore the constraint space systematically."
Analysis: Model correctly identifies its architectural limitation but refuses to attempt the task. This is intellectually honest but confirms the fundamental incompatibility between autoregressive generation and combinatorial search.
Example 2: Context Collapse (DeepSeek-R1, 22% of failures)
Instance ID: 067 User prompt: [2048-bit sequence with 20 checkpoints] Model response (excerpt): "Step 1: acc = 0 XOR b[0] = 0 XOR 1 = 1 Step 2: acc = 1 XOR b[1] = 1 XOR 0 = 1 ... Step 342: acc = [ERROR: checkpoint at position 103 requires acc=0 but current acc=1, need to backtrack] Restarting from step 1 with different choices... Step 1: acc = 0 NOP b[0] = 0 Step 2: acc = 0 XOR b[1] = 0 XOR 0 = 0 ... [Output exceeds maximum length of 8192 tokens, terminated]"
Analysis: Model attempts to backtrack but cannot maintain state consistency across iterations, leading to infinite loops. Context window exhausts before finding a valid path. This demonstrates the architectural mismatchâbacktracking requires explicit state management that autoregressive models lack.
Example 3: Maximum Sequence Length (GPT-OSS-20B, 28% of failures)
Instance ID: 089 Model response: "Let me work through this step-by-step... Position 0: current acc=0, bit=1, choosing XOR, new acc=1 Position 1: current acc=1, bit=0, choosing NOP, new acc=1 ... Position 1847: current acc=0, bit=1, choosing XOR... Position 1848: [MODEL OUTPUT TRUNCATED - REACHED TOKEN LIMIT]"
Analysis: Model generates verbose reasoning traces without pruning invalid paths. Exhausts context window (8192 tokens) before completing the 2048-position sequence. No evidence of constraint checking or early termination when checkpoints are violated.
Example 4: Constraint Hallucination (DeepSeek-R1, 18% of failures)
Instance ID: 073 Model response: "I notice the checkpoint at position 200 requires acc=1, and another at position 350 requires acc=0. These constraints conflict because [INCORRECT REASONING]... therefore this problem is unsatisfiable."
Analysis: Model hallucinates constraint conflicts that donât exist. The two checkpoints are independent and can both be satisfied. This reveals shallow understanding of XOR dynamics and failure to simulate execution traces accurately.
We manually inspect failed solutions from GPT-4. Common failure modes:
1. Checkpoint violation: Solutions satisfy the target output but violate intermediate checkpoints (83% of failures).
1. Local greedy decisions: Models commit to operation choices early that are incompatible with later constraints (e.g., choosing XOR at position 100, then discovering at position 200 that NOP was required).
1. No backtracking attempts: Even when prompted with âPlease verify your solution,â models do not systematically search for corrections. They regenerate solutions but make similar mistakes.
Example failure case: Instance: n=2048, k=20, checkpoints at positions [103, 256, ..., 1987] GPT-4 output: [Sequence of operations] Analysis: - Satisfies checkpoints 1-12 correctly - At checkpoint 13 (position 803): produces acc=0, requires acc=1 - Continues with incorrect accumulator state - Final output also incorrect - No evidence of backtracking or constraint repair
This confirms that LLMs lack the architectural capability to maintain and revise partial solutions.
8 Discussion: Towards Architecturally Diverse AI
8.1 What We Have Learned
This work demonstrates three critical lessons:
1. Architectural mismatch, not capability deficit: The 0% LLM performance on OpenXOR does not mean âLLMs are badââit means autoregressive generation is structurally incompatible with backtracking search
1. Learnable systematic reasoning: The 76% OpenLM result proves neural networks can learn operator-based reasoning when given appropriate inductive biases
1. Theory guides practice: OpenOperator framework provided the conceptual foundation for designing OpenLM, showing that formal reasoning about computational structures yields practical benefits
8.2 The Path Forward: Hybrid Architectures
OpenLMâs 76% (vs. 100% symbolic baseline) suggests the future lies in hybrid systems:
Neural-Symbolic Integration
Combine strengths of different computational paradigms:
- Neural components: Pattern recognition, language understanding, learned heuristics (e.g., OpenLMâs operator policy)
- Symbolic components: Constraint verification, backtracking, formal guarantees (e.g., SAT solvers, theorem provers)
Example architecture: OpenLM generates candidate operator sequences; symbolic verifier checks constraints; if violated, feedback guides next attempt. This combines neural efficiency with symbolic correctness.
Successes in Other Domains
This hybrid approach has proven effective:
- AlphaGeometry [14]: LLM generates geometric constructions + symbolic verification $â$ IMO gold medal level
- AlphaCode 2: Neural sampling + formal test execution $â$ competitive programming success
- Lean Theorem Proving: Language models suggest tactics + proof checker verifies $â$ automated mathematics
OpenLM adds to this evidence: matching architectural structure to computational requirements beats scaling alone.
8.3 Implications for Benchmark Design
OpenXOR demonstrates a new evaluation paradigm:
Isolate Cognitive Capabilities
| MMLU | Knowledge retrieval | Language, memorization |
| --- | --- | --- |
| GSM8K | Arithmetic reasoning | Templates, calculation |
| HumanEval | Code synthesis | Pattern matching |
| OpenXOR | Systematic search | Minimal (XOR/NOP only) |
Table 5: OpenXOR isolates search capability by minimizing confounding factors.
Future Benchmark Criteria
1. Theoretical guarantees: Prove hardness via complexity theory or information theory
1. Minimal confounds: Simple DSL, no domain knowledge required
1. Generative instances: Avoid memorization and contamination
1. Architectural diversity: Test different computational structures (search, planning, verification)
8.4 Broader Impact and Future Directions
OpenOperator as Research Program
The operator-iteration framework opens multiple research directions:
- Algorithm design: Reformulate classic algorithms (Dijkstra, A*, dynamic programming) as operator systems
- Meta-learning: Learn operator policies that generalize across problem families
- Compositional reasoning: Combine operators hierarchically for complex tasks
Scaling OpenLM
Current limitations and future improvements:
- Longer sequences: Train on $n=4096,8192$ to test generalization
- Transfer learning: Pre-train operator policies on multiple problem types
- Curriculum learning: Start with short sequences, gradually increase difficulty
- Reinforcement learning: Move beyond supervised learning to self-improvement
Real-World Applications
OpenOperator principles apply beyond toy problems:
- Constraint optimization: Scheduling, resource allocation, logistics
- Planning: Robotics, automated theorem proving, program synthesis
- Verification: Software testing, hardware design, security analysis
8.5 Limitations and Honest Assessment
We acknowledge several limitations:
Single Domain
OpenXOR tests one specific problem structure. Generalization to other search problems (SAT, graph coloring, planning) remains to be demonstrated.
Gap to Symbolic Baseline
OpenLMâs 76% vs. symbolic backtrackingâs 100% shows room for improvement. Hybrid approaches combining neural and symbolic reasoning may be necessary.
Model Coverage
We test two autoregressive LLMs. Future work should evaluate more models, including specialized reasoning systems and hybrid architectures.
Generalization
OpenLM trained on $n=512$ and tested on $n=2048$ shows some generalization, but performance degrades with sequence length. Better architectures or training procedures may be needed.
Despite these limitations, our core message stands: Architectural alignment matters more than scale. OpenLM ( $\sim$ 100k parameters) outperforms 20B-parameter LLMs because its structure matches the problemâs computational requirements.
9 Conclusion: Reasoning Requires the Right Architecture
We set out to answer a fundamental question: What is reasoning? Through OpenXOR (problem), OpenOperator (theory), and OpenLM (solution), we provide an answer:
Reasoning is iterative operator application in state spaces, converging to fixed points.
This definition is not merely philosophicalâit has concrete architectural implications:
1. Diagnosis: OpenXOR exposes categorical failure of autoregressive LLMs (0% completion rate)
1. Understanding: OpenOperator theory explains the mismatch (autoregressive generation $â $ backtracking search)
1. Solution: OpenLM demonstrates learnable systematic reasoning (76% accuracy) through architectural alignment
9.1 Key Takeaways
For Researchers
- Architecture matters: The 76% vs. 0% gap proves that computational structure outweighs parameter count for reasoning tasks
- Theory guides practice: Formal frameworks (OpenOperator) inform practical designs (OpenLM)
- Hybrid is the future: Combine neural learning with symbolic reasoning for robust systems
For Practitioners
- Know your tools: Autoregressive LLMs excel at language, not systematic search
- Match architecture to task: Choose computational structures aligned with problem requirements
- Donât expect magic: No single architecture solves all problemsâdiversity is strength
For the Field
- Honest evaluation: Benchmarks must isolate capabilities and provide theoretical guarantees
- Architectur al diversity: Build systems with different computational structures, not just bigger transformers
- Constructive criticism: Expose limitations not to condemn, but to guide improvement
9.2 Final Reflection
This work began with frustration at claims of âAGI-level reasoningâ based on benchmark improvements. But we chose a constructive path: not merely criticizing existing systems, but building better ones.
OpenLMâs 76% is not perfect. But it proves a principle: neural networks can learn systematic reasoning when given the right architectural inductive bias. The gap from 0% to 76% demonstrates that progress comes not from scale alone, but from matching computational structures to problem requirements.
The path forward is clear:
- Diversify architectures: Build systems with different computational structures
- Combine approaches: Integrate neural learning with symbolic reasoning
- Evaluate honestly: Use benchmarks with theoretical guarantees
- Learn from failures: Let OpenXORâs 0% guide architectural innovation
We conclude not with despair, but with optimism grounded in understanding. By reflecting on reasoning itselfâits computational structure, its architectural requirements, its theoretical foundationsâwe move from pattern matching toward genuine problem-solving.
Let this work be a starting point: a demonstration that reasoning is not magic, but structure; not scale, but alignment; not inevitable, but achievableâwhen we build the right computational foundations.
Acknowledgments
[To be added upon de-anonymization]
References
- [1] François Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547, 2019.
- [2] Mark Chen, Jerry Tworek, Heewoo Jun, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021.
- [3] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.
- [4] Dan Hendrycks, Collin Burns, Saurav Kadavath, et al. Measuring mathematical problem solving with the MATH dataset. NeurIPS, 2021.
- [5] Dan Hendrycks, Steven Basart, Saurav Kadavath, et al. Measuring coding challenge competence with APPS. NeurIPS, 2021.
- [6] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.04615, 2022.
- [7] Jian Liu, Leyang Cui, Hanmeng Liu, et al. LogiQA: A challenge dataset for machine reading comprehension with logical reasoning. IJCAI, 2020.
- [8] Yujia Li, David Choi, Junyoung Chung, et al. Competition-level code generation with AlphaCode. Science, 2022.
- [9] Kevin Ellis, Catherine Wong, Maxwell Nye, et al. DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning. PLDI, 2021.
- [10] Armando Solar-Lezama. Program synthesis by sketching. PhD thesis, UC Berkeley, 2008.
- [11] Emina Torlak and Rastislav Bodik. A lightweight symbolic virtual machine for solver-aided host languages. PLDI, 2014.
- [12] Niklas Eén and Niklas Sörensson. An extensible SAT-solver. SAT, 2003.
- [13] Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. ICML, 2019.
- [14] Trieu H. Trinh, Yuhuai Wu, Quoc V. Le, et al. Solving olympiad geometry without human demonstrations. Nature, 2024.
Appendix A Backtracking Algorithm Pseudocode
Algorithm 3 Backtracking Solver for OpenXOR
1: Input: Bit sequence $\mathbf{b}$ , target $t$ , checkpoints $\mathcal{C}$ , max steps $M$
2: Output: Valid operation sequence $\mathbf{o}$ or FAIL
3:
4: $\mathbf{o}â[\textsc{NOP},...,\textsc{NOP}]$ // Initialize
5: $\text{steps}â 0$
6:
7: function Search (pos, acc):
8: if $\text{steps}â„ M$ then return False // Timeout
9: $\text{steps}â\text{steps}+1$
10:
11: if $\text{pos}=n$ then // Base case
12: return $\text{acc}=t$
13:
14: if $\text{pos}â\mathcal{C}$ and $\text{acc}â \mathcal{C}[\text{pos}]$ then // Prune
15: return False
16:
17: // Try NOP
18: $\mathbf{o}[\text{pos}]â\textsc{NOP}$
19: if Search ( $\text{pos}+1$ , acc) then return True
20:
21: // Try XOR
22: $\mathbf{o}[\text{pos}]â\textsc{XOR}$
23: if Search ( $\text{pos}+1$ , $\text{acc}\oplus\mathbf{b}[\text{pos}]$ ) then return True
24:
25: return False
26:
27: if Search ( $0$ , $0$ ) then return $\mathbf{o}$
28: else return FAIL
Appendix B Example Test Instance
Short example for illustration:
Input bits: [0, 1, 1, 1, 1, 0, 1] Target output: 1 Checkpoints: {3 1} Ground truth solution: Operations: [XOR, XOR, NOP, NOP, XOR, NOP, XOR] Execution trace: Step 0: acc=0 Step 1: acc=0 XOR 0 = 0 (op=XOR) Step 2: acc=0 XOR 1 = 1 (op=XOR) Step 3: acc=1 (op=NOP) Step 4: acc=1 (op=NOP) [CHECKPOINT: acc=1] Step 5: acc=1 XOR 1 = 0 (op=XOR) Step 6: acc=0 (op=NOP) Step 7: acc=0 XOR 1 = 1 (op=XOR) Final: acc=1 (matches target)
Appendix C GPT-4 Prompt Template
# XOR/NOP Reasoning Challenge with Checkpoint Constraints You are given a sequence of bits and need to determine a sequence of operations (XOR or NOP) that produces a target output while satisfying checkpoint constraints. ## Rules: - Start with accumulator = 0 - Process each bit left-to-right with an operation: * XOR: accumulator = accumulator XOR current_bit * NOP: accumulator stays unchanged - **Checkpoint constraints:** At certain positions, the accumulator MUST equal a specific required value - Goal: Final accumulator should equal the target output AND all checkpoints must be satisfied ## Few-Shot Examples: [... 3-5 short examples ...] ## Your Task: Input bits: [...] Target output: [0/1] Checkpoint constraints: position X Y, position Z W, ... **CRITICAL:** Your solution MUST satisfy ALL checkpoint constraints. Please provide a valid sequence of operations (XOR or NOP). Your answer should be a space-separated sequence of N operations. Operations: