Systems and methods for processing inputs using attention neural networks with tree attention layers. Each tree attention layer includes one or more tree attention sub-layers that are each configured to: process query vectors using a decision tree model for the tree attention sub-layer to determine a respective tree path for each query vector; process key vectors using the decision tree model to determine a respective tree path for each key vector; and generate an attended input sequence comprising a respective attended input at each of the plurality of input positions, comprising: generating, for each particular input position, the respective attended input at the particular input position based on (i) the tree path for the query vector at the particular input position (ii) the respective tree paths for the key vectors at each of the plurality of input positions and (iii) the value vectors at a subset of the input positions.