Search: “constraint-satisfaction”

Smart search ranks by meaning as well as keywords (one row per story, last 45 days).

Ask Before You Optimize: Dynamic Pre-Formulation Clarification for Interactive Optimization

Researchers release OR-Clarify, a benchmark testing whether LLM agents ask clarifying questions before formulating optimization models from incomplete requests.

OR-Clarify evaluates pre-formulation clarification in operations research: each task gives a partial problem description, withholds structured hidden slots, and scores agents via bounded interaction with a simulated user, measuring slot recovery, stopping behavior, silent assumptions, and interaction cost. The authors also propose InterOPT, a two-stage framework that identifies formulation-critical gaps to decide when to ask or stop. In choice-based experiments InterOPT substantially outperforms all baselines in exact slot recovery and remains competitive in the open-ended setting.

Hugging Face daily papers·Sep 3, 20:00 UTC · 12d agoAI research1

35

One Symptom, Three Levers: A Critical Review of On-Policy Self-Distillation

A review paper frames on-policy self-distillation collapse as governed by three levers: token weighting, privileged information, and guidance decay.

The paper critically reviews On-Policy Self-Distillation (OPSD), where a language model trains on its own generations scored token-by-token by a teacher conditioned on privileged information such as reference solutions or environment feedback. It identifies collapse, the progressive narrowing of producible reasoning paths, as the dominant failure mode and analyzes it through three levers: signal weighting, the nature of privileged information, and teacher dynamics. The review is restricted to mathematical reasoning, reports no new experiments, and offers a shared vocabulary separating settled findings from disputed ones.

Hugging Face daily papers·Aug 25, 20:00 UTC · 21d agoAI research

45

Efficient Branch-and-Bound Testing and Verification of zkVMs

ZEBRA verifies zkVM constraint systems via branch-and-bound cardinality counting, finding 11 zero-day bugs across five real-world zkVMs and running 51.5x faster than SMT verification.

ZEBRA reduces zkVM correctness to a solution-set cardinality problem requiring that each constraint system admit exactly one valid execution trace, eliminating redundancies like null-row padding and non-deterministic permutations before counting. It lifts analysis from finite-field witnesses to an integer interval lattice, exploiting that constraints across 5 real-world zkVMs use only 14.0% of theoretical connectivity capacity on average, enabling tight interval propagation. A parallel branch-and-bound search produces concrete counterexamples or certifies absence of violations within a bounded region. ZEBRA discovers 11 zero-day bugs (6 independently confirmed, 3 fixed), is 51.5x faster than SMT-based verification, and verifies 16.5 percentage points more instances.

arXiv cs.CR·Sep 14, 04:35 UTC · 2d agoResearch

45

Beyond Solver Verdicts: Generative Reward Models for Autoformalization

Researchers introduce Generative Verification (GenV), a generative reward model achieving 0.961 AUROC in detecting unfaithful autoformalization that preserves solver verdicts.

The paper formalizes Verdict-Preserving-Unfaithfulness (VPU), a failure mode in neurosymbolic autoformalization where an incorrect encoding executes successfully and matches the expected solver verdict, and proves verdict-only verification is bounded to chance-level detection. The proposed Generative Verification (GenV) distills an offline Z3-equivalence oracle into a reference-free, continuous reference-equivalence score within the language model's vocabulary space. The oracle-mined verifier (GenV+HN) achieves 0.961 AUROC, generalizes zero-shot across unseen translators and formal styles, and yields an 11.3-point downstream accuracy gain in agentic test-time compute allocation. Mechanistic analysis with decision-projected logit lenses and sparse autoencoders shows the generative readout extracts precise spatial error coordinates without explicit localization training.

Hugging Face daily papers·Sep 9, 20:00 UTC · 6d agoAI research1

35

Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration

New optimization theory paper proves near-optimal lower bounds for gradient descent with predetermined stepsizes, confirming silver-schedule optimality.

