Can Language Models Falsify? Evaluating Algorithmic Reasoning with Counterexample Creation

Shiven Sinha, Shashwat Goel, Ponnurangam Kumaraguru, Jonas Geiping, Matthias Bethge, Ameya Prabhu · 2025

Read Can Language Models Falsify? Evaluating Algorithmic Reasoning with Counterexample Creation by Shiven Sinha, Shashwat Goel, Ponnurangam Kumaraguru, Jonas Geiping, Matthias Bethge, Ameya Prabhu (2025) 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-2502-19414.txt.

Introduction

Six researchers wrote a paper in two thousand twenty-five asking whether language models can falsify claims. Science advances by breaking hypotheses, not just by solving problems. Finding a counterexample to a wrong solution takes effort and ingenuity, yet model benchmarks mostly reward generating answers rather than challenging them.

The team built REFUTE, a benchmark of recent programming competition problems paired with wrong submissions that human experts had already refuted. A counterexample there can be checked by running code, so scoring is automatic. Even the best reasoning agents they tested struggled at the task. The authors argue such inverse tests should become a standard measure of reasoning.

Catalog record

CREATORShiven Sinha, Shashwat Goel, Ponnurangam Kumaraguru, Jonas Geiping, Matthias Bethge, Ameya Prabhu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-19414

Browse the full library · About the Tower of Babel

Full text

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

Can Language Models Falsify? Evaluating Algorithmic Reasoning with Counterexample Creation Shiven Sinha, Shashwat Goel, Ponnurangam Kumaraguru, Jonas Geiping, Matthias Bethge, Ameya Prabhu Abstract 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 % <9\% of incorrect solutions in REFUTE, even though ratings indicate its ability to solve up to 48 % 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. REFUTE Bench falsifiers.github.io Code 0 0 footnotetext: \circ Equal Supervision 1 Introduction Empirical science has evolved through an iterative process of new claims, falsification and subsequent refinement of these claims. Mathematicians too follow a similar approach – they propose conjectures and then invest substantial effort in search of counterexamples before attempting a proof. There has been growing interest in using language models (LMs) to accelerate research ( Jumper et al. 2021 ; Lu et al. 2024 ) , which is considered the next frontier for AI progress. Yet, most existing LM benchmarks focus on a model’s ability to generate solutions to problems ( Jimenez et al. 2024 ; Wijk et al. 2024 ; Phan et al. 2025 ) . In this work, we highlight the need for benchmarks that test the inverse capability – falsification . Scientific hypotheses are considered falsified when concrete contrary evidence is presented ( Popper 2005 ) . Researchers create counterexamples to claims by inspecting every step of argumentation and evidence, leveraging domain knowledge, epistemic uncertainty, reasoning and creative intuition. This process requires deep understanding of the problem, and is both challenging and time intensive. Thus, benchmarking counterexample creation can not only accelerate scientific discovery, but also rigorously test LM reasoning abilities. However, a key challenge with creating such benchmarks is to verify whether a model’s output is a valid counterexample to the claim. Traditional benchmarking by comparison with ground-truth reference solutions is insufficient — there could be many valid counterexamples to a claim ( Lakatos 2015 ) . To make initial progress in this direction, we start by focusing on unstructured algorithmic problem solving, where counterexamples can be verified formally through code execution. Language models have already shown promise in solving algorithmic problems at an expert level ( Jain et al. 2024 ; OpenAI 2025 ) . So we ask: Can LMs create counterexamples for incorrect solutions to algorithmic problems? Figure 1: While standard benchmarks for algorithmic reasoning require models to generate solutions, we propose an inverse benchmark to evaluate reasoning about correctness by falsifying incorrect solutions. To allow expressivity, we let the model output a code that generates the counterexample input, and validate it by comparing the output of the incorrect solution with a held out correct solution. To investigate this, we design a novel benchmark: REFUTE ( R efuting E rroneous F indings U sing T argeted E xamples). Each sample in REFUTE contains: (i) a detailed problem description (including input constraints) and (ii) an incorrect solution. The task for LMs is to create inputs satisfying the constraints, such that the given solution fails. The LM must generate a program that prints such an input, and is allowed to use arbitrary programmatic constructs to this end (Figure 1 ). We automatically source samples of incorrect submissions from Codeforces 1 1 1 https://codeforces.com/ contests in 2024 and 2025. These samples are search and contamination free as Codeforces does not reveal non-trivial failure cases. We regularly update our benchmark to prevent indirect leakage due to potential overlap with training data, similar to LiveCodeBench ( Jain et al. 2024 ) . An automated pipeline to extensively filter samples ensures that counterexample discovery requires reasoning about the incorrect solution beyond random search. REFUTE contains 324 samples spanning diverse algorithmic topics with rich metadata annotations (Section 4 ). We benchmark the current best models from five different model developers, as ranked based on their accuracy at generating solutions to these problems on LiveCodeBench ( Jain et al. 2024 ) . These include OpenAI o3-mini (high) and DeepSeek R1, which can generate correct solutions for up to 50% of the problems in our benchmark based on reported Elo ratings. Yet, even with few-shot prompting with chain of thought and a ReAct agent scaffold ( Yao et al. 2022 ) with code execution feedback, these models can only find counterexamples to <9\% of problems in our dataset. Our results additionally demonstrate a prior hypothesis that LMs’ ability to repair their own incorrect code is bottlenecked by their inability to find mistakes in their code ( Gu et al. 2024 ; Olausson et al. 2024 ) . More broadly, our results demonstrate that verification, which includes falsification of subtly incorrect solutions, can sometimes be harder for models than solving the problem correctly. This indicates limitations in the potential for self-improvement using the generator-verifier gap ( Song et al. 2024 ) . As models progress towards solving novel problems where humans cannot provide ground-truth, it will be crucial that they can reflect about their own mistakes ( DeepSeek-AI 2025 ) to produce more reliable outputs. We hope our work spurs interest in the community to create inverse benchmarks to test the ability of models to invalidate incorrect solutions or claims. 2 Related Work Formal verification Programmatic search methods have long assisted researchers by enumerating and validating cases — ranging from symbolic execution tools like higher-order logic systems ( Blanchette & Nipkow 2010 ) , SMT solvers ( De Moura & Bjørner 2008 ) , symbolic execution tools like KLEE ( Cadar et al. 2008 ) and randomized testing frameworks like QuickCheck ( Claessen & Hughes 2000 ) (for details see eloquent survey by Baldoni et al. 2018 ). Automatic test case generation has widely been studied in software engineering (see surveys ( Anand et al. 2013 ; Zhu et al. 1997 ; Runeson et al. 2006 ) ). Existing work on LM based test generation ( Li & Yuan 2024 ) focuses on creating valid inputs and desired outputs for a given task specification. However, counterexamples may reside in non-obvious regions of combinatorially large input spaces, making search-based methods infeasible ( Holzmann 2002 ) , especially in algorithmic reasoning settings ( Forišek 2006 ) . While formal verification tools have made a lot of progress ( Alur et al. 2013 ; Polgreen et al. 2020 ) ,

Read the complete text