





















Abstract: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.
| Comments: | 22 pages |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.20074 [cs.LG] |
| (or arXiv:2605.20074v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.20074 arXiv-issued DOI via DataCite (pending registration) |
From: Thien Le [view email]
[v1]
Tue, 19 May 2026 16:28:18 UTC (1,819 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。