acceptodds
Under review as a conference paper at ICLR 2027

The Primitive Recursor Test: Construction-Recognition Gap and Representation-Shift Failure in Formal Reasoning

Abstract

The primitive recursor, and , is the counted loop inside fold combinators, proof-assistant recursors, and trip-counted compiler loops, and an automated termination tool certifies it in 0.025 seconds. Language models fail on it, in the forms that an observer-license theory of proof classes, stated in this paper, accounts for. The Primitive Recursor Test (PRT) asks 30 models, across 4,160 sessions, three questions: does the system terminate, does the proof have mathematical validity, and does the proof use the displayed rules alone. A Python rulebook decides every proof score from reader transcriptions against certified answers, Lean theorems, and ground-term counterexamples; no model and no person assigns one. The termination verdict is right in 791 of 960 sessions on the two-rule system, its copy-removed control, and an eight-rule system, and the proof behind it fails the test of mathematical validity in 516 of those 791. On the two-rule system, 64.6% of 240 sessions fail mathematical validity and 99.2% give no rule-derived proof under the paper's rulebook; the three models with mathematical validity in all 8 of their sessions give no rule-derived proof either. On the eight-rule system, which contains the recursor, 25.4% of 480 sessions give a wrong termination verdict and none gives a rule-derived proof. Offered the rule-derived method on a menu of five methods that all have mathematical validity, 94.2% of sessions judge that it has mathematical validity and is rule-derived; unaided, 2 of 240 and 0 of 480 sessions construct it, and 29 of 30 models change their method across identical prompts. The theory says why: a proof method uses only what its observer reads, and the step rule copies into the output and into the recursive call, as any first-order rule that records the step argument in its output while continuing the recursion must. No measure that adds symbol weights over the whole term then decreases at the step, so the standard methods need either a precedence or coefficients that the rules do not fix, or the dependency-pair projection, which compares the counter at the recursive call under an imported soundness theorem and is the one method the rules determine. Each failure form the theory derives occurs: termination denied, a decrease claimed that a ground term refutes, or imported parameters that differ from one session to the next. Sessions, reader records, scoring code, and reference proofs accompany the paper as supplementary material.

Primary area:
datasets and benchmarks
Keywords:
large language models, mathematical reasoning, formal reasoning, proof generation, program termination, term rewriting, benchmarks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_7fqdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper evaluates 30 language models on terminating primitive-recursion rewrite systems, separating termination verdicts, mathematical proof validity, construction under a bespoke 'rule-derived' requirement, and recognition of supplied proofs. Its reference mathematics shows why nonnegative additive symbol weights fail on the duplicating recursor and gives successful alternatives. Across 4,160 sessions, it reports low construction success despite stronger supplied-proof recognition, plus a copy-removal control that improves mathematical proof success from 85/240 to 117/240. The main interpretive question is whether these outcomes measure inability to construct a valid proof or sensitivity to the study's additional scoring conventions.

Critical strengths
  1. The benchmark has a concrete mathematical foundation. The additive-weight obstruction is established by a ground substitution rather than failed search, and successful reference proofs distinguish the inadequacy of a proof class from nontermination (Section 2; Appendix C). This makes specific observed proof errors falsifiable.

  2. Separating verdict, proof construction, and supplied-proof assessment is useful. The broad model panel and paired copy-removal contrast provide evidence that a correct termination answer need not come with a valid proof. The +13.33 percentage-point construction improvement under copy removal, with reported interval [7.1, 19.6], is an informative result within the stated scoring regime (Table 1; Appendix H).

Critical weaknesses
  1. The headline 'rule-derived' construction rate does not directly measure whether an answer constructs a valid requested proof. Appendix B.4/Table 9 (PDF p.17) removes credit even when a correct rule-derived proof accompanies a chosen comparison mentioned only hypothetically, rejected, or withdrawn. This scores the entire exposition's purity and can penalize successful final constructions. Moreover, selecting a verified precedence or polynomial is normally proof-witness construction rather than adding object-level assumptions; the open prompts and clarified menu do not express the same restriction equally clearly. The 2/240 and 0/480 figures therefore need final-proof/existential rescoring before supporting the stated construction-recognition gap.

  2. Test 01 appears to score a stronger rewrite relation than the displayed task. The retained Lean prompt (Appendix I, PDF pp.44–47) defines Step with eight root-rule constructors and no context-closure constructor, while Appendix B's proof checks require decrease at arbitrary rewrite positions. Termination of the literal root relation and of its contextual closure are different obligations. Without an explicit mapping from the text shown to models to the scored relation, failures on this arm cannot cleanly establish the claimed representation-shift failure. Together these issues require more than a wording correction to the central benchmark conclusion.