The paper studies the limits of accelerating gradient descent using predetermined nonnegative stepsizes in smooth convex optimization, with the key constant p_sil = log2(1 + sqrt(2)). It proves a non-anytime lower bound of Omega(n^(-p_sil - O(sqrt(log log n / log n)))) on the error achievable by any such stepsize schedule. In the anytime setting, it shows every infinite nonnegative schedule must incur error Omega(n^(-2*p_sil/(1+p_sil) - O(sqrt(log log n / log n)))) at infinitely many horizons. Combined with the silver-schedule upper bound of Altschuler and Parrilo (2025) and the anytime upper bound of Zhang et al. (2025), these results determine the optimal polynomial convergence exponents in both settings.

arXiv cs.AI / cs.LG / cs.CL·Sep 8, 17:59 UTC · 7d agoAI research

28

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarch

New work characterizes language generation in the limit via finite witnesses, proves a full separation-width hierarchy, and formalizes all results in Lean.

The paper fully characterizes when language generation in the limit is possible for arbitrary families over a countable universe: each target must admit a finite positive witness such that targets activated by any finite sample share an infinite common intersection. It defines positive separation width and proves every level of the resulting hierarchy occurs, with countable families admitting singleton witnesses and unions of families with infinite common cores requiring unbounded finite witnesses. The characterization, a universal normalization, and a diagonal capture lemma are machine-checked in the Lean proof assistant, with the development maintained on GitHub.

arXiv cs.AI / cs.LG / cs.CL·Sep 9, 17:54 UTC · 6d agoAI research1

18

Recognition-Refusal Misalignment in LLMs: Why Models Answer Structurally Unanswerable Questions

A linear hidden-state direction encodes question impossibility in 1.7B-70B LLMs, but misalignment with the safety-refusal pathway explains why models answer unanswerable questions.

The study examines why instruction-tuned LLMs from 1.7B to 70B parameters answer structurally unanswerable math and code questions instead of abstaining. A single linear direction in the hidden state separates answerable from impossible prompts, showing models represent impossibility before generation, but this direction is nearly orthogonal to the canonical safety-refusal direction. Generation-time steering along the recognition direction changes invalidity-aware behavior dose-responsively, and the geometry is present even at the pretraining endpoint, indicating a routing failure rather than an encoding failure.

Hugging Face daily papers·Aug 28, 20:00 UTC · 18d agoAI safety & security

30

Bellman Policy Optimization

Bellman Policy Optimization, a critic-free RLVR method derived from Policy Mirror Descent, improves LLM mathematical reasoning without intermediate state-value estimation.

The paper introduces Bellman Policy Optimization (BPO), a critic-free reinforcement learning method for LLMs with verifiable rewards, derived from Policy Mirror Descent. BPO uses the Bellman equations to reformulate PMD as a trajectory-level objective for autoregressive generation with terminal rewards, avoiding state-value estimation at intermediate states. The authors prove BPO shares the same unique optimal solution as PMD and validate it on mathematical reasoning benchmarks.

arXiv cs.AI / cs.LG / cs.CL·Sep 14, 17:59 UTC · 1d agoAI research

38

Safety for Whom? Boundary-Aware Self-Distillation for Controlled LLM Safety Refusal

A self-distillation safety framework tunes narrow-boundary refusals in Qwen3-8B, raising target-domain refusal to 84.75% while cutting over-refusal from 15.20% to 5.20%.

The paper formulates narrow-boundary safety, where deployments need refusals within specific topics rather than whole subjects, and proposes an offline self-generated framework with controlled topic generation, escalating retries, and harmful-benign boundary pairs. On political persuasion with Qwen3-8B, the method raised target-domain refusal from 9.47% to 84.75% and cut the mean unsafe-response rate across three broader benchmarks from 26.26% to 0.14%. Verified target-model responses reduced over-refusal from 15.20% to 5.20%, and boundary-pair data cut comply-side over-refusal on held-out pairs from 32.94% to 4.16%. Results show data composition controls the safety-usability trade-off and alignment should be evaluated on both sides of the refusal boundary.

Hugging Face daily papers·Sep 2, 20:00 UTC · 13d agoAI safety & security1

32

Unfold The World: Factorize 4D Properties in Reinforcing Spatial Reasoning

FactoSR factorizes 4D spatial reasoning into XY, Z, and T reinforcement-learning sub-objectives, boosting VLM performance on VSI-Bench by 5.9% and All-Angles-Bench by 4.5%.

