{"id":"89694cfe-6ace-4446-9e7c-3a5b6bda4280","arxiv_id":"2607.16390","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":5,"one_line_summary":"In immutable open addressing, locality Ω(1/ε²) at some load is unavoidable, matching linear probing; with the final load known, Õ(1/ε) per-operation probes and locality are achievable.","lead":"Open-addressed hash tables that never move stored keys must, at some load, inspect cells at distance Ω(1/ε²) from the first probe — no immutable scheme can beat linear probing's locality. The result explains linear probing's practical dominance and pins down a page-size barrier in external-memory hashing.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly identifies the stateless first probe as the narrowest point; I agree it is necessary and that the proof is sound under it. I find no additional load-bearing concern: the transport lower bound is carefully proved, the convexity argument is correct, and the integration to the all-load bound is valid. The informal statements in the abstract and §1.1 omit the stateless-first-probe qualification, which is a presentational overreach rather than a technical flaw; the formal theorem in §4 is explicit. Hence the ACCEPT verdict stands unchanged.","tokens_in":24926,"tokens_out":26671,"duration_ms":231022,"concrete_test":"Run a Monte Carlo check of Lemma 3.5: fix n=10^5, ε=0.01, choose L=floor(a/ε²) with a=0.01, m=0.99n. For a point-mass distribution D and for the uniform D, estimate E[Σ_s (X_s-L)_+] by repeated sampling. Confirm the point-mass value is ≥ the uniform value; if the inequality reverses, the convexity/Jensen step in Lemma 3.5 is wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 4.1, proved via the amortized lower bound (Theorem 4.2) and the transport lower bound. I checked the three critical links: (i) Lemma 3.1's interval-overload lower bound is valid; (ii) Lemmas 3.4–3.5 correctly show the uniform distribution minimizes expected interval overload by convexity of g(p)=E[(Bin(m,p)-L)_+]; (iii) the hashing reduction correctly uses the stateless-first-probe assumption to make the hard keys' home locations i.i.d. from an arbitrary D, and the universe ω(n²) makes collisions o(1). The integration argument from Theorem 4.2 to Theorem 4.1 is sound. The only fragile point is the stateless-first-probe assumption in §4; without it the result fails, as a free-list algorithm can first-probe an empty cell. The paper explicitly states this is necessary, so the formal theorem is correct under its stated model. The informal abstract/§1.1 omit this qualification, which is a presentational overreach rather than a technical flaw.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces locality—the maximum geometric distance from the first probed cell to any cell inspected or used—as a complement to probe count for immutable (no-reordering) open-addressing hash tables. The main lower-bound results are: (1) an amortized Ω(1/ε) expected-locality lower bound for any sequence of (1−ε)n insertions, even when ε is known in advance, and (2) an all-load impossibility result stating that no scheme in the stated model can have expected insertion locality o(1/ε²) at every load 1−ε. The lower bounds are obtained from a distribution-free transport theorem (Section 3): i.i.d. home locations from any distribution on Z_n require Ω(n/ε) expected movement to distinct cells. Section 4 reduces the hashing problem to this transport statement and derives an external-memory page-size consequence. The upper-bound half proves a variance lemma for symmetric greedy probing schemes (Section 5), gives a load-oblivious greedy scheme with expected O(1/ε) probes and quadratic probe-distance growth, and gives a multilevel deamortized construction with E[T], E[R] = O(ε^{-1} log³(1/ε)) when the final load is known in advance (Section 6). The paper is candid about open problems, including the gap between first-moment probe bounds and expected locality.","tokens_in":25188,"tokens_out":28782,"duration_ms":237685,"significance":"If the formal theorems are taken as stated, this is a substantial contribution. The lower bound gives a clean, self-contained explanation of why linear probing's quadratic locality profile is optimal among immutable schemes, despite the recent probe-count improvements for no-reordering tables; it also provides a geometric justification for the classical B = Ω(1/ε²) page-size threshold. The proof chain is elegant: the interval-overload inequality, the convexity argument showing that the uniform distribution minimizes expected interval overload, and the hashing reduction are all sound. The variance lemma for symmetric probing schemes is a robust and potentially reusable structural statement. The paper is also appropriately candid about its limitations, explicitly noting the necessity of the stateless-first-probe assumption and the failure of the load-oblivious upper bound to yield an expected-locality guarantee. No fitted parameters or circular benchmarks are involved. Provided the advertised statements are qualified to match the formal model, this is a valuable paper.","major_comments":[{"comment":"The advertised no-subquadratic-locality theorem is stated more strongly than the formal result. Theorem 4.1 requires both (a) the stateless-first-probe assumption and (b) the profile f to be locally bounded. Section 4 explicitly notes that (a) is necessary: without it, a free-list scheme can first-probe an empty cell, so the abstract's unqualified sentence is false. Assumption (b) is also used essentially in the proof of Theorem 4.1: if f is allowed to be unbounded on a fixed interval [δ0,1], the O(n) insertions at non-small loads cannot be controlled by M0 n, and the integration argument does not go through. Please qualify the abstract and informal theorems so that they match the formal statement and the model.","section":"Abstract / §1.1 / Theorem 4.1"}],"minor_comments":[{"comment":"The claimed O(ε^{-2} log n) bound for 'any fixed sequence of shifts' is not justified as written when the first k shifts contain duplicates. The proof treats S_k as a set of size k, but if the shifts are not distinct then |S_k| < k, the equality E[|E_t ∩ (h+S_k)|] = εk fails, and the tail probability O(1/(ε²k)) need not hold for a degenerate sequence that repeatedly probes the same cell. Restrict to sequences whose first k probes are distinct, or replace k by |S_k| and adjust the summation.","section":"Remark 5.3"},{"comment":"The sentence 'in all cache-oblivious schemes' overstates the scope. The result is a lower bound for immutable open addressing with stateless first probe, not for the standard cache-oblivious model. The relation between locality R and page span R/B is also an inequality, not an equality; the proof is clear, but the wording should be aligned with the formal model.","section":"Theorem 4.3 / §4.1"},{"comment":"The definition of symmetric greedy mechanisms states that the whole probe sequence is sampled before insertion, while Algorithm 1 is described lazily, sampling phase by phase. These are equivalent, but this equivalence should be stated explicitly to avoid confusion about adaptivity.","section":"§2.2 and Algorithm 1"},{"comment":"The construction assumes that all block sizes divide the table exactly ('assume for simplicity'). Since the results are asymptotic, this is likely harmless, but the rounding details should be acknowledged or deferred to a full version so that the proof is complete for arbitrary n.","section":"Section 6"}],"recommendation":"minor_revision","confidential_remarks":"The formal results appear sound and the paper is a strong fit for the journal. My main concern is presentational: the abstract and Section 1.1 state the main theorem in a form that is false without the stateless-first-probe assumption and stronger than what is proved regarding locally bounded profiles. Once these qualifications are added, I would be happy to see the paper accepted. I do not see grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper actually resolves a question people have been circling for years. It defines locality (geometric distance from first probe to farthest cell) as a parameter separate from probe count, proves an Ω(1/ε²) all-load lower bound, an amortized Ω(1/ε) lower bound even when the final load is known, an external-memory consequence B = Ω(1/ε²), and matches them with upper bounds: a known-load construction with Õ(1/ε) per operation and a load-oblivious greedy scheme with O(1/ε) probes and quadratic distance growth. If the proofs are right, linear probing's quadratic locality is not a defect but an inherent limit of immutable open addressing.\n\nWhat's genuinely new: the transport lower bound is a clean reduction of hashing to one-dimensional optimal transport, and the convexity argument showing the uniform distribution minimizes interval overload is elegant. The variance bound Var(|O_t ∩ S|) ≤ |S| for symmetric probing is a robust and surprising pseudorandomness statement. The multilevel known-load construction is intricate but detailed. I checked the three critical links flagged in the stress-test—the interval-overload inequality, the binomial convexity, and the hashing reduction—and they hold. No fitted parameters, no self-verification loops; constants are existence constants.\n\nThe real soft spot is the mismatch between the abstract/informal theorems and the formal statement. Theorem 4.1 requires the first probe to depend only on the key and initialization, not on previously inserted elements. That assumption is necessary—a free-list algorithm would trivially beat the bound—and the paper states it explicitly in §4. But the abstract and §1.1 say 'no open-addressing algorithm without reordering' without that qualification. That's a presentational overreach, not a technical flaw.\n\nTwo smaller things worth a referee's eye. First, the proof of Lemma 5.1 uses a 'conditional on existing, each swap cell is uniform' step; I think it's right by translation invariance, but it deserves a careful read. Second, Section 6 is dense; the biased minimum-allocation lemma and the top-block overload estimate look sound, but this is where a subtle bug would hide. The paper's own open problems are honestly stated—notably that the load-oblivious scheme does not yet give expected-locality O(1/ε²), only high-probability.\n\nThis is a strong theory paper. It will be useful to anyone working on hash tables, cache-oblivious data structures, or lower-bound techniques based on transport. I would bring it to a reading group and I would cite it. The right outcome is peer review with minor revision: align the informal statements with the formal model and let a careful referee check Section 6. Verdict: accept.","headline":"A genuinely new and mostly rigorous paper: it introduces locality as a formal parameter for immutable open addressing, proves tight lower bounds and matching upper bounds, and explains linear probing's practical edge—but the abstract slightly overstates the formal result by omitting the stateless first-probe assumption.","tokens_in":25664,"tokens_out":2104,"would_cite":true,"duration_ms":19752,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P05","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that no open-addressing hash table without reordering can achieve expected insertion locality better than Θ(1/ε²) at every load 1−ε, matching the locality profile of linear probing.","keywords":["locality","open addressing","hash tables without reordering","linear probing","optimal transport lower bound","variance concentration","external memory page size","greedy probing schemes"],"falsifier":"Exhibit any open-addressing scheme without reordering whose first probe is stateless and whose expected insertion locality at load 1−ε is o(ε^{-2}) at every load; even a single such scheme with ε→0 would refute Theorem 4.1. Concretely, simulate any candidate on a cycle with nε²≫1 and measure expected locality for a sequence ε→0 (e.g., ε = n^{-1/4}, n^{-1/3}, n^{-1/2}) to see if it grows slower than ε^{-2}. A cheaper check: numerically compute the optimal transport cost for i.i.d. uniform points on a cycle of size n and verify that it is Ω(n/ε) as ε→0.","tokens_in":24796,"feed_emoji":"📏","tokens_out":6236,"duration_ms":51419,"temperature":0.7,"pith_summary":"The paper introduces a new performance measure for open-addressed hash tables: locality, the geometric distance between the first probed cell and the farthest cell inspected during an operation. It proves a lower bound: in any scheme that never reorders keys, and whose first probe for a key depends only on the key and the table initialization, the expected insertion locality at load 1−ε cannot be o(1/ε²) at every load. This makes linear probing's quadratic locality profile optimal among immutable schemes. It also proves an amortized lower bound of Ω(1/ε) over a full insertion sequence, and derives a necessary page size Ω(1/ε²) for 1+o(1) page span in external memory. Two upper bounds show the lower bounds are nearly tight: with the target load known in advance, every insertion and search can achieve expected cost Õ(1/ε); without that knowledge, a greedy expanding-window scheme achieves optimal expected probe count with quadratic distance growth.","feed_headline":"Locality hits a quadratic ceiling in immutable hash tables","feed_subtitle":"Without reordering, every open-addressing scheme pays the same geometric cost as linear probing at high load.","key_machinery":"The load-bearing object is a one-dimensional optimal-transport lower bound (Section 3): for m=(1−ε)n i.i.d. home locations from any distribution on the cycle, the minimum expected total movement to reach distinct cells is Ω(n/ε). It is proved by an interval-overload argument — intervals of length Θ(1/ε²) overflow by Θ(1/ε) particles in expectation — plus a convexity argument showing the uniform distribution minimizes this overload. Section 4 converts this into hashing bounds via the stateless-first-probe assumption. The upper bounds rest on a variance lemma (Lemma 5.1): in any symmetric greedy scheme, Var(|O_t∩I|) ≤ |I| for every fixed set I, proved through Efron–Stein's inequality and a swa","core_discovery":"The central discovery is that locality, not probe count, is the quantity that resists improvement in immutable open addressing. The proof works by reducing hashing to a one-dimensional optimal transport problem: after inserting (1−ε)n random keys, their first-probe locations form i.i.d. points from an arbitrary distribution on the cyclic table, and any distinct final placement must move these points a total expected distance of Ω(n/ε). Since each key's locality radius is at least its displacement, the amortized lower bound follows; an integration argument upgrades it to the all-load o(1/ε²) impossibility. The paper matches these bounds with a variance lemma showing that the occupied set of a","pith_inferences":["One testable corollary of the transport lower bound is that any immutable scheme's locality profile is determined almost entirely by the geometry of final placement, not by the probing rule; a scheme that keeps keys hyperlocal after placement could in principle escape the lower bound, but the stateless-first-probe assumption blocks exactly such adaptations.","The variance lemma suggests occupied sets in symmetric probing behave like independent Bernoulli cells to first order; a natural next step would be to ask whether higher moments obey similar bounds, which would resolve the open expected-locality question for the expanding-window sampler.","In database and cache settings where the target load is rarely known in advance, the all-load lower bound implies that the choice between linear probing and uniform probing is a genuine tradeoff with no free lunch — only knowing ε in advance or allowing reordering/rebuilding changes the picture.","The paper's lower bound applies to all no-reordering algorithms, greedy or not; so the open question it leaves is whether non-greedy placement can cut probe count while preserving the quadratic locality — a search space the transport argument does not constrain."],"forward_implications":["If the main lower bound is right, linear probing's Θ(1/ε²) expected insertion locality cannot be improved by any no-reordering scheme, so practical gains in probe count must come from non-greedy placement or from knowing the target load.","The page-size consequence means immutable external-memory hash tables need B=Ω(1/ε²) to achieve 1+o(1) expected page accesses per operation; the quadratic block-size barrier for space-efficient hashing without reordering is not an artifact of construction.","With the target load known in advance, the Õ(1/ε) construction shows the amortized lower bound is essentially tight and can be deamortized: every insertion and search pays the same expected cost.","The variance lemma extends to all symmetric probing schemes: any fixed-shift or random-shift symmetric scheme has expected probe count O(log n/ε²) at every load, a weak but all-load uniform guarantee.","Without knowing the load, the expanding-window greedy scheme simultaneously achieves the optimal Θ(1/ε) expected probe count and a quadratic distance profile, giving locality O(1/ε²) with high constant probability — though expected locality at that scale remains open."],"fun_headline_variants":["Locality in hash tables hits a quadratic wall","No reordering: locality cannot beat quadratic cost","Probe count isn't the only bottleneck: locality is","Hashing's hidden cost: geometric locality is quadratic","Immutable open addressing pays quadratic in locality"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The first probed cell for a key depends only on the key and the table's initialization, never on the keys already inserted; if an algorithm could point its first probe at a currently empty or lightly loaded region, the transport lower bound would not apply.","fun_headline_variants_meta":{"raw":{"variants":["Locality in hash tables hits a quadratic wall","No reordering: locality cannot beat quadratic cost","Probe count isn't the only bottleneck: locality is","Hashing's hidden cost: geometric locality is quadratic","Immutable open addressing pays quadratic in locality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000191,"raw_usage":{"total_tokens":1241,"prompt_tokens":867,"completion_tokens":374,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":315}},"tokens_in":611,"tokens_out":374,"duration_ms":3933,"temperature":1.0,"reasoning_tokens":315,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T21:08:22.684765+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit any open-addressing scheme without reordering whose first probe is stateless and whose expected insertion locality at load 1−ε is o(ε^{-2}) at every load; even a single such scheme with ε→0 would refute Theorem 4.1. Concretely, simulate any candidate on a cycle with nε²≫1 and measure expected locality for a sequence ε→0 (e.g., ε = n^{-1/4}, n^{-1/3}, n^{-1/2}) to see if it grows slower than ε^{-2}. A cheaper check: numerically compute the optimal transport cost for i.i.d. uniform points on a cycle of size n and verify that it is Ω(n/ε) as ε→0.","supporting_citations":[],"review_version":1}