{"id":"4e681789-db09-47b8-84aa-b43ff68bc306","arxiv_id":"2501.06788","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"SampLNS combines a mutually-exclusive-interactions lower bound with large neighborhood search to minimize pairwise interaction test samples and certify optimality.","lead":"This paper introduces SampLNS, an algorithm that finds small test samples for highly configurable software systems and can prove how close those samples are to the smallest possible size. It beats existing sampling tools on 40 of 47 benchmark systems and proves optimality on many of them, giving testers a reliable stopping point.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Optimality certificates hinge on the interaction set I extracted from the initial YASA sample being complete; the paper only checks equality with that sample, so a missed valid pair could turn Property 1 into false positives and inflate lower bounds, invalidating UB=LB certificates.","rationale":"The reader's weakest assumption and my main concern coincide: the optimality certificates require the set I used by both the primal and dual computations to be exactly the complete set of valid interactions. I would sharpen the statement: a missing valid interaction does not merely make the certificate silent; because Property 1 classifies pairs outside I as invalid, a missing pair can make compatible interactions look mutually exclusive, inflating the lower bound and producing a false optimality proof. This arguably makes the empirical claim more fragile than the reader's phrasing suggests, though the paper's explicit choice of algorithms with guaranteed full pairwise coverage partially mitigates it. The duality theorem itself is unconditional and correct; the issue is the input I, not the mathematics. I would therefore keep the reader's CONDITIONAL verdict rather than moving to ACCEPT or REJECT: the empirical certificates should be accepted only after an independent completeness check of I, and the abstract's 63% figure must be reconciled with the body's 55%. The discrepancy between the abstract and the body is a separate reporting issue that does not threaten the theoretical contribution but does affect the precision of the headline claim.","tokens_in":29492,"tokens_out":11976,"duration_ms":117605,"concrete_test":"Independently enumerate all valid pairwise interactions for all 47 feature models: for each unordered pair of literals over concrete features, check satisfiability of the feature-model formula conjoined with that pair (using Kissat or CP-SAT; O(n^2) calls per model, feasible at this scale). Compare the resulting I_full with the interaction set I_SampLNS extracted from the YASA(m=1) initial samples. If I_full != I_SampLNS for any model, rerun SampLNS's lower-bound search and sample optimization using I_full and recompute the UB=LB rows in Table 1. If no certificate survives unchanged, the assumed completeness is the decisive gap; if I_full matches on all models, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1 says 'the set of all valid interactions, I, can efficiently be extracted from a given feasible sample.' This is true if the sample is complete, and the paper states that YASA (used as the initial sample in Algorithm 2, Section 4.2) belongs to algorithms that guarantee full pairwise coverage. So the assumption is plausible in principle. However, Section 6.4 validates output only by checking that the optimized sample's interactions equal the initial sample's interactions, not by independently enumerating the full interaction universe. If YASA or the extraction pipeline misses a valid pair on some model, that pair is absent from I. The consequence is worse than 'the certificate is silent': Property 1 treats any pair {p,q} not in I as an invalid interaction, so two compatible interactions can be declared mutually exclusive. The binary program (1)-(3) and LB-LNS can then select both, producing a lower bound that exceeds the true optimum. A matching SampLNS upper bound would then look like a proof of optimality when it is not. Thus the headline 'provable optimality' results inherit an untested completeness assumption. Separately, the abstract's 63% optimality figure is not supported by the body's 55% (26/47) and should be reconciled.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a duality-based framework for the t-wise interaction sampling problem (t-ISP). It proves that the problem of finding a maximum-cardinality set of mutually exclusive valid interactions is weakly dual to finding a minimum-cardinality complete t-wise sample (Theorem 1), and uses feasible dual solutions as lower bounds. On the algorithmic side, it introduces LB-LNS for lower bounds and SampLNS for upper bounds, combining a YASA initial sample with large neighborhood search and CP-SAT repairs. The authors evaluate SampLNS on 47 feature models from the literature, reporting that it improves on previous algorithms for 40/47 models and that a majority of the resulting samples can be certified optimal by matching upper and lower bounds.","tokens_in":29799,"tokens_out":10763,"duration_ms":104532,"significance":"If the claims withstand scrutiny, this is a substantial contribution to configurable-system testing: it replaces purely heuristic sample-size comparisons with rigorous quality certificates, gives a genuinely weak-dual lower bound that does not depend on fitted constants, and ships reproducible code and data. The core duality argument is elementary and correct, and the empirical protocol has real strengths: five runs per configuration, multiple baselines, coverage-equality checks, and a separate experiment on the influence of the initial sample. The main caveats are that the formal CP-SAT model in Section 4.1 contains an apparent implication-direction error, the empirical optimality certificates inherit an untested completeness assumption on the extracted interaction set, and the abstract's 63% optimality figure conflicts with the body's 26/47 (55%).","major_comments":[{"comment":"The formal CP-SAT model is inconsistent with its surrounding text. Equation (5) is written as u_i ⇒ y_i^I, but the text says that this 'prevents deactivated copies of sample configurations from covering interactions.' As written, an inactive copy (u_i = 0) can still set y_i^I = 1 and cover interactions, while an active copy (u_i = 1) is forced to cover every interaction in I. The objective in Eq. (4) therefore does not minimize the number of used configurations as intended. The correct constraint is y_i^I ⇒ u_i. The released implementation may implement the intended semantics, but the manuscript as written is not a faithful description of the model behind OptSample.","section":"Section 4.1, Eqs. (4)–(8)"},{"comment":"The soundness of the lower-bound certificates and hence the 'provable optimality' results depends on I being the complete set of all valid pairwise interactions. Section 3.1 states that I 'can efficiently be extracted from a given feasible sample,' and Algorithm 2 initializes from a YASA(m=1) sample. Section 6.4 verifies the optimized samples only by checking equality between the interactions of the initial and optimized samples; it never independently enumerates the full set of valid interactions. If the initial sample missed a valid pair, Property 1 and constraint (2) would treat that pair as invalid, potentially declaring genuinely compatible interactions mutually exclusive and inflating the lower bound. In that case a reported UB=LB match would not certify optimality. Please add an independent completeness check of I (e.g., enumerate all valid pairs via SAT or FeatureIDE) and report the outcome for all 47 models.","section":"Section 3.1 and Section 6.4"},{"comment":"The abstract claims that SampLNS can 'achieve and prove optimality of solutions for 63% of all instances,' but Section 6.2.2, Table 1, and the Conclusion consistently report 26 of 47 instances, i.e., approximately 55%. Please reconcile the abstract with the body, or explicitly define the different counting rule (e.g., including extended 3h runs or near-optimal solutions) that produces 63%.","section":"Abstract and Section 6.2.2"}],"minor_comments":[{"comment":"The formal definition says an interaction is a subset of exactly t literals, while the introduction says 'every valid combination of t or less features.' For pairwise sampling the distinction does not affect the results, but the definitions should be aligned.","section":"Section 2.2"},{"comment":"There is a typo: 'Minium Vertex Cover' should be 'Minimum Vertex Cover.'","section":"Section 2.4"},{"comment":"The feature model name 'FreeBDS-8_0_0' should be 'FreeBSD-8_0_0.'","section":"Section 6.3.2"},{"comment":"Figure 3 lists ACTS-IPOF-FT, ACTS-IPOG-FT, ACTS-IPOF-CSP, and ACTS-IPOG-CSP, but Section 6.1 describes only Chvátal, ICPL, IPOG, IncLing, and YASA as the selected baseline algorithms. Please clarify how the ACTS variants were obtained and why they are not described in the experiment-design section.","section":"Figure 3"},{"comment":"The sentence 'the set of all valid interactions, I, can efficiently be extracted from a given feasible sample' should say 'from a complete t-wise sample'; otherwise the sentence is circular, since a feasible sample in the sense of Section 2.2 already covers all interactions in I.","section":"Section 3.1"},{"comment":"The bottom-row notation 'optimality 7 ≥ 26 [15%] [55%]' is cryptic. Please spell out that 7/47 baseline solutions and at least 26/47 SampLNS solutions match the lower bound, and define the percentages explicitly.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The central duality idea is sound and the empirical study is extensive, but the manuscript needs a corrected CP-SAT formulation and a direct validation of the completeness of I before the optimality certificates can be taken at face value. The abstract/body discrepancy in the optimality percentage should also be fixed. These are fixable within the manuscript's scope, so I am not recommending rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one — it is a real contribution, with one number in the abstract that is simply wrong, and one assumption that should be checked before the optimality certificates are used as advertised.\n\nThe core result is Theorem 1: a maximum set of mutually exclusive t-wise interactions is weakly dual to a minimum complete sample. The proof is a short pigeonhole argument and it is correct. This generalizes the existing CALOT/Ansótegui lower-bound idea, which only assigned different values to the same t features, to arbitrary incompatible interaction pairs. That matters for binary feature models, where the old bound is capped at 2^t. The LNS/CP-SAT machinery is standard, but the integration is serious: adaptive destroy-repair, symmetry breaking, parallel lower/upper bound threads, and it ships code and data. The empirical comparison on 47 models is mostly careful — five runs per algorithm, mean reporting, coverage checks on all samples, plus a robustness experiment on the initial sample. The claimed improvements over baselines (40/47) are supportable.\n\nNow the soft spots. First, the abstract claims 63% of instances are proved optimal; the body's Table 1 and the conclusion both say 26/47, which is 55%. That is not a rounding issue and it has to be fixed.\n\nSecond, and more important: every optimality certificate depends on the set I of valid interactions being complete. Section 3.1 says I can be efficiently extracted from a given feasible sample, and SampLNS starts from a YASA sample. Section 6.4 validates correctness only by checking that the optimized sample's interactions equal the initial sample's interactions. It never independently enumerates the full set of valid pairwise interactions. If the initial sample missed a valid pair on any benchmark, that pair is not in I, Property 1 then treats it as invalid, and the lower-bound program can declare two compatible interactions mutually exclusive. A matching upper bound would then certify a false optimum. The paper gives reason to think YASA has full pairwise coverage, so this may be harmless in practice, but it is untested and it is load-bearing for the 26 optimality claims. The duality theorem itself is unconditional; the benchmark certificates are not.\n\nThe paper is for people working on t-wise sampling, covering arrays, and configurable-system testing. It deserves serious peer review — the framework is useful even with the completeness caveat. I would send it out, asking for the 63/55 reconciliation and either independent validation of I on the benchmarks or a downgrade to 'optimal with respect to the extracted interactions.'","headline":"Correct duality result, strong engineering, but the 63% headline is unsupported and the optimality certificates inherit an untested completeness assumption on the extracted interaction set.","tokens_in":30320,"tokens_out":2697,"would_cite":true,"duration_ms":26848,"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 weak-duality theorem for t-wise interaction sampling says every mutually exclusive set of interactions is a lower-bound certificate, and the SampLNS algorithm uses it to find—and often prove—minimal samples for configurable software…","keywords":["t-wise interaction sampling","configurable software systems","feature models","sample-size minimization","duality","lower bounds","large neighborhood search","optimality certificates"],"falsifier":"Run SampLNS on a model where it reports equal lower and upper bounds, then independently enumerate all valid pairwise interactions (e.g., by SAT enumeration) and solve the full sample-minimization problem to proven optimality on that same model; a missing valid interaction in SampLNS's interaction set, or a feasible sample smaller than its reported lower bound, would refute the certificate.","tokens_in":29333,"feed_emoji":"⚙️","tokens_out":13382,"duration_ms":124324,"temperature":0.7,"pith_summary":"Configurable software can have millions of valid configurations, and testing every one is infeasible. This paper attacks the resulting combinatorial question: what is the smallest set of configurations that still contains every valid interaction among up to t features? The central claim is a weak-duality theorem: any collection of pairwise mutually exclusive interactions—interactions that can never be realized in the same configuration—is a lower bound on the size of any full-coverage sample, so finding the largest such collection certifies how low any sample can go. The authors implement this as SampLNS, which runs two large-neighborhood searches in parallel, one shrinking a candidate sample and one growing a mutually exclusive set, and stops when the two sizes meet; on 47 feature models from the literature, they report smaller samples than prior methods in 85% of cases and provable optimality for 63% of all instances. If these results hold, researchers and practitioners no longer need to compare sampling heuristics blindly against each other: a matching lower bound turns the best sample into a certified optimum.","feed_headline":"Duality certifies minimal test samples for configurable software","feed_subtitle":"SampLNS finds smaller test-configuration sets on 85% of 47 systems and certifies most as minimal.","key_machinery":"The carrying object is the compatibility graph of valid interactions: vertices are valid t-wise interactions, and an edge joins two interactions exactly when some valid configuration contains both. A set of mutually exclusive interactions is then an independent set, and the theorem says every independent set is a valid lower bound. The upper-bound side, SampLNS, selects a subset S′ of the current sample to delete, collects the interactions that S′ alone covered, and invokes a CP-SAT model (OptSample) that optimally repairs that subset as quickly as possible. The lower-bound side, LB-LNS, selects a subset E′ of the current mutually exclusive set to delete and invokes a binary-programming model (OptLB) that exactly solves the restricted independent-set problem on the interactions compatible with the remainder. Running the two loops concurrently lets the lower and upper bounds converge, and when they meet, optimality is certified.","core_discovery":"The paper's core discovery is Theorem 1: the problem of finding a maximum-cardinality set of mutually exclusive t-wise interactions is weakly dual to the problem of finding a minimum-cardinality complete t-wise interaction sample. Two interactions are mutually exclusive if no valid configuration contains both; because every configuration in a sample can cover at most one member of a mutually exclusive set, any sample that covers all valid interactions must have at least as many configurations as the set has members. Thus every feasible set of mutually exclusive interactions is a lower-bound certificate, and equality with the size of a feasible sample proves that sample optimal. SampLNS operationalizes this identity by maintaining an upper bound, a heuristic sample improved by deleting blocks of configurations and optimally repairing the uncovered interactions with CP-SAT, and a lower bound, a heuristic mutually exclusive set improved by restricted maximum-independent-set solves with a MIP solver, and it combines the two searches in one parallel process. In the empirical evaluation, the authors report SampLNS matching or beating all previous sampling algorithms on 40 of 47 models and closing the gap to prove optimality in the majority of cases.","pith_inferences":["The duality theorem is stated for arbitrary t, not only pairwise interactions, so the same lower-bound machinery transfers to 3-wise and higher-strength sampling once mutual exclusiveness can be detected for larger tuples; the paper's evaluation is pairwise.","The compatibility-graph view reconnects t-wise interaction sampling to the maximum independent set problem, so advances in exact and heuristic independent-set solving could directly tighten the lower bounds on instances where the gap remains large.","The destroy-and-repair loop only needs to know which interactions become uncovered after deleting configurations, so a similar sampler could certify other coverage criteria, such as partial t-wise or distance-based coverage, without changing the logic of the certificate.","For product lines where each tested configuration is expensive to assemble, a certified lower bound converts test effort from an unknown risk into a hard number: even without optimality, the remaining gap tells a planner exactly how much headroom is left."],"forward_implications":["Matching lower and upper bounds turn a heuristic sample into a certified minimal sample, so on solved instances no future heuristic can beat the result and testing budgets can be fixed with certainty.","For instances where the bounds do not meet, the gap between them is a hard upper limit on possible further savings, letting practitioners distinguish systems that are essentially solved from those worth additional algorithmic effort.","The benchmark results indicate that previous greedy samplers were often far from optimal: for at least 28 of the 47 models the best prior sample was more than 20% above the new lower bound, so the observed improvements are real reductions in test effort.","Because SampLNS's final sample quality barely changes when the initial sample comes from different algorithms, the method can be initialized with the fastest available sampler and still converge to nearly the same result.","On the largest certified model, EMBToolkit with 1,179 features and 5,414 clauses, the paper reports a provably minimal sample, showing that the certificates can scale to industrial-size configurable systems."],"supporting_citations":[{"why":"The NP-hardness framework for Set Cover, used to argue that t-wise interaction sampling is NP-hard and that proving optimality is coNP-hard.","marker":"[14]"},{"why":"The CALOT incremental SAT formulation for combinatorial testing, the predecessor whose exact CP-SAT model SampLNS scales through large-neighborhood search.","marker":"[15]"},{"why":"Prior SAT-based mutual-exclusiveness lower bounds for non-binary features, which the paper generalizes to all valid interactions of binary feature models.","marker":"[32]"},{"why":"The YASA sampling algorithm, which supplies SampLNS's initial sample, the coverage-growth behavior in Figure 2, and a main baseline.","marker":"[26]"},{"why":"The ICPL greedy pairwise sampler, used as a comparison baseline and as a source of alternative initial samples.","marker":"[25]"},{"why":"The IncLing greedy incremental sampler, used as a baseline and as another initial-sample generator for the dependence experiment.","marker":"[34]"},{"why":"The greedy set-cover heuristic, included as a baseline sampling algorithm in the evaluation.","marker":"[41]"},{"why":"The CP-SAT constraint solver, the engine behind the OptSample repair subroutine.","marker":"[27]"}],"fun_headline_variants":["Duality proves optimal test sampling for configurable systems","SampLNS certifies minimal test sets for 63% of configurable systems","Provable lower bounds shrink configurable system test samples","Duality-based algorithm beats heuristics on 85% of systems","Optimal sampling certified via weak duality for t-wise interactions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The empirical optimality certificates assume the starting sample already contains every valid interaction of the feature model, because SampLNS extracts its interaction list from that sample and never independently enumerates all valid interactions; any interaction the starting sample missed would be invisible to the lower bound and to the coverage check.","fun_headline_variants_meta":{"raw":{"variants":["Duality proves optimal test sampling for configurable systems","SampLNS certifies minimal test sets for 63% of configurable systems","Provable lower bounds shrink configurable system test samples","Duality-based algorithm beats heuristics on 85% of systems","Optimal sampling certified via weak duality for t-wise interactions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000239,"raw_usage":{"total_tokens":1561,"prompt_tokens":1039,"completion_tokens":522,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":655,"completion_tokens_details":{"reasoning_tokens":435}},"tokens_in":655,"tokens_out":522,"duration_ms":5088,"temperature":1.0,"reasoning_tokens":435,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:50:34.595143+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SampLNS on a model where it reports equal lower and upper bounds, then independently enumerate all valid pairwise interactions (e.g., by SAT enumeration) and solve the full sample-minimization problem to proven optimality on that same model; a missing valid interaction in SampLNS's interaction set, or a feasible sample smaller than its reported lower bound, would refute the certificate.","supporting_citations":[{"cited_title":"Incomplete maxsat approaches for combinatorial testing.Journal of Heuristics, 28(4):377–431, 2022","cited_arxiv_id":null,"evidence_quote":"Prior SAT-based mutual-exclusiveness lower bounds for non-binary features, which the paper generalizes to all valid interactions of binary feature models."},{"cited_title":"YASA: Yet Another Sampling Algorithm","cited_arxiv_id":null,"evidence_quote":"The YASA sampling algorithm, which supplies SampLNS's initial sample, the coverage-growth behavior in Figure 2, and a main baseline."},{"cited_title":"An Algorithm for Generating T-Wise Covering Arrays from Large Feature Models","cited_arxiv_id":null,"evidence_quote":"The ICPL greedy pairwise sampler, used as a comparison baseline and as a source of alternative initial samples."},{"cited_title":"In- cLing: Efficient Product-line Testing Using Incremental Pairwise Sampling","cited_arxiv_id":null,"evidence_quote":"The IncLing greedy incremental sampler, used as a baseline and as another initial-sample generator for the dependence experiment."},{"cited_title":"A Greedy Heuristic for the Set-Covering Problem.Mathematics of Operations Research (MOR), 4(3):233–235, 1979","cited_arxiv_id":null,"evidence_quote":"The greedy set-cover heuristic, included as a baseline sampling algorithm in the evaluation."},{"cited_title":"Or-tools","cited_arxiv_id":null,"evidence_quote":"The CP-SAT constraint solver, the engine behind the OptSample repair subroutine."}],"review_version":1}