Evaluating Program Semantics Reasoning with Type Inference in System F F
Yifeng He, Luning Yang, Christopher Castro Gaw Gonzalo, Hao Chen · 2025
Read Evaluating Program Semantics Reasoning with Type Inference in System F F by Yifeng He, Luning Yang, Christopher Castro Gaw Gonzalo, Hao Chen (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-2509-23686.txt.
Introduction
Code benchmarks can reward a model that matches surface patterns instead of truly following program logic. Yifeng He and 3 co-authors built TF-Bench to test program semantics reasoning through type inference in System F. Verified transformations strip out natural language that carries no semantic weight, yielding a pure variant of the benchmark. Models must then reason from the code's formal structure alone.
State-of-the-art models struggled: the best, Claude-3.7-sonnet, reached only about fifty-six percent accuracy on the pure set. Two new metrics probe robustness and the value of test-time reasoning. The authors say the gaps mark where current models still fake understanding, and where work should go next.
Catalog record
| CREATOR | Yifeng He, Luning Yang, Christopher Castro Gaw Gonzalo, Hao Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-23686
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Evaluating Program Semantics Reasoning with Type Inference in System F F Yifeng He, Luning Yang, Christopher Castro Gaw Gonzalo, Hao Chen Abstract Large Language Models (LLMs) are increasingly integrated into the software engineering ecosystem. Their test-time compute (TTC) reasoning capabilities show significant potential for understanding program logic and semantics beyond mere token recognition. However, current benchmarks for code reasoning lack a formal, program-centric deductive framework to ensure sound evaluation, and are incapable of assessing whether models genuinely reason about program semantics or merely exploit superficial associations between natural language and code tokens. To bridge this gap, we introduce TF-Bench, a benchmark designed to evaluate LLM reasoning based on type inference in System F F , a task we refer to as program semantics reasoning . By employing verified transformations to remove semantically irrelevant natural language, we construct TF-Bench pure {}_{\text{pure}} , a purely semantics-driven variant of TF-Bench. Our analysis reveals substantial limitations in state-of-the-art LLMs, with the best-performing LLM (Claude-3.7-sonnet) achieving only 55.85 % 55.85\% accuracy on TF-Bench pure {}_{\text{pure}} . Additionally, we propose two novel metrics to assess robustness and the effectiveness of test-time reasoning, underscoring critical limitations in current LLM capabilities and highlighting essential directions for future research. 1 Introduction The ability to understand and write programs has become an important factor in evaluating the intelligence of large language models (LLMs) [ 1 , 2 , 3 ] . More recently, test-time compute (TTC), also referred to as learn to reason , has become a new scaling paradigm to further improve the performance of generative LLMs via reinforcement post-training [ 4 , 5 ] . These reasoning models show promising results in software-related tasks. However, popular tasks in code generation and understanding fail to fully reveal LLMs’ prowess at reasoning about program semantics, i.e. their ability to understand program flows and underlying logic. Hence, popular code generation benchmarks often fail to uncover differences between the training algorithms used to build reasoning LLMs. Previous work on program reasoning for LLMs often involves generating properties for code to satisfy [ 6 , 7 ] or predicting the execution behavior of the code [ 8 , 9 ] . However, these tasks require the LLMs to generate tool-specific properties or behaviors, failing to isolate reasoning capability from knowledge of specific downstream tasks. Furthermore, due to the lack of a clearly defined formal system within the programming language, it is difficult to attribute poor performance to a lack of reasoning capability. Therefore, to rigorously understand the fundamental reasoning capabilities of LLMs as an upstream evaluation, we need a benchmark that: 1. The oracle is well-defined in a formal deductive system, and the result can be produced and verified by the system. 2. The evaluation of program semantics reasoning can be conducted within the programming language itself, isolated from the knowledge requirement about specific downstream tools. Furthermore, natural language (NL) elements within code, such as comments and the names of identifiers, assist programmers in reading code. However, they do not affect how developers and compilers analyze the logic, data flow, and defects in the code. For instance, renaming functions and variables does not impact how the program operates or the outputs it generates. Previous work [ 10 ] showed that the performance of language models on these benchmarks can be heavily influenced by NL elements within code snippets. These NL elements are not related to the program semantics, and can often lead LLM-based approaches to misunderstand programs [ 11 , 12 ] . Program semantics ( e.g. , denotational, operational, and axiomatic) of programming languages describe program behavior, as viewed by the compiler. They are invariant to the NL components of programs. By contrast, a programmer’s understanding of a program is influenced considerably by its NL components. We call this the cognitive semantics of a program. The structural logic behind the programs depends on the program semantics, not the cognitive semantics. The gap between these two types of semantics often leads to bugs and security vulnerabilities in LLM-based software applications. We are not aware of any existing benchmark that addresses this gap in the ability of LLMs to reason about program semantics, a task we refer to as program semantics reasoning . As a first step, we use type inference, or predicting the type signature from function implementations, as a task in reasoning on program semantics. There are three main benefits of using type inference for this evaluation: 1. Type inference is grounded in System F [ 13 ] , which is a formal natural deduction system, providing a well-defined task to evaluate LLMs’ reasoning abilities. 2. Type signatures are unique and can be easily verified. For a provided task, there is only one correct signature, whose correctness can be verified by the Hindley-Milner algorithm [ 14 , 15 ] implemented in the compiler. 3. Type signatures can be inferred solely from provided dependencies (details are described in Section 3.1 ). We propose to use type inference as an upstream reasoning task, which is not affected by nor helped by the NL components, unlike downstream applications and generation tasks. We present TF-Bench, a novel evaluation benchmark for program semantics reasoning. We construct TF-Bench using function-level type inference in Haskell [ 16 ] for its strict type system with easy-to-understand syntax. 1 1 1 As similar to mathematical functions with little syntax noise, please see Appendix A . Haskell’s core language is based on System F [ 13 ] , which is parametric polymorphic, ensuring the diversity of tasks in the benchmark. In addition to System F , Haskell also supports ad-hoc polymorphism [ 17 ] (bounded overloading, System F_{<} [ 18 ] ), which is also included in TF-Bench for task diversity. Tasks in TF-Bench are self-contained with function dependencies explicitly provided, so we can remove NL pieces in the benchmark to construct TF-Bench {}_{\text{pure}} without losing the logic chain, making it sound to evaluate reasoning models without the influence of NL-contaminating tokens. Type inference is a form of natural deduction, which makes TF-Bench a naturally suitable benchmark for emerging reasoning LLMs. To the best of our knowledge, TF-Bench is the first work to introduce and address the problem of PL semantics reasoning. Our contributions 1 . We introduce TF-Bench and its NL-free variant TF-Bench {}_{\text{pure}} , a pair of novel benchmarks each containing 188 tasks for program reasoning. 2 2 2 https://github.com/SecurityLab-UCD/TF-Bench 2 . We comprehensively evaluate 64 LLMs with varying parameter sizes ( Section 4.3 ). Our findings indicate that on TF-Bench {}_{\text{pure}} , the leading API-access LLM, Claude-3.7-sonnet, only achieves 55.85\% accuracy. 3 . Based on the two-variant design of TF-Bench, we propose two novel evaluation metrics: semantic robustness ( Section 4.4 ) and reasoning effectiveness ( Section 4.5 ). These metrics are useful in understanding the effects of the applied TTC post-training methods in doing deductive reasoning about program semantics. 4 . We provide a detailed analysis of LLMs fine-tuned on code or math corpora ( Section 4.6 ). Our results suggest that LLMs fine-tuned on code tend to overfit NL cues, whereas those fine-tuned on math are more likely to solve the task through reasoning. 2 Background and Related Work 2.1 Learning to understand programs Large language models