{"id":"2b255333-4788-4672-aca1-2d747ec3103c","arxiv_id":"2507.08053","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A distance-based categorical kernel and two algorithmic modifications let TPE optimize combinatorial spaces more efficiently than the original TPE on synthetic benchmarks.","lead":"This paper adds a distance-aware kernel to the TPE hyperparameter optimizer, letting it handle combinatorial search spaces such as permutations and binary strings. The authors show on two synthetic benchmarks that the modified TPE finds better solutions in fewer evaluations than the standard TPE.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (8) scales beta in the wrong direction: it multiplies beta by sqrt(log_b C), broadening the kernel and worsening the oversmoothing it purports to fix; the text and ablation claim the opposite.","rationale":"The reader's CONDITIONAL verdict is appropriate, but the most load-bearing problem is not only the external robustness of the user-supplied metric. The paper's own derivation in Section 3.2.2 is internally inconsistent: Eq. (8) has the beta' scaling in the wrong direction relative to its stated purpose, and the adjacent prose and Appendix A describe the opposite effect. Since the Section 3.2.2 modification is presented as the key to improving sample efficiency in large combinatorial spaces, a reader cannot reproduce or assess the method from the paper text alone. This is an internal correctness issue, not a disagreement with the field's consensus. The self-admitted limitations in Section 5 (inadequate evaluation, memory complexity) independently weaken the abstract's 'verified' wording, but they do not change the verdict: they support CONDITIONAL rather than ACCEPT. I also note the code is public and the synthetic experiments are run over 10 seeds, which is real evidence, but it only applies to the implementation actually run; the paper must first specify that implementation correctly. The concrete check above directly resolves which branch of the inconsistency is in play.","tokens_in":7702,"tokens_out":7889,"duration_ms":84648,"concrete_test":"Inspect the released Optuna implementation at https://github.com/nabenabe0928/optuna/tree/freeze/metric-tpe-experiments/ and extract the beta' computation for categorical kernels. If the code computes beta' = beta / sqrt(log_b C_d), Eq. (8) in the paper is wrong and must be corrected; if it computes beta' = beta * sqrt(log_b C_d), the ablation's b_d ordering contradicts the formula and the reported improvement is not explained by the stated mechanism. Independently, re-derive Eq. (8) by requiring the maximum kernel exponent to equal log_{b_d} C_d and confirm whether the radical belongs in the denominator.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algorithmic modification in Section 3.2.2 is internally inconsistent. First, the text says the combined categorical kernel with Hamming distance is (1/(N+1))^{M_Ham/K}, but substituting h=(C-1)/(N+1) into Eq. (7) gives exponent (M_Ham/K)^2, not M_Ham/K. More seriously, Eq. (8) defines beta' = beta * sqrt(log_b C_d). The stated goal is to counteract oversmoothing caused by a maximum kernel exponent of 1 instead of K. To raise the maximum exponent to K, beta must be divided by sqrt(log_b C_d), since the exponent at M=M_max is log((C-1)/h) * (M_max/beta')^2. With the published formula, beta' is larger than beta, making the kernel even broader and increasing exploration, exactly opposite to the claimed fix. This is confirmed by the text immediately after Eq. (8), which says a smaller b_d leads to more exploitation: under Eq. (8), a smaller b_d gives a larger beta' and a wider kernel. The Appendix ablation also treats lower b_d as exploitation-leaning, consistent only with division. Therefore, either Eq. (8) contains a typo (radical in the denominator) or the implemented method differs from the paper. In both cases, the paper as written does not correctly specify the modification claimed to drive the performance gains in Fig. 1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a distance-aware extension of the categorical kernel used in TPE, replacing the Aitchison-Aitken kernel with a Gaussian-like kernel over a user-supplied distance metric, and adds two practical modifications: an efficient approximate maximum-distance computation and a scaling of the bandwidth parameter beta intended to correct oversmoothing on large combinatorial spaces. The method is evaluated on two synthetic problems (EmbeddingCosine and PermutationShiftL1) against original TPE and random search, with code released in Optuna.","tokens_in":7998,"tokens_out":6717,"duration_ms":70854,"significance":"If correct, the contribution is practically relevant: a working distance-aware TPE for combinatorial spaces would fill a real gap in a widely deployed optimizer. The theoretical generalization in Section 3.1 is clean, and the release of the implementation in Optuna is a concrete asset. However, the central modification in Section 3.2.2 contains a direction error in the bandwidth scaling, and the empirical evaluation is too limited to support the paper's stated verification. The significance is therefore contingent on correcting the formulation and strengthening the experiments.","major_comments":[{"comment":"The scaling beta' = beta * sqrt(log_b C_d) is in the wrong direction. Substituting this beta' into Eq. (7), the kernel exponent at the maximum distance becomes -log((C_d-1)/h) / log_b C_d, which is smaller in magnitude than the original -log((C_d-1)/h); hence the kernel is broader, not narrower. The text and Appendix A state that a smaller b_d leads to more exploitation, but under Eq. (8) a smaller b_d gives a larger beta' and a wider kernel. To increase the maximum exponent from 1 to K (or log_b C_d), beta must be divided by sqrt(log_b C_d). Either Eq. (8) is a typo or the implemented method differs from the paper; as written, the paper does not correctly specify the modification claimed to drive the performance gains in Figure 1.","section":"Section 3.2.2, Eq. (8)"},{"comment":"The text states that the combined kernel for a K-bit Hamming distance is (1/(N+1))^{M_Ham/K}, but substituting h = (C_d-1)/(N+1) and M_max = K into Eq. (7) yields exp(-log(N+1) (M_Ham/K)^2), i.e. (1/(N+1))^{(M_Ham/K)^2}. The squared exponent follows from the quadratic form of the Gaussian kernel in Eq. (7) and differs from the linear exponent of the product-of-binary-kernels representation. This derivation error should be corrected; the maximum-exponent comparison (1 vs K) survives, but the interpolation behavior is not as described.","section":"Section 3.2.2"},{"comment":"The empirical evidence is too thin to support the abstract's claim that the method 'identifies better solutions with fewer evaluations' as a verification. The evaluation uses only two synthetic problems, 10 seeds, and 100 evaluations per run, with no statistical tests and no comparison to existing combinatorial Bayesian optimization methods. The paper itself acknowledges an 'inadequate methodological evaluation' in Section 5. Additionally, the default b_d = 6 is selected from an ablation on the same benchmarks (Appendix A), so the reported improvement is partly fitted rather than predicted. The experiments should be expanded with more tasks, error bars with formal comparisons, and at least one established combinatorial BO baseline; the conclusion should be tempered accordingly.","section":"Section 4 and Section 5"}],"minor_comments":[{"comment":"The sentence 'we used the proposed method without the modification discussed in Section 3.2.2' is confusing, since Figure 1 shows both 'Ours' and 'Ours (No Modification)'. Please clarify that two variants of the proposed method were run.","section":"Section 4"},{"comment":"The phrase 'the modification in Eq. (7)' should refer to Eq. (8), since Eq. (7) defines the base kernel and Eq. (8) defines the modification.","section":"Section 4"},{"comment":"The assumption that a combinatorial parameter with C combinations behaves like log_b C independent categorical parameters is not derived or validated; it is used to motivate Eq. (8), so it should be stated explicitly and tested, especially because the direction of Eq. (8) depends on this assumption.","section":"Section 3.2.2"}],"recommendation":"major_revision","confidential_remarks":"The main technical issue in Section 3.2.2 looks like a fixable typo (multiplication instead of division in Eq. (8)), but it is load-bearing because the experiments and ablation are interpreted under the opposite direction. The empirical evaluation is also quite minimal for the strength of the claims. I would ask the authors to correct the formula, rerun or at least confirm the experiments with the corrected implementation, and strengthen the experimental protocol before considering acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kenshin,\n\nRead it. The core proposal is a distance-aware categorical kernel for TPE, and the first part is genuinely nice. Eq. (6)-(7) cleanly bridge the categorical and numerical kernels, and the approximate-maximum-distance trick in Section 3.2.1 is a sensible and practical complexity reduction for large combinatorial spaces. The code is public, and the paper is clearly written.\n\nThe soft spots, though, are load-bearing. In Section 3.2.2, Eq. (8) defines beta' = beta * sqrt(log_{b_d} C_d). The stated goal is to counter oversmoothing and make the kernel more exploitative. But multiplying beta by a factor greater than 1 broadens the kernel—that is more exploration, not less. To raise the maximum exponent to K, beta needs to be divided by sqrt(log_b C_d). The text and the ablation confirm the intent: a smaller b_d should exploit, and under Eq. (8) it does the opposite. So either the formula is a typo or the implementation differs from the paper. Also, just above Eq. (8), the claim that the Hamming-distance kernel is (1/(N+1))^{M/K} is wrong by a square; substituting into Eq. (7) gives (1/(N+1))^{(M/K)^2}. Two math errors in the central section is a heavy burden.\n\nBeyond that, the empirical support is thin: two synthetic problems, 10 seeds, 100 evaluations, no statistical tests, and no comparison to any existing combinatorial BO method. The default b_d = 6 is selected on the same benchmarks, and the paper admits in Section 5 that the methodological evaluation is inadequate. The method's dependence on a user-supplied distance metric is never stress-tested with a poor or misleading metric.\n\nThat said, the underlying idea is sound and likely useful. Eq. (7) is an elegant generalization, the complexity reduction is real, and the plots do show a consistent separation from original TPE that matches the intended mechanism. If Eq. (8) is a typo, the method is plausible.\n\nMy take: this deserves a serious referee, but the authors need to fix the equation, correct the exponent, re-run the experiments against the actual implementation, and add at least one real benchmark plus a combinatorial BO baseline. Send it out, but make those fixes the condition for acceptance.","headline":"Distance-aware TPE is a genuinely useful idea, but Eq. (8) as written multiplies beta where it should divide, so the paper's central modification is internally inconsistent.","tokens_in":8473,"tokens_out":4982,"would_cite":false,"duration_ms":49479,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that giving TPE's categorical kernel a user-defined distance metric lets tree-structured Parzen estimator solve black-box combinatorial optimization problems with fewer evaluations, and it provides two practical…","keywords":["tree-structured Parzen estimator","combinatorial optimization","categorical kernel","distance metric","Bayesian optimization","sample efficiency","Optuna"],"falsifier":"Run the proposed method on EmbeddingCosine with a scrambled distance metric (for instance, permuting the labels of the 1000 categories randomly while leaving the objective unchanged) and count evaluations needed to reach a fixed objective value; if it does no better than the original TPE, the claimed efficiency gain rests entirely on the hand-designed metric. A complementary check: rerun the large EmbeddingCosine (C=1000, K=16) setup with $b_d=6$ versus $b_d=2$ and verify the overexploration pattern reported in the ablation.","tokens_in":7512,"feed_emoji":"🧩","tokens_out":4550,"duration_ms":42447,"temperature":0.7,"pith_summary":"The paper claims that the tree-structured Parzen estimator (TPE), a standard Bayesian optimization method for hyperparameters, can be made efficient on black-box combinatorial optimization problems by giving its categorical kernel a distance structure. The authors rewrite the categorical kernel in a Gaussian-like form, replace the equality-based same-or-different distance with a user-supplied metric, and add two practical fixes for large search spaces. They report on synthetic problems, an embedding/cosine task and a permutation-shift task, that the proposed method reaches better objective values in fewer evaluations than the original TPE and random search, and that the fixes prevent the overexploration seen without them. The method is shipped in the Optuna framework, so practitioners can call it directly.","feed_headline":"Distance-aware TPE beats original TPE on combinatorial search","feed_subtitle":"A distance metric inside the TPE kernel finds better permutations and K-ary solutions in fewer evaluations.","key_machinery":"The load-bearing object is the generalized categorical kernel $k_d(x_d,x'_d)=\\exp(-\\frac12 (M_d(x_d,x'_d)/\\beta)^2)$, obtained by rewriting the Aitchison-Aitken kernel and substituting a user-supplied distance $M_d$ for the binary indicator $1-\\delta(x_d,x'_d)$. This one identity is what lets TPE see similarity structure among categories. Two practical mechanisms carry the large-search-space part of the argument: an approximation of $M_d^{\\max}$ that costs $\\Theta(C_d \\min(C_d, N_d^{\\mathrm{unique}}))$ instead of $\\Theta(C_d^2)$, and the rescaled bandwidth $\\beta'=\\beta\\sqrt{\\log_{b_d} C_d}$ that prevents the kernel from oversmoothing (and thus overexploring) when several categorical dimensions are packed into one combinatorial parameter. The paper fixes a default $b_d=6$ and presents an ablation study of $b_d$ in the appendix.","core_discovery":"The paper's central claim is that TPE's categorical kernel, which treats every category as equally distant from every other, is the bottleneck for combinatorial optimization, and that replacing the binary coincidence factor with a user-defined distance metric removes that bottleneck. Concretely, the kernel becomes $k_d(x_d,x'_d)=\\exp(-\\frac12 (M_d(x_d,x'_d)/\\beta)^2)$, with the scale $\\beta$ chosen so that the kernel falls back to the original Aitchison-Aitken kernel when the distance is maximal. Because computing the exact maximum distance over all category pairs costs $\\Theta(C_d^2)$, the paper proposes using the maximum distance to each observed point instead, and it introduces a modified scale $\\beta'=\\beta\\sqrt{\\log_{b_d} C_d}$ that assumes a combinatorial parameter encodes $\\log_{b_d} C_d$ binary dimensions in order to counteract oversmoothing. The paper states that, in experiments, this identifies better solutions with fewer evaluations than the original TPE on both synthetic problems, and that the modification never degraded performance.","pith_inferences":["A testable extension is to study metric misspecification: if the supplied distance is uncorrelated with the objective's similarity structure, the method should degrade to (or below) the original TPE, so real applications hinge on finding a meaningful metric; the paper does not yet address this.","The $\\beta'$ scaling suggests an interpretation of a combinatorial parameter as a packed binary string; one could push this further by making $b_d$ adaptive to the observed objective landscape instead of fixing it at 6.","Since the kernel is now metric-based, a natural next step is connecting it to embeddings: choosing $M_d$ implicitly defines a geometry on the category space, so categorical variables could be embedded and handled by the numerical kernel machinery already in TPE."],"forward_implications":["If the central claim holds, TPE users can solve permutation and K-ary combinatorial problems with a user-supplied distance metric and will reach the same objective value in fewer evaluations than the original TPE.","The per-kernel calculation cost no longer grows quadratically with the number of categories, so larger combinatorial search spaces become feasible in memory-constrained settings.","Because the modification only changes the per-dimension kernel, it can be combined with other TPE extensions such as multi-objective, constrained, and multi-fidelity variants.","The availability in Optuna means the result is directly usable in existing HPO pipelines rather than remaining a standalone algorithm."],"supporting_citations":[{"why":"Supplies the original categorical kernel that the paper rewrites and generalizes; removing it would leave the fallback identity in Eq. (6) without a basis.","marker":"(Aitchison and Aitken, 1976)"},{"why":"Introduces TPE and the density-ratio sampling mechanism that the proposed kernel is plugged into.","marker":"(Bergstra et al., 2011)"},{"why":"Provides the bandwidth heuristic and default TPE settings used in the experiments and in the derivation of Eqs. (7) and (8).","marker":"(Watanabe, 2023b)"},{"why":"Provides the Optuna TPESampler baseline used in the experiments and the open-source codebase into which the proposed method is integrated.","marker":"(Akiba et al., 2019)"}],"fun_headline_variants":["Distance in TPE kernel speeds combinatorial optimization","TPE with distance metric improves discrete search","New TPE kernel solves black-box combos faster","Distance-aware kernel improves TPE for combinatorial tasks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method requires the user to supply a distance metric between categories that reflects how similar two solutions are for the objective; every experiment uses a hand-designed metric aligned with the synthetic objective, and the paper provides no evidence about what happens when the metric is uninformative or misleading.","fun_headline_variants_meta":{"raw":{"variants":["Distance in TPE kernel speeds combinatorial optimization","TPE with distance metric improves discrete search","New TPE kernel solves black-box combos faster","Distance-aware kernel improves TPE for combinatorial tasks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000903,"raw_usage":{"total_tokens":3903,"prompt_tokens":977,"completion_tokens":2926,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":2868}},"tokens_in":593,"tokens_out":2926,"duration_ms":21475,"temperature":1.0,"reasoning_tokens":2868,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:39:02.529606+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed method on EmbeddingCosine with a scrambled distance metric (for instance, permuting the labels of the 1000 categories randomly while leaving the objective unchanged) and count evaluations needed to reach a fixed objective value; if it does no better than the original TPE, the claimed efficiency gain rests entirely on the hand-designed metric. A complementary check: rerun the large EmbeddingCosine (C=1000, K=16) setup with $b_d=6$ versus $b_d=2$ and verify the overexploration pattern reported in the ablation.","supporting_citations":[{"cited_title":"and Aitken, C","cited_arxiv_id":null,"evidence_quote":"Supplies the original categorical kernel that the paper rewrites and generalizes; removing it would leave the fallback identity in Eq. (6) without a basis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces TPE and the density-ratio sampling mechanism that the proposed kernel is plugged into."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Optuna TPESampler baseline used in the experiments and the open-source codebase into which the proposed method is integrated."}],"review_version":1}