DIRECTOR: Dynamic Index-based Recommendation with Transport-Optimized Retrieval
Yuanhao Pu, Chenghao Zhang, Chao Feng, Xiang Li, Defu Lian
cs.IR
2026-07-29
DIRECTOR replaces autoregressive reranker decoding with one-shot parallel matching. On Kuaishou it cuts CPU 66.7% at matched throughput, beating the best baseline by up to 3.7% NDCG@6.
Reranking is the late stage of a multi-stage recommender that turns an upstream candidate set (size M) into an ordered, duplicate-free slate (length n). The search space is enormous: M=50 and n=10 already gives about 3.7e16 valid slates, and quality depends on position effects, competition, and complementarity, so it is a combinatorial problem.
The dominant setup is Generator-Evaluator: a generator proposes K candidate slates, a list-wise evaluator scores each complete slate with a single scalar, and the highest wins. The evaluator is often an opaque industrial service with no gradients.
The two existing generator approaches each have a hard flaw. Autoregressive (AR) generators pick one position at a time, each choice depending on the previous ones, which models inter-position dependencies naturally; but under greedy or beam search they are stuck: each step waits on the previous one (sequential latency), and a prefix that misses the beam is pruned forever even if it could have grown into the globally best slate. Non-autoregressive (NAR) generators predict all positions in parallel and are fast, but treat positions as independent, defining probability over the duplicate-allowing C^n, so different positions grab the same high-probability item and produce duplicate or conflicting selections that need post-hoc fixing, which drags the sequential procedure back in.
DIRECTOR wants all three at once: NAR parallel speed, global position coordination, and training from a scalar-only evaluator.
DIRECTOR has four parts.
Candidates are encoded into a shared retrieval space (computed once per request, reused across positions and proposals). A context encoder summarizes the request and candidate pool. Instead of predicting which discrete item each position takes, it generates a continuous matrix of dynamic retrieval indices Q (n by d), each row being that position's retrieval intent, a position-aware latent query conditioned on both the user context and the current candidate pool. All n indices are generated jointly, and sampling Q repeatedly yields K proposals with no autoregressive rollout. The generator comes in CVAE and diffusion variants.
Training uses entropy-regularized optimal transport (OT) for supervision. The feasible set is the key: every position must be filled (a row equality constraint), and every candidate is used at most once (a column capacity inequality). This shared capacity constraint couples all positions, so when several positions compete for one candidate their transport masses are adjusted jointly rather than normalized independently. The authors prove this optimum is unique and strictly positive; independent row-wise softmax cannot express this coupling, which is exactly why naive NAR produces duplicates.
At inference the OT solver is bypassed and DIRECTOR solves global hard matching directly (rectangular Hungarian, augmenting-path). Another theorem guarantees a bijection between hard matching and valid slates, with no integrality gap in the LP relaxation, so the output is complete and duplicate-free by construction. K proposals are K independent assignments solved in parallel, with an overhead ratio of O(n/d), cheap because n is far smaller than d.
The last part is prefix-anchored credit assignment. The evaluator is opaque and returns only a scalar for a complete slate, so broadcasting that scalar to every position says nothing about which choice helped. DIRECTOR builds a validity-preserving path from a baseline slate to the generated slate: at step i it places yi at position i (swapping if it already appears later, otherwise replacing), keeping every step duplicate-free. The credit for position i is the reward change between adjacent hybrid slates. These deltas telescope to exactly the total reward gain, so only scalar outputs are needed, and all n+1 intermediate slates can be scored in one batch.
Offline (Table 3, slate length n=6, 5 random seeds, K=20 proposals):
| Dataset | Strongest baseline NDCG@6 | DIRECTOR NDCG@6 | relative gain |
| ML-1M | 0.7399 (JDRec) | 0.7672 (CVAE) | +3.69% |
| Amazon-Books | 0.8255 (JDRec) | 0.8486 (DIFF) | +2.80% |
| RecFlow | 0.1910 (PIER) | 0.1979 (CVAE) | +3.61% |
Online A/B (Kuaishou short video, 7 days; control is the production AR Generator-Evaluator, treatment only swaps the generator for DIRECTOR): valid view (VV) +0.519% (95% CI [0.45%, 0.59%], p<0.05), comment +0.695%, like +0.330%.
Efficiency stress test: under matched peak throughput (about 20k QPS), P99 end-to-end latency at most 30 ms, and 99% availability, compared with an NTP-based AR generator using beam search, CPU consumption is down 66.7%. In the ablations OT contributes the most (removing it drops NDCG@6 from 0.1979 to 0.1675, about 15% relative), while reward guidance and position-specific credit each add their share.
Reranking is a real, latency-sensitive stage, and AR generators are simply slow under beam search. DIRECTOR shows that parallelism does not have to be bought with the duplicate problem: let OT teach conflict-awareness at training time and let hard matching enforce validity at inference, and you get both. The validity-preserving credit-assignment path (telescoping sum) works for any opaque list-wise evaluator, not just recommender ones. Saving two-thirds of the machines at matched throughput and latency on Kuaishou's main app is a concrete operational win.
The 66.7% figure needs context. It is CPU and machine consumption, measured under matched throughput, latency, and availability: latency and QPS are held equal by design, not improved, and the real win is needing about a third of the machines to hit the same SLA. The runtime speedup comes from parallel hard matching, not from optimal transport as community summaries put it; OT is training-time only and is deliberately bypassed at inference. The baseline is Kuaishou's own undisclosed NTP-plus-beam-search generator, not all AR methods, and its architecture and beam config are not disclosed, so the magnitude cannot be calibrated independently.
A few more points. The paper has no dedicated Limitations or Future Work section (unusual). The online test is validated only at one company. Slates are short (n=6) and candidate pools small (M=50/120), and the whole complexity argument relies on n being far smaller than d. The business lift is modest (VV +0.519%, offline +2.8% to 3.7%). Online efficiency is averaged across two DIRECTOR variants and effectiveness is aggregated, so neither can be attributed cleanly to one variant. DIRECTOR only improves the generator; if the opaque evaluator is weak, output quality is still capped.