NeurIPS 2026 Papers

Conference on Neural Information Processing Systems

Decision breakdown

6,437papers

Counted from the official paper list; may differ slightly from the number the conference announced.

  • Oral
    991.5%
  • Spotlight
    2403.7%
  • Poster
    6,09894.7%

Browse all papers

UniVLR: Unifying Text and Vision in Visual Latent Reasoning for Multimodal LLMs

Houcheng Jiang, Jiajun Fu, Junfeng Fang, Chen Gao, Xiang Wang, Xiangnan He, Yong Li

Expand abstract

Multimodal large language models are increasingly expected to perform \emph{thinking with images}, yet existing visual latent reasoning methods still rely on explicit textual chain-of-thought interleaved with visual latent tokens. This interleaved design limits efficiency and keeps reasoning fragmented across separate text and vision channels. We propose **UniVLR**, a unified visual latent reasoning framework that treats textual reasoning and auxiliary visual evidence as a shared visual workspace. Instead of preserving text CoT as an independent inference-time path, UniVLR renders reasoning traces together with auxiliary images and learns to compress this unified representation into compact visual latent tokens. At inference time, the model reasons only through visual latents and directly decodes the final answer, avoiding both external tool calls and verbose text reasoning. Experiments on real-world perception and visual reasoning tasks show that UniVLR outperforms prior visual latent reasoning methods while using substantially fewer generated reasoning tokens, suggesting a more unified and efficient paradigm for visual thinking in MLLMs. Our code is available at: https://anonymous.4open.science/r/UniVLR-1B0C/.

Poster
UniSHARP: Universal Sharp Monocular View Synthesis

Meixi Song, Dizhe Zhang, Ruiyang Zhang, Bo Du, Ming-Hsuan Yang, Lu Qi

Expand abstract

In this work, we focus on extending SHARP, the popular photorealistic view synthesis method, for universal monocular rendering across diverse camera systems, such as large-field-of-view fisheye lenses. To overcome the pinhole-specific assumptions of SHARP, our key idea is to align various images in a unified omnidirectional latent space. Thus, we propose UniSHARP, which performs implicit alignment in both feature and Gaussian spaces. Specifically, 2D semantic embeddings and 3D spatial features are jointly encoded and decoded by UniK3D to support Gaussian construction, while a ray-based universal representation organizes Gaussian primitives along rays and radial distances. To comprehensively evaluate our method, we construct a benchmark covering diverse imaging systems, including pinhole, fisheye and panoramic cameras, across various scenes. The benchmark is further stratified by field of view, spanning narrow perspective, wide-FoV, fisheye, and full panoramic settings. Extensive experiments on the proposed benchmark demonstrate the effectiveness of UniSHARP, outperforming alternative methods by a large margin. Our models, training code, and dataset will be publicly available.

Poster
UniRank: Unified List-wise Reranking via Confidence-Ordered Denoising

Pengyue Jia, HailanYang, Shuchang Liu, Xiaobei Wang, Wanyu Wang, Xiang Li, Yongqi Liu, Kaiqiao Zhan, Kun Gai, Xiangyu Zhao

Expand abstract

List-wise reranking arranges a request-specific pool of candidate items into an ordered slate that maximizes user satisfaction. Existing generative rerankers fall into two paradigms: Autoregressive (AR) rerankers construct the slate left to right and capture inter-item dependencies in the exposure list, but they suffer from error propagation because early mistakes affect subsequent slots. Non-autoregressive (NAR) rerankers predict all slots in parallel and avoid error propagation, but they weaken inter-item interaction modeling under a slot independence assumption. This raises a central question: is there a unified architecture that combines the strengths of both paradigms and delivers stronger reranking performance? We answer this question with UniRank, a unified list-wise reranking framework whose inference time variants recover AR and NAR rerankers as special cases. UniRank integrates bidirectional slate modeling into an iterative denoising process and fills the most confident slot at each step. To instantiate this framework for reranking, we introduce the Task Grounded Diffusion Interface (TGD), which performs denoising at the item level and restricts prediction to the request-specific candidate pool. TGD aggregates each item's semantic tokens into a single item embedding and scores each slot directly against the candidate pool. Experiments on Amazon Books, MovieLens-1M, and an industrial short video dataset show that UniRank consistently outperforms state-of-the-art baselines. Our code is available online.

Poster
UniRAP: Towards Unified Part-level Physical Affordance Reasoning and Actionable Perception

