Falcon: Fast Proximal Linearization of Normalized Cuts for Unsupervised Image Segmentation
Authors: Xiao Zhang
Xiangyu Han
Xiwen Lai
Yao Sun
Pei Zhang
Xia Liu
Konrad Kording
Venue: ICLR 2026 Poster (2026)
Keywords: Unsupervised Segmentation
Graph Cut
Normalized Cut
Proximal Gradient Method
Kurdyka–Łojasiewicz (KL) Convergence
Primary area: applications to computer vision, audio, language, and other modalities
TL;DR: Falcon is a fast proximal-gradient solver for discrete K-way Normalized Cut, with Kurdyka–Łojasiewicz convergence guarantees, outperforming recursive NCut in speed and accuracy on six segmentation benchmarks.

Abstract: Current zero-shot unsupervised segmentation methods based on normalized cuts (NCut) face three key limitations. First, they rely on recursive bipartitions with repeated eigen-decompositions, making them prohibitively expensive at scale. Second, each split requires spectral relaxation followed by rounding, introducing layers of approximation where the final partition may diverge from the true NCut objective. Third, recursive bipartitioning offers no principled assurance of producing a stable $K$-way segmentation, and existing heuristics lack convergence guarantees. We propose \textbf{Falcon}, a proximal-gradient solver that directly optimizes the discrete $K$-way NCut objective without spectral relaxation. We prove linear convergence under the \textit{Kurdyka--\L{}ojasiewicz} (KL) property. Falcon computes closed-form gradient scores weighted by cluster volumes and performs row-wise one-hot proximal updates stabilized by inertia. A monotone backtracking scheme adaptively tunes the proximal parameter, ensuring non-decreasing NCut values. This design preserves discrete feasibility, removes repeated eigen-decomposition, and guarantees convergence. Across six benchmarks, Falcon outperforms the strongest official baseline (DiffCut) by wide margins, e.g., +13.2 mIoU on VOC, +27.7 on COCO-Object, and +3.1 on Cityscapes, while remaining competitive on Pascal Context. It also runs up to an order of magnitude faster than recursive NCut and scales more favorably in memory at high resolution, making it practical for larger token grids. By pairing pretrained foundation models with a principled NCut solver, Falcon sets a new state of the art across six benchmarks and achieves the best performance on 17 of 18 benchmark--encoder pairs, underscoring both its robustness and its generality in bridging the gap between unsupervised and supervised segmentation.

Published as a conference paper at ICLR 2026
FALCON: FAST PROXIMAL LINEARIZATION OF NOR- MALIZED CUTS FOR UNSUPERVISED IMAGE SEGMEN- TATION
Xiao Zhang
Xiangyu Han University of Pennsylvania
Xiwen Lai University of Pennsylvania
University of Pennsylvania
Yao Sun
Pei Zhang
Xia Liu
Hong Kong Polytechnic University
Wuhan University
University of Wollongong
Konrad Kording
University of Pennsylvania
ABSTRACT
Current zero-shot unsupervised segmentation methods based on normalized cuts (NCut) face three key limitations. First, they rely on recursive bipartitions with repeated sigen-decompositionn. making them prohibitively expensive at scale. Second, each split requires spectral relaxation followed by rounding, introduc- ing layers of approximation where the final partition may diverge from the true NCut objective. Third, recursive bipartitioning offers no principled assurance producing stable K K-way segmentation, and existing heuristics lack convergence guarantees. We propose Falcon, proximal-gradient solver that directly optimizes the discrete K K-way NCut objective without spectral relaxation. We prove lin- convergence under the closed-form gradient scores weighted by cluster volumes and performs row-wise one-hot proximal updates stabilized by inertia. A monotone backtracking scheme adaptively tunes the proximal parameter, ensuring non-decreasing NCut values. This design preserves discrete feasibility, removes repeated eigen-decomposition. and guarantees convergence. Across six benchmarks, Falcon outperforms the strongest official baseline (DiffCut) by wide margins, e.g., +13.2 mloU on VOC, +27.7 on COCO-Object, and +3.1 on Cityscapes, while remaining competitive Pascal Context. It also up NCut and scales more favorably in memory at high resolution, making it practical for larger token grids. By pairing pretrained foundation models with principled NCut solver, Falcon sets new state of the art across benchmarks and achieves pairs, underscoring both
(KL) property. Falcon computes
order of magnitude faster than recursive
the best performance on 17 of 18 benchmark-encoue its robustness and its generality bridging the gap between unsupervised and supervised segmentation.
INTRODUCTION
Semantic segmentation partitions image into regions whose pixels share the semantic mean- ing, such as belonging to the same object or stuff category. As a fundamental computer vision task, it underpins wide range of downstream applications, including image editing, medical imaging, scene understanding, and autonomous driving Wang et al. (2023a): Zhuu et al. (2016); Esser et al. (2023); Zhou et al. (201 Li et al. (002b);; Han et al, (2024). Over the past decade, semantic seg- mentation has advanced rapidly, driven first by Fully Convolutional Networks (FCNs) Long et al. (2015) and later by architectures such as SegNet Hu
al. (2018), U-Net WWan & Yang 202 }),
DeepLab Chen et al.) (2017). and PSPNet /Zhao et al. (2017), which improved multi-scale reason- ing and feature fusion. More recently, Transformer- based based models Dosovitskiy al. (2020) Oquab et al. (202)); Caron et al. (202 Xie et al. (2021); (2021):(Cheng [Chnn et al. (2022) and foundation segmentation
models such as SAM Ravi et al. (2024) have substantially strengthened segmentation quality and flexibility.
Coode available http://///aaaiooo////o//aaaaaaaa

---

Published as a conference paper at ICLR 2026
Despite this progress, most high--erformnn segmentation systems rely on dense pixel-level anno- tations, which are expensive and labor-intensive to obtain. This has motivated growing interest in unsupervised and zero-shot segmentation, where the goal is to discover semantically meaningful re- gions without task-specific mask supervision, often for categories not seen during training] Tian al.) ; Couairon et al. (2025); [Sick et al. (2024). Existing approaches roughly fall into two groups. One line relies representation learning and clustering objectives, such as STEGO Hamilton et al. 2002), Ji et al. 2011), and PICIE Cho et al. (2021), which learn or refine patch-level groupings through self-supervision. Another line combines pretrained visual features with classical group- ing principles such as graph partitioning and normalized euts (NCut), yielding strong training-free segmentation pipelines Wang et al. (2023bla), Couairon et al. (0055).
In this paper, we focus on the training-free zero-shot setting: a frozen pretrained encoder is used only at inference time, without mask annotations, task-specific finetuning, or adaptive self-training. This setting is particularly attractive because it separates representation learning from mask gener- ation and enables segmentation to be performed directly from general-purpose foundation features. Among training-frre free methods, graph-basee segmentation has recently shown strong performance. TokenCut Wang al. (203b)) and MaskCut Wang et al. (2023a) recursively apply normalized cut to token affnities extracted from sef-ssuperviee Vision Transformers, while DiffCut[Cuuaree 2025) further improves connectivity by incorporating diffusion priors. These methods demonstrate that strong pretrained features combined with graph partitioning can already produce competitive unsupervised masks.
al.
However, current NCut-based training-free pipelines still face three key limitations. First, they typically rely on recursive bipartitions, where each split requires new eigen-decomposition, this makes inference increasingly expensive as the token graph grows. Second, they optimize spectrally relaxed problem and then round the solution back to discrete labels, introducing layers of approx- imation such that the final partition may deviate from the original discrete K-way NCut objective. Third, recursive bipartitioning provides no principled assurance of producing stable K-way seg- mentation, and the resulting heuristics generally come without convergence guarantees. Together, these issues create a gap between the elegant combinatorial objective of NCut and the practical procedures used in modern zero-shot segmentation systems.
To address this gap, we propose Falcon, a fast proximal linearization method for directly optimiz- ing the discrete K-way NCut objective. Rather than recursively splitting the graph through spectral bipartitions, Falcon maintains global K-way one-hot assignment throughout optimization and up- dates it via closed-form row-wise proximal steps derived from the exact gradient of the objective. A monotone backtracking scheme adaptively adjusts the proximal parameter to ensure non-decreasing objective values, while the discrete one-hot structure preserved at every iteration. In this way, Fal- con removes repeated recursive eigen- digendeecompositinns from the solver itself, avoids relax-and-roum mismatch, and provides principled optimization framework with convergence guarantees under the hurdyka-Lojasiewice (KL) property.
Beyond its theoretical appeal, Falcon is also highly practical. Because it is fully vectorized and avoids recursive NCut passes, it substantially reduces runtime compared with prior graph-cut base- lines. Moreover, while dense token affinities remain quadratic in the number of tokens, Falcon scales more favorably in memory than prior NCut- methods at high resolution, making it more practical for larger token grids.
Our contributions are summarized as follows:
Method. We introduce Falcon, mooximal-gradicn solver for the discrete K-way NCut problem that preserves one-hot fcasibility throughout optimization. Each itcration computes closed-form gradient scores weighted by cluster volumes and performs row-wise one-hot proximal updates stabilized by inertia. This design directly optimizes the original discrete objective without spectral relaxation or recursive bipartitioning.
Convergence. We show that Falcon admits monotone backtracking scheme with non-decreasing objective values and prove convergence under the ular, the iterates have finite length and converge to critical point; when the KL exponent satisfies 0 < 2' the local convergence rate is at least linear.
(KL) framework. In partic-
Performance. Across six benchmarks and three pretrained encoders, Falcon achieves state-of-the- art unsupervised segmentation performance, obtaining the best results on 17 of 18 benchmark- encoder pairs. It also runs up to an order of magnitude faster than recursive NCut baselines and
2

---