Researchers present FactoSR, a factorized reinforcement learning framework that decomposes world-consistent reasoning into planar correspondence, depth consistency, and temporal reversibility sub-objectives. Optimizing these verifiable constraints turns the ill-posed projection recovery problem into tangible reasoning steps. Evaluations show gains of 5.9% on VSI-Bench and 4.5% on All-Angles-Bench for 3D and 4D reasoning, arguing VLMs' spatial bottleneck stems from training on 2D projections versus latent 3D geometry and temporal continuity.

Hugging Face daily papers·Sep 2, 20:00 UTC · 13d agoAI research

26

Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks

Theory paper derives nearly tight Rademacher complexity bounds for sparsely activated one-hidden-layer ReLU networks.

Building on Awasthi et al. (COLT 2024), the authors bound statistical complexity for networks where each input activates at most k of s hidden units. A support-preserving cover and normalized chaining argument remove the explicit dimension factor, with matching lower bounds up to logarithms. They also derive agnostic minimax excess-risk bounds of order min{1, sqrt(s/(km))} for a normalized bounded loss and show bias bounds comparable to WR restore worst-case rates even on domains where sparsity holds globally.

arXiv cs.AI / cs.LG / cs.CL·Sep 8, 17:53 UTC · 7d agoAI research

16

CONTINUITY: Security-Context Contracts for Composable LLM Agent Controls

Researchers introduce CONTINUITY, a framework of assume-guarantee contracts that preserves LLM agent security context across components, verified across 2,560 attack instances.

The paper identifies security-context discontinuity, where individually sound controls drop, widen, or reinterpret security context as actions cross component boundaries, and proposes CONTINUITY, a framework of assume-guarantee contracts using signed root grants, provenance commitments, role-bound transition receipts, and effect-bound execution permits. It formalizes end-to-end consequence integrity, requiring every external effect to be backed by a valid authorization witness linking principal, task, provenance, and policy state. A reference verifier and cross-layer fault-injection suite covering 32 fault classes showed the full configuration committed no harmful external effect across 2,560 parameterized attack instances while completing all 700 benign tasks and escalating all 200 ambiguous cases.

arXiv cs.CR·Sep 4, 15:26 UTC · 12d agoAI safety & security

32

Benign Loss Landscapes Can Coexist with Worst-Case Hardness

Theory paper shows tree tensor networks contain worst-case hard targets yet benign loss landscapes, with difficulty arising from degenerate saddles.

The paper studies tree tensor networks (TTNs), which generalize deep linear networks and Tucker decompositions and embed arbitrary read-once Boolean formulas. It proves that every local minimum that is minimum-norm is global for every realizable target, so bad local minima do not distinguish typical from worst-case problems. Instead, learning difficulty arises from high-order degenerate saddle points caused by rank-deficiency, illustrated via a parity function case study, linking landscape geometry to computational hardness.

arXiv cs.AI / cs.LG / cs.CL·Sep 11, 16:57 UTC · 4d agoAI research

16

LimiX-2: A Contextual Mechanism Network Towards General Structured-Data Intelligence

LimiX-2 scales Contextual Mechanism Networks pretrained via context-conditional masked modeling, beating tabular foundation models on TabArena, TALENT, and BCCO benchmarks.

LimiX-2 is a new tabular model in the LimiX family, developed through model and data scaling guided by previously established scaling laws under the Contextual Mechanism Networks (CMNs) paradigm. It is pretrained with Context-Conditional Masked Modeling (CCMM) on synthetic datasets generated by structural causal models spanning diverse graph structures, functional mechanisms, and observation processes. It outperforms dataset-specific models and tabular foundation models on TabArena, TALENT, and BCCO, and its feature attention encodes direct causal relationships, enabling accurate causal skeleton recovery.

arXiv cs.AI / cs.LG / cs.CL·Sep 15, 17:30 UTC · 23h agoAI research1

18

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Theorists prove multi-step lookahead RL planning is NP-hard for every fixed rational discount factor yet give a randomized polynomial-time approximation scheme.

