Learning Low-Logit-Rank Distributions from Conditional Samples

Abstract

For fully supported binary distributions on length-T strings whose centered next-bit logits have magnitude at most T and rank at most d at every history cut, we prove polynomial-time learning from chosen-prefix next-bit samples at every fixed d. The algorithm adds a small amount of fair-bit noise, approximates the resulting analytic logit transformation by a polynomial, and invokes a robust logit learner through a cached sampling simulation. Its costs are (T + d)^{O(d)} at fixed accuracy and confidence, with Õ_d(T^{6d+15}) submitted and generated tokens, and it returns a standalone student. A second proof transfers the conditional-sampling theorem for low probability rank through a consistent polynomial surrogate. A specified inverse-polynomial probability floor gives joint polynomial learning as a consequence of the published logit simulation. When the rank grows, strong pseudorandom functions in logarithmic-depth circuits rule out a learner polynomial jointly in T and d. The hard teachers carry a linear mismatch counter, which makes every inconsistent-prefix query simulable. We also separate numerical logit simulation from distribution learning: the former requires exponentially many samples even at rank one. Complete token accounting, finite-bit implementations, polynomial sample sufficiency, and a Lean 4 formalization of the main lemmas accompany the proofs.