d$^2$p: Structured Soft Attention Is All You Need

Essence

Figure 1. Structured attention is temperature-controlled. Each panel shows soft marginals (attention weights) at tempera

고전적 dynamic programming(DP) 알고리즘(Smith-Waterman, edit distance, CKY parsing)을 structured soft attention으로 재해석하고, 그 알고리즘 자체의 하이퍼파라미터(gap penalty, edit cost, temperature 등)를 marginal의 2차 미분(Hessian-vector product, cross-Jacobian)을 통해 데이터로부터 직접 학습하는 프레임워크 d2p를 제안한다.

Motivation

Known: 기존 soft DP 완화(soft-DTW, structured attention, SparseMAP, torch-struct, differentiable Smith-Waterman 등)는 log-sum-exp를 통해 max/min 연산자를 미분 가능하게 만들고, 이때 그래디언트가 정렬/파싱 marginal(즉 1차 미분)에 해당함을 활용해 encoder를 학습시킨다.
Gap: 그러나 기존 접근은 DP 알고리즘 자체의 gap penalty, edit cost, span penalty, temperature 등은 hand-tuned 상수로 고정하고 encoder만 학습하는데, 이는 marginal이 이미 1차 미분이므로 그 marginal 자체를 손실에 대해 미분하여 학습하려면 2차 미분(Hessian, cross-Jacobian)이 필요하다는 구조적 한계 때문이다.
Why: DP 알고리즘의 recursion 구조는 그 자체로 일종의 prior이며, 특히 데이터가 희소하고 비용이 큰 자연과학 도메인(단백질 구조 정렬 등)에서는 올바른 구조적 prior가 encoder capacity로 대체될 수 없는 결정적 역할을 하므로, 이를 학습 가능하게 만드는 것이 실용적으로 중요하다.
Approach: DP의 marginal이 log-partition function의 1차 미분이라는 점에 착안해, 정렬·edit distance·parsing을 아우르는 12개 DP 알고리즘에 대해 Hessian-vector product와 cross-Jacobian을 유도하고, 이를 Gibbs 분포 하의 closed-form covariance로 표현한 뒤 fused CUDA kernel(d2p)로 구현하여 end-to-end 하이퍼파라미터 학습을 가능하게 한다.

Achievement

Figure 2. End-to-end differentiable protein structure alignment with d2p. Two protein structures are encoded by a neural

완전한 미분 계층(complete derivative hierarchy) 구축: attention matrix가 log-partition의 1차 미분이라는 통찰로부터, encoder 학습용 Hessian-vector product와 하이퍼파라미터 학습용 cross-Jacobian을 12개 DP 알고리즘 전체에 대해 Gibbs covariance로 유도.
U+W two-pass 알고리즘: cross-Jacobian ∂P_T/∂η을 backward pass와 동일한 점근적 비용으로 계산하는 알고리즘을 제시하고 12개 알고리즘 모두에 인스턴스화.
통합된 알고리즘 패밀리: pairwise alignment, edit distance, parsing을 structured soft attention이라는 단일 틀로 통합(grid=cross-attention, chart=self-attention), T→0에서 고전적 hard DP, 유한 온도에서 pair HMM/SCFG로 환원됨을 보임.
구현 및 속도: 오픈소스 라이브러리 d2p를 공개, PyTorch 대비 100–20,000배, torch-struct 대비 100–1000배 속도 향상 달성.
응용 실증: 단백질 구조 정렬에서 gap penalty를 고정하면 F1이 0.74→0.32(저용량 encoder에서는 0.13)로 붕괴하나 공동 학습 시 0.75 F1, 0.445 lDDT(TM-align 대비 91%) 달성; constituency parsing에서 구조적 CKY CRF가 dense span supervision 없이도 0.003 F1 이내로 근접하고 9개 도메인 중 3개에서는 오히려 능가.

How

Figure 3. Soft alignment marginals across ten DP algorithms and two attention baselines. Each heatmap shows the posterio

Danskin's theorem을 이용해 고전 hard DP의 argmax가 value function의 1차 미분임을 재확인하고, 유한 온도 완화(log-sum-exp)에서는 marginal이 Gibbs 분포 하의 사후 확률(1차 미분)이 됨을 정식화
marginal 자체를 손실에 대해 미분하는 것이 2차 미분 문제임을 규명하고, encoder 학습을 위한 Hessian-vector product(∂P_T/∂S)와 하이퍼파라미터 학습을 위한 cross-Jacobian(∂P_T/∂η)을 유도
두 미분 계열 모두 induced Gibbs distribution 하에서 closed-form covariance로 표현 가능함을 증명
U+W two-pass 알고리즘으로 cross-Jacobian을 backward pass와 동일한 점근 복잡도로 계산
Smith-Waterman(affine gap), edit distance, CKY parsing 등 12개 DP 알고리즘에 대해 fused CUDA kernel로 forward/backward/HVP/cross-Jacobian 연산을 구현(d2p 라이브러리)
단백질 구조 정렬(encoder capacity를 substitution matrix부터 128차원 신경망까지 스윕, Smith-Waterman/row-softmax/DTW 세 가지 prior 비교)과 constituency parsing(구조적 CKY CRF vs dense per-span supervision) 실험으로 검증

