# Can Language Models Falsify? Evaluating Algorithmic Reasoning with Counterexample Creation

arXiv: https://arxiv.org/abs/2502.19414 · HTML: https://mlsanity.com/paper/2502.19414/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 27 of its 67 references that are in the map.
- First posted on arXiv 26 Feb 2025.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

## Builds on (most cited first, 27 of 27)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [FEVER: a large-scale dataset for Fact Extraction and VERification](https://mlsanity.com/paper/1803.05355/) (2018)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [Humanity's Last Exam](https://mlsanity.com/paper/2501.14249/) (2025)
- [Can LLMs Generate Novel Research Ideas? A Large-Scale Human Study with 100+ NLP Researchers](https://mlsanity.com/paper/2409.04109/) (2024)
- [Measuring Progress on Scalable Oversight for Large Language Models](https://mlsanity.com/paper/2211.03540/) (2022)
- [Is Self-Repair a Silver Bullet for Code Generation?](https://mlsanity.com/paper/2306.09896/) (2023)
- [RE-Bench: Evaluating frontier AI R&D capabilities of language model agents against human experts](https://mlsanity.com/paper/2411.15114/) (2024)
- [Automated Fact-Checking for Assisting Human Fact-Checkers](https://mlsanity.com/paper/2103.07769/) (2021)
- [Complex Claim Verification with Evidence Retrieved in the Wild](https://mlsanity.com/paper/2305.11859/) (2023)
- [On scalable oversight with weak LLMs judging strong LLMs](https://mlsanity.com/paper/2407.04622/) (2024)
- [PentestGPT: An LLM-empowered Automatic Penetration Testing Tool](https://mlsanity.com/paper/2308.06782/) (2023)
- [Critique Fine-Tuning: Learning to Critique is More Effective than Learning to Imitate](https://mlsanity.com/paper/2501.17703/) (2025)
- [EnIGMA: Interactive Tools Substantially Assist LM Agents in Finding Security Vulnerabilities](https://mlsanity.com/paper/2409.16165/) (2024)
- [CiteME: Can Language Models Accurately Cite Scientific Claims?](https://mlsanity.com/paper/2407.12861/) (2024)
- [Large Language Models in Cybersecurity: State-of-the-Art](https://mlsanity.com/paper/2402.00891/) (2024)
- [Large Language Models as Test Case Generators: Performance Evaluation and Enhancement](https://mlsanity.com/paper/2404.13340/) (2024)
- [Supernotes: Driving Consensus in Crowd-Sourced Fact-Checking](https://mlsanity.com/paper/2411.06116/) (2024)
- [Mind the Gap: Examining the Self-Improvement Capabilities of Large Language Models](https://mlsanity.com/paper/2412.02674/) (2024)
- [Leveraging Print Debugging to Improve Code Generation in Large Language Models](https://mlsanity.com/paper/2401.05319/) (2024)
- [CounterExample Guided Neural Synthesis](https://mlsanity.com/paper/2001.09245/) (2020)
- [On the Challenges of Fuzzing Techniques via Large Language Models](https://mlsanity.com/paper/2402.00350/) (2024)

## Built on by (most cited first, 7 of 7)

- [From Code Foundation Models to Agents and Applications: A Comprehensive Survey and Practical Guide to Code Intelligence](https://mlsanity.com/paper/2511.18538/) (2025)
- [HarnessLLM: Automatic Testing Harness Generation via Reinforcement Learning](https://mlsanity.com/paper/2511.01104/) (2025)
- [Beyond Problem Solving: UOJ-Bench for Evaluating Code Generation, Hacking, and Repair in Competitive Programming](https://mlsanity.com/paper/2606.12864/) (2026)
- [Selection Without Signal, Recovery Through Expression: A Measurement Study of Post-Hoc Falsification Operators for Frozen Small Code Models](https://mlsanity.com/paper/2606.16999/) (2026)
- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)
- [Counterexample Generation via Per-Theorem Symbolic Verifiers: When Imitation Hurts and Reinforcement Repairs](https://mlsanity.com/paper/2610.02444/) (2026)
- [Beyond the Verdict: Agentic Code Judging with Verifiable Feedback](https://mlsanity.com/paper/2610.18760/) (2026)

## Abstract (arXiv)

There is growing excitement about the potential of Language Models (LMs) to accelerate scientific discovery. Falsifying hypotheses is key to scientific progress, as it allows claims to be iteratively refined over time. This process requires significant researcher effort, reasoning, and ingenuity. Yet current benchmarks for LMs predominantly assess their ability to generate solutions rather than challenge them. We advocate for developing benchmarks that evaluate this inverse capability - creating counterexamples for subtly incorrect solutions. To demonstrate this approach, we start with the domain of algorithmic problem solving, where counterexamples can be evaluated automatically using code execution. Specifically, we introduce REFUTE, a dynamically updating benchmark that includes recent problems and incorrect submissions from programming competitions, where human experts successfully identified counterexamples. Our analysis finds that the best reasoning agents, even OpenAI o3-mini (high) with code execution feedback, can create counterexamples for only <9% of incorrect solutions in REFUTE, even though ratings indicate its ability to solve up to 48% of these problems from scratch. We hope our work spurs progress in evaluating and enhancing LMs' ability to falsify incorrect solutions - a capability that is crucial for both accelerating research and making models self-improve through reliable reflective reasoning.