Published as a conference paper at ICLR 2026
exhibits more favorable memory scaling at high resolution, demonstrating both robustness and prac- ticality training-free segmentation.
2 RELATED WORKS
Vision Foundation Models. Vision foundation models typically leverage unlabeled data to learn robust and generalizable representations. Early contrastive methods like MoCo He et al. (2020) and B BOL Grill et al. (2020) laid the groundwork for advanced frameworks such as SwAV Goyal
et al. (2021), DINO UNNOCaroo Caron et al. (2021); Oquab et al. (2023): Darcet et al. (2023): Siméoni et al. (2025), , and iBOT Zhou al. (202I), while masked autoencoders He al. (2022) have further re- fined reconstruction-bee based pre-training. Beyond purely visual approaches, multimodal pre-training has surged in prominence, with models like CLIP Radford al. (2021). BLIP Li et al. (2022a), and SigLIP et al. (2023); Tschannen al. (2025) aligning high-level image features to text. In parallel, diffusion- methods such as Stable Diffusion Rombach et al. (2021); Gupta et al. (2024) extend these capabilities by learning rich generative representations, enabling tasks ranging from zero-shot classification to semantic correspondence. Collectively, these developments high- light the efficacy of foundation models in scaling to large, diverse datasets and adapting readily to downstream tasks.
Semantic Segmentation. Semantic segmentation partitions an image into semantically coherent regions by labeling each pixel, enabling the understanding of the structured scene. It is broadly cat- egorized into supervised and unsupervised methods. Supervised segmentation, extensively studied
and achieving high accuracy Namekata et al. (2024); Wang et al. (2021); Cheng et al. (2021); Ravi jet al. (2024), relies on large-scale annotated datasets. Recent work has explored text based supervi- sion to miligatee the need for dense annotations Ranasinghe et al. (2023); Xu et al. (2022) Cha el al.
(2023); ; Ren et al. (2023). In contrast, unsupervised methods often require dataset-specifie training to achieve competitive performance| [iang et al. (2023): Feng et al. 2023);; Cho et al. (2021) g Li al.
2023), and zero-shot segmentation for unseen categories remains challenging. DiftSeg Tian et al.
2024 leverages self-attention maps from pre-trained diffusion model, applying KL-divergence-
based iterative merging for segmentation. DiffCut Couairon et al. (2025) improves upon this by extracting richer encoder features from the self-attention block of a Transformer and incorporating a recursive N-Cut Shi & Malik (200a)) algorithm.
Graph-based Image Segmentation. Early approaches, such as Normalized Cut (N-Cut) Shi & Ma- lik [ (2000a), optimized the segmentation problem through spectral graph theory, formalizing spectral clustering theory based on the N-Cut objective; yet, its computational limitations persisted. To im- prove efficiency and adaptability, [F & P (2004) proposed adaptive merging strategy that utilizes both intra-region and inter-region criteria, while Grady (206) introduced probabilistic random walk framework that leverages adjacent pixel relationships to handle complex textures and weak boundaries. Recent deep toSC Fan et al.] (2022), and DiffCut Couairon et al.) (2025), compute token-level similarities via self-superviser Transformer features but remain constrained by N-Cut's recursive bisection strategy and hard segmentation constraints.
approaches. such as TokenCut Wang al. (2022). Au-
Proximal Gradient Methods. Proximal gradient algorithms handle composite objectives that pair smooth data term with possibly nonsmooth regularizer frequently seen learning (c.g., spar- sity, total variation, simple constraints). A gradient step on the smooth part followed by a proximal step on the regularizer yields a simple, scalable routine with standard convergence guarantees and practical backtracking/lne--sacd implementations Parikh & Boyd (2014). The accelerated variant FISTA achieves the optimal O (1/k22 rate for convex problems. and monotone variants stabilize the objective along the iterates Beck Teboulle (2009); Chambolle & Dossal (015). For noncon- vex formulations common in modern models, convergence to a critical point can be justified under the Bandyka--Ljasiewiic framework and via blockwise/prox-linea updates Attouch et al. (2013);
Bolte et al.] (2014). Inertial extensions further improve empirical speed while retaining convergence guarantees under mild conditions Ochs et al. (2014).
3 METHODOLOGY
3.1 SEGMENTATION AS NCUT ON TOKENS
Graph-based segmentation casts image segmentation as partitioning a weighted graph. Following normalized-cut pipelines Wang al. 2002 2023a); Couairon al. (2025), we build undirected
3

---