The paper resolves open questions about reinforcement learning with multi-step transition lookahead. It shows exact planning remains NP-hard for every fixed rational discount factor in (0,1), not just discounts arbitrarily close to one, and introduces a randomized polynomial-time approximation scheme for every fixed lookahead depth. Extending to unknown transitions and stochastic rewards via optimism and variance-adaptive confidence bounds, the algorithm achieves cumulative regret matching classical tabular discounted RL up to logarithmic factors.

arXiv cs.AI / cs.LG / cs.CL·Sep 10, 16:58 UTC · 5d agoAI research1

22

Sound Debloating of Redundant Checks in Zero-Knowledge Machine-Learning Circuits

Automated framework soundly removes up to 48.7% of redundant constraints in ezkl and zkml ZK-ML circuits, cutting prover time by up to 72.8%.

The framework uses whole-circuit abstract interpretation and a provenance graph to verify that each removed redundant check (range proofs, sign lookups, bit decompositions) remains entailed by the rest of the circuit, provably preserving soundness. It was evaluated on MLP, CNN, RNN, and transformer circuits generated by ezkl and zkml, with up to 25.3 million constraints. It removes up to 48.7% of constraints and reduces prover time by up to 72.8% without weakening security. Under-constrained circuits in deployed ZK systems have previously enabled attackers to forge transactions and bypass verification.

arXiv cs.CR·Sep 9, 13:27 UTC · 7d agoResearch1

35

Beneath the Surface of Chains-of-Thought: A Mechanistic Interpretation of Reasoning Operations in LLMs

Study shows LLM reasoning operations like planning and deduction are geometrically separable in hidden states, with separability peaking in middle layers.

Researchers investigate whether functional reasoning operations — problem formulation, goal decomposition, deduction — have corresponding geometric structure in LLM hidden representations. They find operations are separable in held-out representations with separability peaking in middle layers, ruling out lexical and positional confounds; token-wise operation alignment becomes more distributed across layers, and identical surface tokens are represented differently depending on their surrounding chunk. Attention-masking interventions show chunk-onset operation-aligned representations depend on preceding reasoning context; code is released on GitHub (naver-ai/beneath-cot).

Hugging Face daily papers·Sep 3, 20:00 UTC · 12d agoAI research1

40

Atlas: Efficient Verifiable Semantic Search

Atlas delivers zero-knowledge proofs for HNSW semantic search, verifying RAG retrieval in under a second on SIFT1M and 2.0 seconds at 100M vectors.

Atlas lets a search provider prove that a query was answered correctly against a committed HNSW index without revealing the index, addressing provider deviations like truncation or bias. It combines offline preprocessing, a fixed-size-state restructuring of HNSW with a correctness proof, and timestep-tagged batching of per-step arguments. The system proves queries in under a second on SIFT1M and 2.0 seconds at 100 million vectors while preserving plaintext HNSW recall, and proven retrieval maintains end-to-end RAG answer quality at lower cost than prior verifiable retrieval systems.

arXiv cs.CR·Sep 10, 17:30 UTC · 5d agoResearch1

40

Your Agent Aced the Task. Will It Do It Again?

IBM Research Hugging Face post examines whether LLM agents that succeed at a task once will reliably succeed again.

Hugging Face published an IBM Research blog post titled 'Your Agent Aced the Task. Will It Do It Again?' with URL slug 'altk-evolve-consistency'. No article text was provided, but it appears to address agent consistency and reliability evaluation across repeated task runs. This is relevant to developers building or evaluating LLM agent systems.

Hugging Face Blog·Sep 15, 16:00 UTC · 1d agoAI tools & infra

30

Same Trajectory, Contradictory Rewards (ROBORMBENCH): Paraphrase Fragility in Vision Language Reward Models

New ROBORMBENCH benchmark shows vision-language reward models can flip robot success/failure judgments when goal instructions are paraphrased.

The authors show that paraphrasing the instruction alone can substantially change progress scores from VLM reward models, even flipping identical robot trajectories between failure and success. ROBORMBENCH comprises 2,390 real-robot trajectories with ground-truth progress labels and 21,673 verified paraphrases covering lexical, syntactic, and action-goal rewrites. Instability is widespread across proprietary and open-source VLMs, grows with more divergent rewrites, and is not reliably reduced by scale or explicit reasoning, while trajectory-grounded dedicated reward models are markedly more stable.

