{"id":"238a8f73-9dc6-4279-9251-25bf5c86a40b","arxiv_id":"2607.17494","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"At load factor 1−1/x, a layered non-greedy insertion strategy cuts worst-case expected insertion time for stable linear probing from Θ(x^2) to O(x log x).","lead":"Standard greedy linear probing takes Θ(x^2) expected time per insertion when a hash table is filled to within 1/x of capacity. This note describes a non-greedy insertion rule that skips some free slots and reduces worst-case expected insertion time to O(x log x), without ever moving placed elements.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's O(x log x) bound is proven only when n is a power of two; the one-sentence assertion that 'careful rounding' extends it to arbitrary n is unsupported and the layer geometry depends on exact powers of two.","rationale":"I read the paper carefully, focusing on the proof of Theorem 1. For n a power of two, the argument appears internally consistent: the layer partition is well-defined, the routing probabilities yield the expected-cost tradeoff, the overflow bound relies only on independent geometric variables, and the failure probability is indeed o(1/n^2) under x = o(n/log^2 n). The main gap is that the theorem is stated for arbitrary n, while the proof is explicitly for powers of two. The single sentence in Section 2 asserting that 'careful rounding' handles general n is not a proof, and the analysis uses exact identities (N_i = n/2^i, s_i N_i = n) that can be perturbed by rounding. This directly affects the central claim, not just a peripheral remark. The reader's weakest assumption captures exactly this. I also considered the unsupported claim about positive queries in the introduction, but that is not needed for Theorem 1, which concerns insertions only; the arbitrary-n issue is load-bearing for the stated theorem. Thus the reader's CONDITIONAL verdict is appropriate: the paper should be accepted only if the rounding is supplied or the theorem is restricted to n = 2^k.","tokens_in":5766,"tokens_out":21008,"duration_ms":165987,"concrete_test":"Analytic check: fix n = 2^k + 1 and a concrete rounding, e.g., let L_i consist of slots with index congruent to 2^{i-1} mod 2^i for i ≤ k−1, and put the remaining slots into L_k. Re-derive (a) the correctness sum Σ min(|L_i|, (s_i/bx)|L_i|) with s_i the true stride in each L_i, and (b) the distribution of the first L_i slot hit by a uniform h(u). Verify that the sum is ≤ n/x + o(n/x) and that the first-hit slot is within O(1) of uniform, so the Θ(s_i/δ_i^2) cost bound and Claim 1 still hold. If either fails, Theorem 1 must be restated with n a power of two (or the rounding supplied).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1) is stated for arbitrary n, but the proof repeatedly relies on n being a power of two. In Section 2 the table is partitioned into layers L_i with |L_i| = N_i = n/2^i and slots spaced s_i = 2^i apart; these quantities are exact only for n = 2^k. The correctness argument sums min(N_i, (s_i/bx)N_i) = min(n/2^i, n/bx), and the analysis of Claim 1 uses s_i N_i = n, p_min = λ s_i/bx, and the uniformity of the first L_i slot reached by h(u). All of these break under rounding: layer sizes cannot all be n/2^i for arbitrary n, s_i N_i = n fails, and the first L_i slot is not necessarily uniform if the stride partition is irregular. The paper's only justification is the sentence 'with careful rounding, all of the same arguments also apply for arbitrary n' (Section 2); no rounding is specified and no lemma verifies that the two key bounds (total free slots ≤ n/x and the overflow bound of Claim 1) survive. Since Theorem 1 as stated covers all n, this is a load-bearing gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a non-greedy insertion strategy for linear probing. The table is partitioned into dyadic layers; in each phase i, a new key is sent to the active layer L_i with probability pi = min(1, λ bx δ_i^2/s_i) and otherwise to the overflow layer L_{i+1}. The analysis shows that with high probability the overflow layer stays at most half full, and the expected insertion cost is O(bx) = O(x log x), provided x = o(n/log^2 n). Theorem 1 states this worst-case expected-time bound for each of the first (1−1/x)n insertions. The proof uses a Chernoff bound for the overflow count and a direct expected-cost calculation.","tokens_in":6131,"tokens_out":32968,"duration_ms":283903,"significance":"If the result holds for all n, it is the first stable (no-reordering), unidirectional linear-probing insertion scheme with sub-Θ(x^2) worst-case expected insertion time, improving to O(x log x). The algorithm is simple and the proof is direct, with explicit inequalities and no hidden fitting of constants; the main technical work is a clean geometric argument controlling overflow between layers. The principal caveat is that the proof as written covers only n a power of two, despite the theorem's general statement, so the significance for arbitrary n is conditional.","major_comments":[{"comment":"Theorem 1 is stated for arbitrary n, but the proof uses exact power-of-two structure: N_i = n/2^i, s_i N_i = n, and the uniformity of the first L_i slot reached by h(u). These are used in the correctness sum and in Claim 1 (p_min = λs/bx, θN = Ω(n/bx)). The only justification for general n is the sentence 'with careful rounding, all of the same arguments also apply for arbitrary n' (Section 2); no rounding is specified and no lemma verifies that the total-free-slot bound and the overflow bound survive. Since Theorem 1 covers all n, this is a load-bearing gap. Either prove the rounding or restrict the theorem to powers of two.","section":"Section 2 and Theorem 1"}],"minor_comments":[{"comment":"The claim that the structure supports 'positive queries' needs a query-algorithm specification. Because non-greedy insertions can leave free slots before an inserted key, the standard linear-probing query (stop at first empty slot) may fail to find a present key. The authors should clarify that positive queries require scanning past empty slots and that negative queries are not supported under the usual semantics.","section":"Section 1"},{"comment":"The proof writes sums over all r ≥ δ*_i N as if 1/p_r equals sN^2/(λbxr^2) for every r, but for r with p_r = 1 that equality fails. The argument is valid if the sums are understood to range only over r with p_r < 1; please state this explicitly.","section":"Claim 1"},{"comment":"The constants C0 and λ are introduced as 'sufficiently large' without explicit values. Since the theorem is asymptotic and uses these constants in thresholds (e.g., the split in the correctness sum and the choice of λ in Claim 1), it would improve reproducibility to state how large they need to be, or at least to make the existence claim precise.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The main proof is sound for n a power of two, and the gap for arbitrary n is likely fixable with a careful rounding argument or by restricting the theorem. The positive-query issue should be addressed. The paper is otherwise clear and the result is significant."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading. The note delivers a real improvement: a stable (no-reordering) linear-probing insertion method with worst-case expected O(x log x) time at load 1 − 1/x, beating the classic Θ(x²) and the concurrent bidirectional O(x log³ x) result. The layered-interleaving idea is the right kind of simple: split the table into dyadic layers, route to the active layer with probability proportional to δ_i²/s_i, and keep the overflow layer sparse by letting that probability vanish as the active layer fills. The expected-cost calculation is clean: the active-layer term cancels to O(bx), and the overflow layer is at most half full with high probability, so its contribution is O(s_{i+1}) = O(x log x).\n\nThe proof of Claim 1 (overflow-count concentration) checks out. The geometric-variable decomposition is valid, the sum of 1/p_r is computed correctly, and the final exponent is indeed −Ω(n/bx), which is well below 1/n² under x = o(n/log² n). The correctness bound on total free slots also works for dyadic layers.\n\nSoft spots, in order of seriousness. First, Theorem 1 is stated for arbitrary n, but the proof only works for n a power of two. The sentence in Section 2 about \"careful rounding\" is not a proof: layer sizes |L_i| = n/2^i, the identity s_i N_i = n, and the uniformity of the first L_i slot reached by h(u) all depend on exact powers of two. That is a load-bearing gap for the general-n claim, even if it is likely fixable. Second, the abstract says the structure supports positive queries, but no query operation is ever specified. Standard linear probing lookup would terminate at an empty slot before finding a key that was inserted non-greedily later in the probe order. This is a genuine omission. Third, the abstract omits the side condition x = o(n/log² n), which could easily mislead a casual reader.\n\nNone of this undermines the main contribution for power-of-two n. The flaws are repair items, not structural ones. The paper is short, but it deserves a serious referee—one who will request the rounding details and a query definition, and will likely then clear it.","headline":"A genuinely new O(x log x) stable linear-probing insertion strategy whose core proof is sound for power-of-two n; the arbitrary-n extension and the positive-query claim are asserted, not shown.","tokens_in":6585,"tokens_out":9131,"would_cite":true,"duration_ms":77477,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P05","68W20","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a simple non-greedy insertion rule — skip free slots to reserve them for later keys — reduces the worst-case expected insertion time of stable linear probing from Θ(x²) to O(x log x).","keywords":["linear probing","non-greedy insertion","stable hash table","open addressing","worst-case expected time","clustering","layered insertion","random hashing"],"falsifier":"Choose an n that is not a power of two, set x near the largest value satisfying x = o(n/log² n), and simulate the algorithm with a fully random hash, recording the maximum expected insertion time over the first (1−1/x)n insertions. If that maximum grows like x² rather than x log x, the theorem as stated is false.","tokens_in":5700,"feed_emoji":"⚡","tokens_out":6784,"duration_ms":60855,"temperature":0.7,"pith_summary":"Classical linear probing inserts each key into the first free slot after its hash; at load factor 1−1/x this greedy rule makes worst-case expected insertion time Θ(x²). This paper proves that a simple non-greedy rule — sometimes skip a free slot and keep probing, reserving that slot for later keys — cuts the worst-case expected insertion time to O(x log x), with no element ever moved after placement. The construction fixes the target load x in advance, partitions the circular table into geometrically spaced layers, and routes each insertion probabilistically between the current layer and an overflow layer. If correct, this is the first stable, unidirectional linear-probing scheme to beat quadratic worst-case insertions, and it brings positive queries to the same bound as a byproduct.","feed_headline":"Skipping free slots speeds hash inserts from x^2 to x log x","feed_subtitle":"No element moves after insertion, yet worst-case expected insertion time at load 1−1/x drops to O(x log x).","key_machinery":"The load-bearing object is the layer partition L_i of one slot every 2^i positions, together with the probabilistic routing rule p_i(δ_i) = min(1, λ x log(2x) δ_i² / 2^i). The layer spacing s_i = 2^i converts the expected number of probes in a layer, Θ(δ_i^{−2}), into a physical cost Θ(s_i/δ_i²); the routing probability is chosen so that cost times probability is Θ(x log x). The companion guarantee is Claim 1: with high probability the overflow layer L_{i+1} receives fewer than half its slots during phase i, which keeps overflow insertions cheap. The definition b(x) = C_0 x log(2x) sets the phase-ending threshold δ_i^* = s_i / b(x), and the correctness argument sums min(n/2^i, n/b(x)) over l","core_discovery":"The central claim is Theorem 1: assuming a fully random hash function and x = o(n/log² n), each of the first (1−1/x)n insertions into an n-slot circular table completes in worst-case expected O(x log x) time under the Interleaved Layered Insert algorithm. The algorithm divides the table into layers L_i, where L_i contains every 2^i-th slot, and during phase i routes a new key to active layer L_i with probability min(1, λ x log(2x) δ_i² / 2^i), where δ_i is the current empty fraction of L_i; otherwise it routes to the overflow layer L_{i+1}. By keeping L_{i+1} less than half full with high probability, the expected cost of an overflow insertion is O(2^i) = O(x log x), while the expected cost","pith_inferences":["If the n-power-of-two restriction is not merely cosmetic, the theorem as stated overreaches: the Section 2 assertion that 'careful rounding' handles arbitrary n is not accompanied by a proof, and the layer geometry (one slot every 2^i positions) is what makes the uniformity argument work.","A concrete next experiment is to run the algorithm with n not a power of two and measure whether the worst-case expected insertion time tracks O(x log x) or reverts to Θ(x²); this would test the missing rounding rather than the core idea.","The parameter x is an input; extending the scheme to adaptively learn x from the arrival stream, or to handle a range of loads, is the obvious practical next step.","The skip-to-reserve mechanism suggests a broader design principle: sparse reserved slots can absorb overflow without moving keys, which may transfer to other open-addressing variants such as bidirectional probing or cuckoo-style tables with stability constraints."],"forward_implications":["If Theorem 1 is right, insertion-only stable linear probing reaches O(x log x) worst-case expected insertion time at load 1−1/x, the first sub-Θ(x²) bound of its kind.","Because elements never move and probing is in one direction, the same O(x log x) bound applies to queries for keys already inserted.","The result separates the cost of clustering from the cost of stability: avoiding reordering no longer forces quadratic worst-case insertions.","The near-full-table regime changes from infeasible to nearly linear: a table planned for target load can stop at 1−1/x with per-insertion cost O(x log x).","The analysis leaves open whether the extra log factor can be removed; the O(x) target remains unresolved."],"fun_headline_variants":["Non-greedy insertion improves hash worst-case to O(x log x)","Layered non-greedy probing: worst-case insert drops to x log x","Skipping free slots: hash insertions in O(x log x) worst-case","Non-greedy linear probing: faster worst-case without reordering"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The clean geometry of the proof requires n to be a power of two; the paper states without proof that rounding extends the result to arbitrary n, so for general n the O(x log x) insertion bound is not actually established.","fun_headline_variants_meta":{"raw":{"variants":["Non-greedy insertion improves hash worst-case to O(x log x)","Layered non-greedy probing: worst-case insert drops to x log x","Skipping free slots: hash insertions in O(x log x) worst-case","Non-greedy linear probing: faster worst-case without reordering"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000309,"raw_usage":{"total_tokens":1578,"prompt_tokens":698,"completion_tokens":880,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":442,"completion_tokens_details":{"reasoning_tokens":797}},"tokens_in":442,"tokens_out":880,"duration_ms":7173,"temperature":1.0,"reasoning_tokens":797,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T17:51:22.486079+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose an n that is not a power of two, set x near the largest value satisfying x = o(n/log² n), and simulate the algorithm with a fully random hash, recording the maximum expected insertion time over the first (1−1/x)n insertions. If that maximum grows like x² rather than x log x, the theorem as stated is false.","supporting_citations":[],"review_version":1}