Technical Summary: SAPO (Step-Aligned Policy Optimization)

1. Problem Statement

Generative recommendation treats next-item prediction as an autoregressive generation task, where items are encoded as Semantic Identifiers (SIDs)—short, coarse-to-fine token sequences (e.g., $K=3$ levels) produced by a hierarchical vector quantizer. Recent approaches augment these systems with explicit reasoning traces (thinking blocks) and optimize them using Reinforcement Learning from Verifiable Rewards (RLVR), typically employing Group Relative Policy Optimization (GRPO) with outcome-reward feedback.

The core problem identified is a mismatch in action granularity between the outcome-reward signal and the structured nature of SID decoding:

• Coarse Rollout-Level Feedback: Standard outcome-reward GRPO assigns a single scalar reward (exact-match indicator) to the entire generated response. It verifies only whether the final SID tuple matches the ground truth.
• Fine-Grained Structure: In large-catalog recommendation, a generated SID tuple may partially match (e.g., correct coarse-level tokens but incorrect fine-level tokens). Outcome-reward RL fails to distinguish between a "near miss" (correct prefix, wrong suffix) and a "total failure" (wrong prefix).
• Consequences: This mismatch leads to two failure modes:
  1. Penalization of Correct Steps: Matched SID-token positions are penalized alongside mismatched positions because the scalar advantage is broadcast to the entire sequence.
  2. Loss of Localization: The scalar advantage cannot isolate which specific reasoning step or SID-token prediction caused the error. This results in unstable training dynamics, length drift, and format degradation, particularly when exact-match feedback is sparse.

2. Methodology: SAPO

The authors propose SAPO (Step-Aligned Policy Optimization), a reinforcement learning method that aligns the credit assignment unit with the natural decomposition of the SID decoding process.

Core Design: The Reasoning Step

SAPO defines a reasoning step as the pairing of one thinking block (reasoning trace) with its corresponding SID token. For a $K$-level SID hierarchy, a response consists of $K$ such steps: $(\tau^{(k)}, s^{(k)})$, where $\tau^{(k)}$ is the $k$-th thinking block and $s^{(k)}$ is the $k$-th SID token.

Key Components

1. Reasoning-Step Match Reward:
   Instead of a single reward at the end of the rollout, SAPO assigns a reward $r_{i,k}$ to each reasoning step $k$.
   $$r_{i,k} = \alpha \cdot \mathbb{I}[s^{(k)}_i = s^{(k)}_{gt}] + \beta \cdot \mathbb{I}[k=K] \cdot b_i$$
   Where the first term provides a dense, verifiable match signal for each SID token position, and the second term is a small format bonus for the final step if the response structure is valid. This preserves the exact-match optimum while providing denser supervision.

2. Step-Level Group-Relative Advantage:
   SAPO computes the advantage $\hat{A}_{i,k}$ independently for each reasoning step $k$ within a group of $G$ rollouts:
   $$\hat{A}_{i,k} = \frac{r_{i,k} - \text{mean}_{i'}(r_{i',k})}{\text{std}_{i'}(r_{i',k})}$$
   This ensures that rollouts differing only at a specific SID level receive a contrastive update signal only at that step, rather than broadcasting a global signal.

3. Step-Aligned Surrogate with Step-Normalized Token Aggregation:
   The policy gradient objective is optimized over reasoning steps. The advantage is normalized by the length of the step unit ($|y^{(k)}_i| = |\tau^{(k)}| + 1$) before being applied to the tokens within that step:
   $$J_{SAPO}(\theta) = \mathbb{E} \left[ \frac{1}{\sum |y_\ell|} \sum_{i} \sum_{k} \sum_{t \in y^{(k)}_i} \min \left( w_{i,t}(\theta) \tilde{A}_{i,k}, \text{clip}(\dots) \tilde{A}_{i,k} \right) \right]$$
   where $\tilde{A}_{i,k} = \hat{A}_{i,k} / |y^{(k)}_i|$. This prevents long reasoning blocks from dominating the gradient update magnitude.

3. Key Contributions

• Identification of Granularity Mismatch: The paper identifies that outcome-reward RL is misaligned with hierarchical SID decoding because it treats the entire rollout as a single action unit, obscuring which specific token predictions caused errors.
• SAPO Algorithm: A novel RL method that treats the (thinking block, SID token) pair as the atomic action unit. It derives a per-step match reward, a step-level group-relative advantage, and a step-aligned surrogate loss without requiring a learned reward model.
• Theoretical Consistency: The authors prove that the cumulative per-step match reward preserves the exact-match optimum under realizability conditions, ensuring that the denser supervision does not alter the fundamental objective.
• Empirical Validation: Extensive experiments on three real-world Amazon datasets (Office Products, Video Games, Industrial & Scientific) demonstrate that SAPO stabilizes RL training and improves ranking metrics (Recall and NDCG) compared to outcome-reward baselines.

4. Experimental Results

• Performance: SAPO consistently outperforms existing generative recommendation baselines, including traditional sequential models (SASRec, GRU4Rec), non-reasoning generative models (TIGER, HSTU), and reasoning-based models using outcome-reward RL (SIDReasoner, OneRec-Think).
  • SAPO achieved the best NDCG across all columns in the main results table.
  • Improvements were most pronounced in settings where sparse exact-match feedback makes fine-grained credit assignment critical.
• Training Dynamics:
  • Stability: SAPO exhibits steadier reward trajectories and prevents the reward collapse and oscillation observed in GRPO.
  • Length Control: Unlike GRPO, which often suffers from response length drift and KL divergence growth, SAPO maintains controlled reasoning budgets and step-wise lengths.
  • SID Match Rate: SAPO shows a stronger correlation between training progress and actual SID-token prediction accuracy.
• Ablation Studies: Removing either the per-step advantage or the per-step match reward degrades performance, indicating that both components are complementary. The full SAPO configuration is necessary to achieve both stability and high ranking quality.
• Case Studies: Qualitative analysis shows that SAPO preserves fine-grained evidence (e.g., specific product features like "stepper motor control") that outcome-reward models often wash out into generic reasoning, leading to more accurate SID predictions.

5. Significance and Claims

The paper claims that reinforcement learning objectives for structured generation should mirror the decoder's own decomposition of the output.

• Generalizability: The authors suggest that whenever a generation task admits a natural hierarchical decomposition (e.g., codebooks, tool-call schemas, structured answers), this hierarchy can serve as a fundamental source of per-step supervision for RL, eliminating the need for learned reward models.
• Efficiency: SAPO achieves these gains without significant computational overhead; the additional reward and advantage computation time is negligible (<1% of the update step).
• Modest Scope: The authors acknowledge limitations, noting that their evaluation is currently restricted to three English Amazon categories with a fixed $K=3$ SID hierarchy. They do not claim universal superiority but highlight that their approach specifically addresses the credit-assignment failure modes inherent in outcome-reward RL for hierarchical token generation.