{"id":"78c53d4f-1d32-4e6c-b67c-8d93ee299e5b","arxiv_id":"2607.08979","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"A primal-dual Track-and-Stop algorithm matches the information-theoretic lower bound for fixed-confidence top-k identification from pairwise comparisons as δ→0.","lead":"The paper gives the first asymptotically optimal algorithm for fixed-confidence top-k identification from noisy pairwise comparisons under latent-utility models. It matters because many ranking and selection tasks (LLM arenas, recommender shortlists, tournaments) rely on costly comparisons and need tight sample complexity.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the strongest claim (exact asymptotic optimality) and the most delicate modeling hypothesis (compact Θ). That hypothesis is load-bearing for the concentration and threshold arguments, yet it is standard, openly discussed, and does not create an internal contradiction. The technical development follows the established Track-and-Stop / gamification template and the proofs appear complete; the only practical caveat (loose finite-δ threshold) is already acknowledged by the authors and does not affect the lim δ→0 statement. Consequently no adjustment to the ACCEPT verdict is warranted.","tokens_in":37077,"tokens_out":492,"duration_ms":6107,"concrete_test":"Independently re-derive the duality-gap bound of Lemma C.3 and the transfer from averaged FTRL iterates to the empirical allocation ŵemp_t (the last three displays of the Prop. 6.3 proof) without invoking the burn-in truncation bt=⌈t^{1/4}⌉; if the same o(1) rates are recovered, the high-probability oracle-rate lower bound is robust and the asymptotic claim is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 6.5) is that lim δ→0 Eθ[τδ]/log(1/δ)=1/Γ*(θ). The supporting chain—boundary reduction of Alt(θ) to the k(n-k) half-spaces Θij (Sec. 4.1), existence of a saddle point of F by Sion (Sec. 4.2), well-posed KL projections under connected support (Lemma 4.2), high-probability oracle-rate tracking via entropic FTRL + C-tracking (Prop. 6.3), GLR stopping with mixture-martingale threshold (Prop. 6.4), and the final limsup argument (Thm. 6.5 / App. E)—is internally consistent under the stated assumptions. Boundedness of Θ (the reader’s weakest assumption) is conventional for linear-bandit concentration and is used only to guarantee a>0, finite Dmax/L, and logarithmic growth of β(t,δ); Appendix G.2 already notes that the same conclusions hold for any practically relevant R. No hidden gap that would break the asymptotic equality appears.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies fixed-confidence top-k identification from noisy pairwise comparisons under a latent-utility exponential-family model. It derives the instance-dependent lower bound Γ*(θ) via a boundary-pair reduction of Alt(θ), reformulates the oracle allocation as a saddle-point game F(w,q;θ), and gives an adaptive algorithm that tracks this equilibrium online by entropic FTRL with stochastic gradients, C-tracking sampling, and a GLR stopping rule. The main results are δ-correctness (Proposition 6.4) and asymptotic optimality (Theorem 6.5): lim_{δ→0} E_θ[τ_δ]/log(1/δ) = 1/Γ*(θ), matching the information-theoretic lower bound of Theorem 3.4 including constants. Simulations compare the method to SEEKS and Active Ranking on synthetic instances.","tokens_in":37333,"tokens_out":935,"duration_ms":22858,"significance":"This appears to be the first algorithm that is asymptotically optimal (exact constant match as δ→0) for top-k identification from pairwise comparisons under latent-utility models, filling a gap relative to Track-and-Stop-style results for multi-armed and linear bandits and to existing pairwise top-k procedures that are optimal only up to log factors or under different models. The boundary reduction to k(n-k) half-spaces and the resulting primal–dual game are clean and make online learning of the allocation computationally tractable via single-boundary-pair stochastic gradients. Full appendix proofs of δ-correctness and asymptotic optimality, built from standard martingale, FTRL-regret, and C-tracking arguments, are a clear strength. The contribution is solid for the pure-exploration literature even if practical moderate-δ performance remains limited by the stopping threshold.","major_comments":[],"minor_comments":[{"comment":"Section 7 and Figure 1: the equally-spaced and SST instances show that the GLR threshold (4) can make Algorithm 1 worse than SEEKS at δ=0.01 when ∥θ̂_t∥₂ grows with n. Figure 2 partially addresses this for smaller δ, but a short quantitative discussion of when β(t,δ) becomes tight (e.g., relative size of log(1/δ) vs. (λ/2)∥θ̂∥₂²) would help readers set expectations.","section":null},{"comment":"Section 5.5: the O(k(n-k)n²) cost of the full stopping check is noted; stating the sparse-check schedule used in the experiments (or that none was used) would improve reproducibility.","section":null},{"comment":"Appendix G.3 and the choice of α=0.2, γ=1/3: the sensitivity plots (Figures 3–4) are useful; a one-sentence default recommendation in the main text (e.g., α∈[0.15,0.3], γ=1/3) would make the algorithm easier to reimplement.","section":null},{"comment":"Assumption 3 and Θ_gap: the positive-gap condition is standard, but a brief remark that the algorithm’s finite-time behavior near vanishing gaps is not characterized (only the asymptotic rate for fixed θ∈Θ_gap) would clarify the scope.","section":null},{"comment":"Related work (Section 2.2): Wang et al. (2021) are correctly distinguished as nonparametric/combinatorial; a single sentence on whether their Frank–Wolfe oracle could be specialized to the latent-utility boundary structure would further situate the contribution.","section":null},{"comment":"Notation table and Algorithm 1: ˆB_t vs B(θ) and Θ_ij(t) are clear in the appendix but slightly dense in Section 5; a short inline reminder that after t_stab the estimated boundary equals the true one (Corollary 6.2) would help the main-text reader.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is already framed as an ICML 2026 proceedings paper. For a journal version the theory is ready as-is; the main practical limitation (loose moderate-δ threshold) is honestly acknowledged by the authors and does not undermine the asymptotic claim. No novelty or citation concerns stood out."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper closes a genuine gap: asymptotic optimality (matching constants) for fixed-confidence top-k under latent-utility pairwise models. Track-and-Stop and game-theoretic pure exploration already exist, but the reduction of Alt(θ) to the k(n-k) boundary half-spaces, the resulting saddle-point game F, and the primal-dual FTRL learner that tracks it online are new for this setting and make the oracle allocation tractable.\n\nWhat works: Section 4 is clean. Sion applies, KL projections are unique once the support graph is connected (they force full support via entropic FTRL), and the stochastic-gradient estimates stay unbiased. The high-probability oracle-rate bound (Prop. 6.3) carefully separates FTRL regret, estimation, mixing, and burn-in; the δ-correctness and lim E[τδ]/log(1/δ)=1/Γ*(θ) arguments then follow the usual martingale + C-tracking template. Appendix proofs look complete. Simulations are honest: they beat SEEKS/Active Ranking on random utilities, track the oracle on equally-spaced instances, and stay competitive under SST misspecification. The authors themselves flag the loose moderate-δ threshold driven by ∥θ̂∥².\n\nSoft spots are real but proportionate. Boundedness of Θ is used for a>0, finite Dmax/L, and log growth of β(t,δ); Appendix G.2 already notes any practical R works. Hyperparameters α,γ need tuning (they recommend α≈0.2, γ=1/3). Per-round cost of the projections is O(n^{2}) even with one-sample gradients, so large n still hurts. None of this breaks the asymptotic claim.\n\nThis is for people who already care about pure-exploration sample complexity or run pairwise preference platforms. The math and citation pattern are solid; no circularity. I would send it to referees and would cite the boundary reduction and the algorithm when I next need an asymptotically optimal top-k comparator.","headline":"Solid asymptotic-optimality result for top-k from pairwise comparisons; the boundary-pair saddle point is the real contribution, and the proofs hold under standard assumptions.","tokens_in":37950,"tokens_out":575,"would_cite":true,"duration_ms":8715,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"An online algorithm matches the information lower bound for fixed-confidence top-k identification from pairwise comparisons under latent utilities.","keywords":["top-k identification","pairwise comparisons","fixed-confidence pure exploration","asymptotic optimality","Track-and-Stop","primal-dual online learning","latent utility models","Bradley-Terry"],"falsifier":"On any fixed positive-gap instance, plot E[τ_δ]/log(1/δ) against log(1/δ) for successively smaller δ; the curve must approach the constant 1/Γ*(θ) computed from the true θ, not merely stay within a log-factor of existing elimination bounds.","tokens_in":37954,"feed_emoji":"⚖️","tokens_out":743,"duration_ms":6757,"temperature":0.7,"pith_summary":"The paper studies how to find the top-k items among n candidates by adaptively choosing noisy pairwise comparisons and stopping only when the returned set is correct with probability at least 1-δ. The design goal is to make the expected number of comparisons as small as possible. Information theory supplies a lower bound on that expectation that is governed by an oracle allocation of comparisons; until now no algorithm was known to match that bound for top-k under a latent-utility model. The authors rewrite the oracle problem as a two-player game whose equilibrium gives both the optimal sampling proportions and the minimal sample complexity. They then build a primal-dual online learner that tracks that equilibrium from data and prove that the resulting adaptive procedure is asymptotically optimal: its expected stopping time, divided by log(1/δ), tends exactly to the reciprocal of the information rate as δ goes to zero. A sympathetic reader cares because the same reduction and tracking scheme apply to both binary and cardinal comparisons and yield a practical algorithm that is competitive with existing elimination methods on moderate-sized instances.","feed_headline":"Top-k from pairwise tests now hits the information limit","feed_subtitle":"A primal-dual tracker matches the lower bound as error probability vanishes","key_machinery":"The boundary reduction of the alternative set: every alternative parameter must invert at least one of the k(n-k) boundary pairs that straddle the true top-k cut. This turns the max-min oracle program into a saddle-point game F(w,q;θ) whose primal-dual gradients can be estimated by sampling a single boundary pair, enabling efficient entropic FTRL updates that track the optimal design.","core_discovery":"For top-k identification under a latent-utility pairwise model, the information-theoretic lower bound is attained by a computationally tractable primal-dual procedure that learns the optimal comparison allocation online; the resulting Track-and-Stop algorithm is δ-correct and satisfies lim δ\to0 E[τ_δ]/log(1/δ) = 1/Γ*(θ).","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Primal-dual tracker attains lower bound for top-k pairwise ID","Track-and-Stop matches info limit for latent-utility top-k","Asymptotically optimal top-k ID from noisy pairwise comparisons","Online allocation learning solves top-k pairwise pure exploration","Saddle-point primal-dual yields optimal top-k comparison allocation"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"Utilities are confined to a known bounded range so that the exponential-family link has uniform curvature and sub-Gaussian tails on that compact set.","fun_headline_variants_meta":{"raw":{"variants":["Primal-dual tracker attains lower bound for top-k pairwise ID","Track-and-Stop matches info limit for latent-utility top-k","Asymptotically optimal top-k ID from noisy pairwise comparisons","Online allocation learning solves top-k pairwise pure exploration","Saddle-point primal-dual yields optimal top-k comparison allocation"]},"model":"grok-4.5","effort":"low","cost_usd":0.005634,"raw_usage":{"total_tokens":1521,"prompt_tokens":777,"num_sources_used":0,"completion_tokens":94,"cost_in_usd_ticks":56340000,"prompt_tokens_details":{"text_tokens":777,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":650,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":777,"tokens_out":94,"duration_ms":6799,"temperature":1.0,"reasoning_tokens":650,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T01:15:46.336221+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On any fixed positive-gap instance, plot E[τ_δ]/log(1/δ) against log(1/δ) for successively smaller δ; the curve must approach the constant 1/Γ*(θ) computed from the true θ, not merely stay within a log-factor of existing elimination bounds.","supporting_citations":[],"review_version":1}