BeyondBench: Contamination-Resistant Evaluation of Reasoning in Language Models

BeyondBench introduces a contamination-resistant evaluation framework that uses on-the-fly algorithmic problem generation to assess the true reasoning capabilities of 101 language models across 44 tasks, revealing significant performance gaps in complex problem-solving and the critical role of tool usage.

The Gist

Imagine you are trying to test how good a student is at math. You give them a worksheet with 100 problems. If the student has seen those exact 100 problems before in their textbook, they might just memorize the answers and get 100%. But that doesn't mean they are actually good at math; it just means they have a good memory.

This is exactly what is happening with Artificial Intelligence (AI) today. The "textbooks" (the internet data used to train AI) are so huge that AI models have likely memorized the answers to the standard tests we use to judge them. They aren't "thinking"; they are just "reciting."

BEYONDBENCH is a new way to test AI that fixes this problem. Here is how it works, explained simply:

1. The Infinite Library (No More Memorization)

Imagine a library where the books are written by a magical machine. Every time you ask for a test, the machine generates a brand new book that has never existed before and will never exist again.

• Old Way: We used static tests (like a fixed list of math problems). It's like giving the same test to every student. If the test is leaked, everyone cheats.
• BEYONDBENCH Way: It creates problems on the fly. The number of possible problems is larger than the number of grains of sand on Earth (over $10^{15}$ possibilities). It is statistically impossible for an AI to have memorized the specific problem you just gave it. It forces the AI to actually solve the puzzle, not just recall an answer.

2. The Three Levels of Difficulty (The Video Game Analogy)

The paper organizes these problems into three "levels," like a video game:

• Easy Level (The Tutorial): Basic arithmetic and counting. Can the AI add numbers or find the biggest number in a list?
• Medium Level (The Boss Fight): Patterns and sequences. Can the AI figure out the next number in a complex pattern (like a Fibonacci sequence) or solve a number theory puzzle?
• Hard Level (The Final Dungeon): These are "NP-complete" problems. Think of these as the most complex puzzles in the universe, like Sudoku, Tower of Hanoi (moving disks between pegs), or Graph Coloring (painting a map so no touching countries have the same color). These require deep, step-by-step logical planning.

3. The "Truth Machine" (No Guessing)

In many AI tests, the computer has to guess if the AI's answer is right. Sometimes the AI gives a weird answer that might be right, and the computer gets confused.

BEYONDBENCH uses a "Truth Machine" (mathematical solvers). Before the AI even sees the problem, the computer calculates the exact correct answer.

• If there is only one right answer, the computer checks for that.
• If there are multiple right answers (like in some puzzles), the computer lists all of them.
• If the AI gets it right, it gets credit. If it gets it wrong, it gets zero. No guessing, no ambiguity.

4. The Results: The "Thinking" Illusion

The researchers tested 101 different AI models, from tiny ones to massive super-computers. Here is what they found:

• The "Thinking" Models are Overthinking: Some new AI models are designed to "think" longer before answering (like taking a deep breath). The paper found that for these complex puzzles, thinking longer often made them worse. They would start solving a puzzle correctly, get confused in the middle, and then try to "fix" their own mistake, which only made it worse. It's like a student who knows the first step of a math problem but then starts second-guessing themselves and writes a completely wrong answer.
• The "Tool" Users Win: The best performers weren't the ones trying to do everything in their head. They were the ones that knew when to use a calculator or write code.
  • Analogy: Imagine a human trying to solve a Sudoku. If they try to do it entirely in their head, they might fail. But if they are allowed to use a pencil and paper (a tool), they can solve it easily. The best AIs realized, "I can't hold all these numbers in my memory; I need to write them down."
• The Ceiling: Even the smartest AI models hit a "ceiling" on the hardest puzzles. They could solve about 50-60% of the hardest problems, but they couldn't get to 100%. This suggests that current AI is still missing a fundamental piece of "reasoning" that humans have.

5. Why This Matters

BEYONDBENCH proves that many AI models are illusions of intelligence. They look smart because they memorized the training data, but when you give them a brand new, never-before-seen puzzle, they struggle.

The paper concludes that to build truly intelligent AI (Artificial General Intelligence), we shouldn't just make the models bigger. Instead, we need to build hybrid systems: AIs that can talk and understand language, but also know when to stop and use a calculator, a code interpreter, or a search engine to get the job done.

In short: BEYONDBENCH is the first test that catches AI models cheating by memorizing answers. It shows us that while AI is getting better at talking, it still struggles to truly think through complex, new problems without help.

Technical Summary

Technical Summary: BEYONDBENCH: Contamination-Resistant Evaluation of Reasoning in Language Models

1. Problem Statement

The evaluation of Large Language Models (LLMs) is increasingly compromised by data contamination. As training corpora grow to web-scale, static benchmarks (e.g., GSM8K, MATH, OlympiadBench) inevitably overlap with training data. This leads to models "memorizing" specific answers rather than learning generalizable reasoning patterns, resulting in inflated performance metrics that do not reflect true algorithmic reasoning capabilities. Existing dynamic benchmarks often lack mathematical guarantees regarding solution uniqueness or fail to account for model-specific constraints like token budgets.

2. Methodology: The BEYONDBENCH Framework

BEYONDBENCH is an evaluation framework designed to eliminate contamination through algorithmic problem generation. Instead of static datasets, it generates problems on-the-fly from a combinatorial space exceeding $10^{15}$ unique instances per task.

Core Components

