Can Language Models Falsify? Evaluating Algorithmic Reasoning with Counterexample Creation

We are glad you found our research question valuable and timely, dataset carefully constructed, and findings insightful. We appreciate the constructive feedback, and will address it below:

the benchmark would be more broadly applicable and valuable if it included a greater proportion of Python examples.

We acknowledge that the dataset primarily consists of C++ examples, reflecting the nature of competitive programming data sources. Although a Python-based benchmark is feasible, most competitive programming data remains predominantly in C++. C++ is preferred for its efficiency and suitability under strict runtime constraints, and models generally exhibit strong proficiency in this language. Evaluations by organizations such as OpenAI [1] also predominantly use C++-based Codeforces problems. Additionally, C++’s Standard Template Library (STL) conveniently provides built-in constructs suited for competitive programming. The abundance of high-quality training data available in C++ further biases model performance towards it. We will explicitly acknowledge the predominance of C++ as a limitation in our dataset.

[1] OpenAI. "Competitive programming with large reasoning models." arXiv preprint arXiv:2502.06807 (2025).

Could the authors provide a discussion on how to improve the model’s ability to generate counterexamples based on the observed shortcomings?

We now include a detailed analysis addressing when and why models succeed or fail in generating counterexamples in the common response in Error Analysis section.

In the analysis of factors influencing the model's ability to generate counterexamples, could the authors examine model performance across different algorithm types or problem topics?

We provide some analysis in Figure 4. We will add the distribution of model performance across problem type tags in the revised draft. We additionally conducted analysis over distribution of errors, which might be more relevant here and obtain the following results:

We observe:

• This distribution is notably skewed when compared to the underlying distribution of bug types in the dataset, which are more evenly balanced with no single dominating class, based on a manual analysis of a random sample of 100 problems.
• Models are less likely to identify when the approach taken by the code is logically flawed, either irreparably or in very specific cases which can be separately handled. And they are much worse at spotting the latter.
• On the other hand, they are more likely to find simpler issues with using wrong constants in code compared to what the input constraints would require, or other errors like off-by-one errors.

We thank the reviewer for the suggestions and will be sure to include an explicit discussion of the error analysis, distribution of bug types and acknowledge the predominance of C++ as a limitation. We are glad this makes our paper stronger!

We are glad you found our work a novel perspective on a critical problem, and our proposed evaluation effective. Below, we address the specific concerns raised:

First, the coverage and diversity of the benchmark are somewhat insufficient.

We agree our benchmark is only a proof of concept for how LLM falsification capabilities can be measured, and not representative of general falsification capabilities. Our work is meant to demonstrate that:

• 1. Falsification capabilities can be evaluated as generating code that creates counterexamples which demonstrate a claim or solution is wrong.
• 2. As a first step, we chose a domain where automatic verification is relatively easy for novel counterexamples, and recent reasoning models already perform well at solution generation. We found that despite this, they are not good at generating counterexamples for incorrect solutions.

We agree more research will be required to create falsification benchmarks with better domain coverage and diversity, and are happy to acknowledge this more explicitly in a new limitations section.

Although the authors employed a large number of carefully designed automated methods to clean the data, credible evidence is still lacking to confirm that the benchmark data is of high quality.

The data quality is enforced from the rules we used for data curation and filtering.

• We only take official solutions on the codeforces website which are verified to be incorrect and fail some test case.
• We highlight we had strict filtering of problems with a domain-expert, i.e. a grandmaster on Codeforces go through every problem and incorrect solution included in the benchmark to ensure its validity. The domain-expert found some initial solutions included conditional statements to make the code fail for some inputs, which are trivial samples for falsification. We explicitly excluded these.

Overall, our dataset has 0% label noise, in that all solutions are verified to be incorrect, and are challenging to falsify as they passed a large number of initial test cases.

Additionally, the construction of our evaluation guarantees that any valid counterexample will be accepted by the evaluation procedure, and the model isn’t restricted in the ones in the ground truth. An ideal model can achieve 100% success rate, which is rare in LLM benchmarks [1].

• [1] Vendrow, J., Vendrow, E., Beery, S., & Madry, A. (2025). Do Large Language Model Benchmarks Test Reliability?. arXiv preprint arXiv:2502.03461.

The authors should consider incorporating some reflective methods into the baselines to enhance the comprehensiveness of the benchmark [1, 2].

We agree and will provide a comparison in the updated draft, we are currently running experiments on DeepseekV3 using self-reflection. We highlight that the reasoning models we tested are explicitly RL-trained with emergent reflection, and yet they performed poorly. It is officially recommended to keep prompts for reasoning models simple and direct, and recommendations for non-reasoning LLMs (prompting for chain of thought or reflection) may not apply: https://platform.openai.com/docs/guides/reasoning-best-practices

We thank the reviewer for the suggestions and will be sure to include an explicit discussion of the data quality, and acknowledge the coverage as a limitation. We are glad this makes our paper stronger!

We are glad you found our research question of great need, and dataset curation thorough. We appreciate the constructive feedback, and will address it below:

The framing in the introduction largely focuses on falsifying hypotheses in scientific discovery while the main contribution is to introduce a benchmark for finding counter-examples to programming problems, mostly in C++. It it not clear to me that these are the same kinds of reasoning and that being better at one would help the other.

