Inference in Graphical Models via Semidefinite Programming Hierarchies
원문 초록
Maximum A posteriori Probability (MAP) inference in graphical models amounts to solving a graph-structured combinatorial optimization problem. Popular inference algorithms such as belief propagation (BP) and generalized belief propagation (GBP) are intimately related to linear programming (LP) relaxation within the Sherali-Adams hierarchy. Despite the popularity of these algorithms, it is well understood that the Sum-of-Squares (SOS) hierarchy based on semidefinite programming (SDP) can provide superior guarantees. Unfortunately, SOS relaxations for a graph with $n$ vertices require solving an SDP with $n^{\Theta(d)}$ variables where $d$ is the degree in the hierarchy. In practice, for $d\ge 4$, this approach does not scale beyond a few tens of variables. In this paper, we propose binary SDP relaxations for MAP inference using the SOS hierarchy with two innovations focused on computational efficiency. Firstly, in analogy to BP and its variants, we only introduce decision variables corresponding to contiguous regions in the graphical model. Secondly, we solve the resulting SDP using a non-convex Burer-Monteiro style method, and develop a sequential rounding procedure. We demonstrate that the resulting algorithm can solve problems with tens of thousands of variables within minutes, and outperforms BP and GBP on practical problems such as image denoising and Ising spin glasses. Finally, for specific graph types, we establish a sufficient condition for the tightness of the proposed partial SOS relaxation.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
프롬프트에 노이즈 추가하기: 연속 확산 언어 모델에서 조건부 토큰 노이즈화
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}{코드}를 이용할 수 있습니다.
분류 성능의 지표로서 라이프-유사 네트워크 오토마타 규칙의 형태 불규칙성
Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance
복잡 네트워크(Complex Network, CN) 분류는 스케일 불변(scale-invariant)이면서도 계산적으로 효율적인 고수준의 구조적 특성화를 필요로 합니다. 라이프-유사 네트워크 오토마타(Life-Like Network Automata, LLNA) 기반 방법은 사전에 제공된 특징 없이도 창발적 시간 패턴을 활용하여 네트워크 기술자(descriptor)를 추출하는 흥미로운 방식을 제공하지만, 그 효과는 오토마타 전이 규칙의 선택이라는 높은 비용의 조합 최적화 문제로 인해 병목 현상을 겪습니다. 기존 연구들은 대규모 응용에 실현 불가능한 전수 탐색(exhaustive search)에 의존하는 반면, 본 연구는 규칙 공간이 LLNA 전이 함수와 톱니 형태의 유사성을 정량화하는 '들쭉날쭉함(jaggedness)'이라는 특성으로 근본적으로 구조화되어 있음을 밝힙니다. 우리는 이 지표가 혼돈성(chaoticity)과 민감도(sensitivity)에 대한 이론적 대리 지표로 작용함을 입증하며, 이러한 특성은 네트워크 범주 간의 식별력 있는 동적 동작을 생성하는 데 필수적입니다. 나아가, 우리는 들쭉날쭉함을 활용하여 규칙 선택을 유도하는 휴리스틱 탐색 전략을 도입합니다. 실험 결과에 따르면 본 접근법은 전수 탐색 방식에 비해 계산 오버헤드를 90% 줄이면서도 전역 최적값 대비 5% 이내의 분류 정확도를 달성합니다. 우리의 발견은 패턴 인식을 위한 오토마타 기반 방법을 최적화하는 새롭고 효율적인 프레임워크를 제공합니다.
JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증
JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs
복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.
SpectralCache: 스펙트럼 특징 캐싱을 통한 확산 기반 월드 모델 가속화
SpectralCache: Accelerating Diffusion-Based World Models via Spectral Feature Caching
확산(diffusion) 기반 월드 모델은 고품질의 대화형 환경 생성을 가능하게 하지만, 노이즈 제거(denoising) 과정에서 반복적인 트랜스포머(Transformer) 평가로 인해 상당한 추론(inference) 오버헤드가 발생합니다. 기존 캐싱 기법들은 주로 특징(feature)이나 토큰(token) 수준의 시간적 중복성을 활용할 뿐, 확산 특징의 기저에 있는 수학적 구조는 거의 탐색하지 않았습니다. 본 연구에서는 월드 모델의 특징이 인접한 노이즈 제거 단계 전반에 걸쳐 매우 안정적인 특이 부분공간(singular subspace)을 보이며, 이들의 특잇값(singular value)은 예측 가능한 진화 패턴을 따른다는 점을 밝혀냅니다. 이러한 관찰을 바탕으로, 안정적인 특이 부분공간을 재사용하고 선형 외삽법(linear extrapolation)을 통해 저차원 특잇값만을 추정하는 학습(training)이 필요 없는 스펙트럼 캐싱 프레임워크인 SpectralCache를 제안합니다. 나아가 인접한 전체 계산 특징 간의 스펙트럼 일관성을 활용하여, 특잇값 스케일링을 통해 계산 비용이 큰 특정 백본 평가를 건너뜁니다. 대표적인 월드 모델을 대상으로 한 광범위한 실험을 통해 SpectralCache가 생성 품질을 유지하면서 추론 효율성을 일관되게 향상시킴을 입증합니다. HunyuanWorld-Voyager-13B에서 SpectralCache는 정적 장면에 대해 65.90의 WorldScore를 유지하면서 5.22배 가속을 달성하여, 기존의 학습 불필요 캐싱 기법보다 추론 효율성 면에서 크게 우수한 성능을 보였습니다.
TRAC: 효율적인 자기회귀 비디오 생성을 위한 궤적 인식 재사용 및 적응형 보정
TRAC: Trajectory-aware Reuse and Adaptive Correction for Efficient Autoregressive Video Generation
본 논문에서는 효율적인 자기회귀(AR) 비디오 생성을 위한 학습(training) 불필요 프레임워크인 TRAC(trajectory-aware reuse and adaptive correction)을 제시합니다. 기존의 가속 기법들은 주로 양방향 어텐션(attention)을 사용하는 단일 궤적 생성을 목표로 합니다. 반면 AR 비디오 생성은 청크(chunk) 단위의 노이즈 제거 궤적들을 순차적으로 결합합니다. 그 결과, 생성 과정 전반에 걸쳐 근사 오차가 누적되고 전파됩니다. TRAC은 견고한 누적 스케줄링(RCS), 자기회귀 궤적 인식 가이던스 스케줄링(ATGS), 스펙트럼 구조 보정(SSC)의 세 가지 구성 요소로 이 문제를 해결합니다. RCS는 누적 롤아웃(rollout) 오차와 청크 간/프롬프트(prompt) 변동을 기반으로 캐시 재사용 일정을 선택합니다. ATGS는 전체 AR 궤적을 따라 CFG 갱신을 조율합니다. SSC는 첫 번째 청크의 저주파 구조를 복원하여 장기적인 구조적 손실(loss)을 바로잡습니다. SkyReels-V2 및 FramePack-F1에 대한 실험 결과, TRAC은 기존 방법들과 비교하여 AR 비디오 생성에서 가장 높은 추론(inference) 효율성과 최고의 생성 품질을 모두 달성함을 보여줍니다.
FloodDiffusion 2: 효율적이고 경로 제어가 가능한 스트리밍 모션 생성
FloodDiffusion 2: Efficient and Path Controllable Streaming Motion Generation
우리는 최신 스트리밍 모션 생성 모델인 FloodDiffusion(FD1)을 기반으로 하는 효율적이고 제어 가능한 프레임워크인 FloodDiffusion 2(FD2)를 제시한다. FD1은 그럴듯한 모션을 생성하지만, 어텐션 설계가 전체 히스토리에 대해 반복적인 계산을 요구하기 때문에 효율성이 낮고, 실제 응용을 위한 정밀한 궤적 제어가 부족하여 제어 가능성이 제한적이라는 문제가 있다. 이러한 한계를 해결하고 생성 품질을 향상시키기 위해 FD2는 세 가지 개선 사항을 도입한다. 첫째, Partial Attention은 확정된 히스토리 표현(finalized history representation)을 활성 윈도우(active window)와 독립적으로 만들어, KV 캐싱 추론(KV-cached inference)과 효율적인 학습을 위한 공유 히스토리 패킹(shared-history packing)을 가능하게 한다. 둘째, 회귀 손실(regression loss)에 대한 필요충분(necessary-and-sufficient) 브레그만(Bregman) 기준을 확립하여 디퓨전(diffusion)의 조건부 평균 속도장(conditional-mean velocity field)을 보존한다. 이 기준은 온라인 순방향 동역학(forward kinematics, FK) 평가 없이도 모션 기하학(motion geometry)을 포함하는 FK 유도 이차 손실(FK-induced quadratic loss)을 이끌어낸다. 셋째, FD2는 자연스러운 신체 모션을 유지하면서 캐릭터의 루트 궤적(root trajectory)을 제어하기 위한 정밀한 경로 조건화(path conditioning)를 도입한다. 실험 결과, FD2는 학습 연산량을 4.6배 줄이고 디노이징(denoising)을 11.29배 가속화하여 긴 시퀀스에서 업데이트당 2.303ms에 도달한다. 이러한 효율성 향상과 더불어 FD2는 FD1보다 모션 품질을 개선하며, 스트리밍 방법들 중 SEED에서 0.048, HumanML3D에서 0.053이라는 최첨단(state-of-the-art) FID 점수를 달성한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.