CS Paper Radar

Evaluating SAT Solver Metrics as Predictors of Human-Perceived Nonogram Difficulty

Changdao He, Yibing Ju, Jonathan Calver, Alice Gao

cs.HC cs.AI ·submitted 2026-08-24 14:24 UTC · v1

Abstract

Algorithmic solver effort is often assumed to align with perceived puzzle difficulty, but this assumption is rarely tested against human solving data. We evaluate this assumption for Nonograms, a popular logic puzzle similar to Sudoku in which numeric clues along each row and column determine a unique solution grid. We formulate Nonograms as a constraint satisfaction problem and solve them using existing SAT solvers. We then conduct a user study in which we collect data on both participant interactions and reported difficulty. We find that neither participants' reported difficulty nor their behavioural signals correlate meaningfully with SAT solver metrics; however, we find evidence that expertise moderates the relationship between solver metrics and reported difficulty. In this process, we uncover distinct, recurring solving strategies that indicate human preference for complex propagation, diverging from solver-measured complexity.

Comment
16 pages, 7 figures, 4 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Investigating Human--AI Discrepancies via Multiple-Solution Problems

cs.CY cs.AI ·2026-09-28 ·Zihao Wang, Francesco Insulla, Andrea Montanari
code/data similarity 0.64
Abstract · 50 pages, 16 pdf figures

Frontier artificial intelligence (AI) models are benchmarked on whether they reach a correct answer. Yet many problems admit several correct answers and repeated attempts, by different people or by the same model resampled, trace out a distribution over them. In this work, we ask whether human and model reasoning lead to different distributions over valid solutions. Our testbed comprises 270 reasoning puzzles across five puzzle families. These multiple-solution puzzles each have 3 to 8 valid solutions and are simple enough that humans and models can solve them reliably. The resulting distributions differ markedly: models differ from one another, yet resemble each other far more than they resemble humans. Model distributions are, moreover, within every puzzle family, less diverse than human ones. We compare these discrepancies across puzzle categories, and trace how they respond to reasoning-effort settings, to prompting, and to perturbations of the puzzle that leave its solutions unchanged. Together, these results point at significant differences between human and AI problem-solving processes, and their choice among equally defensible solutions. As progressive deployment of AI systems in society comes into focus, evaluating such differences (beyond one-dimensional accuracy metrics) is increasingly important. Data and code are available at https://hai-discrepancies.github.io/

0.49

Query Your Way Out: Benchmarking Multi-Turn Knowledge Reasoning through Generalized Puzzle Solving

cs.CL cs.AI ·2026-10-12 ·Xin Cheng, Junming Yang, Ning Xu
benchmarkcode/data similarity 0.56
Abstract · 20 pages, 8 figures

Puzzles offer a natural testbed for Large Language Models (LLMs) reasoning because they pose verifiable goals under partial information and require multi-step decisions to reach a solution. However, existing puzzle benchmarks typically focus on narrow environments with rigid mechanics and tightly constrained solution targets. To bridge this gap, we introduce the Active Probing Benchmark (APB), which generalizes puzzle-solving by casting concept identification as an interactive reasoning task that integrates specialized knowledge assessment into the puzzle setting. Specifically, APB evaluates whether models can acquire information via multi-turn active probing and inference to pinpoint 960 target concepts of specialized difficulty across eight diverse academic domains. Our evaluation reveals a counter-intuitive phenomenon: most open-source reasoning models significantly underperform their standard instruction counterparts. This finding suggests that in interactive settings, these models struggle to leverage procedural reasoning to reliably access and apply specialized domain knowledge. Beyond these empirical insights, APB provides a scalable pipeline for generating benchmarks that probe knowledge reasoning under interaction across diverse settings.

0.37

Mathematics for and by human cognition: A resource-rational search for bottlenecks in problem-solving

cs.AI ·2026-09-28 ·Sneha Aenugu
position similarity 0.56
Abstract

Human cognitive constraints are generally viewed as limiting factors in problem-solving. We argue that these constraints can instead play a critical role in driving advances in mathematics and beyond. We propose a theory of mathematical abstraction as a resource-rational search for bottlenecks in problem-solving. Bottlenecks arising from cognitive constraints create pressure to restructure existing knowledge, potentially giving rise to novel formalisms with applications beyond the problems that originally motivated them. Drawing on episodes from the history of mathematics, we illustrate how such bottlenecks can drive the development of novel abstractions and examine how cognitive constraints and affective responses shape this process. Finally, we discuss the implications of this account for machine mathematical discovery and argue that incorporating human-like constraints may facilitate the discovery of useful mathematical abstractions.

0.20

How AI Assistance Affects Human Skill Development: A Study of Learning with Logic Puzzles

cs.AI ·2026-08-24 ·Shang Wu, Catarina G Belem, Shuyuan Fu, Mark Steyvers, Padhraic Smyth
published similarity 0.56
Abstract · Accepted at Human-AI Complementarity and Alignment (HCOMP) 2026

