Transmit beamforming design is a fundamental problem in integrated sensing and communication (ISAC) systems. Numerous methods have been proposed to jointly optimize key performance metrics such as the signal-to-interference-plus-noise ratio and Cramér-Rao bound. However, the computational complexity of these methods often grows rapidly with the number of transmit antennas at the base station (BS). To tackle this challenge, we prove a fundamental structural property of the ISAC beamforming problem, i.e., there exists an optimal solution exhibiting a low-dimensional structure. This leads to an equivalent reformulation of the problem with dimension related to the number of users rather than the number of BS antennas, thereby enabling the development of low-complexity algorithms. When applying the interior-point method to the reformulated problem, we achieve up to six orders of magnitude in complexity reduction when the number of antennas exceeds the number of users by an order of magnitude. To further reduce the complexity, we develop a balanced augmented Lagrangian method to solve the reformulated problem. The proposed algorithm maintains optimality while achieving a computational complexity that scales quartically with the number of users. Our simulation results demonstrate that the proposed R-BAL method can achieve a speedup of more than 10000$\times$ over the conventional IPM in massive MIMO scenarios.