HPSERec: A Hierarchical Partitioning and Stepwise Enhancement Framework for Long-tailed Sequential Recommendation

Thank you. We've made responses (Res) to all Questions (Q):

Q1: What is the computational cost introduced by training experts? Could this be theoretically analyzed?

Res to Q1: We sincerely thank you for raising this important question. In the Feedforward stage, using SASRec as the base recommender architecture, the overall computational complexity of expert training can be expressed as: $\mathcal{O}(E \cdot T^2 \cdot d \cdot L_T)$ where $T$ denotes the sequence length, $d$ is the embedding dimension, $L_T$ is the number of Transformer layers, and $E$ is the number of expert modules. This reflects the fact that each expert is trained independently on a subset of data in a staged manner. In the Feedback stage, the cost is primarily associated with computing soft alignment between user representations via Sinkhorn optimal transport. Specifically, constructing the pairwise similarity matrix has complexity $\mathcal{O}(m^2 \cdot d)$. The Sinkhorn-Knopp algorithm, with t iterations, has complexity $\mathcal{O}(t \cdot m^2)$, resulting in an overall cost of $\mathcal{O}(m^2 \cdot (d + t))$, where $m$ is the batch size (typically 128 or 256), $d$ is the embedding dimension, and $t$ is the number of Sinkhorn iterations (usually between 10 and 20). Given the relatively small size of $m$, this cost remains manageable and GPU-friendly. Finally, in the inference stage, only the final expert is used for prediction. Hence, the inference complexity is $\mathcal{O}(T^2 \cdot d \cdot L_T)$, which is equivalent to that of a standard SASRec model, ensuring no additional latency at test time.

In summary, the overall training complexity is $\mathcal{O}(E \cdot T^2 \cdot d \cdot L_T) + \mathcal{O}(m^2 \cdot (d + t)),$ and the inference complexity is $\mathcal{O}(T^2 \cdot d \cdot L_T)$.

Q2: Does the entire training process guarantee convergence? How is convergence determined?

Res to Q2: Thank you for raising this important question. Due to the complexity of our model, which involves multiple expert networks, knowledge distillation, and the Sinkhorn optimal transport mechanism, we have not provided a formal theoretical proof of convergence in the paper. However, empirical evidence shows that the training process of HPSERec is stable and exhibits clear convergent behavior. For example, on the Music dataset, HPSERec typically converges within approximately 20 epochs, while on the Yelp dataset, convergence is generally achieved within around 15 epochs. We employ the following combined strategies to determine model convergence:

1. Validation metrics (e.g., HR@10, NDCG@10) are computed after each epoch. Early stopping is triggered if no improvement is observed for a consecutive number of epochs (default: 5).
2. The overall training loss (encompassing both cross-entropy and feedback losses) consistently exhibits stable descent and eventual convergence across multiple experimental runs.

Q3: Does the stepwise data-increment method for training experts ensure diverse data distribution across different experts?

Res to Q3: Thank you for your question. In our method, each expert receives a different subset of user interaction sequences and is assigned a distinct responsibility. Specifically, the first expert is trained only on long-tail items, the second expert on long-tail plus mid-tail items, and so on, with the final expert receiving all items. Accordingly, the first expert focuses on learning users’ long-tail interests, the second expert on mid-tail interests, and the final expert on users’ global preferences. This diversity in training data across experts inherently ensures that each expert captures a different aspect of the user-item distribution.

Q4: Which expert does the model rely on for its final output?

Res to Q4: Thank you for raising this question. As explained in our response to the previous question, the final expert is responsible for learning the complete user interest representation. Therefore, the model relies on the output of the last expert for its final prediction.

Thank you. We've made responses (Res) to all Questions (Q):

Q1: The proposed method trains user interests starting from tail interests in the feedforward module until complete user interests are learned. However, is the reverse approach more reasonable?

