IJCAI 2026 论文列表

Spectral relaxation is widely used for large-scale combinatorial optimization due to its computational efficiency. Yet its effectiveness depends critically on the choice of graph normalization, a design decision typically made heuristically. Here, we show that normalization can be treated as a continuous optimization variable rather than a fixed preprocessing choice. Our method, Differentiable Spectral Normalization (DSN), parameterizes the spectral relaxation through a diagonal metric and maximizes the resulting lower bound via projected gradient ascent. Exact gradients are obtained through the Hellmann-Feynman theorem using only the principal eigenpair, maintaining linear complexity per iteration. On benchmark instances ranging from 10^3 to 8.4 x 10^6 nodes, DSN improves solution quality by 3-15% over static spectral methods. Its performance comes within 1-3% of state-of-the-art metaheuristics, such as simulated annealing, at up to 190x lower computational cost on large-scale instances. These results suggest that learning problem-specific relaxation geometry can substantially close the gap between spectral scalability and metaheuristic solution quality.

Despite decades of intensive research and optimization, modern Boolean Satisfiability (SAT) solvers have reached a plateau where significant performance gains are increasingly difficult to achieve. While Large Language Models (LLMs) have demonstrated remarkable capabilities in pattern recognition and code generation for combinatorial optimization, their direct application to highly optimized SAT solvers remains a formidable challenge due to the extreme complexity and sensitivity of solver heuristics. In this paper, we introduce AESAT (Auto-Evolving SAT solving), a novel neuro-symbolic framework designed to automatically evolve and optimize the heuristic functions of SAT solvers. AESAT employs a memetic-inspired approach, synergizing LLM-guided individual optimization with evolutionary exploration. By leveraging self-optimized prompting techniques, our framework enables LLMs to iteratively discover and refine sophisticated heuristics that bypass the limitations of human-engineered designs. The efficacy of AESAT is demonstrated by its flagship derivative, AE-Kissat-MAB, which won the main track of the 2025 International SAT Competition by a wide margin. This result represents the first time an LLM-enhanced solver has dominated the world's premier SAT competition, marking a paradigm shift in the automated design of reasoning algorithms.

Given a social network ? with n nodes and m edges, the opinion maximization (OM) problem aims at identifying k (k ≪ n) opinion leaders to maximize their opinion propagation in ?. Despite its significance and prevalence, existing OM methods often struggle to strike a satisfactory balance between theoretical performance and practical efficiency. This paper provides an inverse optimization perspective for OM by reformulating it as an opinion minimization (OMin) problem, whose objective function holds succinct expression and desired properties. Then, we introduce a bounded estimation scheme (BES) that can estimate the objective function of OMin with bounded error in Õ(kn+m) expected time, thereby making the optimization for OMin more efficient. To further enhance the optimization efficiency, a decomposition-based decremental estimation algorithm (DDEA) with a near (1-1/e) approximation ratio in Õ(kmn) expected time is specifically designed for OMin. Extensive experiments on real-world social networks of varying scales demonstrate the effectiveness of BES and the superiority of DDEA.

