Scattering amplitudes in Yang-Mills theory are known to exhibit kinematic structures which hint to an underlying kinematic algebra that is dual to the gauge group color algebra. This color-kinematics duality is still poorly understood in terms of conventional Feynman rules, or from a Lagrangian formalism. In this work, we present explicit Lagrangians whose Feynman rules generate duality-satisfying tree-level BCJ numerators, to any multiplicity in the next-to-MHV sector of pure Yang-Mills theory. Our Lagrangians make use of at most three pairs of auxiliary fields (2, 1, 0-forms) — surprisingly few compared to previous attempts of Lagrangians at low multiplicities. To restrict the Lagrangian freedom it is necessary to make several non-trivial assumptions regarding field content, kinetic terms, and interactions, which we discuss in some detail. Future progress likely hinges on relaxing these assumptions.