Linfei Li, Ruining Hu, Lin Zhang, Zhong Wang, Fengyi Zhang, Ying Shen, Binqiang Wang, Xin Zhang

Expand abstract

Vision-language perception has achieved impressive progress in aligning natural language with visual observations, yet grounding high-level semantics into part-level physical interaction remains challenging. To address this gap, we propose UniRAP, a unified model for inferring part-level physical affordances and mapping language instructions to actionable geometric representations. UniRAP formulates this problem as a conditional multimodal generation task, integrating visual inputs, textual instructions, and optional prompts into a shared spatiotemporal representation space through a unified interface token mechanism. To predict executable contact geometry, we introduce a Unified Affordance Decoder (UAD), which jointly performs object detection, part-level affordance segmentation, and 4-DoF interaction pose estimation by leveraging intermediate segmentation features. In addition, we propose a curriculum-based transfer training strategy that progressively adapts the model from general visual parsing to interaction-aware perception, improving data efficiency under limited textual annotations. Experiments show that UniRAP achieves state-of-the-art performance on referring expression segmentation, affordance grounding, and interaction pose estimation, while maintaining strong spatiotemporal consistency in dynamic video scenarios. These results demonstrate the effectiveness of UniRAP as a unified perception framework for language-guided physical manipulation. All data and code will be made publicly available.

Poster
UniPrefill: Universal Long-Context Prefill Acceleration via Block-wise Dynamic Sparsification

Qihang Fan, Huaibo Huang, zhiyingwu, Bingning Wang, Ran He

Expand abstract

As large language models (LLMs) continue to advance rapidly, they are becoming increasingly capable while simultaneously demanding ever-longer context lengths. To improve the inference efficiency of long-context processing, several novel low-complexity hybrid architectures have recently been proposed, effectively alleviating the computational burden of long-context inference. However, existing research on long-context prefill acceleration remains predominantly focused on sparse attention mechanisms, which achieve their maximum speedup only on full-attention models. When transferred to emerging architectures — such as linear/full attention hybrids or sliding window/full attention hybrids — these prefill acceleration approaches suffer significant performance degradation. Furthermore, such methods are generally incompatible with continuous batching, making them difficult to integrate into modern inference engines such as vLLM. To this end, we propose UniPrefill, a prefill acceleration framework applicable to virtually any model architecture, which directly accelerates the model's computation at the token level. We further implement UniPrefill as a continuous batching operator and extend vLLM's scheduling strategy to natively support prefill-decode co-processing for UniPrefill, enabling its seamless integration into vLLM. UniPrefill achieves up to 2.1x speedup in Time-To-First-Token (TTFT), with the acceleration becoming increasingly pronounced as the number of concurrent requests grows.

Poster
UniPath: Adaptive Coordination of Understanding and Generation for Unified Multimodal Reasoning

Haoyue Bai, Yinyi Luo, Wenwen Wang, Qingsong Wen, Jindong Wang

Expand abstract

Unified multimodal models (UMMs) aim to integrate understanding and generation within a single architecture. However, it remains underexplored how to effectively coordinate these two capabilities for more effective and efficient reasoning. Existing coordination approaches either perform coupling during training, without explicit inference-time coordination, or impose a fixed coordination pattern for all inputs. In this work, we show that multimodal tasks exhibit substantial coordination-path diversity: different inputs favor different coordination paths. This suggests that exploiting such diversity is key to improving performance. We propose UniPath, a framework for adaptively modeling and exploiting coordination-path diversity. Instead of enforcing a single coordination pattern, we represent task solving as the selection and execution of a path, ranging from direct answering to textual inference, visual-thought construction, and hypothesis-based exploration. We construct role-aligned trajectories to train a path-conditioned executor and introduce a lightweight planner mechanism to enable input-dependent path selection. Experiments show that leveraging coordination-path diversity improves performance over fixed coordination strategies while providing interpretable intermediate behaviors. The code is available at: https://anonymous.4open.science/r/UniPath.

Poster
UniGS: Unified Geometry-Aware Gaussian Splatting for Multimodal Rendering

Yusen Xie, Zhenmin Huang, Jianhao Jiao, Dimitrios Kanoulas, Jun Ma

Expand abstract

