# Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimization

arXiv: https://arxiv.org/abs/2605.20074 · HTML: https://mlsanity.com/paper/2605.20074/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 32 references that are in the map.
- First posted on arXiv 19 May 2026.

## Builds on (most cited first, 25 of 25)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [TinyBERT: Distilling BERT for Natural Language Understanding](https://mlsanity.com/paper/1909.10351/) (2019)
- [Toy Models of Superposition](https://mlsanity.com/paper/2209.10652/) (2022)
- [The Linear Representation Hypothesis and the Geometry of Large Language Models](https://mlsanity.com/paper/2311.03658/) (2023)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Towards Debiasing Sentence Representations](https://mlsanity.com/paper/2007.08100/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Debiasing Vision-Language Models via Biased Prompts](https://mlsanity.com/paper/2302.00070/) (2023)
- [Black is to Criminal as Caucasian is to Police: Detecting and Removing Multiclass Bias in Word Embeddings](https://mlsanity.com/paper/1904.04047/) (2019)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Does equivariance matter at scale?](https://mlsanity.com/paper/2410.23179/) (2024)
- [Scaling MLPs: A Tale of Inductive Bias](https://mlsanity.com/paper/2306.13575/) (2023)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [Asynchronous Algorithmic Alignment with Cocycles](https://mlsanity.com/paper/2306.15632/) (2023)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [NN-Steiner: A Mixed Neural-algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem](https://mlsanity.com/paper/2312.10589/) (2023)
- [Distribution Free Learning with Local Queries](https://mlsanity.com/paper/1603.03714/) (2016)

## Abstract (arXiv)

Distillation transfers knowledge from a large model trained on broad data to a smaller, more efficient model suitable for deployment. In structured prediction settings, prior knowledge about the task can guide the choice of a target architecture that is algorithmically aligned with the underlying problem. Building on recent learning-theoretic analyses of decision-tree (DT) distillation (Boix-Adsera, 2024), we study when distillation succeeds for combinatorial optimization tasks. We focus on the case where the target model is a graph neural network whose architecture is aligned with a dynamic programming (DP) algorithm for the task. Assuming that the source model is sufficiently rich, formalized through the linear representation hypothesis (LRH) (Elhage et al., 2022; Park et al., 2024), we show that the distillation problem can be solved efficiently in the complexity parameters of the DP transition function, represented as a DT. Our results provide a rigorous sufficient condition for successful distillation in the flavour of algorithmic alignment.