Budget-Aware Adaptive Test-Time Compute with Hierarchical Self-Verification for Semantic ID Generative Recommendation

Semantic identifier (SID) generative recommenders cast retrieval as autoregressive decoding over short sequences of residual-quantized codewords. Most published SID recommenders decode all requests with one fixed beam width, which is optimal only if the marginal utility of compute is constant across requests. We find that it is not; additional search changes little for users with consistent histories, but improves accuracy substantially for cold start, interest-drifting, and long-tail users. The main methodological contribution of this paper is request-level allocation of decoding compute, in which a router predicts the accuracy gain of each configuration in a finite decoding menu over the cheapest configuration and selects the configuration with the largest gain net of a priced cost. The selection rule follows from standard Lagrangian arguments, which we use as tools; what is specific to this work is the use of this per-configuration gain as the routing target for SID decoding instead of a difficulty or uncertainty score. The resulting framework, called Bastion, combines the router with a hierarchical process verifier over the quantization levels, a listwise terminal verifier, codeword consistency voting, and budget-constrained group relative policy optimization. On five benchmarks built from Amazon Reviews 2023, MovieLens, and MicroLens, Bastion improves NDCG@10 by 5.7% to 8.7% over the strongest baseline. Its mean latency on Amazon-Beauty is 14.5 ms, against 14.6 ms for a beam-20 TIGER decoder, while its median and 99th-percentile latencies are higher by 0.9 ms and 7.0 ms. At every evaluated budget, its accuracy exceeds that of all baselines on the three datasets for which accuracy versus latency frontiers was measured.