In this paper, we propose UniGS, a unified map representation and differentiable framework for high-fidelity multimodal 3D reconstruction based on 3D Gaussian Splatting. Our framework integrates a CUDA-accelerated rasterization pipeline capable of rendering photo-realistic RGB images, geometrically accurate depth maps, consistent surface normals, and semantic logits simultaneously. We redesign the rasterization to render depth via differentiable ray-ellipsoid intersection rather than using Gaussian centers, enabling effective optimization of rotation and scale attribute through closed-form analytic depth gradients. Furthermore, we derive the analytic gradient formulation for surface normal rendering, ensuring geometric consistency among the reconstructed 3D scenes. To improve computational and storage efficiency, we introduce a learnable attribute that enables differentiable pruning of Gaussians with minimal contribution during training. Quantitative and qualitative experiments demonstrate the state-of-the-art reconstruction accuracy across several datasets, validating the efficacy and robust optimization stability of our geometry-aware paradigm.

Poster
UniFunc3D: Unified Active Spatial-Temporal Grounding for 3D Affordance Segmentation

Jiaying Lin, Dan Xu

Expand abstract

Affordance segmentation in 3D scenes requires an agent to ground implicit natural-language instructions into precise masks of fine-grained interactive elements. Existing training-free methods typically rely on fragmented pipelines, which introduce visual blindness during task parsing and limit accuracy through single-scale spatial and temporal processing. We present UniFunc3D, a unified and training-free framework that treats the multimodal large language model as an active observer. By consolidating semantic, temporal, and spatial reasoning into a single forward pass, UniFunc3D performs joint reasoning to ground task decomposition in direct visual evidence. Our approach introduces active spatial-temporal grounding with a coarse-to-fine strategy. This allows the model to select correct video frames adaptively and focus on high-detail interactive parts while preserving the global context necessary for disambiguation. On SceneFun3D, our UniFunc3D achieves state-of-the-art performance, surpassing prior training-free methods by a large margin with a relative 59.9\% mIoU improvement, and even outperforming training-based methods without any task-specific training. Code will be released.

Poster
UniFlowDock: Flexible Docking with Complete Equivariant Velocity Fields

Kangxin Chen, Jieyu Zhao, Xulun Ye, Kun Zhou, Jinli Hu, Yuanyuan Deng, Min Xie

Expand abstract

Flexible molecular docking is crucial for drug discovery; however, existing flow-matching generative models often produce physically invalid conformations (e.g., steric clashes, distorted bond geometry). Our analysis suggests that a primary contributor to this challenge lies at the modeling level: when the flow is parameterized by standard equivariant networks, an intrinsic approximation floor can emerge, potentially hindering the learned velocity field from reaching its optimal convergence bound, particularly for highly flexible molecules. We present UniFlowDock, which addresses this by introducing strictly Complete Equivariant Velocity Fields, thereby eliminating the dimensional incompleteness of standard architectures. This theoretical completeness is further bolstered by Fragment-Adaptive Optimal Coupling, a method that structurally linearizes transport trajectories and decomposes the generation process into physics-aware subproblems. Experiments on PDBBind and PoseBusters demonstrate UniFlowDock achieves state-of-the-art accuracy and physical validity, showing consistent gains in highly flexible docking scenarios where target distributions exhibit higher transport complexity.

Poster
UniCustom: Unified Visual Conditioning for Multi-reference Image Generation

Yiyan Xu, Qiulin Wang, Wenjie Wang, Yunyao Mao, Xintao Wang, Pengfei Wan, Kun Gai, Fuli Feng

Expand abstract

Multi-reference image generation aims to synthesize images from textual instructions while faithfully preserving subject identities from multiple reference images. Existing VLM-enhanced diffusion models commonly rely on decoupled visual conditioning: semantic ViT features are processed by the VLM for instruction understanding, whereas appearance-rich VAE features are injected later into the diffusion backbone. Despite its intuitive design, this separation makes it difficult for the model to associate each semantically grounded subject with visual details from the correct reference image. As a result, the model may recognize which subject is being referred to, but fail to preserve its identity and fine-grained appearance, leading to attribute leakage and cross-reference confusion in complex multi-reference settings. To address this issue, we propose UniCustom, a unified visual conditioning framework that fuses ViT and VAE features before VLM encoding. This early fusion exposes the VLM to both semantic cues and appearance-rich details, enabling its hidden states to jointly encode the referred subject and corresponding visual appearance with only a lightweight linear fusion layer. To learn such unified representations, we adopt a two-stage training strategy: reconstruction-oriented pretraining that preserves reference-specific appearance details in the fused hidden states, followed by supervised finetuning on single- and multi-reference generation tasks. We further introduce a slot-wise binding regularization that encourages each image slot to preserve low-level details of its corresponding reference, thereby reducing cross-reference entanglement. Experiments on two multi-reference generation benchmarks demonstrate that UniCustom consistently improves subject consistency, instruction following, and compositional fidelity over strong baselines. Our code, checkpoints, and the training dataset will be released soon.