1. Algorithmic Problem Generation:

   • Dynamic Generation: Tasks are defined by generators $G_\tau$ that map configurable parameters (e.g., list sizes, constraint densities) and random seeds to problem instances.
   • Contamination Resistance: The problem space size ($|\Theta \times R| > 10^{15}$) is orders of magnitude larger than any feasible training corpus ($|C| < 10^{12}$), making the probability of an exact instance collision negligible ($< 10^{-3}$).
   • Formal Verification: Every generated problem is verified for well-posedness.
     • Unique Solutions: For tasks like arithmetic or Tower of Hanoi, solvers verify a single unique solution exists.
     • Multi-Solution Handling: For tasks like N-Queens or Sudoku, the framework enumerates the complete set of valid solutions. Models are credited if their output matches any valid solution, preventing penalization for non-canonical but correct answers.

2. Token-Aware Evaluation Protocol:

   • The framework dynamically scales problem difficulty based on a model's specific context window and output token budget ($C$).
   • Constraint: $T_{prompt}(n) + T_{solution}(n) + T_{buffer} \leq C$.
   • If a problem's minimal solution length exceeds the model's capacity, the problem is excluded or scaled down, ensuring fair evaluation that tests reasoning rather than architectural limits.

3. Difficulty Curriculum:
   The benchmark is structured into three suites covering 44 algorithmic tasks and 117 variations:

   • Easy Suite (29 tasks): Polynomial-time solvable problems (arithmetic, sorting, basic statistics). Complexity: $O(n^k)$.
   • Medium Suite (5 tasks, 49 variations): Exponential growth patterns (Fibonacci, geometric sequences, prime number theory). Complexity: $O(2^n)$ to $O(n!)$.
   • Hard Suite (10 tasks, 68 variations): NP-complete and constraint satisfaction problems (Tower of Hanoi, N-Queens, Graph Coloring, Boolean SAT, Sudoku). Complexity: NP-complete.

3. Key Contributions

1. Contamination-Resistant Evaluation: A framework that mathematically guarantees the impossibility of memorization-based cheating through an exponentially large, dynamically generated problem space with formal solution verification.
2. Token-Aware Scaling: A novel evaluation protocol that adapts problem complexity to model architecture, preventing unfair penalization of models with smaller context windows.
3. Comprehensive Empirical Study: A systematic evaluation of 101 language models (85 open-source, 16 closed-source) ranging from 0.5B to 141B parameters, including quantized variants and "reasoning" models.
4. Tool-Augmented Analysis: A rigorous assessment of how code execution and symbolic solvers impact reasoning, distinguishing between innate reasoning and tool-assisted capabilities.

4. Key Results and Insights

A. Systematic Performance Collapse

Models exhibit sharp performance cliffs rather than gradual degradation as complexity increases.

• Easy vs. Hard: While top models achieve ~90% on Easy tasks, performance drops precipitously on Hard tasks. For example, GPT-5 drops from 97.3% (Easy) to 71.7% (Hard). Open-source models like Llama-3.3-70B drop from 74.8% to 27.2%.
• Threshold Behavior: Tasks like Sudoku and N-Queens show a "phase transition" where accuracy remains high until a critical complexity threshold (approx. $0.7 \times \log_2(\text{context_length})$) is reached, after which performance collapses to near zero.

B. Limitations of Scaling and "Thinking"

• Parameter Scaling: Performance gains follow a logarithmic curve with diminishing returns. Increasing model size from 0.6B to 32B yields significant gains, but further scaling offers marginal improvements on Hard tasks.
• Reasoning Models (LRMs): "Thinking" models (e.g., o3, Phi-4-reasoning) show negligible improvements over their base versions on algorithmic tasks. Detailed case studies reveal they often fail due to state management errors during extended reasoning (e.g., losing track of disk positions in Tower of Hanoi after 89 steps), rather than a lack of algorithmic knowledge.
• Math Fine-Tuning: Specialized mathematical fine-tuning (e.g., Qwen2.5-72B-math) often degrades performance on algorithmic reasoning, suggesting that optimizing for equation solving does not transfer to procedural algorithmic execution.

C. The Role of Tools

• Tool Augmentation: Models with tool access (code execution, calculators) show massive performance gains (e.g., +44% on Tower of Hanoi, +55% on Sudoku).
• Orchestration Bottleneck: The primary bottleneck for smaller models is not the reasoning itself but the orchestration of tools (selecting the right tool, formatting inputs, interpreting outputs). GPT-5 achieves 94% tool orchestration success, while Qwen2.5-3B achieves only 41%.
• Implication: Top-tier proprietary models likely succeed not through superior "pure" reasoning but by effectively recognizing when to offload computation to external tools.

D. Contamination Resistance Validation

• Training Experiments: When models were fine-tuned on 66,000 BEYONDBENCH instances (using a different seed than evaluation), performance on the Hard Suite improved by only ~12-15%, whereas static benchmarks (like GSM8K) show near-perfect scores when trained on test data. This confirms that BEYONDBENCH forces the learning of generalizable heuristics rather than memorization.

5. Significance and Conclusion

BEYONDBENCH redefines the standard for evaluating LLM reasoning by shifting from static, contamination-prone datasets to dynamic, mathematically grounded algorithmic challenges.

• Fundamental Bottleneck: The study reveals that innate algorithmic reasoning is a fundamental bottleneck for current LLMs that cannot be solved by scaling parameters or extended "thinking" alone.
• Path to AGI: The results suggest that the path toward Artificial General Intelligence lies in hybrid neuro-symbolic architectures and agentic systems that can seamlessly integrate language understanding with external computational tools.
• Fair Evaluation: By ensuring contamination resistance and token-aware fairness, BEYONDBENCH provides a reliable leaderboard for measuring genuine reasoning capabilities, exposing the "illusion of reasoning" in models that merely recall training data.

The framework is open-source, allowing the community to extend the benchmark with new tasks and continue evaluating models as they evolve beyond current capabilities.