Questions for authors
  1. Please report valid-proof existence and final-endorsed-proof rates separately from whole-answer purity. How many failures arise solely from hypothetical, rejected, or withdrawn alternatives, and how much of the construction-recognition gap remains?

  2. Was contextual closure explicitly included in the instructions shown to every Test 01 model? Please provide that text, or rescore against the literal Lean Step relation and separately report results for contextual rewriting.

  3. Can independent termination experts audit a stratified sample of the semantic transcriptions and scoring decisions? This could materially change confidence in the extreme success rates, particularly given the 166/1,200 mathematical-score changes reported in Appendix B.5.

1 comment
AuthorsOpenReview ↗

Author Response to Reviewer 7fqd

Thank you very much for your thorough review. The review reads the scoring rulebook and the prompt files closely, and it is right on several points. The revision reports each count that the review asks for, and we give them here.

First, the core of the paper in one line. The two rules do the same thing as the factorial of everyday arithmetic, n! (not to be confused with the factorial system in the paper). Four factorial becomes four times three factorial: the line gets longer, but the calls count down to 0, and there the run halts. The rule of the paper has the same countdown and copies one item at each call.

We are asking frontier LLMs: does the everyday factorial n! eventually produce an answer?

It is an extremely simple question, and the failure holds under every reading that the review asks for.

Weakness 1 and Question 1, the scoring. We agree that a checked ranking of the symbols or a checked polynomial is ordinary proof construction, and the paper gives it full mathematical credit. The rule-derived score is a second, separate property: the proof compares the counter at the recursive call and picks no ranking and no coefficients. Table 10 of the revision gives the readings that the review asks for. On the two-rule recursor (30 models, 8 runs each, 240 answers), a valid proof is present in 85 answers as a whole, in 86 with the main proof alone, and in 125 with any proof anywhere in the answer. A rule-derived proof is present in 2 answers as a whole, in 20 with the final proof alone, and in 41 anywhere. On the eight-rule system the valid-proof counts are 80, 65 and 99 of 480, and the rule-derived counts are 0, 0 and 6. Ignoring alternatives that are hypothetical, rejected, withdrawn or quoted adds no pass on either system. An answer that asserts a false proof beside a true one leaves the choice to the reader, and the whole-answer rule was fixed before the submission (entries of 30 June and 9 August 2026 in the scoring record). On a list of five valid methods, 452 of 480 answers judge the counter proof right, so the gap between writing that proof and recognizing it is 93 points under the paper's score and 77 points under the widest reading. We agree that the open prompt and the clarified list state the restriction with unequal clarity, and the paper reports the effect of the clearer wording.

Weakness 2 and Question 2, the eight-rule prompt. The answer is no: that prompt did not state the closure under contexts (its text is in Appendix I.1). Its Lean text defines Step by eight root constructors, and our scores used the rewrite relation that those rules generate, closed under contexts. The reviewer's reading is right. Section 2 and Appendix B.9 of the revision say so, and Table 12 scores both relations. The answers saw it too: 168 of the 480 state that the displayed relation has no rule for steps inside a term. Under the literal root relation, 85 to 177 of the 480 answers hold a valid proof, against 80 under the closure, and 109 to 122 answers give a wrong termination verdict under both relations. The root relation cannot test recursion: the recursive rule fires once at the root and stops, since no rule starts with the wrapper, and even the rule without its counter, F(x, y) → G(y, F(x, y)), stops after one root step. In factorial terms, once 4! has become 4 × 3!, a root step can no longer reach 3!, since the multiplication is at the root. Our main result does not depend on that prompt: 3,480 of the 4,160 sessions of the paper do not depend on that reading. The two-rule recursor and its control print plain rewrite rules in the TPDB format, and rewriting inside terms is the standard meaning of that format.

