We develop a progression of methods for accelerating fixed-point iterations by leveraging approximate and reduced formulations of Anderson acceleration (AA). Firstly, we establish rigorous theoretical error bounds that enable approximate calculations within AA when solving linear problems. We prove that, as long as the approximate computations satisfy these bounds, the convergence guarantees of AA are preserved while computational cost can be reduced. Guided by these results, we introduce computable heuristic quantities that automate accuracy tuning in practice, ensuring monotonic residual reduction and convergence within prescribed tolerances. Motivated by this analysis, we propose a reduced variant of AA in which the least-squares system underlying Anderson mixing is projected onto an adaptively chosen subspace. Secondly, we extend the paradigm to a novel two-level sketching Alternating Anderson–Picard (AAP) method for challenging single- and multi-physics PDE simulations. Our extension combines a static, physics-informed projection (e.g., via Schur-complement reduction to the most informative field) with a dynamic, algebraic sketching stage derived from backward stability analysis under Lipschitz continuity. To balance stability and efficiency, we design inexpensive error estimators and cache-aware randomized sketching strategies that minimize memory footprint and computational overhead. Implemented in Julia, our two-level sketching AAP achieves up to 50% reductions in time-to-solution over standard AA, while maintaining convergence robustness, on benchmark problems including Stokes, p-Laplacian, Bidomain, and Navier–Stokes systems. Together, these contributions provide a rigorous theoretical basis and scalable algorithmic extensions that make Anderson-type accelerations more efficient, adaptive, and applicable across a wide range of scientific computing problems.