{"id":"0236127b-deed-4f07-8113-0fc6d99562ae","arxiv_id":"2607.27692","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"ReTopK, a training-free method, reuses historical Top-K index selections from similar queries to cut index-discovery cost in long-context attention, achieving 3.07x speedup at 128K with only 0.50% perplexity increase.","lead":"ReTopK speeds up long-context Transformer attention by reusing the token-selection decisions of similar past queries and only re-scoring a small candidate set, instead of scanning the whole context for every new token. The paper reports a roughly 3x attention speedup at 128K context with near-identical perplexity to exact Top-K attention.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Speedup claim may be inflated by fusion-level asymmetry: Exact Top-K baseline fusion level is unreported, and ReTopK gains 2.57x from kernel fusion alone (Table 4); remeasure with a matched fused baseline.","rationale":"I examined the central claim of 3.07x attention speedup with 0.50% PPL increase. The quality side appears plausible: support recall (~57-79%) with high retained mass (91-99%) is consistent with the reranking mechanism, and the long-horizon study shows bounded error. The speedup side, however, has a concrete methodological vulnerability. The paper provides no fusion-level characterization of the Exact Top-K baseline. Table 4's own ablation shows that ReTopK's speedup is 2.57x from L1 to L5, so the baseline choice could dominate the reported speedup. The reader's weakest_assumption focused on query-similarity reliability, but the paper provides empirical evidence (Figures 2, 3, 6) and a fallback threshold, so I judge that assumption adequately supported. The fusion-level asymmetry is more load-bearing because it directly undermines the headline number. My proposed test—comparing against a matched fused Exact Top-K—would settle this. I agree with the reader's CONDITIONAL verdict; my concern reinforces condition (1) rather than changing the verdict.","tokens_in":13379,"tokens_out":10220,"duration_ms":98481,"concrete_test":"Reimplement Exact Top-K using the same fused kernel pipeline as ReTopK's L5 (indexed QK scoring fused with Top-K selection, sparse Softmax-value aggregation, and cache update/sorting in a single kernel), keeping the exact Top-K logic identical. Run the same PG19 latency benchmark at 128K, K=512, BF16 on an NVIDIA L20. If the speedup of ReTopK over this matched-fusion Exact Top-K drops below, say, 1.5x, then the 3.07x headline is largely attributable to fusion-level mismatch rather than the recall-before-rerank algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central speedup claim (3.07x at 128K, K=512) rests on comparing ReTopK's fully fused kernel implementation against an Exact Top-K baseline whose kernel-fusion level is never specified. The paper states 'matched kernels' (Experiments, Implementation settings) but does not report whether the Exact Top-K baseline is at a comparable fusion stage. Table 4 shows ReTopK's own speedup over its separate-kernel baseline rises from 1.0x (L1) to 2.57x (L5) at 64K, meaning fusion alone contributes up to 2.57x. If the Exact Top-K implementation is at L1-like quality (e.g., separate QK, top-k, and softmax-v kernels), a large portion of the 2.03x/3.07x speedup is an engineering artifact rather than the algorithmic benefit of retrieval-decision reuse. This is not a quibble: the abstract's headline is about acceleration, and the end-to-end speedup at 128K is only 1.13x (Table 5), so the attention-only metric carries the claim. A matched-fusion baseline could shrink the reported speedup substantially.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ReTopK, a training-free approximate dynamic Top-K attention method for long-context decoding. ReTopK maintains a bounded per-head FIFO cache of normalized query embeddings together with the support indices selected for those queries. At each decoding step it retrieves the R most similar cached queries by cosine similarity, unions their stored supports with a recent W-token window, scores only the resulting compact candidate set (size M_t <= RK+W), reranks to K, and performs sparse softmax-value aggregation over the reranked support. A similarity-based fallback (threshold tau) and a periodic exact refresh (interval Tr) invoke full-history Exact Top-K when reuse is deemed unreliable. The paper reports quality and efficiency results on PG19, RULER NIAH, and LongBench across Qwen2.5-7B, Llama-3.1-8B, and Qwen2.5-14B, claiming attention speedups up to 3.07x at 128K context with only a 0.50% perplexity increase over Exact Top-K. It also provides a fused GPU implementation, kernel-level ablation, sensitivity analysis, long-horizon stability experiments, and end-to-end decoding measurements.","tokens_in":13740,"tokens_out":7018,"duration_ms":70194,"significance":"If the speedup claim holds under matched implementations, ReTopK is a useful contribution: it targets the index-discovery bottleneck of sparse attention without evicting KV entries and without any training. The recall-before-rerank design is simple and well motivated by the query-similarity/support-overlap evidence in Figures 2--3. The empirical study is thorough: three model families, three benchmarks, component ablation, hyperparameter sensitivity, long-horizon stability, a five-stage kernel fusion analysis, and end-to-end scaling to very long contexts. The complexity analysis for the reuse path is correct and the paper is transparent about the fact that fallback and refresh steps perform full-history Exact Top-K. The main caveat is that the headline 3.07x attention speedup is measured against an Exact Top-K baseline whose kernel-fusion level is not reported; Table 4 shows that ReTopK's own fusion improvements alone account for up to 2.57x, so the claimed algorithmic speedup is not cleanly separated from implementation engineering.","major_comments":[{"comment":"The paper states that attention latency is measured with 'matched kernels', but the Exact Top-K baseline's kernel-fusion level is never specified. Figure 9 decomposes Exact Top-K into separate components (Full-context QK, Exact Top-K select, Sparse Softmax-SV, Split-attention merge), suggesting an unfused or partially fused baseline. Table 4 shows ReTopK's own L1-to-L5 fusion improvements are 2.57x at 64K and 2.29x at 128K. Since the claimed 3.07x speedup at 128K is attention-only (end-to-end speedup in Table 5 is only 1.13x), the baseline comparison is load-bearing. Please report the exact kernel structure of the Exact Top-K baseline and remeasure against a fused Exact Top-K baseline (e.g., fused full-context QK + top-K selection + sparse softmax-V).","section":"Implementation settings; Table 4; Figure 9"},{"comment":"The complexity statement that a reuse step 'replaces both full-history QK scoring and global selection over L_t entries with bounded cache lookup and candidate processing' is correct only for the reuse path. On fallback and refresh steps the method executes full-history Exact Top-K with O(L_t d) work. The paper's broader phrasing that the selector work 'does not grow with context length' is therefore not a worst-case statement; the measured speedup depends on the fallback/refresh mixture, which is why ReTopK's latency still grows with context in Figure 9. Please state the amortized/expected complexity with respect to the exact-path rate and give the worst-case bound explicitly.","section":"Methodology, Eq. (14); Figure 9"},{"comment":"The default hyperparameters C=W=32, R=4, tau=0.85, Tr=128 are selected by one-at-a-time sensitivity analysis on PG19 at 64K, and the same configuration is then used for the headline 128K 0.50% PPL increase and for the NIAH/LongBench results. Because the selection and evaluation are on overlapping data, the reported operating point may be optimistically selected. The cross-model results in Table 2 mitigate this concern, but the paper should describe the selection protocol precisely (e.g., whether NIAH/LongBench were touched during tuning) and, ideally, report a validation-split or holdout model/context pair to establish out-of-sample behavior.","section":"Experiments; Figure 7; Table 1"},{"comment":"The method's reliability rests on the empirical correlation between query cosine similarity and support overlap, but the paper does not characterize the tail behavior of reuse fidelity. Figure 6 reports average support recall of only 56.9% on reuse-path pairs with 91.6% retained mass; this is encouraging, but the paper does not state the fraction of head--token pairs with low retained mass or low head-output cosine. Since reranking cannot recover indices absent from the candidate set, and the fallback triggers only on raw similarity rather than predicted recall, there may be input segments where reuse silently degrades. Please report quantiles of retained mass/head-output cosine and a calibration-style analysis of similarity versus recall to justify the tau threshold.","section":"Figure 6; fallback design"}],"minor_comments":[{"comment":"The abstract says ReTopK achieves the 'lowest PG19 perplexity and highest NIAH and LongBench scores among the evaluated approximate methods' without specifying the configuration. With the default tau=0.85, NIAH at 16K is 85.3 versus 96.3 for tau=0.90. Please state the configuration used for the headline claim.","section":"Abstract; Table 1"},{"comment":"Cross-model results use K=1024 at 128K while the headline Table 1 uses K=512. The 128K PPL deltas in Table 2 are therefore not directly comparable to the 0.50% figure in the abstract; please label this clearly.","section":"Table 2 versus Table 1"},{"comment":"Figure 5 reports 78.9% support recall and 99.45% retained mass for one representative head, while Figure 6 reports 56.9% average recall and 91.6% mass over all heads. The caption should explicitly note that Figure 5 is a single favorable head.","section":"Figure 5 versus Figure 6"},{"comment":"The first branch of the path rule uses Tr>0 and t_dec in {Tr,2Tr,...}; for Tr=0 the condition is undefined. The notation should be written so that Tr=0 disables scheduled refresh without an undefined expression.","section":"Equation (13)"},{"comment":"The 'Non-attn.' column is the shared decoder latency as a fraction of Exact Top-K latency; please define this in the caption or text, since it explains why the end-to-end speedup grows with context length.","section":"Table 5"},{"comment":"No code or data availability statement appears in the paper. Given the reproducibility-sensitive nature of kernel-level speedup claims, a code release or detailed kernel pseudocode would strengthen the manuscript.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically solid and the quality evidence is convincing, but the headline speedup claim is not yet cleanly separated from kernel-engineering effects. The fusion-level asymmetry in Table 4/Figure 9 is the main blocker. I recommend major revision rather than rejection: the algorithmic idea is sound, and the required matched-baseline remeasurement is within scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is genuinely neat: cache per-head query–support pairs, retrieve the most similar historical queries, union their supports with a recent window, and rerank only that compact candidate set. That specific combination — with similarity fallback and periodic refresh — is not something I've seen in one place, and the paper describes it clearly. The complexity analysis is correct, the evaluation spans three models and three task families, and the quality results are credible: ReTopK sits close to Exact Top-K on PPL while beating the other approximate baselines. The long-horizon stability test is a nice touch, and the support-recall/attention-mass diagnostics show real effort to understand the method.\n\nNow the soft spots, in proportion.\n\nFirst, the speedup claim. Table 4 shows that ReTopK's own gain from kernel fusion is up to 2.57x at 64K and 2.29x at 128K. The paper says all methods use \"matched kernels,\" but it never reports the Exact Top-K baseline's fusion level. If the baseline is at the separate-kernel stage (L1), then a large chunk of the reported 2.03x–3.07x attention speedup is engineering fusion, not algorithmic reuse. This is not a nitpick: at 128K the end-to-end speedup is only 1.13x, so the attention-only metric is what carries the claim. The fix is straightforward — report the Exact Top-K baseline at the same fusion level, or at least disclose its stage.\n\nSecond, the missing baselines. The paper cites Kascade, IndexCache, and PRR as related reuse methods but doesn't evaluate against any of them. Those are the closest competitors, and without that comparison we don't know whether the reuse mechanism is actually better than simpler cross-layer or temporal-reuse schemes. I'd want that added.\n\nThird, no code release. Given the heavy engineering component and the fusion sensitivity, reproducibility matters more than usual here.\n\nOverall, I think the method itself is sound and the quality evidence is solid — the reuse heuristic is plausible and the ablation shows each component matters. The speedup concern is a measurement artifact risk, not a fundamental flaw. A careful revision that re-baselines at matched fusion and adds the direct comparisons could make this a solid paper.\n\nThis deserves a serious referee. I'd accept it with major revision, with the fusion baseline as the first item. I'd also bring it to a reading group — the fusion-asymmetry trap is a useful cautionary tale for anyone measuring sparse-attention speedups.","headline":"Useful recall-based top-K attention with a plausible algorithm, but the headline speedup is likely inflated by asymmetric kernel fusion; needs a matched-fused baseline and the missing reuse baselines.","tokens_in":14211,"tokens_out":2454,"would_cite":true,"duration_ms":27295,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"ReTopK speeds up dynamic Top-K attention by reusing past retrieval choices, delivering 3.07x speedup at 128K with only 0.50% perplexity loss.","keywords":["efficient attention","Top-K sparse attention","long-context inference","KV cache","retrieval reuse","query similarity","training-free method","decoding acceleration"],"falsifier":"Force the reuse path unconditionally (disable fallback and refresh), then measure the overlap between ReTopK's candidate set and the exact Top-K support on a held-out long-context corpus; if highly similar cached queries (cosine similarity above 0.85) recover less than roughly half the exact support on most steps, the central reuse assumption is false and the speedup will not generalize.","tokens_in":13327,"feed_emoji":"⚡","tokens_out":6727,"duration_ms":55467,"temperature":0.7,"pith_summary":"ReTopK targets the index-discovery bottleneck of exact Top-K attention: even when aggregation is restricted to K keys, finding those keys still requires scoring every query against the entire KV cache. The paper's central claim is that similar queries attend to overlapping key supports, so the support selected for a new query can be recalled from a small cache of previous query–support pairs, unioned with a recent-token window, and then reranked with exact current-query scores. This training-free recall-before-rerank procedure keeps the full KV cache, reuses only index selections, and makes the selector's work independent of context length, with similarity fallback and periodic refresh as safeguards. If correct, the main linear-in-context cost of sparse attention—full-history scoring and global Top-K selection—disappears from most decoding steps; the paper reports a 3.07x attention speedup at 128K context with K=512 and only a 0.50% perplexity increase over exact Top-K.","feed_headline":"Reuse old retrieval decisions to speed Top-K attention 3.07x","feed_subtitle":"Similar queries share top keys, so a small cache and rerank replace full-history scoring at 128K.","key_machinery":"The mechanism is a recall-before-rerank selector: a bounded per-head query–support cache (normalized queries plus the Top-K index sets selected at those steps) is searched for the R most similar cached queries; their supports are unioned with a recent window of W positions, and only the resulting M_t ≤ RK+W candidates are scored with the current query and reranked to the final K indices. The cache stores only index selections—never historical scores, weights, or outputs—so the complete KV cache remains intact. A similarity fallback (ρmax < τ invokes full exact Top-K) and periodic refresh (every Tr steps) are the reliability mechanisms that keep reuse from degrading.","core_discovery":"The central discovery is an empirical regularity plus a design that exploits it: for each attention head, the exact Top-K support of a query is largely recoverable from the supports of a few historically cached queries that are most similar to it, plus a small window of recent positions. ReTopK maintains a bounded per-head FIFO cache of normalized queries and their selected index sets; on a reuse step it computes cosine similarity against the cache, takes the R most similar entries, unions their stored Top-K supports with the last W positions, computes exact QK scores only on that candidate set, and reranks to select exactly K indices. Because the recalled indices are only candidates, the fi","pith_inferences":["If the similarity–overlap regularity is robust, ReTopK's cache could be built during chunked prefill rather than only during decoding, extending the same recall-before-rerank idea to the first pass over a long context.","Because reuse quality varies by head, an adaptive per-head choice of cache size, number of retrieved queries, and fallback threshold could push the speed/quality Pareto frontier beyond the fixed defaults reported here.","The candidate set ReTopK produces is a natural, query-informed signal for which KV entries matter; under a hard memory budget, the union of recalled supports could double as an eviction policy, a use the paper does not explore."],"forward_implications":["Index discovery, not aggregation, becomes the cost that matters: at long contexts full-history QK scoring and global Top-K selection account for 87–97% of exact Top-K latency, and ReTopK's reuse path removes both on most steps.","If the reuse regularity holds, sparse attention decoders can stop scanning the KV cache at every step without evicting any keys, so retrieval quality remains query-dependent rather than fixed by a streaming window.","The method transfers across model families and scales without retuning: 82.5–89.6% of head–token steps take the reuse path, with perplexity changes within about 2.8% of exact Top-K and speedups of 1.26–2.66x.","Support recall of roughly 57–79% is enough: because reranking uses exact current scores, unmatched low-weight keys contribute little, so 99%+ of attention mass and about 97% output cosine can be retained.","End-to-end decoding gains widen as the shared non-attention work shrinks, reaching about 3.7x at multi-million-token contexts in the paper's measurements."],"fun_headline_variants":["Reuse top-key picks from similar queries to speed attention 3x","Similar queries share top-K sets, so cache and rerank to speed 3x","Training-free: recycle cached top-K lists to accelerate attention","Cut attention compute 3x by reusing similar query supports","Near-exact Top-K attention at 3x speed via historical reuse"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is empirical: similar query vectors reliably attend to overlapping sets of keys, so a small cache of lookalike queries plus a recent-token window covers most of the exact Top-K support; if query drift weakens that link, fallback fires more often and the promised speedup shrinks.","fun_headline_variants_meta":{"raw":{"variants":["Reuse top-key picks from similar queries to speed attention 3x","Similar queries share top-K sets, so cache and rerank to speed 3x","Training-free: recycle cached top-K lists to accelerate attention","Cut attention compute 3x by reusing similar query supports","Near-exact Top-K attention at 3x speed via historical reuse"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000321,"raw_usage":{"total_tokens":1688,"prompt_tokens":830,"completion_tokens":858,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":764}},"tokens_in":574,"tokens_out":858,"duration_ms":8133,"temperature":1.0,"reasoning_tokens":764,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T03:11:10.823070+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Force the reuse path unconditionally (disable fallback and refresh), then measure the overlap between ReTopK's candidate set and the exact Top-K support on a held-out long-context corpus; if highly similar cached queries (cosine similarity above 0.85) recover less than roughly half the exact support on most steps, the central reuse assumption is false and the speedup will not generalize.","supporting_citations":[],"review_version":1}