論文の概要: How Much Does One Wrong Answer Cost? Error Propagation in Constraint Pruning with Noisy LLM Oracles
- arxiv url: http://arxiv.org/abs/2610.25739v1
- Date: Mon, 19 Oct 2026 03:44:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-24 11:55:14.402184
- Title: How Much Does One Wrong Answer Cost? Error Propagation in Constraint Pruning with Noisy LLM Oracles
- Title（参考訳）: アンサーのコストはいくらか? ノイズの多いLLMオラクルとの制約緩和におけるエラー伝播
- Abstract要約: Constraint pruningはクエリを大きな言語モデル(LLM)や他のノイズオラクルに保存する。
我々は、プルーニングは、神託の発散時にそのリスクによって判断されるべきであり、それは、受け入れられた間違った答えが、それが意味するあらゆる質問に広まるからである。
- 参考スコア（独自算出の注目度）: 1.4355156736131904
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constraint pruning saves queries to a large language model (LLM) or another noisy oracle by skipping each yes/no question implied by answers accepted earlier, for example through transitivity. Entity-resolution systems and LLM-based rankers use this idea. However, their analyses typically assume a correct oracle. We argue that pruning should be judged by its risk when the oracle errs, since an accepted wrong answer spreads to every question it implies. When each answer is wrong independently with small probability $\varepsilon$, the first-order risk is set by how many facts one wrong answer corrupts on average. We consider two kinds of constraints. For implication rules, as in taxonomies, pruning in a random order adds no first-order risk: a wrong answer that would change $k$ facts is accepted with probability $1/k$, so it costs one fact on average. Rules with $s$ premises break this balance: a wrong answer at a premise shared by $r$ rules can cost order $r^{1-1/s}$ facts. For entity resolution with $m$ records of one entity, the first-order risk equals $\varepsilon$ times the Wiener index (the total pairwise distance) of the spanning tree built by the query order. Pivot orders, which first compare one record with all others, amplify errors by less than 2 and are optimal; random orders by order $m^{1/3}$; the common most-similar-first order is the worst in one dimension and, for large $m$, worse than random in two. With several entities, the cost of wrongly merging two does not depend on how many others exist. Simulations agree with every predicted constant within sampling error.
- Abstract（参考訳）: 制約プルーニング(Constraint pruning)は,クエリを大きな言語モデル(LLM)あるいは他のノイズオラクルに保存する。
エンティティレゾリューションシステムとLLMベースのローダはこのアイデアを使用している。
しかし、それらの分析は通常正しいオラクルを仮定する。
我々は、プルーニングは、神託の発散時にそのリスクによって判断されるべきであり、それは、受け入れられた間違った答えが、それが意味するあらゆる質問に広まるからである。
それぞれの答えが小さな確率$\varepsilon$と独立に間違っている場合、一階のリスクは、1つの間違った答えが平均でどれだけの事実を損なうかによって設定される。
制約は2種類ある。
含意規則については、分類学のように、ランダムな順序でプルーニングを行うと、一階のリスクは生じない:$k$の事実を変える間違った答えは、確率1/k$で受け入れられる。
a wrong answer at a premises by $r$ rules can cost order $r^{1-1/s}$ facts。
1つのエンティティの$m$レコードを持つエンティティ解決では、1次リスクはクエリ順序によって構築されたスパンニングツリーのWienerインデックス(全対距離)の$\varepsilon$倍になる。
1つのレコードを他のすべてのレコードと比較したPivot Orderは、エラーを2未満に増幅し、最適である; 順序$m^{1/3}$でランダムオーダー; 一般的な最も類似したファーストオーダーは1次元で最悪のものであり、大きな$m$の場合は2次元でランダムよりも悪い。
いくつかのエンティティでは、間違った2つのマージのコストは、他の何つのエンティティが存在するかに依存しない。
シミュレーションはサンプリングエラーの全ての予測定数と一致する。
関連論文リスト
- Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。
本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。
本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
論文 参考訳（メタデータ） (2026-09-29T15:39:50Z) - An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order [6.657272312990604]
Attias, Hanneke, Ramaswami (NeurIPS 2025) は、クラスが神託を通してのみアクセス可能である場合に、オンライン学習に必要な神託呼び出しを、ランダム化が確実に減少させるかどうかを問うた。
未知のTインスタンスの総順序に対するしきい値のトランスダクティブオンライン学習と、クエリされたラベル付きセットと整合した完全な概念を返却する一貫性型ERMオラクル、あるいは非実現可能性の報告。
論文 参考訳（メタデータ） (2026-09-09T14:02:47Z) - Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。
クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。
このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文 参考訳（メタデータ） (2026-01-07T22:07:44Z) - On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。
予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
論文 参考訳（メタデータ） (2025-11-17T23:58:11Z) - Fair Ordering in Replicated Systems via Streaming Social Choice [2.480023305418]
先行研究は、複製された状態マシンにおける「かなり」順序付けトランザクションの問題を研究する。
我々は、この問題は社会選択論のレンズを通して最もよく見られていると論じる。
論文 参考訳（メタデータ） (2023-04-05T20:20:15Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2023-01-29T20:42:54Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
論文 参考訳（メタデータ） (2022-11-19T11:14:19Z) - Private Query Release via the Johnson-Lindenstrauss Transform [93.20051580730234]
差分プライバシーを持つ統計的クエリに対する回答を解放する新しい手法を提案する。
鍵となる考え方は、クエリの回答を低次元空間にランダムに投影することである。
単純なノイズ付加機構を用いて予測されたクエリに回答し、元の次元まで答えを引き上げます。
論文 参考訳（メタデータ） (2022-08-15T19:19:16Z) - Query complexity of heavy hitter estimation [6.373263986460191]
我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-05-29T07:15:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。