Hidden-free-fermion (HFF) Hamiltonians exhibit free-fermion spectra despite lacking an explicit quadratic representation, yet their algebraic provenance and periodic-boundary behavior remain open questions. Here we establish that a broad class of HFF models arises from distinct Lax operator realizations of a twisted multistate Perk--Schultz
R matrix. Its reflected degeneration generates a closed finite hierarchy of mutually commuting transfer matrices, whose functional relations determine the complete many-body spectrum. As a decisive example, we solve the inhomogeneous free-fermions-in-disguise (FFD) chain, which exhibits HFF, nested HFF, or interacting spectra, depending on its coupling. The homogeneous FFD chain with both one-wrap and periodic boundary conditions exhibits an emergent cubic finite-size gap while retaining the exact
z=3/2 bulk behavior. The construction extends to higher-state and face-type realizations, providing a common algebraic framework for coupling-dependent spectral organization and multiscale behavior in interacting quantum systems.
We show that a quantum spin system has an exact description by non-interacting fermions if its frustration graph is claw-free and contains a simplicial clique. The frustration graph of a spin model captures the pairwise anticommutation relations between Pauli terms of its Hamiltonian in a given basis. This result captures a vast family of known free-fermion solutions. In previous work, it was shown that a free-fermion solution exists if the frustration graph is either a line graph, or (even-hole, claw)-free. The former case generalizes the celebrated Jordan-Wigner transformation and includes the exact solution to the Kitaev honeycomb model. The latter case generalizes a non-local solution to the four-fermion model given by Fendley. Our characterization unifies these two approaches, extending generalized Jordan-Wigner solutions to the non-local setting and generalizing the four-fermion solution to models of arbitrary spatial dimension. Our key technical insight is the identification of a class of cycle symmetries for all models with claw-free frustration graphs. We prove that these symmetries commute, and this allows us to apply Fendley's solution method to each symmetric subspace independently. Finally, we give a physical description of the fermion modes in terms of operators generated by repeated commutation with the Hamiltonian. This connects our framework to the developing body of work on operator Krylov subspaces. Our results deepen the connection between many-body physics and the mathematical theory of claw-free graphs.