{"id":"ece94226-b087-40b6-a775-787177013e35","arxiv_id":"2507.19926","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Hierarchical tiling lets sorting-based median filters on GPUs reach O(k log k) and O(k) per-pixel complexity for k x k kernels, with large measured speedups.","lead":"This paper introduces a GPU median filtering algorithm that shares sorting work across nearby pixels through hierarchical tiling, achieving O(k log k) or O(k) per-pixel complexity for k by k kernels. It reports CUDA implementations up to 5 times faster than prior state of the art for 8-bit, 16-bit, and 32-bit images.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The algorithm's exactness rests on an unproved multi-pixel pruning invariant; the arXiv version omits the proof, pseudocode, and code, so the central correctness claim cannot yet be checked.","rationale":"The reader's weakest-assumption analysis identifies exactly the load-bearing point: correctness hinges on the pruning invariant in §2.2/§3.2, and the paper provides no proof in the arXiv version, only references to supplemental material. I agree with that assessment. The invariant is plausible and the worked example in Fig. 6 is internally consistent, so I do not claim a demonstrated counterexample; the issue is that an unproved invariant is not enough for the headline claim that the algorithm computes exact medians at the stated complexities. The benchmark-hardware concern is real but secondary: even if the speedups were revised, a correct algorithm with moderate speedups would still be a contribution, whereas a broken pruning invariant would invalidate every result. The concrete test I propose would settle the invariant directly by exhaustive and random comparison against a brute-force median. Since the reader's conditional verdict already requires supplemental proofs and code before acceptance at face value, my review does not move the verdict; it reinforces the condition.","tokens_in":11643,"tokens_out":18442,"duration_ms":257708,"concrete_test":"Independently re-derive the containment lemma behind Fig. 6's 'Keep' formulas: for a tile with core size C and unseen count m=N-C, let P be the middle m+1 values of the sorted core. After adding b new elements that become part of the child core, with m'=m-b, prove and exhaustively check that the middle m'+1 values of the merged child core are contained in P union the b new elements, for all tiling patterns and k∈{3,5,7,9}. Then implement the recursion from §3.4 on a 2×2 root tile and compare leaf outputs to a brute-force median on all 2^16 4×4 binary images plus 10^5 random 8-bit crops; any mismatch invalidates the invariant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central correctness condition is the forgetfulness/pruning invariant stated in §3.2 and exercised in Fig. 6: after a tile split, the remaining elements of the parent sorted core, merged with the new extra rows/columns and then pruned, must still contain the median for every pixel of each child tile, down to the 1×1 leaf. This is not a trivial consequence of Fig. 3, because one sorted core serves multiple pixels and the number of unseen elements decreases by different amounts at horizontal and vertical splits. The manuscript asserts the invariant but does not prove it: §4.2 and §5.2 defer all proofs to 'the supplemental material,' and the arXiv version includes neither the proofs, the pseudocode, nor the source code. If the prune count is off by even one on either side for some tiling/kernel combination, the final 'median' can be wrong. A separate reproducibility concern is that the performance comparisons use benchmarks published by Adams and by Moroto/Umetani on their respective pages, which may have been measured on different GPUs; the claimed up-to-5x speedup could partly reflect hardware rather than algorithm. These are not accusations of error, but the headline claims are not independently verifiable from the submitted text.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a new exact median filtering algorithm for GPUs based on hierarchical tiling. The image is partitioned into a binary tree of tiles; at each split, sorted rows/columns and a sorted \"core\" are reused and pruned via a forgetfulness principle. Two variants are described: a data-oblivious selection-network variant claimed to achieve O(k log k) per-pixel complexity for a k x k kernel, and a data-aware multi-pass variant claimed to achieve O(k). CUDA implementations are presented, with benchmarks against OpenCV's histogram method, Adams' separable sorting networks, and Moroto/Umetani's 2D wavelet matrix method on an NVIDIA L40S GPU. The paper reports that the combined implementations are the fastest for most kernel sizes from 3 x 3 to 75 x 75, with speedups over prior work up to 5x. The authors explicitly defer correctness proofs, pseudocode, and implementation details to a supplemental document that is not present in the arXiv version.","tokens_in":11926,"tokens_out":4681,"duration_ms":58712,"significance":"If the correctness invariant and the complexity bounds are fully established, the contribution is significant: it would provide sorting-based exact median filtering with per-pixel complexity O(k log k) and O(k), which would be an improvement over the O(k^2 log^2 k) sorting-network approaches and a competitive alternative to histogram and wavelet-matrix methods across a wide kernel range. The hierarchical tiling idea is well motivated and the split between a register-resident data-oblivious variant and a multi-pass data-aware variant is sensible. The paper is also commendably candid about practical limitations such as compilation time, binary size, and memory footprint. However, the central correctness and complexity claims are currently assertions backed by an absent supplement, and the performance comparison mixes locally measured numbers with published results from other GPUs, so the headline claims are not yet independently verifiable.","major_comments":[{"comment":"The exactness of the algorithm rests on a pruning invariant that is asserted but not proved in the main text. The text states that after a split the parent sorted core is merged with new extra rows/columns and that 'extrema are discarded,' but it never specifies the exact number of elements to discard or proves that the remaining sorted core still contains the median for every pixel of each child tile. The single-pixel forgetfulness argument in Fig. 3 is insufficient, because one sorted core serves multiple child pixels and the number of unseen elements decreases by different amounts for horizontal versus vertical splits. The paper explicitly defers the proof to the supplemental material, which is not included in the arXiv submission. This invariant is load-bearing for both correctness and the complexity claims, so the authors must provide a complete proof in the manuscript or in the submitted supplement.","section":"§3.4 and Fig. 6 (also §4.2/§5.2)"},{"comment":"The performance comparison is not apples-to-apples. The manuscript states that OpenCV was measured on the L40S GPU, but for Adams it uses 'the benchmark published by Adams in the ACM digital library' and for Moroto/Umetani it uses 'the benchmark published on their project page.' Those published baselines were likely measured on different hardware, so the claimed 'up to 5 times faster' and 'fastest in most cases' conclusions could reflect GPU differences rather than algorithmic advantage. The authors should rerun the baselines on the same L40S GPU, or clearly disaggregate and qualify the comparison, and should report run-to-run variance or error bars. Without this, the central performance claim is not reproducible from the submitted text.","section":"§6, Fig. 8"},{"comment":"The per-pixel complexity results O(k log k) and O(k) are stated as theorems but the proofs are deferred entirely to the supplemental material, which is not present. The high-level outline—initialization O(k^2 log^2 k) per root tile and recursion O(t(k)^2 k log k)—does not by itself establish the claimed per-pixel bounds; a full accounting of all sorting, merging, multi-way merging, and corner-handling costs is needed, along with the justification for choosing t(k) = 2^{floor(log2 k)-1}. As written, the complexity claim cannot be checked from the manuscript alone.","section":"§4.2 and §5.2"}],"minor_comments":[{"comment":"'Perrot el al.' should be 'Perrot et al.'","section":"§2.2"},{"comment":"The variables n and m in the forgetfulness illustration are not defined in the caption or the immediately preceding text; please define n as the total number of inputs and m as the number still unseen, and explain the two extreme cases shown in (a) and (b).","section":"Fig. 3 and surrounding text"},{"comment":"The legend entries are abbreviated and the provenance of each curve should be clearer: specify that 'Histogram (OpenCV)' is Green's implementation, and add a note that the Adams and Moroto/Umetani curves are taken from their published benchmarks (with the caveat noted in the major comments).","section":"§6, Fig. 8"},{"comment":"The limitation statement mentions that the data-aware version's memory requirement 'exceeding the size of the input image by up to two orders of magnitude' is 'detailed in the supplemental material.' Since the supplement is absent, please include at least one concrete example or a short table in the main text so readers can judge the practical memory budget.","section":"§7.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is essentially a claims document: the full proofs, pseudocode, and code are in a supplement that is not included with the arXiv submission. The correctness invariant is nontrivial and is the core of the paper; the benchmark comparison also needs to be made homogeneous. If the authors can supply the missing supplement and either rerun or qualify the baseline comparisons, a revised version could be publishable. I would not recommend acceptance without seeing the proof and the corrected benchmark methodology."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The hierarchical tiling algorithm is a genuine extension of Adams' separable sorting networks. Splitting tiles recursively, sharing work first among many pixels then among fewer, and pruning extrema at each level gives per-pixel complexities of O(k log k) and O(k) for sorting-based median filtering, which is new as far as I can tell from the cited work. The paper is clearly written, gives a fair account of prior methods, and is honest about its own limitations: long compile times, large binaries, and memory use that can exceed the image by two orders of magnitude.\n\nThe soft spot is the correctness invariant. The whole algorithm rests on the claim that after a tile split, the pruned sorted core still contains the median for every pixel in each child tile, down to 1x1 leaves. The paper states this, illustrates it with Figure 6, and then defers all proofs to supplemental material. The arXiv version includes neither the proofs nor the pseudocode, and no source code. That is a real gap: the invariant is not a trivial consequence of the single-pixel forgetfulness principle, because one sorted core serves multiple pixels and the number of unseen inputs shrinks differently in horizontal and vertical splits. I am not claiming the invariant is false; I am saying it is unverifiable from this text. For a paper whose headline is a new exact algorithm, that is the one part a referee needs to see.\n\nThe benchmark section has a separate, smaller problem. The Adams and Moroto/Umetani numbers are taken from published benchmarks, not rerun on the same hardware. The L40S runs for the author's method and the published numbers likely come from different GPUs, so the 'up to 5x faster' and '50x faster at 75x75' figures may partly reflect hardware rather than algorithm. No error bars and no code archive make it hard to separate the two.\n\nWhat holds up: the complexity argument is derived from standard sorting and merging network bounds, not from fitting; the root tile heuristic is openly a heuristic; and the paper concedes that the wavelet matrix wins for the largest kernels. The engineering details are plausible and well-motivated.\n\nThis paper deserves a serious referee. I would accept it for review and ask for the supplemental proofs to be available to reviewers, and for a same-hardware comparison of at least the Adams baseline. The hierarchical tiling idea is worth engaging with, but the exactness claim should be checkable from the submission itself.","headline":"Genuinely new separable sorting-network median filter with O(k log k) and O(k) per-pixel complexity claims; plausible and well written, but the arXiv version omits the correctness proof and mixes benchmark hardware, so the strongest speedup claims are provisional.","tokens_in":12367,"tokens_out":2384,"would_cite":true,"duration_ms":25971,"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 hierarchical-tiling algorithm computes exact median filters on GPUs with per-pixel cost O(k log k) for a register-backed variant and O(k) for a data-aware variant, and reports up to five times higher throughput than prior GPU…","keywords":["median filter","sorting network","GPU","parallel algorithm","hierarchical tiling","selection network","image processing","data-oblivious algorithm"],"falsifier":"Compute the exact median by brute-force sorting for every pixel of random 8-bit and 32-bit test images, for a range of odd kernel sizes such as 3x3 up to 31x31, and compare against both GPU variants; any mismatch, particularly on adversarial patterns designed to hit the pruning boundary, would falsify the exact-median claim and, more specifically, the forgetfulness discard invariant.","tokens_in":11456,"feed_emoji":"⚡","tokens_out":7414,"duration_ms":77149,"temperature":0.7,"pith_summary":"The paper claims that median filtering, long considered too expensive for large kernels and high bit depths, can be made much faster by reusing sorted intermediate results across overlapping kernels. It introduces hierarchical tiling: a tile of pixels is split recursively, and at each split the already-sorted core of each child kernel is extended with only the newly exposed rows, columns, and corners while extrema are discarded. From this, two GPU algorithms follow: a data-oblivious selection network with per-pixel complexity O(k log k), and a data-aware multi-pass version with O(k) per-pixel complexity, both computing exact medians. If correct, these are the first sorting-based median filters with these complexities, and the paper's benchmarks show them ahead of existing GPU implementations for most kernel sizes from 3x3 to 75x75 across 8-, 16-, and 32-bit data.","feed_headline":"Median filter on GPUs now runs up to 5x faster","feed_subtitle":"A hierarchical tiling scheme computes exact medians for 8-, 16-, and 32-bit images across most kernel sizes from 3x3 to 75x75.","key_machinery":"The central mechanism is hierarchical tiling, a binary tree of tile subdivisions, combined with a sorted-core invariant. The core of a tile is the intersection of all kernels over that tile's pixels; at every subdivision the sorted core of the parent is merged with the newly included extra columns or rows to form the child's sorted core, and the forgetfulness principle (when m inputs remain unseen, the median lies in the middle m+1 of the seen values) justifies discarding extrema, keeping the candidate set small. The data-oblivious variant implements all merges as comparison networks compiled to register min/max instructions, while the data-aware variant uses linear-time merging algorithms and saves intermediate state to memory between passes.","core_discovery":"The paper's central claim is that the overlapping kernels of adjacent pixels can be separated recursively, not just once, so that a single sorted core is reused through a hierarchy of tile subdivisions. Concretely, for a tile of pixels the algorithm sorts the core of the tile (the intersection of all kernels), the extra columns, and the extra rows once; each split of the tile then absorbs the newly exposed columns or rows into the child's sorted core with a small merge, applying the forgetfulness principle to discard values that cannot be medians. When the recursion reaches single pixels, the sorted core contains exactly the median of that pixel's kernel. This yields per-pixel complexity O(k log k) for the register-resident selection-network variant and O(k) for the data-aware multi-pass variant, and the paper reports that the GPU implementation is the fastest exact median filter for most tested kernel sizes and data types.","pith_inferences":["The paper does not prove the discard invariant in the main text; a formal proof or exhaustive test of that invariant would be the first thing to check, since a failure would produce silently wrong medians rather than graceful degradation.","The hierarchical tiling recursion is generic to rectangular neighborhoods, so the same machinery could plausibly be adapted to 3D kernels, a direction the paper names as future work; if it carries over, medical-imaging denoising with large 3D kernels could see similar speedups.","The complexity proof relies on a root-tile heuristic that keeps the root tile within a constant factor of the kernel size, so tile-size sensitivity is worth measuring; the claimed O(k) bound may hold only when that relationship is maintained.","The data-oblivious variant's sharp performance drop after 15x15 kernels is likely register pressure, so the crossover between the two variants should shift with GPU register-file size and occupancy; on future architectures the register variant may dominate for larger kernels."],"forward_implications":["If the claimed complexities hold, median filtering cost grows only linearly (data-aware) or as k log k (register variant) with kernel diameter, so kernels of diameter 31 or larger become usable in real-time pipelines instead of being prohibitive.","16-bit and 32-bit channels stop being a handicap: sorting-based filters are not limited by histogram bin count, so high-precision image data can be filtered at the same speed profile as 8-bit data.","Because the output is the exact median, not an approximation, the method can replace existing GPU median filters in any pipeline without changing downstream semantics.","The crossover point with constant-time wavelet-matrix filters (around 61x61 for 8-bit, 75x75 for 16-bit) sets a clear regime: use hierarchical tiling for small and medium kernels and constant-time methods only for very large ones.","Improving the parallel multi-way merge bottleneck would extend the data-aware version's dominance to even larger kernels."],"supporting_citations":[{"why":"Introduces separable sorting networks for median filters and the tile/core/extras vocabulary that hierarchical tiling extends, and serves as the main sorting-based baseline.","marker":"Adams [2021]"},{"why":"Supplies the odd-even sorting and merging networks and the complexity bounds the data-oblivious variant builds on.","marker":"Batcher [1968]"},{"why":"Establishes the forgetful-selection principle that justifies discarding extrema during recursive splits.","marker":"Perrot el al. [2013]"},{"why":"Shows 2D sharing of work between four overlapping kernels, the direct predecessor of tile-based sharing.","marker":"Salvador et al. [2018]"},{"why":"Defines the per-pixel O(k) baseline for median filtering through running histograms.","marker":"Huang et al. [1979]"},{"why":"Provides the OpenCV histogram GPU median filter used as a benchmark.","marker":"Green [2018]"},{"why":"Provides the constant-time wavelet-matrix median filter, the asymptotic competitor that eventually overtakes the new method at large kernels.","marker":"Moroto and Umetani [2022]"},{"why":"Supplies the multi-way merging network used in the data-oblivious implementation.","marker":"Lee and Batcher [1995]"},{"why":"Supplies the parallel merge-path algorithm used for linear-time merging in the data-aware variant.","marker":"Odeh et al. [2012]"}],"fun_headline_variants":["GPU median filtering up to 5x faster via hierarchical tiling","Hierarchical tiling makes median filtering fast on GPUs","Exact median filter runs 5x faster on GPU with hierarchical tiling","5x faster exact median filter on GPU using hierarchical tiling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the recursive discard rule: after each split, the algorithm assumes the values it throws away from the sorted core can never be the median of any child tile's pixel, an invariant the paper asserts by reference to supplemental material rather than proves in the main text.","fun_headline_variants_meta":{"raw":{"variants":["GPU median filtering up to 5x faster via hierarchical tiling","Hierarchical tiling makes median filtering fast on GPUs","Exact median filter runs 5x faster on GPU with hierarchical tiling","5x faster exact median filter on GPU using hierarchical tiling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00042,"raw_usage":{"total_tokens":2170,"prompt_tokens":963,"completion_tokens":1207,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":1133}},"tokens_in":579,"tokens_out":1207,"duration_ms":10163,"temperature":1.0,"reasoning_tokens":1133,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T13:51:33.091611+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact median by brute-force sorting for every pixel of random 8-bit and 32-bit test images, for a range of odd kernel sizes such as 3x3 up to 31x31, and compare against both GPU variants; any mismatch, particularly on adversarial patterns designed to hit the pruning boundary, would falsify the exact-median claim and, more specifically, the forgetfulness discard invariant.","supporting_citations":[],"review_version":1}