🤖 machine learning

Evaluating the Architectural Reasoning Capabilities of LLM Provers via the Obfuscated Natural Number Game

This paper introduces the Obfuscated Natural Number Game as a benchmark to evaluate "Architectural Reasoning"—the ability to synthesize proofs using only local axioms without semantic cues—and demonstrates that while general large language models suffer performance degradation under obfuscation, specialized reasoning models maintain their accuracy, thereby distinguishing genuine logical reasoning from pattern matching.

Original authors: Lixing Li

Published 2026-05-04

📖 4 min read☕ Coffee break read

CC0 1.0

Original authors: Lixing Li

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a student to solve a math puzzle. Usually, the puzzle comes with helpful labels like "Addition," "Multiplication," or "Succesor." A smart student might not actually understand the rules of the game; they might just recognize the word "Addition" and recall a memorized trick they've seen before.

This paper asks a tough question: Are these AI models actually doing math, or are they just good at recognizing words?

To find out, the researchers created a "blindfolded" version of a famous math game called the Natural Number Game. Here is how they did it and what they found, explained simply:

The Experiment: The "Alien" Game

The researchers took a standard math game where every rule and number has a clear name (like add or zero). Then, they ran a "scrambler" on it. They replaced every meaningful name with random, nonsense strings like x9z, q22, and b7a.

The Original Game: You see add and know it means addition.
The Scrambled Game (Obfuscated NNG): You see x9z and have no idea what it means. You can't guess; you have to look at the logic of how the pieces fit together to figure out what x9z does.

This tests something the authors call "Architectural Reasoning." It's the ability to build a solution using only the structural blueprints (the logic), ignoring the helpful signs on the doors (the names).

The Results: The "Latency Tax"

The researchers tested several top-tier AI models on both the original game and the scrambled game. They found two main things:

1. The "Universal Latency Tax" (Everyone gets slower)
When the names were scrambled, every single AI model took longer to solve the problems.

Analogy: Imagine you are driving to a familiar coffee shop. You know the signs, the street names, and the landmarks. Now, imagine someone painted over all the signs and renamed the streets with random letters. You still know how to drive, but you have to stop, look at the map, and think harder about every turn. You arrive eventually, but it takes much longer.
The Finding: The AI models had to do this "mental map reconstruction" for every problem. They couldn't just rely on memory; they had to process the raw logic, which cost them time.

2. The "Reasoning vs. Rote" Split
While everyone got slower, the accuracy of the models split into two distinct groups:

The "General" Models (e.g., GPT-4o, Claude): These models are like students who are great at memorizing flashcards. When the names were scrambled, they got confused. Their success rate dropped significantly.
- What this means: They were relying on the "signs" (the names) to solve the puzzle. When the signs were gone, they couldn't find their way.
The "Reasoning" Models (e.g., DeepSeek-R1, GPT-5, DeepSeek-Prover-V2): These models are like students who actually understand the rules of the game. Even when the names were scrambled, their success rate stayed exactly the same.
- What this means: They didn't need the labels. They looked at the logical structure (the "architecture") and figured out the solution just as well as before.

The Conclusion

The paper concludes that there is a real difference between AI that just matches patterns (like recognizing the word "add") and AI that can truly reason through logic structures.

General models are like tourists who need a guidebook with names on it. If you take the guidebook away, they get lost.
Reasoning models are like architects who can read the blueprints. Even if the building has no signs, they can still figure out how the walls and beams fit together.

The study proves that while all AI models get "slower" when forced to think without labels, only the true "reasoning" models can keep their accuracy high in this "alien" environment. This suggests that for AI to discover new math in the future (where no names or labels exist yet), we need these reasoning-focused models, not just the ones that are good at pattern matching.

1. Problem Statement

Despite the success of Large Language Models (LLMs) in formal mathematics benchmarks like MiniF2F and PutnamBench, a critical ambiguity remains: do these models possess genuine logical reasoning capabilities, or are they merely performing semantic pattern matching against their pre-training data?

The Gap: Current benchmarks often rely on library retrieval (e.g., Mathlib), where success depends on recognizing high-level lemmas and semantic identifiers (e.g., add, succ). This fails to test a model's ability to synthesize proofs in "alien" mathematical domains where no external libraries or familiar semantic cues exist.
The Need: To achieve automated theorem discovery, AI must demonstrate Architectural Reasoning: the ability to synthesize formal proofs using only local axioms, definitions, and structural logic, independent of semantic meaning or external repositories.

2. Methodology

The authors introduce the Obfuscated Natural Number Game (O-NNG), a zero-knowledge benchmark designed to isolate structural reasoning from lexical retrieval.