Res to Q1: Thank you for raising this insightful question. This issue was indeed considered during our experimental exploration. Our empirical results show that starting from tail interests achieves superior performance. This observation can be interpreted as follows: In the feedforward module, beginning from head items allows the model to learn well-established knowledge, which is then propagated to the global user representation. While this seems plausible, it presents a limitation in the feedback stage. Since head interests are already well trained, using the global representation to supervise them yields marginal gains. In contrast, our proposed approach begins with tail interests in the feedforward module and progressively transfers this knowledge upward. We hypothesize that this process implicitly assigns more importance to tail interests, encouraging the global user representation to better encode information from the long tail. Subsequently, in the feedback module, the global representation guides the refinement of tail interests, delivering additional supervision and significantly enhancing their accuracy. This targeted reinforcement helps to overcome the inherent sparsity and noise associated with tail data, leading to more robust overall performance.

Q2: Why does this paper not include comparisons with classical long-tail recommendation methods, such as LightGCN?

Res to Q2: Thank you for raising this important question. As demonstrated in many related studies [2,6], the accuracy of several classical long-tail recommendation methods, such as LightGCN, is generally lower than that of the more advanced baselines we compared against in this paper. To further strengthen our experimental evaluation, we will include two recent long-tail recommendation methods, named ASReP and INSERT, in the comparative experiments in the final version of the paper.

[2] K. Kim, D. Hyun, S. Yun, and C. Park, “Melt: Mutual enhancement of long-tailed user and item for sequential recommendation,” in Proceedings of the 46th international ACM SIGIR conference on Research and development in information retrieval, 2023, pp. 68–77.

[6]Z. Liu, Z. Fan, Y. Wang, and P. S. Yu, “Augmenting sequential recommendation with pseudoprior items via reversely pre-training transformer,” in Proceedings of the 44th international ACM SIGIR conference on Research and development in information retrieval, 2021, pp. 1608–1612.

Q3: Is there a potential error in the definition of data imbalance (Equation 5)? Could the authors clarify the meanings of the two exponential terms (α and 1/(1−α)) separately?

Res to Q3: Thank you for raising this important question. The definition in Equation (5) is essentially derived from a variant of Rényi entropy, which is designed to quantify the unevenness of interaction frequency distributions within each subset. In our context, it serves as a measure of the “entropy-based imbalance” for each partitioned item group.

1. The parameter α controls the sensitivity of the metric to the distribution of probabilities. When α -> 0, all items are treated nearly equally, resembling a measure of set cardinality. As α -> \infty, the metric becomes increasingly dominated by the highest-frequency items, thus emphasizing head items in a long-tail distribution. A smaller α encourages more uniform subset splits, while a larger α highlights skewed distributions. In essence, α determines the smoothness and focus of the entropy measure.
2. 1/1-α is not an independent parameter but a structural component of the Rényi entropy definition. It acts as a power transformation to normalize the scale of \sum p_i^α across different values of α, ensuring that the resulting measure remains comparable across settings. Its purpose is to map the aggregated value back into the entropy space, where higher values indicate lower imbalance and greater distributional uniformity.

Q4: While the paper primarily addresses the long-tail distribution of known items, how does the proposed method perform on entirely cold-start items?

Res to Q4: Thank you for raising this important question. The key issue addressed in this paper is the long-tail problem, which, although related to the cold-start problem, has a distinct definition and focus. The long-tail problem arises from the imbalance in user-item interactions, which results in suboptimal recommendations for users and limited exposure for less popular items. In contrast, the cold-start problem refers to the challenge of making recommendations when users or items have little to no historical interaction data. In our future work, we plan to explore how the proposed framework can be extended to effectively handle cold-start scenarios.

Thank you. We've made responses (Res) to all weaknesses (W) and Questions (Q):

W1, W2 & Q1: Regarding the division of head and tail, it seems that for different data sets, a simpler strategy can be used to divide them through statistical information. The division method proposed by the author is reasonable, but is it necessary? Could the authors provide comparative experiments using simpler or naive grouping strategies to better demonstrate the necessity and effectiveness of their proposed partitioning approach?

Response to W1, W2 & Q1: We sincerely thank the reviewer for this insightful suggestion. While simpler partitioning strategies do exist, they tend to compromise overall model accuracy, which is the central focus of this work. In fact, we carefully considered multiple partitioning strategies during the design of our method, and experimental results consistently showed that these alternatives underperformed compared to our proposed approach. To further evaluate the necessity and effectiveness of our method, we conducted experiments with two additional variants: 1) HPSERec-QSplit adopts a simpler quantile-based partitioning strategy that statically divides items based on their interaction counts. This comparison helps evaluate whether the use of more complex partitioning algorithms is justified in practice. 2) HPSERec-DPPrune incorporates a pruning-based optimization into our original dynamic programming framework. While this variant does not guarantee finding the global optimum, it substantially improves computational efficiency.

The corresponding experimental results are presented below.

W3: The author focuses on the long-tail problem, but in the selection of baselines, there are not enough methods that focus on the long-tail problem for comparison.

Res to W3: Thank you for highlighting this limitation. Among the seven baselines we included in our current experiments, three methods, CITIES, MELT, and LLM-ESR, are specifically designed to address the long-tail recommendation problem. In the final version of the paper, we will further enrich the comparative evaluation by including additional long-tail-focused baselines, namely ASReP and INSERT, to provide a more comprehensive assessment.

The corresponding experimental results are presented below.

W4: The experiment in Figure 4 is difficult to understand, and the correspondence between the two axes and the figure should be more clearly stated. At the same time, it seems that the performance trends of different methods in different groups are consistent, which does not seem to clearly show the advantages of the author's method for long-tail problems.

Res to W4: Thank you for your valuable suggestion. We acknowledge that Figure 4 lacks a clear explanation in its current form. In this figure, we split users and items into seven groups based on sequence length and popularity, respectively. The bar chart represents the number of users or items in each group, while the line chart indicates the recommendation performance of each method within the corresponding group.

It is true that all methods exhibit a consistent performance trend, with weaker results on tail data and stronger results on head data, which is a common characteristic in long-tail recommendation scenarios. However, closer inspection reveals distinctive behaviors among the models: for instance, MELT performs well on head items but suffers significantly on tail items. In contrast, our proposed HPSERec achieves the best performance across all user groups, demonstrating its ability to provide consistent and high-quality recommendations for both head and tail users.

In the final version of the paper, we will offer a more precise explanation of both axes and the comparative insights it conveys, to ensure greater clarity and stronger support for our claims.

W5: The method is relatively complex, and it is recommended to add experiments to demonstrate its scalability.

Res to W5: Thank you for your suggestion. We acknowledge that the current version of the paper lacks a thorough discussion of the scalability of our proposed method. In the present submission, we have evaluated the integration of our framework with SASRec. To address this concern, we will include additional experiments in the final version by incorporating our framework into FMLP, thereby providing a more comprehensive analysis of the method’s scalability and adaptability to different backbone architectures.

Thank you. We've made responses (Res) to all Questions (Q):

Q1: The authors note in the appendix that the proposed method is only suitable for small-scale datasets, but fail to clarify its potential industrial application scenarios. Could the authors elaborate on how this approach might be adapted or scaled for real-world industrial deployment?

Res to Q1: Thank you for raising this important question. This method can mainly be divided into two parts: dataset division and recommendation framework. Although the algorithm complexity of dataset division is relatively high, in the industrial field, it is acceptable for an item pool in the tens of millions. As for the recommendation framework part, although the training process involves multiple expert networks, in the inference stage, we only use the last expert network. In future research, we will combine it with incremental learning algorithms to further enhance the practicality of this method.

Q2: Although thposed alternating training strategy—optimizing downstream experts during the feedforward moduleand fine-tuning upstream experts in the feedback module—significantly improves model performance, does the backpropagation-based update of upstream expert parameters during the feedback module risk disrupting the already stabilized parameters learned in the feedforward module?

Res to Q2: Thank you for the insightful question. While it is reasonable to be concerned that updating upstream experts via backpropagation may cause representation drift, our framework is specifically designed to mitigate this risk. The updates in the feedback module are guided by an optimal transport plan that ensures distribution-consistent fine-tuning rather than disruptive re-learning. Empirically, the feedback module consistently improves performance across head and tail users/items, indicating that it enhances rather than destabilizes upstream representations.

Thank you. We've made responses (Res) to all weaknesses (W) and Questions (Q):

W1: While the proposed distribution balancing algorithm improves over fixed-ratio partitioning, it still assumes static, discrete partitions of items and users. The method does not address temporal dynamics, gradual shifts in item popularity, or cross-group interactions, which are common in real-world recommendation scenarios. This limits the generalizability of the approach beyond the datasets and static environments tested.

Res to W1: Thank you for your insightful question. Our method is not intended for modeling temporal dynamics or behavioral evolution, but rather focuses on constructing a more reasonable data partitioning structure to enable subsequent models to better utilize tail data. In our future work, we can incorporate the time factor by combining "sliding window partitioning" or "incremental re-grouping" methods, and integrate incremental learning recommendation algorithms to further enhance the practicality of the method.

W2: The use of multiple expert models, stepwise distillation, and computationally expensive Sinkhorn optimal transport introduces non-negligible computational overhead. The paper lacks a detailed analysis of training and inference efficiency, particularly on large-scale datasets or in real-time scenarios.

Res to W2: Thank you for your valuable comment. We agree that computational overhead is a critical factor in assessing the practicality of recommendation systems. Compared to recent long-tail recommendation methods that incorporate large language models, our method introduces significantly lower computational complexity.

The training complexity of our method is $\mathcal{O}(E \cdot T^2 \cdot d \cdot L_T) + \mathcal{O}(m^2 \cdot (d + t)),$ where $E$ is the number of expert modules, $T$ is the sequence length, $d$ is the embedding dimension, $L_T$ is the number of Transformer layers, $m$ is the user batch size, and $t$ is the number of Sinkhorn iterations.

The inference complexity is $\mathcal{O}(T^2 \cdot d \cdot L_T),$ which matches that of standard Transformer-based recommenders, as only the final expert is used during inference. We will include the complete theoretical analysis of computational complexity in the appendix of the final version of the paper.

Q1: How sensitive is the performance of HPSERec to the number of partitions (L)?

Res to Q1: We thank you for your insightful question. In the hyperparameter analysis section of our paper (Appendix B.2), we systematically investigate the impact of the number of partitions L on model performance. Specifically, we evaluate the model on the Yelp and Beauty datasets by varying L from 2 to 6, and observe the following trends:

1. When L ranges from 2 to 4, the model exhibits notable improvements in HR@10 and NDCG@10, indicating that appropriately partitioning the item space facilitates tail representation enhancement and alleviates data imbalance.
2. When L > 4, the performance gains become marginal or slightly degrade. This is primarily due to over-segmentation, which results in fewer interactions per upstream subset. Consequently, the representation quality deteriorates, diminishing the effectiveness of knowledge distillation.

Overall, HPSERec exhibits moderate sensitivity to the choice of $L$, but maintains stable performance within a reasonable range, making it practical and easy to tune in real-world applications.

Q2: Have you explored adaptive or learned partitioning beyond static imbalance-based splitting?

Res to Q2: Thank you for your thoughtful question. We have indeed explored adaptive or learned partitioning methods, such as incorporating clustering losses to guide subset construction via deep learning. However, these approaches did not yield satisfactory results and introduced substantial computational overhead to the overall framework. To further evaluate the necessity and effectiveness of our method, we conducted experiments with two additional variants: 1) HPSERec-QSplit adopts a simpler quantile-based partitioning strategy that statically divides items based on their interaction counts. This comparison helps evaluate whether the use of more complex partitioning algorithms is justified in practice. 2) HPSERec-DPPrune incorporates a pruning-based optimization into our original dynamic programming framework. While this variant does not guarantee finding the global optimum, it substantially improves computational efficiency. The corresponding experimental results are presented below.

Although the time complexity of these schemes is not as high as that of the method described in the text, the focus of this study is on accuracy, so we have abandoned the other methods.