While AI assistance can improve human task performance in the short term, it may also undermine the development of skills in the longer term. We examine this tension in a controlled logic-puzzle experiment involving on-demand AI assistance, where participants complete tasks before, during, and after AI is available. By experimentally varying AI request costs, we find that lower-cost assistance induces more frequent AI use. We also find that participants who request AI assistance during the AI-access phase perform worse at the task after assistance is removed, and their subsequent unassisted performance is overestimated when predicted from earlier AI-assisted performance. We use a Bayesian latent ability model to separate initial ability, post-AI ability, and participant-specific skill change, while estimating how independent reasoning during the AI-access phase relates to skill development. The results show that greater independent problem-solving effort is associated with larger gains in latent ability, consistent with the interpretation that skill development is weaker when AI assistance substitutes for independent reasoning.

0.67

Fractal basins trap latent reasoning

cs.LG ·2026-09-04 ·Jeffrey Lai, Anthony Bao, John Quinn, William Gilpin
theoryhot directionhighly cited similarity 0.54
Abstract · 6 pages, 5 figures

Reasoning allows artificial intelligence models to revisit and correct their mistakes, enabling recent frontier advances in mathematical theorem solving, software engineering, and autonomous task planning. Reasoning models are widely observed to reason for longer on harder tasks, but the general mechanism responsible for these slowdowns is unknown. Here, we show that reasoning models exhibit transient chaos, a physical consequence of the computational complexity of difficult tasks. As a consequence, we show that diverse leading reasoning models are dynamical systems with fractal basins, with fractality increasing with task difficulty across diverse tasks like Sudoku and maze solving, visual puzzles, and mathematical logic. We show that transient chaos emerges due to reasoning becoming trapped for extended durations near saddle points, which we show correspond to nearly-correct attempted solutions of the underlying problem. Our results show that reasoning slowdowns are an inevitable consequence of problem hardness in modern artificial intelligence models, and establish reasoning traces as a rich new class of dynamical system.

0.58

When Does Confidence Reveal Problem Difficulty?

cs.AI ·2026-11-14 ·Xiyu Bao, Langyuan Cui, Hwee Tou Ng, Chun Kai Ling
similarity 0.53
Abstract

While confidence signals are commonly evaluated for their ability to predict a model's own correctness, their relationship with problem difficulty remains less understood. In this work, we investigate a wide range of confidence-related signals and whether they can serve as indicators of problem difficulty across various task domains. We find that perturbation inconsistency, semantic entropy, and solution length exhibit strong associations with population difficulty than token-level uncertainty. Notably, these relationships persist even when restricting the analysis to problems correctly answered by the focal model, suggesting that such signals capture information about difficulty beyond their ability to predict the model's own correctness. We further explore applications of these signals, illustrating the potential and limitations of using confidence-related signals to guide inference-time decisions. Our findings highlight the utility of model-specific signals as imperfect but informative proxies for population-level problem difficulty.

0.27

Thinking effort aligns between humans and reasoning models in abductive reasoning

cs.CL cs.AI ·2026-09-01 ·Henry Arthur
top venue similarity 0.52
Abstract · 14 pages, 5 figures. To appear in Findings of EMNLP 2026

A major question in cognitive modeling concerns the behavioral alignment between large language models and humans across linguistic and non-linguistic tasks. Unlike standard LLMs, large reasoning models (LRMs) are optimized with reinforcement learning from verifiable rewards, encouraging correct solutions to reasoning tasks rather than preference-aligned responses. Recent work (de Varda et al., 2025) investigates the cost of thinking in humans and LRMs by comparing human reaction times with model reasoning traces across a range of reasoning tasks. We isolate this alignment by turning to abductive reasoning: unlike deductive tasks, its difficulty cannot be inferred from formal structure and offers no shortcuts a model could exploit to mimic effort without genuine search, providing firmer ground for empirical claims of shared effort. We find further evidence of alignment between LRM and human reasoning effort, as well as evidence that models and humans tend to make similar errors. Finally, we show that decoding methods that let models explore multiple reasoning paths increase alignment in reasoning cost between humans and LRMs across the three models tested.

0.64

Do Reasoning Representations Help Humans Evaluate LLM Outputs?

cs.LG cs.HC ·2026-09-08 ·Jaewoo Lim, Sungbok Shin, Sanghyun Hong
top venue similarity 0.52
Abstract · 19 pages. EMNLP 2026 (Findings)

Reasoning representations are increasingly used as explanations for large language model outputs. Yet they are typically evaluated with model-centric criteria, such as answer accuracy and faithfulness, leaving it unclear whether they help people evaluate model responses. In this work, we study reasoning representations as human-facing interfaces rather than proxies for model reasoning ability. We conduct a controlled human study of six reasoning formats across tasks of varying complexity, supported by a web-based framework that randomizes task domains, problem instances, and representation order. The study collects fine-grained judgments of structural understanding, error detection and localization, and trust calibration. Our study shows a mismatch between perceived preference and support for human evaluation. Participants prefer planning- and decomposition-based representations, but simpler chain-of-thought traces better support verification, trust, and interpretability. Preferred representations also introduce calibration risks, with more false alarms on correct traces and high trust despite low willingness to verify.

0.34