Solver-Hard Is Not Model-Hard: A Hardness-Controlled Diagnostic for LLM Constraint Reasoning

• URL: http://arxiv.org/abs/2607.17047v1
• Date: Sun, 19 Jul 2026 03:23:22 GMT
• Title: Solver-Hard Is Not Model-Hard: A Hardness-Controlled Diagnostic for LLM Constraint Reasoning
• Abstract summary: LLM constraint reasoners are often evaluated near the random-SAT phase transition, confounding density and solver hardness.<n>We compare proof-hard expander-Tseitin and proof-easy ladder-Tseitin formulas, pigeonhole anchors, and density-mismatched controls.<n>Across three included models, the near-matched-density accuracy gaps range from $-32$ to $+20$ points.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: LLM constraint reasoners are often evaluated near the random-SAT phase transition, confounding density and solver hardness. We test instance-level transfer while near-matching clause density. At aligned size bins, with near-matched density and matched maximum clause width, we compare proof-hard expander-Tseitin and proof-easy ladder-Tseitin formulas, pigeonhole anchors, and density-mismatched controls. Theory separates their resolution hardness; a solver-specific Glucose mean-conflict proxy differs by up to $51\times$, and five other solvers preserve the direction. Across three included models (243 instances each; a fourth is excluded for abstention), the near-matched-density accuracy gaps range from $-32$ to $+20$ points, with a pooled gap of $+1.7$ points ($p=0.74$) and a wrong-signed correctness-versus-conflict association ($r=+0.15$). A proof-preserving relabeling lowers accuracy in all five clusters for one model (mean $-93$ points) but not another, exposing model-surface sensitivity. In a preregistered extension, provider-reported completion-token spend does not consistently increase with the proxy after accounting for formula length and censoring. At 16k, the reasoning model spends more on proof-easy matched formulas and exhausts its budget on the solver-easiest UNSAT family; the 32k C1 gap is absent. These scoped dissociations concern verdict accuracy and observed token spend, not certificate solving, exact proof length, or allocation efficiency.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• The geometry of AI validation: Exact certification limits for iid best-of-N search [0.0]
  We represent validation and deployment rules as kernels over a reliability surface.<n>Knowing best-of-$n$ reliability through $n=m$ leaves exact ambiguity width $B_m,N=1+2sum_r=1m(-1)rcos2Nr/[(m+1)]$.
  arXiv  Detail & Related papers  (2026-08-21T15:18:11Z)
• Lévy Attention: Single-Pass Predictive Uncertainty for Continuous-Time Attention [0.0]
  Lévy Attention is a cross-attention operator whose output is integral against an inhomogeneous random measure.<n>On t-PatchGNN operator swap costs at most 5.6% accuracy against a matched control and nothing on the sparsest dataset.<n>One pass ranks 3,383 unseen patients by trust in 1.4 seconds.
  arXiv  Detail & Related papers  (2026-08-19T17:50:16Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Adaptive operator-generated subspaces for effective many-body Hamiltonians [0.0]
  We present the Adaptive Clifford-Algebra Subspacesolver (A-CASE)<n>Overlap, Hamiltonian, observable, and response matrices are reconstructed from one shared Pauli-expectation bank.<n>A grouped iteration propagates finite-shot variability through thresholding, root matching, spectral weights, susceptibility, and broadening.
  arXiv  Detail & Related papers  (2026-08-01T09:51:25Z)
• Conformal Cascade: Distribution-Free Accuracy Guarantees for Multi-Tier LLM Inference [6.094431019524038]
  Large language model (LLM) cascades reduce inference cost by routing easy queries to a small model and deferring hard queries to a larger one.<n>We introduce textbfConformal Cascade (CC), a multi-tier inference framework that uses conformal prediction set size as the deferral rule.
  arXiv  Detail & Related papers  (2026-07-27T19:19:58Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  We show that a lower bound holds for every admissible function and follows from a convex relaxation giving stronger bounds.<n>A theory verifies each agent one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point in the interval.
  arXiv  Detail & Related papers  (2026-06-30T06:10:25Z)
• Why Do Few-Step Text Latents Fail When Image Latents Work? Non-Commitment at Sharp Categorical Readouts [1.1760370831826417]
  We show that a smooth, regularity-limited deterministic map cannot resolve a discrete branch choice before a sharp categorical readout.<n>In the overlapping regime of real text autoencoders, we prove that the posterior-mean terminal step flips tokens at the rate of the latent mass in an $O(s(t)$ tube around decision boundaries.
  arXiv  Detail & Related papers  (2026-06-29T14:20:57Z)
• Auditing Combinatorial Randomness from Finite Transcripts [0.2864713389096699]
  We study black-box auditing of $k$-subset draws from $m$ labels under the exact uniform-without-replacement null.<n>For structured faults, we construct generator null-agnostic audits on the hypersimplex using marginal chi-square, pair maxima, serial overlap, anchored-boxpulsion and low-dimensional discrepancy.<n>Across observed and reference-source audits, no statistic remains significant after false-discovery correction.
  arXiv  Detail & Related papers  (2026-06-20T13:17:44Z)
• Adaptive Consensus in LLM Ensembles via Sequential Evidence Accumulation: Automatic Budget Identification and Calibrated Commit Signals [0.0]
  DASE produces a commit-type routing partition that generalises across benchmarks.<n> Adaptive stopping, not injection bandwidth, drives accuracy.<n>Injection-based methods exhibit an inverted-U accuracy-vs-inference trajectory.
  arXiv  Detail & Related papers  (2026-05-05T19:24:10Z)
• A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification [0.0]
  PLACE (Persistence-Landmark Analytic Classification Engine) is a closed-form pipeline for classifying point clouds and graphs.<n>Three quantitative guarantees -- a margin-based excess-risk rate, a closed-form descriptor-selection rule, and a per-prediction certificate -- are derived from training labels alone.
  arXiv  Detail & Related papers  (2026-05-04T17:15:01Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Criterion-referenceability determines LLM-as-a-judge validity across physics assessment formats [0.01116979912801043]
  We compare GPT-5.2, Grok 4.1, Claude Opus 4.5, DeepSeek-V3.2, Gemini Pro 3, and committee aggregations against human markers under blind, solution-provided, false-solution, and exemplar-anchored conditions.<n>For $n=771$ blind university exam questions, models achieve fractional mean absolute errors (fMAE) $approx 0.22$ with robust discriminative validity.<n>Across $n=55$ scripts, blind AI marking is harsher and more variable than human marking, with discriminative validity already poor.
  arXiv  Detail & Related papers  (2026-03-16T02:09:06Z)
• Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs [72.82403830490084]
  We argue that the decoding rule should be calibrated by correctness, not confidence alone.<n>We propose simple strategies that achieve this goal: Greedy-Threshold makes sampling greedy at very low confidence steps.<n>Together, our findings challenge prevailings about decoding under uncertainty and show gains across math and general reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-10-07T14:46:12Z)
• Large Language Monkeys: Scaling Inference Compute with Repeated Sampling [81.34900892130929]
  We explore inference compute as another axis for scaling, using the simple technique of repeatedly sampling candidate solutions from a model.<n>Across multiple tasks and models, we observe that coverage scales with the number of samples over four orders of magnitude.<n>In domains like coding and formal proofs, where answers can be automatically verified, these increases in coverage directly translate into improved performance.
  arXiv  Detail & Related papers  (2024-07-31T17:57:25Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.