論文の概要: Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching
- arxiv url: http://arxiv.org/abs/2605.08658v1
- Date: Sat, 09 May 2026 03:54:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:49.796895
- Title: Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching
- Title（参考訳）: Sketch-and-Verify: プログラムのスケッチによる構造化推論時間スケーリング
- Abstract要約: SKETCHVERIFYは、普遍的な精度向上ではなく、内部レベルのコストパフォーマンスポリシーである。
階層内では、スケッチが一致した候補数でのフラットサンプリングを支配します。
階層横断のスケッチはアップグレードに取って代わらない。
- 参考スコア（独自算出の注目度）: 11.731523303184472
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: SKETCHVERIFY is a within-tier cost-performance policy, not a universal accuracy improvement. The operational question: a practitioner stuck with a small, cheap code model (here, Gemini 3.1 Flash Lite) for latency, deployment, or budget reasons -- how should they spend a small amount of extra test-time compute? SKETCHVERIFY factorizes the search space: the LLM enumerates K distinct algorithmic strategies, writes a program sketch for each (a partial program with ?? holes), and fills each sketch M times, producing K x M structurally diverse candidates that are verified by execution and selected by fingerprint clustering. Each extra sketch is guaranteed to explore a different algorithm; each extra flat sample likely duplicates an existing one. Our central evidence is a cost-quality Pareto plot on HumanEval+ across three Gemini tiers (Lite, Flash, Pro), and a reanalysis of the 19 problems where Lite greedy fails. Two findings: (1) Within-tier, sketching dominates flat sampling at matched candidate count. On the hard subset, Lite Sketch K=2, M=5 recovers 11/19 (58%) vs. flat N=10 at 5/19 (26%, +32pp); Lite Sketch K=10, M=10 recovers 15/19 (79%) vs. flat N=100 at 10/19 (53%, +26pp). Flat cannot close the gap even at ~3x the budget: flat N=50 still loses to Sketch K=2, M=5 by +11pp. (2) Cross-tier, sketching does not replace upgrading. Pro greedy (89%) dominates Lite Sketch K=10, M=10 (79%) on both pass@1 and dollar cost. Practitioner rule: if a stronger tier is available, use greedy on it; otherwise sketching is the cost-effective way to spend extra compute. We characterize the K-vs-M trade-off via a Flash Lite scaling sweep, report HumanEval+ saturation on Flash and Pro, and show the method composes cleanly with execution-based selection from the concurrent Semantic Voting line of work.
- Abstract（参考訳）: SKETCHVERIFYは、普遍的な精度向上ではなく、内部レベルのコストパフォーマンスポリシーである。
運用上の問題として、レイテンシやデプロイメント、予算上の理由から、小さな安価なコードモデル(ここではGemini 3.1 Flash Lite)で立ち往生した実践者が、テストタイムの計算に少額の時間を費やすには、どうすればよいのか?
SKETCHVERIFY は検索空間を分解する: LLM は K の異なるアルゴリズム戦略を列挙し、各プログラムのスケッチ(???穴のある部分的なプログラム)を書き、各スケッチ M 回を埋め、実行によって検証され、指紋クラスタリングによって選択される構造的に多様な候補を生成する。
各余分なスケッチは、異なるアルゴリズムを探索することが保証され、各余分な平らなサンプルは、おそらく既存のスケッチを複製する。
私たちの中心的な証拠は、HumanEval+の3つのGeminiティア(Lite、Flash、Pro)におけるコスト品質のParetoプロットと、Liteが失敗する19の問題の再分析です。
2つの結果:(1)内部のスケッチは一致した候補数で平坦なサンプリングに支配される。
ハードサブセットでは、Lite Sketch K=2, M=5は11/19 (58%)、フラットN=10は5/19 (26%, +32pp)、ライトSketch K=10は15/19 (79%)、フラットN=100は10/19 (53%, +26pp)である。
平坦な N=50 は Sketch K=2, M=5 by +11pp に負ける。
2) 階層横断で、スケッチはアップグレードに取って代わらない。
Pro greedy (89%) は Lite Sketch K=10, M=10 (79%) を支配している。
実践的ルール(Practitioner rule): 強い階層が利用可能であれば、それに対して欲張り(greedy)を使用すること。
我々は、Flash Liteスケーリングスイープを介してK-vs-Mトレードオフを特徴付け、HumanEval+飽和をFlashとProで報告し、同時にセマンティック投票ラインから実行ベースの選択をクリーンに構成する手法を示す。
関連論文リスト
- The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation [26.519824862057547]
線形スケッチによる次元の低減は強力で広く使われている手法であるが、敵の入力に弱いことが知られている。
ここでは、Rk × n$ の固定されたスケッチ行列 $A が Rn$ の高次元ベクトル $v を Rk$ の低次元スケッチ $A v に写像する。
我々は、$tildeO(k2)$クエリを使用して、ノルム推定の失敗または逆入力を構成する、普遍的で非適応的な攻撃を示す。
論文 参考訳（メタデータ） (2025-07-22T08:25:05Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - A Scalable Algorithm for Active Learning [3.046981426681863]
FIRALはロジスティック回帰を用いた多クラス分類のための決定論的能動学習アルゴリズムである。
ストレージ要求を$mathcalO(n(d+c) + cd2)$に減らし、計算複雑性を$mathcalO(bn2)$とする近似アルゴリズムを提案する。
MNIST, CIFAR-10, Caltech101, ImageNet を用いたアプローチの精度とスケーラビリティを実証した。
論文 参考訳（メタデータ） (2024-09-11T16:34:01Z) - Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
3ドルの登録アプローチでは、1000万ドル(107ドル)以上のポイントペアを、99%以上のランダムなアウトレイアで処理することができる。
我々はこの手法をTEARと呼び、Trncated Entry-wise Absolute Residualsを演算するoutlier-robust損失を最小限にする。
論文 参考訳（メタデータ） (2024-04-01T04:43:39Z) - SketchINR: A First Look into Sketches as Implicit Neural Representations [120.4152701687737]
暗黙的ニューラルモデルを用いてベクトルスケッチの表現を前進させるSketchINRを提案する。
可変長ベクトルスケッチは、時間とストロークの関数として下層の形状を暗黙的に符号化する固定次元の潜時空間に圧縮される。
初めてSketchINRは、ストロークの数と複雑さの点で、さまざまな抽象化でスケッチを再現する人間の能力をエミュレートする。
論文 参考訳（メタデータ） (2024-03-14T12:49:29Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - CLIP for All Things Zero-Shot Sketch-Based Image Retrieval, Fine-Grained
or Not [109.69076457732632]
ゼロショットスケッチに基づく画像検索(ZS-SBIR)におけるCLIPの利用
私たちはこのシナジーを達成するのにいかに最適かという新しいデザインを提唱した。
これまでの最先端技術よりも26.9%の領域で顕著なパフォーマンス向上が観察された。
論文 参考訳（メタデータ） (2023-03-23T17:02:00Z) - On the Robustness of CountSketch to Adaptive Inputs [22.34019676119989]
CountSketchは、ベクトルをランダム化線形測定を用いて低次元にマッピングする一般的な次元削減手法である。
古典的推定器はロバストではなく、スケッチサイズの順序の複数のクエリで攻撃可能であることを示す。
本研究では,スケッチサイズで2次的なクエリ数を推定できるロバストな推定器を提案する。
論文 参考訳（メタデータ） (2022-02-28T13:04:41Z) - Complex-to-Real Sketches for Tensor Products with Applications to the
Polynomial Kernel [15.535749953841274]
p$ベクトルの積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。
本稿では、実乱射影を複素射影に置き換える、よく知られたスケッチの単純な複素対Real (CtR) 修正を提案する。
本手法は,文献の他のランダム化近似と比較して,精度と速度の面で最先端の性能を達成することを示す。
論文 参考訳（メタデータ） (2022-02-04T09:15:43Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳（メタデータ） (2021-02-25T15:50:19Z) - Learning-Augmented Sketches for Hessians [54.97773807211337]
第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。
学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-02-24T14:50:59Z) - Learning the Positions in CountSketch [51.15935547615698]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。
このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
論文 参考訳（メタデータ） (2020-07-20T05:06:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。