{"id":"d623fa90-7740-4a65-ad0d-2cfa990ef3a7","arxiv_id":"2411.16030","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A binary search method that consumes a predicted distribution over key positions achieves O(H(p)+log eta) expected comparisons, with a matching lower bound.","lead":"This paper gives a search algorithm for sorted data that uses a machine-learned probability distribution over where a target key lives, rather than a single predicted location. The expected number of comparisons is roughly the entropy of the true distribution plus a logarithmic term in how far the predicted distribution is from the true one, and this is optimal up to constants.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's upper bound is false: on a geometric prediction with a singleton true distribution at the array median, the described algorithm needs Θ(√n) queries while η = Θ(n), so O(log η) cannot hold.","rationale":"The reader's conditional accept rested on a 'small repair' to Theorem 1's proof. My analysis shows the flaw is not a minor inequality slip but a fatal gap: the algorithm's endpoint probing only guarantees D_i > 2^{2k_i−2}, and the proof's inference from this to 2^{k_i} ≤ 2 log D_i is invalid. The constructed instance—geometric prediction, singleton true distribution at the median—is a legal instance of the model with η = Θ(n), yet the algorithm's cost is Θ(√n). This directly contradicts the paper's central claim of O(H(p) + log η) query complexity. The lower bound (Corollary 3) appears sound via the reduction to Mehlhorn's bound, so the issue is specifically the upper bound. Because the main algorithmic result is false as stated, the appropriate verdict is reject rather than conditional accept. I agree with the reader that the weak spot is in Theorem 1's proof around the endpoint probing inequality, but disagree that the intended conclusion survives a repair: the algorithm would need a different design (e.g., much faster endpoint growth or a different bisection rule) to achieve the claimed bound.","tokens_in":14901,"tokens_out":26651,"duration_ms":225934,"concrete_test":"Implement the exact Section 3 algorithm and run it with n = 2^{20}, prediction \\hat p_j = 2^{-j}/(1−2^{-n}), and true key at n/2. Count the number of comparisons until the key is found. The observed cost will be approximately 2^{11} = 2048, while log_2 η ≈ 20. Alternatively, analytically verify for this instance that at the iteration just before the target is found, D_i ≤ 2^{2k_i−1}, so the proof's key inequality fails. If the measured cost scales as Θ(√n) rather than O(log n), Theorem 1 is disproved.","verdict_should_be":"REJECT","load_bearing_attack":"The main upper bound (Theorem 1) is not merely missing a repair; the algorithm as described fails its claimed guarantee. Let n = 4^m, let the prediction be geometric, \\hat p_j ∝ 2^{-j} for j ∈ [n], and let the true distribution be a point mass at i = n/2. Then H(p) = 0 and the earth mover's distance η = Θ(n), so Theorem 1 promises O(log n) queries. But trace the Section 3 algorithm. In each bisection step, the median of the geometric distribution is the leftmost remaining index, because the mass at that index equals half the remaining mass. Thus the 2^t bisection steps of iteration t advance the left boundary by only 2^t positions. The endpoint phase of iteration t removes 2^{2t} positions from each side. Hence after K iterations the left boundary is ≈ 4^K/3, and the target is found only when 4^K/3 + 2^{2K} ≥ n/2, i.e. K ≈ log_4 n. The total cost is dominated by the last bisection phase, Σ_{t≤K} 2^t = Θ(2^K) = Θ(√n), contradicting O(log n). The proof's step '2^{2k_i−1} < D_i, which means that 2^{k_i} ≤ 2 log(D_i)' is doubly wrong: the endpoint probe at iteration k_i−1 uses distance 2^{2k_i−2}, not 2^{2k_i−1}, and even the weaker D_i > 2^{2k_i−2} only gives k_i < (log D_i + 2)/2, hence 2^{k_i} ≤ 2√D_i, not a logarithmic bound. The subsequent Jensen step therefore yields at best O(√η), not O(log η).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a model of binary search with distributional predictions, in which the algorithm receives a predicted distribution over key locations rather than a single point prediction, and the prediction error is measured by the earth mover's distance eta between the predicted and true distributions. The main claimed result (Theorem 1) is an algorithm that interleaves a distribution-median bisection phase with endpoint binary search and has expected query complexity O(H(p)+log eta), where H(p) is the entropy of the true distribution. The paper complements this with a lower bound Omega(H(p)+log eta) (Corollary 3), an extension to portfolios of predictions (Theorem 4), and synthetic and real-data experiments.","tokens_in":28,"tokens_out":11014,"duration_ms":215684,"significance":"The modeling contribution is attractive: distributional predictions are a natural generalization of point predictions, and the earth mover's distance is a well-motivated measure of prediction error in this geometric setting. The lower-bound component, based on Yao's principle and Mehlhorn's entropy lower bound, is coherent, and the experiments address a real data setup. However, the main upper bound is not established: the proof of Theorem 1 contains a concrete inequality error, and the proposed algorithm in fact fails the claimed guarantee on a simple instance. Since the advertised optimal tradeoff rests on this upper bound, the paper's central claim is unsupported as submitted.","major_comments":[{"comment":"The step 'Since a_i is not found before iteration k_i, we conclude that 2^{2k_i-1} < D_i, which means that 2^{k_i} <= 2 log(D_i)' is incorrect in two ways. The endpoint phase at iteration k_i-1 probes at distance d=2^{2(k_i-1)}=2^{2k_i-2}, so the correct inference is D_i > 2^{2k_i-2}; moreover, even from D_i > 2^{2k_i-2} one obtains 2^{k_i} = O(sqrt(D_i)), not O(log D_i). The subsequent Jensen step therefore bounds the I_2 cost by O(sqrt(eta)) rather than O(log eta), so the proof does not establish Theorem 1.","section":"Section 3.1, proof of Theorem 1"},{"comment":"The described algorithm fails the claimed bound on a concrete instance. Let n=4^m, let the predicted distribution be the geometric distribution p_hat_j proportional to 2^{-j} over [n], and let the true distribution be a point mass at i=n/2. Then H(p)=0 and eta=Theta(n), so Theorem 1 promises O(log n) queries. However, in every bisection step the median of the remaining geometric mass is the leftmost remaining index, so iteration t advances the left boundary by only 2^t bisection steps, while the endpoint phase removes 2^{2t} positions from each side; the target is reached only after K approximately log_4 n iterations, and the cost is dominated by the sum over t<=K of 2^t, which is Theta(2^K)=Theta(sqrt(n)). Thus Theorem 1 is false as stated for the proposed algorithm.","section":"Section 3, Theorem 1"},{"comment":"The portfolio analysis inherits the same invalid inference. Equations (1)-(5) use the relation 2^{T_i} <= 2 log(D_i), which fails by the same argument as in the proof of Theorem 1; hence Theorem 4 is not supported either. Because Corollary 3's optimality claim depends on the unproven upper bound, the claimed tight tradeoff is not established, although the Omega(log eta) component via Yao's principle and the cited lower bound appears sound.","section":"Appendix A, proof of Theorem 4"}],"minor_comments":[{"comment":"Figures 3 and 4 show only mean values for the real-data experiments; no error bars or other variance measures are reported, so statements such as '20-25% comparisons on average' lack a significance assessment.","section":"Section 5.2"},{"comment":"The experiments replace the analyzed parameter d=min(2^{2i}, r-l) with d=min(2^{8*2^i}, r-l), so the implemented variant is not the algorithm analyzed in Section 3; the later claim that the results 'validate the theory' is therefore overstated.","section":"Section 5"},{"comment":"The word 'erorr' should be 'error'.","section":"Section 5.1"},{"comment":"The entropy notation should state the standard convention that 0 log 0 = 0 for zero-probability keys.","section":"Section 3.1"},{"comment":"The quantification 'For any eta in [n]' should be stated more precisely as 'for every integer eta with 1 <= eta <= n'.","section":"Theorem 2"}],"recommendation":"reject","confidential_remarks":"The paper is clearly written and the modeling choices are appealing, but the main theorem is contradicted by the counterexample in Major Comment 2. Repairing this requires a substantially different algorithm and proof rather than a local correction, and the current manuscript therefore does not support its advertised optimality result. I recommend rejection despite the interest of the model and the soundness of the lower-bound component."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the main theorem is wrong. I traced the counterexample from the stress-test note and it holds. The algorithm's O(H(p) + log η) upper bound fails on a geometric prediction with a singleton true distribution at the median.\n\nWhat is genuinely new: the distributional-predictions model for binary search, the point-prediction impossibility in Section 2.1, the lower bound in Theorem 2, and the portfolio extension. The lower-bound reduction via Yao and Mehlhorn's external entropy bound is clean and likely correct. The experiments are honest and don't overclaim.\n\nThe problem is the proof of Theorem 1. The line '22k_i−1 < Di' is doubly wrong. In iteration k_i−1 the endpoint phase probes distance 2^{2k_i−2}, not 2^{2k_i−1}. And even with a corrected exponent, taking logs gives 2^{k_i} ≤ O(√Di), not O(log Di). So the Jensen step produces at best O(√η), not O(log η). This is not a repairable typo: the algorithm as written actually needs Θ(√n) queries on the geometric/singleton instance. The predicted mass sits at the left edge, so each bisection step removes only the leftmost remaining index. After K iterations the left boundary is about 4^K/3, and the target at n/2 is only reached when 4^K ≈ n, making the bisection cost Σ_{t≤K} 2^t = Θ(√n). With H(p)=0 and η=Θ(n), that contradicts the claimed O(log n).\n\nThe portfolio theorem inherits the same error, and the 'distributionally-robust optimal BST' equivalence is asserted, not developed. The experiments use normal distributions and don't test the geometric failure mode, so they don't reveal it.\n\nWho should read this? The model and the lower bound are worth knowing about; the algorithm as stated is not usable. The paper deserves referee attention because the model is natural and the flaw is subtle, but it is not publishable in current form. I'd recommend sending it to review with the expectation that the upper bound needs substantial rework—likely a different endpoint or interleaving strategy—before acceptance.","headline":"The main upper bound is false — the endpoint argument gives √η, not log η — but the model and the lower bound are worth a serious look.","tokens_in":15803,"tokens_out":7103,"would_cite":false,"duration_ms":59987,"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 predicted distribution, not a single point, can drive binary search to the query-optimal tradeoff $O(H(p)+\\log\\eta)$.","keywords":["distributional predictions","binary search","earth mover's distance","entropy","algorithms with predictions","optimal binary search tree","query complexity","lower bound"],"falsifier":"Look at the lower-bound construction: keys $1,\\dots,n$, true distribution a singleton at position $i$, predicted distribution uniform on $\\{1,\\dots,\\eta\\}$. If any comparison-based algorithm were found whose expected number of comparisons on this family is $o(\\log\\eta)$ for arbitrarily large $\\eta$, the claimed $\\Omega(\\log\\eta)$ bound would be false. On the upper-bound side, running the proposed algorithm on $n$ keys with $p=\\hat p$ uniform should give expected queries at most $4\\log n+O(1)$; measured query counts growing like $c\\log n$ with $c$ clearly above $4$ would indicate the analysis is off.","tokens_in":14706,"feed_emoji":"🔍","tokens_out":7550,"duration_ms":67053,"temperature":0.7,"pith_summary":"The paper asks what binary search can do when the prediction it receives is not a single array position but a whole distribution over positions, as modern machine-learning systems naturally output. It tries to establish that the right performance target is $O(H(p)+\\log\\eta)$: the entropy of the true query distribution plus the logarithm of the earth mover's distance between the true and predicted distributions. A reduction to any single point prediction is shown to fail on simple two-atom distributions, so the full distribution must be used. The paper gives an interleaved algorithm that alternates phases of median-of-predicted-distribution bisection with binary search at the endpoints of the remaining range, and proves this bound. It also proves a matching lower bound, showing the tradeoff between entropy and earth-mover error is optimal up to constants.","feed_headline":"Distributional predictions give optimal binary search up to constants","feed_subtitle":"Expected cost equals entropy of the true query distribution plus log earth-mover error; no algorithm can beat it.","key_machinery":"The load-bearing object is an interleaving of two classical search routines, executed in iterations $i=0,1,2,\\dots$. In the Bisection phase the algorithm spends $2^i$ comparisons probing the median of the predicted distribution restricted to the current range, halving the predicted mass each time; in the Endpoint-Binary-Search phase it probes distance $d=2^{2i}$ inward from both ends and, if the target is there, finishes with ordinary binary search on that small block. The proof's key accounting step is the observation that a key not found by iteration $k$ has left a predicted mass below $p_i/2$ inside the range, so the true distribution must transport at least $p_i/2$ mass across the distance $D_i$ from the key to the range boundary; summing these distances lower-bounds the earth mover's distance $\\eta$. Concavity of $\\log$ then converts the per-key distance sum into the $\\log\\eta$ term, while early-found keys are bounded by $p_i\\log(1/p_i)$ and hence by $H(p)$.","core_discovery":"On its own terms, the central discovery is that a predicted distribution can be exploited nearly as well as the true distribution, with graceful degradation as the prediction drifts. If the target key is drawn from $p$ and the algorithm is handed $\\hat p$, the interleaved algorithm has expected query complexity at most $4H(p)+8\\max(\\log(\\eta)+2,1)+8$, where $\\eta$ is the earth mover's distance between $p$ and $\\hat p$; this is $O(H(p)+\\log\\eta)$. The analysis splits keys: those found after at most $\\log\\log(4/p_i)$ iterations are charged to the entropy term, while keys that survive longer force at least $p_i/2$ probability mass to be moved across a distance $D_i$, so their cost is charged to $\\eta$ through Jensen's inequality. The matching lower bound uses an instance family in which the true distribution is a singleton at one of $\\eta$ positions and the prediction is uniform over those $\\eta$ positions; any comparison-based algorithm must pay $\\Omega(\\log\\eta)$ there, and combining this with the classical $\\Omega(H(p))$ lower bound for known distributions proves the tradeoff tight.","pith_inferences":["A natural editorial extension: any search structure that can be tuned to a distribution could use the same interleave-and-charge-to-EMD pattern, replacing the endpoint binary search with whatever worst-case fallback exists; the entropy-plus-transport-distance form may be a template for other algorithms with distributional predictions.","The lower-bound construction suggests the $\\log\\eta$ term is driven by long-range mass movement; if real predictors make only local errors, restricting the earth mover's distance to a bounded neighborhood might give better constants or a refined bound.","The algorithm's constants and the doubling schedule $d=2^{2i}$ are analysis artifacts rather than necessary design choices; the experiments already push $d$ to $2^{8\\cdot 2^i}$, so a data-dependent schedule could reduce practical overhead while preserving the asymptotic guarantee."],"forward_implications":["If the bound is right, no comparison-based search algorithm can make asymptotically better use of a distributional prediction: the $O(H(p)+\\log\\eta)$ tradeoff is optimal up to constant factors.","A possibly wrong predicted distribution can be turned into a binary search tree whose expected lookup time under the true distribution is $O(H(p)+\\log\\eta)$; this is described as the first optimal-BST result that tolerates a wrong input distribution.","Point-prediction reductions are ruled out: on a two-atom distribution with zero earth-mover error and entropy $1$, every choice of a single predicted location forces $\\Omega(\\log n)$ expected comparisons, so the distribution itself is necessary.","With $m$ predicted distributions the algorithm remains competitive with the best one, at an extra $O(\\log m)$ factor: $O(\\log m\\,(H(p)+\\min_k\\log\\eta_k))$.","In the paper's experiments on temporal network data, the learned search tree cuts comparison counts by 20-25% versus baselines on two datasets and degrades smoothly as $\\log\\eta$ grows."],"supporting_citations":[{"why":"Supplies the median-of-distribution bisection method the algorithm alternates with, and the known-distribution lower bound that the paper's lower bound imports.","marker":"[27]"},{"why":"Provides the point-prediction doubling binary search that the paper shows cannot be obtained by collapsing a predicted distribution to a point.","marker":"[28]"},{"why":"Introduces the bisection/median scheme on which the first phase of the interleaved algorithm is based.","marker":"[19]"}],"fun_headline_variants":["Distributional predictions make binary search optimal","Binary search hits entropy plus log earth-mover bound","Optimal binary search via predicted distributions","Distribution predictions: binary search's optimal error"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's optimality claim inherits the classical lower bound that a search strategy for a known distribution needs $\\Omega(H(p))$ comparisons; if that outside theorem, or its application to algorithms that are also given the predicted distribution, turned out to be false, the matching lower bound would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Distributional predictions make binary search optimal","Binary search hits entropy plus log earth-mover bound","Optimal binary search via predicted distributions","Distribution predictions: binary search's optimal error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000649,"raw_usage":{"total_tokens":3029,"prompt_tokens":1049,"completion_tokens":1980,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":665,"completion_tokens_details":{"reasoning_tokens":1934}},"tokens_in":665,"tokens_out":1980,"duration_ms":13545,"temperature":1.0,"reasoning_tokens":1934,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:38:52.086755+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Look at the lower-bound construction: keys $1,\\dots,n$, true distribution a singleton at position $i$, predicted distribution uniform on $\\{1,\\dots,\\eta\\}$. If any comparison-based algorithm were found whose expected number of comparisons on this family is $o(\\log\\eta)$ for arbitrarily large $\\eta$, the claimed $\\Omega(\\log\\eta)$ bound would be false. On the upper-bound side, running the proposed algorithm on $n$ keys with $p=\\hat p$ uniform should give expected queries at most $4\\log n+O(1)$; measured query counts growing like $c\\log n$ with $c$ clearly above $4$ would indicate the analysis is off.","supporting_citations":[{"cited_title":"Nearly optimal binary search trees.Acta Informatica, 5:287–295, 1975","cited_arxiv_id":null,"evidence_quote":"Supplies the median-of-distribution bisection method the algorithm alternates with, and the known-distribution lower bound that the paper's lower bound imports."}],"review_version":1}