Learning Deep Choice Hierarchies from Four Exact Probability Responses

Can four probability responses reveal an unknown deep choice hierarchy, and can an inexact reconstruction be certified? We study reduced nested-logit trees of arbitrary finite arity with unknown parameters and affine item-input scales, under independently adjustable continuous inputs and full positive probability-vector access. A scale-free finite-coupling identity reuses the same responses across all levels. A baseline and three random perturbations identify the entire model almost surely; for three or more alternatives, four are optimal even with adaptive queries. For inexact observations, a candidate-only shared-response certificate uses the proposed tree's clades to exclude every competing compatible topology, with cubic arithmetic work after a strict binary proposal is supplied. When unique structure cannot be certified, a separate packed outer cover can instead certify one common predictor across structures and all available-item sets on a declared domain. These guarantees require family membership, valid observation intervals, and successful verified computation; refusal is permitted. Across 12 fresh synthetic models and 72 correlated design/precision conditions, shared-response certification provides 66 total-variation bounds at most 0.01, versus 36 for packed certification. A matched enclosure ablation supports the mechanism. Public-component polytomies require the complementary packed route. Float32 certification remains weak, a dense classical control is faster locally, and frequency-based structure recovery fails the prespecified criterion under the tested sampling conditions. This is a probability-query boundary with conditional certification, not recovery from four choices or a general noisy-sample guarantee.