[SIGIR 2026] APAO: Bridging the Gap Between Training and Beam Search in Generative Recommendation

TL;DR

Generative recommendation is transitioning from a niche concept to a dominant paradigm. However, it harbors a hidden flaw: models are trained to predict the next token perfectly given the truth, but they fail during inference when "beam search" prunes away the correct item's prefix. APAO (Adaptive Prefix-Aware Optimization) solves this by forcing the model to optimize every step of the generation, ensuring the correct candidates "survive" the pruning process.

The "Survival of the Fittest" Problem in Decoding

In modern Generative Recommendation (GR), items are represented as sequences of tokens (e.g., semantic codes). To find the best item, we don't just pick the most likely first token; we use Beam Search to maintain $K$ candidate paths.

The authors identify a critical Training-Inference Inconsistency:

• Training: The model assumes it always has the correct prefix (Teacher-Forcing). It doesn't care if the probability of a middle token is low, as long as the total sequence probability is eventually high.
• Inference: If a prefix's probability drops out of the Top-$K$ at any step, that item is discarded forever.

The image below (Figure 1 from the paper) illustrates how items identified as Top-20 by a full-item sort are often "lost" during the early steps of beam search because the model wasn't trained to prioritize those early prefixes.

Methodology: Optimizing the Probabilistic Chain

Instead of just looking at the final item sequence, APAO breaks down the loss into a prefix-aware objective.

1. Prefix-Aware Losses

The framework offers two flavors of supervision:

• Pointwise: Reweights the Cross-Entropy loss based on prefix length.
• Pairwise: Introduces negative sampling for each prefix length ($m$). It explicitly trains the model to rank the ground-truth prefix higher than incorrect prefixes of the same length.

2. Adaptive Worst-Prefix Optimization

The most "academic" contribution here is how they weight these prefixes. Not all steps are equally difficult. The authors propose an adaptive mechanism that identifies the "worst-performing" prefix—the weakest link in the chain—and increases its weight ($w_m$) in the loss function. Through a Karush–Kuhn–Tucker (KKT) derivation, they provide a stable, closed-form update for these weights.

Performance and Scaling

The results across 0.01B parameter models (TIGER and Llama backbones) are telling. APAO doesn't just improve accuracy; it improves efficiency. Using a smaller beam size ($K=20$) with APAO yields better results than standard models with $K=100$. This suggests that APAO makes the model significantly more robust to greedy pruning.

Analysis shows that as prefix length increases, the relative improvement of APAO over baselines grows, confirming it successfully prevents pruning at every stage.

Critical Insight: Why This Matters

The fundamental takeaway is that Autoregressive Generation $eq$ Sequence Identification. In recommendation, we aren't just generating text; we are navigating a structured tree of item identifiers.

APAO treats the generation process as a survival game. By focusing on "Worst-Prefix Optimization," it effectively hardens the model against the specific failures of Beam Search. While the pairwise variant is more computationally expensive ($O((B(N+1)T)$), the pointwise variant offers a "free" performance boost with zero added training complexity.

Conclusion

APAO represents a shift from "LLM-for-Rec" to "Search-Aware-Rec." By aligning the optimization objective with the actual constraints of the inference algorithm, the authors provide a principled way to improve generative models without needing larger architectures or more data.