Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Unrestricted randomized adaptive query procedures

Definition
SketchAttr_LOO_Supplement_Adaptive

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

adaptive-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity

A procedure with worst-case budget qqq consists of an arbitrary seed space, measurable query functions, and a measurable terminal output function. At round ttt, the next query depends on the seed and all ttt previous answers. The output depends on the seed and the completed transcript:

Qt=Qt(s,a0,…,at−1),L^=H(s,a0,…,aq−1).Q_t=Q_t(s,a_0,\ldots,a_{t-1}),\qquad \widehat L=H(s,a_0,\ldots,a_{q-1}).Qt​=Qt​(s,a0​,…,at−1​),L=H(s,a0​,…,aq−1​).

The unknown matrix is accessible only through the oracle that generates the answers. There is no restriction on computation between queries. Earlier stopping is represented by padding to the worst-case budget and ignoring the extra answers. The seed law is supplied separately, independently of the unknown input. This reusable interface is independent of the particular matrix and higher-derivative oracles.

Definition code
import Mathlib

open MeasureTheory

namespace SketchAttr.LOO.Supplement

/-- Unrestricted measurable adaptive q-query procedures. Neither the query
functions nor the terminal output receive the unknown oracle parameter.
A stopping procedure is padded with unused queries to its worst-case budget. -/
structure AdaptiveProcedure (Seed Query Answer Output : Type*)
    [MeasurableSpace Seed] [MeasurableSpace Query]
    [MeasurableSpace Answer] [MeasurableSpace Output] (q : ℕ) where
  query : (t : ℕ) → Seed → (Fin t → Answer) → Query
  output : Seed → (Fin q → Answer) → Output
  query_measurable : ∀ t, Measurable (Function.uncurry (query t))
  output_measurable : Measurable (Function.uncurry output)

/-- The history consists of exactly t previous answers, in chronological order.
The seed is fixed through the entire run. -/
noncomputable def adaptiveHistory {Seed Query Answer Output : Type*}
    [MeasurableSpace Seed] [MeasurableSpace Query]
    [MeasurableSpace Answer] [MeasurableSpace Output] {q : ℕ}
    (P : AdaptiveProcedure Seed Query Answer Output q)
    (oracle : Query → Answer) (seed : Seed) : (t : ℕ) → Fin t → Answer
  | 0 => Fin.elim0
  | t + 1 =>
    let h := adaptiveHistory P oracle seed t
    Fin.snoc h (oracle (P.query t seed h))

noncomputable def adaptiveOutput {Seed Query Answer Output : Type*}
    [MeasurableSpace Seed] [MeasurableSpace Query]
    [MeasurableSpace Answer] [MeasurableSpace Output] {q : ℕ}
    (P : AdaptiveProcedure Seed Query Answer Output q)
    (oracle : Query → Answer) (seed : Seed) : Output :=
  P.output seed (adaptiveHistory P oracle seed q)

end SketchAttr.LOO.Supplement
Source
Chris Liaw, Aranyak Mehta, Grigoris Velegkas, Felix Zhou, Sketching Language Models for Context Attribution, STOC 2027 submission #9 (October 2026), PDF sha256 86af2569e45c55b1009e7453d4f53047b5820d44868a7f528bdb6fed1a2ef0e2, Section 5.3, p. 19, and Appendix C, p. 29

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me