| paper | d4-conf-aaai-2026-3058 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1 (Linear time and space)
statement extracted from the paper’s text layer
Given a candidate set \(V\) and an explicit support of \(\tau\) complete evaluator judgment patterns with rational masses \(\mu_t\), compute the paper’s greedy denoising output: its total order, backward-edge set, and retained DAG, using edge weights \(W_\mu(u,v)=\sum_t\mu_t\mathbf{1}[t\text{ prefers }u\text{ to }v]\).
Treat evaluators as a population: each type is a complete pairwise judgment pattern over the fixed candidate set, and \(\mu_t\) is its population mass. Aggregate those masses into rational edge weights, then run the paper’s sink/source and maximum weighted-degree-difference denoiser; the task is to compute its output, not to find an optimal feedback arc set.
Covers the greedy denoising runtime result and its arbitrary-weight extension; leaves the exact feedback-arc optimization problem, the ground-truth recovery theorem, and the downstream empirical results unmirrored.
The strongest honest mirror is Mass-Weighted Preference-Graph Denoising, for one fixed prompt and candidate set \(V\). A type \(t\) is an evaluator’s complete judgment pattern over every pair of candidates, including ties or abstentions. The society is a rational distribution \(\mu\) over those types; \(\mu_t\) is the fraction of evaluators with pattern \(t\). The ensemble edge weight is then \(W_\mu(u,v)=\sum_t \mu_t\,\mathbf 1[t\text{ prefers }u\text{ to }v]\): the share of the evaluator population preferring \(u\) to \(v\).
The problem is to run the paper’s denoising procedure on this aggregate graph and return its total order \(\pi\), its backward-edge set \(R_\pi\), and the retained DAG. On the current graph, the procedure repeatedly places sinks at the end and sources at the beginning; when neither exists, it removes a vertex maximizing its weighted out-degree minus in-degree. A valid solution follows those choices, with any allowed tie-breaking. Its removed preference mass is \(D_\mu(\pi)=\sum_{(u,v)\in R_\pi}W_\mu(u,v)\). That quantity measures the dissent discarded by the output; the greedy procedure does not promise to minimize it globally.
My anchor is Appendix M, Theorem 1 (Linear time and space), proved in this paper. It says that, under Assumption 1—arc weights are integers in \(\{0,\ldots,k\}\) for a fixed \(k\ge1\)—the paper’s denoising algorithm runs in \(O(m)\) time and uses \(O(m)\) space, where \(m\) is the number of positive-weight arcs. The theorem is about computing the greedy denoising output, not about solving exact weighted feedback arc set.
For the continuous mirror, edge weights are rational masses rather than bounded integers. The paper’s Appendix M, Remark 1 says that the same procedure handles arbitrary real weights using a heap in \(O(m\log |V|)\) time. Thus the rational-mass version should take \(O(\tau |V|^2+m\log |V|)\) arithmetic operations from an explicit support of \(\tau\) types, with polynomial bit-cost in the input length \(L\). I expect this mirror to be tractable (Class A). For a finite panel of \(N\) evaluators, setting \(\mu_t=N_t/N\) recovers its normalized aggregate graph; the population representation makes the dependence on \(N\) disappear once the type masses are given.
A plausible regime is a large benchmark or annotation service in which many independent evaluators judge the same fixed candidate responses under a shared criterion. Types are complete judgment patterns for that prompt and candidate set; in a sufficiently large, repeated task, \(N\) annotators may greatly exceed the number \(\tau\) of distinct patterns observed. The paper’s ensemble is already built from evaluator graphs, and its theoretical section models \(N\) i.i.d. graphs, so treating the evaluators as a population is a recognizable extension of its setup. The scenario is not universal: if nearly every evaluator has a unique pattern, then \(\tau\) may approach \(N\) and the compression gains little.
A natural further question is the exact mass-weighted problem: given \(\mu\), find an order minimizing \(D_\mu(\pi)\). I expect hardness to transfer (Class B) when evaluator types may have cyclic judgment graphs: a society concentrated on one such type already represents an ordinary directed feedback-arc instance. The paper itself says in §3.3 that computing the optimal ordering is NP-hard, citing prior work, but it gives no numbered theorem for that claim, so I do not use it as an anchor.
The weak point in my case is that the anchor establishes fast computation of the paper’s heuristic denoiser, not tractability of its exact optimization objective. The continuous version also relies on the paper’s arbitrary-real-weight remark; Theorem 1’s linear bound assumes fixed bounded integer weights. I think the mirror remains credible because it preserves the actual ensemble-and-denoise task, and the fractional edge weights arise directly from the evaluator population.
Appendix M, Theorem 1 is a genuine complexity result, so “there is no named computational result” is not an argument here. The strongest negative case is narrower: the proposed population mirror has no computation beyond the paper’s existing weighted-graph computation.
For a fixed candidate set, let \(t\) be an evaluator’s complete pattern of pairwise judgments. The denoiser sees the population only through the aggregate edge weights
\[
W_\mu(u,v)=\sum_t \mu_t\,\mathbf{1}[t\text{ prefers }u\text{ to }v].
\]
Once those weights are formed, the type distribution has no further role: the output order and removed edges are functions of \(W_\mu\) alone. But the paper already defines its graph weights as real-valued and, in Appendix M, Remark 1, gives the arbitrary-real-weight version of the algorithm with a heap and \(O(m\log |V|)\) running time. Computing \(W_\mu\) from an explicit support adds only the direct summation over types. So the proposed mass-weighted denoising question is covered by the paper’s existing computational object, with the evaluator population serving as an interpretation of its edge weights. There is no separate population-level decision or optimization for this theorem to analyze.
The exact mass-weighted feedback-arc problem is not a stronger mirror of Theorem 1: it replaces the paper’s greedy algorithm and its runtime guarantee with a different optimization task. Section 3.3 already distinguishes that task from the algorithm the paper runs. It could motivate another question, but it does not rescue this anchor.
I would not reject the scenario on multiplicity grounds. A large annotation service could plausibly have many evaluators sharing judgment patterns, and the proposed type definition fits the task. That is the weakness in the negative case: the mirror is sensible as a population interpretation. My case against it is that, for this particular result, the population representation contributes no new computational question beyond arbitrary real-weighted graph denoising, which the paper already handles.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.