Originality

DP marginal이 이미 1차 미분이라는 관찰로부터 하이퍼파라미터 학습이 본질적으로 2차 미분 문제임을 규명한 점이 핵심적 통찰
Mensch & Blondel(2018)이 Viterbi/DTW에 대한 score-score Hessian만 제공하고 CherryML(Prillo et al., 2023)이 autodiff로 rate matrix만 학습한 데 비해, 본 논문은 구조 공간 자체를 조건화하는 cross-Jacobian을 closed-form Gibbs covariance로 12개 알고리즘 전체에 대해 유도한 점이 최초
DP를 structured attention의 zero-temperature 극한으로 보는 관점(standard attention은 unconstrained soft correspondence, DP는 monotone/gap-respecting 또는 grammatical/hierarchical한 제약이 걸린 attention)을 통해 정렬·edit distance·parsing을 하나의 틀로 통합
하이퍼파라미터가 encoder capacity로 대체 불가능함을 실증적으로 보여 Sutton의 bitter lesson에 대한 반례적 통찰(구조가 결정적인 도메인에서는 올바른 prior가 데이터 부족을 보완하는 지속적 대체재라는 논지)을 제시

Limitation & Further Study

초록 발췌 내용상 12개 알고리즘 전체에 대한 실험적 검증(특히 edit distance 계열)이 본문에서 충분히 제시되었는지 확인이 어려우며, 대표 사례(Smith-Waterman, CKY)에 집중된 것으로 보임
단백질 구조 정렬 실험이 특정 데이터셋과 encoder 구조에 한정되어 있어, 다른 구조적 예측 문제나 더 큰 규모의 최신 protein language model과의 결합 가능성에 대한 논의가 필요
constituency parsing에서 대형 언어모델 기반 encoder 대비 정확도 자체는 열세이며, 논문이 강조하는 '지도 효율성'의 이점이 실제 대규모 응용에서 어느 정도 실용적 가치를 갖는지 추가 검증 필요
후속 연구로 다른 구조적 예측 문제(예: RNA 구조, 계층적 시퀀스 라벨링)로의 확장, 그리고 cross-Jacobian 계산의 수치적 안정성에 대한 심층 분석이 요구됨

Evaluation

Novelty: 5/5 Technical Soundness: 4/5 Significance: 4/5 Clarity: 4/5 Overall: 4/5

총평: DP marginal이 이미 1차 미분이라는 통찰에서 출발해 하이퍼파라미터 학습을 2차 미분 문제로 정식화하고 이를 12개 알고리즘에 대해 closed-form으로 유도·구현한 점에서 이론적 기여와 실용적 가치(속도, 성능 개선)를 모두 갖춘 견실한 연구이다.

같이 보면 좋은 논문

Neural Ordinary Differential Equations

기반 연구SPECTER2 유사도 0.90로 Computational Molecular Design와 Scientific AI for Physics and Environment가 맞닿아, 'Neural Ordinary Differential Equations'가 이 ICML 2026 논문의 배경·대안·응용 맥락을 보완한다.

GPT-4 Technical Report

기반 연구SPECTER2 유사도 0.91로 Computational Molecular Design와 LLM Benchmarking and Agent Evaluation가 맞닿아, 'GPT-4 Technical Report'가 이 ICML 2026 논문의 배경·대안·응용 맥락을 보완한다.

HiPerRAG: High-performance retrieval augmented generation for scientific insights

기반 연구SPECTER2 유사도 0.90로 Computational Molecular Design와 Scientific Information Extraction and QA가 맞닿아, 'HiPerRAG: High-performance retrieval augmented generation for scientific insights'가 이 ICML 2026 논문의 배경·대안·응용 맥락을 보완한다.

Bayesian Last Layer for Neural Force Fields

기반 연구dynamic programming과 attention 메커니즘 연결의 이론적 기초를 제공함

Plug-and-Play Guidance for Discrete Diffusion Models via Gradient-Informed Logit Correction

다른 접근structured soft attention을 통한 DP 알고리즘 재해석의 다른 접근법을 제시함

Ares: Loss-Free Mixture-of-Experts Routing for Bidirectional Protein Encoders

응용 사례구조화된 attention을 시퀀스 정렬이나 파싱 문제에 적용한 응용 사례이다.