Below is a summary of why, as far as we know, there is no “magic shortcut’’ that, given the list of absolute‐values {|λ₁|,…,|λₙ|}, recovers the signs sign(λᵢ) in o(n³) (or o(n^ω)) time without essentially re‐doing a spectral computation.

1. The problem really is to decide, for each magnitude aᵢ, whether the corresponding eigenvalue of A is +aᵢ or −aᵢ. Equivalently one needs an eigenvector vᵢ for that eigenspace and to check the Rayleigh quotient
   R(vᵢ)=vᵢᵀAvᵢ / vᵢᵀvᵢ
   whose sign is sign(λᵢ). Extracting even one eigenvector to reasonable accuracy costs about as much as finding the eigenvalue itself (e.g. power or Lanczos iterations, or a symmetric QR step).

2. One can rephrase “find all signs’’ as computing the matrix sign‐function
   sign(A)=A·(A²)^{−1/2} so that sign(A)V=V·diag(sign(λᵢ)),
   and then reading off sign(λᵢ) from Vᵀsign(A)V. But all of the standard ways to compute sign(A)—Newton iterations
   X_{k+1} = ½(X_k + X_k^{−1}), or Padé approximants, or an LDLᵀ‐based inertia algorithm—require O(n^ω) per matrix multiplication/inversion and at least O(log κ(A)) steps for sufficient accuracy. In other words you pay about the same as for a full spectral decomposition, up to polylog factors.

3. You might hope that knowing {|λᵢ|} cuts down the work. Unfortunately, it merely tells you the spectrum of A², and A² and A share eigenvectors but the same 1‐dimensional eigenspaces for +aᵢ and −aᵢ are indistinguishable via A² alone. To break the ± ambiguity you still must apply A to those eigenspaces.

4. From a complexity‐theory point of view there is no known reduction that takes “sign‐recovery’’ and solves it in asymptotically less time than any of the standard O(n³) (or, with fast matrix‐mult., O(n^ω)) eigenvalue‐or‐inertia algorithms. Nor is there any lower‐bound proof that it must cost Ω(n³); the barrier is simply that all known numeric or algebraic methods for distinguishing eigenspaces of ±aᵢ end up doing essentially the same linear‐algebra work as full diagonalization or LDLᵀ factorization.

Conclusion:
— Best known exact or high‐accuracy methods for extracting the individual signs sign(λᵢ) run in O(n³) (using classical Gaussian elimination / QR / divide‐and‐conquer) or in O(n^ω log (1/ε)) if you invoke fast matrix multiplication and iterate to accuracy ε.
— There is no known algorithm that, merely from the list of absolute‐values {|λᵢ|}, peels off the ± signs in truly sub‐cubic time.