Instance-based models offer natural interpretability by making decisions based on concrete examples. However, their transparency is often hindered by the use of complex similarity measures, which are difficult to interpret, especially in high-dimensional datasets. To address this issue, this paper presents a meta-learning framework that enhances the interpretability of instance-based models by replacing traditional, complex pairwise distance functions with interpretable pairwise distance trees. These trees are designed to prioritize simplicity and transparency while preserving the model’s effectiveness. By offering a clear decision-making process, the framework makes the instance selection more understandable. Also, the framework mitigates the computational burden of instance-based models, which typically require calculating all pairwise distances. Leveraging the generalization capabilities of pairwise distance trees and employing sampling strategies to select representative subsets, the method significantly reduces computational complexity. Our experiments demonstrate that the proposed approach improves computational efficiency with only a modest trade-off in accuracy while substantially enhancing the interpretability of the learned distance measure.