acceptodds
Under review as a conference paper at ICLR 2027

Cusp: Evaluating reasoning on the boundary of solvability

Abstract

Language models have demonstrated notable progress on a variety of reasoning and mathematics tasks. We consider reasoning in the context of set theory and propose a benchmark for evaluating the ability of language models to reason about sets under constraints. We programmatically construct and verify our problem instances. Datasets in our benchmark comprise problem instances with minimally sufficient constraint sets that places them on the boundary of (unique) solvability. We evaluate the ability of language models to perform two separate tasks: (1) generate an assignment of elements to the sets in the problem such that all constraints are satisfied and (2) state how many solutions exist to the problem. We find that on the boundary of solvability, accuracy on these reasoning tasks can vary substantially depending on two levers that we pull simultaneously: the complexity of the problem instance and the pragmatics of the prompt. Some of the behaviors we observe are consistent with reports of short-cutting in earlier literature, while others are novel and warrant further investigation.

Primary area:
datasets and benchmarks
Keywords:
LLM evaluation, benchmark, reasoning, constraint satisfaction, set theory, shortcut learning, solvability, diagnostic evaluation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_BhZyOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Cusp evaluates finite-set constraint reasoning through assignment recovery and solution-space classification. It generates constraints from sampled sets, prunes them while checking uniqueness, and distinguishes a retention sweep from derived deletion-tested minimal cores. Evaluations vary constraint structure, universe size, inference settings, and prompt framing. The strongest controlled prompt result is a cue-by-answer-space interaction: asserting uniqueness changes set accuracy by -0.4 percentage points when an assignment is required and +7.8 points when a non-unique response is permitted. The primary classification result excludes the surface-detectable unsatisfiable class and reaches 78.6% on UNIQUE versus MULTIPLE. The benchmark offers useful tests of set reasoning, but its added value over existing benchmarks, relevance to practical tasks, and explanations of model behavior need stronger support.

Critical strengths
  1. Cusp tests whether models can recover sets and judge whether a solution is unique. Its solver-verified instances and deletion-tested minimal cores extend the set-operation tasks in SetLexSem and the CSP puzzles in ZebraLogic.
  2. The paper checks earlier labeling errors, compares prompts on the same instances, and tests added information against repetition and padding. It also examines reasoning budgets and separates the harder uniqueness decision from easy contradiction detection.
Critical weaknesses
  1. The contribution mainly combines ideas in synthetic constraint benchmarks, solver verification, and prompt variation. Methodological novelty is limited, and the paper does not sufficiently establish what useful diagnosis this combination adds beyond benchmarks such as SetLexSem and ZebraLogic.
  2. Cusp measures single-shot reasoning over synthetic set constraints, but its relevance to practical mathematical work or general reasoning has not been established, the benchmark’s practical significance remains uncertain.
  3. The paper attributes prompt effects to whether models commit to an answer and interprets scaling failures as evidence about their solving strategies. But changes in output accuracy and refusal rates do not establish these internal mechanisms or rule out other explanations.
  4. All evaluated systems are accessed through APIs, including the open-weight models. No locally deployed checkpoint is evaluated. This may cast doubt on the reproducibility of this paper.
  5. The presentation is overly defensive, using repeated caveats, corrections to earlier interpretations, and future plans that interrupt the main argument explanation. Also, too much space is spent explaining the limits.
  6. The reported reversal between GPT-5.4 and o4-mini after adjusting reasoning effort shows that these rankings depend on configuration. Therefore, accuracy should be compared alongside token use and output limits.
Questions for authors
  1. I suggest checking whether the low-retention and uniqueness errors persist when models can run code to verify their answers. A representative subset would help assess the relevance of these failures to practical use.
  2. With base instances and inference settings held fixed, what additional failure patterns do deletion-tested minimal cores reveal compared with the retention sweep?
  3. For the -0.4 and +7.8 percentage-point cue effects in Section 5, please report how individual instances move between correct assignments, wrong assignments, and non-unique responses. These transitions would help assess the claim that computation stays unchanged.
  4. Section 5 would be clearer with the matched-instance comparison as its main result and the repeated qualifications consolidated around it, since the original Implicit/Explicit comparison also changes the constraint regime.
4 comments

