The Ability of Large Language Models to Evaluate Constraint-satisfaction in Agent Responses to Open-ended Requests

In general, this paper would benefit from substantially more time, a clearer focus (is it aiming to be a benchmark or a validation framework?), and a more carefully constructed and relevant dataset. In its current form, it feels far from complete, and I cannot recommend it for publication. I'll do my best to constructively break down why I believe this:

The premise of the paper is valid and asks an important question: can LLMs be useful as automatic constraint satisfaction verifiers for LLM responses to user queries? The current direction has promise for making a useful contribution to answering this question, but only if much more is added.

1. The paper raises many immediately relevant questions but dismisses them as further work throughout the body of the work (lines 158, 352, 433, 447, 455). This "further work" includes significant amounts of analysis that I believe should actually be in the main results of this paper, especially the F1 score analysis (line 158) and examining intermediate numerical values rather than just final boolean evaluations (line 447).
2. GPT-4o succeeds on over 97% of all problems in the dataset, thus saturating it. If this were a benchmark which was a well-validated representation of the domain it claimed to examine, this could be taken as evidence that this model is already sufficient for the task of evaluating constraint satisfaction in responses to user queries. However, as the authors themselves admit, this is a deliberately simplified dataset: only one constraint is evaluated at a time, and only the simplest kinds of arithmetic constraints are represented. A more useful evaluation set would either provide significant evidence that the current state of the art is sufficient for the task or would highlight where and how SoTA currently fails, thus giving potential directions for improvement (whether train time or via inference-time augmentations).
3. The error analysis is unclear and incomplete. The biggest category by far is "other." The classification of errors is confusing: counting is considered a "reasoning" task, while multiplication (a procedure that, in a sense, generalizes counting) isn't. In general, the definition of reasoning here seems both very broad and inconsistent. Why is information extraction a reasoning task? For clarity, I would recommend removing the "reasoning" label entirely from Table 2 and its associated analysis paragraphs.
4. As the authors mention in the introduction, there have been many prior benchmarks and analyses that have looked at the same LLM abilities as those being tested here. The fact that the generation being evaluated by the LLM was in response to a "NORA" prompt doesn't fundamentally change the nature of the benchmark questions, as all of them do have one right answer (either "satisfiable" or "unsatisfiable"). This is especially true given that the full dataset was automatically generated rather than sourced from a real setting.
5. The dataset presented is too small and irrelevant. While the authors claim that it is "difficult" and "realistic," it is (as mentioned) already saturated, and no justification is provided for its realism. Currently it consists of a handful of very small artificial domains and uses an LLM as a user proxy but does not attempt to examine the validity of this use. A much more useful dataset would consist of actual user requests "in the wild" together with a selection of LLM generations (ideally across various models). At the very least, any benchmark purporting to answer the questions this paper is interested in should validate whether its benchmark is reflective of the sorts of queries and constraints LLMs are likely to encounter in practice.
6. The paper's focus is also unclear. The introduction mentions an automatic evaluation framework for LLMs tasked with constrained query generation and presents a figure, but this framework is not mentioned in the body of the paper. Multiple pieces of this system are not described in detail: What is the scoring system? What is the intended role of this system? For example, is the generation model reprompted if the evaluation comes up negative (or just has too low a score? in which case how is the cutoff calculated?)? If the paper is meant to be a benchmark paper, then it is unclear what the purpose of describing the framework is, unless it is modified and expanded on to create something like a living benchmark which grows with more queries or similar. If the framework is meant as a standalone contribution, then the paper must include not only further description but also further analysis of it, as well as evaluations of whether and how much it improves performance.

Nitpicks/Typos

1. The paper introduces a number of new (nonstandard) acronyms. In particular, WOV is used only three more times after it is introduced. This makes the paper harder to read. It would be clearer if these terms were spelled out each time.
2. Line 52: while the proposed benchmark does seem to have well-defined constraints (I haven't seen the prompts), the use case it purports to model often will not. Non-arithmetical constraints which may seem at first blush to be objective and well-defined may not fully be. The example the authors give "a 3-day meal-plan with no meat products" arguably has this property. Must a 3-day meal plan include three meals a day? Does fasting for three days satisfy the requirements? Which definition of meat are we using? Does fish count? Do insects? Does lab-grown meat count? E.g. the state of Missouri required "meat" to be derived from "harvested production livestock or poultry," which would answer no to all three of the meat questions. In general, polysemanticity and linguistic ambiguity makes it very difficult to make strong claims about whether constraints are truly well-defined. If the authors wish to retain this aspect of their analysis, I think it is important that they discuss these issues, and whether and to what extent well-defined, objective, and verifiable criteria exist beyond mathematical tasks.
3. Line 105: "The dataset if available at blinded for submission." (Typo)
4. Line 167-168: "generate the text in all stages decribes next:" (Typo)
5. Line 298: The authors claim that the problems "can be seen" as "elementary school level," but provide no justification for why this is true or why it matters. It is well-known that LLMs fail on simple grade school tasks like multiplication (even with CoT/scratch space), but can score highly on some graduate level exams. Evaluations and rankings based on approximately equivalent human school level do not seem particularly meaningful for these systems.
6. Line 432: "composed of very large tokens" should be "composed of very large numbers of tokens"

Weaknesses:

1. Some parts of the writing are unclear.
2. There are too many manual steps involved in dataset generation.
3. The dataset is relatively small.

I am following the introduction of the dataset, which is a non-trivial amount of work and nicely contributes to the literature and community. This is all great. What is less clear to me is 1) the high-level motivation behind doing this, and 2) the ultimate path this might take our understanding further.

Specific to the evaluation dataset, as noted by the authors, GPT4o achieves %97+ accuracy. It is not clear how much further this can be improved (I assume there will always be some data uncertainty etc.) and what value remains. This is quite important if this dataset is to be serving as a "benchmark". This might not be the case here.
I understand that experiments rely on LLMs only but I would have liked to see a comparison with an LLM with tools access as another additional baseline. Some of the steps required such as counting, arithmetic, summation, etc. are clear candidates for tool usages. The paper claims that most errors are due to reasoning rather than calculation (which I tend to agree) but still an LLM with a tool is an immediate baseline to include in experiments. I wonder if that would open-source LLMs, which are trailing behind GPT, to close the gap.

• Most modern LLMs do fairly well on arithmetic reasoning problems and the results in table 1 aren't actually surprising. Therefore, I think the proposed ACS dataset may be too easy for constraint satisfaction task considered.