arXiv:2406.19705

DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems

Kexiong Yu, Hang Zhao, Yuhang Huang, Renjiao Yi, Kai Xu, Chenyang Zhu

제출 2024-06-28

원문 초록

Combinatorial Optimization (CO) problems are fundamentally important in numerous real-world applications across diverse industries, characterized by entailing enormous solution space and demanding time-sensitive response. Despite recent advancements in neural solvers, their limited expressiveness struggles to capture the multi-modal nature of CO landscapes. While some research has shifted towards diffusion models, these models still sample solutions indiscriminately from the entire NP-complete solution space with time-consuming denoising processes, which limit their practicality for large problem scales. We propose DISCO, an efficient DIffusion Solver for large-scale Combinatorial Optimization problems that excels in both solution quality and inference speed. DISCO's efficacy is twofold: First, it enhances solution quality by constraining the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions. Second, it accelerates the denoising process through an analytically solvable approach, enabling solution sampling with minimal reverse-time steps and significantly reducing inference time. DISCO delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference time up to 5.28 times faster than other diffusion alternatives. By incorporating a divide-and-conquer strategy, DISCO can well generalize to solve unseen-scale problem instances, even surpassing models specifically trained for those scales.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.09145v2cs.LG공통 태그 Denoising, Combinatorial Optimization

프롬프트에 노이즈 추가하기: 연속 확산 언어 모델에서 조건부 토큰 노이즈화

Noise Your Prompt: Noising Conditioning Tokens in Continuous Diffusion Language Models