We thank the reviewer for engaging with the paper down to the appendices. We acknowledge the point on presentation: the repeated caveats, corrections of earlier interpretations and etc. The next revision will state each qualification in one place, and keep the main text on the results. Below is answer to each of your question:

Q1 (code execution). We ran this check: when a model writes a z3 program instead of answering in context, the frontier models recover every core they had failed (Sonnet 4.6 25/25, Opus 4.6 183/183, all constraints encoded correctly), Haiku 4.5 recovers 84% (359/427) and Llama 3.3 70B 52% (398/760), the remainder being program faults (crashes, syntax errors, mis-encoded constraints) rather than reasoning errors, so the low-retention and uniqueness failures measure in-context composition and commitment, which a solver call removes. This complements the global response, where Z3 search statistics (decisions, conflicts, propagations) explain almost none of the variance in model accuracy (R2=0.05R^2 = 0.05) while what the constraints determine explains half of it (R2=0.50R^2 = 0.50): what is hard for a complete solver is not what is hard for these models, and handing the models the solver removes exactly the step they fail.

Q2 With base instances, model and inference settings fixed, the cores expose three failure patterns that the sweep does not.

Pattern 1. The failure moves from reading a constraint to inference by composition. We score a wrong answer as a reading failure when it misplaces an element that a single constraint already fixes (the first-order must/cannot rules), and as a composition failure when every single-constraint inference is right and the error lies only on elements that two or more constraints determine jointly.

Example (App. A.2), U=0,1,2,4,7,10,13,21,25,29,33,34U = {0,1,2,4,7,10,13,21,25,29,33,34}:

ConstraintType
A∖B=0,2,13,33A \setminus B = {0, 2, 13, 33}value
∣A∪B∣=8\lvert A \cup B \rvert = 8size
A,△,C=0,1,2,4,13,21,25,33A ,\triangle, C = {0, 1, 2, 4, 13, 21, 25, 33}value
∣B,△,C∣=8\lvert B ,\triangle, C \rvert = 8size
SetOpus 4.6Ground truthHow Opus got thereVerdict
BB7,10,29,34{7,10,29,34}7,10,29,34{7,10,29,34}reads 0,2,13,33∉B0,2,13,33 \notin B (c.1) → derives ∣B∣=4\lvert B \rvert = 4 (c.1+c.2) → guesses "try 7,10,29,34{7,10,29,34}" → checks c.4 ✓right
CC1,4,21,25{1,4,21,25}1,4,21,25{1,4,21,25}from c.1 + c.3right
AA0,2,7,10,13,29,33,34{0,2,\mathbf{7,10},13,\mathbf{29},33,\mathbf{34}}0,2,13,33{0,2,13,33}the same guess put the four into AA; c.3 never re-checked4 extra, all from BB

On the sweep instance of comparable size (App. A.3) every set is read off two or three value constraints and all are correct. A no-search propagation baseline fully solves 33.6% of the sweep but 2.6% of the cores; on the cores, must/cannot accuracy stays above 92% and second-order accuracy at 98–100% while can elements fall to 86–87% for mid-tier models; 98.8% of wrongly included elements belong to another target set.

Wrong answers on the 891 cores (Implicit prompt), by failure type:

ModelAccset\text{Acc}_{\text{set}}WrongCompositionReadingNo answer
o4-mini87.511610 (9%)1 (1%)105 (91%)
Opus 4.686.8197163 (83%)20 (10%)14 (7%)
Sonnet 4.687.4174107 (62%)19 (11%)48 (28%)
Sonnet 478.6288232 (81%)25 (9%)31 (11%)
Haiku 4.564.2494354 (72%)73 (15%)67 (14%)
Llama 3.3 70B34.4776437 (56%)323 (42%)16 (2%)

What the cores add, same bases and same prompt:

ModelReading failures: sweep → coreComposition failures: sweep → coreSame-prompt Accset\text{Acc}_{\text{set}} drop
Opus 4.68 → 20 (+12)50 → 163 (+113)−10.1-10.1 pp
Sonnet 4.611 → 19 (+8)39 → 107 (+68)−9.2-9.2 pp
Sonnet 419 → 25 (+6)104 → 232 (+128)−13.4-13.4 pp
Haiku 4.584 → 73 (−11-11)184 → 354 (+170)−17.9-17.9 pp
Llama 3.3 70B300 → 323 (+23)289 → 437 (+148)−20.7-20.7 pp
o4-mini4 → 17 → 10−9.9-9.9 pp (truncations 16 → 105)

