# SoftStep: Learning Sparse Similarity Powers Deep Neighbor-Based Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 62 references that are in the map.
- First posted on arXiv 9 Jun 2025.

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Robust Speech Recognition via Large-Scale Weak Supervision](https://mlsanity.com/paper/2212.04356/) (2022)
- [A ConvNet for the 2020s](https://mlsanity.com/paper/2201.03545/) (2022)
- [HuBERT: Self-Supervised Speech Representation Learning by Masked Prediction of Hidden Units](https://mlsanity.com/paper/2106.07447/) (2021)
- [Matching Networks for One Shot Learning](https://mlsanity.com/paper/1606.04080/) (2016)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [Smarter, Better, Faster, Longer: A Modern Bidirectional Encoder for Fast, Memory Efficient, and Long Context Finetuning and Inference](https://mlsanity.com/paper/2412.13663/) (2024)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [SAINT: Improved Neural Networks for Tabular Data via Row Attention and Contrastive Pre-Training](https://mlsanity.com/paper/2106.01342/) (2021)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Convolutional Neural Networks for Medical Image Analysis: Full Training or Fine Tuning?](https://mlsanity.com/paper/1706.00712/) (2017)
- [Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning](https://mlsanity.com/paper/1803.04765/) (2018)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Neural Nearest Neighbors Networks](https://mlsanity.com/paper/1810.12575/) (2018)
- [Detecting cognitive decline using speech only: The ADReSSo Challenge](https://mlsanity.com/paper/2104.09356/) (2021)
- [Dissecting Supervised Contrastive Learning](https://mlsanity.com/paper/2102.08817/) (2021)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [The COUGHVID crowdsourcing dataset: A corpus for the study of large-scale cough analysis algorithms](https://mlsanity.com/paper/2009.11644/) (2020)
- [Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers](https://mlsanity.com/paper/2406.16747/) (2024)
- [Comparing Acoustic-based Approaches for Alzheimer's Disease Detection](https://mlsanity.com/paper/2106.01555/) (2021)
- [Self-Driving Car Steering Angle Prediction Based on Image Recognition](https://mlsanity.com/paper/1912.05440/) (2019)
- [The Topology and Geometry of Neural Representations](https://mlsanity.com/paper/2309.11028/) (2023)
- [House price estimation from visual and textual features](https://mlsanity.com/paper/1609.08399/) (2016)
- [DNNR: Differential Nearest Neighbors Regression](https://mlsanity.com/paper/2205.08434/) (2022)

## Abstract (arXiv)

Neighbor-based methods are a natural alternative to linear prediction for tabular data when relationships between inputs and targets exhibit complexity such as nonlinearity, periodicity, or heteroscedasticity. Yet in deep learning on unstructured data, nonparametric neighbor-based approaches are rarely implemented in lieu of simple linear heads. This is primarily due to the ability of systems equipped with linear regression heads to co-learn internal representations along with the linear head's parameters. To unlock the full potential of neighbor-based methods in neural networks we introduce SoftStep, a parametric module that learns sparse instance-wise similarity measures directly from data. When integrated with existing neighbor-based methods, SoftStep enables regression models that consistently outperform linear heads across diverse architectures, domains, and training scenarios. We focus on regression tasks, where we show theoretically that neighbor-based prediction with a mean squared error objective constitutes a metric learning algorithm that induces well-structured embedding spaces. We then demonstrate analytically and empirically that this representational structure translates into superior performance when combined with the sparse, instance-wise similarity measures introduced by SoftStep. Beyond regression, SoftStep is a general method for learning instance-wise similarity in deep neural networks, with broad applicability to attention mechanisms, metric learning, representational alignment, and related paradigms.