A. The Obfuscation Algorithm

The core innovation is the systematic removal of semantic cues from the Natural Number Game (NNG) in Lean 4:

Noise Level ( $\lambda$ ): Defined in the range $[0, 1]$ $[0, 1]$ .
- $\lambda = 0$ : Original NNG (semantic identifiers intact).
- $\lambda = 1.0$ : Complete randomization of identifiers.
Perturbation Mechanism: An exponential relationship $P = \lambda^{2.5}$ $P = λ^{2.5}$ determines the probability of character-level perturbations.
- Substitution: Replaces characters with valid Unicode/ASCII candidates.
- Insertion: Injects new characters (probability $0.4P$ ).
- Deletion: Removes characters (probability $0.3P$ ), ensuring identifiers remain non-empty.
Goal: This process transforms the dataset into a "closed environment" where identifiers (e.g., axioms, theorems, tactics) are random strings, forcing the model to rely solely on the logical structure of Peano axioms.

B. Experimental Setup

Dataset: 68 formal problems from the NNG, organized into 8 modules (Addition, Multiplication, etc.).
Models Evaluated: Five state-of-the-art models via API:
- Reasoning Models: DeepSeek-R1, GPT-5, DeepSeek-Prover-V2.
- General Models: GPT-4o, Claude-Sonnet-4.5.
Pipeline:
1. Parsing: Extract NNG with strict dependency ordering.
2. Obfuscation: Apply character-level perturbations based on $\lambda$ .
3. Query Generation: Construct prompts containing "alien" axioms, target theorems, and available tactics.
4. Inference: Models output a JSON with a natural language plan ("Draft") and Lean 4 code ("Code").
5. Verification: Automated validation using the Lean 4 compiler (v4.27.0) to check for syntax and logic errors.
Metrics:
- Correct Rate (%): Ratio of successfully proven theorems.
- Average Time (s): Inference latency.

3. Key Contributions

Definition of Architectural Reasoning: Formalized as the capacity to synthesize proofs using exclusively local definitions and axioms within a closed theory, excluding external libraries and high-level automated tactics (like linarith).
The O-NNG Benchmark: A novel, zero-knowledge evaluation framework that quantifies the "Semantic-Reasoning Gap" by measuring performance degradation when semantic identifiers are removed.
Quantification of the "Latency Tax": Established that navigating alien domains imposes a universal computational cost (increased inference time) on all models, regardless of architecture.

4. Results and Analysis

The study reveals a sharp divergence in model behavior when semantic cues are removed:

Universal Latency Tax:
- All models exhibited a statistically significant increase in inference time as $\lambda$ increased.
- Implication: Removing semantic identifiers forces models to perform more intensive internal searches or logical reconstruction, regardless of their base capability.
Divergence in Robustness (Accuracy):
- Reasoning Models (DeepSeek-R1, GPT-5, DeepSeek-Prover-V2): Maintained stable accuracy across all noise levels ( $\lambda \in [0, 1]$ $λ \in [0, 1]$ ). The drop in performance was not statistically significant.
  - Conclusion: These models rely on structural logic and can navigate Peano axioms without semantic anchors.
- General Models (GPT-4o, Claude-Sonnet-4.5): Suffered a statistically significant drop in success rates as $\lambda$ $λ$ increased.
  - Conclusion: Their performance on standard formal tasks relies heavily on semantic pattern matching and familiarity with naming conventions rather than pure logical synthesis.
Statistical Significance: One-Way ANOVA confirmed that the performance drop for general models and the latency increase for all models were statistically significant ( $p < 0.05$ ).

5. Significance and Implications

Benchmarking True Reasoning: O-NNG provides a rigorous metric to distinguish between models that "know" mathematics via pattern matching and those that can "reason" via structural logic.
Architectural Direction: The results suggest that for the future of automated theorem discovery (AI4Math), reasoning-focused architectures (like DeepSeek-R1 and GPT-5) are superior to general-purpose models, as they are robust to the absence of semantic priors.
The "Reasoning Uncanny Valley": The data hints at a non-linear relationship where partial noise might be more detrimental than total obfuscation, suggesting that residual semantic cues can act as distracting heuristics.
Future AI Agents: The findings advocate for the development of "Knowledge-Grounded Semantic Agents" capable of operating in domains with incomplete or obscured ontologies, a prerequisite for discovering novel mathematical theorems.

In summary, the paper demonstrates that while current LLMs can solve known problems via pattern matching, only specific "reasoning" architectures possess the Architectural Reasoning necessary to solve problems in entirely unfamiliar, obfuscated logical environments.