Merge and Branch: Efficient Tree-Structured Supervised Fine-Tuning of LLMs for Recommendation

1 Introduction

• Generative recommendation predicts semantic identifiers from interaction histories, but text-rich histories can contain thousands of tokens for a target SID of only a few tokens.The introduction frames reducing history-processing cost while learning more from each history as the motivating question.Source: §1 · p. 1
• Additional observed future interactions and teacher-proposed synthetic targets provide supervision beyond the next item, while separate examples would repeatedly process the same history.The desired training structure shares history computation while keeping each target independent.Source: §1 · p. 1
• M&B combines a compact history with multiple independent target branches, compressing each historical item’s SID and text into learned tokens.The targets include observed future items and teacher-proposed synthetic targets; each branch attends to shared history and its own preceding SID tokens.Source: §1 · p. 1
• Tree FlashAttention computes the shared history once and accumulates gradients from every branch without materializing a dense attention matrix.A tree-structured key/value cache stores the shared history once while maintaining separate states for each beam hypothesis.Source: §1 · p. 1
• M&B outperforms sequential and generative recommendation baselines on three Amazon domains while reducing training cost and improving beam-search latency and memory use, especially at long contexts.The reported efficiency comparison is against processing uncompressed SID and text histories.Source: §1 · p. 1
• The paper’s contributions include an interaction token merger and multi-target objective combining observed and synthetic targets, plus tree kernels and shared-prefix caching for training and decoding.Source: §1 · pp. 1–2

2 Related Work

• Generative recommendation methods vary item representations and targets, including hierarchical SIDs [28], collaborative or behavioral tokenization [25] [32] [34], multiple-target supervision [1] [30], and non-autoregressive SID generation [14] [21] [26] [33] [35] [43].M&B retains the SID output space and focuses on multiple independent targets over a compact history.Source: §2 · p. 2
• LLM recommenders range from task-formulated encoder–decoder models [10] [16] and decoder-only candidate prediction [3] [22] to generated identifiers [13] [41] and continuous item embeddings.GenRec linearly merges SID embeddings and serializes targets into a page [44], whereas M&B jointly compresses SID and text and keeps targets independent.Source: §2 · p. 2
• Prior tree-attention work covers speculative verification and tree-structured training, while M&B targets shallow trees formed by long recommendation histories and short SID branches.Its tree kernels support multi-target fine-tuning, and its KV cache applies the visibility structure to constrained beam search.Source: §2 · p. 2

3.1 Problem Formulation and Overview

• M&B represents each user with an observed item history and predicts catalog items by generating their semantic identifiers (SIDs).Source: §3.1 · p. 2

3.2 Interaction Token Merging

• A shared merger compresses each interaction’s SID and text into N_q soft tokens, preserving item order for the LLM to model dependencies across interactions.SID-conditioned queries select content within each item; the outputs retain the SID anchor as a residual.Source: §3.2 · pp. 2–3

3.3 Multi-Target Training

• Training branches predict the primary next item, additional observed future items, and teacher-proposed synthetic targets from the shared history, without reading one another.Future targets capture further observed preferences, while synthetic targets transfer recommendations from a frozen teacher; group weights are distributed uniformly over available targets.Source: §3.3 · pp. 3–4

3.4 Tree FlashAttention

• Tree FlashAttention executes the shared-prefix layout without materializing a dense attention matrix, while preserving branch-specific visibility and gradients to the shared history.It computes the history once and shares its projections, feed-forward computation, and saved activations across targets.Source: §3.4 · p. 4

3.5 Shared-Prefix Beam Search

• The tree-structured KV cache stores at most T + WL token states per layer instead of W(T + L), saving (W − 1)T stored prefix states.Each beam hypothesis still attends to the history, but the shared prefix is stored only once.Source: §3.5 · pp. 4–5

4.1 Public Benchmarks (RQ1)

• M&B outperforms all baselines on all four metrics across three Amazon domains, improving 2.48%–16.19% over the strongest baseline for each metric.The benchmark compresses each item’s SID and text into one token.Source: §4.1 · p. 5, Table 3 · p. 6

4.2 Ablations (RQ2)

• Combining SID and text beats either input alone under next-item supervision; in the compact model, synthetic targets provide the largest gain and future targets improve accuracy further.Figure 3 reports component ablations on Beauty at Nq=4, with error bars showing standard deviations over five seeds.Source: §4.2 · p. 6, Figure 3 · p. 6
• Increasing the merged-token budget raises sequence length and training cost without consistently improving accuracy, so the main benchmark uses one token per item.The token-budget ablation varies Nq across 1, 2, 4, and 8.Source: §4.2 · p. 6, Figure 4 · p. 6
• Group weighting improves NDCG for both causal and tree layouts, and the weighted tree layout achieves the highest mean scores.The additional targets improve recommendation without requiring dependencies between targets.Source: §4.2 · p. 6, Figure 5 · p. 7

4.3 Efficiency (RQ3)