The added composition failures almost all violate a value constraint

ModelComposition failuresBreaks value constraints onlyBreaks size onlyBreaks both
Opus 4.650 → 163 (+113)21 → 123 (+102)5 → 12 (+7)24 → 27 (+3)
Sonnet 4.639 → 107 (+68)22 → 90 (+68)3 → 9 (+6)14 → 8 (−6-6)
Sonnet 4104 → 232 (+128)41 → 144 (+103)6 → 7 (+1)57 → 80 (+23)
Haiku 4.5184 → 354 (+170)61 → 197 (+136)17 → 25 (+8)106 → 131 (+25)
Llama 3.3 70B289 → 437 (+148)43 → 149 (+106)21 → 22 (+1)225 → 266 (+41)

The pattern is guess-and-check with the check skipped: a cardinality should decide the open elements, the model resolves them by guessing, and commits without re-verifying an explicit value constraint the guess breaks.

Continue to the answer to Q2:

Pattern 2. Spurious refusal. When the prompt offers NO_UNIQUE_SOLUTION, models take it on instances that have exactly one solution, sometimes after the trace has already derived that solution. Example, U=0,4,8,11,12,15,16,21U = {0, 4, 8, 11, 12, 15, 16, 21}:

#Constraint
1C∖A=0,12C \setminus A = {0, 12}
2B∪C=0,4,11,12,16B \cup C = {0, 4, 11, 12, 16}
3B∖A=4,11,16B \setminus A = {4, 11, 16}
4∣A∪B∣=6\lvert A \cup B \rvert = 6

Ground truth: A=8,15,21A = {8, 15, 21}, B=4,11,16B = {4, 11, 16}, C=0,12C = {0, 12}. Opus 4.6's trace:

StepReasoning traceStatus
14,11,16∈B4, 11, 16 \in B and ∉A\notin A; 0,12∈C0, 12 \in C and ∉A\notin A; so A⊆8,15,21A \subseteq {8, 15, 21}correct
2C∖A=CC \setminus A = C, so C=0,12C = {0, 12}correct
3"BB contains 4,11,16{4, 11, 16} and possibly some of 0,12{0, 12}"wrong: 0∉A0 \notin A, so 0∈B0 \in B would put 00 into B∖AB \setminus A, violating c.3; B=4,11,16B = {4, 11, 16} exactly, and ∣A∪B∣=6\lvert A \cup B \rvert = 6 then forces A=8,15,21A = {8, 15, 21}
4"A=8,15,21A={8,15,21}, B=4,11,16B={4,11,16}, C=0,12C={0,12} works"the correct answer, stated in full
5"A=8,15A={8,15}, B=0,4,11,16B={0,4,11,16}, C=0,12C={0,12} also works"violates c.3 (B∖A=0,4,11,16B \setminus A = {0,4,11,16})
6<solution>NO_UNIQUE_SOLUTION</solution>spurious refusal

Refusals on the 891 cores (Explicit prompt, neutral cue) whose trace had already stated every set correctly:

ModelRefusalsDerived all sets, then refused% of refusals
Opus 4.61552818.1%
Sonnet 4.62255022.2%
Sonnet 4.5381128.9%
Sonnet 4951313.7%
Haiku 4.51241512.1%
Gemini 2.5 Flash51815.7%
Gemini 2.5 Flash-Lite600.0%
Mistral Large661162.4%
Qwen3 32B5411.9%
Llama 3.3 70B732101.4%
Llama 4 Maverick164127.3%

The sweep cannot show this: with about 59 constraints a redundant value constraint removes the doubt, and under the Implicit prompt the sweep traces voice uniqueness doubt on 0–1 of 891 instances for the Anthropic models.

Pattern 3. Sensitivity to which core is shown. The same hidden answer has many exactly-minimal cores, and which one the prune order leaves decides the outcome. Illustration for the answer A=0,2,13,33A={0,2,13,33}, B=7,10,29,34B={7,10,29,34}, C=1,4,21,25C={1,4,21,25} (36 true constraints):

