SAPO: Step-Aligned Policy Optimization for Reasoning-Based Generative Recommendation

Zaiyi Zheng, Guanghui Min, Yaochen Zhu, Liang Wu, Liangjie Hong, Chen Chen, Jundong Li · 2026

Read SAPO: Step-Aligned Policy Optimization for Reasoning-Based Generative Recommendation by Zaiyi Zheng, Guanghui Min, Yaochen Zhu, Liang Wu, Liangjie Hong, Chen Chen, Jundong Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17648.txt.

Introduction

Zaiyi Zheng and colleagues present Step-Aligned Policy Optimization (SAPO) for reasoning tasks. Recommendation treats next-item picks as semantic identifier generation. In large catalogs, exact-match feedback only says whether the final item is correct, not which token caused it. The credit unit is one step: one thinking block plus one identifier token. SAPO computes a separate advantage per step, applied only to the corresponding thinking block and token. Across three datasets, SAPO stabilizes training and improves over baselines, with the largest gains where feedback is sparse.

Catalog record

CREATORZaiyi Zheng, Guanghui Min, Yaochen Zhu, Liang Wu, Liangjie Hong, Chen Chen, Jundong Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82194
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.17648

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SAPO: Step-Aligned Policy Optimization for Reasoning-Based Generative Recommendation Zaiyi Zheng, Guanghui Min, Yaochen Zhu, Liang Wu, Liangjie Hong, Chen Chen, Jundong Li Abstract Generative recommendation treats next-item prediction as autoregressive item-identifier generation. Specifically, items are encoded as semantic identifiers (SIDs), which are short coarse-to-fine token sequences whose early tokens capture broad semantics and later tokens refine them. Recent work augments this paradigm with reasoning traces and optimizes them via reinforcement learning with verifiable rewards, typically outcome-reward algorithm with exact-match feedback on the generated SID. However, in large-catalog recommendation, exact-match feedback on the generated SID only reports whether the final item is correct; when a generated SID mismatches, outcome-reward cannot identify which SID-token prediction caused the mismatch and may penalize matched SID-token positions together with the mismatched position. We identify that the natural unit of credit assignment in this setting is a single reasoning step (one thinking block paired with one SID token). We instantiate this idea in SAPO (Step-Aligned Policy Optimization): rather than broadcasting one advantage to the whole response, SAPO computes a separate group-relative advantage for each reasoning step and applies it only to the corresponding thinking block and SID token. Across three real-world recommendation datasets, SAPO stabilizes reinforcement-learning training and consistently improves over existing generative recommendation baselines, with the largest gains where sparse exact-match feedback makes reasoning-step credit assignment important. Our results suggest that reinforcement-learning objectives for structured generation should mirror the decoder’s own decomposition of the output. Our code is available at https://github.com/zhengzaiyi/SAPO . 1 Introduction The item recommendation task requires a model to identify items a user is likely to interact with from a large catalog of closely related candidates. Traditional systems typically decouple candidate retrieval from ranking, whereas generative recommendation offers an alternative by casting recommendation as autoregressive item generation. Building on advances in language modeling [ 12 ] , this formulation has become increasingly attractive, with prior work demonstrating strong empirical performance [ 14 , 1 ] . Because assigning a unique token to every item would require a prohibitively large output vocabulary, items in this paradigm are represented as semantic identifiers (SIDs), which are short token sequences produced by a hierarchical vector quantizer. The language model is then trained to autoregressively generate the SID of the item a user will interact with next. A complementary line of work augments generative recommenders with explicit reasoning traces, typically by prompting the model to produce a reasoning trace before SID decoding [ 9 , 23 , 10 , 3 ] . These traces are intended to help the model interpret user histories and surface relevant preference signals prior to generating an item identifier. Recent systems increasingly adopt a post-training recipe that first aligns the backbone to the recommendation vocabulary via supervised fine-tuning (SFT), then activates structured reasoning, and finally applies reinforcement learning (RL) from verifiable rewards (RLVR) [ 6 ] when reliable outcome checks are available. This recipe bridges SFT-only reasoning recommenders and newer SFT-then-RL variants, including GRPO-style approaches for recommendation [ 29 ] . Once a response contains both a reasoning trace and a multi-token SID, the central training question becomes one of credit assignment under the match feedback of SID: which SID-token prediction caused the final mismatch? For hierarchical SID decoding, credit assignment should respect the positional structure of the SID hierarchy. While final-item verification checks only the whole SID tuple, each SID-token position reveals whether the model has captured fine-grained item information or has failed to identify the broad intent. Outcome-reward RL discards this structure by broadcasting a scalar reward across the reasoning tokens and all SID-token predictions. This mismatch produces two failure modes: matched SID-token positions can be penalized together with the mismatched position, and scalar advantage broadcast cannot localize the mismatched SID-token prediction among unrelated reasoning steps. The underlying issue is action granularity: the rollout is too coarse, yet individual tokens are too fine-grained to serve as the credit-assignment unit for structured SID decoding. To address this mismatch, we propose SAPO , a reinforcement learning method for the RL stage of reasoning-based generative recommendation. SAPO exploits the structure already present in SID decoding: each generated SID tuple exposes multiple verifiable token predictions, giving every rollout a natural decomposition into reasoning steps. We therefore define a reasoning step as one thinking block paired with its corresponding SID token and treat this pair as the action unit for reinforcement learning. Once the action unit is fixed, the rest of the update follows naturally: SAPO assigns a verifiable match reward to each reasoning step from SID-token correctness, estimates a group-relative advantage at the reasoning-step level, and optimizes a step-aligned surrogate with step-normalized token aggregation so that each reasoning step receives its own update signal. The resulting credit assignment remains consistent with the original exact-match objective while providing denser supervision when exact SID-tuple matches are sparse. Our main contributions are as follows: • We identify the mismatch between exact-match outcome feedback and reasoning-based SID decoding as a problem of action granularity: rollout-level rewards cannot identify the specific mismatch steps, while rollout-level advantages can penalize matched step positions (Section 3 ). • We propose SAPO , which treats each reasoning step, pairing one thinking block with one SID token, as the RL action unit and derives from this choice a verifiable per-step match reward, a step-level group-relative advantage, and a step-aligned surrogate with step-normalized token aggregation, and introduces no learned reward model (Section 4 ). • Experiments on three real-world recommendation datasets show that SAPO produces more stable RL dynamics and yields strong overall Recall and NDCG results, especially in settings where fine-grained credit assignment matters (Section 5 ). 2 Preliminaries This section introduces the notation and setup used throughout the paper; Appendix A provides a consolidated summary of symbols and notations used in the paper. 2.1 Generative Recommendation with Hierarchical Semantic Identifiers We formulate generative recommendation over hierarchical semantic identifiers (SIDs). Let \mathcal{C} denote the item catalog. Following recent work on generative recommendation with SIDs [ 14 , 1 ] , each item v\in\mathcal{C} , where v denotes an item, is mapped to a tuple of K SIDs. The tuple can be obtained with a hierarchical vector-quantization scheme, such as a residual-quantization variational autoencoder (RQ-VAE) adapted from residual-quantized image generation [ 7 ] . Let \mathcal{V}^{(k)} denote the vocabulary of the k -th codebook for k=1,\ldots,K . The quantizer defines an injection \phi\colon\mathcal{C}\to\mathcal{V}^{(1)}\times\mathcal{V}^{(2)}\times\cdots\times\mathcal{V}^{(K)} . Let \Phi\mathrel{:=}\phi(\mathcal{C}) denote the set of valid catalog SID tuples. Each item v is then uniquely represented as \phi(v)=(s^{(1)},s^{(2)},\ldots,s^{(K)}) , where s^{(k)}\in\mathcal{V}^{(k)} captures progressively finer-grained item semantics, with larger k corresponding to finer semantic levels. We set K{=}3 , which suffices to uniquely identify every item in our catalogs. Given a chronologically ordered user interaction history x=(v_{1},\ldots,v_{T_{x}}) , we study the sequential recommendation task of predicting the next item v^{\star}=v_{T_{x}+1} . The history is encoded as a textual prompt that contains past interactions and a task instruction, and we learn a policy \pi_{\theta}(y|x) parameterized by a language model with parameters \theta . Its response y terminates in a valid SID tuple \phi(\hat{v})\in\Phi , where \hat{v} denotes the predicted next item. In the simplest non-reasoning setting, the policy directly decodes the K SID tokens. We defer the reasoning-augmented response layout and the

Read the complete text