Poster
UniCon3R: Unified Contact-aware 4D Human-Scene Reconstruction from Monocular Video

Tanuj Sur, Shashank Tripathi, Nikos Athanasiou, Ha Linh Nguyen, Kai Xu, Michael Black, Angela Yao

Expand abstract

We introduce $\textbf{UniCon3R}$, a unified feed-forward framework for online human-scene 4D reconstruction from monocular video. Current feed-forward human-scene reconstruction methods suffer from artifacts, where bodies float above the ground or penetrate parts of the scene. A key reason is the lack of effective interaction modelling between the human and the environment. Our goal is to exploit contact between the human and the scene during inference to actively improve the human mesh reconstruction. To that end, we explicitly model interaction by inferring 4D contact from the human pose and scene geometry and use the contact as a corrective cue for generating the pose. This enables UniCon3R to jointly recover scene geometry and spatially aligned 4D humans within the scene. Experiments on standard human-centric video benchmarks show that UniCon3R outperforms state-of-the-art baselines on physical plausibility and global human motion estimation while preserving fast, feed-forward inference speeds. The results validate our central claim: contact serves as a powerful internal prior, thus establishing a new paradigm for physically grounded joint human-scene reconstruction. Source code and models will be released upon acceptance.

Poster
UniClawBench: A Universal Benchmark for Proactive Agents on Real-World Tasks

Zhekai Chen, Chengqi Duan, Kaiyue Sun, Bohao Li, Yuqing Wang, Manyuan Zhang, Xihui Liu

Expand abstract

The rapid development of large language models and multimodal large language models has accelerated the emergence of proactive agents capable of operating everyday tools and assisting users in real-world environments. However, existing benchmarks struggle to evaluate such agents effectively, as they often rely on sandboxed environments and single-turn evaluation paradigms. Moreover, their scenario-based task taxonomies mix multiple model capabilities within the same task category, making it difficult to identify the root causes of agent failures. To address these limitations, we introduce UniClawBench, the first capability-driven benchmark designed to evaluate proactive agents in dynamic, real-world settings. UniClawBench is built around five foundational model capabilities: Skill Usage, Exploration, Long-Context Reasoning, Multimodal Understanding, and Cross-Platform Coordination. Based on these capabilities, we design 400 bilingual real-world tasks. Unlike previous benchmarks that rely on static, pre-recorded answers, our benchmark evaluates agents in live Docker containers using fine-grained, step-by-step completion checkpoints. Furthermore, we design a closed-loop evaluation strategy comprising an executor agent, a hidden supervisor agent, and a user agent to simulate realistic multi-turn human feedback without leaking grading criteria. To disentangle base model capabilities from framework-level design choices, we evaluate state-of-the-art models under multiple agent frameworks. Through comprehensive comparisons across both models and frameworks, we show how base model capabilities and agent framework designs jointly shape performance in real-world environments.

Poster
Uni-Synergy: Bridging Understanding and Generation for Personalized Reasoning

zijun shen, Ruichuan An, Sihan Yang, Ziyu Guo, Hao Liang, Ming Lu, Renrui Zhang, Wentao Zhang

Expand abstract

Unified Multimodal Models (UMMs) excel in general tasks but struggle to bridge the gap between personalized understanding and generation. Prior works largely rely on implicit token-level alignment via supervised fine-tuning, which fails to fully capture the potential synergy between comprehension and creation. In this work, we propose Sync-R1, an end-to-end reinforcement learning framework that jointly optimizes personalized understanding and generation within a single, explicit reasoning loop. Through this unified feedback process, Sync-R1 enables personalized comprehension to guide content creation, while the resulting generation quality reciprocally refines understanding within an integrated reward landscape. To efficiently orchestrate this dual-task synergy, we introduce Sync-GRPO, a reinforcement learning method utilizing an ensemble reward system. Furthermore, we propose Dynamic Group Scaling (DGS), which adaptively filters low-potential trajectories to reduce gradient variance and accelerate convergence. To better reflect real-world complexity, we introduce UnifyBench++, featuring denser textual descriptions and richer user contexts. Experimental results demonstrate that Sync-R1 achieves state-of-the-art performance, showcasing superior cross-task reasoning and robust personalization without requiring complex cold-start procedures.

