{"id":"eb088030-7413-4855-9ed4-ee8b4753d0ab","arxiv_id":"2607.24621","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Almost all heap working-set bounds are amortized-equivalent; a new recursive construction achieves the stronger stack-like bound with O(1) decrease-key and o(log* n) insert.","lead":"The paper proves that nearly all working-set bounds for heaps are amortized-equivalent, and builds the first heap that is stack-like while supporting O(1) decrease-key and near-constant insert. That closes a long-open gap between locality-aware heaps and Fibonacci-style decrease-key speed.","discovery_kind":"unification","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"No significant objection identified. The delicate quartermaster charging in §3.3.4 is compressed, but its segment accounting appears to support the claimed token invariant.","rationale":"The reader located the correct residual risk: the multi-level size-invariant and charging argument, not the independently argued equivalence theorem in Section 4. I agree with that assessment, but the specific mechanism appears sound after reconstructing the segment inequality. In particular, the seemingly underexplained trimming step can be interpreted as retaining each segment through its last relevant forward FixTooBig; multiple forward rebalances within one segment do not invalidate the inequality because every net increase of \\(F_i\\) still requires a PushLeft. Likewise, the temporary bound \\(|Q_i|=O(w_i)\\) follows inductively from the ascending FixTooBig order and the geometric domination in Claim 3.23. Because the concern is about compressed exposition and lack of machine checking rather than a concrete gap, it does not justify changing the reader’s ACCEPT verdict. The proposed token-invariant formalization would provide high-value assurance for the central construction.","tokens_in":27280,"tokens_out":8631,"duration_ms":348533,"concrete_test":"Formalize the per-boundary token invariant \\(T_i(t)=P_i(t)-M_i(t)\\ge 0\\) in a proof assistant or executable state-machine model, using the event rules in §3.3.4 and the endpoint bounds of Claims 3.23–3.24. Explicitly check PushLeft, Delete, forward batch moves, reverse batch moves, quartermaster creation/deletion, and segment tails. If the invariant survives induction over all events, Lemma 3.26’s \\(O(t)\\) charging is sound; if it fails, the counterexample exposes the missing charge.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most delicate load-bearing step is the one identified by the reader: Lemmas 3.25–3.26 must rule out unbounded item oscillation across quartermaster boundaries while charging each boundary’s moves to prior PushLeft operations. On close reading, the argument has a coherent invariant. Within a segment beginning after \\(Q_i\\) was empty or after a reverse move into \\(Q_i\\), Claims 3.23–3.24 put \\(|F_i|\\) below \\(w_i/2+o(w_i)\\); after the segment-ending forward FixTooBig, it is above \\(w_i-o(w_i)\\). Inside such a segment, only PushLeft increases \\(|F_i|\\), while deletes and forward moves decrease it. Hence \\(P_s-M_s\\ge w_i/2-o(w_i)\\), which is nonnegative for sufficiently large fixed \\(i\\). Reverse moves are also necessarily preceded by forward moves of the same item across that boundary, and small-\\(i\\) boundaries have \\(w_i=O(1)\\). The prose about “trimming” segments is terse and should be formalized, but I did not find a case that breaks the accounting. This is therefore a verification risk rather than an identified flaw in Theorem 3.3.","agreement_with_reader":"agree"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper makes two contributions on beyond-worst-case heaps in the comparison model. First (Section 4, Theorem 1.3), it proves that six working-set-style properties appearing in the literature (regular, touched-items, insert-only, delete-only, strong [Iacono], strict) are all equivalent up to constant factors in the amortized sense, while the stack-like property is strictly stronger (Lemma 1.4) and the size property strictly weaker (Theorem 4.14 and the following separation). The equivalences are proved by explicit potential-redistribution arguments (Theorems 4.10–4.11) that reassign O(1) potential per operation to pay for deletions of \"unhappy\" items. Second (Section 3, Theorem 3.3/Theorem 1.5), the paper constructs, for any fixed k, a heap with amortized Insert in O(log*(k) n), DecreaseKey in O(1), and ExtractMin/Delete in O(log s_x) (stack-like). The construction is inductive: starting from a Fibonacci heap augmented with a linked list (Lemma 3.6), each inductive step (Lemma 3.5) replaces the warehouse heap by the previously constructed f-deque-like heap, using \"quartermasters\" of preferred sizes w_i ≈ 2^{f(w_{i+1})} with bundles of size ≈ f(w_i), and a charging argument (Lemmas 3.25–3.26) to bound item migrations between adjacent quartermasters. Section 5 gives simple splay- and finger-tree-based working-set/stack-like heaps without fast DecreaseKey.","tokens_in":27578,"tokens_out":5509,"duration_ms":663874,"significance":"If correct, both results are of clear value. The equivalence theorem genuinely simplifies a fragmented landscape: prior work built special-purpose heaps for the strong and strict variants, and Theorem 1.3 retroactively shows any working-set heap suffices for those applications (e.g., the sorting-under-partial-information result of [Hae+26]). The proofs are short, self-contained, and black-box. The heap construction resolves the open problem stated in [EFI12] of a stack-like heap with fast DecreaseKey, at the cost of only an o(log* n) additive Insert overhead — a strong, concrete, and falsifiable bound. The construction is fully specified with explicit invariants, potentials, and charging lemmas, and the base case and inductive step are standard-comparison-model arguments with no fitted parameters (only the iteration depth k and a constant base size w_0 are free). The manuscript is also unusually honest about its limitations (amortized-only bounds, constant-factor blow-up per inductive level in Remark 3.7, the \"ends empty\" caveat in §5.1).","major_comments":[{"comment":"This lemma carries the entire amortization of the recursive construction (it is the only place where item oscillation across quartermaster boundaries is ruled out), yet its proof is the most compressed in the paper. The segment argument has a coherent invariant — within a segment starting with |F_i| < w_i/2 + o(w_i) and ending after a forward FixTooBig with |F_i| ≥ w_i − o(w_i), only PushLeft increases |F_i|, giving P_s − M_s ≥ w_i/2 − o(w_i) ≥ 0 for large fixed i — but several steps are left implicit and should be formalized: (a) the 'trimming' procedure (what exactly happens to a segment whose terminal FixTooBig is interleaved with FixTooSmall calls at other levels, and why segments without any FixTooBig contribute M_s = 0 and can be discarded); (b) the case split at segment start (Q_i previously empty vs. a preceding reverse move), including why |F_i| = o(w_i) in the empty case follow","section":"§3.3.4, Lemma 3.25"},{"comment":"The stack-like bound O(log s_x) for Delete relies on s_x ≥ |Q_{i−1}| ≥ w_{i−1}/2, i.e., on the size invariant holding at the moment the quartermaster-level Delete is invoked. The text acknowledges the invariant 'can be temporarily violated in the middle of an operation' and only proves |Q_i| = O(w_i) at all times (Claim 3.24). The argument is almost certainly fine — quartermaster Deletes happen at operation start, before FixTooSmall runs, so the invariant from the end of the previous operation applies up to an O(1) slack absorbed by the logarithm — but this ordering is never stated, and the chain f(w_i) = O(f(w_{i−1})) additionally uses f(n+1) = O(f(n)) from Remark 3.9 without saying so. Since this inequality is what converts the additive f(w_i) term into the stack-like bound, please make the invariant-at-operation-boundary assumption and the f-regularity steps explicit.","section":"§3.3.3, Claim 3.22 (and its interaction with Claim 3.24)"}],"minor_comments":[{"comment":"Typo: 'DecreaseKey ando(log ∗ n)-time insert' — missing space; also 'O(1)-time decrease-key' capitalization is inconsistent with the body.","section":"Abstract"},{"comment":"The claim that taking k = α(n) yields a '2^{O(α(n))}-deque-like heap' is asserted without justification and the phrasing is ambiguous (is the 2^{O(α(n))} a constant-factor blow-up per operation?). Either give a one-line derivation from the per-level constant-factor blow-up or soften the statement.","section":"Remark 3.7"},{"comment":"Notation mismatch: the lemma states BatchPop cost O(|L|) for the returned list L, while Claim 3.16 states O(|B|) for 'the bundle being returned'. Since a batch is a single bundle this is presumably the same quantity, but please unify the notation.","section":"Claim 3.16 vs. Lemma 3.11(4)"},{"comment":"Two clarifications would help: (i) the individual weights 1/k² decrease over time as k grows, so the splay access lemma (stated for fixed weights) is being applied via a potential-decrease argument — one sentence making this explicit would preempt confusion; (ii) the 'provided the heap ends empty' restriction (negative potential of a non-empty tree) deserves a remark on whether it can be removed, e.g., by adding a constant to the potential.","section":"§5.1"},{"comment":"'Distance of x to H.First ... plus one' is informal; since s_x is used quantitatively throughout (e.g., s_x ≥ |Q_{i−1}| ≥ w_{i−1}/2 in Claim 3.22), please define it as a count of items in the linked-list interval, consistent with Definition 1.1.","section":"Definition 3.2"},{"comment":"The 'can be reanalysed' framing is appropriate and honestly stated; it would be worth one additional sentence noting that the redistribution in Theorems 4.10–4.11 is non-constructive (the potential assignment at time t depends on future deletion times), so the equivalence is about amortized cost accounting, not about an online rebalancing scheme.","section":"§4, framing paragraph"},{"comment":"The figure would benefit from arrow labels or a caption sentence stating the direction of implication (strictly stronger → weaker) and where the strict separations are proved (Lemma 1.4, §4.3).","section":"Figure 1"},{"comment":"Several line-break artifacts appear in the text ('W orking-set', 'A VL', 'T ouch-based', 'F raming', 'R oadmap') — presumably a PDF extraction issue, but please check the source. Also, ˜w_x (strict working-set size), w_i (preferred sizes), and w(x) (splay weights in §5.1) are three distinct uses of w; consider differentiating.","section":"General"}],"recommendation":"minor_revision","confidential_remarks":"The citation pattern is heavily weighted toward the authors' own prior line of work, but this appears appropriate: they created much of the relevant literature and the concurrent papers [Rut26, Van+26, VRR25a/b] are cited and accurately positioned. The two contributions are each publishable on their own; the equivalence theorem is the cleaner result, while the construction's crux (Lemma 3.25) is sound on my reading but under-written. I recommend minor revision primarily to get the §3.3.4 charging argument into a form a reader can verify without reconstructing it."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"Two real results here. First, they show that the six working-set variants people have been carefully distinguishing (regular, touched-items, insert-only, delete-only, strong, strict) are amortized-equivalent up to constants, while stack-like is strictly stronger. That collapses a fragmented toolkit that recent Dijkstra and partial-info sorting papers were dancing around. Second, they give the first comparison-model heap that is amortized stack-like and still has O(1) decrease-key, with insert only O(log*(k) n) for any fixed k. Prior stack-like heaps either lacked fast decrease-key or were not known to have it; the working-set heaps with fast decrease-key stopped short of stack-like.\n\nThe equivalence half is short, clean potential redistribution (happy/unhappy items, 1/i^2 charges by insertion or deletion order). It is the kind of argument you wish someone had written five years ago. The construction is the heavier lift: recursive quartermasters over warehouses of bundles, preferred sizes w_i ≈ 2^{f(w_{i+1})}, FixTooBig/FixTooSmall, and a stack-to-deque black box. Invariants and potentials are spelled out; base case is Fibonacci plus a linked list.\n\nThe soft spot is exactly where the reader and the stress-test put it: the multi-level move charging in §3.3.4 (Claims 3.23–3.24, Lemmas 3.25–3.26). Segment cutting is terse, and o(w_i) error terms have to stay controlled for slow f. On reading, the token accounting holds—segments start low and end high, only PushLeft grows F_i inside a segment, reverse moves are preceded by forward ones, small-i levels are O(1)—so this is verification risk, not a hole I can exhibit. Constant-factor blow-up per induction step is acknowledged (Remark 3.7); they correctly stop at fixed k. Section 5’s BST/splay sketches are secondary and known-style.\n\nCitations are appropriate; self-cites to their Dijkstra/sorting work are the natural clients. No code, no Lean—normal for this venue and style.\n\nThis is for people who build or use beyond-worst-case heaps, or who need a clean reference for which working-set bound they can assume. I would bring it to reading group, cite the equivalence and the existence result, and send it to referees. The central claims hold as stated.","headline":"Clean unification of working-set heap bounds plus the first stack-like heap with true O(1) decrease-key; the delicate charging looks sound on a close read.","tokens_in":29071,"tokens_out":633,"would_cite":true,"duration_ms":15779,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P05","68Q25"],"pacs":[],"model":"grok-4.5","headline":"Almost all working-set heap bounds are the same amortized guarantee; only the stack-like bound is strictly stronger, and a new heap achieves it with constant decrease-key.","keywords":["heaps","priority queues","working-set bound","stack-like property","decrease-key","amortized analysis","beyond-worst-case data structures"],"falsifier":"Exhibit an infinite family of insert/delete sequences on which every heap obeying one of the six working-set definitions still pays ω(n) total extract cost while a stack-like heap pays O(n), or produce a concrete implementation whose FixTooBig/FixTooSmall phases force super-constant amortized work per push for some fixed iteration depth k.","tokens_in":28910,"feed_emoji":"📚","tokens_out":979,"duration_ms":23486,"temperature":0.7,"pith_summary":"Heaps are usually judged by worst-case time, yet many algorithms only need good behavior when recent items are deleted often. The paper shows that the many natural definitions of this “working-set” guarantee—regular, insert-only, delete-only, touched-items, strong, and strict—are equivalent up to constants once costs are amortized, so any heap that meets one of them meets them all. The sole exception is the stack-like bound, which charges only the logarithm of how many still-present items are no older than the deleted one; that bound is strictly stronger. The authors then build the first comparison-model heap that attains the stack-like bound while still supporting decrease-key in constant amortized time and insert in time that is an arbitrarily slow iterated logarithm. The construction therefore simultaneously simplifies the theory and supplies a single data structure strong enough for the applications that previously demanded distinct heap variants.","feed_headline":"Six heap working-set bounds collapse to one","feed_subtitle":"Only the stack-like bound is stronger—and a new heap hits it with constant decrease-key","key_machinery":"An inductive family of f-deque-like heaps built from quartermasters: each quartermaster stores consecutive items in bundles of size roughly f(w) inside an already-constructed f-deque-like warehouse, and a sequence of such quartermasters of preferred sizes w_i ≈ 2^{f(w_{i+1})} is kept balanced by FixTooBig/FixTooSmall moves that amortize to O(1) per item.","core_discovery":"In the amortized comparison-model setting, six working-set-style heap properties that appear throughout the literature are equivalent up to constant factors while preserving the cost of every other operation; the stack-like property is strictly stronger, and there exists a heap realizing it together with O(1) decrease-key and O(log*^(k) n) insert for every fixed k.","pith_inferences":["Because the equivalence is black-box, future papers can safely cite “a working-set heap” without re-proving which of the six formulations they need.","The same quartermaster layering may be portable to other multi-order structures (e.g., set-union or order-maintenance) that must keep both a temporal spine and a key-order heap.","If the constant-factor blow-up per induction step can be made independent of k, an inverse-Ackermann insert overhead would become plausible; the paper leaves that open."],"forward_implications":["Any existing heap already known to satisfy one working-set variant can be re-analyzed to satisfy all six, immediately transferring prior application results that required a stronger-looking variant.","Dijkstra and topological heapsort that previously needed a specially constructed strong or strict working-set heap now run with any ordinary working-set heap.","A single comparison-model structure can serve both as a classical Fibonacci-style heap and as a stack, with deletion cost interpolating smoothly between the two regimes.","Further constant-factor applications of the same inductive step yield heaps whose additive insert overhead is any fixed-height iterated logarithm."],"fun_headline_variants":["Six working-set heap bounds collapse into one","Stack-like bound is strictly stronger than the rest","New heap hits stack-like bound with O(1) decrease-key","Working-set heap properties prove equivalent up to constants","First heap with stack-like bound and sub-log* insert"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The charging argument that moves items between successive quartermasters costs only a constant per insertion, even after the o(w_i) size-error terms that appear while sizes are being repaired, must hold for every slow-growing f in the iteration.","fun_headline_variants_meta":{"raw":{"variants":["Six working-set heap bounds collapse into one","Stack-like bound is strictly stronger than the rest","New heap hits stack-like bound with O(1) decrease-key","Working-set heap properties prove equivalent up to constants","First heap with stack-like bound and sub-log* insert"]},"model":"grok-4.5","effort":"low","cost_usd":0.00462,"raw_usage":{"total_tokens":1235,"prompt_tokens":643,"num_sources_used":0,"completion_tokens":70,"cost_in_usd_ticks":46204000,"prompt_tokens_details":{"text_tokens":643,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":522,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":643,"tokens_out":70,"duration_ms":6275,"temperature":1.0,"reasoning_tokens":522,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T10:18:02.062059+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit an infinite family of insert/delete sequences on which every heap obeying one of the six working-set definitions still pays ω(n) total extract cost while a stack-like heap pays O(n), or produce a concrete implementation whose FixTooBig/FixTooSmall phases force super-constant amortized work per push for some fixed iteration depth k.","supporting_citations":[],"review_version":1}