Rethinking logic in AI: A novel benchmark inspired by polynomial analogue of Gandy's fixed point theorem
llm;logic;benchmark;Gandy's fixed point theorem
Yes
No ethics review needed.
The title starts very strongly: RETHINKING LOGIC IN AI. Are you actually doing that?

Abstract: The abstract seems to have redudant text
eg, 
Even advanced models like GPT-4 exexhibit significant biases in solving benchmark problems

and then 
even the most advanced GPT-4 models exhibit biased behavior while
solving recursive problems.

5 on the results of mathematical logic -> it is not very clear what you refer to here
The paper addresses a pertinent ptoblem

The proposal seems sound and allows for a number of parameters

The evaluation is interesting and includes both open and closed source systems.
The paper introduces a method to generate functions that will be evaluated by a LLM in order to study how LLLMs perform as interpreters\
Reading this work, I got the feeling that it may be too early for such in-depth analysis, we should first improve LLMs :). 

The paper does provide some insight on problems with bias, but the results seem quite independent of parameter variation. Again, raises the question of whether we are pushing the LLMs too hard?

Finally, do you consider the parameters representative of what the LLMs will find?

pg 6: being easy to verify in one’s mind -> that's an interesting point, the paper does not discuss this basic question much,

There are some typos, namely Eq?? in 3
Yes
No ethics review needed.
None.
It is interesting to study the capabilities of LLMs using mathematically defined objects.
The authors study the reasoning capabilities of LLMs by studying their capabilities to decide recursively defined properties of nested lists. They formulate the properties to be tested so that they are polynomial time testable. They implement a generator that generates these problem instances with varying complexity; pairs consisting of a nested list and recursively defined property. They consider two kinds of encodings of their problems to LLMs; inputs to conversational LMs and inputs to code completion LMs. They then compare the reasoning capabilities of different LLMs.

They found out that the LLMs they tested were not capable of deciding the recursive properties.
In summary, the authors study the capabilities of LLMs by studying how well they can decide recursively defined properties of nested lists. While to have understanding on the capabilities of LLMs is important, the paper itself seems to me more like a good student project to showcase the limits of the current capabilities of LLMs, than a research paper ready to be published. In particular, the main contribution of the paper is the idea to study capabilities of LLMs by inputing pairs consisting of nested lists and recursively defined properties of those lists, the task being to decide whether the list satisfied the properties given. The authors then test various LLMs on the inputs they generate.

The theoretical contribution of the submission is to consider recursively defined properties and inputs to decide, and the technical contribution is to generate these inputs and tabulate the results with respect to different LLMs. I do not think that either contribution of the paper suffices for a publication in a top general conference in machine learning.
Yes
No ethics review needed.
1) Why is the class of problems considered in this submission so relevant as to represent a benchmark for LLMs?

2) How does this contribution compare to the current state of the art?
1) The challenge of assessing precisely the reasoning capabilities of LLMs is extremely important to the development of LLMs themselves. This paper makes a contribution in this sense by introducing what looks like an interesting benchmark.
However, why the proposed benchmark is actually important is not developed enough in the submission.

2) The experimental evaluation is rather in-depth, with several important LLMs considered, both proprietary and publicly available.
This paper introduces a novel benchmark for evaluating the logical reasoning capabilities of Large Language Models (LLMs). 

The proposed approach involves generating [object, condition] pairs, where objects are nested lists of elements (for example, numbers) and conditions are expressed with recursive functions. The task of the LLM is to determine whether the object satisfies all conditions.
The source code of the benchmark is publicly available.

The main finding of the paper is that current state-of-the-art LLMs fail to reliably solve even the most straightforward cases, thus pointing to significant limitation in their logical reasoning capabilities.
1) The paper is only 8 pages long, two pages shorter than the page limit. 
It is not clear why the authors didn't include some of the material appearing in the appendix, for instance.

2) The authors define their class of problems through the Polynomial Analogue of Gandy’s Fixed Point Theorem (which I am not familiar with). However, it is not clear why this specific class is so important as to represent a benchmark for LLMs.