Question 3, the audit. No outside expert has audited a sample yet, and we welcome such an audit. The supplement holds every answer, its recorded reading with verbatim quotes, its score and the rule that decided it, so an expert can grade a sample blind and compare. For the final version we can have outside termination experts grade a sample stratified by task and by outcome. The 166 changed scores come from the move from earlier recorded judgments to the checker program, and 130 of them remove credit (Appendix B.5). Our own re-audit has already corrected one reader defect, and three control answers regained credit (Appendix B.6). We will post the reading, the counterexample and the deciding rule of any session that the reviewer names.

The bottom line. Set the eight-rule prompt aside, set the rule-derived score aside, and credit any valid proof anywhere in an answer. On the two-rule recursor, 115 of 240 answers still hold no valid proof, for two rules that a standard termination tool proves in 0.025 seconds. This is the everyday factorial, and it is the failure that the paper reports.

Reviewer_8tnYOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
2(+1)
Soundness
2
Read review
Paper summary

This paper is completely outside my research field: I have never heard of primitive recursive functions but AC encouraged me to write the review. I interpreted this paper using AI, and the following decisions are based on my interpretation of the AI-generated text.

The paper introduces the Primitive Recursor Test, a prompt-based evaluation of LLM reasoning about termination of term-rewriting systems centred on a primitive-recursion pattern. Across 30 models and 4,160 sessions, it distinguishes correct termination verdicts, mathematically valid proofs, and proofs satisfying an additional “rule-derived” requirement. It compares proof construction with assessment of supplied methods and examines changes in copying, notation, context and system size.

Critical strengths
  • Substantial experimental coverage within the selected setting. The study includes ten core task types and eight auxiliary groups, with repeated evaluations across multiple providers.

  • Useful controlled comparisons. The copy-removal experiment is particularly informative: mathematical-proof credit increases from 85/240 to 117/240, while correct termination verdicts change only from 215/240 to 218/240. This helps distinguish answering correctly from constructing an adequate justification.

Critical weaknesses
  • The motivation and central contribution are difficult to extract. As a reader outside the area, I found the main message obscured by dense terminology and numerous detailed results. The introduction would benefit from a worked example showing the input, a valid argument, an invalid argument, and how the two scoring criteria differ. The paper should explain more directly what an average ICLR reader learns from this diagnostic and why that insight matters. Please avoid names like Schema A or Test 01. Give a meaningful naming convention instead. Reviewers are not AI agents with dense attention.

  • Dependence on changing APIs and provider defaults limits reproducibility and comparison. The recorded model identifiers, collection dates and archived responses are valuable. Nevertheless, later API behaviour may differ, and provider-default reasoning settings need not represent comparable computational budgets. Conclusions should be explicitly tied to the sampled versions and settings. Corroboration with fixed model checkpoints or more controlled inference budgets would strengthen the findings.

The methodology relies solely on prompting, which falls short of my expectations.

Questions for authors
  1. How does this diagnostic relate to Medley and Manolios, Feedback & Synthesis in LLM-Assisted Termination Proofs (ITP 2026, DOI: 10.4230/LIPIcs.ITP.2026.22)? A direct comparison would help establish the contribution relative to published LLM termination-proof research.
  2. What are the one or two principal insights that extend beyond previously reported differences between answer accuracy, proof quality and verification ability? Please explain how these insights could guide the development or evaluation of future reasoning systems.
2 comments
AuthorsOpenReview ↗

Author Response to Reviewer 8tnY

Thank you very much for your thorough review. First and foremost, we fully acknowledge and accept all the criticisms about the accessibility of the paper, the language and the presentation. We believe we can present the core of the paper in a much more intuitive manner.

As we laid out in our response to Reviewer ZFgm (to avoid posting duplicated content), it is very helpful to look at the factorial of everyday arithmetic, n! (not to be confused with the factorial system in the paper). It is the perfect instantiation of the same primitive recursion. Both systems have duplication on the right-hand side: one multiplies it, and one carries the duplicated record as emitted memory. And both kernels halt when the counter drops to its halt condition.

