Upper bound of efficiency loss is a valuable issue for transport network design and planning. This paper initially explores it in a taxed stochastic traffic network whose equilibrium flow pattern is deduced by a cross-nested Logit (CNL) flow assignment model, and a centrally controlling Stackelberg strategy. With the assumptions of separability, nondecreasingness, and convexity of the link time function and the fixed origin-destination (OD) demand of network, the equivalent variational inequality for a CNL-based stochastic user equilibrium (CNL-SUE) model is established and first used to obtain upper bounds on Stackelberg network inefficiency. Further, for low-degree link time function such as Bureau of Public Roads and the affine forms, their inefficiency upper bounds are analyzed with some meaningful results.