Poster
UnfoldArt: Zero-Shot Recovery of Full Articulated 3D Objects from Text or Image

Mohamed El Amine Boudjoghra, Ivan Laptev, Angela Dai

Expand abstract

Articulated 3D objects are essential for interactive environments in embodied AI, robotics, and virtual reality, but reconstructing their structure and motion from sparse observations remains challenging. Existing approaches remain largely constrained by lack of supervised data or lack priors needed to reliably recover articulation, hidden geometry, and internal object structure. We present the first hierarchical agentic approach for articulated 3D object reconstruction from text or image inputs, combining hierarchical, debate-based reasoning with a video generative prior for articulation modeling. High-level agents reason about object semantics and motion using knowledge from vision-language and video models, while low-level agents estimate articulation parameters and interaction points; together, they engage in structured debate to resolve ambiguities in structure and motion. To enable reliable generation, including interior object structures, from only text or image inputs, we introduce a video generative model prior that not only synthesizes plausible object motions, but also expose occluded interiors and geometry that cannot be inferred from a single static view. By combining agentic reasoning with a video generative prior, our approach jointly infers articulation and reconstructs complete 3D articulated objects, producing high-fidelity geometry, internal structure, and motion-consistent states beyond directly observed surfaces.

Poster
Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs

Nuojing Liang, Xiaotong Yuan, Pan Zhou

Expand abstract

Chain-of-Thought (CoT) reasoning substantially improves Large Language Models (LLMs), yet its out-of-distribution (OOD) generalization mechanism remains theoretically underexplored. We study CoT as compositional OOD generalization: the target task lacks complete reasoning trajectories or direct input-output pairs, while training provides only in-distribution (ID) atomic step data. We show that CoT generalizes by repeatedly applying a shared single-step predictor to compose reusable ID transitions. Theoretically, the OOD task risk is controlled by the sum of ID subtask risks, with an error-propagation coefficient independent of reasoning depth/steps $T$. A Rademacher-complexity analysis further gives a generalization gap of $\mathcal{O}(\sqrt{T/n})$, rather than linear in $T$, due to predictor sharing, where $n$ denotes training samples per subtask. For autoregressive Next-Token Prediction, we derive an explicit bound $\mathcal{O}\big(k\big(\sqrt{{T}/{mn}}+\sqrt{{T}/{n}}+{T}/{m}\big)\big)$, where $m$ and $k$ denote context length and output token number per step. Experiments on Atom-Task and GSM8K support the theory, showing that CoT enables short-to-long and compositional generalization, while explicit state tracking is crucial.

Poster
Understanding the Interplay between Memorization and Learning in Large Language Models

Bishwamittra Ghosh, Soumi Das, Qinyuan Wu, Mohammad Aflah Khan, Deepak Garg, Krishna Gummadi, Evimaria Terzi

Expand abstract

We investigate foundational questions about the interplay between memorization and learning in large language models (LLMs). When an LLM generates a string, can we disentangle the roles of rote memorization and contextual learning? Rote memorization results in an LLM regurgitating specific details of a training string, while contextual learning leads to the generation of new strings that follow generalizable patterns of the underlying language. Related questions of interest include: can an LLM avoid memorization when optimally learning a language?, and if not, can we design training schemes to reduce memorization and improve learning? To address these questions, we propose contextual memorization, a new measure that precisely disentangles memorization from learning. Using this measure, we establish that different training strings are memorized at different epochs in training, and that memorization of some training strings is unavoidable when optimally learning a language. Finally, we propose memorization-aware training, a scheme that dynamically down-samples training strings based on their memorization, and in doing so, equalizes learning across strings, reduces memorization, and improves learning. Our conclusions are supported by extensive experiments on multiple LLMs using formal languages as a controlled testbed, enabling precise language specification, exact string sampling, and elimination of data contamination; and further validated on natural languages.

Poster
Understanding the Effects of Hyper-Connections on Self-Attention Dynamics: A Bifurcation Analysis

Yen N Pham, Dung V Nguyen, Trinh Nguyen, Thieu Vo, Tan Nguyen

Expand abstract