arXiv cs.AI / cs.LG / cs.CL·Sep 4, 17:47 UTC · 11d agoAI research1

35

PLC-DPO: Posterior Label Correction in Noisy and Ambiguous Preference Optimization

PLC-DPO corrects noisy preference labels during DPO by routing each pair as clean, flip, or tie using calibrated policy-reference margins.

PLC-DPO addresses reversed, weak, or ambiguous preference labels in Direct Preference Optimization by using the calibrated policy-reference margin as online evidence to route each pair's training signal as clean, flip, or tie. This actively corrects supervision direction and strength rather than only filtering suspicious examples. Across 57 dataset-model-benchmark cells, PLC-DPO achieves the best mean win rate of 60.5 versus 55.5 for the next-best method. Injected-noise and tie stress tests plus human disagreement analysis show the routing stays stable and distinguishes flipped from weakly directional pairs.

Hugging Face daily papers·Aug 30, 20:00 UTC · 16d agoAI research

28

Measuring LLM Sycophancy under Sustained Multi-Turn Pressure

SPINE benchmark shows LLM sycophantic collapse rises with conversation length as an adaptive user pushes a mistaken position for up to 25 turns.

The SPINE benchmark uses an LLM proxy that persistently and adaptively defends a mistaken user position for up to 25 turns, testing four production LLM systems and three OLMo3-7B variants on 100 false-presupposition and 100 unethical-query items. Collapse rates increase with conversation length for every model, and short-horizon evaluation protocols underestimate sycophancy. Analysis of accessible reasoning traces shows the correct position often remains represented when the model concedes, indicating models choose to please users rather than lacking knowledge. Among tested tactics, emotional appeals are most associated with inducing sycophantic behavior.

arXiv cs.AI / cs.LG / cs.CL·Sep 8, 17:35 UTC · 7d agoAI safety & security1

50

An Open Recipe for IMO Gold: Training Nemotron for Olympiad Mathematics

Open post-training pipeline turns Nemotron 3 Ultra checkpoints into an IMO 2026 gold-medal system, scoring 30/42 without formal provers or external tools.

Starting from Nemotron 3 Ultra, researchers trained two specialist checkpoints using supervised fine-tuning and reinforcement learning for natural-language olympiad proof generation. Three checkpoints power an iterative generate-verify-refine search plus a separate high-compute selection stage, operating entirely in natural language with no formal prover, external tools, or internet access. The system scored 30 of 42 points at IMO 2026, reaching the gold-medal threshold. The release includes the post-trained checkpoints, training data, training and inference code, submitted solutions, and Nemotron-IMO-Bench with 200 novel olympiad-level problems.

Hugging Face daily papers·Sep 8, 20:00 UTC · 7d agoModel release

65

Coupled Calibration and Learning: Mitigating Teacher Bias in LLM Distillation without Target-Domain Reward Feedback

CCL couples teacher calibration with student updates via token-level branching, provably removing teacher bias in LLM distillation.

The paper proposes Coupled Calibration and Learning (CCL), an LLM distillation algorithm that alternates teacher calibration using source-question reward feedback with student training on target questions under covariate shift. Each iteration calibrates the teacher on source feedback, trains the student on target questions, and lets the updated student inform subsequent calibration. The authors prove the student's expected KL divergence to the oracle student converges to zero at a polynomial rate, and show regularized direct matching error can remain bounded away from zero.

arXiv cs.AI / cs.LG / cs.CL·Sep 15, 17:15 UTC · 23h agoAI research

20

Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

Theory paper combines differential privacy with fixed-parameter tractable encoders, improving approximation guarantees for combinatorial optimization and proving new lower bounds.

The paper studies combinatorial optimization under epsilon-differential privacy within the implicit encoder-decoder framework of Gupta et al. (SODA 2010), generalizing it to allow fixed-parameter tractable encoders. This circumvents approximation barriers inherent to polynomial-time algorithms and yields improved guarantees for fundamental combinatorial optimization problems. The authors establish the first representation-independent lower bounds: assuming a non-uniform variant of the Gap Exponential Time Hypothesis, no epsilon-DP encoder-decoder pair can achieve certain approximation guarantees with a subexponential-time decoder for sufficiently small epsilon. Representation-dependent lower bounds are also provided for larger epsilon.