• Compact histories reduce training time and peak memory, while auxiliary branches cost much less than processing uncompressed SID-plus-text histories.Measurements use an effective batch size of 128 on H200.Source: §4.3 · p. 6
• Tree FlashAttention handles independent branches with modest runtime overhead and the same peak memory as causal FlashAttention; shared-prefix caching brings its largest beam-search benefits at long contexts.Standard attention is slower and more memory-intensive than tree FlashAttention at long contexts and runs out of memory at the longest context.Source: §4.3 · p. 7, Table 4 · p. 7, Figure 6 · p. 7

4.4 Convergence (RQ4)

• Qwen3 and LLaMA converge faster than T5, but can overfit late; validation-based checkpoint selection is preferable to training loss or a fixed epoch count.Pretraining and instructions mainly speed early progress, while Qwen3-1.7B achieves the best test performance at selected checkpoints.Source: §4.4 · p. 7, Figure 7 · p. 8
• Merged representations of validation- and test-first items mix with training items rather than forming separate clusters by data split.The embeddings are visualized in a shared t-SNE map fitted to text embeddings.Source: §4.4 · p. 7, Figure 8 · p. 8

• M&B reduces the cost of text-rich histories and learns from multiple targets, with strong recommendation performance alongside lower training and decoding costs.The paper frames these results as favoring learning more from each history rather than increasing the input processed.Source: §5 · p. 8
• Sharing history computation makes richer supervision possible at a small additional cost.Source: §5 · p. 8
• The current model assigns the same token budget to every item and predicts targets independently.Future work could allocate tokens according to item information or jointly generate recommendation lists to capture item relationships and balance relevance with diversity.Source: §5 · p. 8

• For a query row, invisible positions have score −∞, while the online softmax recurrence is introduced with initial values m(0)=−∞, z(0)=0, and a(0)=0.Source: A Tree FlashAttention Derivation · p. 10
• Joint normalization across prefix and branch tiles yields one softmax over visible keys, and the output divides the accumulated state by its normalizer.The saved log-sum-exp is computed from the final recurrence state.Source: A Tree FlashAttention Derivation · p. 10
• The backward pass recomputes visible probabilities and accumulates gradients blockwise without storing full probability or derivative matrices; branch keys and values receive contributions only from their own branch queries.With matching positions and zero dropout, packed and separate branches have the same weighted objective and gradients in exact arithmetic, though floating-point outputs may differ.Source: A Tree FlashAttention Derivation · p. 10

• Baseline results combine the authors’ runs, results from original papers, and published reproductions; P5-CID and LC-Rec use the GRAM reproduction because their original evaluations lack the same three Amazon domains.Source: §B.1 · p. 10
• The authors reproduce LETTER on Sports and Toys, ETEGRec on all three datasets, and EAGER-LLM on Toys using official or released implementations and recommended settings.Source: §B.1 · p. 10
• For SASRec, SASRec-CE, and BERT4Rec, the selected run maximizes validation NDCG@10, and its test metrics are reported.The tuning search varies history length, model size, layers, learning rate, weight decay, and dropout; BERT4Rec also varies mask ratio.Source: §B.1 · p. 10

B.2 M&B on Public Data

• Each item is represented by its SID, title, category, and description; public benchmarks omit action-type and time-bucket embeddings.SIDs use Sentence-T5-XXL embeddings, a 3-level, 256-way RQ-VAE, and a deterministic collision-suffix token, for depth 4.Source: §B.2 · p. 10
• Training windows contain the next observed item, at most one additional future item, and two synthetic targets, while retaining windows without an additional future item.No held-out item fills a missing branch; group weights are λS = 1.0 and λF = 0.25, distributed across valid branches.Source: §B.2 · p. 10
• Runs fine-tune Qwen3 1.7B with Nq = 1, a maximum history length of 20, and validation NDCG@10 checkpoint selection.Training uses four epochs, batch size 128, tree attention, and beam width 50.Source: §B.2 · p. 10

B.3 Efficiency Measurement

• Tree FA matches causal FA peak allocated memory with negligible runtime overhead across tested contexts; standard attention with an explicit mask grows rapidly in cost as context length increases.The H200 attention benchmark uses BF16, batch size 128, and averages 30 forward–backward iterations after warm-up in each of five repeats.Source: §B.3 · p. 10, Table 5 · p. 11
• Decoding efficiency is measured at batch size one with beam width 100 on synthetic 64–2048-token contexts, using identical inputs and catalog constraints for both methods.Timing includes prefill and beam search but excludes shared input preparation and trie construction; numerical differences may change beam candidates.Source: §B.3 · p. 11
• End-to-end training measurements use tree FA, BF16, a compiled backbone, five independent runs, and effective batch size 128.The component and token-budget ablations report that auxiliary supervision improves recommendation performance, whereas additional queries increase training cost without consistently improving accuracy.Source: §B.3 · p. 11

B.4 Auxiliary Branch Counts and Weights

• The best tested settings are λF = 0.25 for future supervision and SB×2 with λS = 1.0 for synthetic supervision.Table 9 studies future and synthetic supervision separately, each added to the next-item objective.Source: §B.4 · p. 11, Table 9 · p. 12
• Adding more synthetic branches at the same total weight improves Recall@10 but reduces NDCG@10, indicating a trade-off between retrieval coverage and top-ranked relevance.The study varies the number and weights of future and synthetic branches on Beauty.Source: §B.4 · p. 11, Table 9 · p. 12