{"id":"04955ce2-4dc2-4093-b609-3d753396c117","arxiv_id":"2607.28892","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Two practical hash-table designs—Chained-TPHT and Flattened-TPHT—use byte-sized pointers and key quotienting to reach 105.4% and 83.4% space efficiency with constant-time operations and high throughput.","lead":"Hash tables usually trade memory for speed. This paper builds two hash tables that compress pointers to one byte and shrink stored keys, achieving one variant that uses less memory than the raw key-value data (105.4% space efficiency) and another that runs up to 89.3% faster than strong baselines while still saving memory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Dereference-table capacity test may not use address-derived IDs; 98.2% load factor (and the <data-size footprint) is unvalidated for the actual ID distribution used in Chained-TPHT.","rationale":"The central claim is that Chained-TPHT is a practical succinct hash table with footprint below raw data size. This claim concretely rests on the dereference table's ability to sustain ~98.2% load without allocation failure (Section 5.3 formula). The reader's weakest assumption identified exactly this: the dereference table's failure rate is tested with random keys, not with the address-derived IDs the design mandates. I agree. The concern is not that the power-of-two-choice scheme is flawed in general, but that the paper provides no evidence that it remains failure-free at 98.2% load for the specific ID distribution created by using pointer-field addresses as IDs. This distribution has structure (consecutive head-array addresses; slot-spaced p-field addresses) that could in principle bias the two hash functions, weakening the balancing. The paper's Section 8.6 description is ambiguous about whether the test uses the real ID sequence; if it uses random 64-bit IDs, the headline claim is unvalidated for the actual implementation. The suggested test settles this by replaying real ID logs. Other issues (no PaCHash comparison, no error bars, wrong concentration statement) are secondary and do not directly threaten the correctness of the space-efficiency claim. Thus the verdict remains CONDITIONAL, as the reader said, pending this specific validation.","tokens_in":27613,"tokens_out":20241,"duration_ms":209343,"concrete_test":"Re-run the Section 8.6 dereference-table capacity experiment using the actual ID sequences produced by Chained-TPHT: instrument the implementation to log every Allocate/Free ID (the address of the pointer field) during the YCSB and microbenchmark workloads in Section 8, then replay these exact ID sequences in a standalone dereference table initialized at 98.2% load and measure whether any allocation fails. Additionally, run the same replay under adversarial workloads (sequential keys, low/high Hamming-weight keys, churn with high deletion rate) to confirm the 98.2%/95% load factors hold for address-derived IDs. If failure occurs, the stated space efficiency (105.4%) is not workload-robust.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Chained-TPHT's space-efficiency claim (Section 5.3) and the headline 'footprint less than the total data size' rely on the dereference table operating at load factor 1−δ with δ≈2%. Section 8.6 reports that the dereference table supports 98.2% load (insertion-only) and 95% (with deletions), but the experiment is described as performing 'random insertions' and 'random insertions and deletions' without stating the ID distribution. In Chained-TPHT, IDs are the in-memory addresses of the tiny-pointer fields (Section 3.3): head-array entries are consecutive byte addresses, and node p-fields are spaced by slot size in the data table. These addresses are not i.i.d. random values—they are an artifact of the allocation history. If h0,h1 do not hash this structured address set to bins with sufficient independence, the power-of-two-choice balancing can degrade, and Allocate can fail at a lower load factor. On failure, the table returns an error (Section 7.2), voiding the space-efficiency and O(1)-time guarantees for that workload. The paper offers no analysis of the address-ID distribution and no adversarial key/history test. This is the load-bearing link between the practical design and the claimed succinctness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents Tiny Pointer Hash Tables (TPHT), two hash-table designs that combine tiny pointers (implemented via a dereference table) with one-round Feistel quotienting. Chained-TPHT targets maximal space efficiency and is claimed to be the first simple, practical succinct hash table, with footprint below the raw data size while supporting O(1) expected-time operations. Flattened-TPHT targets latency by using cache-line-sized home blocks and SIMD-accelerated fingerprint checks. Both support concurrency, deletions, and resizing. The evaluation uses YCSB and microbenchmarks against general and compact baselines, reporting that Chained-TPHT achieves 105.4% space efficiency and Flattened-TPHT achieves 83.4% space efficiency while improving throughput. The theoretical space analysis in Section 5.3 derives a formula approaching the information-theoretic lower bound in the regime w=O(log n).","tokens_in":27949,"tokens_out":15480,"duration_ms":169088,"significance":"If the central claims are correct, this is a significant advance: it would demonstrate that succinct hash tables with constant-time operations can be practical, and that a hash table can store 64-bit key-value pairs in less memory than the raw pairs occupy. The paper ships source code, uses a broad set of baselines, and gives explicit space formulas tied to an information-theoretic lower bound. The main risk is that the space-efficiency claims depend on the dereference table achieving a 98.2% load factor under the specific ID distribution used in the actual hash table (the address of the tiny-pointer field). The paper's capacity test in Section 8.6 does not clearly establish this. A second, more localized issue is a numerical error in the failure-rate analysis in Section 6.4. Both are fixable with additional experiments/analysis; the overall design is plausible and the empirical scope is substantial.","major_comments":[{"comment":"The load-bearing space claim rests on the dereference table operating at load factor 1−δ with δ≈2%, but Section 8.6 does not validate this for the actual ID distribution used by Chained-TPHT. In Sections 3.3 and 5.1, the ID k passed to Allocate/Dereference is the in-memory address of the tiny-pointer field that references the node. These IDs are not i.i.d. random: head-array IDs are consecutive byte addresses, and node p-field IDs are spaced by the slot size and depend on the entire prior allocation history through the two-choice process. The capacity experiment in Section 8.6 is described only as 'random insertions' and 'alternating random insertions and deletions' without stating what IDs were used. If those experiments used random IDs rather than the address-derived IDs, the reported 98.2%/95% load factors do not transfer to the real system. This matters directly for Section 5.3: with","section":"Sections 3.3, 5.1, 8.6"},{"comment":"The numerical assertion that the Azuma deviation is 'below 1% of the dataset size' for n≥10^5 is arithmetically incorrect. With λ=2√(2n ln n), for n=10^5 we have λ≈3035, which is about 3% of n; for n=10^6, λ≈10500, still above 1% of n. The threshold should be around n≳1.1×10^6. This affects the statement that the dereference table for Flattened-TPHT is 'conservatively sized' at the indicated dataset sizes. Please correct the threshold or the claimed deviation, and adjust any sizing guidance that relies on it.","section":"Section 6.4, Claim 4"}],"minor_comments":[{"comment":"The caption says 'Meta table (2n bytes)', but with bins of 2^7−1 slots and a data table of ≈n entries, the meta table should be 2(n/127) bytes = 16n/127 bits, matching the formula in Section 5.3. Please correct the inconsistency.","section":"Section 3.2"},{"comment":"The probability statement is reversed. If 2^ℓ ≥ n, then n/2^ℓ ≤ 1 and 1−e^{−n/2^ℓ} ≤ 1−e^{−1} ≈ 63.2%, not ≥ 63.2%. Rephrase to say that the probability a lookup finds a singleton chain is at most this value, or adjust the condition to 2^ℓ = n for the claimed lower bound.","section":"Section 5.2"},{"comment":"The claim that the indicators X_i^(b) are negatively associated is asserted without proof, with a general citation [94] rather than a derivation for the Feistel-constructed family. Since this underlies the theoretical max-load bound, a short justification or a more specific reference would strengthen the claim. The empirical results in Section 8.7 provide some practical support.","section":"Section 4.1, Claim 2"},{"comment":"Throughput numbers are reported as single-point measurements without error bars or repeated-run statistics. Given the precise percentage comparisons (e.g., 89.3% higher throughput), reporting variance or at least multiple runs would make the empirical claims more robust.","section":"Section 8"}],"recommendation":"major_revision","confidential_remarks":"The artifact and code availability are a strength, as is the breadth of the benchmark suite. The principal risk is the dereference-table load factor under the address-derived ID distribution; if the authors can provide the targeted experiment, I would view the core claims as substantially supported. The numerical error in Section 6.4 is local and easily corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. TPHT is the first hash table I've seen that convincingly turns tiny-pointer theory into a working structure with >100% space efficiency and competitive speed. The two designs are real: Chained-TPHT is simple and compact, Flattened-TPHT keeps single-cache-miss common case. The benchmark suite is broad—YCSB, microbenchmarks, scaling, concurrency, resizing—and the standalone implementation plus artifacts are promised, which is real evidence. Feistel quotienting for exact keys is a nice practical trick. The central empirical claims mostly hold.\n\nThe soft spots are real but not fatal. First, the dereference table's 98.2% load factor is demonstrated with 'random insertions' but not with the address-derived IDs actually used in Chained-TPHT. Those IDs are in-memory addresses of tiny pointer fields; they are structured (consecutive or spaced by slot size), not i.i.d. random. If the two hashes don't handle that structure, Allocate can fail earlier and the succinctness claim degrades. The paper should either test with address-derived IDs or provide an argument that the ID distribution doesn't matter. This is the main load-bearing gap.\n\nSecond, Section 8 has no error bars or repeated runs; one concentration statement (n>=1e5 gives <1% deviation) is numerically wrong—at n=1e5 the deviation is about 3%. Minor, but easy to fix.\n\nThird, the compact-baseline comparison omits PaCHash, the most relevant prior systems-oriented compact hash table. It should be added.\n\nThe space analysis is consistent with the reported footprints. The theory relies on [12], which is the right citation, and the practical instantiation is genuinely new. The paper does not overclaim beyond 'to our knowledge.'\n\nWho it's for: hash-table and database researchers, plus systems folks who want a usable standalone. It deserves a serious referee. Send it to peer review, but ask for the dereference-table ID experiment, error bars, and a PaCHash comparison.","headline":"A credible practical succinct hash table that deserves referee time; the main weakness is that the dereference table's load factor isn't validated on the address-derived IDs the design actually uses.","tokens_in":28438,"tokens_out":2756,"would_cite":true,"duration_ms":31374,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P05","68P20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that two theoretical techniques, tiny pointers and quotienting, can be engineered into practical hash tables, yielding a chained design whose memory footprint drops below the raw size of the stored key-value pairs while op","keywords":["hash tables","succinct data structures","tiny pointers","quotienting","dereference table","space efficiency","cache locality","dynamic resizing"],"falsifier":"Run a sustained workload at 98.2% dereference-table load using keys deliberately chosen to make their bin addresses cluster, and count Allocate failures: a single failure at the claimed load, or a failure probability above the predicted negligible rate over polynomially many operations, would falsify the practical-succinctness claim. One can also check directly whether the address-derived IDs remain uniformly distributed across bins under different allocator layouts.","tokens_in":27534,"feed_emoji":"🗜️","tokens_out":5006,"duration_ms":56562,"temperature":0.7,"pith_summary":"This paper claims that two theoretical compression ideas, tiny pointers (shrinking a 64-bit address to one byte via a dereference table) and quotienting (hiding part of each key in its hash location via a one-round Feistel permutation), can be turned into production-ready hash tables. The result is Chained-TPHT, a chained hash table whose footprint can fall below the size of the stored key-value data while preserving expected constant-time insert, delete, and query operations, and Flattened-TPHT, a cache-line-oriented variant that keeps the common case to a single cache miss. A reader should care because memory, not raw speed, is often the binding constraint in large in-memory systems, and conventional hash tables waste significant DRAM on pointers and metadata. If these claims hold, succinct hash tables move from a theoretical curiosity to a practical option with a measured space efficiency above 100% for Chained-TPHT and 83.4% for Flattened-TPHT.","feed_headline":"A hash table beats the raw data size at constant speed","feed_subtitle":"Tiny pointers and key quotienting push hash tables past 100% space efficiency with O(1) operations.","key_machinery":"Key machinery: (1) Tiny pointers with a dereference table, a fixed-size allocator that returns an 8-bit pointer (a direction bit plus a bin index) instead of a 64-bit address, where dereferencing is a pure computation and power-of-two choices keep allocation failure negligible at 98.2% load. (2) One-round Feistel quotienting, a hash construction that splits each key k = q_pre ∘ r into a stored remainder r and a quotient q = h(r) ⊕ q_pre, so log n bits per key never need to be stored and the full key can be recovered as (q ⊕ h(r)) ∘ r. These two mechanisms work together to shrink the chained table's head array by a factor of eight and keep chains short, which is what allows the footprint to f","core_discovery":"The paper's central claim is that Chained-TPHT is, to its authors' knowledge, the first simple and practical succinct hash table: for n pairs of w-bit keys and values, it uses approximately n(2w - log n + 8 + 16/127)/(1 - delta) + 8n bits, which in the standard parameter regime w = O(log n) is within a (1+o(1)) factor of the information-theoretic lower bound while supporting O(1) expected-time operations. This is achieved by storing every pointer as an 8-bit tiny pointer through a dereference table and storing only the remainder of each key after quotienting away its high-order bits. The paper further claims Flattened-TPHT reaches 83.4% space efficiency with up to 89.3% higher throughput tha","pith_inferences":["[Editorial inference] The address-as-ID trick means the dereference table's hash inputs are the in-memory addresses of tiny-pointer fields; since allocators and layout choices shape those addresses, a workload that skews which bins those addresses hash to could stress the bin balance and trigger the allocation-failure path.","[Editorial inference] The pairing of tiny pointers and Feistel quotienting could plausibly transfer to other pointer-heavy structures, such as linked lists, tries, or adjacency lists, wherever per-node metadata dwarfs payload.","[Editorial inference] Supporting variable-length keys and values would require an extra indirection to the actual payload, adding a memory access and partially offsetting the space gain; the paper notes this extension but does not measure it.","[Editorial inference] A natural stress test is to run adversarial key distributions at 98% dereference-table load and watch for allocation-failure errors, which would reveal whether the 98.2% load factor is robust beyond the random-key and insert/delete mixes tested."],"forward_implications":["Chained-TPHT's head array shrinks by a factor of eight, so a large table's head array can fit in cache and most lookups complete in a single probe.","Quotienting saves log n bits per key, which is enough to push total memory below the raw size of the stored key-value pairs.","The two-choice dereference table at 98.2% load gives a practical instantiation of tiny pointers with no extra memory access on dereference.","The resizing framework divides growth into collaborative strides, avoiding stop-the-world pauses while keeping worst-case space efficiency at 46.7% with staggering.","Flattened-TPHT's home-block layout bounds operations to at most three cache misses outside resizing, with an average near 1.25, giving a strong tail-latency profile."],"fun_headline_variants":["Hash table smaller than its own dataset hits O(1) ops","Tiny pointers yield succinct hash tables: 105% space efficiency","Sub-data-size hash tables with constant-time operations","Chained-TPHT: first practical succinct hash table","Flattened-TPHT: 83% space, 89% faster than baselines"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the dereference table's two-choice bin allocation keeps every bin far enough from full when the tiny-pointer IDs are simply the addresses of the pointer fields; this is verified empirically on random keys and insert/delete mixes, but not analyzed or tested for adversarial or highly skewed key patterns, and if a bin ever fills, Allocate fails and the hash table returns an error by design.","fun_headline_variants_meta":{"raw":{"variants":["Hash table smaller than its own dataset hits O(1) ops","Tiny pointers yield succinct hash tables: 105% space efficiency","Sub-data-size hash tables with constant-time operations","Chained-TPHT: first practical succinct hash table","Flattened-TPHT: 83% space, 89% faster than baselines"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000702,"raw_usage":{"total_tokens":3032,"prompt_tokens":799,"completion_tokens":2233,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":2142}},"tokens_in":543,"tokens_out":2233,"duration_ms":17613,"temperature":1.0,"reasoning_tokens":2142,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T01:21:58.139153+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a sustained workload at 98.2% dereference-table load using keys deliberately chosen to make their bin addresses cluster, and count Allocate failures: a single failure at the claimed load, or a failure probability above the predicted negligible rate over polynomially many operations, would falsify the practical-succinctness claim. One can also check directly whether the address-derived IDs remain uniformly distributed across bins under different allocator layouts.","supporting_citations":[],"review_version":1}