We are asking frontier LLMs: does the everyday factorial n! eventually produce an answer?

It is an incredibly simple question. Yet the failure rate and the instability in reasoning are off the charts. In our main test, the two-rule recursor (30 models, 8 runs each, 240 answers), 64.6% of the answers (155 of 240) fail to present a valid proof that the system terminates. Across our three open tests, 29 of 30 models give more than one method in repeated runs of the same test. We also encourage the reviewer to completely forget about the additional condition about external assumptions. Assume we are just asking the models: does this system terminate, and if yes, show the proof.

Test interface and reproducibility. The numbers reported in the paper are from our latest corpus. Our original tests were conducted in March and April 2026, entirely through the Copilot interface and the models it provides. The results were highly similar, although the date, the interface and the settings all differ: on the two-rule recursor, valid proofs were 34 of 108 answers in the first corpus and 85 of 240 in the second. Tool use (web search and code execution) also had a near-zero effect. Every rate in the paper is tied to a model version and a collection date. We can also add runs on fixed model checkpoints and controlled inference budgets for the final version.

Prompting. We do not believe that prompting is a determining factor in the failure rates that we are seeing. The question requires reasoning identical to the same question about the everyday factorial. The rules are present, and the proof arithmetic is as basic as it comes. The scoring uses no model as a judge: checker programs decide every score.

Question 2, the two insights.

1. A model can reject a failing measure when it is handed one, and still write one as its own proof. Handed three whole-term sums to check on the eight-rule system (a larger system with the same rule), 232 of 240 answers reject all three. Asked for their own proof on that system, 130 of 480 answers propose a direct measure on the whole term, and all 130 fail. The paper proves that the copy rules out the fixed-weight sums in advance. For builders and evaluators: checking a given proof and writing one are different skills, so a test that only asks for approval or rejection overstates ability. A benchmark can also know in advance that one kind of proof can never work.

2. One copied item breaks the proof, and neither the yes-or-no answer nor the model's own review shows it. Take the copy of y out of the rule (the copy-removed control), and valid proofs go from 85 of 240 to 120 of 240, while the yes answers stay the same (215 and 218). A model's own review of its proof carries almost no information about the score. Outside our tests, in the public math benchmark ProcessBench, 521 of the 1,700 solutions with a correct final answer carry a wrong step marked by its annotators. For builders and evaluators: a right answer and a model's review of its own work cannot serve as the check. A reasoning system needs an outside checker, and for recursion a tool that finds the recursive calls, as the prover of Medley and Manolios does.

The worked example and the names. The introduction now has the worked example (Figure 1), and the main text now uses plain names, such as "two-rule recursor" and "copy-removed control".

Question 1, Medley and Manolios (ITP 2026). They join two open models to a theorem prover (ACL2s) that sends each failed proof back for another try, and they count the problems solved after those tries. Our paper measures the first try: the proof that each of 30 models writes by itself, before any feedback, on the smallest counted loop. Their findings match ours: their models alone often fail to split a program into its recursive calls, and their paper prints a model that retries one failed formula with a new constant each time, the same stuck search as our whole-term measures. Their conclusion names the reading of thinking traces as future work, and our paper does that reading. The revision cites the study in Sections 4.2 and 7.

Thank you for your effort in your explanation.

I'm willing to raise my rating of the presentation, but it will be improper for me to give a weak acceptance based on my overall understanding of this paper. I'm sorry to the authors.

Reviewer_ZFgmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed primitive recursor test to validate whether LLMs can build valid termination proofs for a minimal recursive system. The experiments are conducted with 30 models with 4160 sessions. The paper concluded an observer-license theory to explain the reasons why models can recognize a suitable proof method while fail to build it.

Critical strengths
  • This paper targets an important problem in my view and the minimal recursor provides a well-defined test case.
  • This paper presents an empirical study and auditing support, which could be beneficial for follow-up studies.
