{"id":"5e7d8053-fd6d-4ca8-93df-91c4d758ce3c","arxiv_id":"2608.01502","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A softmax-sampled, budgeted replacement for the classical sequential search step keeps per-step cost independent of dimensionality and, with online-learned feature statistics, matches or beats ranking baselines up to 10^4 features.","lead":"This paper introduces a budgeted stochastic sampler that replaces the full candidate sweep in sequential feature selection, so the cost of each search step no longer depends on the number of features. On three benchmarks up to 10,105 dimensions it claims to retain most of the quality of exhaustive floating search while running in minutes, making interaction-aware selection practical in very high dimensions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (3)'s online contrast is a self-referential, low-sample estimator at D≥10^4; if it loses informativeness the sampler degrades toward the uniform collapse the paper warns about, and the claimed retention/dominance has no support in that regime.","rationale":"The reader identified the same load-bearing premise; my pass sharpens it. The paper's central empirical claim—retention and dominance—would fail if Eq. (3) misleads the sampler, because the only alternative (uniform) collapses on synergistic data (Fig. 3). The manuscript gives empirical evidence on madelon, but that is D=500 with abundant per-feature observations; reuters is 5 seeds and no failure-mode analysis. The frozen-statistic ablation is informative but not dispositive: it isolates online adaptation at one probe size, not the full retention curve. The proposed synthetic experiment would directly test whether the online contrast carries the load. I do not see a reason to change the reader's CONDITIONAL verdict; the concern is about how strong the evidence is, not an internal contradiction. Credit: the paper is honest about the gisette holdout inversion, includes ablations for each design ingredient, and provides a reproducible standalone implementation; those are real strengths.","tokens_in":889,"tokens_out":2500,"duration_ms":185355,"concrete_test":"Generate a synthetic D=10,000 synergistic benchmark with known ground truth (e.g., 30 informative features arranged in 10 triplets, rest pure noise, n=500), run default sSFFS for 20 seeds, and compare against two equal-budget controls: (i) statistics frozen after warm-up, and (ii) scores s(f) randomly permuted across features after warm-up (preserving the score distribution while destroying the assignment). If control (i) or (ii) matches sSFFS on criterion and holdout across the full size range, the online contrast is not load-bearing and the abstract's 'online adaptation carries the quality' is unsupported; if the real sSFFS dominates and its early s(f)-to-true-marginal-benefit rank correlation is significantly positive, the concern is resolved. Report worst-seed retention curves to test the literal 'at least 97% at every subset size' wording as well.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing premise is that s(f) in Eq. (3), accumulated from z-standardized evaluations of subsets proposed by a softmax that is itself a function of s(f), is a trustworthy utility signal at very high D. This is a self-referential estimator: proposals are drawn from exp(s/tau), so the distribution of subsets fed back into the accumulator is biased toward features that already have high s(f). The positive-feedback risk is concrete: with default y=100 and rho_u=0.2, only 20 floor proposals per forward step re-explore the least-evaluated features; a feature that is spuriously high after warm-up can be proposed and reinforced repeatedly, and at D=10^4 the per-feature average proposal count over a 0.81M run is ~80, concentrated far from uniformly. The paper's own ablation (Section 6) shows the online update adds only +0.015 over the frozen warm-start ranking at y=100 on madelon (paired t=3.1), and the limitation section concedes there is no formal guarantee; the uniform-sampling collapse (Section 5) is exactly the failure mode that would appear if this statistic becomes uninformative. No evidence is given that the statistic remains informative in the D>>500 regime where the headline claims live.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Stochastic Sequential Search (SSS), a family of budgeted sequential feature-selection methods obtained by replacing the exhaustive per-step sweep of classical ADD/RMV operators with a fixed-size sampled step. The sampled candidates are drawn from a softmax proposal distribution driven by an online dependency-aware per-feature contrast statistic, with a uniform exploration floor; the resulting sSFFS variant is studied empirically. On madelon the method is compared with full floating search as retention evidence; on gisette and reuters it is compared with ranking baselines (BIF, DAF) at matched evaluation budgets. The central claims are that per-step cost becomes independent of dimensionality, that sSFFS retains at least 97% of full-SFFS criterion value at about a quarter of the evaluations on madelon, and that on reuters it dominates BIF and DAF on both the search objective and holdout accuracy at every subset size. The paper also reports an honest analysis of the gisette criterion-generalization gap and provides a verified standalone implementation.","tokens_in":20858,"tokens_out":6433,"duration_ms":65903,"significance":"If the empirical claims hold, the paper makes a meaningful contribution: it extends set-level, interaction-aware floating search to regimes (D > 10^4) previously accessible only to ranking methods, while preserving anytime and d-optimizing behavior. The strengths of the work are its careful matched-budget comparisons, the explicit ablations separating uniform, top-k, frozen, and online-informed sampling, the honest reporting of the gisette holdout inversion, and the reproducible seed-pinned implementation with a standalone verification harness. The paper does not provide formal guarantees, and its headline retention number is sensitive to how the seed/split axis is read, but the central empirical edifice is credible and the presentation is largely transparent.","major_comments":[{"comment":"The abstract states that sSFFS 'retains at least 97% of the full-SFFS criterion value at every subset size up to 165 at about a quarter of its evaluations.' In the body this is strictly true only on the shared-split seed (with the default y=100/y_b=50 configuration, 97.1% at every size). The ten-seed campaign is weaker: 'between 145 and 165 of the 165 sizes lie above the 97% mark per seed, and no single size falls below 93.5% anywhere in the campaign.' The unqualified abstract wording is thus an overstatement if read as a claim over seeds/splits. Please qualify the claim by stating that the 97%-at-every-size statement refers to the shared-split seed and give the across-seed range in the abstract or conclusion.","section":"Abstract; Section 5, madelon retention paragraph"},{"comment":"The central mechanism is the online contrast s(f) of Eq. (3), and the paper's strongest regime is D=10,105 (Table 3). The ablation evidence for the online update being load-bearing is confined to madelon: Section 6 reports that online updating adds only +0.015 over the frozen warm-start ranking at y=100 (paired t=3.1). No frozen-statistics or warm-start-only ablation is reported for gisette or reuters. Since the proposal distribution is a function of s(f) and the evaluations fed back to s(f) come from proposals biased by s(f), it is important to show that the statistic remains informative when per-feature observation counts are low and the floor is small in absolute terms. I ask for at least one high-dimensional ablation (e.g., frozen vs. online statistics at the reuters setting) or diagnostics such as per-feature proposal counts and score stability; alternatively, the paper should expli","section":"Section 3.1; Section 6; Table 3"}],"minor_comments":[{"comment":"The exploration floor is defined as drawing u candidates 'uniformly without replacement from the 4u least-evaluated features of F.' The factor 4 is unexplained and appears inconsistent with the subsequent statement that the floor 'cycles through the least-observed features.' If the intended pool is the u least-evaluated features, please correct; otherwise justify the 4u factor.","section":"Section 3.2, stage 1"},{"comment":"The notation z(f∈X) in the update equation is not defined. Please specify explicitly that it means z when f is in the evaluated subset and 0 when f is absent (or whichever convention is intended).","section":"Section 3.1, Eq. (3)"},{"comment":"The phrase 'per-seed mean retention spans 99.0–101.2%' is ambiguous: it should state whether this is the mean over subset sizes within each seed, the mean over seeds at each size, or another aggregation. The surrounding text gradually clarifies, but a precise definition would help.","section":"Section 5, madelon retention paragraph"},{"comment":"The conclusion repeats the unqualified 'at least 97% of full floating-search quality at a quarter of its evaluations.' This should be aligned with the qualified statement recommended above so that the abstract, body, and conclusion are consistent.","section":"Conclusion"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know this about arXiv:2608.01502: the central engineering claim is real. Replacing the exhaustive per-step sweep with a fixed-size, online-informed stochastic sample genuinely makes per-step cost independent of dimensionality, and the experimental campaign backs it up with matched budgets, ablations, and honest reporting. The madelon retention evidence is strong (seed-1 same-split retention ≥98.2%, and the anytime frontier holds up across seeds), and the gisette and reuters results, if correct, are a real advance: set-level, interaction-aware selection at D>10^4 with about two minutes of single-core work on reuters.\n\nWhat's actually new: the combination of a budgeted sADD/sRMV operator pair, online dependency-aware statistics learned from the search's own evaluations, softmax with a uniform exploration floor, and the application to floating search. The paper correctly distinguishes from LFS (static truncation), stochastic greedy (uniform sampling), and FUSE (UCT, no exclusion). The ablation matrix isolates each ingredient against a prior-art principle, which is exactly how it should be done.\n\nThe soft spots are mostly presentation, not load-bearing. The abstract's \"at least 97% at every subset size\" is only strictly true on the shared-split seed; across ten seeds some sizes drop to 93.5%. That needs a qualifier. Tables 2 and 3 report means without error bars, which is a real gap given the stochastic nature of the method. And the reproducibility claim rests on a standalone implementation and config files that cannot be inspected from the preprint; I'd want the code actually available before trusting the numbers.\n\nThe deeper concern you'd want a referee to probe: the online statistic s(f) in Eq. (3) is a self-referential, low-sample estimator at D≥10^4. The paper's own ablation shows the online update adds only +0.015 over the frozen warm-start ranking at y=100 on madelon. That's significant but modest, and it suggests the warm-start DAF-style ranking is doing most of the heavy lifting, not the continual adaptation the paper emphasizes. The stress-test fear—that the feedback loop could concentrate on spuriously high-scoring features and degrade toward the uniform collapse—is not contradicted by any formal argument. But the empirical results on reuters (where the method dominates both rankings on both axes) are hard to explain if the statistic were thoroughly uninformative, and the limitation section openly concedes the lack of a guarantee. So I read the stress-test as a real limitation to probe, not a demonstrated flaw.\n\nVerdict: this deserves a serious referee. The method is clearly specified, the experiments are carefully designed, and the claims are meaningful. I'd send it out with a request to fix the abstract, add error bars, and make the code verifiable. It's a solid within-field contribution.","headline":"A well-executed, honest paper with a real structural advance; the abstract overstates retention and the online-statistic's contribution is smaller than advertised, but it deserves peer review.","tokens_in":21335,"tokens_out":3340,"would_cite":true,"duration_ms":31418,"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":"A fixed-size stochastic sample can replace the exhaustive sweep of sequential feature selection, keeping at least 97% of full floating-search quality at a quarter of its evaluations and extending set-level selection past 10,000 features.","keywords":["feature selection","stochastic sequential search","floating search","sSFFS","softmax sampling","online dependency-aware statistics","very high dimensionality","wrapper criteria"],"falsifier":"Run sSFFS on a synthetic dataset at $D \\approx 10^4$ with a known optimal subset and count how often the anytime frontier recovers the true informative features as the per-step budget $y$ shrinks toward 10. The mechanism predicts graceful degradation; if recovery drops to near chance while criterion values stay high — different spurious subsets on every seed — the contrast statistic is not informing the sampler at extreme $D$. A cheaper probe: on gisette at matched budget, correlate mid-search $s(f)$ with marginal contributions measured by a DAF probe campaign; near-zero correlation would mean","tokens_in":20398,"feed_emoji":"🎯","tokens_out":19986,"duration_ms":147741,"temperature":0.7,"pith_summary":"Classical sequential feature selection — forward selection with floating backtracking — remains the quality reference for choosing feature subsets, but every step evaluates every remaining candidate feature, which prices the whole family out of problems with thousands to tens of thousands of features. This paper claims that the per-step full sweep is not what carries the search's quality: it can be replaced by a fixed-size stochastic sample whose candidates are drawn by a temperature-controlled softmax over dependency-aware per-feature statistics learned online, at no extra evaluation cost, from every criterion value the search itself produces, with a uniform exploration floor keeping every feature reachable. Substituting this operator pair into floating search yields sSFFS, which on the 500-dimensional madelon benchmark retains at least 97% of the full method's criterion value at every subset size at about a quarter of its evaluations — while uniform sampling at the same budget collapses on madelon's synergistic features. At 5,000 and 10,105 dimensions, far beyond the full method's reach, sSFFS beats dependency-aware and individual-feature ranking at matched budgets on the search objective and, on reuters, on holdout accuracy at every subset size, in about two minutes of single-core evaluation work. If correct, this makes set-level, interaction-aware feature selection routine in a regime previously reserved for interaction-blind rankers.","feed_headline":"Feature search keeps 97% quality at a quarter of the evaluations","feed_subtitle":"Sampling replaces the exhaustive sweep, opening interaction-aware selection at 10,000+ features.","key_machinery":"The engine is the online dependency-aware contrast $s(f)=\\mu_f-\\bar\\mu_f$: the difference between exponentially forgetting running means of batch-standardized criterion values of evaluated subsets containing $f$ and those lacking it, z-standardized within each step so the contrast aggregates across subset sizes. The operator sADD/sRMV draws $\\lfloor\\rho_u y\\rfloor$ candidates uniformly from the least-evaluated features and the rest by softmax over $s(f)$ with temperature $\\tau=\\mathrm{IQR}/1.349$, evaluates exactly $y$, commits the best, then folds the batch into the statistics. Substituting sADD/sRMV for ADD/RMV defines the Stochastic Sequential Search family; the fixed budget $y$ makes per","core_discovery":"Sequential search quality, the paper claims, lives in the search's own evaluation history, not in the exhaustive sweep. The budgeted operator pair sADD/sRMV evaluates exactly $y$ candidates per step — some uniform from the least-evaluated features, the rest by softmax over the contrast $s(f)=\\mu_f-\\bar\\mu_f$, the batch-standardized mean criterion value with vs. without $f$, updated online. Substituting these operators makes per-step cost independent of the feature count $D$, yielding stochastic floating search sSFFS. Empirically sSFFS retains at least 97% of full-SFFS criterion value at every subset size on madelon at a quarter of the evaluations, and dominates BIF and DAF at matched budgets","pith_inferences":["The method's success is conditional on the contrast statistic $s(f)$ staying informative when each feature is observed rarely; the paper's ablations support this on madelon but offer no formal guarantee, so an open empirical question is whether the retention rate holds on datasets where the useful subset is large relative to $D$.","The near-total selection instability on gisette (a stability index near 0.036 with near-identical criterion values across runs) implies that standard stability indices cannot distinguish a stochastic optimizer sampling among many equally good subsets from a broken search — a caution that should transfer to any stochastic selector deployed in redundant high-dimensional spaces.","The occasional 'greedy-trap escapes' suggest a testable hybridization: using the budgeted search as a randomized perturbation and the full sweep as a local polish could improve even the exact sequential method at moderate dimensionality.","Because the statistics are learned from the criterion itself, the sampler inherits the criterion's biases; the gisette results imply the method should be paired with trustworthy criteria (as the reuters multinomial filter is) rather than raw cross-validation accuracy at small sample sizes."],"forward_implications":["Set-level, interaction-aware feature selection becomes routinely feasible at $D \\ge 10^4$: a full sSFFS frontier run on reuters (10,105 features) costs roughly two minutes of single-core evaluation work, where previously only interaction-blind ranking could operate.","The anytime and d-optimizing properties of floating search are preserved: one run reports the best subset found at every cardinality, tracing the criterion-vs-size curve and exposing the optimal dimensionality.","Per-step spend becomes predictable and independent of $D$: the non-floating form sSFS reaches size $d$ in exactly $y_f \\cdot d$ evaluations, a hard a priori bound previously available only to ranking methods and probe-based ranking.","The operator substitution is generic: sSFS, sSBS, sSBFS, and sOS all follow from the same replacement rule, though only sSFFS is empirically studied here.","The gisette experiments locate the binding constraint beyond the sequential frontier in the criterion, not the search: at 500 training samples with 5,000 candidate features, more powerful optimization transfers the wrapper criterion's selection bias, making criterion design the practitioner's limiting decision."],"supporting_citations":[{"why":"Defines the floating search (SFFS) schedule that the paper's sSFFS inherits and that serves as the quality reference and retention baseline on madelon.","marker":"[4]"},{"why":"Supplies the dependency-aware ranking contrast (DAF) that the online statistic generalizes, plus the madelon/gisette/reuters test bed and evaluation protocol the experiments reuse.","marker":"[2]"},{"why":"Provides the fixed-size stochastic-greedy sampling idea and its approximation rationale; the paper's uniform-sampling ablation is exactly Stochastic-Greedy transferred to wrapper feature selection.","marker":"[6]"},{"why":"The nearest prior-art point in method space: static pool truncation (LFS) whose documented limitations motivate the online-updated sampling design and the static top-k ablation.","marker":"[7]"},{"why":"Hybridization operators formalize the deterministic top-\\lambda gate; the top-k ablation embodies this principle with the learned statistics as filter.","marker":"[8]"},{"why":"Shows uniform fixed-size sampling fails with high probability unless the sample grows; the paper's adaptive concentration of a fixed budget is the direct response to that failure mode.","marker":"[25]"},{"why":"FUSE introduced online per-feature statistics guiding candidate choice inside a search; the paper's batch-standardized contrast is the same epistemic move placed in a floating-search container.","marker":"[26]"}],"fun_headline_variants":["97% quality at 25% evaluations in feature search","Stochastic sequential search cuts evaluations 75%","No full sweeps: feature selection at 10k features","Sampling replaces exhaustive sweep, preserves 97% quality","sSFFS: interaction-aware selection without exhaustive search"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The method stands or falls on whether the online contrast $s(f)=\\mu_f-\\bar\\mu_f$, accumulated from the search's own evaluations, reliably estimates a feature's usefulness in combination; the paper itself says the retention results are empirical and the uniform-case guarantee does not transfer. If the statistic becomes noise at very high dimensionality, the sampler could concentrate on spuriously good features and collapse the way uniform sampling does on madelon.","fun_headline_variants_meta":{"raw":{"variants":["97% quality at 25% evaluations in feature search","Stochastic sequential search cuts evaluations 75%","No full sweeps: feature selection at 10k features","Sampling replaces exhaustive sweep, preserves 97% quality","sSFFS: interaction-aware selection without exhaustive search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000492,"raw_usage":{"total_tokens":2315,"prompt_tokens":863,"completion_tokens":1452,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":1382}},"tokens_in":607,"tokens_out":1452,"duration_ms":10926,"temperature":1.0,"reasoning_tokens":1382,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:04:25.019104+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run sSFFS on a synthetic dataset at $D \\approx 10^4$ with a known optimal subset and count how often the anytime frontier recovers the true informative features as the per-step budget $y$ shrinks toward 10. The mechanism predicts graceful degradation; if recovery drops to near chance while criterion values stay high — different spurious subsets on every seed — the contrast statistic is not informing the sampler at extreme $D$. A cheaper probe: on gisette at matched budget, correlate mid-search $s(f)$ with marginal contributions measured by a DAF probe campaign; near-zero correlation would mean","supporting_citations":[{"cited_title":"Pudil, J","cited_arxiv_id":null,"evidence_quote":"Defines the floating search (SFFS) schedule that the paper's sSFFS inherits and that serves as the quality reference and retention baseline on madelon."},{"cited_title":"Fast dependency-aware feature selection in very- high-dimensional pattern recognition","cited_arxiv_id":null,"evidence_quote":"Supplies the dependency-aware ranking contrast (DAF) that the online statistic generalizes, plus the madelon/gisette/reuters test bed and evaluation protocol the experiments reuse."},{"cited_title":"Large Scale Attribute Selection Using Wrappers,","cited_arxiv_id":null,"evidence_quote":"The nearest prior-art point in method space: static pool truncation (LFS) whose documented limitations motivate the online-updated sampling design and the static top-k ablation."},{"cited_title":"Somol, J","cited_arxiv_id":null,"evidence_quote":"Hybridization operators formalize the deterministic top-\\lambda gate; the top-k ablation embodies this principle with the learned statistics as filter."},{"cited_title":"Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling","cited_arxiv_id":"1907.09064","evidence_quote":"Shows uniform fixed-size sampling fails with high probability unless the sample grows; the paper's adaptive concentration of a fixed budget is the direct response to that failure mode."},{"cited_title":"Feature selection as a one-player game","cited_arxiv_id":null,"evidence_quote":"FUSE introduced online per-feature statistics guiding candidate choice inside a search; the paper's batch-standardized contrast is the same epistemic move placed in a floating-search container."}],"review_version":1}