Core 1 (App. A.2)Core 2 (illustrative, solver-verified unique and minimal)
ConstraintsA∖B=0,2,13,33A \setminus B = {0,2,13,33}; ∣A∪B∣=8\lvert A \cup B \rvert = 8; A△C=…A \triangle C = {\ldots}; ∣B△C∣=8\lvert B \triangle C \rvert = 8A∖B=0,2,13,33A \setminus B = {0,2,13,33}; B∖C=7,10,29,34B \setminus C = {7,10,29,34}; C∖A=1,4,21,25C \setminus A = {1,4,21,25}; ∣A∩B∣=∣B∩C∣=∣A∩C∣=0\lvert A \cap B\rvert = \lvert B \cap C\rvert = \lvert A \cap C\rvert = 0
Unique / minimalyes / yesyes / yes
Solving needscomposition (guess-and-check)reading only (disjoint ⇒ A∖B=AA \setminus B = A)
Opus 4.6wrongright

In the prune-order study (100 bases × 10 independently pruned cores) model rankings are identical across orders (Spearman 1.00) while single-instance outcomes flip (accuracy ICC 0.06–0.16). Restricting to bases whose sweep instance the model solved:

ModelSweep solved (bases)Cores all rightCores mixedCores all wrongMean cores right / 10
Opus 4.6178909.1
Haiku 4.51501505.1
Qwen3 32B80803.5

