Let $R_k$ be the worst-case ratio between the expected cost of the $k$ seeds chosen by $k$-means++ and the optimal $k$-means cost. In their seminal paper introducing $k$-means++, Arthur and Vassilvitskii (SODA 2007) showed that $2\ln k\le R_k\le8(\ln k+2)$, and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to $5(\ln k+2)$. We prove $R_k\le\frac{1163}{233}+2.108\,H_{k-2}$ for every $k\ge3$ by a computer-assisted argument, and $R_k\le5+2.3139\,H_{k-2}$ for every $k\ge2$ by a short analytic argument; here $H_j$ is the $j$th harmonic number. Since $H_{k-2}\le1+\ln k$, this lowers the leading coefficient of $\ln k$ from $5$ to $2.108$. We also determine $R_2=5$ and $R_3=185/32$ exactly; both are suprema that are approached but not attained. On the lower side we prove $R_k\ge2(1+H_{k-1})$ for every $k$, and give a second family of lower bounds that is larger than this for $2\le k\le18$. Previous analyses bound the expected cost of a cluster just after it is first sampled by a constant times its optimal cost, and then charge that cost for the rest of the run. We instead track how a cluster's cost evolves after its first hit: a cluster left with a large residual cost is likely to be sampled again before it accumulates much of the logarithmic charge, and each repeat repairs it.
Carson Rodrigues, Clive Rodrigues, Aravind Reddy G
原文摘要
When a large language model (LLM) agent writes parametric CAD code from a natural-language specification, syntactic success decouples from semantic correctness. We release a benchmark and harness that measure this gap directly: 13 specification tasks whose every requirement maps to machine-checkable properties of the produced B-rep, measured by the kernel against published tolerance bands, with reference solutions and the full graded attempt corpus. The exact, self-audited oracle isolates two quantities no prior CAD benchmark reports: the silent-failure rate (a valid, renderable solid, an explicit completion claim, and at least one failed semantic check) and completion-claim calibration. Across four models from four vendors (156 attempts per architecture), single-shot agents claimed completion on 98% of attempts and were silently wrong on 14.1%; a tool-use loop that enforces measure-then-claim cut silent failures to 3.2% and raised claim precision from 64% to 96%, and a four-model ablation attributes the change to the claim contract rather than the feedback. A planner-coder-checker pipeline matched that precision at lower coverage with no success gain. Stated confidence was miscalibrated single-shot (ECE 0.32) and became informative under verification for three of four models. Hardening our own oracle flipped 18 of 519 regraded verdicts from pass to fail and none in reverse; a blind expert audit overturned 3 of the 18 silent failures outside the one ambiguously specified task; and fourfold scaling of every tolerance band leaves the contrast intact.