Feature crossing is a popular method for augmenting the feature set of a machine learning model by taking the Cartesian product of a small number of existing categorical features. While feature crosses have traditionally been hand-picked by domain experts, a recent line of work has focused on the automatic discovery of informative feature crosses. Our work proposes a simple yet efficient and effective approach to this problem using tensor proxies as well as a novel application of the attention mechanism to convert the combinatorial problem of feature cross search to a continuous optimization problem. By solving the continuous optimization problem and then rounding the solution to a feature cross, we give a highly efficient algorithm for feature cross search that trains only a single model for feature cross searching, unlike prior greedy methods that require training a large number of models. Through extensive empirical evaluations, we show that our algorithm is not only efficient, but also discovers more informative feature crosses that allow us to achieve state-of-the-art empirical results for feature cross models. Furthermore, even without the rounding step, we obtain a novel DNN architecture for augmenting existing models with a small number of features to improve quality without introducing any feature crosses. This avoids the cost of storing additional large embedding tables for these feature crosses.