본 연구에서는 연속 확산 언어 모델(continuous diffusion language model) 문헌에서 표준적으로 통용되던, 학습(training) 중 조건부 프롬프트(prompt) 토큰을 깨끗한 상태(clean)로 고정하는 관행을 재검토합니다. 우리는 매우 간단한 수정 사항을 적용하여, 학습 중 조건부 프롬프트 토큰에도 노이즈를 추가합니다. 이러한 수정된 학습 목적 함수 하에서 스도쿠(Sudoku) 및 N-퀸(N-Queens)과 같은 조합 추론(combinatorial reasoning) 태스크에서 더 우수한 일반화 성능을 달성함을 입증하였으며, 특히 더 어려운 변형에서 가장 큰 폭의 향상(Sudoku Hard 해결률 $3.73\% \to 24.65\%$)과 생성된 해의 다양성 증가(10x10 N-Queens 커버리지 $50.60\% \to 73.79\%$)를 확인했습니다. 또한 Gigaword 요약을 통한 적당한 데이터셋(dataset) 환경에서 자연어 생성 품질의 측정 가능한 개선을 보여주었으나, 이러한 이점이 모든 자연어 태스크(예: 개방형 대화 생성)로 전이되지는 않음을 명확히 보여줍니다. 본 논문의 방법론은 학습 목적 함수에 단 한 줄만을 변경하는 방식이며, 기본적으로 추가적인 추론(inference) 비용이 발생하지 않고, 분류기 없는 유도(classifier-free guidance)에서 영감을 얻은 유도 샘플링(guided sampling)의 유연성을 제공합니다. 공개된 \href{https://github.com/LateralIntelligence/noise-your-prompt}{코드}를 이용할 수 있습니다.

arXiv:2610.13503v2cs.CV공통 태그 Combinatorial Optimization

SplatQ: 2차 선택을 통한 3D 가우시안 스플래팅의 상호작용 인지 가지치기

SplatQ: Interaction-Aware Pruning of 3D Gaussian Splatting via Quadratic Selection

기존의 3D 가우시안 스플래팅(3DGS) 가지치기(pruning) 방법들은 주로 독립적인 중요도 점수에 기반한 전역 Top-K 선택에 의존하여, 영역별 예산 제어가 부족하고 공동 삭제 효과를 무시합니다. 결과적으로 전체 장면에 걸쳐 균형 잡힌 재구성 품질을 보장하지 못합니다. 본 논문에서는 고정된 예산 하에서 영역별 예산 할당과 공동 가우시안 선택을 조율하는 조합 가지치기 알고리즘인 SplatQ를 제안합니다. SplatQ는 공간적 근접성과 외형 유사성을 기준으로 가우시안을 크기가 제한된 블록으로 분할하여, 전역 선택 문제를 특정 크기의 하위 문제들로 분해합니다. 그런 다음 중요도 기반의 블록 유지 할당량을 평활화하여 과도한 예산 집중을 방지합니다. 마지막으로 가우시안 불투명도 변화에 대한 대표 픽셀 색상의 반응을 활용하여 공동 삭제 효과의 2차 근사를 구성합니다. 개별 반응, 쌍별 상호작용 및 할당량 페널티는 2차 비제약 이진 최적화(QUBO) 목적 함수에 통합되며, 모의 담금질(SA) 또는 코히런트 이징 머신(CIM)을 사용하여 이를 해결함으로써 가우시안을 공동으로 선택합니다. 5개 벤치마크에 대한 실험을 통해 SplatQ가 종합적인 재구성 품질, 공간적 품질 균형, 렌더링 속도 측면에서 최신 가지치기 방법들보다 우수한 성능을 보임을 입증합니다. 절제 연구(ablation)를 통해 예산 평활화가 국소적인 세부 표현 재구성을 향상시키는 한편, 상호작용 모델링이 고정된 예산 하에서 가우시안 선택 품질을 향상시킴을 확인합니다.

arXiv:2609.27901v2cs.CV공통 태그 Denoising

모든 모달리티는 동등하지만, 비디오는 더 동등하다: 공동 비디오 생성에서 크로스-어텐션 격차 줄이기

All modalities are equal, but video is more equal: Closing the Cross-Attention Gap in Joint Video Generation

비디오는 외형, 기하학, 모션, 시간적 변화를 포착하여 물리적 사건을 풍부하게 표현합니다. 3D 신체 모션이나 오디오와 같은 다른 모달리티(modality)는 동일한 사건의 더 좁은 측면만을 인코딩합니다. 본 연구에서는 공동 멀티모달 확산 트랜스포머(joint multimodal diffusion transformer)가 교차 모달 대응(cross-modal correspondence)에서 그에 상응하는 비대칭성을 보임을 발견했습니다. 즉, 동반 모달리티는 비디오에 대해 강한 대응성을 형성하지만, 이들이 비디오를 제약하는 상호 대응성(reciprocal correspondence)은 실질적으로 훨씬 약하게 유지됩니다. 저자들은 두 방향을 비디오 토큰(token)에 대한 비교 가능한 대응 분포로 표현하고, 이들의 불일치를 상호 대응 격차(reciprocal correspondence gap)로 정의합니다. 또한 상호 교차 모달 어텐션 정규화(Reciprocal Cross-modal Attention Regularization)를 뜻하는 RecCAR를 제안합니다. 이는 이미 잘 확립된 비디오-모달리티 간 대응을 고정된 참조 기준으로 삼고, 더 취약한 모달리티-비디오 간 대응을 이에 맞춰 정렬하는 KL 정규화(regularizer) 기법입니다. 공동 비디오-모션 및 비디오-오디오 생성 전반에 걸쳐, RecCAR는 전반적인 생성을 개선하면서도 Human Anatomy 점수를 0.69에서 0.75로 향상시키고 오디오-비디오 비동기화(desynchronization)를 0.804에서 0.752로 감소시킵니다

arXiv:2609.14856v3cs.CV공통 태그 Denoising

RAIN: 시맨틱 워터마크 추출을 위한 영역 인식 역전 네트워크

RAIN: Region-Aware Inversion Network for Semantic Watermark Extraction

확산 모델을 위한 시맨틱 워터마크는 시각적 품질을 보존하면서 생성 과정에 소유권 정보를 삽입하지만, 전통적으로 Gaussian-Shading 추출은 초기 노이즈를 복구하기 위해 다단계 확산 역전(multi-step diffusion inversion)을 필요로 합니다. 최근의 1단계(one-step) 방식들은 이러한 비용을 크게 줄일 수 있음을 보여줍니다. 본 연구에서는 확장된 플로우 매칭(extended flow matching)과 조건부 회귀(conditional regression)를 통해 이 문제를 다룹니다. 핵심 관찰은 높은 신호 대 잡음비(high-SNR) 이미지 종점 근처에서 고 SNR 영역의 확장된 플로우 매칭 첫 단계 출력으로 주어지는 유용한 노이즈 통계량을 복구하는 것이 전체 역전 궤적(inverse trajectory)을 재구성하는 것보다 훨씬 단순하며, Gaussian Shading은 복구된 잠재 변수(latent)가 올바른 워터마크 결정 영역 내에 유지되기만 하면 된다는 점입니다. 이러한 관찰을 바탕으로, 종점 복구를 이미지와 유사한 앵커와 노이즈 지향적 잔차로 분해하여 GPU 병렬 연산 활용 능력을 향상시키는 경량 프롬프트-프리 추출기를 제안합니다. 이를 통해 얻어진 방법은 반복적인 역전과 확산 규모 U-Net의 반복 평가(evaluation)를 피함으로써, 간결한 이론적 해석을 갖춘 효율적인 1단계 추출 파이프라인을 제공합니다. 노이즈 추출의 연산 비용은 OSI와 FARI 모두보다 낮습니다. GitHub 저장소는 https://github.com/TheLovesOfLadyPurple/RAIN-lightweight-NN-for-one-step-semantic-watermark-extraction 에서 확인할 수 있습니다.

arXiv:2609.27149v2cs.CV공통 태그 Denoising

원격 탐사 변화 탐지를 위한 시간 순서화된 영역 토큰 Mamba와 로짓 공간 확산 모델

Temporally Ordered Region-Token Mamba with Logit-Space Diffusion for Remote Sensing Change Detection

원격 탐사의 변화 탐지(Change Detection, CD)는 변화된 영역을 정확히 위치시키기 위해 이시점 문맥과 세밀한 공간적 세부 정보를 함께 모델링해야 한다. 밀집 어텐션은 이시점 관계를 효과적으로 포착하지만, 계산 비용 때문에 고해상도 영상으로의 확장성이 제한된다. 반면 기존의 특징 융합과 거친 디코딩은 실제 변화와 외형 변이를 구별하고 객체 경계를 보존하는 데 어려움을 겪는 경우가 많다. 이러한 한계를 극복하기 위해, 우리는 시간적으로 구조화된 상태 공간 모델링과 로짓 공간 확산 정제를 통합한 프레임워크인 BMD-CD(Bitemporal Mamba-Diffusion for Change Detection)를 제안한다. BMD-CD는 먼저 심층 이시점 특징을 영역 토큰으로 변환하고 이를 명시적인 시간 분할로 조직하여 양방향 상태 공간 전파를 수행한다. 이어서 시간 정보를 통합하는 학습 가능한 삼각 융합(Learnable Trigonometric Fusion, LTF) 모듈과, 짧은 DDIM 스케줄로 로짓 공간에서 거친 예측을 정제하여 세밀한 고해상도 변화 지도를 생성하는 조건부 확산 디코더를 사용한다. LEVIR-CD, WHU-CD, DSIFN-CD, CDD, S2Looking에서의 광범위한 실험을 통해 제안 방법의 효과를 입증한다. BMD-CD는 WHU-CD, DSIFN-CD, LEVIR-CD, CDD에서 각각 0.923, 0.957, 0.882, 0.979의 IoU 점수를 달성하며, ValaisCD와 B-FLAIR-test에서도 강력한 제로샷 견고성을 보인다.

arXiv:2607.14836v2cs.CV공통 태그 Denoising

3D 수어 생성을 위한 확산 기반 운동학 및 동역학 모델

A Diffusion-Based Kinematics and Dynamics Model for 3D Sign Language Production

수어 생성(SLP)은 언어적 입력으로부터 연속적인 수어 동작을 생성하며 수어 아바타와 같은 접근성 기술을 구동한다. 확산 모델을 포함한 현재의 생성기는 관절 좌표를 구조 없는 벡터로 회귀하므로, 생성된 신체가 해부학이나 운동의 역학을 따르도록 보장하는 요소가 없다. 물리학은 기하학적 손실 항을 통해서만 SLP에 도입되었으며 그 이점이 이해도에 미치는 영향은 검증되지 않았고, 수어를 하는 신체의 동역학은 모델링되지 않았다. 본 논문은 두 수준에서 물리 정보를 활용하는 확산 모델 PIDiffSign을 제안한다. 운동학 측면에서는 순기구학 헤드가 뼈의 방향과 길이를 출력하고 이를 조합하여 해부학적으로 정확한 골격을 구성한다. 동역학 측면에서는 인체측정학적 매개변수를 갖는 상체 강체 모델이 두 가지 학습 사전분포를 뒷받침한다. 운동 제어의 두 법칙을 포함하는 물리적 타당성 평가 모음이 생성된 수어를 평가한다. 통제된 프로토콜에서 이 헤드는 PHOENIX14T와 CSL-Daily에서 역번역 단어 오류율을 약 5포인트 낮추는 반면 기하학적 페널티는 측정 가능한 효과가 없으며, 대조 실험은 이득이 뼈 길이 보존이 아니라 운동학적 사슬 표현에서 비롯됨을 추적한다. 동역학 사전분포는 PHOENIX14T에서 물리적이지 않은 대응 대조군보다 약 1포인트 추가 이득을 주지만 CSL-Daily에서는 그렇지 않다. 생성된 수어는 운동 제어 법칙을 실제 수어만큼 근접하게 따르지만 운동 에너지는 현저히 적다. 정확한 골격은 리깅된 아바타를 직접 구동할 수 있으며, 이 평가 모음은 향후 SLP 시스템을 위한 물리적 벤치마크를 제공한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.