Critical weaknesses
  • This paper is not well-written and the contents are not organized in a clean way, which make it hard to follow. Also, there is a lack of intuitive expressions and illustration. I think this paper requires careful revisions.
  • Technically, the proposed representation-shift explanation may not be supported by the experiments. For example, a failed additive whole-term measure cannot tell whether or not models rely on the representation. Also, whether the conclusion of construction failures stand may be affected by prompt information and search difficulty, etc.
Questions for authors

N/A

1 comment
AuthorsOpenReview ↗

Author Response to Reviewer ZFgm

Thank you for your feedback. We fully acknowledge the criticism about the accessibility and the presentation of the paper. We have revised the body with more accessible language and relatable examples, and we commit to a thorough and careful revision for the camera-ready version if the paper is accepted. We hope our response will make the case for that chance.

The perfect instantiation of the primitive recursion in our paper is the everyday factorial "n!" (not to be confused with the factorial system in the paper). Factorial is an identical system, with the only difference that the duplicating term in factorial, n, is multiplied, and in the primitive recursor it is carried in the wrapper as an emitted record. In both systems the duplication happens on the right-hand side and the counter drops. And there is a halt state: "0! = 1" for factorial and "F(x, y, 0) → x" for the recursor.

We are asking frontier LLMs: does the everyday factorial n! eventually produce an answer?

This is at the most primitive mathematical level. Our main test is the two-rule recursor: the two rules of the paper, given to 30 models, 8 runs each, 240 answers in all. Even if we completely ignore the extra condition of the benchmark, that a proof use nothing from outside the system, 64.6% of the answers (155 of 240) fail to present a valid proof that the system terminates. This is the main failure we report.

The whole-term measure proof (the whole-term observer). The direct proof is the whole-term observer: it looks at the system as is, with no representation shift. All a model has to do is compare the size of the left-hand side with the size of the right-hand side (the number of symbols) and see if it is shrinking. It is not shrinking! This failure is arithmetically visible. Still, in the two-rule recursor test, 57 of the 240 answers give such a measure as their main proof, and not one of the 57 holds a valid whole-term measure.

Representation shift. Dependency pairs work because they ignore the duplication. The prover looks at the system, decides that the duplication has no bearing on termination, fully ignores the duplicating term, and only observes and projects to the counter. This changes the representation of the system, and all that remains is the comparison "n > (n-1)", and it always holds. This is not a complex question, and the answer is extremely simple. Path orders and polynomials go the other way: the prover adds something that the rules do not contain, a ranking of the symbols or the coefficients of a scoring rule. So a representation shift is the observer (the prover) making a decision on the way it observes the system: a dimension of the data is discarded and ignored (here, the duplicating term), or a new dimension is introduced.

On "whether or not models rely on the representation". Representation is the only thing a model can rely on, because it is the thing the model sees: the rules as written, and the way it treats them. We agree that one failed sum alone shows little, and this is the reason the paper changes the rule and counts again. The copy-removed control is the same test with one change: the rule no longer duplicates y, so the whole-term measure works. Valid proofs go from 85 of 240 on the two-rule recursor to 120 of 240 on the copy-removed control.

On prompt information and search. This task requires very little reasoning: a standard termination tool proves that the two rules terminate in 0.025 seconds. The failure rate is still remarkably high, and the failure reproduces in two collections of answers gathered months apart, and with web search and code execution turned on. The models also know the object: some answers name the system as primitive recursion, and most of those still give no valid proof. So we believe that prompting has little effect on this result.

Circular reference and external safety signal. Take the minus-one out of the everyday factorial (n! = n × n!) and take the counter out of our rule (F(x, y) → G(y, F(x, y))), and the result is a true circular reference that runs forever. Put the counter back in, and every run halts, yet a whole-term symbol count grows on both systems. Direct whole-term counting cannot tell a halting counted loop apart from an endless loop. That makes this tiny system a clean test for catching a right answer with broken reasoning. Public benchmarks show the same pattern: in ProcessBench, 521 of 1,700 correct final answers contain a reasoning error marked by its annotators. As a broader motivation (labeled by us as speculative): LLMs are computer programs with the same architectural limits as earlier software, and the places where theory proves that simple checks fail are concrete places to look for reasoning and safety failures.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.