ASTRAL-III is a faster version of the ASTRAL method for phylogenetic reconstruction, capable of scaling to 10,000 species. It improves the running time of ASTRAL-II by guaranteeing polynomial time complexity as a function of both the number of species (n) and the number of genes (k). ASTRAL-III limits the bipartition constraint set (X) to grow linearly with n and k, handles polytomies more efficiently, and uses techniques to avoid searching parts of the search space that are mathematically guaranteed not to include the optimal tree. The asymptotic running time of ASTRAL-III in the presence of polytomies is O((nk)^{1.726}D), where D is the sum of degrees of all unique nodes in input trees. ASTRAL-III enables testing whether contracting low support branches in gene trees improves accuracy. Simulations show that removing branches with very low support (e.g., below 10%) improves accuracy, while overly aggressive filtering is harmful. On a biological avian phylogenomic dataset of 14K genes, contracting low support branches greatly improves results. ASTRAL-III has six new features, including modified heuristics for building X, a new way of computing w(q), a polytree representation of gene trees, a new algorithm for computing upper bounds, and a two-stage heuristic mechanism. These improvements reduce the running time and improve accuracy. ASTRAL-III's running time grows as O(D(nk)^{1.726}) for both binary and multifurcating gene trees. It also improves the efficiency of handling polytomies and reduces the search space. ASTRAL-III's accuracy remains unchanged compared to ASTRAL-II, with differences in error less than 0.002 across all datasets. ASTRAL-III's improved running time does not come at the price of reduced accuracy. ASTRAL-III can scale to datasets with up to 10,000 species.ASTRAL-III is a faster version of the ASTRAL method for phylogenetic reconstruction, capable of scaling to 10,000 species. It improves the running time of ASTRAL-II by guaranteeing polynomial time complexity as a function of both the number of species (n) and the number of genes (k). ASTRAL-III limits the bipartition constraint set (X) to grow linearly with n and k, handles polytomies more efficiently, and uses techniques to avoid searching parts of the search space that are mathematically guaranteed not to include the optimal tree. The asymptotic running time of ASTRAL-III in the presence of polytomies is O((nk)^{1.726}D), where D is the sum of degrees of all unique nodes in input trees. ASTRAL-III enables testing whether contracting low support branches in gene trees improves accuracy. Simulations show that removing branches with very low support (e.g., below 10%) improves accuracy, while overly aggressive filtering is harmful. On a biological avian phylogenomic dataset of 14K genes, contracting low support branches greatly improves results. ASTRAL-III has six new features, including modified heuristics for building X, a new way of computing w(q), a polytree representation of gene trees, a new algorithm for computing upper bounds, and a two-stage heuristic mechanism. These improvements reduce the running time and improve accuracy. ASTRAL-III's running time grows as O(D(nk)^{1.726}) for both binary and multifurcating gene trees. It also improves the efficiency of handling polytomies and reduces the search space. ASTRAL-III's accuracy remains unchanged compared to ASTRAL-II, with differences in error less than 0.002 across all datasets. ASTRAL-III's improved running time does not come at the price of reduced accuracy. ASTRAL-III can scale to datasets with up to 10,000 species.