Indeed, more research will be required to create an automatic evaluation for falsification of counterexamples to general scientific claims. Our work provides a proof of concept for algorithmic problem solving, where counterexamples are programmatically verifiable. We do think that our proposed abstraction of generating code that outputs a counterexample to a claim can generalize beyond coding scenarios, we characterize this in Section 3.1 and Section 3.2 which might be helpful. In Appendix B.3, we include a preliminary discussion of how the generated code could include entire experiments, as the agentic capabilities of LLMs improve going forward. In this domain where recent reasoning models have become quite good at generating solutions, we find they struggle at falsifying incorrect algorithmic solutions — implying being capable at generating solutions does not imply falsification capability, which might get overlooked given recent interest in the community about verification being easier than generation. We will include a reference to Section 3.1 and 3.2 to clarify our contribution, and highlight we tried to caveat this aspect even in the title. We are happy to be more up front about what our work achieves.

Was the evaluation conducted over multiple runs? It seems difficult to conclude how significant these results are

We provide bootstrapped confidence intervals to quantify result variability. See below:

The benchmark seems to massively oversample solutions in C++ ... I wonder if this doesn't skew the benchmark in favor of models with higher C++ capability.

We acknowledge that the dataset is predominantly in C++, an inherent property stemming from the nature of competitive programming data source. While a Python-based version is possible, most real-world competition data is in C++. C++ is preferred due to its efficiency and suitability for strict runtime constraints. The models we test are proficient in C++ given that their competitive programming capabilities are reported based on C++ solutions [1]. This is also because there is abundant high-quality C++ code available online as training data for competition tasks. We will note the use of C++ as a limitation of our dataset.

[1] OpenAI. "Competitive programming with large reasoning models." arXiv preprint arXiv:2502.06807 (2025).

Including an expert human baseline in Table 1

Note that all samples included in our dataset failed on human-generated test cases. In that sense, across problem setters, the human success rate was 100%. It is expensive to report a human baseline across samples here for a single human. However, we did separately also report model performance on the “hacked subset” where humans found the counterexample in a extremely time-limit setting, and provide results below:

We discover the performance on the hacked subset is uniformly lower-- as these are the hardest subset of the problems. Every solution here passing the full array of test cases, including corner cases set by the problem setter.

I think the contribution would be more valuable if the error analysis/identification of failure modes was more thorough.

We now include a detailed analysis addressing when and why models succeed or fail in generating counterexamples in the common response in Error Analysis section.

We are glad you found our work impactful and experiments well designed. We appreciate the constructive feedback and address it below:

In its current form, the work comes across as a specialized benchmark for code debugging rather than a general advancement toward AI-driven falsification in science.

Indeed, more research will be required to create an automatic evaluation for falsification of counterexamples to general scientific claims. Our work provides a proof of concept for algorithmic problem solving, where counterexamples are programatically verifiable. We do think that our proposed abstraction of generating code that outputs a counterexample to a claim can generalize beyond coding scenarios, we characterize this in Section 3.1 and Section 3.2 which might be helpful. In Appendix B.3, we include a preliminary discussion of how the generated code could include entire experiments, as the agentic capabilities of LLMs improve going forward. In this domain where recent reasoning models have become quite good at generating solutions, we find they struggle at falsifying incorrect algorithmic solutions — implying being capable at generating solutions does not imply falsification capability, which might get overlooked given recent interest in the community about verification being easier than generation. We will include a reference to Section 3.1 and 3.2 to clarify our contribution, and highlight we caveat this aspect even in the title. We are happy to be more up front about what our work achieves.

A simple fuzzing or symbolic execution baseline could have provided a point of reference (e.g., can an automated programmatic method find counterexamples for any of these buggy solutions?)

Since the problems are stated in natural language, we are unsure how this would work. Could the reviewer please expand how fuzzing or symbolic execution systems handle natural language input? We agree such comparisons, if possible, would be quite interesting!

yet they never quantify how a brute-force or heuristic search might perform on the remaining problems.

In Table 2, we showcase the RandSearch baseline where LLMs are prompted to generate a brute-force solution and randomly generated test cases given access to the problem and the incorrect solution. The obtained accuracies are low, with the best success rate being 8.3% from o3-mini (high). Note that this is different from the filtering step, where access to the incorrect solution was not provided, so any cases found this way were not a targeted falsification of the incorrect solution, and thus these samples were not included in the final dataset.

provide more insights into why the models fail, consider conducting a comprehensive error analysis that categorizes the types of incorrect solutions and corresponding counterexamples within the REFUTE benchmark.

We now include a detailed analysis addressing when and why models fail in the common response in Error Analysis section.

(1) Are the models failing because they can not comprehend the incorrect code logic, or because they can not generate complex inputs, or due to context length issues?

We analysed the performance of models based on the problem statement and code length and provide the plot in Fig 6 (Appendix). We found that model successes are not predictable based on the length, and observe similarly poor performance on even the smallest code samples which are a few hundred characters. This indicates that context length issues are unlikely to be at play. Additionally, we note that we mitigate the difficulty in generating long counterexamples that follow a fixed patterns (which are commonly used to trigger bugs, and are the standard method for creating hacks on Codeforces) by letting the model output a script that prints the counterexample.

(2) Are certain categories of bugs (e.g., greedy algorithm errors, off-by-one mistakes, etc.) more challenging than others?

We conducted an analysis over distribution of errors, and obtain the following results:

We observe:

• This distribution is notably skewed when compared to the underlying distribution of bug types in the dataset, which are more evenly balanced with no single dominating class, based on a manual analysis of a random sample of 50 problems.
• Models are less likely to identify when the approach taken by the code is logically flawed, either irreparably or in very specific cases which can be separately handled. And they are much worse at spotting the latter.
• On the other hand, they are more likely to find simpler issues with using wrong constants in code compared to what the input constraints would require, or other errors like off-by-one errors.