Within those mixed bases we asked whether the failing cores are measurably harder than the passing cores of the same base (compared with the passing cores' median): readability = share of sets propagation alone fixes; value share = share of value constraints; open decisions = element–set decisions no single constraint fixes.

ModelBasesWrong coresReadability: harder / same / easierValue shareOpen decisionsFailure types (composition / reading / no answer)
Opus 4.6112040% / 25% / 35%45% / 25% / 30%55% / 5% / 40%18 / 1 / 1
Haiku 4.51910263% / 16% / 22%49% / 23% / 28%56% / 4% / 40%72 / 22 / 8
Qwen3 32B128039% / 25% / 36%55% / 22% / 22%38% / 4% / 59%38 / 19 / 23

The failing cores are not systematically harder on any of the three measures (within-base R2≤0.05R^2 \leq 0.05 for Opus and Haiku), and 90% of Opus's failures on them are composition failures. The outcome depends on which minimal subset the model sees, not on a measurable difficulty of that subset. This brittleness is itself a boundary finding and the reason the paper restricts itself to aggregate claims on the cores.

Continue to question 3 and 4:

Q3: We thank the reviewer for asking this question, as the data support our argument that pragmatics are relevant to the evaluation of language models on reasoning tasks. As shown in the transition probability matrix below, the presence of the cue that the problem is uniquely solvable results in 35% of previously-wrong responses to become correct, and 71% of previously-refused responses becoming correct. The statistically significant changes in accuracy are due to the previous refusals becoming either correct or wrong are shown in bold.

neutral cue → asserted cueCORRECTWRONGREFUSE
CORRECT (5,462)4,932 (90.3%)455 (8.3%)75 (1.4%)
WRONG (1,364)479 (35.1%)874 (64.1%)11 (0.8%)
REFUSE (910)648 (71.2%)213 (23.4%)49 (5.4%)

Percentages are calculated within rows; counts are pooled over nine models.

  • Significant at p<0.001 across three pairwise likelihood-ratio tests comparing each transition with its reverse (df=1). CORRECT ↔ REFUSE: G²=520.47; WRONG ↔ REFUSE: G²=222.78. The unmarked off-diagonal pair is not significant (CORRECT ↔ WRONG: G²=0.62, p=0.43)

Q4 (structure of Section 5). We agree and will restructure Section 5 as you suggest: the matched-instance factorial becomes the main result, the Implicit/Explicit aggregate becomes the motivating observation with its regime difference stated once, and the qualifications are consolidated around it.

Every new number above was computed from artifacts that are already in the public release, without any new model runs. With Section 5 restructured as you propose, we would be grateful if you would reconsider your assessment.

Dear Reviewer BhZy,

Thanks for your time and effort in reviewing our paper. As the author-reviewer discussion period will end in 1 day, we gently request that you read the rebuttal and check if your concerns are addressed. Thanks again for your time and help in improving the quality of our paper.

Regards from authors.

Reviewer_gVayOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces CUSP, a benchmark for evaluating language models on finite-set constraint reasoning. It constructs instances from known assignments and uses solver-based checks to generate uniquely solvable constraint subsets, ranging from redundant systems to deletion-minimal cores. Models are evaluated on assignment recovery and solution-space classification. Experiments vary constraint retention, constraint types, universe size, and prompt framing. The reported results show sensitivity to problem structure, a separation between assignment and uniqueness-classification performance, and an interaction between uniqueness cues and the availability of abstention. Additional controls examine redundancy, text length, and inference configuration.

Critical strengths
  1. Controlled and verifiable construction. Programmatic generation, deterministic rendering, and solver-based checks provide a reproducible framework for studying constraint reasoning. Preserving unique solvability while modifying the available constraints enables useful paired comparisons.

  2. A concrete finding about prompt-sensitive answer submission. The reported uniqueness-cue effect is near zero when an assignment is required but positive when abstention is available. This interaction shows that response protocols can materially affect accuracy and supports distinguishing incorrect assignments from incorrect non-uniqueness responses.

Critical weaknesses
  1. The incremental diagnostic value remains unclear. Existing benchmarks such as ZebraLogic and SATBench already investigate controlled constraint reasoning and complexity-dependent failures. Many CUSP findings—lower accuracy with larger universes, fewer redundant constraints, or more indirect information—are compatible with ordinary changes in task difficulty. The paper should more clearly establish which findings provide additional understanding of model reasoning and why they are consequential beyond this particular task.

  2. The mechanistic interpretations exceed the evidence. Unique solvability does not imply equal computational difficulty: removing redundant constraints can increase the required derivation, while explicit membership constraints simplify inference compared with cardinality constraints. Likewise, fixed constraint count does not control representation length, membership tracking, or output burden as the universe grows. Consequently, these accuracy differences do not sufficiently identify shortcut reliance or distinguish enumeration from constraint propagation. Although the paper qualifies some interpretations, stronger claims remain central to its motivation and conclusions.

Questions for authors
  1. What is the strongest substantive insight enabled by CUSP beyond existing CSP evaluations, particularly ZebraLogic and SATBench? Please identify the corresponding result and explain why it provides additional diagnostic information rather than another measurement of task difficulty.

  2. What evidence supports interpreting the observed performance differences as shortcut reliance or differences in solving strategy? In particular, how do the existing controls distinguish these explanations from increased inference, membership-tracking, or output token demands as the problems become larger or less redundant?

1 comment

We thank the reviewer for the two questions; both are answered in the global response. In brief: CUSP's strongest insight beyond ZebraLogic and SATBench is that solving an instance and knowing its solution is unique are separate capabilities, and the existing length, padding and ∣U∣|U| controls together with the new random-forest analysis (operator semantics R2=0.50R^2 = 0.50 vs. Z3 search effort R2=0.05R^2 = 0.05) show that the failures track what the constraints determine rather than how long or search-heavy the problem is; we will reword the remaining strategy-flavored phrases as behavioral statements.

Reviewer_Ad4oOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

CUSP evaluates language-model reasoning on finite-set constraint problems near the boundary of unique solvability. A solver-guided procedure removes constraints to obtain minimal or near-minimal sufficient systems. The benchmark includes an Assignment task, which requires recovering the sets, and a Classification task, which asks whether a system has one, multiple, or no solutions. The experiments distinguish local deduction, global consistency reasoning, and the decision to commit to an answer.

Critical strengths
  1. The experimental controls are careful, and the authors revise claims when the evidence requires it. They conduct a two-solver audit, identify confounding between constraint count and retention rate, and add matched-instance prompt experiments. They also clearly disclose the surface shortcut in the unsatisfiable examples.
  2. The benchmark offers useful diagnostic control. Minimal cores, universe size, the balance of value and cardinality constraints, and the must/cannot/can partition provide several ways to investigate reasoning bottlenecks.
  3. The gap between solving and recognizing uniqueness is interesting. Even when Assignment accuracy is near perfect, the best UNIQUE-versus-MULTIPLE classification accuracy is only 78.6%. Finding a solution therefore does not imply understanding the solution space.
Critical weaknesses
  1. Test-time computation is not fully comparable across models. Provider-default reasoning settings differ, and the 8,192-token limit may affect models that require longer searches. Deliberate abstention, reasoning failure, and output truncation should be separated more clearly.
  2. The unsatisfiable examples are too easy to identify through surface rules. The current 900 examples contain directly contradictory value constraints, leaving most of the substantive classification difficulty in distinguishing UNIQUE from MULTIPLE.
Questions for authors

If models are allowed to write or execute Python/Z3 programs, do the main errors shift to formalizing the constraints correctly? Have the authors considered evaluating this setting?

1 comment

Thank you for the thoughtful review, and especially for highlighting the assignment-vs-uniqueness gap. That is the finding we most hoped a reader would take away.

Regarding your question: while the intent of CUSP is to stress test the inherent capabilities of language models, we have run tasks that allow writing and execution of Z3 in Python, and we observed improvement in task performance. Because language models are known to be good at translating information into a structured format (essentially, in a traditional NLP setting, a form of slot filling along with a context-free grammar), we are unsurprised at this result.

We have evaluated this setting. Four systems from two providers (Sonnet 4.6, Opus 4.6, Haiku 4.5, Llama 3.3 70B) receive the identical universe and constraint text and are asked to write one self-contained Python program that uses z3 to model each set as a subset of UU (one Boolean per set-element pair), encode exactly the listed constraints, enumerate up to two solutions, and print the assignment, MULTIPLE, or NO_SOLUTION. We execute each program in a restricted sandbox and score its output against solver ground truth. Every row is paired with the same model's in-context answer on the same instance from the paper's runs (Opus, Haiku and Llama on Bedrock at temperature 0; the Sonnet 4.6 pilot through the Anthropic CLI). In total, 2,000 programs.

Assignment on exactly-minimal cores (task-exact).

ModelRowsIn-contextz3 programResidual: crash / syntax / wrong encoding
Sonnet 4.625 own failures0/2525/250 / 0 / 0
Opus 4.6183 own failures0/183183/1830 / 0 / 0
Opus 4.6100 random80/100100/1000 / 0 / 0
Haiku 4.5427 own failures0/427359/427 (84%)38 / 3 / 27
Haiku 4.5100 random52/10082/10010 / 2 / 6
Llama 3.3 70B760 own failures0/760398/760 (52%)113 / 16 / 233
Llama 3.3 70B100 random16/10057/10017 / 1 / 25

Analysis: Do the errors shift to formalization?

For the frontier models the errors do not shift to formalization. They disappear. Sonnet 4.6 and Opus 4.6 encode every constraint correctly on all 208 cores they had failed in-context and on 100 random cores. Writing the program requires reading every constraint, so the in-context failures were not failures to understand the constraints. What the solver call removes is the in-context assembly of local inferences into one consistent assignment, and the decision to commit to it. That is the capability CUSP measures, and the one a system without a solver still needs when deciding whether a specification is under-determined.

For weaker models, yes, and the share grows as the model gets weaker. Haiku 4.5 recovers 84% of its failures; the rest are program faults (crashes from misused z3 calls, 9%; encodings that over-constrain the instance so z3 reports NO_SOLUTION or MULTIPLE, 6%; syntax, 1%). Llama 3.3 70B recovers 52%; the other 48% are wrong encodings (31%), crashes, often on invented z3 functions such as z3.Equals (15%), and syntax errors (2%). On classification Llama does worse with the tool than without, because a broken program replaces a correct guess.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Global Response

We thank the reviewer for their insightful comments and questions. The reviewer asked about the contributions of CUSP in relation to ZebraLogic and SATBench.

Each benchmark evaluates language model reasoning under constraints on problems of varying complexity. ZebraLogic controls search complexity, SATBench varies the clause count, and CUSP varies the number of sets NN, the universe size ∣U∣|U|, the overlap OO, the constraint type, and the fraction RR of constraints from the complete pairwise set that the task description provides. We created CUSP to support more thorough diagnosis and to distinguish more failure modes. ZebraLogic problems assume that a unique solution exists, and SATBench collapses problems with one or multiple solutions into a single category (SAT). CUSP, by contrast, measures both whether a model can produce the correct assignment and whether it can state whether that assignment is uniquely determined. The gap between these abilities is large. The best models reach about 97% accuracy on the Assignment task, but no model exceeds 78.6% on UNIQUE versus MULTIPLE classification, against a 51.9% majority-class baseline. CUSP also shows that language models perform worse when a higher proportion of the constraints are size constraints, such as ∣A∪B∣=5|A \cup B| = 5, even though every Assignment problem remains uniquely solvable. Among these three benchmarks, only CUSP analyzes how performance varies with constraint composition, revealing behavior consistent with models relying on constraints that name elements directly.

CUSP also tests prompt pragmatics, an issue that matters for real-world deployment of language models and that neither ZebraLogic nor SATBench examines. On the same 891 uniquely solvable minimal problems, telling the model that there is a unique solution has essentially no effect when it must provide an assignment (−0.4-0.4 pp), but improves accuracy by +7.8+7.8 pp and reduces refusals by 10.010.0 pp when it is allowed to answer that no unique solution exists. With the cue, models refused less often and supplied more correct assignments, while the number of wrong assignments changed little. This reveals an undesirable sensitivity to prompt pragmatics. Without an explicit statement of uniqueness, models refuse problems that have exactly one solution, and the cue changes whether they commit to an answer rather than the answer they compute.

A key virtue of the approach we take in CUSP is that we characterize problem difficulty as a function of operator semantics. The analysis of the information provided by the different value and size constraint set operators, which elements a single operator fixes on its own, which decisions remain open until several operators are composed, and which can only be settled through a cardinality, is a better predictor of difficulty given a problem instance than are the Z3 statistics that, e.g., ZebraLogic characterizes complexity by Z3 conflict count together with search-space size; SATBench varies clause count rather than solver statistics, which corresponds to our constraint-count knob. That this is true can be seen in the following table, which lists the feature importance of a Random Forest regression model trained to predict the average accuracy across models:

Due to the characters limitation, put the table in next Global Response

AuthorsOpenReview ↗

Global Response 2

The feature importance table, continue to previous global response

FeatureFamilyImportanceρ\rho
n_pairs_covered (distinct set pairs that have at least one constraint)constraint mix / graph0.145−0.40-0.40
n_elements_in_multiple_sets (elements of UU belonging to ≥2\geq 2 target sets)solution shape0.125−0.48-0.48
mean_pairwise_jaccard (average ∣A∩B∣/∣A∪B∣\lvert A \cap B \rvert / \lvert A \cup B \rvert over target-set pairs)solution shape0.090−0.36-0.36
input_tokens (prompt length in tokens)prompt0.068−0.48-0.48
set_size_std (standard deviation of target-set sizes)solution shape0.054−0.39-0.39
prompt_chars (prompt length in characters)prompt0.046−0.47-0.47
open_decisions_after_second_order (element–set decisions not fixed by the first- or second-order inference rules)propagation0.035−0.26-0.26
open_decisions_first_order (decisions not fixed by any single constraint)propagation0.028−0.27-0.27
n_size_dependent_decisions (decisions the value constraints alone leave open; a size constraint must settle them)search-required0.021−0.16-0.16
Z3 propagations, uniqueness proofZ3 statistics0.016−0.14-0.14
Z3 propagations, totalZ3 statistics0.016−0.14-0.14
Z3 propagations, find solutionZ3 statistics0.010−0.13-0.13
Z3 decisions, uniqueness proofZ3 statistics0.010−0.11-0.11
Z3 conflicts, find solutionZ3 statistics0.008−0.09-0.09
Z3 conflicts, uniqueness proofZ3 statistics0.007−0.11-0.11
Z3 decisions, totalZ3 statistics0.006−0.10-0.10
Z3 decisions, find solutionZ3 statistics0.006−0.10-0.10
Z3 conflicts, totalZ3 statistics0.005−0.10-0.10
# symmetric-difference constraints (value + size)operator type / count0.009−0.35-0.35
# symmetric-difference value constraintsoperator type / count0.007−0.32-0.32
# intersection / difference / union constraintsoperator type / count0.006 / 0.006 / 0.004−0.03-0.03 / −0.26-0.26 / −0.05-0.05
share of value / size constraintsoperator type / count0.004 / 0.004+0.06+0.06 / −0.06-0.06
# value constraints / # size constraintsoperator type / count0.003 / 0.002−0.37-0.37 / −0.22-0.22
per-type counts (∩\cap, ∪\cup, ∖\setminus, △\triangle ×\times value, size)operator type / count0.002–0.004 each
# subset / superset constraintsoperator type / count0.000
Other<0.02< 0.02 each

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.