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

Classical dynamic programming algorithms such as Smith-Waterman, edit distance, and constituency parsing solve structured combinatorial problems using hard constraints. Soft relaxations replace hard $\max$ or $\min$ operators with differentiable probabilistic models whose gradients correspond to alignment or parsing marginals, but existing approaches typically treat the DP algorithm itself as fixed, relying on hand-tuned gap penalties, edit costs, span penalties, and temperatures. We show how to learn these parameters directly from data: the marginals these algorithms produce are themselves first-order derivatives, so learning them is inherently a second-order problem. We derive efficient Hessian-vector products and cross-Jacobians for twelve dynamic programming algorithms spanning alignment, edit distance, and parsing; both derivative families admit closed-form covariance expressions under the induced Gibbs distribution. We implement these operators as fused CUDA kernels in d$^2$p, achieving $100$--$20{,}000\times$ speedups over standard PyTorch and making end-to-end parameter learning practical at modern scales. We then demonstrate that learning these parameters is critical in practice. In protein structure alignment, freezing gap penalties collapses performance from $0.74$ to $0.32$ $F_1$ (and to $0.13$ at lower encoder capacity), while jointly learning them recovers biologically meaningful gap regimes and reaches $0.75$ $F_1$ and $0.445$ lDDT, $91$% of the TM-align lDDT ceiling. The same machinery transfers to constituency parsing, where a structured CKY CRF matches dense per-span supervision to within $0.003$ $F_1$ on English with no direct parse-tree structural supervision.

Many problems in science and language come down to lining things up and finding their correspondences: matching sequences of text, matching the parts of two proteins to measure how similar their shapes are, or finding the grammatical structure hidden inside a sentence. For decades these have been handled by classic step-by-step algorithms that work well but depend on settings a person has to choose in advance, often arbitrarily, such as how harshly to penalize a gap when two things do not quite match. This paper shows that these classic algorithms are closely related to the "attention" mechanism that powers modern AI systems, and works out the mathematics needed to let a neural network learn those previously hand-chosen settings on its own, instead of leaving them fixed. We find that letting the system learn its own settings matters. When comparing the three-dimensional shapes of proteins, a model that learns its settings is far more accurate than one using textbook defaults, and choosing the right underlying algorithm can matter more than simply making the AI model larger. We also show the same approach can uncover the structure of sentences, including computer code, without ever being shown correct answers to imitate. To make these tools usable by others, we release fast, open-source software that runs efficiently on modern hardware.