A central challenge in understanding deep sequence models is characterizing how token representations evolve across layers: whether they collapse, diverge, or converge to nontrivial structures. We study this question for Transformers with hyper-connections, whose learnable cross-layer coupling makes the stability of representation collapse analytically tractable. In contrast to standard residual connections, hyper-connections introduce additional parameters that directly control the hyperbolicity of the zero fixed point, at which the local stability is fully determined by the Jacobian eigenvalues, thereby enabling a rigorous and precise bifurcation analysis of the dynamical system underlying the model. In particular, we derive a continuous-depth ODE limit of self-attention with hyper-connections and use bifurcation theory to characterize its token dynamics. For the 1-stream case, we obtain a closed-form critical threshold at which a pitchfork bifurcation occurs, separating representation collapse from divergence or convergence to nontrivial stable states. For the 2-stream case, the richer coupling structure yields two distinct stability boundaries, corresponding to qualitatively different instabilities: one arising when a real eigenvalue crosses zero, altering the number of nearby equilibria (static type), and another when a complex-conjugate pair reaches the imaginary axis, leading to oscillatory behavior (Hopf type). These phenomena have no counterpart in the 1-stream setting. Experiments on pretrained hyper-connected language models validate our theory and show that unstable regimes yield stronger performance.

Poster
Understanding the Curse of Unrolling

Sheheryar Mehmood, Florian Knoll, Peter Ochs

Expand abstract

Algorithm unrolling is ubiquitous in machine learning, particularly in hyperparameter optimization and meta-learning, where Jacobians of solution mappings are computed by differentiating through iterative algorithms. Although unrolling is known to yield asymptotically correct Jacobians under suitable conditions, recent work has shown that the derivative iterates may initially diverge from the true Jacobian, a phenomenon known as the curse of unrolling. In this work, we provide a non-asymptotic analysis that explains the origin of this behavior and identifies the algorithmic factors that govern it. We show that truncating early iterations of the derivative computation mitigates the curse while simultaneously reducing memory requirements. Finally, we validate our theoretical findings both on synthetic problems and in a meta-learning setting for few-shot classification, where we study the behavior of gradients obtained via unrolling and implicit differentiation.

Poster
Understanding the Convergence of Direct Training of SNNs with Surrogate Gradients

Zelin Wei, Tianxing Man, Wanli Shi, Bin Gu

Expand abstract

Spiking Neural Networks (SNNs) offer high energy efficiency, but direct optimization is challenging because spike generation is governed by a non-differentiable hard threshold. Practical direct-training methods, including surrogate gradients (SG) and local zeroth-order (LocalZO) estimators, maintain hard spikes in the forward pass while using surrogate or perturbation-induced derivatives in the backward pass. This forward--backward mismatch raises a central theoretical question: how do local gradient discrepancies propagate through the spatiotemporal computation graph, and can the resulting biased updates still provide guaranties for the original discrete-spike objective? We develop a unified convergence analysis framework for SG and LocalZO direct SNN training. A smoothed spike objective is introduced only as an analytical bridge, allowing us to separate the core error into two components: the gradient-level mismatch between the direct-training mean direction and the smoothed-objective gradient, and the objective-level consistency gap between the smoothed and original discrete objectives. Both components are controlled by a threshold-tail functional that measures how often hard-trajectory membrane potentials lie near the firing threshold. Under suitable regularity assumptions, we obtain a non-asymptotic guarantee for the original discrete-spike objective. Experiments across representative SNN architectures and benchmarks verify convergence consistency, the existence of errors, and demonstrate that the threshold-tail statistic is an effective diagnostic for direct SNN training.

Poster
Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Minimal Communication Gives Maximal Speed-Ups

Benjamin Doerr, Moaad Elmoutassim, Martin S. Krejca, Guy Mushiata Kibulu

Expand abstract

Besides domination-based algorithms such as the NSGA-II, the decomposition-based MOEA/D is one of the most popular and successful optimization heuristic for multi-objective problems. It decomposes the problem into several, single-objective subproblems. By solving these in a co-evolutionary manner and archiving non-dominated solutions, it approximates or computes the Pareto front. Interestingly, so far no advantages from the co-evolutionary communication of subproblem solutions were proven. In this first mathematical runtime analysis addressing this research question, we investigate how the mutation-based MOEA/D solves the classic OMM benchmark when solutions are exchanged among subproblems in different distances $r$. We show, for the first time, that the MOEA/D profits from an exchange of solutions, and that already very small communication radii $r$ are sufficient to maximally profit from this feature of the algorithm. More precisely, for all values $r \ge 1$ we prove a tight runtime guarantee of $\Theta(n^2)$, where $n$ is the problem size. This is asymptotically faster than the known bound of $O(n^2 \log n)$ guarantee for $r=0$, which we complement with a matching bound of $\Omega(n^2 \log n)$.

Poster