{"id":"098cba2f-c8a3-41b7-a0e9-cd88c57b0a47","arxiv_id":"2607.21368","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"An incremental assignment solver with warm-started dual potentials claims 1.1–6.5× speedups over Hungarian on synthetic block-sparse crowd matrices, with the headline 3.7–6.5× range not matching its own data.","lead":"This paper proposes reusing the previous frame's matching solution as a warm start for assigning detections to tracks in dense crowds, avoiding full Hungarian re-solves each frame. It reports 1.1–6.5× speedups on synthetic crowd instances, but the advertised 3.7–6.5× range is contradicted by its own table and no code is released.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Warm-start advantage rests on unmeasured augmenting-path length L (Table 2), and the potential initialization in §5.3 Eq. (9)–(10) is circular as written.","rationale":"The reader's weakest assumption — L≪k — is exactly where the central claim is least secure. The correctness of the incremental scheme is plausible (shortest augmenting paths with feasible potentials is a standard route), but the paper's headline advantage is the warm-start yielding short paths. No proof or measurement of L is provided. The circular Eq. (9)–(10) is a separate, concrete internal inconsistency that a careful reader must flag: Y_n depends on X_n and X_n depends on Y_n, so the algorithm as written cannot be run. It is probably fixable by swapping the computation order, so it does not push the verdict to REJECT, but it reinforces the need for revision. The concrete test is straightforward: instrument the code and report L/k; this would settle whether the complexity analysis and the speedup explanation are valid. The empirical speedups in Table 3 may still hold, but without L measured, the asymptotic and structural claims are unsupported. Therefore the reader's CONDITIONAL verdict stands unchanged.","tokens_in":9148,"tokens_out":12286,"duration_ms":133785,"concrete_test":"Instrument Algorithm 2 to record, for every augmentation step n in scenarios S1/S2/S3 at N=200, 500, 1000, 2000, 3000, 5000, the number of columns added to T (i.e., L), and report mean and max L/k. If max L scales with k or is not ≪1, the O(N²L log k/C) complexity and the warm-start advantage are unsupported. Additionally, re-derive Eq. (9)–(10) in non-circular order (compute X_n from j<n before Y_n) and check that the resulting potentials are feasible and reproduce the §2.4 example; if the printed order is kept, LabelCompanion is undefined.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that chaining the incremental primitive with dual potentials optimal for the (n−1)×(n−1) subproblem makes each augmenting path short (L≪k), giving the O(N²L log k/C) bound in Table 2 and the reported 3.7–6.5× speedup. This is the least secure condition. Section 6.3 asserts 'short O(1) augmenting paths', but no theorem bounds L and Section 7 never measures it. If L grows like k, the bound degrades to O(N³/C), which is no better than dense Hungarian and the asymptotic advantage disappears. The runtime scaling in Table 3 is consistent with this worry: the incremental S1 times grow roughly as N^2.7, not N², suggesting L is not O(1) (N=200: 0.000458s; N=5000: 2.981s). Additionally, the algorithm is not executable as printed: Eq. (9) defines Y_n using X_i for i=n, while Eq. (10) defines X_n using Y_n, so LabelCompanion is circular. Both issues must be addressed before the complexity claim is accepted.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an incremental exact assignment algorithm for the N×N bipartite matching problem arising in crowd tracking. The method grows the matching from 1×1 to N×N by adding one trajectory/detection pair at a time, maintaining dual potentials that are claimed to be exactly optimal for the current subproblem, and uses a Dijkstra augmenting-path search for each extension. A diagonal-reordering invariant, SparseReorder, is introduced to keep the matching in canonical form. The paper claims the same optimal matching as the Hungarian algorithm with O(N²L log k/C) complexity and 3.7–6.5× speedup on synthetic crowd instances up to N=5000, with correctness verified against Hungarian. The evaluation is entirely on synthetic clustered graphs (Scenarios S1–S3); no real MOT data or code are provided.","tokens_in":9485,"tokens_out":4905,"duration_ms":53349,"significance":"If the complexity claim and the measured speedups hold, the paper would make exact data association in dense crowds substantially cheaper and would provide a useful extension of the incremental assignment literature. The practice of verifying every reported run against the Hungarian optimum is a strength, as is the careful construction of block-sparse crowd-like test instances. However, the central complexity gain rests on the unmeasured augmenting-path length L, and the potential initialization as written is circular. The advertised speedup range is also not consistent with the full table of results. The paper's practical claim for real-time crowd tracking is not yet supported because no real tracking data are used. These issues are load-bearing for the main claims, so the manuscript should be revised before acceptance.","major_comments":[{"comment":"The potential initialization is circular as written. Equation (9) defines Y_n using X_i for all i≤n, which includes X_n, while Eq. (10) defines X_n using Y_n. LabelCompanion therefore cannot be executed in the order presented, and Theorem 1's inductive step — which relies on LabelCompanion to establish feasibility for node n — is not substantiated. Please correct the index ranges (presumably i<n in Eq. (9)) and provide a complete proof that the resulting potentials are feasible and satisfy complementary slackness.","section":"§5.3, Eqs. (9)–(10)"},{"comment":"The complexity bound O(N²L log k/C) and the assertion of 'short O(1) augmenting paths' depend on L, the average augmenting path length, but L is never precisely defined, measured, or bounded. If L grows like k, the incremental bound degrades to O(N³/C), which is no better than dense Hungarian. The runtime scaling in Table 3 is not reassuring: for S1, runtime grows from 0.000458 s at N=200 to 2.981 s at N=5000, a factor of ~6500, far above the N² factor of 625. This suggests L is not constant. A theorem bounding L under the stated cluster model, or at minimum an empirical measurement of L across N, is essential to support the central complexity claim.","section":"Table 2 / §6.3"},{"comment":"The abstract and §1.2 claim a 3.7–6.5× speedup over Hungarian, but Table 3 reports speedups as low as 1.1× (S2, N=200), with additional values below 3.7× (e.g., 2.1×, 2.3×, 2.5×). The speedup claim should be revised to the observed range (1.1–6.5×), and the small-N behavior should be discussed rather than obscured by an average or best-case statement.","section":"Abstract vs. Table 3"},{"comment":"The experimental evaluation is performed exclusively on synthetic graphs generated from the paper's crowd model (Table 1). No real MOT sequences, detector outputs, or trackers are used. The introduction and §7.3 frame the contribution as enabling real-time crowd tracking at 25 fps, but the feasibility numbers are only for generated instances. If the paper is intended as an algorithmic contribution on structured assignment problems, this should be stated clearly; if it is intended for tracking, evaluation on a standard benchmark such as MOT16 or MOT20 is needed. The absence of code also limits reproducibility of the timing claims.","section":"§7"}],"minor_comments":[{"comment":"The scale factor is called SCALE in Eq. (1) and S in Eq. (4). Use a single notation throughout.","section":"§2.2 / §3.1"},{"comment":"SparseReorder is described only informally. The phases 'save', 'apply', and 'reset' are hard to follow, and the invariant maintained by the σ mapping is not defined rigorously. Please give a complete pseudocode and state explicitly how matching cost and potentials are preserved.","section":"Algorithm 1"},{"comment":"The line 'parent[j*] ← src[j*]' refers to src without prior definition. Clarify what src stores (presumably the row/node that reached j*).","section":"Algorithm 2, line 6"},{"comment":"The 'Key distinction' paragraph should be more precise about what is new beyond the author's prior incremental-assignment paper [12]. Simply chaining the primitive N times may not be a sufficient novelty statement; the invariant that makes warm-starting valid should be highlighted.","section":"§8"},{"comment":"The table is not referenced in the running text. Add a sentence such as 'Table 3 reports the raw runtimes and speedups.'","section":"Table 3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a plausible algorithmic contribution, but it needs a corrected and fully proven initialization step, a measured or proven bound on L, and a more honest statement of the speedup range before it can be accepted. I would also ask the editor to consider whether the paper's overlap with the author's own [12] is sufficiently addressed; the novelty appears to be primarily the block-sparse warm-starting application, which needs strong empirical support. The lack of real-data evaluation and code is a concern for a cs.CV venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is an engineering extension of your own 2007 incremental assignment work, applied to block-sparse crowd cost matrices. The idea is plausible and the experiments do show real speedups at large N, but the abstract overstates the speedup range, the central complexity parameter L is never measured, and two equations as printed are circular. It needs a solid revision before I'd trust it.\n\nWhat's actually new: chaining the incremental step N times, carrying dual potentials that are optimal for the (n−1)-subproblem, plus the SparseReorder and cumulative-offset queue to keep the data structures compact on clustered matrices. The synthetic crowd model with three scenarios is a reasonable testbed, and verifying every run against dense Hungarian is the right discipline.\n\nWhere it falls short:\n\n1. The abstract claims 3.7–6.5× speedup, but Table 3 shows 1.1× at N=200 for S2. That's not a rounding issue; it's a contradiction with the paper's own data. Fix it.\n\n2. The whole complexity story rests on L ≪ k (Table 2). L is never measured and no bound is proven. Worse, the reported incremental runtimes grow roughly as N^2.7 (from 0.00046 s at N=200 to 2.98 s at N=5000), which is not what you'd expect from L=O(1). The speedups at N=5000 are still real, but the asymptotic claim is unsubstantiated. Measure L for each scenario and report it.\n\n3. The initialization in Eqs. (9)–(10) is circular: Y_n depends on X_n and X_n depends on Y_n. Most likely the max in Eq. (9) should be over i < n, but as printed the algorithm is not executable.\n\n4. No real video data, no MOTA/HOTA numbers, no code. For a paper titled 'Real-Time Crowd Tracking,' that's a gap. The synthetic results are fine for a complexity study, but they don't show the method works inside an actual tracker.\n\nWho gets value: someone working on exact data association for large crowds, or on incremental assignment. The speedups at N ≥ 1000 are worth knowing about, even with the caveats.\n\nRecommendation: send it to a referee. The core idea is likely correct and the author is transparent about the synthetic setup. But expect a major revision: fix the abstract range, measure L, fix the initialization, and release the code. If those are addressed, this could be a useful practical contribution.","headline":"Plausible incremental assignment for crowd graphs, but the abstract overstates the speedup range and the central complexity parameter L is unmeasured; needs revision before I'd trust it.","tokens_in":9871,"tokens_out":4518,"would_cite":false,"duration_ms":47119,"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 warm-started incremental assignment algorithm reproduces the exact optimal N×N matching of the Hungarian algorithm on block-sparse crowd graphs, with 3.7–6.5× speedup for N up to 5000.","keywords":["multi-object tracking","assignment problem","Hungarian algorithm","incremental algorithm","dual potentials","block-sparse matrix","data association","crowd analysis"],"falsifier":"Instrument the algorithm to record the average augmenting path length L for each N on real or synthetic crowd data; if L is not small relative to k (or is not bounded by O(1) empirically), then the O(N²L log k/C) bound loses to Hungarian. Alternatively, run the algorithm on non-clustered, uniform random cost matrices where the block-sparse assumption fails: if it is not substantially faster than Hungarian there, that would confirm the speedup is purely a structural artifact of cluster gating.","tokens_in":9056,"feed_emoji":"👥","tokens_out":5773,"duration_ms":55294,"temperature":0.7,"pith_summary":"This paper tries to prove that exact data association in dense-crowd tracking does not have to pay the Hungarian algorithm's O(N³) cost per frame. The key move is to exploit the block-sparse structure of crowd cost matrices—dense within clusters, forbidden across clusters—by building the assignment incrementally. After each step, the dual potentials are exactly optimal for the smaller subproblem, so adding the next person needs only a single short augmenting path search inside its own cluster. The paper claims this produces the same global optimum as Hungarian, verified on every run, while measuring 3.7–6.5× speedups on synthetic but realistic crowd scenes with 200 to 5,000 people. If it holds in real-world settings, trackers that currently resort to greedy or auction approximations could keep exact matching at frame rate.","feed_headline":"Exact crowd tracking 6.5× faster via incremental assignment","feed_subtitle":"Warm-started dual potentials make each new person one short augmenting path, beating Hungarian at the same optimum.","key_machinery":"The engine is the incremental extension of a perfect matching, chained from 1×1 to N×N, where the previous subproblem's exactly-optimal dual potentials serve as a certified warm start. The 'equality subgraph' — the set of edges whose slack is zero under the current potentials — is the object that carries the argument: a single augmenting path in it absorbs the new node. Two supporting mechanisms keep the search cheap: a diagonal-reordering invariant (SparseReorder) keeps the matching in canonical diagonal form after each augmentation, and a cumulative-offset priority queue implements the shortest-path search so that only valid, non-forbidden edges are scanned. The net effect is that each ext","core_discovery":"On the paper's own terms, the central discovery is that warm-starting from dual potentials that are exactly optimal for the (n−1)×(n−1) subproblem makes the n-th incremental extension a single augmenting-path search — a strictly stronger starting condition than the mere feasibility Hungarian maintains between its outer iterations. Complementary slackness is preserved by a diagonal-reordering invariant and a cumulative-offset priority queue, so the search only follows tight, valid edges and never leaves the new node's cluster. The paper proves by induction that the diagonal matching after each step is optimal for the n×n subproblem, and hence that the final N×N matching is exactly the Hungari","pith_inferences":["The paper asserts but never measures the average augmenting path length L; tracking L on real MOT20-style sequences would reveal whether the O(1) warm-start advantage survives beyond the synthetic cluster model.","The warm-start principle should extend to decremental matching (people leaving the scene) and to unbalanced assignment problems, both of which are routine in tracking; the paper lists these as future work, and they are natural next results.","If the incremental invariant holds for more general affinity functions — appearance embeddings, learned costs — the speedup could carry over to re-identification-based trackers, though block sparsity would need an analogous gating mechanism.","The comparison baseline is a dense Hungarian implementation; a sparse Hungarian variant might outperform the reported numbers for the incremental solver on some hardware, so the claimed speedup is partly a statement about the chosen baseline and cache behavior."],"forward_implications":["At 25–30 fps, exact assignment becomes real-time for scenes up to roughly 1,000 tracked people, where the dense Hungarian baseline already misses the frame budget.","The speedup grows with N and plateaus beyond 3,000 people, so large-scale events such as stadium exits stand to gain the most.","Because the final matching is provably identical to Hungarian's, the algorithm can replace Hungarian in existing SORT/ByteTrack-style pipelines with no change to association semantics.","The stronger subproblem-optimality condition used here suggests a general recipe: any solver that can certify optimality on a subproblem can be extended incrementally in one augmenting path.","On the paper's model, gating and cluster separation directly control runtime, implying that better detectors with tighter gates translate into faster exact association."],"fun_headline_variants":["Incremental assignment tracks crowds 6.5× faster, exactly optimal","Warm-started duals cut crowd tracking time 6.5×, same optimum","One augmenting path per person: optimal crowd tracking 6.5× faster","Exact crowd tracking from 200 to 5000 people now 6.5× faster","Cluster-sparse cost matrices yield 6.5× speedup in crowd tracking"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The speedup depends on the unmeasured assumption that each incremental augmenting path stays very short (length L far below the cluster size k, roughly constant in practice); if L grows toward N on harder data, the theoretical bound collapses to O(N³) and the advantage over Hungarian disappears.","fun_headline_variants_meta":{"raw":{"variants":["Incremental assignment tracks crowds 6.5× faster, exactly optimal","Warm-started duals cut crowd tracking time 6.5×, same optimum","One augmenting path per person: optimal crowd tracking 6.5× faster","Exact crowd tracking from 200 to 5000 people now 6.5× faster","Cluster-sparse cost matrices yield 6.5× speedup in crowd tracking"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000231,"raw_usage":{"total_tokens":1360,"prompt_tokens":817,"completion_tokens":543,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":443}},"tokens_in":561,"tokens_out":543,"duration_ms":5670,"temperature":1.0,"reasoning_tokens":443,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T07:38:56.858601+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument the algorithm to record the average augmenting path length L for each N on real or synthetic crowd data; if L is not small relative to k (or is not bounded by O(1) empirically), then the O(N²L log k/C) bound loses to Hungarian. Alternatively, run the algorithm on non-clustered, uniform random cost matrices where the block-sparse assumption fails: if it is not substantially faster than Hungarian there, that would confirm the speedup is purely a structural artifact of cluster gating.","supporting_citations":[],"review_version":1}