Also, the authors might consider to clarify the relation with standard propositional Boolean logic (which I assume is the non-nested version).

3) The related literature is not discussed at any length. It almost looks like there has not been any other effort to assess the reasoning capabilities of LLMs, including logic-based reasoning.
Yes
No ethics review needed.
The problem is prompted to the LLMs in the format of python code. Why not represent the problems using text? Were other representations considered to represent the problems?

Were there any further analysis performed on the results shown in Figure 1? Would simply negating the solution from GPT-4-turbo achieve 90%+ accuracy? Does a model getting the wrong answer 90% of the time mean it is consistently doing (wrong) reasoning internally?
The proposed dataset can be generated parametrically, which varies its difficulty level. 

The proposed dataset is difficult for existing LLMs. 

The dataset generators are well-defined.
This paper introduces a new benchmark dataset for evaluating the reasoning ability of LLMs, based on the PAG theorem. The problems in the dataset contain a theorem that returns boolean output based on a given nested list. The dataset is created using a condition generator and a probe generator to generate the theorems and the nested list instances respectively. The theorem and the assignment are represented in text as Python functions and lists. The paper then prompts LLMs to predict whether a theorem is satisfied or not by the given nested list, and finds that state of the art LLMs are unable to when prompted in a zero shot setting.
To me, the dataset is not strongly motivated. I agree that new reasoning benchmark datasets are important for LLMs, but why this specific dataset is needed is unclear. What is the advantage of this dataset over, for example, a set of problems that include SAT formulas in CNF and the set of assignments to the variables, where the LLM is asked to verify if the solution is valid?

It seems that the LLMs are only evaluated on this dataset using zero-shot prompting. Extensive literature has shown that LLM reasoning abilities can be significantly enhanced by chain-of-thought [1], tool-using [2], self-consistency [3] etc. Therefore, it is hard to draw a definitive conclusion on LLM reasoning abilities from zero-shot prompting results alone.

By representing the problem in Python code, the dataset is limited to evaluating LLM’s reasoning ability in the specific context of executing Python, which may not represent LLM’s reasoning ability in the general case. For example, by asking the conversational LLM to output the result of print(is_member_0(x)), the LLM needs to understand the Python syntax on top of the logic of whether x satisfies f or not.

[1] Wei, Jason, et al. "Chain-of-thought prompting elicits reasoning in large language models." 

[2] Schick, Timo, et al. "Toolformer: Language models can teach themselves to use tools." 

[3] Wang, Xuezhi, et al. "Self-consistency improves chain of thought reasoning in language models."
We introduce a benchmark revealing that even advanced LLMs like GPT-4 struggle with basic logical reasoning tasks
@inproceedings{
anonymous2024rethinking,
title={Rethinking logic in {AI}: A novel benchmark inspired by polynomial analogue of Gandy's fixed point theorem},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=mHx8JFURtn},
note={under review}
}
This paper introduces a novel benchmark for evaluating the logical reasoning capabilities of Large Language Models (LLMs), grounded in the polynomial analogue of Gandy's classical fixed point theorem. Drawing on concepts from mathematical logic, we design a parameterized set of recursive problems where the objective is for LLMs to predict the outcome of a Boolean function, achievable within a polynomial number of steps. By varying the parameters, we generate problem instances of differing complexity. Our experiments reveal that current state-of-the-art LLMs fail to reliably solve even the simplest cases, despite an effective deterministic algorithm existing. Notably, even advanced models like GPT-4 exhibit significant biases in solving benchmark problems. These findings highlight the limitations of modern LLMs as code interpreters, even in basic scenarios, and underscore the necessity for hybrid LLM/interpreter systems. Furthermore, they emphasize the importance of developing quantitative tests for reasoning, given the increasing reliance on LLM-based systems in decision-making applications.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
llm logic benchmark Gandy's fixed point theorem
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/81081b0335e17658e384400f214e6c096b4e35ec.pdf
datasets and benchmarks
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Rethinking logic in AI: A novel benchmark inspired by polynomial analogue of Gandy's fixed point theorem
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission