One Pass, Any Order: Position-Invariant Listwise Reranking for LLM-Based Recommendation

1. Problem Statement

The paper addresses a critical reliability issue in using Large Language Models (LLMs) for listwise reranking in recommender systems.

• The Mismatch: Recommendation candidates form a mathematical set, but decoder-only LLMs process inputs as sequences.
• The Consequence: Standard LLM rerankers are order-sensitive. Permuting the order of the same candidate set can lead to different item scores and final rankings. This "position bias" means the ranking reflects prompt serialization rather than genuine user preference.
• Limitations of Existing Solutions:
  • Inference-time methods (e.g., permutation ensembling) improve stability but require multiple forward passes, increasing latency and cost.
  • Training-time regularization penalizes disagreement across permutations but does not prevent the model from accessing order information during computation.
  • Post-hoc calibration adjusts scores after the fact but does not fix the underlying instability.

2. Root Cause Analysis

The authors identify two specific architectural sources of order dependence in decoder-only LLMs:

1. Cross-Candidate Attention Leakage: In standard causal attention, tokens from one candidate can attend to tokens from other candidates in the sequence. This creates interference where an item's score depends on its neighbors.
2. RoPE-Induced Offset Drift: Under Rotary Positional Embeddings (RoPE), the relative positional offsets between candidates and the shared user context change when the candidate order is permuted. This alters attention patterns and scores even if the content remains the same.

3. Methodology: InvariRank

The authors propose InvariRank, a framework that enforces permutation invariance directly at the architectural level rather than through training objectives or inference aggregation. It operates in a single forward pass.

Key Architectural Components:

• Structured Attention Masking (Candidate Isolation):
  • The model imposes a structured segment mask that blocks cross-candidate attention.
  • Each candidate token is allowed to attend only to the shared user context (history/instruction) and its own tokens.
  • This prevents interference between candidates, ensuring $s_i = g_\theta(H, c_i)$ regardless of other items in the list.
• Shared Positional Framing:
  • To counteract RoPE drift, the authors assign positions using a "shared frame."
  • While the user context tokens occupy positions $1 \dots |T_H|$, every candidate segment is assigned positions starting immediately after the context ($|T_H| + 1 \dots$), independent of the candidate's order in the input sequence.
  • This ensures that the relative positional offset between any candidate and the user context remains constant, regardless of permutation.
• Listwise Training Objective:
  • Despite the independent scoring during the forward pass, the model is trained using a LambdaRank objective.
  • The loss function optimizes pairwise preferences weighted by the change in nDCG ($\Delta nDCG$). This preserves listwise supervision (ranking quality) while the architecture enforces invariance.

4. Key Contributions

1. Diagnosis: Identified cross-candidate attention leakage and RoPE offset drift as the concrete sources of position bias in LLM reranking.
2. InvariRank Framework: Proposed a novel architecture that achieves permutation invariance by design (via structured masking and shared framing) without requiring permutation-based training or ensembling.
3. Empirical Validation: Demonstrated that the model achieves near-perfect permutation robustness while maintaining competitive ranking effectiveness.

5. Experimental Results

The model was evaluated on MovieLens-32M and Amazon Books datasets using LLaMA 3.2 3B and Mistral 7B backbones.

• Permutation Robustness:
  • InvariRank achieved near-perfect robustness metrics: Kendall's $\tau \approx 0.99$ and Spearman's $\rho \approx 0.99$.
  • In contrast, standard Listwise Fine-Tuning (LFT) showed significantly lower robustness ($\tau \approx 0.88$), indicating its rankings still fluctuate with input order.
  • Inference-time baselines (like Bootstrapping) improved robustness but required multiple passes and still fell short of InvariRank's single-pass performance.
• Ranking Effectiveness:
  • InvariRank maintained competitive ranking performance (HR@10 and nDCG@10).
  • While standard LFT achieved slightly higher nDCG (e.g., 0.8486 vs. 0.8166 on ML-32M), InvariRank's performance was statistically comparable, proving that invariance does not require a massive sacrifice in accuracy.
• Position Bias:
  • Analysis of "Top-5 Exposure" showed that standard methods exhibited strong bias toward items appearing earlier in the prompt. InvariRank flattened this exposure, distributing it uniformly across input positions.

6. Significance and Conclusion

• Reliability: InvariRank solves the fundamental reliability problem of LLM-based recommenders, ensuring that rankings are based on content and user context, not arbitrary serialization.
• Efficiency: By achieving invariance in a single forward pass, it avoids the computational overhead of inference-time ensembling.
• Design Philosophy: The paper argues that architectural constraints are necessary to solve order dependence, as training objectives alone cannot fully decouple the model from positional artifacts.
• Limitations: The strict isolation of candidates removes potential benefits from cross-candidate interactions (e.g., direct comparison). Future work may explore hybrid designs that allow controlled interaction while maintaining invariance.

In summary, InvariRank provides a practical, efficient, and theoretically sound solution for deploying stable, order-invariant LLM rerankers in production recommendation systems.