Hybrid tables, also referred to as `smart' in the literature, represent a valuable modeling technique within Constraint Programming (CP). These tables allow us to handle disjunctive cases (constraining expressions) in a compact and structured way, by authorizing tuples (table entries) to contain simple unary and binary arithmetic restrictions (similar to internal constraints). In this paper, we show the practical interest of using hybrid tables for planning-like combinatorial puzzles, when the transition from one state to the next can be encoded by a single hybrid table. Experimental results show that these hybrid models exhibit greater compactness and efficiency in solving compared to their conventional counterparts.

We present complementary branching, a new branching approach for model counting based on the complement counting paradigm. Instead of branching on individual variables, complementary branching decomposes the counting problem for arbitrary CNF formulas into several subformulas, which naturally augments the classic DPLL branching. We show two novel results in which the main tool is complementary branching. First, we design new #SAT algorithms for sparse CNF formulas running in time O*(2^(alpha n)), for some constant alpha < 1. As a second application, we improve the best known deterministic upper bound for #3-SAT to O*(1.637^n) by using a version of clause learning based on complementary branching. These results demonstrate that complementary branching is a powerful tool for designing faster exact algorithms for propositional model counting.

Optimizing survival outcomes, such as patient survival or customer retention, is a critical objective in data-driven decision-making. Off-Policy Evaluation (OPE) provides a powerful framework for assessing such decision-making policies using logged data alone, without the need for costly or risky online experiments in high-stakes applications. However, typical estimators are not designed to handle right-censored survival outcomes, as they ignore unobserved survival times beyond the censoring time, leading to systematic underestimation of the true policy performance. To address this issue, we propose a novel framework for OPE and Off-Policy Learning (OPL) tailored for survival outcomes under censoring. Specifically, we introduce IPCW-IPS and IPCW-DR, which employ the Inverse Probability of Censoring Weighting technique to explicitly deal with censoring bias. We theoretically establish that our estimators are unbiased and that IPCW-DR achieves double robustness, ensuring consistency if either the propensity score or the outcome model is correct. Furthermore, we extend this framework to constrained OPL to optimize policy value under budget constraints. We demonstrate the effectiveness of our proposed methods through simulation studies and illustrate their practical impacts using public real-world data for both evaluation and learning tasks.

The Maximum Weight Clique Problem (MWCP) is NP-hard and is typically solved exactly within a Branch-and-Bound (BnB) framework, where the quality of upper bounds critically determines the pruning efficiency. Recent solvers enhance independent-set-based bounds using MaxSAT reasoning. However, their effectiveness is limited by two inherent limitations: (i) independent sets in conflicts are discarded after a single use, preventing their reuse in subsequent reasoning; and (ii) conflicts are detected in a fixed order regardless of their potential contribution to bound tightening. To address these issues, we propose two complementary techniques. The UnLocking Mechanism (ULM) preserves conflict cores and enables the reuse of independent sets in subsequent reasoning, while the Benefit-Enhanced Strategy (BES) steers the MaxSAT reasoning process toward conflicts and independent sets with higher pruning potential. By integrating ULM and BES, we develop a new solver, ULE-MWC (UnLocking Enhanced MWC). Experimental results on standard benchmarks show that ULE-MWC consistently yields tighter upper bounds and outperforms state-of-the-art exact solvers in both runtime and search efficiency.

Satisfiability (SAT) with cardinality constraints arises naturally in many practical applications, where high-level counting requirements coexist with standard Conjunctive Normal Form (CNF) clauses. Translating these constraints into CNF can destroy structural information, limiting the effectiveness of search-based heuristics. In this paper, we propose a cardinality-aware local search framework to solve this problem, denoted as CardSAT-LS. CardSAT-LS integrates a preprocessing phase based on the generalized unit propagation and resolution, a cardinality-sensitive scoring function combining the make-break mechanism and cardinality violation, and an initialization based on fake-backbone variables. Furthermore, CardSAT-LS employs a unified framework that adaptively alternates between flip and swap operators when the search gets trapped in local optima. Finally, we conduct experiments on five public benchmarks from real-world applications as well as the MaxSAT and SAT competitions. Compared with ten state-of-the-art competitors, including SAT, MaxSAT, and PB solvers, CardSAT-LS solves the most instances with the lowest PAR-2 score. Additionally, we integrate CardSAT-LS into exact solvers for phase selection, which leads to significant speedups.

We introduce QUINTIC, a general algorithm for actively learning quantitative automata from preferences. Quantitative automata evaluate input sequences by applying a valuation function---such as sum, product, or average---to the output labels of the states visited. Such models naturally arise in use cases ranging from probabilistic verification, sequence classification, and sequential decision making. However, existing learning approaches, such as variants of L*, weighted‐automata learning algorithms, and active learning preference‐driven methods, either assume finite output alphabets or restrict the valuation function to particular forms. QUINTIC utilizes a symbolic observation table and applies deductive reasoning with the assistance of an SMT solver to identify the correct minimal state, transition, and state label combination of the quantitative automaton. The deductive reasoning relies on the minimal combination of theories determined by the valuation function and output alphabet. Consequently, QUINTIC has completeness, minimalism, and query complexity guarantees, and learns quantitative automata across finite, integer, and rational outputs. Our extensive experiments show how QUINTIC scales under weak or strong feedback, and alternative MaxSMT objectives.

Factored tasks are a classical planning representation that extends SAS+ with limited forms of disjunctive preconditions, conditional effects, and angelic nondeterminism. This added expressiveness allows for a more compact representation of taks than traditional formalisms such as STRIPS or SAS+, and supports a wide range of task transformations. However, existing planning approaches for factored tasks have been limited to heuristic search methods. In this work, we investigate how to encode factored tasks in SAT. We propose several ways to encode the tasks, focusing on different strategies for translating the factored transition relation into propositional logic. We also analyze how to exploit parallelism at various levels in this setting and study the impact of common task transformations on the performance of SAT-based planners.

The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MaxSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables n (instance scale), the maximum coefficient magnitude k (numeric range), and structural parameters of the constraint graph such as treewidth tw (decomposability), and vertex cover size vc (density). We show that MaxSTP is W[1]-hard parameterized by n, implying that n and parameters that depend on n (including tw and vc) are insufficient for fixed-parameter tractability. For combined parameters, we give an O^*(k^n)-time algorithm, yielding single-exponential solvability for fixed k. While k+tw remains W[1]-hard, MaxSTP is in XP via an O^*((n * k)^tw) algorithm. Our results suggest that MaxSTP is often computationally harder than optimizing qualitative CSPs - we verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by n or tw. However, we also demonstrate that FPT algorithms for MaxSTP are indeed possible but with other parameters such as k + vc.

Decision-focused learning has shown great promise for addressing predict-then-optimize problems, particularly in the presence of under-specified models. However, its practical deployment is often hindered by high computational costs and limited scalability, as it requires solving a constrained optimization problem for each training instance at every iteration. To address these challenges, we propose a novel framework that incorporates Lagrangian decomposition into the decision-focused learning paradigm. Specifically, we introduce a new surrogate objective along with two loss functions for evaluating and training the underlying prediction model. We further propose two variants of our approach, which offer different trade-offs between computational efficiency and solution quality. Our framework can be seamlessly integrated with standard decision-focused learning methods, including Smart Predict-then-Optimize (SPO+) and Implicit Maximum Likelihood Estimation (IMLE). Through experiments on two standard benchmarks, the multi-dimensional knapsack problem and quadratic portfolio optimization, we demonstrate that our approach achieves competitive performance while remaining amenable to parallelization. In particular, it consistently outperforms traditional decision-focused learning methods on large-scale instances, involving up to eight times more variables than those typically considered in related work. The implementation is available at https://github.com/corail-research/DFL-LD.

Joint optimization of pricing, dispatching, and routing is critical for hub-based mobility services but challenging due to complex decision couplings and strict service guarantees, such as Order Response Rate (ORR). Conventional constrained reinforcement learning often struggles in this mixed continuous--combinatorial action space, suffering from oscillatory behavior in Lagrangian dual variables and unstable constraint satisfaction. To address this, we propose PID-SACA, a unified framework that integrates an entropy-regularized actor--critic policy for continuous pricing and dispatching assisted by an embedded routing solver for execution-aware feedback. Crucially, we adapt the PID control mechanism to the Lagrangian dual update process. This approach leverages proportional, integral, and derivative feedback to dampen oscillations caused by stochastic gradient variance, ensuring robust long-term constraint enforcement. We provide theoretical analysis on the boundedness of dual variables, and experiments on publicly available large-scale mobility datasets demonstrate that PID-SACA significantly outperforms baselines, achieving high revenue with stable service compliance. Code: https://github.com/jerry0375/PID-SACA

Optimization problems such as Viterbi decoding and V-optimal histogram construction seek a path of exact length L through a state space that minimizes a cost function. These problems are traditionally solved using dynamic programming (DP). A best-first-search (BFS) solution is also applicable, yet requires maintaining a priority queue. In all cases, memory usage grows linearly with both state space size and path length. In this paper, we propose CompactBFS, a framework that limits the growth of the BFS priority queue to space-efficiently determine the exact optimal cost for a fixed-length path and then constructs such a path by a divide-and-conquer strategy that eliminates the memory overhead. We apply CompactBFS to Viterbi decoding, which remains relevant to speech recognition, and V-optimal histogram construction. Our experimental results demonstrate significant gains over state-of-the-art solutions in runtime and memory consumption.

Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often used for query evaluation in probabilistic databases. Due to the computational intractability of exact DNF counting, there has been a line of research into a variety of approximation algorithms. We develop a new Monte Carlo approach with an adaptive stopping rule and short-circuit formula evaluation. We prove it achieves Probably Approximately Correct (PAC) learning bounds and has asymptotically improved time and randomness complexity compared to previous methods. We also show experimentally that it out-performs prior algorithms by at least three orders of magnitude in running time and scalability.

Despite recent advances in training-free text-guided image editing using pretrained rectified flow models, achieving a balance between text adherence and background preservation remains a challenge. Existing methods typically treat image editing as an open-loop trajectory generation task, adopting either an inversion-based or inversion-free paradigm. However, neither can perfectly achieve this goal. Specifically, inversion-based approaches accumulate inversion errors without feedback, whereas inversion-free methods exhibit unstable trajectories due to the lack of constraints. To address this, we propose EKFEdit, a novel framework that formulates image editing as a sequential state estimation problem in a nonlinear dynamic system, which models inversion-free editing trajectories as the system’s prior dynamics and leverages an Extended Kalman Filter to adaptively fuse observations from external editing algorithms. EKFEdit enables adaptive trajectory correction, effectively combining the complementary strengths of the different paradigms. We instantiate this framework into two concrete approaches (EKFEdit-RF and EKFEdit-DNA) via different observation methods, respectively. Extensive experiments demonstrate that our approaches achieve new state-of-the-art performance compared to previous methods. Code is available at https://github.com/baiyeweiguang/EKFEdit.

Backdoor attacks pose a serious threat to deep neural networks, especially when training relies on third-party data, allowing adversaries to inject malicious behaviors through data poisoning. In this work, we reveal that backdoor behaviors tend to be absorbed by a simpler parallel branch when jointly trained with the main network. Motivated by this insight, we propose Trapping and Removing (TR), a simple yet effective training-time defense that introduces a lightweight shortcut branch as a “honeypot” to trap backdoor knowledge. After training, backdoors can be removed by discarding the shortcut, without requiring any additional data. To further enhance backdoor isolation while maintaining benign performance, we design a knowledge decoupling strategy with entropy-based weight assignment, encouraging poisoned samples to flow through the honeypot while guiding the main network to focus on benign learning. In addition, we introduce an automatic shortcut generation strategy to improve generalization across model architectures. Extensive experiments on four benchmark datasets and five model architectures demonstrate that our approach effectively mitigates a wide range of backdoor attacks while preserving performance on benign data. Code: github.com/Zixuan-Zhu/TR.

Diffusion policy has shown impressive performance in robotic manipulation tasks while struggling with out-of-distribution shifts and limited demonstrations. Recent advances primarily focus on improving geometric or perceptual representations for diffusion policy. However, these approaches rely heavily on instantaneous observations, making them vulnerable when visual inputs deviate from the training distribution. Our key insight is that robust generalization in diffusion policy requires both structured reasoning over skill compositions and an explicit memory mechanism for accumulating and reusing learned policy knowledge. To this end, we propose "raise one and infer three" diffusion policy (ROITDP), a novel approach that introduces two complementary mechanisms. First, we propose a reasoning mechanism built upon the Chain-of-Skill Noise Watermark, which encodes skill-level reasoning graph representations into the initial noise space, thereby enabling temporally coherent multi-step reasoning throughout the diffusion process under distribution shifts. We further introduce a memory mechanism in the form of a Self-evolving Policy Knowledge Bank that discretizes spatio-temporally refined trajectories into reusable skill primitives via a VQ-VAE architecture, providing adaptive memory to guide and refine action generation. Extensive experimental results on both simulated and real-world environments demonstrate the superiority and robustness of our method.

With the expanding use of artificial intelligence generated images (AGIs) in scenarios such as gaming, art, and film production, evaluating their quality is essential to ensure their practical utility. To guarantee effective quality measurement, both content and distortion must be considered. However, existing image quality assessment (IQA) methods fail to sufficiently combine the two aspects in their assessments. Meanwhile, the AGIs annotated with credible content and distortion labels are lack, thus, employing cross-domain methods to utilize typically public image datasets is meaningful. Based on the above conclusions, this paper proposed a cross-domain AI-generated IQA via content-distortion awareness (CDAQA). Firstly, the large language model has been utilized to obtain content and distortion expressions of images. Secondly, a dual-stream contrastive language-image pre-training module (DCLIP) has been designed to gain both quality-aware features in images and the corresponding expressions that related to content and distortion, respectively. Thirdly, a graph knowledge transferring module (GKT) that constructs graphs via inter-domain content relevance has been proposed. GKT can update distortion information in the source domain according to the target domain representations. Finally, the cross-domain framework has been designed to update the existing IQA model for AGIs. And, the contrastive loss of DCLIP, feature update loss of GKT, and quality prediction loss are coordinated to jointly update different modules, enabling sufficient fusion of target domain knowledge. Experimental results demonstrate that CDAQA achieves higher accuracy and stability in cross-domain AGIs tasks.