arXiv cs.CR·Sep 11, 07:13 UTC · 5d agoResearch

18

ENCP: Episode-Normalized Conformal Prediction for Vision-and-Language Navigation

ENCP calibrates conformal prediction per navigation episode, giving step-level coverage guarantees for vision-language navigation agents despite within-episode dependence.

Episode-Normalized Conformal Prediction (ENCP) rescales a nonconformity score by a VLN policy's residual confidence and calibrates one maximum score per episode, preserving step-level coverage of at least 1−α despite dependence among steps within an episode. Across four VLN policies and three nonconformity scores on R2R and REVERIE, ENCP meets all reported empirical step-coverage targets in seen-to-unseen evaluation. The model-agnostic uncertainty estimates can signal when an agent should defer to a stronger predictor or human assistance.

arXiv cs.AI / cs.LG / cs.CL·Sep 15, 17:42 UTC · 23h agoAI research

12

AgentGrad: Intervention-guided Prompt Optimization for Multi Agent Systems

AgentGrad introduces intervention-guided prompt optimization for LLM multi-agent systems, achieving state-of-the-art results with 2.5x faster optimization.

AgentGrad is a prompt optimization framework for LLM-based multi-agent systems that addresses limitations in textual gradient extraction and aggregation. It uses sequential intervention to identify the agent whose prompt modification resolves a given failure, then applies agent-level supervision and semantic gradient clustering to build generalized gradients. Experiments report state-of-the-art performance across five MAS benchmarks and a 2.5x average reduction in wall-clock optimization time versus the next-fastest baseline.

Hugging Face daily papers·Sep 7, 20:00 UTC · 8d agoAI research

32

Thought without systematicity? Evaluating reasoning models on rule induction tasks

Study finds reasoning models often fail on structurally equivalent variants of tasks they solve, suggesting their reasoning lacks systematicity.

The paper extends rule induction tasks from cognitive science using task isomorphisms such as recombination and substitution to test systematicity in reasoning models. Despite solving tasks correctly, models frequently fail on structurally equivalent variants of the same task. The authors conclude many model behaviors lack systematicity, making it difficult to establish cognitive abilities beyond the specific evaluation contexts.

Hugging Face daily papers·Sep 11, 20:00 UTC · 4d agoAI research

35

Negative Self-Distillation: Learning to Reason by Avoiding Flaws

Researchers propose Negative Self-Distillation (NSD), a label-free LLM self-improvement method that diverges from self-generated flawed reasoning rather than imitating privileged solutions.

The authors show On-Policy Self-Distillation can degrade complex reasoning by forcing imitation of artificially confident traces built on privileged information, suppressing uncertainty and self-correction. NSD instead generates a question-specific negative condition — such as acting as a 'careless reasoner' — and pushes the model's distribution away from it without ground-truth labels. A dynamic gating mechanism isolates reasoning-critical tokens so gradient updates fix behavioral flaws without damaging foundational linguistic capabilities. NSD consistently outperforms OPSD and other label-free, self-bootstrapping reinforcement learning baselines.

Hugging Face daily papers·Sep 9, 20:00 UTC · 6d agoAI research1

30

Learning to Solve Hard Problems in RL for LLMs by Never Giving Up

Paper introduces Never Give Up adaptive sampling, fixing RL's 'Matthew Effect' where compute is wasted on easy problems and hard problems see little improvement.

Researchers identify a 'Matthew Effect' in reinforcement learning for LLMs, where RL yields large gains on easy problems but minimal improvement on hard ones because compute is misallocated. They propose Never Give Up (NGU), an adaptive sampling method that keeps generating samples for a problem until one is correct, using asynchronous RL to filter easy problems cheaply and concentrate compute on hard ones. NGU improves performance per compute on the Deepscaler math benchmark and iteratively solves the Manufactoria coding task where standard GRPO with per-test reward fails.

Hugging Face daily papers·Sep 10, 20:00 UTC · 5d agoAI research

45