{"id":"fc2d01b9-7315-44bf-8ff3-1cf3a675009d","arxiv_id":"1908.07031","paper_version":7,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"HQS measures a hierarchy's search efficiency as a POMDP bot's expected reward, without ground-truth labels.","lead":"The paper defines HQS, a score for how well a product-catalog hierarchy supports item search, using a POMDP model of a bot that descends or stops at each node. The score works without ground-truth labels, so it could help online retailers and ML teams compare hierarchical clusterings directly.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"HQS's policy is optimized on squared η while its oracle score uses unsquared η, so the measure can disagree with the search efficiency it claims to quantify.","rationale":"The paper makes a clear, implementable proposal and provides code, and the case study is a reasonable sanity check for the intended behaviour. However, the most load-bearing concern is not only whether real searchers follow the softmax guidance function, but whether the score even measures the search efficiency of the bot it defines. The transition model in Eq. (3) squares η, and although the belief update cancels one factor, the cancellation does not reach the RTBSS policy's Q-values. The policy is therefore optimised under a squared-η model while HQS is evaluated under an unsquared-η oracle. This can cause the policy to stop at the root when descending would improve the oracle value, so HQS understates the hierarchy's true search efficiency. This is an internal correctness issue, not merely a question of external validity, and it is testable analytically on a two-child hierarchy. The reader's weakest assumption identified the dual role of η as a concern; this attack sharpens that concern by showing a concrete place where the dual role changes the computed score. Since the issue is fixable and the empirical ordering may survive correction, a conditional acceptance remains the right verdict, with the mismatch as an explicit condition to address.","tokens_in":16568,"tokens_out":11650,"duration_ms":128546,"concrete_test":"Derive HQS and the RTBSS decision for a two-child hierarchy with one correct child, η(c0,c1)=0.9, η(c0,c2)=0.1, and equal child rewards r. Compare the RTBSS stop/descend decision against the oracle-optimal decision, which descends iff 0.9(r+1)−1 > r(c0). If there exist r(c0) and r such that the policy stops at the root while descending yields a higher oracle value, the mismatch is confirmed. Additionally, recompute the five-hierarchy ranking from Section 5.1 with \\hat Q computed using η(c,c′) instead of η(c,c′)^2; if the ranking changes, the reported validation does not survive the correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central issue is an internal mismatch between the probability model used to choose the policy and the probability model used to score it. In the transition specification, Eq. (3) defines p(⟨c′,1⟩|⟨c,1⟩,ad)=η(c,c′)^2 and p(⟨c′,0⟩|⟨c,1⟩,ad)=η(c,c′)(1−η(c,c′)), so the descent transition double-counts η: once as the probability that the searcher selects child c′, and once as the probability that the target is actually in c′. The Bayes filter in Eqs. (5)–(7) then cancels one factor, leaving the oracle value in Section 3.2 proportional to a single product of η along the correct path. But the RTBSS policy in Section 4.1 is computed from the belief states: \\hat Q(b,ad)=Σ_{c′} η(c,c′)(b_{c′}(r(c′)+1)−1)=b_c Σ η(c,c′)^2(r(c′)+1)−1. Thus the policy is optimized against squared η while HQS is evaluated against unsquared η. In a symmetric two-child example with η(c0,c1)=0.9, the true expected reward of descending and stopping is 0.9(r+1)−1, whereas the policy's estimate is 0.82(r+1)−1. For r(c0)=0.5 and r=0.8, RTBSS stops at the root, producing HQS=0.5, although descending would give oracle value 0.62. HQS therefore does not equal the expected search efficiency of the bot it defines; the measure depends on a policy that is miscalibrated with respect to the stated objective. The paper should either define π to optimize the oracle value directly, using η rather than η^2, or justify why this belief-policy suboptimality is an acceptable part of the quality measure.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes HQS (Hierarchy Quality for Search), a quantitative measure for evaluating hierarchical clusterings without ground-truth labels. The author models an item search as a Partially Observable Markov Decision Process in which a bot descends a tree stochastically according to a softmax guidance function based on item-cluster similarities, and may stop and search at any node. The quality score is the expected long-term reward of the bot's policy, specifically the oracle value in the underlying MDP when the bot uses a belief-based RTBSS policy. The paper provides a POMDP formulation, a simplified policy with polynomial complexity, a case study on 12 Amazon items under five constructed hierarchies, and a scaling experiment with sampling. The central claim is that HQS orders hierarchies by their support for efficient search without requiring ground-truth information.","tokens_in":17013,"tokens_out":12195,"duration_ms":121528,"significance":"If the model were internally consistent, HQS would address a genuine gap: few existing measures evaluate the structural organization of a hierarchy independently of ground truth, and the decision-theoretic framing is original. The paper is clearly written, introduces an interesting notion of an 'oracle value' for a stochastic search policy, and releases a public implementation. The scaling experiment usefully demonstrates that a sampled approximation of HQS converges quickly. However, the correctness of the measure as defined is undermined by an inconsistency between the transition model used for policy optimization and the oracle value used for scoring, so the practical contribution cannot be accepted without reworking the model.","major_comments":[{"comment":"The scaling experiment uses a different similarity function (inverse Euclidean distance after PCA) from the case study (cosine similarity on TF-IDF), and a single automatically generated hierarchy via agglomerative clustering. The relation between the two experimental settings is not explained, and it is unclear whether the sampling approximation result generalizes to the original guidance function. The paper should clarify the experimental protocol or provide results for the same similarity on both settings.","section":"Sec. 5.2"}],"minor_comments":[{"comment":"The phrase 'we develop a POMPD model' contains a typo: 'POMPD' should be 'POMDP'.","section":"Sec. 3, first paragraph"},{"comment":"The sentence 'Let use denote a policy by π' should read 'Let us denote a policy by π'.","section":"Sec. 3, value function paragraph"},{"comment":"The notation sim(x,c′) is used without a formal definition for a cluster c′; the later definition in Section 5.1 is specific to the experimental similarity and should be introduced earlier or clearly referenced.","section":"Sec. 3, Eq. (2)"},{"comment":"The justification for setting δ = ⌈1/100⌉ = 0.01 based on the number of PCA dimensions is unclear; the ceiling notation is unusual for a temperature parameter, and the paper would benefit from an explanation of why δ should scale inversely with dimensionality.","section":"Appendix D.2"},{"comment":"The sentence 'Both HQS and HAI rank Hier-E and Hier-B as first and second, excluding the ground-truth' could be clearer; the paper should explicitly state the full ranking produced by HAI and the full ranking produced by HQS for comparison.","section":"Sec. 5.1.2"}],"recommendation":"major_revision","confidential_remarks":"The central issue in Eq. (3) is a modeling error, not a mere presentation gap, and it directly affects the meaning of the proposed measure. I encourage revision with a corrected transition model and a re-derivation of the policy and oracle value. The validation is illustrative but too thin to support the empirical claims; sensitivity analysis and a broader study would be needed. The topic is within the scope of the journal and the idea is worth pursuing, so I do not recommend rejection at this stage."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nShort take: this is a legitimate extension of Moreno et al.'s MDP hierarchy evaluation into POMDP territory, and the mathematics is more consistent than the stress-test note suggests. The squared η in the transition model is not an error; it follows from the model treating η as both the physical move probability and the probability that the target is in that child. The Bayes filter then correctly yields the posterior belief η b_c, and the oracle value in Section 3.2 is the right expected reward of the stochastic descent process. The RTBSS Q̂ function is also computing the correct ex ante expectation; the stress-test's 0.62 versus 0.5 example confuses the conditional reward at the correct child with the unconditional expectation over random descent. So I would not pursue that thread.\n\nWhat the paper does well: it gives a clean POMDP specification, a concrete policy (RTBSS with two-step look-ahead), a closed-form oracle value, and a definition of HQS that is easy to compute. The code is available, and the scaling experiment suggests sampling works. The five-hierarchy case study at least demonstrates that HQS orders obvious cases in a sensible direction.\n\nSoft spots, in order of importance. First, the big one: the model assumes the guidance function η is simultaneously (i) the bot's subjective posterior, (ii) the physical probability of moving to a child, and (iii) the true probability that the target lies in that child. That is a strong calibration assumption. If real searchers use different choice probabilities, HQS measures the hierarchy's support for a specific, idealized bot, not search efficiency generally. The paper hand-waves this by saying the transition is \"designed\", but it never discusses the gap. Second, the validation is thin: 12 items, five hand-built hierarchies, one value of δ, no sensitivity analysis for any of the four free parameters, no error bars. Third, the HAI comparison is not apples-to-apples: HAI measures agreement with a ground truth, while HQS measures search efficiency, so \"outperforming\" HAI on a few hand-made trees doesn't tell us much. Fourth, the complexity proof is only a sketch and the constants are unclear.\n\nWho it's for: people working on evaluation metrics for hierarchical clustering without labels, especially in e-commerce catalogues. It's a useful tool if you buy the calibration assumption. I'd send it to a serious referee; it deserves a hearing, but the referee should push on the η assumption and demand more robust empirical support.","headline":"The POMDP extension is coherent and the stress-test's squared-η concern does not hold up, but HQS rests on an unvalidated equivalence between the bot's beliefs and the true dynamics.","tokens_in":17508,"tokens_out":10462,"would_cite":false,"duration_ms":98765,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A search-bot's expected reward, modeled as a POMDP, scores how well a hierarchy supports finding items, with no ground-truth labels needed.","keywords":["hierarchical clustering evaluation","POMDP","belief states","search efficiency","hierarchy quality","ground-truth-free evaluation","guidance function","online planning"],"falsifier":"Measure human search times for the same item set in two hierarchies that HQS ranks far apart; if searchers are not consistently faster in the higher-scoring hierarchy, the claim that HQS tracks search efficiency is refuted. A cheaper computational check is to re-rank the hierarchies under several values of the temperature $\\delta$; if the ordering flips within a plausible range, the score depends on an uncalibrated knob rather than on the hierarchy itself.","tokens_in":16366,"feed_emoji":"🔍","tokens_out":13864,"duration_ms":121819,"temperature":0.7,"pith_summary":"The paper sets out to measure the quality of a hierarchical clustering arrangement by the efficiency with which a searcher can find items in it, without using any ground-truth labels. It defines Hierarchy Quality for Search (HQS) as the average, over all target items, of the long-run expected reward a stochastic search bot collects while navigating the hierarchy. The bot's uncertainty, decisions, and the cognitive payoff of stopping at a small cluster are modeled as a Partially Observable Markov Decision Process (POMDP), with branch choices driven by how similar each child cluster is to the target. The authors argue that this score needs no ground-truth hierarchy; in their case study it places a ground-truth hierarchy top and a deliberately poor hierarchy bottom.","feed_headline":"Score hierarchies by search-bot rewards, no labels needed","feed_subtitle":"A POMDP-based score evaluates catalogue trees purely from item similarities and branch structure.","key_machinery":"The load-bearing machinery is a Partially Observable Markov Decision Process (POMDP)---a decision model for an agent that never observes the true state and acts on a probability distribution over states---together with the belief update $b_{c'}=\\eta(c,c')b_c$, which collapses the full belief state to one scalar per node because the bot cannot backtrack and always observes its location. That identity makes the probability of being on the correct path the product of softmax similarities along the path. On top of it, the paper's simplified real-time belief-space search policy compares the value of stopping at the current node, $Q(b,a_s)=b_c(r(c)+1)-1$, with the one-level look-ahead estimate $\\hat{Q}(b,a_d)=\\sum_{c'\\in C(c)}\\eta(c,c')(b_{c'}(r(c')+1)-1)$, and descends only when the look-ahead is larger. HQS then averages the resulting per-item oracle values.","core_discovery":"The paper's central claim is that hierarchy quality for search can be reduced to a single number computed from a POMDP's oracle value: for each item $x$, the bot starts at the root with belief $b=1$ that it is on the correct path, and the probability of being on the correct path after reaching a node $c$ is $b_c=\\prod_{t=1}^T\\eta(c_{t-1},c_t)$, the product of guidance values along the path. The guidance function is the softmax $\\eta(c,c')=\\exp\\{\\mathrm{sim}(x,c')/\\delta\\}/\\sum_{c''\\in C(c)}\\exp\\{\\mathrm{sim}(x,c'')/\\delta\\}$, so the model treats the searcher's branch choice and the searcher's belief as the same probability. The value for the target is $V_x^\\pi(H)=(r(c_T)+1)\\prod_{t=1}^T\\eta(c_{t-1},c_t)-1$, where $r(c_T)$ rewards stopping at a small cluster on the correct path and $-1$ penalizes a wrong stop; HQS is the average of these values over all items. The discovery is that this decision-theoretic quantity orders hierarchies by search efficiency consistently with intuition in the paper's experiments, and that it can be approximated efficiently by sampling items.","pith_inferences":["Inference: Because $\\delta$ is a user-set temperature in the guidance softmax, HQS is really a family of measures indexed by how decisive searchers are assumed to be; ranking hierarchies under several $\\delta$ values would show whether a top-ranked hierarchy is robust or an artifact of the chosen temperature.","Inference: The per-item values that HQS averages could be used diagnostically to locate the branches and items that drag a hierarchy's score down, turning the measure from a ranking tool into a repair guide.","Inference: The model suggests a direct behavioural test the paper does not run: if HQS genuinely tracks search efficiency, hierarchies with higher scores should produce faster human search times in a controlled user study, and the assumed softmax guidance could be measured against actual branch choices.","Inference: The guidance function could be learned from clickstream or navigation logs instead of being fixed by a similarity function, letting HQS adapt to the search behaviour of a specific population while keeping the same POMDP evaluation structure."],"forward_implications":["HQS assigns a single number to a whole hierarchy, not just to one cut, so hierarchies with different depths and branching structures can be compared on the same scale.","Because HQS needs no ground truth, it can be used to tune hyperparameters of hierarchical clustering algorithms, a use the paper explicitly points toward.","The score has polynomial worst-case cost $O(N^3F(\\mathrm{sim}))$ and logarithmic average cost, so evaluating large catalogues is practical; in the paper's scaling test, sampling 30% of items already brings the normalized L1 error below 5%.","Hierarchies that split a target's close neighbours into different branches are penalized automatically, because the relevant product of guidance values shrinks even if the item is ultimately found."],"supporting_citations":[{"why":"Supplies the POMDP formalism of states, observations, belief states, and belief updates that the whole model is built on.","marker":"[Kaelbling et al., 1998]"},{"why":"The earlier MDP-based hierarchy-evaluation prototype that this paper extends by adding partial observability and a concrete policy.","marker":"[Moreno et al., 2017]"},{"why":"Source of the online planning perspective and the RTBSS algorithm specialised in Section 4 to make the policy tractable.","marker":"[Ross et al., 2008]"},{"why":"Defines the HAI metric used as the ground-truth-based baseline that HQS is compared against in the case study.","marker":"[Johnson et al., 2013]"},{"why":"Provides the product item texts underlying the case study and scaling experiments.","marker":"[McAuley et al., 2015]"},{"why":"Supplies the average-link agglomerative-clustering idea reflected in the item-cluster similarity used in the guidance function.","marker":"[Day and Edelsbrunner, 1984]"},{"why":"Used to argue that general POMDP hardness does not apply to this setting, supporting the polynomial complexity claim.","marker":"[Papadimitriou and Tsitsiklis, 1987]"}],"fun_headline_variants":["Search-bot rewards rank hierarchies, no labels","POMDP scores hierarchies via stochastic search","Evaluate catalog trees by searcher beliefs, no labels","No ground truth? Score hierarchies by POMDP search","Decision-theoretic hierarchy quality from search rewards"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire score rests on assuming a searcher picks each branch with probability proportional to an exponential of an item-cluster similarity, with a temperature parameter set by the user; if real people choose branches differently, HQS measures the assumed model rather than actual search efficiency.","fun_headline_variants_meta":{"raw":{"variants":["Search-bot rewards rank hierarchies, no labels","POMDP scores hierarchies via stochastic search","Evaluate catalog trees by searcher beliefs, no labels","No ground truth? Score hierarchies by POMDP search","Decision-theoretic hierarchy quality from search rewards"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000589,"raw_usage":{"total_tokens":2777,"prompt_tokens":973,"completion_tokens":1804,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":1731}},"tokens_in":589,"tokens_out":1804,"duration_ms":12044,"temperature":1.0,"reasoning_tokens":1731,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:28:37.642924+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure human search times for the same item set in two hierarchies that HQS ranks far apart; if searchers are not consistently faster in the higher-scoring hierarchy, the claim that HQS tracks search efficiency is refuted. A cheaper computational check is to re-rank the hierarchies under several values of the temperature $\\delta$; if the ordering flips within a plausible range, the score depends on an uncalibrated knob rather than on the hierarchy itself.","supporting_citations":[],"review_version":1}