Published as a conference paper at ICLR 2026
Image Feature Extraction
Fast Proximal Linearization of NOut
Nonlinear Adaptive Mask Refinement
Input Image
Affinity Matric
Lonwro
Output Mask
Htigh-re
Assigrell labds
Highnes
Yokara
Nost
Pretrained Encoder
Corairud Goal f
Num Labels
Tokans
1
Updaes
Upsample
11
Herraive
11
Refinmment
Plastral Projection
Figure 1: Overview of Falcon. (1) Image feature extraction: tokens are extracted from the input image. (2) Fast proximal linearization of NCut: an affinity matrix constructed between tokens, and the discrete --way assignment is iteratively updated by row-wise one-hot proximal steps. (3) Optional mask densification and refinement: the coarse loken-level mask is first densified intermediate grid and can then be paired with a lightweight pixel-level refiner such as PAMR or NAMR.
graph G (V, E)) with N nodes, one per d-dimensional token from Vision Transformer:
V (Ny) f: E F= [fi
fx] E RRx
(1)
We use a dense affinity graph (without self-loops) and form a nonnegative, symmetric similarity by row-normalizing features to unit & norm (cosine similarity), rescaling to [0, 1]. and applying clementwise power sharpening:
F = row www.o FF),
FFFF
W = ((A)
2
diag( (W) + O, (2)
where & maps similarities [0, (e.g., (ss) = max(s, 0) or min min-max scaling per image). We then define
d=W1 D diag(d)
Let (PI...., Px} } be a partition and let 24 E {0, denote the indicator vector of partition Pk- Stacking these indicators gives row-wise one-hot assignment matrix X (#,,...,, [x,] i.e. each token is assigned to exactly one cluster. The normalized
{0, 1 1)N8 satisfying X1 cut objective Shi & Malik (2000)
K
cut(PE, Pt) vol(Pr)
Neut(PI,..... Pk)
cut(Pa, Px)=
E
Wi.
vol(PA) = Σ de
iEP, JEN
iEP
(4)
Equivalently, minimizing NCut the same maximizing the normalized association (i.e., a sum of K generalized Rayleigh quotients)
((x)
= Σ k=
W σk
Neut( = --
(5)
Dzy
The problem is discrete and nonconvex; finding the exact optimum is NP-hard, which motivates principled relaxations and iterative schemes.
3.2 FALCON: FAST PROXIMAL. LINEARIZATION OF NCUT
Classical NCut pipelines typically optimize a relaxed continuous problem, extract one or few cigenvectors, and then convert the result back to discrete labels through recursive bipartitioning and rounding. Falcon instead operates directly iteration, it evaluates how favorable is to assign each token to each cluster under the exact gradient of the normalized association objective, and then projects each row back to valid one-hot label. proximal term acts as an inertia mechanism, discouraging unnecessary label flips and stabilizing the discrete updates, while a monotone backtracking rule automatically adjusts its strength to ensure non-decreasing objective values. In this way, Falcon performs principled local search the original discrete NCut objective, rather than relying on spectral relaxation and recursive splitting.
global discrete K K-way assignment. At each
Rather than relaxing the row-wise one-hot constraints, we model discreteness through the extended- valued composite objective
min X X
((X) h(X) + g(X),
h(X) f(x),
g(X) (v
(6)
4

---

Published as a conference paper at ICLR 2026
where fX E [0,1)N*K X1 1} is the set of row-wise one-hot assignments and by is its indicator (0 on V, +oo otherwise). We additionally enforce nonempty clusters algorithmically through a simple empty-cluster repair step if they arise, and only require Ux(X) 0 locally in the analysis, where
Uk ()= 23 Dar-
On (X E V: ex (X) > 0, vk), the map f is C² so h ff is smooth, while the nonsmooth part exactly encodes one-hot feasibility. No heuristic rounding is needed.
To derive the gradient of the smooth part efficiently, we introduce the cached quantities
G = WX E R N
(X @ G v= = === d E RK
(8)
so that = o Way is the intra-cluster association of cluster k, and uk = 0yz Dæy is its volume.
By the quotient rule,
ak
WE 9: Dxx).
vf(x) 20 -Dx Ph: of (9)
20
Here denotes column- wwie division by w.
For the nonsmooth part g. Falcon applies proximal projection onto discrete assignments. Let ( be the current iterate. If f is locally Li-Lipschizz neighborhood where en > then for any Ti 2 L the standard smoothness inequality gives a local quadratic minorizer of f:
f(Y) 2 f(x + (Vf(X()), Y - xx)) 2 Y - X (1) 12.
(10)
Maximizing this surrogate over the original discrete set V is row-separable. Because each feasible
row is one-hot, | 12 = is constant and - 2 Ilys - X 1 = 2/2 (2 x!1) - 1). so only the
cross term remains. This yields the dlsed-form row-wise update
a
((+1)
e.
arg mAXNE(K) A x
(1) = ((((
(11)
where ties are broken deterministically (e.g. by the smallest k). Here Mi is the first-order gain score
(t)
of assigning token to cluster k; while the additive term xx(() acts as an inertia bonus that favors keeping the current label unless another assignment is sufficiently better. Thus, each step remains fully discrete and feasible while avoiding gratuitous label flips.
Because L, is unknown and may vary, we adopt monotone line search on T3t start with T. Tu 0; II accept
compute equation]
((x(1-)) 2 ((x()) 8
8 E (0,
(12)
otherwise set Te + YTB (y > 1) and recompute. This Armijo-type sufficient increase guarantees monotonic ascent of and finite termination of the backtracking. Equivalently, in the minimization view for & ((X) = ((x) + (X). equation 12 is identical to
x (( < (x ÔT:
which we use in the Kurdyka-LLoasiewiin based analysis (Appendix
Convergence under the Kurdyka--.ojasieviee (KI.) Property. Falcon forward-backward scheme with monotone backtracking: the update equation IT is the proximal step for g = by (row- wise projection), driven by the linearization of h -f. while equation 12 provides quantitative acceptance rule. Under standard conditions, such as bounded sublevel sets, local Lipschitz con- tinuity of Vf in positive-volume neighborhood, and the KL property of & at limit point, the generated sequence enjoys: (i) finite termination of backtracking and sufficient descent of 4; (ii) uniform subgradient- step bound; (iii) convergence of the whole sequence] and (iv) local linear rates when the KL exponent satisfies 0 < J. The precise assumptions, lemmas, and proof (following Jia al. (2023). Section 4) are given in Appendix C with the notational correspondence T, < 7 and the same 6.
"Here, "global convergence" refers to the convergence of the entire sequence stationary point, rather than convergence glohal optimum of the NP-hard NCut objective.
5

---

Published as a conference paper at ICLR 2026
Imput Image
Nonlinear Pixel-Adaptive Mask Refinement (NAMR)
Pixel-Adaptive Mask Refinement (PAMIR
Output Mask Label
Nonlinear Affinity
Averaged Affinity
Lincar Affinity
t=T-1
Average
Figure 2: NAMR vs PAMR. NAMR computes pixel affinities using a nonlinear operator and av- erages them across multiple temperatures. In contrast, PAMR uses a linear operator and computes affinities at a single temperature. After affinities are obtained, mask labels are iteratively updated based on them.
Our discrete NCut objective involves polynomial expressions of the affinity matrix together with one-hot constraints on cluster assignments, and is therefore semi semi-algebraic. Semi-algebraic func- tions satisfy the KL property [Bolte al. (2007); Attouch al. (2013). Under the additional dition that the KI. exponent satisfies 0 S 2. our proximal-gradien scheme enjoys least local linear convergence rate near stationary points, addition to the monotonic descent guaranteed by the backtracking line search.
3.3 SEGMENTATION MASK GENERATION
K......KJaa. The optimization in Section 3.2 yields a discrete token-level assignment & E {l..... KJ j on transformer token grid. While this already provides a coarse segmentation, its spatial resolution (h, w) is much lower than that of the input image. We therefore first perform a lightweight densifica- tion intermediate grid of size (Hm, Wm) (e.g., 128 128), which improves spatial coherence while remaining computationally inexpensive.
We upsample the discrete label map by nearest-neighbor interpolation to obtain i E {1...., K) "
parallel, the feature map is bilinearly upsampled to RCx x xWi;; denote uu, E RC the feature embedding at location (u, v) the intermediate grid. The nearest- step preserves sharp boundaries in the label field, whereas bilinear interpolation maintains smooth variation in the embedding space.
From ? we form the one-hot mask tensor M E (0, 10.1)KxH=xx.... with MR 1 iff lu,. k. The prototype of partition the average embedding of its assigned locations:
Hm Wm -u=l ME,,,0 Zu.v
P&
Hm EVm MR,,,F
Pk ER.
(13)
These prototypes summarize cluster statistics on the intermediate grid. Each location then reas- signed to the prototype with the largest dot- dot-product similarity:
Ey
arg max Zu.oPk. KE[K]
(14)
yielding the refined mask l" E (l,..., , duces tokenization artifacts and improves spatial coherence, and be further upsampled to the original image size if desired.
This intermediate-resolttion densification re-
3.4 PEVEL-LEVEL MASK REFINEMENT
Falcon's 's core contribution is the discrete NCut solver described in Section 3.2 The refinement mod- ule optional and independent of the solver: included only form a complete segmentation pipeline and to align our evaluation protocol with prior work. particular, Falcon can be paired with refiner, with PAMR, with DenseCRF, or with other lightweight post-processing methods.
Starting from the coammeddiat--esolutiinn mask, we optionally recover pixel-level mask aligned with image boundaries by applying a lightweight refinement step on top of a nearest-neighhoy (NN) upsampled initialization. Classical refiners such DenseCRF can improve boundary adherence, but may introduce additional applemmentation-deeeddeee overhead or require solving global systems, making them less convenient in modern GPU-heavy pipelines.
daapive Mask Refinement (PAMR). We adopt PAMR as a lightweight edge-aware refiner following prior work. Let T E H x3 be the RGB image and Mo [0, [][C+I)xHxxW the

---

Published as a conference paper at ICLR 2026
NN-upsampled class-probe class-probability tensor (including background). For pixel (i, and local neigh- borhood N (i. (built from small x 3 kernels with dilations), PAMR forms per-direction affinities by softmax over negative, locally normalized RGB differences:
+ +ots)) Σ ((r))N(())))) exp ( F(I.s) //,r otss)) F(JeJ, It,)) Σ
exp ( - F(Lg l,m)
Oijjdnn
where di.j is the local standard deviation around (i.j) and e > 0 ensures numerical stability. Refinement proceeds by T iterations of locally weighted averaging:
M Ri =
Σ (IJ))
Oiiiia adm
L 1=1,..., M = Mo-
Each update is a convex combination across neighbors (row-stochastic weights), yielding an anisotropic diffusion that respects intensity edges and is stable under small T.
Nonlinear Adaptive Mask Refinement (NAMR). To show that Falcon is not tied to a spe- cific refinement choice, we also instantiate a simple nonlinear variant, NAMR. NAMR replaces with a contrast-amplifedd discrepancy 7r obtained by pointwise nonlinearity (e.g.. Φ(x) = I + 1.5 (z)(x) before taking absolute values and channel averaging, and aggregates multiple temperature values
(Tr.j. (- (e))) M (Mo),, Mr= = ITI Σ M
(- TTToi (-
(T) softmax((.)EN(.)))) L.dnn
TET
Small T emphasizes edge preservation, while larger favors smoothing: averaging across temper- atures improves robustness across textures and scales. In experiments, we compare several post- processing choices-includee NN only, PAMR, and NAMR in the main setting, and DenseCRF in controlled comparisons to show that Falcon's 's gains do not depend on any particular refiner.
4 EXPERIMENTS
4.1
IMPLEMENTATION DETAILS
We evaluate Falcon in the training-free zero-shot setting, where a frozen pretrained encoder is used only at inference time, without mask annotations, task-specific finetuning, or adaptive self-training.
Datasets and Metrics. We evaluate Falcon on six widely used benchmarks spamning objects, scenes, and urban environments: Pascal VOC [Everingham et al. (2013) (20 classes), Pascal Context Mot- taghi et al. (2014) (59 classes with contextual labels), COCO-O COCO-Stuff277 27Lin Lin et al. (2014) (27 consolidated classes), Cityscapes DisscapesCCrrttss et al. (2016) (27 urban categories), and ADE20K Zhou et al. (2019a) (150 classes). Segmentation quality is measured by (mloU). Since Falcon produces class-agnostir masks, we align pre- dictions with ground-truth labels using the Hungarian algorithm Kuhn (1955), with many-to-one mapping for background categories. As a secondary metric, we report Pixel Accuracy (Pixel Acc.), i.c., the proportion of correctly classified pixels after the same alignment procedure.
et al. (2014) (80 categories),
mean ditersection-vver-uut
Settings. Following the evaluation protocol of previous work for fair comparison in the training- free setting, all input images are resized to 1024 x 1024. Features are extracted at lower resolu- tions: 32 x 32 from diffusion models Gupta et al. (2024) (prompt-free, t=50) and 64 x 64 from DINOv3 Siméoni et al. 2025)). followed by & normalization and an a-power transformation on affinities. Falcon first produces an initial token-level segmentation, which is then densified on an intermediate 128 x 128 grid as described in Section 3.4 before any optional pixel-level refinement.
The number segments K is estimated before Falcon optimization via simple spectral heuristic: we compute the cigenvalues of the normalized affinity matrix once, count eigenmodes below negative cutoff x, and clamp the resulting value predefined range. We a single x per dataset rather than tuning it per image, reflecting dataset-specific annotation granularity. In practice, this spectral step contributes only small fraction of the total runtime, and Section 4.4 Figure shows that performance remains stable over a reasonable range of x values.
Unless otherwise noted, Falcon is paired with PAMR in the main setting to align with prior training- free segmentation pipelines; additionally report no-refinement and NAMR variants, and include

---

Published as a conference paper at ICLR 2026
Table 1: Unsupervised segmentation on six benchmarks (higher is better). Reports mloU.
MaskCLIP Dong et al. (2023) requires text prompts. i; reported by us. AutoSC, DiffCut, and Falcon use the SSD-1B encoder the main setting.
Method
mloU (%)
VOC
Context
COCO-Objec
COCO-Stulf-27
Cityscapes
ADE20K
MaskCIIIP Dong al.
2023
38.80
23.60
20.60
19.60
10.00
9.80
MaskCul Wang et al.
2
53.80
43.40
30.10
41.70
18.70
35.70
DiftSed
49.80
48.80
23.20
44.20
16.80
37.70
DiffCul Conatron
4025
65.20
56.50
34.10
49.10
30.60
44.30
AutoSCT (ours, refined)
77.57
57.27
61.56
49.39
25.72
40.10
DiffCut' (ours, refined)
71.68
58.17
61.65
49.18
30.77
44.10
Falcon (ours)
78.40
57.15
61.80
50.37
33.69
45.17
controlled DenseCRF comparisons in the appendix. Experiments are run in PyTorch on single NVIDIA RTX 4090.
Mask refinement. Since Falcon's 's core contribution is the discrete NCut solver, refinement is treated as optional post-processing component used to align with prior evaluation protocols and to test refiner-agnostic robustness.
PAMR, we follow the standard DifiCut setting: 3x3 kernels with dilations D {1, 2, 4, 8), yielding P = 8| D directional filters, T = 10 refinement steps, per-pixel local variance oi over (i.j). and ε = 10
Gradients are not propagated through the refiner. For 1.5 ELU(x) to construct (r and average over a temperature set T = {0.06, 0.08, 0.10, 0.12, 0.14, 0.16, 0.18}. Unless noted otherwise, no additional data-fidelity mixing with Mo is applied. The NN baseline simply upsamples the intermediate mask to (H, W) via nearest-neighhor interpolation without further refinement.
NAMR, we use the same neighborhoods and T 10, define 6(x)
4.2
MAIN RESULTS
Overall performance. Table reports mloU on six standard benchmarks. Unless noted otherwise, AutoSC, DiffCut, and Falcon use the SSD-IB encoder with PAMR refinement, matching the set- ting highlighted in Table Our main comparison focuses training-free methods, which match Falcon's setting of using frozen pretrained features without additional training.
Relative to the strongest published training-free baseline, DiffCut Couairon et al. (2025), Falcon establishes a new state of the art on five of six datasets: VOC (+13.2, 78.40 vs. 65.2), COCO- Object (+27.7, 61.80 vs. 34. 1), COCO-Stuff-27 (+1.3, 50.37 vs. 49.1), Cityscapes (+3.1, 33.69 vs. 30.6), and ADE20K (+0.9, 45.17 44.3); Pascal Context, Falcon remains competitive (57.15 vs. 56.5). These results show that Falcon consistently improves upon the prior training-free state of the art.
We further include refined re-implementations of DiffCut and AutoSC (1) under unified pipeline for a stronger controlled comparison. While these enhanced baselines outperform their official coun- terparts (e.g., DiffCut! reaches 61.65 on COCO-Object and 58.17 on Context), Falcon still surpasses them in most cases: +0.83 on VOC, +0.98 on COCO-Stuff-211 +2.92 on Cityscapes, and +0.77 on ADE20K. Averaged over all six datasets, Falcon attains 54.43 mloU, exceeding the strongest per- dataset controlled baseline by +0.77 points on average.
Compared with earlier prompt-free methods (MaskCut, DiffSeg) and stronger controlled re- implementations (DiffCut", AutoSCt), Falcon delivers robust gains across both object-centric and scene-centric benchmarks, supporting the effectiveness of directly optimizing the discrete K-way NCut objective.
Across encoders and refinement. Table analyzes robustness across feature backbones (SSD- 1B, DINOv3-B, SD2.1) and post-processing choices (none PAMR / NAMR). SSD-1B yields the strongest overall results and serves as our default setting. Refinement effects are dataset-dependent on scene-heavy datasets (Cityscapes, COCO-Stum Stuff-27, ADE20K), PAMR and NAMR usually pro- vide additional gains, whereas on object-centric VOC, the raw Falcon segmentation already very strong (79.15 15 without refinement), DINOv3-B and SD2. trail SSD-IB B in absolute performance but preserve the same qualitative trend across post- post-processing choices.
8

---

Published as a conference paper at ICLR 2026
Table 2: Unsupervised segmentation across encoders and post-processiee choices (higher is
better). Columns report Pixel Acc. (%) and mloU (%) for each encoder.
Settings
SSD-1B
DINOv3-B
SD2.1
Benchmark
Method
Relin.
Pixel Acc. (%)
mioU (%)
Pixel Acc. (%)
mloU
Pixel Acc, (%)
mloL (%)
DitICut
none
83.55
28.35
28.38
12.75
57.29
17.09
Cityscapes
(ouns, relined)
panur
namir
85.91
86.02
30.95
29.48
12.37
65.40
19.41
mone
83.08
30.56
63.26
25.29
78.56
26.65
pamr
manir
83.65
33.50
63.88
24.41
82.87
28.21
DitCCut
81.60 31.60
68.40
76.71
59.41
70.41
50.88
VOC
(ours, refined)
punir
82.04
81.81
71.68
71.94
76.54
76.66
65. 63
65.73
71.57
71.40
60.16
60.41
none
88, 12
79.15
81.48
76.44
86.78
77.94
Falcon
pani
78.40
83.79
75.27
86.51
77:10
namr
88, 28
78.83
81.19
75.62
86.78
77.35
77.86
54.55
61.14
37.69
70.45
45.66
DiffCut
(ours, refined)
pamr
80.2/
80.36
58.17
58.10
61.24
61.16
43.04
42 63
74.02
73.57
52.05
52.02
Context
78.47
41.24
52.38
Falcon
pamr
80.53
57. 15
62:22
45.00
78.04
55.56
80.48
57.23
62.31
45.21
77.84
55.39
DilCCut!
none
74.97
COCO-
(ours, refined)
namir
pumr
78.19
78.47
49.18
24.43
13.54
67.37
37.43
Stuff
75.85
Faleon
punur
78.56
50.37
48.82
30.32
75.07
46.41
78.39
46.18
DiffCut!
mone
80.28
62.96
72.42
52.71
67.36
48.82
77.44
61.65
71.74
59.11
67.93
51.70
(ours, refined)
namr
78.60
62.94
71.75
55.63
Object
none
84.67
63.98
69.53
62.19
76.17
59.21
Falcon
pamr
21.22
61.80
67.70
59.69
73.76
58.21
namr
82.30
68.31
DifCCut
none
72.
09.55
44.40
12.54
29.23
28.05
25.85
26.50
65.82
60:43
41.92
38.38
ADE20K
(ours, relined)
mamir
71.84
44.53
28.86
26.32
64.71
41.56
none
07.64
43.05
50.15
41.87
68.33
41.11
Falcon
70.85
45.17
60.20
42.29
70.73
42.62
nami
70.38
45.06
60.04
42.44
70.42
42.70
5006
1000
1509
2009
222
50.55
Figure 3: End-to-end evaluation time across datasets. Falcon substantially reduces inference time relative to recursive NCut baselines on a single RTX 4090.
Importantly, Falcon consistently outperforms DiffCutt across encoders and refiners, showing that its gains come from the solver ule. This supports the refiner-agnostic design of Falcon and its robustness across diverse pretrained representations.
itself rather than from any particular backbone or post-processing mod-
4.3 RUNTIME AND EFFICIENCY
Table and the stacked-bar plots report the end-to-end evaluation time across Data Preparation, Feature Extraction. and Mask Generation. The first two stages are identical across methods, so the runtime differences stem primarily from the graph-partitioning solver. In the main paper,

---

Published as a conference paper at ICLR 2026
mtou
IbI milu
XV14
335
314
20
75.37
22.13
18
20
6.4
1:30
000
0.38
Figure 4: Hyperparameter sensitivity. Impact of the power parameter ar (left) and spectral cutoff (right) on mIoU for Cityscapes and VOC.
therefore emphasize end-to-end comparisons, while appendix tables further decompose inference into graph-cut time and refinement time, including controlled comparisons against MaskCut and DenseCRF-basee variants.
Falcon consistently delivers the fastest Mask Generation time, yielding the lowest overall Total Time. The speedup is particularly striking when token counts are high: for example, on DINOv3- B, Cityscapes, Falcon reduces Total Time from 784.04s (DiffCut) to 87.47s, and Mask Generation from 747.97s to 52.49s. These results show that Falcon scales much more favorably than recursive NCut solvers as token resolution increases. This strong practical efficiency is also consistent with our convergence analysis: in practice, Falcon typically converges in very few outer iterations, so the monotone proximal scheme translates into fast solver.
4.4 HYPERPARAMETER TUNING STUDIES
Power Transformation in the Affinity Matrix. In high-dimensional embedding spaces, graph- based methods often suffer from similarity collapse, where pairwise affinities become nearly uni- form and blur true cluster boundaries. To address this, we apply a power transformation that non- linearly rescales affinities: stronger connections are amplified while weaker ones suppressed. This contrast enhancement sharpens the affinity structure, reduces sensitivity to noise, and yields more stable partitions. As shown in Figure 4] tuning the power parameter a leads to promising gains in mean Intersection-over-Uniii (mloU), validating the effectiveness of this transformation for clarifying semantic structure.
Spectral Threshold for K Selection. The number of segments K is estimated via a simple spec- tral heuristic: compute the eigenvalues of the normalized affinity matrix once, count those below a negative cutoff к, and clamp the result to a predefined range. practice, we use single per dataset rather than tuning it per image. This dataset-level choice reflects annotation granularity: object-centric datasets such VOC typically favor smaller effective number of segments, whereas denser scene-centric datasets such as Cityscapes or COCO-Stufi tend to favor larger values.
Varying does affect segmentation quality, but the effect is generally moderate over semantically reasonable range. As shown Figure 4 Cityscapes and Paseal VOC exhibit slightly different sensitivities to K, yet overall performance remains relatively stable. This suggests that Falcon is robust the precise cutoff, while still allowing explicit control over segmentation granularity.
CONCLUSION
We introduced Falcon, a proximal-gradient solver for the discrete K-way NCut objective that op- erates directly on one-hot assignments, avoids spectral relaxation and recursive bipartitioning. pre- serves feasibility throughout optimization, and enjoys convergence guarantees under the Kurdtyka- Lojasiewicz framework. Across six benchmarks and three pretrained encoders, Falcon achieves of-te-of-the-ar unsupervised segmentation performance on 17 of 18 benchmark-ent -nncoer pairs. also runs up to order of magnitude faster than recursive NCut methods and scales more favorably in memory high resolution, making it practical for larger token graphs in training-free segmenta- tion. These results highlight the value of treating NCut as a principled discrete optimization problem rather than sequence of relax-and-round heuristics. More broadly, Falcon suggests that combining foundation-mode model features with efficient discrete solvers is a promising direction for training free segmentation, pseudo-mask generation, and other structured grouping problems beyond semantic segmentation.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Hedy Attouch, Jérôme Bolte, and Benar Svaiter. Convergence of descent methods for semi- algebraic and tame problems: Proximal algorithms, forward-backwandd splitting, and regu-
larized gauss- methods. Mathematical Programming. 137(1-2):91-129, 2013. doi:
10.1007761100070011-444444
Amir Beck and Mare Teboulle. fast iterative shrinkage-thresholling algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2(1):183-202, 2009, doi: 00.11370800716522
Jéröme Bolte, Aris Daniliidis, Adrian Lewis, and Masahiro Shiota. Clarke subgradients of strati- fiable functions. SIAM Journal on Optimization, 18(2):556- 2007. doi: 137/0666666772998
Jéröme Bolte, Shoham Sabach, and Marc Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, (46112))459-44999 2014. doi: 10.100776101077013-0000--1
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9650-9660, 2021.
Junbum Cha, Jonghwan Mun, and Byungseok Roh. Learning to generate text-grounded mask for open- world semantic segmentation from only image-text pairs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11165-11174, 2023.
Antonin Chambolle and Charles Dossal. On the convergence of the iterates of the FISTA al- gorithm. Journal of Optimization Theory and Applications, 166(3):968-995)) 982, 2015. doi:
10.10077610057-055544444444
Liang-Chieh Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE transactions on pattern analysis and machine intelligence, 40(4): 834-848, 2017.
Bowen Cheng, Alex Schwing, and Alexander Kirillov. Per-pixel classification is all you need for semantic segmentation. Advances in neural information processing systems, 34: 34:17864-17875. 2021.
Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar. Masked- attention mask transformer for universal image segmentation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1290-1299, 2022.
Jang Hyun Cho, Utkarsh Mall, Kavita Bala, and Bharath Hariharan. Picie: Unsupervised semantic segmentation using invariance and equivariance in clustering. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 16794-16804, 2021.
Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schicle. The cityscapes dataset for semantic urban scene understanding. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3213-3223, 2016.
Paul Couairon, Mustafa Shukor, Jean-Emmanuel Haugeard, Matthieu Cord, and Nicolas Thome. Diffcut: Catalyzing zero-shot semantic segmentation with diffusion features and recursive nor- malized cut. Advances in Neural Information Processing Systems, 07:13548-1351111 2025.
Timothée Darcet, Maxime Oquab, Julien Mairal, and Piotr Bojanowski. Vision transformers need registers, 2023.
Xiaoyi Dong, Jianmin Bao, Yinglin Zheng, Ting Zhang, Dongdong Chen, Hao Yang, Ming Zeng, Weiming Zhang, Lu Yuan, Dong Chen, et al. Maskelip: Masked self-distillation advances con- trastive language-image pretraining. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10995-11005, 2023.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 19299 2020.
11

---

Published as a conference paper at ICLR 2026
Patrick Esser, Johnathan Chiu, Parmida Atighehchian, Jonathan Granskog, and Anastasis Germani- dis. Structure and content-guided video synthesis with diffusion models. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 7346-7356, 2023.
Mark Everingham, SM Ali Eslami, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes challenge: A retrospective. International journal of computer vision, 111:88-166, 2015.
Felzenszwalb P F and Huttenlocher D P. Efficient graph-base based image segmentation. International Journal of Computer Vision, 2004.
Jicong Fan, Yiheng Tu, Zhao Zhang, Mingbo Zhao, and Haijun Zhang. simple approach to automated spectral clustering. NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN
Qianli Feng, Raghudeep Gadde, Wentong Liao, Eduard Ramon, and Aleix Martinez. Network-free unsupervised semantic segmentation with synthetic images. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 23602-23610, 2023.
Priya Goyal, Mathilde Caron, Benjamin Lefaudeux, Min Xu, Pengchao Wang, Vivek Pai, Mannat Singh, Vitaliy Liptchinsky, Ishan Misra, Armand Joulin, et al. Self-supervised pretraining of visual features in the wild. arXiv preprint 1rxXiv:2003009900 2021.
L. Grady. Random walks for image segmentation. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2006.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach self-supervised learning. Advances in neural information processing systems, 33:21271-2123 2020.
Yatharth Gupta, Vishnu V Jaddipal, Harish Prabhala, Sayak Paul, and Patrick Von Platen. Pro- gressive knowledge distillation of stable diffusion xl using layer level loss. arXiv preprint arXiv:2401.02677, 2024.
Mark Hamilton, Zhoutong Zhang, Bharath Hariharan, Noah Snavely, and William T Freeman. Unsupervised semantic segmentation by distilling feature correspondences. arXiv preprint arXiv:2203.08414 2022.
Xiangyu Han, Zhen Jia, Boyi Li, Yan Wang, Boris Ivanovic, Yurong You, Lingjie Liu, Yue Wang. Marco Pavone, Chen Feng, et al. Extrapolated urban view synthesis benchmark. arXiv preprint arXiv:2412.05256, 2024.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-97227 2020.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li. Piotr Dollár, and Ross Girshick. Masked au- toencoders are scalable vision learners. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 16000-16009, 2022.
Jie Hu, Li Shen, and Gang Sun. Squeeze-and-excitatii networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7132-7141, 2018.
Xu Ji, Joao Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9865-9874, 2019.
Xiaoxi Jia, Christian Kanzow, and Patrick Mchlitz. Convergence analysis of the proximal gradient method in the presence of the Eojsssewwiaaaiiiiiiiee.o property without global lipschitz assump- tions. SIAM Journal on Optimization, 33(4)330383056, 2023. doi: 10. 00.117723M1548222 URL
htttps://dds http///i.oggg..... wtt.g//.....1....... 548293]
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics
quarterly, 2(1-2):83-97, 1955.
12

---

Published as a conference paper at ICLR 2026
Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. Blip: Bootstrapping language-iman imase pre- training for unified vision-language understanding and generation. In International conference on machine learning, pp.
PMLR, 2022a.
Kehan Li, Zhennan Wang, Zesen Cheng, Runyi Yu, Yian Zhao, Guoli Song, Chang Liu, Li Yuan, and Jie Chen. Acseg: Adaptive conceptualization for unsupervised semantic segmentation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 7162- 7172, 2023.
Qi Li, Yue Wang, Yilun Wang. and Hang Zhao. Hdmapnet: An online hd map construction and evaluation framework. In 2022 International Conference on Robotics and Automation (ICRA), pp. 4628-4634. IEEE, 2022b.
Feng Liang, Bichen Wu, Xiaoliang Dai, Kunpeng Li, Yinan Zhao, Hang Zhang, Peizhao Zhang, Peter Vajda, and Diana Marculescu. vocablocyy semantic segmentation with mask-adapted clip. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 7061-7070, 2023.
Tsung-Y Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects context. In Computer vision-ECCV 2014: 13th European conference, zurich, Switzerland, September 6- 12, 2014, pro- ceedings, part 13, pp. 740-755. Springer, 2014.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and paltern recognition, pp. 3431-3440, 2015.
Roozbeh Mottaghi, Xianjie Chen, Xiaobai Liu, Nam-Gyu Cho, Seong- Seong-Whan Whan Lee, Sanja Fidler, Raquel Urtasun, and Alan Yuille. The role of context for object detection and semantic seg- mentation in the wild. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 891-898, 2014.
Koichi Namekata, Amirmojtaba Sabour, Sanja Fidler, and Seung Wook Kim. Emerdiff: Emerging pixel-level semantic knowledge in diffusion models. arXiv preprint arXiv:2401.11739, 2024.
Peter Ochs, Yunjin Chen, Thomas Brox, and Thomas Pock. ipiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal on Imaging Sciences, 7(2):1388-141)) 2014. doi: 10.1137//30042954
Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Mare Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al. Dinov2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07193, 2023.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, (3):127-239, 2014. doi: 10.1561/2400000000..
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp- 8748-8763, PmLR, 2021.
Kanchana Ranasinghe, Brandon McKinzie, Sachin Ravi, Yinfei Yang, Alexander Toshev, and Jonathon Shlens. Perceptual grouping in contrastive vasion-language models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5571-5584, 2023.
Nikhila Ravi, Valentin Gabeur, Yuan-Ting Hu, Ronghang Hu, Chaitanya Ryali, Tengyu Ma, Haitham Khedr, Roman Rädle, Chloe Rolland, I Laura Gustafson, Eric Mintun, Junting Pan, Kalyan Va- sudev Alwala, Nicolas Carion, Chao-Yuse Wu, Ross Girshick, Piotr Dollár, and Christoph Fe- ichtenhofer. Sam 2: Segment anything in images and videos. arXiv preprint arXiv:2408.007 2024. URL https: / //aaaxax// araai.av... org. / abs / 2400 00714
Pengzhen Ren, Changlin Li, Hang Xu. Yi Zhu, Guangrun Wang, Jianzhuang Liu, Xiaojun Chang, and Xiaodan Liang. Viewco: Discovering text-supervised segmentation masks via multi-view semantic consistency, arXiv preprint arXiv:2302. 10307, 2023.
13

---

Published as a conference paper at ICLR 2026
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models, 2021.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000a.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEFE Transactions on pattern analysis and machine intelligence, 22(8):888-906 2000b.
Leon Sick, Dominik Engel, Pedro Hermosilla, and Timo Ropinski. Unsupervised semantic segmen- tation through depth-guided feature correlation and sampling. In Proceedings of the IEEÉ/CVF Conference Computer Vision and Pattern Recognition, pp. 3637-3646. 2024.
Oriane Siméoni, Huy V. Vo, Maximilian Seitzer, Federico Baldassarre, Maxime Oquab, Cijo Jose, Vasil Khalidov, Marc Szafraniec, Seungeun Yi, Michaël Ramamonjisoa, Francisco Massa, Daniel Haziza, Luca Wehrstedt, Jianyuan Wang, Timothée Darcet, Théo Moutakanni, Leonel Sentana, Claire Roberts, Andrea Vedaldi, Jamie Tolan, John Brandt, Camille Couprie, Julien Mairal, Hervé Jégou, Patrick Labatut, and Piotr Bojanowski. DINOv3, 2025. URL htttt:t//axxiii org/
2208/2508.00 10104
Junjiao Tian, Lavisha Aggarwal, Andrea Colaco, Zsolt Kira, and Mar Gonzalez-Franco. Diffuse attend and segment: Unsupervised zero-shot segmentation using stable diffusion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3554-3563, 2024.
Michael Tschannen, Alexey Gritsenko, Xiao Wang, Muhammad Ferjad Naeem, Ibrahim Alabdul- mohsin, Nikhil Parthasarathy, Talfan Evans, Lucas Beyer, Ye Xia, Basil Mustafa, et al. Siglip 2: Multilingual vision- languale encoders with improved semantic understanding, localization, and dense features. arXiv preprini 2rXiv:2502.14788 2025.
Huiyu Wang, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang-Chich Chen. Max-deeplab: End- to-end panoptic segmentation with mask transformers. In Proceedings of the IEEE/CVF confer- on computer vision and pattern recognition, pp.
2021.
S Wang and F Yang. Remote sensing image semantic segmentation method based u-net feature fusion optimization strategy. Comput. Sci, 6828):162-168, 2021.
Xudong Wang, Rohit Girdhar, Stella X Yu, and Ishan Misra. Cut and learn for unsupervised object detection and instance segmentation. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 3124-3134. 2023a.
Yangtao Wang. Xi Shen, Shell Xu Hu, Yuan Yuan, James L. Crowley, and Dominique Vaufreydaz. Self-supervised transformers for unsupervised object discovery using normalized cut. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 14553, June 2022.
Yangtao Wang, Xi Shen, Yuan Yuan, Yuming Du, Maomao Li, Shell Xu Hu, James Crowley, and Dominique Vaufreydaz. Tokencut: Segmenting objects in images and videos with self-supervised transformer and normalized cut. IEEE transactions on pattern analysis and machine intelligence, 45(12):15790-1580 2023b.
Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, Jose M Alvarez, and Ping Luo. Seg- former: Simple and efficient design for semantic segmentation with transformers. Advances in neural information processing systems, 34: 14:17077-10000, 2021.
Jiarui Xu, Shalini De Mello, Sifei Liu, Wonmin Byeon, Thomas Breuel, Jan Kautz, and Xiaolong Wang. Groupvit: Semantic segmentation emerges from text supervision. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 18134-18144 2022.
Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer. Sigmoid loss for language image pre-training. In Proceedings of the IEEE/CVF international conference pp. 19985-11986, 2023.
confereece on computer vision,
Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia. Pyramid scene parsing network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2881-2890, 2017.
14

---

Published as a conference paper at ICLR 2026
Bolei Zhou, Hang Zhao, Xavier Puig, Tete Xiao, Fidjer Adela Barriuso, and Antonio Torralba. Semantic understanding of scenes through the ade20k dataset. International Journal of Computer Vision, 127:302-321 -2 2019a.
Jinghao Zhou, Chen Wei, Huiyu Wang, Wei Shen, Cihang Xie, Alan Yuille, and Tao Kong. ibot: Image bert pre-training with online tokenizer. arXiv preprint arXiv:2111.07832, 2021.
Zongwei Zhou, Md Mahfuzur Rahman Siddiquee, Nima Tajbakhsh, and Jianming Liang. Unet++: Redesigning skip connections to exploit multiscale features in image segmentation. IEEE trans- actions on medical imaging, 196):1856-1867, 2019b.
Hongyuan Zhu, Fanman Meng, Jianfei Cai, and Shijian Lu. Beyond pixels: A comprehensive survey from bottom-up to semantic image segmentation and cosegmentation. Journal of Visual Communication and Image Representation, 34:12-27, 2016.
A EQUIVALENCE OF K-WAY NCUT AND A SUM OF GENERALIZED RAYLEIGH QUOTIENTS
We consider an undirected weighted graph with symmetric nonnegative affinity matrix W E R NxN and degree matrix D (W1), and let L = D W be the combinatorial Laplacian. A K K-way partition {P1.... ....... Px } is represented by one-hot indicator columns 2& {0,1)A and the assignment matrix X = [z...... œx| E {0, N satisfying X1 = 1.
For each part PR. denote its volume and cut by
vo.(Pt)
Σ de
Put
Σ Wii. PEP
(15)
iEP
The normalized cut objective Shi & Malik (000b) is
K
cut Pk, Pk) vk)(Pk)
Neut Pe..,, Pk)
(16)
1m
With the indicator Iy of Pk, we have the following standard equalities:
vol(Pa) Fg Dæc,
cut(Pk, Pa) xg Lxg x D 2g W We:.
(17)
Since [æte] = 1 iff E PE. oy Dæs = EN de | Eier. di = vP)( Moreover, using the well-known Laplacian quadratic form z Lz = $ Ens Wo)(z=zzy) and taking Dg {0, 1
the summand is iff {i.j} crosses the cut Pk), which yields a Læs = cut(Pa, Px). The decomposition L = D - W gives the alternative expression.
Dividing equation 17 termwise gives
cut(Pk, Ph)
2. La
I Wa
(18)
vol(Pw)
2 Dea
2x Dæa
Summing equation over 4: = 1,..., ....,KK and using equation
16 yields
K
K
T Læ
x Wab
Neut(X2 (X)
K
(19)
x Dwc
x Dws
k=1
k=1
Define the normalized association
K
Fg W x
f(x)
so that
Neut = K f(X).
(20)
Day
Each summand of f(X) is generalized Rayleigh quotient of the matrix pencil (W, D) evaluated the indicator 26. With K fixed, minimizing Ncut is equivalent maximizing over the discrete assignment set X' == [X E [0,1]N*K, X1 ). The set X' is combinatorial and nonconvex, and the ratio structure in equation 19 and equation 20 further complicates the landscape, so the exact K-way problem is NP-hard in general. This motivates spectral relaxations and continuous surrogates followed by discrete projection back onto X.
15

---

Published as a conference paper at ICLR 2026
B ON THE SUBOPTIMALITY OF RECURSIVE NORMALIZED CUT
Recursive partitioning applies a two-way Normalized Cut (Ncut) repeatedly until K parts are ob- tained. The procedure is simple and often efficient, yet it may be far from the global optimum of the K K-way objective. This note explains why greedy bipartitions solution and highlights the mathematical and structural causes.
deviate from the best K- K-way
Let 9 = E, W) be an undirected graph with | = N, affinity matrix W E R
RNN, and degree
matrix D = diag( W1). A K-way partition {Ac) K minimizes
cut(AA,, v(.))) vol(As)
Ncut((As))
Cut(A,
E.e, Wey vol(A) = =Ed, dd. SEB
Exact minimization is NP-hard for K 2. A common heuristic first finds two-way Neut (A, on g, then recurses on the induced subgraphs until K clusters are formed. Despite its convenience, this scheme does not, in general, recover globally optimal K-way partition.
Lack of optimal substructure. The K-way objective does not decompose into independent two- way subproblems. Once a boundary between A and B is fixed, subsequent decisions are constrained within induced subgraphs. A locally optimal bipartition Ncut B) need not be part of any globally optimal K way solution.
Objective mismatch under recursion. Consider K = 3 with ground-truth communities A, B, C. recursion first splits S A U B from C, then refines S into A and B, the recursive score equals cut (S, C) cut(S, C) (S) vol(C)
cAt B) cA,
vols
vBl
first hipurtition G
second bipartition on the induced subgraph S
where cuts and vols are computed in the induced subgraph on S. By contrast, the global 3-way objective is
cut(A, BUC) + Aut(BAUUC) + (C, vol(B)
vol(A)
vol(C")
These expressions differ in the normalizers for the second stage: typically vols(A) vol(A) and vols < v)l(B) whenever A or B has edges to C. Hence the recursive refinement overweights cuts (A, B) cut(A, B) by dividing through smaller denominators, which can increase the total objective. There exist graphs where this "normalization gap" makes the recursive sum strictly larger than the global 3-way optimum, and the same phenomenon extends to K > 3.
Irreversibility and greedy commitment. Early boundaries are irrevocable. bipartition that reduces the two-way score may merge distinct communities because the two-way objective favors grouping parts whose union has a large volume, even if a later K K-way split would separate them. Once merged, separating them inside the induced subgraph ignores edges to the rest of the graph, which distorts normalization and may prevent recovery of the best global arrangement.
Spectral information loss in two-way splits. Two-way Neut is driven by the Fiedler vector of Laym- For K > 2, higher eigenvectors encode additional community structure. Sequentially apply- ing single eigenvector per split neglects joint information in the top K eigenvectors and can miss multi-community signals; rounding and recursion cannot, general, reconstruct the simultaneous K- K-way structure.
Recursive bipartitioning is useful heuristic, yet it imposes sequential search global objective. Local optimality at each step is not sufficient for global optimality, especially on non-hicrarchical graphs or when multiple spectral components are essential. Methods that optimize K K-way objec- tive directly or allow global refinement can mitigate these failures.
C KURDYKA-LOIASIEWE CONVERGENCE ANALYSIS OF FALCON
Following the Hurdyya-Looasiewice (KL) Convergence analysis method in Jia et al. (2023). we establish the convergence of the entire sequence generated by Falcon to stationary point of the
16

---

Published as a conference paper at ICLR 2026
objective function. This is achieved under the condition that accumulation point of the sequence satísfies Kurdyka-Lojasiewie (KL) property.
C.1 PROBLEM, ALGORITHM, AND STANDING ASSUMPTIONS
Let X = NNK with Frobenius inner product and norm || ||- We consider
min XeX
(x = f(X) + 6(X).
(21)
where X + is C and X + (-00, +o0| is proper, lower semicontinuous (Isc). In FAI.CON, Φ = by, encodes the row-wise one-hot feasibility with nondegenerate cluster volumes; thus dom( V++
In Falcon with monotone backtracking, given X E Edom(o) and parameters
2>0, O,
7>1 1, 8 (0, 1),
for 1: = 0,1, perform:
(A1) Backtracking loop. Initialize a trial stepsize 7/e E 12 +00).
(A2) forward-backwand subproblem. Compute
X k+1
E arg min (V)(**) Y
Y
x
1| 1
d(Y).
(22)
When Ø = tv., equation 22
reduces to row-wise one-hot projection of X 7k
(x(( onto V+.
(A3) Acceptance test. Accept if
7k
v ((*+1) S // (X.)
x X21
(23)
2
Otherwise set 7/k + 77 and repeat (A2)-(A3).
Assumption C.1 (Standing; ef. Assumption 3.2).
(a) vb is bounded from below on (Ø).
(b) Φ is bounded from below by affine function.
(c) V is locally Lipschitz continuous.
We also assume the subproblem equation 22 is solvable for all ls (true here since o is indicator and the objective Y is strongly coercive).
Definition C.2 (KL property (at X))). A proper Isc & has the Kurdyka-Lojasiewicz (KL) property X * if there exist 7 > 0, neighborhood U/ of X", and concave C'l function X (0, 70 - R+ with (t) such that
((((X) - v(x))) dist (x)) 2 1
for all X E l with ((X)) < (X) < v(X') + If x(() ct with 0 E [0, then 0 is the
KL exponent.
C.2 PRELIMINARIES: DESCENT AND OPTIMALITY RESIDUAL
Lemma C.3 (Finite termination of backtracking and sufficient decrease). Under Assumption C.I the backtracking loop terminates after finitely many inner steps. The accepted (Xk+1 7%k satisfies
equation 23 converges.
Consequently, (b( is monotonically decreusing and bounded below; hence
Proof. By local Lipschitz continuity, there exists L₃ with
f(Y) < s(xx) (VI(x*), x
Y x11
for Y near x Combining this with the optimality of equation yields equation 23 whenever ? 2 L (1 8). Since 7k increases geometrically in backtracking, acceptance occurs in finitely many C.I.
inner steps. The monotonicity and the lower bound of / (Assumption C.T(a)) imply convergence of vb (X**).
17

---

Published as a conference paper at ICLR 2026
Lemma C.4 (Optimality of the prox subproblem and residual bound). For the accepted (X*+1 one has
.7%)
O vf(*)) + + (X*+1 -x) + -6(xxx+)
(24)
Hence
(x*+1)
VF Vf
7h X X
(25)
Proof. The inclusion equation 24 the first-order condition equation 22 Adding and subtracting
f((++1) and using diL( X FT) Vf(x 0o(x++1) gives equation 25
STEP 1 (LEMMA 4.1 ANALOGUE): LOCAL BOUNDEDNESS OF ACCEPTED STEPSIZES
Lemma C.5 (Local boundedness of )kd). Let X* be an accumulation point of {X*). Then there exist neighborhood u of X" and constant 7 < such that, for all sufficiently large k with X E Ed, the accepted stepsize satisfies Tik S
Proof. By Assumption C.I c), V is L-piiscchizz on ball 1 = 1
X S p} for small
p > The descent argumeni in Lemma C.3 shows that equation 23 holds for any ? 2 Lp d). provided X X E L' with slightly larger radius. Thus, once is large so that iterates stay in U! the backtracking will accept a step with 7 < == 17 / - 8).
STEP 2 (LEMMA 4.2 ANALOGUE): CONVERGENCE OF FUNCTION VALUES
Lemma C.6 ((b(*))
(X*)). Let X* be an accumulation point of {X*}. Then (x*)
(X*).
Proof. By Lemma C.3 x/(X (X
converges to some 2/.0 Take ky - 00 with X
X Lower
semicontinuity of Φ and continuity of f give (xx))
< lim inf (x**s = शे Since (xx²)) is
decreasing and X lies in the same sublevel set, gi
& (X*). Hence equality holds.
STEP 3 (LEMMA 4.4 ANALOGUE): SUBGRADIENT- STEP RELATION
Lemma C.7 (Subgradient controlled by step length). There exist kn and > such that for all
k 2 Ko-
C||X*+1-X -X
(26)
Proof. Restrict to the tail where x lies in the neighborhood 4 of Lemma C.5 Then V Lp Lipschitz and 7h S From equation 25
dist (xb(X z (Lp + +7) x X*II
Set C := Lo L, + and choose kn large so that the neighborhood assumptions hold.
C.3 MAIN THEOREM (THEOREM 4.5 ANALOGUE): GLOBAL CONVERGENCE
Theorem C.8 (Global convergence and finite length). Suppose Assumption C. holds and the quence (X*} generated by FALCON has accumulation point X* at which vp satisfies the KL property. Then { converges to X* and
2
Σ
|x++1 _X| 00.
Proof. Let AA = ((x)) (X* O. By Lemma C.3 and Lemma C.6
Ae J 0. By Lemma C.7
for k 2 Ko:
dist (0, (xx*)) < C C k - k-1
The KL inequality at X* yields
x(Ar) 2 - X
( ko).
(27)
18

---

Published as a conference paper at ICLR 2026
From the sufficient decrease equation
23
and
Y
8
4 AK+1
2
|
k+ 11.
2
Concavity of x implies
87
X - X#12
x(Ax) x(4x+1) x'(A)) (Ax -A++1) 2
2C
X X
Summing from k ko to and telescoping the left-hand side gives
x k++ 1 X -
2C (x(Aka) - x(Am+1)) - x(Aro).
20 81
82
A Kg
An elementary inequality then yields ΣnSkD X X < co (finite length). Hence {X*) is
Cauchy and converges; as X is an accumulation point, the whole sequence converges to X
C.4 RATE (THEOREM 4.6 ANALOGUE): LINEAR CONVERGENCE FOR KL EXPONENT
Theorem C.9 (Linear rates for = 5) Under the assumptions of Theorem C.8 suppose x(1)
ct2/2 near X (i.e., KL exponent 0 = 11 Then there exist E (0, 1), > 0, H E (0, 1), and K1
such that
(Q-linear values)
((x (x') S ((((**)= ((*)), 4k: 2 kn,
(R-linear iterates)
X X11l w wpp Ak: 2 ki-
Proof. With x(t) = 122 equation 27 becomes
c (As)
1/2
2
2
C -
---1-x*iip and following the standard argument in the proof of Theorem 4.6 (cf. Section 4), one obtains a linear contraction A I q As for all large and
Combining with Ag A + -
some q E (0. 1). The R-linear rate for iterates follows from summing the sufficient decrease and bounding | 1 in terms of A A+t1 to dominate the tail distance to X by a geometric series.
C.5 REMARKS SPECIFIC FALCON
Feasible set and KL property. When d = vv and f' analytic in neighborhood of limit point X* V4 with nondegenerate cluster volumes, f + Lv, is definable in o-minimal structure, thus satisfies the KL property at X*
Local Lipschitz of V in token-NCut. For the normalized association objective used by FAL- CON, the explicit gradient formula shows V is locally Lipschitz on any region where per-cluster volumes are bounded away from zero, which is enforced by dom(@) V4. This verifies Assump- tion c) near accumulation points.
Template note. The structure of Lemmas C.5
C.7 and Theorems C.8 follows the Section
framework (descent, subgradient bound, KL) of Jia et al. 2023).
D TIME COMPLEXITY OF FALCON
We analyze proximal update of FALCON under affinity matrix W e NNN, Let X {0, 13 NN be row-one-hot. In one accepted outer iteration, the algorithm forms
G WX,
g (X ② T
T d, d= W1,
D diag(d)
19

---

Published as a conference paper at ICLR 2026
and computes the gradient
= 2Gx
Q Pk o
then performs the row-wise arg max update and evaluates the Armijo-tppe acceptance criterion. The dominant costs are
Per iteration cost
O(N2K)
+ column scalings and subtraction in V
((NK)
+ row-wise arg max
O(NK)
G WX
O(N=K)
Hence one accepted iteration costs ( K), omitting lower-order ONN terms.
If B, 2 denotes the number of line-search trials in iteration (including the accepted one), each trial repeats W X together with light (NK) work, so the cost of iteration is O 2 Near the limit set, Armijo acceptance holds for any T 2 Lpp(1 - o); starting from To >> and multiplying by gives
B. S 1 log, (1 8) )
Lp
ie., uniform constant bound, so backtracking contributes only small multiplicative factor. If B, = O()) and accepted outer iterations are performed, then
Total cost = B.) = O(), T
Classical spectral methods (eigenvector computation for the Laplacian normalized affinity) and recursive NCut typically require solving an N x N eigenproblem, leading to cubic O(N*) time in standard dense linear algebra. In contrast, Falcon's 's core cost is quadratic ( for constant K and T. Moreover, our KL-based analysis guarantees convergence the whole sequence (and linear rates when the KL exponent is 1 1/2). property that plain power or cigen-solvers used in recursive NCut do not directly provide the discrete assignment level.
E PROPERTIES AND TIME COMPLEXITY OF PAMR AND NAMR
Let Ω c 2 be the pixel grid, ||]| N, with image / +2++R2 R3 The initial segmentation is Mo E [0, ([C+))NN (one-vs-rest probabilities from NN-upsampled token masks). For a set of dilations D C N+, define displacement sets Aa of the 8 neighbors at distance d and A = Uaen Ad with D) For A, the shift operator (1) = æ(i + 5) uses border replication.
For each (i, 8), define channelwise discrepancies
(x (1) [a + +5), F(i,8) Σ rx(1,8). a(i) Stdse F(i, 8).
NAMR replaces F by (r) 5) 1 Σx (T(((i)) Te + 6))] with fixed pointwise ø.
PAMR as anisotropic diffusion on row-stochastic graph. For stabilization constant 6 > 0 and (optionally) scale factor absorbed into a, define directional logits and softmax weights
O(i,0) ((i,5) + (1))
exp(l(i, 0)}
p(1,8)
EsEA exp(e(i,8')}
20

---

Published as a conference paper at ICLR 2026
Collect p(i, 8) into sparse row-stochastic matrix W E RNN with (ii,++8) = =p(,,) and zeros elsewhere. For each class e,
m 2+11 W m.
-= T 1, M = Mo,
M = I my m
(1)
Stability. Since W is row-stochastic, each update is convex combination, |l 11s0 S |mm] 11x- Energy view (fixed W). ). finite number of Jacobi steps upproximates minimizing
E(M) (M. (I, M(:.))ll + a M - Moll.
with an optional data-fidelity a 2 0. Early stopping (T' 5-10) balances denoising and edge preservation.
NAMR: non-linear contrast and multi-temperature aggregation. For T -.. Tm Tm-
(1,6)) (i, 8)
(1, softmaxsEa (1,8),
(1 = (1,
E + TT))
Run T steps per temperature,
M (r) (W(r))?M Mo.
My
1
Σ M TET
i(1) arg max M/O (1).
Small downweights cross-edge transport; large encourages within-region smoothing. The aver- age Mr behaves like a multi-bandwidth anisotropic diffusion, improving robustness across appear- ances.
Time Complexity. Let HWW classes C+1,, directions / 8) iterations T', and m T (for NAMR). Constructing F and a costs O(N-3-P) Each message-passing step costs (NN-C.P)
Hence:
PAMR: (((3P+TCP));
NAMR: [LN(3++mTCP)
The framework is drop-in: RGB be replaced by any guidance features (e.g.. depth encoders) without changing derivations.
21

---

Published as a conference paper at ICLR 2026
sphere
Figure 5: Qualitative segmentation results of Falcon across diverse domains. Examples span natural scenes, urban landscapes, medical CT, paintings, cartoons, and planetary imagery. Fal- consistently produces coherent partitions with sharp boundaries and stable region assignment, demonstrating strong generalization beyond single modality.
F FALCON SEGMENTATION RESULTS VISUALIZATION
22

---

Published as a conference paper at ICLR 2026
G END-TO-END RUNTIME ACROSS DATASETS AND ENCODERS
Table reports the end-to-end evaluation time across all dataset-encoder pairs, decomposed into Data Preparation, Feature Extraction, and Mask Generation. Unlike Appendix [ which isolates graph-cut time and refinement time under controlled post-processing settings, this table summarizes the full pipeline runtime used in the main paper.
Falcon achieves the lowest total runtime across all 18 dataset-encoder pairs. Representative amples include: (i) DINOv3-B, Cityscapes: Total Time drops from 784.04s (DiffCut) to 87.47s (~-8.9x), and Mask Generation from 747.97s to 52.49s (~~1433x): (ii) SD2.1, Context: Total Time reduces from 2535.03s 1173.87s (~2.2x), and Mask Generation from 1546.75s 182.86s (~8.5%)); (iii) SSD-IB, Cityscapes: even when preprocessing dominates, Falcon still lowers To- tal Time from 177.27s to 114.67s (~1.5x) and reduces Mask Generation from 78. 11s to 15.46s (~5.0xx).
23

---

Published as a conference paper at ICLR 2026
Table 3: End-to-end evaluation time across datasets and encoders. Best Total Time (s) and Mask Generation (s) for each datasct-encoder pair are bold.
Encoder
Benchmarks
Method
Total
Data Preparation
Feature
Mask Generation
AntoSC
126.63
23.02
76.25
27.36
Citscapes
Falcon
114.67
22.96
76.25
15.46
AutoSC
368.96
68.61
220.71
79.64
VOC
DifíCat
483.05
71.21
220.39
191.45
Falcon
335.31
68.88
220.96
45.47
AutoSC
1288.12
232.30
SSD-1B
Context
DiffCut
1700.30
237.37
775.37
687.50
Falcon
1170.80
233.73
775.74
161.33
AutoSC
551.18
100.89
330.78
119.51
COCO-Stuff
Falenn
497.55
98.84
330.91
67.80
AutoSC
556.11
105.84
330.72
119.55
COcO-Objes
DifACat
748
14.85
330.68
303.43
Falcon
506.54
106.48
331.23
68.83
AutoSC
91.34
ADE20K
DiffCut
686.08
90.65
304.03
291.40
Falcon
459.25
92.13
304.77
62.35
AutoSC
129.15
23.13
74.44
31.58
Ciyscapes
Falcon
114.35
23.13
74,58
16.64
AutoSC
374.69
68.68
214.97
91.04
VOC
DiffCut
719.16
68.37
214.77
436.02
Falcon
1313.00
234.68
756.28
SD2.1
Context
DifCCtt
2535.03
233.09
755.19
1546.75
Falcon
1173.87
234.24
756.77
182.86
AutoSC
$61.70
101.46
322.60
137.64
CoCO-Stuff
99.31
Falcon
498.58
97.88
322.90
77.80
AutoSC
566.79
106.95
322.52
137.32
COCO-Objet
DiffCut
1208.45
103.69 69
322, 18
782.56 782.58
Falcon
503.54
AutoSC
514.99
91.26
296.62
127.11
ADE20K
DifCCut
1090.35
90.80
296.25
703.30
Falcon
487.40
89.28
296.60
71.52
AutoSC
242.67
23.07
12.14
207.45
Cityscapes
23.93
Falcon
87.47
22.48
12.50
$2.49
AutoSC
718.39
69.10
35.00
614.29
VOC
DifCCut
1950.92
66.33
34.97
1849.62
66.34
AutoSC
2528.36
236.62
122.93
2168.81
DINOv3-b
Context
DiffCut
6935.53
234.54
122.85
6578.14
Falcon
903.28
237.21
123.24
542.83
AutoSC 1073.20
100.08
$2.47
920.65
COCO-Stuff
DiffCut
2916.03
99.05
52.43
2764.55
Falcon
384.14
101.16
52.41
230.57
AutoSC
1184.79
107.20
52.47
1025 12
COCO-Objec
DifCCut
2947.12
102.48
52.43
2792.21
Falcon
52.72
231.99
AutoSC
996.57
93.55
48.26
854.76
ADE20K
DiffCut
2787.44 44
90.47
48.22
2648.75
Falcon
351.39
90.10
48.46
212.83
24

---

Published as a conference paper at ICLR 2026
Table 4: Controlled comparison with MaskCut under matched settings (mloU). All methods are evaluated under the same class-agnostic semantic segmentation protocol. "Reported" denotes numbers taken from the DiffCut paper; "our reported" denotes re-implementation in our unified codehase.
Method
Encader
VOC
Context
COCO-Ohject
COCO-StufF-27
Cityscapes
ADE20K
MaskCat k= treported by DiftCut)
Unknown
53. 80
43.40
30.10
41.70
18.70
35.70
MaskCut k= (our reported)
DINOV3-B Key
81811
30.46
51.97
21.70
2.74
14.83
MaskCat k=5 (our reported)
DINOv3-B Token
73.07
33.26
52.87
25.51
6.06
17.48
Falcon
DINOv3-B Token
75.15
42.04
H CONTROLLED COMPARISONS WITH MASKCUT AND DENSECRE
To complement the main-paper comparison against published baselines, additionally perform controlled comparisons with MaskCut under matched settings. The goal is to isolate the contribution of the segmentation solver itself by aligning the encoder, resolution, evaluation protocol, and post- processing choices.
Specifically, we re-implement MaskCut within our unified codebase and evaluate it using the same image resolution, the same class-agnostic Hungarian-matchin protocol, and matched post- processing settings for controlled comparison. Since the original MaskCut paper uses ViT key em- beddings together with DenseCRF, we report both key-feature and token-feature variants of Mask- Cut. We also evaluate Falcon with DenseCRF to provide direct comparison under the same post- processing family.
The results show that Falcon consistently outperforms the controlled MaskCut variants even when using the same token features and the same DenseCRF post-processing. This confirms that the gains of Falcon come from directly optimizing the discrete K K-way NCut objective, rather than from encoder or refiner differences alone.
Under matched token features and the same DenseCRF post- post-processing, Falcon clearly outperforms MaskCut across all six benchmarks. This controlled comparison strengthens the main-paper results by showing that Falcon's gains attributable to the discrete K K-way solver itself, rather than to backbone choice or post- prosessooessing differences.
I RUNTIME DECOMPOSITION BY GRAPH CUT AND REFINEMENT
The runtime analysis in the main paper focuses on end-to-end evaluation time. further clarify where the speedup comes from, we decompose inference into graph-cut time and refinement time. This decomposition particularly important for comparing Falcon with recursive NCut methods and with different post-procee pessterocessing modules.
All methods are measured under the same hardware and implementation setting. In particular, we use the same image resolution, the same encoder setting, and the same evaluation protocol, and we report wall-clock time for the graph-partiiioing stage and the subsequent refinement stage sep- arately. For MaskCut, we pair the recursive NCut solver with DenseCRF, following its classical refinement setup. For Falcon, we report three post-processing choices: PAMR, NAMR, and Dense- CRF.
The results show that Falcon's efficiency gains come primarily from the graph-partitioning solver itself. Even when paired with the same DenseCRF post-processing, Falcon remains substantially faster than MaskCut across all six benchmarks. Moreover, PAMR and NAMR contribute only small overhead relative to Falcon's graph-cut stage, whereas DenseCRF introduces a larger but still secondary refinement cost.
Across all six benchmarks, Falcon remains substantially faster than MaskCut when both paired with DenseCRF. For example, on Pascal Context, Falcon+CRF reduces graph-cut time from 2537.03. $337.03s to 542.73s. while also reducing refinement time from 310.40s to 217.635 On Cityscapes, Falcon+CRF reduces graph-cut time from 241.28s 52.37s. These comparisons confirm that the dominant speedup comes from replacing recursive spectral partitioning with Falcon's 's direct discrete K- K-way solver.
25

---

Published as a conference paper at ICLR 2026
Table 5: Runtime decomposition into graph-cut time and refinement time (seconds), All num- bers are measured under the same codebase and hardware setting.
Method
vOC
Contest
COco-Object
COCO-Stuff27
Cityscapes
ADM20K
GraphCut
GraphCut
Retine
GraphCut
Refine
GraphCut
Refine
GraphCut
Retine
GraphCurt
Retine
MariCuus (with CKF)
720.75
80.18
2537 .3
310.40
1078.50
125.
1077.81
241
32.00
1001 .57
120.20
231.39
230.87
1.70
NAMR) 136.77
12.88
641.50
44.65
231.50
21.05
231.20
23.40
62.39
5.02
211.34
20.55
Palcon (with CRF)
137.78
08.74
642.73
217.63
230.89
108.46
230.55
115.09
02.37
27.3
212.78
97.86
Table 6: Peak GPU memory usage (GB) at different input resolutions. Numbers are averaged over six datasets using DINOv3-B with batch size on RTX 6000 Ada GPU.
Resolution
MaskCut
DiffCut
Falcon
256
0.51
0.51
0.51
512"
0.54
0.51
0.54
7682
0.59
0.82
0.59
1024
1.00
1.95
0.93
2048
23.71
9.48
The table also shows that PAMR and NAMR add only a modest overhead relative to Falcon's graph- cut stage. For instance, VOC, Falcon requires 137.00s for graph cut and only 4.37s for PAMR refinement; even NAMR remains comparatively lightweight at 12.88s. DenseCRF's more expensive than PAMR or NAMR, but the solver-level advantage of Falcon persists under the same CRF post- processing family.
Overall, these results support the main-paper runtime analysis from complementary angle: Falcon is not merely faster because of a lighter refiner, but because its graph-cut stage is substantially more efficient than recursive NCut baselines.
J MEMORY USAGE AT DIFFERENT INPUT RESOLUTIONS
Since dense affinity methods scale quadratically in the number tokens, memory usage is an im- portant practical consideration in addition to runtime. To quantify this aspect, measure peak GPU memory at different input resolutions for MaskCut, DifiCut, and Falcon on top of DINOv3-B. All measurements are averaged over the six benchmark datasets used in the main paper, with batch size 1 on NVIDIA RTX 6000 Ada GPU.
The results show that Falcon is substantially more memory-efficient than DiffCut at high resolution, while remaining comparable to or slightly better than MaskCut. In particular, at 2048 x 2048, Falcon uses about 2.5x less peak GPU memory than DiffCut (9.48GB vs. 23.71GB), supporting its practicality for larger token graphs.
At lower resolutions, all three methods have similar memory footprints, as the token graph remains relatively small. As the input resolution increases, however, the gap becomes more pronounced: DiffCut incurs the largest memory growth, whereas Falcon remains much closer to MaskCut while still optimizing a global discrete K- -waay objective. This complements the runtime analysis in the main paper and shows that Falcon is not only faster in practice, but also more scalable in memory than prior recursive NCut-based methods at high resolution.
K SENSITIVITY TO THE INERTIA AND BACKTRACKING PARAMETERS
Falcon uses a proximal inertia parameter together with a monotone backtracking rule. To exam- ine the robustness of these optimization parameters, we sweep the initial inertia weight and the backtracking growth factor 7 on Cityscapes using two representative encoders. DINOv3-B16 and SSD-IB. Unless otherwise noted, Falcon uses the same default values To and = across datasets and pretrainings.
The results show that Falcon highly insensitive to these settings: the final mIoU varies by less than 0. % across the tested configurations. Under the default setting, Falcon typically converges in essentially outer iteration per image with negligible backtracking. Even under more aggressive
26

---

Published as a conference paper at ICLR 2026
Table 7: Sensitivity to the inertia and backtracking parameters on Cityscapes. mloU remains essentially unchanged across settings, while the default configuration converges in about one outer iteration per image.
Encoder
7
Outer iters/ing
Backtrack
mloU (%)
DIN0
DINOv3-B16
0.50
5.00
1.22
43.40
25.27
DINOv3-B16
1.00
1.00
0.00
25.29
SSD-IB
0.50
1.44
30.56
SSD-1B
0.50
5.00
1.21
67.80
30.56
SSD-IB
1.00
30.56
initializations, backtracking acts as a safety mechanism and increases runtime only slightly, without changing the final segmentation quality.
Under the standard choice (To: 7) (1.0, 2.0), Falcon converges in essentially outer iteration with almost zero backtracking. This supports the practical runtime observations in the main pa- and shows that the backtracking rule functions mainly as stability safeguard rather than sensitive tuning knob.
In all reported experiments, we set a small upper bound maax = 5 and stop early when the objective converges. In practice, the stopping condition is typically met after the first outer iteration. Likewise, the line search never behaves like heavy inner loop: under the default setting, the descent condition is usually satisfied on the first trial, and even with a smaller initialization such as 0.5, the additional overhead remains negligible relative one graph-cut update.
27


Reviews:
[{"review_id": "LqghUE4XLu", "reviewer": "Reviewer_v4WW", "summary": "This paper presents a new pseudo-mask generation framework, Falcon, which incorporates fast proximal linearization and adaptive mask refinement to achieve better or the same unsupervised segmentation performance with much faster generation.", "questions": "None", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. good motivation. Repeated NCut is slow. This paper presents a faster generation method with better performance.\n2. clear formulation and presentation. This paper formulates the generation problem using many formulas and proofs.\n3. efficiency analysis. Inference time of different methods are compared.\n4. encoder ablation. The author presents ablation of different SSL encoder to validates the effectiveness of Falcon.", "weaknesses": "1. While Falcon is more efficient than recursive NCut methods, its complexity still scales quadratically with the number of tokens, making it less optimal for extremely large datasets or scenarios with very high token resolutions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WS52apsNPB", "reviewer": "Reviewer_zCyW", "summary": "This paper introduces FALCON, a proximal-gradient solver for the discrete K-way normalized-cut (NCut) problem in unsupervised image segmentation. FALCON directly optimizes discrete assignments without spectral relaxation or eigen-decomposition. Experiments show the performance on six segmentation benchmarks (VOC, COCO-Object, Cityscapes, etc.)", "questions": "1. Sensitivity of hyperparameters. How sensitive is convergence to the choice of the backtracking parameter $\\gamma$ and the inertia term?\n2. Can FALCON handle dynamic or streaming data scenarios where affinities evolve online?\n3. The number of segments $K$ is determined by counting eigenmodes below a cutoff $k$. How robust is this spectral thresholding across datasets, and could a data-adaptive or learnable k further improve stability?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper reformulates the classical NCut objective as a proximal-gradient problem with discrete feasibility preserved at every step, eliminating spectral relaxation and rounding. The idea is sound and interesting.\n2. Experiments across six public benchmarks validate the performance of the proposed method.", "weaknesses": "1. It seems that the proposed method is mathematical. But the the intuition for why the proximal scheme works well is not clear.\n2. The method relies on pretrained vision encoders (e.g., SSD-1B, DINOv3), raising questions about its standalone generality in low-resource or domain-shift settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W4mCw1cwHO", "reviewer": "Reviewer_uM5A", "summary": "This paper presents a method for unsupervised semantic image segmentation. The begins by image feature extraction using pre-trained models such as Vision Transformer trained with DINO. An affinity matrix is assembled by pairwise feature similarity. The affinity matrix elements are viewed as weights on graph edges. This enables a bipartitioning objective, where the resulting partitions equate to segments in the input image. This paper presents Falcon, an extension of Normalized Cuts and recently proposed Mask Cut algorithms that partition the graph in a recursive fashion; more than $K=2$ partitions are obtained by recursively partitioning the remaining subgraph. Instead, Falcon partitions into $K>2$ groups at once and avoids eigenvalue decomposition, reducing the method complexity from $\\mathcal{O}(N^3)$ to $\\mathcal{O}(KN^2)$. Since tokens are subsampled wrt. the input image resolution, the authors propose two methods to recover partitioning at a higher resolution.", "questions": "- The number of clusters $K$ is \"is determined via spectral thresholding\". What is the complexity of this algorithm?\n- How does the accuracy depend on the number of iterations $\\mathbf{X}^{(t)}$? How many iterations does Falcon use in practice?\n- How many iterations are required to perform the line search in each iteration from Equation (12)?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper considers an important topic in computer vision. Contributions to semantic image segmentation are meaningful and relevant. The work is also well motivated; current methods based on graph partitioning depend on eigenvalue decomposition that is $\\mathcal{O}(N^3)$ in time, making them unscalable as input resolution grows. The experimental section includes evaluations on six datasets.", "weaknesses": "The method section is really complex and difficult to follow. There is an abundance of symbols that are not gradually included, and the text between the equations does not connect the formalism in understandable fashion. For example, most quantities are not expressed in text: readers would appreciate understanding what do $\\mathbf{v}$ and $\\mathbf{q}$ hold, and that $v_k$ and $c_k$ are merely elements within these vectors. Some variables are multiplied. For instance, a square similarity matrix $\\mathbf{S}$ is introduced in Equation (2). Afterwards, a $N \\times K$ matrix $\\mathbf{S}$ is used in Equation (8). Similarly, $c_k$ (Equation(9)) and $\\mathbf{c}_k$ (Equation(13)) refer to different quantities. Equation (11) expresses the update in the proposed iterative algorithm, but it seems to render improperly in the PDF.\n\nThe experimental section lacks proper comparison with related work.\nFirstly, influential relevant related methods, U2Seg [1] and UnSAM [2], are not included in experimental comparison.\nSecondly, since CutLer uses MaskCut to generate instance segmentation pseudo labels, it is unclear how is Mask Cut adapted for unsupervised semantic segmentation. This is important to note as Falcon is most related to Mask Cut. Moreover, the original work uses DINOv1 and CRF [3] to generate instance pseudo labels. A fair comparison should include the same backbone and postprocessing to highlight the contribution. Furthermore, the proposed postprocessing methods are not validated against the commonly used CRF postprocessing, therefore there is no validation of the proposed postprocessing methods.\n\nExecution time measurements do not include a comparison with Mask Cut. Also, separate time measurements for graph partitioning and postprocessing (the two contributions) are missing.\nThe authors comment that CRF post processing is CPU-bound. This is true for the official Mask Cut implementation [4], but does hold in general [5]. To highlight the lower theoretical complexity of Falcon, the experimental section could include measurements under common implementation and hardware*.\n\n- [1] Niu, Dantong, et al. \"Unsupervised universal image segmentation.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2024.\n- [2] Wang, XuDong, Jingfeng Yang, and Trevor Darrell. \"Segment anything without supervision.\" Advances in Neural Information Processing Systems 37 (2024): 138731-138755.\n- [3] Krähenbühl, Philipp, and Vladlen Koltun. \"Efficient inference in fully connected crfs with gaussian edge potentials.\" Advances in neural information processing systems 24 (2011).\n- [4] https://github.com/facebookresearch/CutLER/blob/main/maskcut/maskcut.py\n- [5] https://github.com/heiwang1997/DenseCRF\n\n$*$ Note that Mask Cut performs eigenvalue decomposition on CPU.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kIYABuhNAb", "reviewer": "Reviewer_mrYD", "summary": "This paper proposes “Falcon,” a graph cut algorithm for performing unsupervised image segmentation using embeddings from pretrained vision transformers. This algorithm is a proximal-gradient solver that directly optimizes the discrete K-way NCut objective without spectral relaxation. The paper shows this proposed method outperforms baseline approaches on common datasets and provides ablation and runtime experiments.", "questions": "Addressed in Weaknesses section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Technical novelty and practical impact\n- The authors propose a new graph cut method that is both performant and efficient for solving unsupervised segmentation problems provided a pretrained vision transformer.\n- The authors show improved performance compared to baseline methods (MaskCLIP, MaskCut, DiffSeg, DiffCut, AutoSC) on common benchmark datasets (VOC, Context, COCO-Object, COCO-Stuff-27, Cityscapes, ADE20K), suggesting the proposed method improves unsupervised segmentation with pretrained transformer models. \n\nHelpful ablation experiments\n- The authors perform helpful ablations showing the method improves performance over multiple pretrained networks and evaluating the refiner on both the proposed method as well as with baseline methods. \n- The authors provide detailed runtime experiments showing the method improves inference speed compared to two baselines.", "weaknesses": "Baseline method selection\n- The authors focus on a few previously published methods and show the proposed method convincingly outperforms them, but do not convince the reader these are representative/comprehensive baselines. Authors should clarify how and why they choose what baseline to include vs. exclude (e.g., zero shot SAM; STEGO; diffuse attend and segment; U2Seg; etc.), and consider including additional baselines if there is no convincing reason they should be excluded.\n\nReproducibility\n- Will the authors publish code to make this method usable/reproducible? If not, I have doubts about the reproducibility of this method.\n\nThere are a few items that need to be clarified to contextualize the strengths of the method:\n- Why are images resized to 1024 x 1024? This seems higher resolution than is typical for these natural image datasets and would increase runtime with the pretrained transformers. It also seems like this resize may be inflating inference speedups.\n- How is K determined? You say “K is determined via spectral thresholding: we count eigenmodes below a negative threshold κ and clamp K to a predefined range, “ but it is unclear to me what this means. Is K a range, and final K value is selected via best empirical performance? Does this need to be hand tuned per dataset? Where in the method pipeline is this operation performed? What is the rationale for the negative threshold and clamping? Is kappa hand tuned per dataset?\n- Can the authors comment on how memory usage compares to baseline methods? Since many of the intermediate matrices are NxN, is there a limit on image/token size * feature size (both dependent on the pretrained network) that is practical with this method?\n- Since gradient scores are weighted by cluster volumes, how do the authors expect volume size to impact performance? Is this dependence seen in the empirical results? (e.g., significantly stronger performance on large objects vs. small)\n\nMinor weaknesses:\n- I think the authors have used \\cite{}, which includes citations in-text, where they should have used \\citep{}, which includes citations in parentheses. The authors should switch the citations to the correct format as appropriate to improve readability. \n- Typo on line 43, “as” instead of “has.”\n- The authors lay out 3 challenges with existing segmentation methods in the abstract. Similarly, they list 3 challenges with existing segmentation methods in the introduction. However, these 3 challenges are not the same in the abstract vs. intro. This makes it challenging as a reader to know what limitations with previous methods the authors are aiming to address. The authors should make the abstract and intro consistent with one another.\n- Line 242, “(iii)” is repeated twice.\n- The authors lay out issue with “classical refiners” in lines 295-297, but do not state how PAMR or NAMR get around these challenges. A transition paragraph would help. \n- (H, W) seems to be overloaded notation. The authors use (H,W) to describe the size of the intermediate mask/features in Section 3.3, but then use (H,W) to describe the full resolution image in Section 3.4. Are (H,W) always the same, i.e. is the intermediate mask in Section 3.3 always at full resolution? If so, that is not clear from Section 3.3, as you refer to this stage as “intermediate-resolution refinement.”\n- There are no segmentation visualizations in the main text, they are instead put in the supplementary. If the authors have space, consider moving these to the main text. Additionally consider including visualizations of baseline vs. Falcon results for the reader to qualitatively understand differences in the methods.\n- There are many parameters given in Section 3; authors should include defaults for each of these in either the main text or supplementary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)