Scout: Scalable Document Extraction via Data Similarity

Scout: Scalable Document Extraction via Data Similarity Yiming Lin∗ , Chiyu Hao† , Shreya Shankar∗ , Aditya G. Parameswaran∗ ∗ UC Berkeley, † Shanghai Jiao Tong University

{yiminglin, shreyashankar, adityagp}@berkeley.edu, haochiyu84@gmail.com

arXiv:2608.08261v1 [cs.DB] 8 Aug 2026

Abstract Extracting values from large document collections powers data analysis across a variety of domains. Frontier LLMs extract such values accurately, but processing an entire collection using one is prohibitively costly. Yet this cost is largely avoidable: real-world collections exhibit rich similarity, so for the same query over a set of similar documents, the answer tends to recur in similar locations; an LLM need only read that small span, not the whole document. Prior methods that exploit this similarity fall short: they either assume a rigid document structure, or assume the answer is a set of substrings of the input and use an LLM-generated program to return it directly. Even a frontier agent fails to generate effective programs to directly locate the answer’s span, as the search space is large and programs learned from a small sample tend to be overfitted. We present Scout, a tool that generates accurate and cost-effective programs (that we call rules) to extract data at scale. From a few sampled documents, Scout generates a broad rule set and refines it by selecting a pareto-optimal subset with low cost without sacrificing accuracy. We prove this rule refinement to be NP-hard and present a greedy solution with a provable approximation guarantee. Scout can handle collections that are only partly similar, where similarity holds within clusters of documents. For such a setting, a sampling strategy, using no LLM, extracts samples from each cluster of similar documents; and a cascade strategy selects a subset of refined rules, falling back to the unrefined rule set when the selected rules don’t contain the answer. Experiments on six real-world datasets show that Scout matches the accuracy of the strongest baseline, a frontier LLM agent that reads each full document, while being 61× to over 1000× cheaper on a collection of 1,000 documents, and is 61% more accurate than the strongest prior program-based approach. PVLDB Reference Format: Yiming Lin∗ , Chiyu Hao† , Shreya Shankar∗ , Aditya G. Parameswaran∗ . Scout: Scalable Document Extraction via Data Similarity. PVLDB, XX(X): XXX-XXX, 2027. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/yiminl18/SCOUT.

1

Introduction

Data analytics in many domains centers on processing documents, including SEC filings in finance [23], federal court opinions in law [1], and drug product labels in medicine [2]. At the core of This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. XX, No. X ISSN 2150-8097. doi:XX.XX/XXX.XX

Q1: What is the commission file number?

Q2: Did management report any material weaknesses in internal control over financial reporting? (Yes/No)

Evaporate

Evaporate

Source: . . . Commission file number 1-3285 . . . State of Incorporation: Delaware . . . Code: re.search(r"Commission file number\s+([\d-]+)", doc) Answer: 1-3285 ✓

Source: . . . fatigue testing revealed a material weakness in the titanium alloy of our turbine blades, prompting a product recall . . . Code: re.search(r"material weakness(es)?", doc) Answer: Yes ✗

Ground truth source (Q2): . . . management concluded that internal control over financial reporting was effective as of December 31, 2022 . . . ⇒ Answer: No ✓

Figure 1: Extraction queries over a 10-K. Each panel shows the query, its source span (answer-relevant parts in blue italics), and the program Evaporate generates with the answer it returns.

these analyses is extracting structured fields from the documents. Table 2 lists representative domains and the fields extracted from each. These tasks all hinge on extraction that is both accurate and scalable. Large language models (LLMs) have proven powerful for document extraction, but running them directly over large document collections is prohibitively costly. For example, extracting data specified in Table 2 from 1M financial reports (e.g., from OfficeQA [38], each with ~110,000 tokens) with GPT-5.5 naively would cost ~$275,000. Pre-trained ML models, on the other hand, while inexpensive, are narrow: each is tuned to one domain, does not generalize, and struggles with complex extraction. We need an approach that matches the accuracy of LLMs with the low cost to scale to large collections. Thankfully, real-world documents are rarely independent: collections exhibit rich similarity that can be exploited for scale, in two forms. First, documents may share similar structure, as in a template or layout, such as articles from the same publisher or medical reports from the same hospital. Second, documents may share domain semantics, the same concepts and terminology, as research papers in the same field do. This similarity leads to one key insight: for the same query over a set of similar documents, the answer tends to recur in similar locations. Such similarity makes extraction scalable: once the answer’s location has been learned, the LLM needs to only read that small span, rather than the complete document. Prior work leveraging data similarity falls short. Prior work exploiting data similarity for scalable extraction falls into two categories. One assumes documents share a rigid structure, such as a tabular [29] or hierarchical [30] template, or structured markup such as HTML tags of web pages [7, 11, 14, 17, 27], and uses it to locate and extract the target field. Such approaches fail when a collection follows no consistent template or markup. The other [8] assumes each answer is a substring of the input, so that an LLMgenerated program can extract it directly; e.g., in Figure 1, a regex can recover the commission file number (Q1). Such approaches break down when the answer is not stated in the text and must

Ground truth span

Sampled Documents

Unsampled Documents

Question: What was the year-over-year net sale growths in 2018?

Rule 1 (r1): Return span of Section titled “Item 8: Financial Statements and Supplementary Data.”

Rule 2 (r2): Return span of Table titled “Consolidated Statement of Income”

Rule 3 (r3):

r1

r1

Return span with 1000 tokens under the keyword called “net sales”

r3

… r2

…

r2

r2

d1 a) Total ruleset generated by agents given the question, sampled documets, and their answers

r2

r3

dn dn

dk+1

dk

b) Illustration of rule refinment and application in SCOUT

Figure 2: Motivating example to illustrate Scout’s pipeline on financial datasets. instead be inferred from the context; for Q2, a program matching “material weakness” returns a false positive. Beyond the above, a large body of work studies extraction from each document individually, ignoring data similarity, and is thus either inaccurate at scale or not scalable; we defer detailed discussion to Section 7. Frontier agent for data extraction program synthesis. Deterministic programs are attractive for extraction because they are cheap and fast. One approach synthesizes a program to emit the answer directly, e.g., [8], which is brittle. Instead, one can instruct a frontier agent (e.g., Codex [37]) to generate programs, or what we call rules, that return only the subset of a document where the answer lies, then let an LLM read that subset to produce the answer. Since the LLM, not the program, produces the final answer, this approach is more flexible, at the cost of a little extra reasoning over the located span. For the net-sales query in Figure 2, an agent may generate rules 𝑟 1 –𝑟 3 , each returning a candidate location: 𝑟 1 the section titled “Item 8. . . ”, 𝑟 2 the income-statement table, and 𝑟 3 the 1000 tokens around the keyword “net sales”. The green ground-truth span is where the answer lies, and an oracle (e.g., a top-of-the-line LLM) can extract the answer from it. If a rule such as 𝑟 2 returns a small superset of this span, an oracle reading only that span, rather than the full document, yields correct answers at low cost, whenever such a location pattern recurs across the collection. So, can a frontier agent generate effective rules that locate answers accurately? We run a GPT-5.4 agent on the six datasets in Table 1 (baseline agent), giving it the documents, queries, and tools that measure each program’s accuracy (whether the located span lets the oracle recover the answer) and cost (the fraction of the document fed to the oracle), with targets of high accuracy and low cost (setup described in Section 6). The agent typically samples a few documents, obtains the oracle’s answer on each, iteratively generates rules until the targets are met, applies them to the unsampled documents, and is scored against the ground truth. As Table 1 shows, its set of rules is still 16 points less accurate than what we call a golden baseline, which runs the same agent over each full document; and though far cheaper than that baseline, its cost is over 3× what is achievable: $0.016 per document, versus the $0.0047 our approach achieves at the golden baseline’s accuracy. This gap has two systematic causes. First, selecting a cheap yet accurate subset from the large space of candidate rules is NP-hard (Section 4), and the agent searches this space heuristically, with no guarantee of near-optimality. Second, to keep the generation cost low, the agent learns rules from a small sample, so they may

Golden baseline

Baseline agent

Dataset (# of docs)

Accu

$/doc

Accu

$/doc

Accu

Scout $/doc

Court (294) FinanceBench (100) NoPV (242) OfficeQA (200) Product (200) Tropic (200)

0.918 0.986 0.922 0.830 0.902 0.813

0.24 0.22 0.28 0.74 0.25 0.21

0.751 0.764 0.781 0.666 0.802 0.671

0.008 0.020 0.011 0.034 0.013 0.011

0.925 0.943 0.929 0.831 0.886 0.873

0.0004 0.0096 0.0039 0.0031 0.0040 0.0072

Average

0.895

0.32

0.739

0.016

0.898

0.0047

Table 1: Accuracy and cost of agentic data extraction; $/doc amortizes program-generation cost over the collection.

overfit and fail to generalize to the rest of the collection; enlarging the sample raises the generation cost. Scout: robust and effective rule generation for scalable extraction. To use agents for program synthesis while overcoming their lack of guarantees, we propose Scout1 , which generates accurate and cost-effective extraction rules with provable guarantees, and is broadly applicable, without requiring rigid document structure or answers being substrings of the input. Developing Scout involves two challenges. The first is to learn, from a few sampled documents, a rule set that generalizes to the rest of the collection with high accuracy and low cost. The second is that a collection is rarely uniform: answers may recur in similar locations only within clusters of documents, so rules learned from one cluster may miss the others. Scout addresses both through a series of techniques, organized as the pipeline in Figure 3. Given the extraction query 𝑄, a set of sampled documents (our sampling approach is described shortly), and their answers produced by an oracle LLM, Scout first prompts an agent to generate a set of candidate rules (rule generation in Section 3). This step prioritizes correctness over cost. We say a set of rules is correct on a document if the oracle can reproduce the answer from the union of the spans returned by its rules. In this step, Scout instructs the agent to generate as many rules as possible, each returning a subset of each document by capturing a recurring answer pattern, so that their union is correct on as many documents as possible. This is both critical and achievable: we empirically show later (Table 3) on six real-world datasets that the generated rules, when applied, match the accuracy of the most accurate but expensive baseline that runs the oracle over each complete document. Although the complete set of rules Scout generates is correct on most documents, it may contain both inefficient rules, which return too much text (e.g., 𝑟 1 in Figure 2), and inaccurate rules, which 1 Scout stands for Scalable document extraction via data similarity

2

Dataset

Description

Extracted data

FinanceBench [23]

SEC financial filings (10-K and 10-Q) from major publicly traded companies.

Registrant name, state of incorporation, reporting period, total revenue and net income, total assets, stock exchange and trading symbol.

Court [1]

U.S. federal court appeal opinions.

Docket numbers, presiding and panel judges, argument and filing dates, final disposition, majority opinion author.

NoPV [3]

PHMSA Notices of Probable Violation for pipeline safety.

Operator name, CPF case number, PHMSA region, cited CFR sections, correctiveaction deadlines, inspection dates.

OfficeQA [38]

U.S. Treasury Bulletins of periodic financial reports.

Quarter and year, GDP growth, unemployment rate, federal deficit, gross federal debt, total federal receipts, debt held by the public.

Publications [18]

Academic and scientific research papers.

Title, authors, affiliations, venue and year, DOI, datasets referenced.

Medical Records [25]

Clinical patient records such as admission notes and discharge summaries.

Patient MRN, age and sex, admission and discharge dates, diagnoses (ICD codes), medications, attending physician.

NHC Tropical Cyclone Reports [4]

Post-storm reports from the U.S. National Hurricane Center.

Cyclone name, basin-year identifier, report date, lead author, minimum central pressure, peak winds, direct deaths, total damage.

EMA EPAR Product Information [2]

EU drug product labels (Summary of Product Characteristics) from the European Medicines Agency.

Product name, active substance, pharmaceutical form, first therapeutic indication, ATC code, half-life, marketing authorisation holder.

Table 2: Datasets from distinct domains, with representative values extracted per document. Answers on D∖Ds

often miss the answer (e.g., 𝑟 3 ). Applying all of them is therefore unnecessarily expensive. Scout performs rule refinement (Section 4) to select the lowest-cost subset that remains correct on the sampled documents. Here, we assume the oracle is monotone: if a span is sufficient for it to reproduce the answer, so is any superset of that span. Building on this assumption, our key insight is that once a rule subset is correct on a document, adding more rules cannot make it incorrect, since the union of returned spans still contains the answer. We show that rule refinement is NP-hard via a reduction from Set Cover, so Scout uses a greedy, provably near-optimal algorithm with an approximation factor of 𝑂 (ln 𝑛), where 𝑛 is the number of sampled documents. At each step it adds the rule correct on the most not-yet-covered documents per unit of additional cost, favoring rules correct on many documents, which curbs overfitting. A subset selected on the sampled documents is still not enough, since a rule correct on the sample may fail on an unseen document. Scout therefore constructs a cascade of nested rule subsets (detailed in rule application in Section 5.2): the first refined rule, the first two rules, and so on, ordered by their accuracy-to-cost ratio. For each subset in order, a cheap proxy LLM checks whether the returned spans contain enough information to answer 𝑄. If so, the oracle answers 𝑄 from those spans; otherwise, Scout proceeds to the next subset. If no refined subset passes the proxy, Scout falls back to the complete set of rules, which is correct on nearly all documents. Finally, when a collection is not uniformly similar, Scout uses a sampling strategy (Section 5.1). Such a collection splits into clusters, i.e., groups of documents whose answers share the same location pattern (e.g., in the same section) and are covered by one rule; the sample must include one document per cluster. This is difficult as identifying the clusters requires both the rules and the oracle, to verify which rules are correct on which documents, and neither is known a priori. Scout instead approximates by identifying the clusters with no LLM calls, computing the distribution of embedding similarities between the query and a document’s chunks, which is used to further approximate the similarity between documents. It then draws a sample by repeatedly choosing the document least similar to those already selected, to cover distinct clusters. We summarize our contributions as follows.

Oracle R′

Unsampled Documents D∖Ds

Yes

4) Rule Application If Proxy is No: R

No Proxy

Document collection D 1) Sampling

As+Agent 2) Rule Generation Sample Ds

3) Rule Refinement

Refined Rules R′

Rules R



Figure 3: Pipeline of Scout. • We formalize document similarity as rules, Python programs synthesized by LLMs that retrieve portions of documents to be fed into an oracle LLM. Such rules serve as primitives for scalable document extraction. (Section 2) • We formalize the selection of an accurate, cost-efficient rule set as a pareto-optimal optimization problem, prove it to be NP-hard, and provide a greedy algorithm with a provable approximation guarantee. (Section 4) • We develop techniques that improve robustness for collections of varying similarity, including a sampling strategy and cascade rule application. (Section 5) • We show on six datasets that Scout matches the accuracy of a frontier agent that processes each complete document while being 61× to over 1000× cheaper at 1,000 documents, and is 61% more accurate than the strongest prior programbased approach. (Section 6)

2

Rule Definition and Overview of Scout

In this section, we formalize the concept of rules and then give an overview of Scout.

2.1

Preliminaries

Consider a data extraction query 𝑄 in natural language and a document collection D = {𝑑 1, 𝑑 2, . . . , 𝑑𝑛 }. Let 𝑂 be an oracle that takes a document 𝑑 𝑗 as input and produces the answer 𝐴 𝑗 to 𝑄, denoted 3

𝑂 (𝑑 𝑗 , 𝑄) = 𝐴 𝑗 . The oracle 𝑂 is a ground-truth labeler (e.g., a human) or a top-of-the-line LLM (e.g., GPT-5.5). Given D and 𝑄, our goal is to produce 𝐴 𝑗 for every 𝑑 𝑗 ∈ D, matching the accuracy of the oracle but at minimal cost. For now, we focus on a single query 𝑄 over the collection D; we discuss multiple queries in Section 6. Here, both |D | and the size of an individual document can be large, making answering 𝑄 over the entire collection prohibitively costly. We treat each document 𝑑 𝑗 as a sequence of words in their reading order, 𝑑 𝑗 = [𝑤 𝑗1, 𝑤 𝑗2, . . . , 𝑤 𝑗𝑚 ], obtained by serializing its source file (e.g., a PDF or Word document) with off-the-shelf OCR tools, e.g., docling [9]. An image is treated as a special word that points to its location in the document, i.e., its page and bounding box, so an LLM can analyze it, say, to extract data from it.

2.2

average cost ratio of a set of rules 𝑅 over a document collection 𝐷 Í 𝑑 ∈𝐷 𝑐𝑟 (𝑅,𝑑 𝑗 )

. is 𝑐𝑟 (𝑅, 𝐷) = 𝑗 |𝐷 | Finally, we state a monotonicity property that formalizes an assumption about oracle behavior. Given 𝑄, if a subsequence 𝑑 𝑖𝑗 ⊆ 𝑑 𝑗 produces the oracle answer, i.e., 𝑂 (𝑑 𝑖𝑗 , 𝑄) = 𝑂 (𝑑 𝑗 , 𝑄), then any superset 𝑆 of it with 𝑑 𝑖𝑗 ⊆ 𝑆 ⊆ 𝑑 𝑗 also produces 𝑂 (𝑑 𝑗 , 𝑄), since adding extra text to 𝑑 𝑖𝑗 never misses the span that produces the answer. This property carries over to rules: if a rule set 𝑅 ′ is correct on 𝑑 𝑗 , then any superset 𝑅 ⊇ 𝑅 ′ is also correct on 𝑑 𝑗 , because applying 𝑅 Ð returns the union 𝑟𝑖 ∈𝑅 𝑑 𝑖𝑗 to the oracle, which only grows as rules are added. Under this assumption, a set of rules 𝑅 over a document set 𝐷 has accuracy at least that of any of its subsets over 𝐷, i.e., 𝑎(𝑅, 𝐷) ≥ 𝑎(𝑅 ′, 𝐷) for any 𝑅 ′ ⊆ 𝑅. We formally state this as the accuracy monotonicity property below.

The Notion of Rules

Property 1 (Accuracy monotonicity). For any rule sets 𝑅 ′ ⊆ 𝑅 and any document 𝑑 𝑗 , 𝑎(𝑅 ′, 𝑑 𝑗 ) = 1 ⇒ 𝑎(𝑅, 𝑑 𝑗 ) = 1. Consequently, 𝑎(𝑅 ′, 𝐷) ≤ 𝑎(𝑅, 𝐷) for any document set 𝐷.

To support accurate extraction at low cost, we observe that answers to the same query often recur in similar patterns across similar subsets of a document collection. We model answer locations using rules, on which we build the notion of data similarity. Let 𝑟𝑖 be a rule, implemented as a Python program synthesized by an agent. Given a document 𝑑 𝑗 , it returns a subsequence 𝑑 𝑖𝑗 ⊆ 𝑑 𝑗 . For example, for the query “What was the year-over-year net sales growth in 2018?” in Figure 2(a), rule 𝑟 2 returns the “Consolidated Statement of Income” table of a 10-K document 𝑑 𝑗 as its subsequence 𝑑 2𝑗 . However, not all rules are effective. Some return a span that misses the ground-truth answer, such as rule 𝑟 3 on document 𝑑 1 in Figure 2(a). Others return a span that contains the answer but is unnecessarily large, so the oracle still incurs a high cost, such as rule 𝑟 1 , which returns the entire “Item 8” section. We define a few properties below to quantify how effective a rule is. Accuracy. Given the query 𝑄, a rule 𝑟𝑖 is correct on document 𝑑 𝑗 if running the oracle 𝑂 on the returned subsequence 𝑑 𝑖𝑗 produces the answer 𝑂 (𝑑 𝑗 , 𝑄), i.e., 𝑂 (𝑑 𝑖𝑗 , 𝑄) = 𝑂 (𝑑 𝑗 , 𝑄). We denote the accuracy of 𝑟𝑖 on 𝑑 𝑗 as 𝑎(𝑟𝑖 , 𝑑 𝑗 ) ∈ {0, 1}. Now, we define the accuracy of a set of rules, also called a rule set, 𝑅 = {𝑟 1, . . . , 𝑟𝑚 } on document 𝑑 𝑗 as 𝑎(𝑅, 𝑑 𝑗 ). 𝑅 is correct on 𝑑 𝑗 if running the oracle on the union of Ð its returned subsequences 𝑟𝑖 ∈𝑅 𝑑 𝑖𝑗 produces the same answer, i.e., Ð 𝑂 ( 𝑟𝑖 ∈𝑅 𝑑 𝑖𝑗 , 𝑄) = 𝑂 (𝑑 𝑗 , 𝑄). Finally, the accuracy of 𝑅 over a docu-

Even a top-of-the-line LLM (e.g., GPT-5.5) is not a true oracle, so monotonicity may not always hold. Such failures are rare in practice: a recent study [31] (published at VLDB 2026) reports that monotonicity holds on over 94% of documents across real-world datasets, and we therefore adopt it as an assumption. When monotonicity fails on a document, only that document is affected, so the guarantees that follow degrade by at most the fraction of documents on which monotonicity fails. Having formalized rules, we now give an overview of Scout.

2.3

As shown in Figure 3, given a data extraction query 𝑄 and a document collection D, Scout is a tool that consists of four steps to generate effective programs to extract data from D. Given 𝑄, Scout first samples a subset 𝐷𝑠 ⊆ D (Section 5.1, described later), then uses an agent to generate a set of rules from 𝐷𝑠 and 𝑄, prioritizing accuracy (Section 3). Scout then refines these rules by selecting a subset that preserves their accuracy while reducing cost (Section 4). Selecting such a subset from the large space of candidate rules is NP-hard, so Scout employs a greedy approach with a provable guarantee. Because the rules are selected on the sample, a rule correct on 𝐷𝑠 may still be incorrect on an unseen document. To reduce this overfitting and to handle collections where not all documents are similar, Scout uses two strategies (Section 5): (1) a sampling strategy that draws a small but representative document subset (Section 5.1), and (2) a rule-application strategy that applies the refined rules using a cascade with a proxy model and a fallback (Section 5.2).

Í

𝑑 ∈𝐷 𝑎 (𝑅,𝑑 𝑗 )

ment set 𝐷 = {𝑑 1, . . . , 𝑑𝑙 } is 𝑎(𝑅, 𝐷) = 𝑗 |𝐷 | , the fraction of documents in 𝐷 on which 𝑅 is correct. A good rule should also be general: it should be correct on many documents rather than a few, so that it captures a recurring answer pattern rather than a coincidence in a handful of documents. We measure this generality by the coverage of a rule 𝑟𝑖 over a document set 𝐷, which Í is basically its accuracy taken individually over 𝐷: 𝑑 ∈𝐷 𝑎 (𝑟𝑖 ,𝑑 𝑗 )

𝑎(𝑟𝑖 , 𝐷) = 𝑗 |𝐷 | , the fraction of documents in 𝐷 on which 𝑟𝑖 is correct. Cost. Beyond being correct and general, a rule should also be costeffective: the subsequence it returns should be small enough to keep the cost of the oracle on that subsequence low. We define the cost of a rule 𝑟𝑖 on document 𝑑 𝑗 as the number of tokens in the subsequence it returns, denoted c(𝑟𝑖 , 𝑑 𝑗 ) = |𝑑 𝑖𝑗 |. We further define

3

|𝑑 𝑖 |

|

Ð

𝑖 𝑟𝑖 ∈𝑅 𝑑 𝑗 |

|𝑑 𝑗 |

Rule Generation

We now introduce how to generate an initial rule set by using an agent. For now, we assume we are given a query 𝑄 and a sampled subset 𝐷𝑠 ⊆ D, and defer how to construct 𝐷𝑠 to Section 5.1. Rule generation prioritizes accuracy over cost: it aims for a broad rule set with high accuracy over D, even if the cost of applying all its rules is high. This allows the larger set of generated rules to be used as a fallback, when a small set of refined rules does not contain the answer (as we will see later).

the cost ratio of 𝑟𝑖 on 𝑑 𝑗 as cr (𝑟𝑖 , 𝑑 𝑗 ) = |𝑑 𝑗𝑗 | , the fraction of 𝑑 𝑗 ’s tokens that 𝑟𝑖 retrieves. Similarly, 𝑐𝑟 (𝑅, 𝑑 𝑗 ) =

Overview of Scout

. Finally, the 4

Scout-RuleGen-Prompt: You are a document rule engineer working in the project repository. You are given a question [Question] and, for each sampled document, its enriched span representation [Documents] together with the ground-truth answer [Answers]. Write Python span-retrieval rules def rule_name(doc) that return the spans that contain the answer from the given collection. Objective: maximize the accuracy of the rule pool, and keep the cost ratio of each individual rule low. Generate as many rules as possible to capture distinct data patterns. Targets (accuracy first): (1) accuracy of the total rules at least 0.95 on the sampled documents; (2) each rule’s cost ratio below 0.1; accuracy always takes priority over cost. Tools: [Accuracy specification] and [Cost ratio specification] are callable tools. You may also use all default agent tools, [default tool specifications], e.g., load a document, filter spans by label, page, or keyword, search tables, retrieve spans by embedding similarity, and evaluate arithmetic. Workflow (iterative): study where the answer sits in each sampled document; add one or more new rules to the current pool and measure their accuracy and cost with the tools; never discard an existing rule. Repeat, extending the pool, until the soft targets are met. Hints: locate the answer using (1) physical location (page), (2) semantic location (section header or path), (3) keyword proximity, (4) data features (table cells), (5) typography (bold, large, or all-caps), (6) structural position (heading level and depth), and (7) any other recurring pattern. Requirements: each rule must be self-contained, must never raise, and must return an empty list when nothing matches. Prefer returning a few extra spans over missing the answer.

def rule_net_sales(doc): # "Consolidated Statement of Income" tables # that report net sales. out = [] for span in doc["texts"]: if span["label"] != "table": # tables only continue path = span["structure"]["path_text"].lower() text = span["text"].lower() # keep only the Consolidated Statement of Income if "consolidated statement of income" not in path: continue # match in the rendered text or in the cells if "net sales" in text \ or "net sales" in join_cells(span): # ... out.append(span) return out # (returns [] on any error)

Figure 4: Python script of 𝑟 2 in Figure 2.

3.1

Rule Generation

Input and tools. Rule generation takes as input a query 𝑄, sampled documents 𝐷𝑠 , and their oracle answers {𝐴 𝑗 : 𝑑 𝑗 ∈ 𝐷𝑠 }, obtained by running the oracle 𝑂 on each 𝑑 𝑗 ∈ 𝐷𝑠 . Although a document is a sequence of words, we do not expose this word sequence to the agent. Instead, let 𝑑b𝑗 be 𝑑 𝑗 enriched by open-source OCR tools (e.g., Docling). 𝑑b𝑗 is a list of consecutive spans in reading order, 𝑑b𝑗 = ⟨𝑜 𝑗1, 𝑜 𝑗2, . . . , 𝑜 𝑗𝑘 ⟩, where each span 𝑜 𝑗𝑖 is a contiguous sequence of words annotated with a type label (e.g., section_header, text, table, list_item), a page number, typographic attributes (e.g., a bold flag and font size), and structural metadata (e.g., for tables, the row and column cell grid, and the caption/title). The spans partition the words of 𝑑 𝑗 , so 𝑑b𝑗 is a labeled segmentation over the words of the document, and a rule reads both this span structure and the span text (e.g., via regex or keyword matching) to decide which sequence of words to return, down to spans or sub-spans. The output is a rule set 𝑅 = {𝑟 1, . . . , 𝑟𝑚 }, each a Python function that maps a document to a subsequence of 𝑑 𝑗 (Section 2.2); Figure 4 shows one rule for the net-sales query, which returns the table spans in the “Consolidated Statement of Income” whose text or cells mention “net sales”, regardless of the page it appears on. Beyond documents, the agent is equipped (powered by GPT-5.4, but any frontier LLM would work) with a set of tools: its accuracy and cost-ratio metrics (Section 2.2), exposed as tools so the agent can measure how good a rule (or a ruleset) is, as well as the default agentic tools (in this case from OpenAI) for inspecting documents, such as loading and filtering spans by page, or keyword, searching tables, or retrieving spans by embedding similarity. Embeddingbased retrieval is one pattern a rule can express, making retrievalaugmented extraction possible via rules; rules may additionally capture structural and positional patterns, such as a section, a table, or a page, that semantic similarity alone may miss. Prompt specification. The agent is instructed as a document rule engineer to emit Python-based functions with format def rule_name(doc) to return subsets of documents that may contain the answer (the full prompt is in Figure 5). The agent is instructed to maximize the accuracy of the rule set while keeping each individual rule cheap. To this end, it is instructed to generate as many rules as possible, each capturing a distinct data pattern (such as the

Figure 5: A concise version of the rule-generation prompt. hint categories below); this diversity reduces overfitting and keeps accuracy 𝑎(𝑅, D) high across D. Concretely, the prompt states two targets, with accuracy taking priority: (i) the accuracy of the rules on the sample 𝐷𝑠 is at least 0.95, and (ii) each rule’s cost ratio is below 0.1. Given 𝑄, 𝐷𝑠 , and their oracle answers, {𝐴 𝑗 : 𝑑 𝑗 ∈ 𝐷𝑠 }, the prompt lists seven hint categories for locating oracle answers in the sample 𝐷𝑠 , namely physical location (page), semantic location (section header or path), keyword proximity, data features (table cells), typography (bold, large, or all-caps), structural position (heading level and depth), and an open-ended “any other” category. The prompt also requires each rule to be self-contained and to return an empty list when nothing matches. When unsure, an agent is instructed to have a rule to return extra spans rather than risk dropping the answer. Iterative agentic rule generation. Scout generates the rule set with an agent that tests and iterates on candidate rules. Starting from an empty set, the agent initially generates as many rules as possible; in later iterations, it is instructed to generate rules for the sampled documents on which the current rule set is not yet correct, checking their accuracy and cost with the tools above. Agent continues until the targets are met.

3.2

Empirical Assessment: Rule Quality

So far, we have presented how an agent can produce a rule set 𝑅 based on sample 𝐷𝑠 ; now we empirically evaluate how accurate 𝑅 is over the entire collection D. We evaluate agent-generated rules on six datasets from distinct domains, each using a sample (generated by our strategy to be described in Section 5.1) and a Codex agent powered by GPT-5.4 as the oracle. We defer the setup details to Section 6. For each query, 𝑅 has on average 19 to 41 rules across the datasets (column Avg # rules), each encoding one recurring pattern of where the answer resides. Table 3 reports the accuracy 𝑎(𝑅, D) (column Scout) and cost ratio cr (𝑅, D) (column Cost ratio) of 𝑅 5

Dataset (# Sampled / # Total)

Scout

Golden baseline

Cost ratio

Cost ratio (refined rules)

Avg # rules

FinanceBench (20/100) Court (20/294) NoPV (20/242) OfficeQA (20/200) Product (20/200) Tropic (20/200)

0.943 0.925 0.929 0.831 0.886 0.873

0.986 0.918 0.922 0.830 0.902 0.813

0.088 0.074 0.392 0.208 0.096 0.211

0.0056 0.0047 0.0373 0.0035 0.0153 0.1015

∼35 ∼40 ∼41 ∼33 ∼19 ∼28

Pareto-optimal rule set Non-pareto-optimal rule set Pareto-optimal curve

a(R,Ds) a(R,Ds) - 𝛼

over the collection D. We also present a golden baseline that runs the oracle 𝑂 over each entire document 𝑑 𝑗 , the most accurate but most expensive strategy. Table 3 reveals two findings. First, the agent-generated rules have high recall. We measure the accuracy 𝑎(𝑅, D) of the returned rule set 𝑅. 𝑎(𝑅, D) for Scout’s rules, 0.898, matches the golden baseline’s 0.895. Hence the rules, taken together, lose almost no accuracy relative to running the oracle 𝑂 on the entire document. Second, there is substantial room to reduce cost. Even without refinement, the rule set 𝑅 is efficient: its union reproduces the golden-baseline accuracy while reading only a fraction of each document, a cost ratio 𝑐𝑟 of 0.07 to 0.39 versus cr = 1 for the full document. As we show in Section 6.2, a refined, selective subset of 𝑅 is far cheaper still: its cost ratio (column Cost ratio (refined rules)) reaches only 0.004 to 0.102, a 2× to 60× reduction over 𝑅’s at comparable accuracy. Achieving this reduction is the goal of rule refinement, described next.

1-cr(R’,Ds)

Figure 6: Rule refinement as a Pareto problem. that is at least as accurate. The two labeled rule sets 𝑅1′ and 𝑅2′ are both pareto-optimal, yet neither dominates the other: 𝑅1′ is more accurate while 𝑅2′ is cheaper. Problem 1 (Rule Refinement). Given the set of rules 𝑅, the sample 𝐷𝑠 , and an accuracy tolerance 𝛼 ≥ 0, find the pareto-optimal subset of least cost whose accuracy stays within 𝛼 of 𝑅’s accuracy on 𝐷𝑠 : 𝑅 ∗ = arg min cr (𝑅 ′, 𝐷𝑠 )

s.t. 𝑎(𝑅 ′, 𝐷𝑠 ) ≥ 𝑎(𝑅, 𝐷𝑠 ) − 𝛼 .

𝑅′ ∈ P

The tolerance 𝛼 controls how much accuracy we trade for cost. We center it at 𝑅’s accuracy because, by accuracy monotonicity (Property 1), no subset of 𝑅 can exceed 𝑎(𝑅, 𝐷𝑠 ). Taking 𝛼 = 0 then yields the cheapest subset of 𝑅 that matches 𝑅’s accuracy; a larger 𝛼 allows for a bounded drop in accuracy for further savings. Such an 𝑅 ∗ is pareto-optimal by definition. For example, if the tolerance admits both labeled subsets in Figure 6 (both sit above the 𝑎(𝑅, 𝐷𝑠 ) − 𝛼 line), an answer to Problem 1 would return 𝑅2′ . Complexity. Problem 1 is intractable even in its simplest form. Consider 𝛼 = 0, where we ask for the cheapest subset that matches 𝑅’s accuracy exactly. We show this is already NP-hard by a simple reduction from Set Cover: each rule corresponds to a set and each document an element, matching 𝑅’s accuracy requires the chosen rules to cover every document, and minimizing the cost ratio corresponds to minimizing the number of chosen rules. We state the result next .

Rule Refinement

As we saw, the agent generates a set of rules 𝑅 with high recall, yet applying all of 𝑅 returns far too much of each document, leaving substantial room to reduce cost. We now present rule refinement, which selects a small subset of 𝑅 that preserves accuracy while reducing cost.

4.1

R’2 : (0.6,0.88)

a(R’,Ds)

Table 3: Rule-generation quality.

4

R’1 : (0.2,0.9)

Problem Definition

Given the set of rules 𝑅 generated by the agent over the sample 𝐷𝑠 , for each rule 𝑟𝑖 ∈ 𝑅, and more generally any subset 𝑅 ′ ⊆ 𝑅, we can evaluate its accuracy 𝑎(𝑅 ′, 𝐷𝑠 ) and cost ratio cr (𝑅 ′, 𝐷𝑠 ) over 𝐷𝑠 , as defined in Section 2.2. The cost ratio is free to compute, as it only requires counting the fraction of tokens retrieved by a rule; accuracy, in contrast, requires invoking the LLM and is therefore more costly to estimate. Intuitively, the subset of rules we retain should be cost-efficient, selecting as little of each document as possible, and accurate, reproducing the oracle’s answer on every document. These goals conflict. We therefore seek subsets that best trade off cost against accuracy on the sample (the pareto-optimal ones). Note that generalization to unsampled documents is not part of this objective, but is handled separately by our algorithm, which favors general, high-coverage rules (Section 4.2). Now we define a pareto-optimal set:

Theorem 4.2. Rule Refinement (Problem 1) is NP-hard, even for 𝛼 = 0. Proof. Fix 𝛼 = 0 and consider the decision version of Problem 1: given a budget 𝐵, decide whether some subset 𝑅 ′ ⊆ 𝑅 has cr (𝑅 ′, 𝐷𝑠 ) ≤ 𝐵 and 𝑎(𝑅 ′, 𝐷𝑠 ) ≥ 𝑎(𝑅, 𝐷𝑠 ). Since no subset can exceed the full pool’s accuracy (Section 4.1), the accuracy constraint is equivalent to 𝑎(𝑅 ′, 𝐷𝑠 ) = 𝑎(𝑅, 𝐷𝑠 ). We reduce from Set Cover, which is NP-complete [26]: given a universe 𝑈 = {𝑢 1, . . . , 𝑢𝑛 }, a family C = {𝐶 1, . . . , 𝐶𝑚 } with 𝐶𝑘 ⊆ 𝑈 , and an integer 𝑘, decide Ð whether 𝑘 of the sets cover 𝑈 . We assume 𝑘 𝐶𝑘 = 𝑈 (otherwise no cover exists and the instance is trivially negative). Oracle semantics. We instantiate the oracle as follows: every document carries a designated single-token answer span, and the oracle reproduces a document’s answer exactly when the text it receives contains that span. This semantics is monotone (extra text never removes a correct answer), so it satisfies the assumption behind Property 1; a rule set is correct on a document iff the union of its returned spans contains the answer span.

Definition 4.1 (Pareto-optimal subset). Given subsets 𝑅 ′, 𝑅 ′′ ⊆ 𝑅, 𝑅 ′ dominates 𝑅 ′′ if cr (𝑅 ′, 𝐷𝑠 ) ≤ cr (𝑅 ′′, 𝐷𝑠 ) and 𝑎(𝑅 ′, 𝐷𝑠 ) ≥ 𝑎(𝑅 ′′, 𝐷𝑠 ), with at least one inequality strict. 𝑅 ′ is pareto-optimal if no subset dominates it. P is the set of all pareto-optimal subsets. For example, in Figure 6 the circles are pareto-optimal and the crosses are not, with each cross being dominated by a cheaper circle 6

Construction. In polynomial time we build a refinement instance. The sampled subcollection is 𝐷𝑠 = {𝑑 1, . . . , 𝑑𝑛 } ∪ {𝐺 1, . . . , 𝐺𝑚 }: one element document 𝑑 𝑗 per element 𝑢 𝑗 , and one ballast document 𝐺𝑘 per set 𝐶𝑘 . Every document has 𝑇 = 2𝑚𝑛 + 1 tokens, with its answer span at the last token. The pool has one rule per set, 𝑅 = {𝑟 1, . . . , 𝑟𝑚 }, defined by what each rule returns: • on element document 𝑑 𝑗 , rule 𝑟𝑘 returns 𝑑 𝑗 ’s answer span if 𝑢 𝑗 ∈ 𝐶𝑘 , and the empty span otherwise; • on ballast document 𝐺𝑘 , rule 𝑟𝑘 returns the first 𝑇 − 1 tokens of 𝐺𝑘 , missing its answer span, while every other rule returns the empty span. Hence cr (𝑟𝑘 , 𝑑 𝑗 ) ∈ {0, 1/𝑇 }, whereas cr (𝑟𝑘 , 𝐺𝑘 ) = 1 − 1/𝑇 and cr (𝑟𝑘 ′ , 𝐺𝑘 ) = 0 for 𝑘 ′ ≠ 𝑘. No rule’s span contains a ballast document’s answer span, so 𝑎(𝑅 ′, 𝐺𝑘 ) = 0 for every subset 𝑅 ′ , including the full pool; the full pool answers exactly the 𝑛 element documents (each 𝑑 𝑗 via some 𝑛 𝐶𝑘 ∋ 𝑢 𝑗 ), so 𝑎(𝑅, 𝐷𝑠 ) = 𝑛+𝑚 . A subset 𝑅 ′ answers 𝑑 𝑗 iff its union Ð 𝑘 ′ 𝑟𝑘 ∈𝑅 ′ 𝑑 𝑗 contains 𝑑 𝑗 ’s answer span, i.e., iff some 𝑟 𝑘 ∈ 𝑅 has Ð 1 ′ 𝑢 𝑗 ∈ 𝐶𝑘 . Hence 𝑎(𝑅 , 𝐷𝑠 ) = 𝑛+𝑚 { 𝑗 : 𝑢 𝑗 ∈ 𝑟𝑘 ∈𝑅 ′ 𝐶𝑘 } , so

Algorithm 1: Rule refinement (cost-effectiveness greedy) Input: rule set 𝑅, sample 𝐷𝑠 , tolerance 𝛼 Output: refined subset 𝑅 ′ 1 foreach 𝑟 ∈ 𝑅 do 2 estimate 𝑎 (𝑟, 𝑑 𝑗 ) for all 𝑑 𝑗 ∈ 𝐷𝑠 with the cheap model; compute cr (𝑟, 𝐷𝑠 ) by token count 3 end ′ 4 𝑅 ← ∅; 𝑈 ← {𝑑 𝑗 ∈ 𝐷𝑠 : 𝑎 (𝑅, 𝑑 𝑗 ) = 1} ′ 5 while 𝑎 (𝑅 , 𝐷𝑠 ) < 𝑎 (𝑅, 𝐷𝑠 ) − 𝛼 do | {𝑑 𝑗 ∈ 𝑈 : 𝑎 (𝑟, 𝑑 𝑗 ) = 1} | 6 𝑟 ∗ ← arg max ′ cr (𝑟, 𝐷𝑠 ) 𝑟 ∈𝑅\𝑅 7 𝑅 ′ ← 𝑅 ′ ∪ {𝑟 ∗ }; 𝑈 ← 𝑈 \ {𝑑 𝑗 : 𝑎 (𝑟 ∗ , 𝑑 𝑗 ) = 1} 8 end ′ 9 return 𝑅

Scout then builds the subset greedily. The algorithm starts from an empty subset 𝑅 ′ and marks every answerable document, 𝑈 = {𝑑 𝑗 ∈ 𝐷𝑠 : 𝑎(𝑅, 𝑑 𝑗 ) = 1}, as not yet covered (Line 4). In each step, Scout picks the rule with the best cost-effectiveness: the number of still-uncovered documents, divided by its cost ratio cr (𝑟, 𝐷𝑠 ), so a rule that answers many new documents cheaply is picked (Line 6). Scout adds this rule 𝑟 ∗ to 𝑅 ′ and marks the documents it answers as covered (Line 7). The algorithm repeats until 𝑅 ′ ’s accuracy 𝑎(𝑅 ′, 𝐷𝑠 ) comes within 𝛼 of 𝑎(𝑅, 𝐷𝑠 ) (Line 5), then returns 𝑅 ′ . This greedy algorithm also alleviates overfitting as a side-effect. Our cost-effective rule notion (Line 6) divides the number of documents in 𝑈 on which a rule is correct by that rule’s cost ratio cr (𝑟, 𝐷𝑠 ). For two rules with the same cost ratio, Scout selects the one correct on more documents of 𝑈 , i.e., the rule with higher coverage 𝑎(𝑟, 𝑈 ) (Section 2.2). Such a rule is correct on many sampled documents because its answer pattern recurs across them, so it is more likely to be correct on the unsampled documents. Approximation guarantee. At 𝛼 = 0, Algorithm 1 is exactly the greedy algorithm for weighted Set Cover [47]: each answerable document is an element to cover, and each rule is a set weighted by its cost ratio cr (𝑟, 𝐷𝑠 ). We then present a provable guarantee below for this approximation algorithm.

𝑎(𝑅 ′, 𝐷𝑠 ) = 𝑎(𝑅, 𝐷𝑠 ) ⇐⇒ {𝐶𝑘 : 𝑟𝑘 ∈ 𝑅 ′ } covers 𝑈 . For the cost, the ballast document 𝐺𝑘 is private to rule 𝑟𝑘 , so the union shares no cost across rules: each rule in 𝑅 ′ contributes 1−1/𝑇 through its ballast document, while the element documents add Í between 0 and 𝑛/𝑇 in total. Hence 𝑑 ∈𝐷𝑠 cr (𝑅 ′, 𝑑) = |𝑅 ′ | + 𝛿 with 𝑚 𝑛 1 − 𝑇 ≤ 𝛿 ≤ 𝑇 , so |𝛿 | < 2 since 𝑇 > 2𝑚𝑛, and, since |𝐷𝑠 | = 𝑛 + 𝑚, cr (𝑅 ′, 𝐷𝑠 ) =

|𝑅 ′ | + 𝛿 , 𝑛 +𝑚

𝑘+ 1

so cr (𝑅 ′, 𝐷𝑠 ) ≤ 𝑛+𝑚2 ⇐⇒ |𝑅 ′ | ≤ 𝑘. 𝑘+ 1

Equivalence. Set the budget 𝐵 = 𝑛+𝑚2 . If C has a cover of size at most 𝑘, the corresponding rules form a subset 𝑅 ′ with 𝑎(𝑅 ′, 𝐷𝑠 ) = 𝑎(𝑅, 𝐷𝑠 ) and cr (𝑅 ′, 𝐷𝑠 ) ≤ 𝐵. Conversely, any 𝑅 ′ with 𝑎(𝑅 ′, 𝐷𝑠 ) = 𝑎(𝑅, 𝐷𝑠 ) and cr (𝑅 ′, 𝐷𝑠 ) ≤ 𝐵 yields a cover {𝐶𝑘 : 𝑟𝑘 ∈ 𝑅 ′ } of size |𝑅 ′ | ≤ 𝑘, since |𝛿 | < 12 and |𝑅 ′ | is integral. The reduction is polynomial, so the decision problem is NP-hard. Hardness carries over to Problem 1 itself: at 𝛼 = 0 the feasible subsets are exactly those of maximum accuracy, so a minimum-cost feasible subset cannot be dominated and is pareto-optimal; solving Problem 1 thus yields the minimum feasible cost, which decides the budget question. □

Theorem 4.3. Let 𝑛 = |{𝑑 𝑗 ∈ 𝐷𝑠 : 𝑎(𝑅, 𝑑 𝑗 ) = 1}| be the number Í of answerable documents in 𝐷𝑠 , and let 𝐻𝑛 = 𝑛𝑖=1 1𝑖 = 𝑂 (ln 𝑛). At ′ 𝛼 = 0, the subset 𝑅 returned by Algorithm 1 and the optimal 𝑅 ∗ of Problem 1 satisfy ∑︁ cr (𝑅 ′, 𝐷𝑠 ) ≤ 𝐻𝑛 cr (𝑟, 𝐷𝑠 ).

The decision problem lies in NP whenever 𝑎(𝑅 ′, 𝐷𝑠 ) and cr (𝑅 ′, 𝐷𝑠 ) are polynomial-time computable, in which case it is NP-complete.

4.2

𝑟 ∈𝑅 ∗

The theorem follows from Chvátal’s analysis [16] of the greedy algorithm for weighted Set Cover. If the sample size |𝐷𝑠 | = 20 (assuming every sampled document is answerable), then 𝐻𝑛 ≤ 3.6. Í Proof. The first inequality is cr (𝑅 ′, 𝐷𝑠 ) ≤ 𝑟 ∈𝑅 ′ cr (𝑟, 𝐷𝑠 ), since on every document the union of the spans of 𝑅 ′ has at most as many tokens as those spans counted one rule at a time. For the second, Algorithm 1 at 𝛼 = 0 is Chvátal’s greedy [16] on the weighted Set Cover instance whose universe is the 𝑛 answerable documents, with one set per rule 𝑟 holding the documents 𝑟 is correct on and weight cr (𝑟, 𝐷𝑠 ): Line 6 admits the rule of least weight per newly covered document, and the loop (Line 5) ends once every answerable document is answered, since at 𝛼 = 0 this is exactly when the target

Rule Refinement Algorithm

We now present Algorithm 1 to approximately solve Problem 1. Given the rules 𝑅 from rule generation, Scout first labels, for every sampled document, which rules lead to a correct answer, and computes each rule’s cost ratio (Line 2). Running the oracle (e.g., GPT-5.4) to estimate the accuracy for each rule would be expensive, so Scout uses a cheap proxy model (e.g., GPT-5.4-mini). The proxy is reliable because the text it reads per rule is small: even the union of all rules in 𝑅 has a cost ratio of only 0.07 to 0.39 (average 0.18) across the datasets (the Cost ratio column of Table 3), and any single rule is smaller still. On such short inputs, the proxy matches the oracle’s estimate of each rule’s accuracy at a fraction of the cost. 7

Algorithm 2: Farthest-point sampling r1

r2

r3

a) R = {r1, r2, r3}

r1

Input: collection D, vectors {𝑉𝑖 }, distance dis, stop ratio 𝜌 = 0.5 Output: sample 𝑆 1 𝑑 1 ← document farthest from the centroid of D 2 𝑆 ← {𝑑 1 }; 𝑔prev ← ∞ 3 while 𝑆 ≠ D do 4 𝑑 ∗ ← arg max min dis𝑖,𝑗

r2 ∪ r3 b) R = {r1, r2 ∪ r3}

Figure 7: Documents cluster by where their answers to 𝑄 reside,

𝑑𝑖 ∈D\𝑆 𝑑 𝑗 ∈𝑆

and each rule covers one cluster of similar documents. 5

𝑑 𝑗 ∈𝑆

𝑎(𝑅, 𝐷𝑠 ) is met. Chvátal’s theorem [16] bounds the total weight of the greedy’s cover by 𝐻𝑛 times that of any feasible cover. At 𝛼 = 0 the constraint of Problem 1 forces 𝑎(𝑅 ∗, 𝐷𝑠 ) = 𝑎(𝑅, 𝐷𝑠 ), so 𝑅 ∗ is correct on all 𝑛 answerable documents and is a feasible cover, Í Í giving 𝑟 ∈𝑅 ′ cr (𝑟, 𝐷𝑠 ) ≤ 𝐻𝑛 𝑟 ∈𝑅 ∗ cr (𝑟, 𝐷𝑠 ). □ For 𝛼 > 0, Algorithm 1 stops once it covers enough documents to stay within tolerance; this is greedy partial cover, and Slavík’s analysis [43] gives the analogous bound 𝐻𝑛′ , where 𝑛 ′ is the number of documents the subset must cover. Finally, the labels 𝑎(𝑟, 𝑑 𝑗 ) in Line 2 come from a cheap proxy model, so the guarantee holds with respect to these labels, which are reliable on the short spans that rules return, as discussed above.

5

6 7 8 9 10 11

if |𝑆 | ≥ 2 and 𝑔 < 𝜌 · 𝑔prev then break end 𝑆 ← 𝑆 ∪ {𝑑 ∗ }; 𝑔prev ← 𝑔 end return 𝑆

subset is too expensive. To this end, we approximate a document distance that is used for sampling without invoking the oracle. Approximate Document Distance. Our key insight is that a good distance metric should not measure how similar the contents of two documents 𝑑𝑖 and 𝑑 𝑗 are, but whether their answers to the query 𝑄 can be represented by using similar data patterns, e.g., in similar locations. Consider a document 𝑑𝑖 ∈ D and a query 𝑄. Scout splits 𝑑𝑖 into 𝑚 chunks and computes the embedding similarity 𝑠𝑘 between 𝑄 and each chunk 𝑘. It stores these values in a vector 𝑉𝑖 = [𝑠 1, . . . , 𝑠𝑚 ], ordered by the reading order of the chunks in 𝑑𝑖 . 𝑉𝑖 approximates how similarity to 𝑄 is distributed across chunks in 𝑑𝑖 . Given two documents 𝑑𝑖 and 𝑑 𝑗 , we define the distance between 𝑉 ·𝑉 their vectors 𝑉𝑖 and 𝑉𝑗 as the cosine distance dis𝑖,𝑗 = 1 − ∥𝑉𝑖 𝑖∥ ∥𝑉𝑗 𝑗 ∥ . Vector 𝑉𝑖 approximates the likelihood that document subsets (represented by chunks) contain the answer to 𝑄 and the relative locations of the answers. Cosine distance dis𝑖,𝑗 measures how similar the relative locations of answers to 𝑄 are in documents 𝑑𝑖 and 𝑑 𝑗 . A small dis𝑖,𝑗 indicates that 𝑑𝑖 and 𝑑 𝑗 place their answers in similar relative positions, so a single rule that encodes a recurring data pattern (e.g., a section or a page) is likely to cover both. The number of chunks 𝑚 controls the granularity of the similarity curve: a larger 𝑚 gives a finer-grained curve. We empirically set 𝑚 = 50, which yields a reliable estimate. While this distance metric is not exact, we show that it is effective. When two documents in the same true cluster have a large dis𝑖,𝑗 and thus are split apart, we usually end up picking too many documents rather than too few, which is permissible as we don’t leave a cluster unrepresented. Farthest-point Sampling. We now present Algorithm 2 to select a sample. Scout seeds the sample 𝑆 with the document farthest from the centroid of the collection D under dis (Line 1). Scout then repeatedly takes the candidate whose distance to 𝑆 is the largest, where a document’s distance to 𝑆 is its smallest distance to any document in 𝑆, and stores that distance as the gap 𝑔 = max𝑑𝑖 ∈ D\𝑆 min𝑑 𝑗 ∈𝑆 dis𝑖,𝑗 (Lines 4–5). Scout admits the candidate unless 𝑔 drops below 𝜌 times the previous gap, in which case it stops (Lines 7–9). 𝑔 is non-increasing by construction, since adding a document to 𝑆 can only reduce the distance of every remaining document to 𝑆. While some cluster has no document in 𝑆, 𝑔 is at least the smallest distance between two documents in different clusters; once every

Robustness of Scout

So far, rule refinement returns a rule set that is accurate and costefficient on the sample 𝐷𝑠 . Multiple challenges remain, however, before these rules can be applied on unsampled documents. One is that the rules learned on the sample may overfit, performing well on the sample but poorly on unseen documents. To reduce overfitting, we further introduce two strategies: (1) a sampling strategy that ensures that 𝐷𝑠 covers as many data patterns to locate answers as possible so that the learned rules are correct on D \ 𝐷𝑠 (Section 5.1), and (2) a rule application strategy that falls back to the rule set returned by the agent when the refined rules don’t contain the correct answer (Section 5.2). We first define document similarity by defining the concept of document clusters below, followed by presenting the above strategies. Document similarity. Given a query 𝑄 and a set of documents D, a document subset 𝐶 𝑗 ⊆ D is called a cluster if there exists a rule 𝑟𝑖 that, when applied to 𝐶 𝑗 , incurs a small cost, i.e., 𝑐𝑟 (𝑟𝑖 , 𝐶 𝑗 ) < 𝛿 (𝛿 is a small constant fraction, say 0.1), and is correct on every document in 𝐶 𝑗 , i.e., 𝑎(𝑟𝑖 , 𝐶 𝑗 ) = 1. Such a rule 𝑟𝑖 on 𝐶 𝑗 implies that documents in 𝐶 𝑗 are similar since there exists a data pattern encoded by the rule 𝑟𝑖 (e.g., to return the span of a table whose caption matches a keyword) that can be used to extract data correctly with low cost from 𝐶 𝑗 . In this case, we also say 𝑟𝑖 covers the cluster 𝐶 𝑗 . Consider the example in Figure 7(a), where D, represented by colored shapes, is split into three clusters, each covered by one of the rules 𝑟 1 , 𝑟 2 , and 𝑟 3 , while the right cluster in Figure 7(b) is covered by 𝑟 2 ∪ 𝑟 3 (returning the union of the spans of 𝑟 2 and 𝑟 3 ), where neither 𝑟 2 nor 𝑟 3 can cover this cluster individually.

5.1

𝑔 ← min dis𝑑 ∗ ,𝑗

Sampling

Ideally, an effective sample draws documents from every cluster of D, so that Scout sees all possible data patterns to locate answers and learns rules that are less likely to overfit. Generating such a sample is non-trivial, as we do not have rules before sampling, and using the oracle to verify whether a rule is correct on a document 8

cluster has a document in 𝑆, the next candidate is in a cluster that has already been sampled. Hence 𝑔 is at most the largest distance between two documents in the same cluster. We now analyze the returned sample 𝑆. Let 𝑔∗ be the value of the gap 𝑔 when Algorithm 2 stops at Line 7. Let D partition into clusters {𝐶 1, . . . , 𝐶𝑘 } with 𝑘 ≥ 2, and measure all distances using dis. The separation of a document subset 𝑈 ⊆ D is the smallest distance between a document in 𝑈 and a document outside 𝑈 ; for a cluster 𝐶 𝑗 , let 𝛿 𝑗 = min𝑑𝑎 ∈𝐶 𝑗 , 𝑑𝑏 ∉𝐶 𝑗 dis𝑎,𝑏 be its separation.

document to 𝑆, and the document attaining the previous maximum is no longer a candidate, so the next maximum does not grow. Step 2: diversity. Consider two picks 𝑝𝑎 , 𝑝𝑏 with 𝑎 < 𝑏. When 𝑝𝑏 was admitted, 𝑝𝑎 was already in 𝑆, so dis𝑝𝑎 ,𝑝𝑏 ≥ 𝑔𝑏 ≥ 𝑔𝑇 > 2 𝑔∗ , where the last inequality is the condition in Line 7. Step 3: coverage. By Lines 4–5, 𝑔∗ is the largest distance from a document outside 𝑆 to the closest document in 𝑆, so every document outside 𝑆 is within 𝑔∗ of some document in 𝑆. Now suppose a union 𝑈 of clusters with separation greater than 𝑔∗ had no document in 𝑆; then every document in 𝑈 would be at distance greater than 𝑔∗ from every document in 𝑆, all of which lie outside 𝑈 , contradicting Step 3. Theorem 5.1 is the case where 𝑈 is a single cluster, and Theorem 5.2 the case where 𝑈 is the union of two. The two properties mirror Gonzalez’s analysis of farthest-point traversal for 𝑘-center [21], where the selected points form both a packing and a cover; the condition in Line 7 certifies the factor of two between the two radii. At most one document per cluster. Suppose the clusters are wellseparated. First, while some cluster has no document in 𝑆, every pick lands in such a cluster: each document of a cluster that already has a document in 𝑆 is within 𝛿 intra of that document, while every document of a cluster with none is at distance at least 𝛿 inter > 𝛿 intra from every document in 𝑆, so farthest-point selection (Line 4) prefers the latter. Second, once every cluster has a document in 𝑆, the next candidate is within 𝛿 intra of its cluster’s document in 𝑆, while 𝑔prev is at least 𝛿 inter , since the last admitted document was picked while its cluster had no document in 𝑆; well-separation gives 𝛿 intra < 0.5 𝛿 inter ≤ 0.5 𝑔prev , so the condition in Line 7 holds and Algorithm 2 stops. The sample therefore never contains two documents from the same cluster. Remark (uneven separations). A cluster whose separation is at most 𝑔∗ can be missed, e.g., when one cluster sits far from the rest and another lies close to a sampled one; this is the identifiability limit of distance-based clustering. Enriching the distance features (stronger embeddings or finer chunking) widens the separations and mitigates it. Finally, for 𝑘 = 1 the condition in Line 7 requires |𝑆 | ≥ 2, so Scout draws one extra document, a harmless oversample.

Theorem 5.1 (Cluster coverage). The sample returned by Algorithm 2 contains at least one document from every cluster whose separation is greater than 𝑔∗ . Every document outside 𝑆 is within 𝑔∗ of some document in 𝑆 by definition, and every two documents in 𝑆 are at distance greater than 2 𝑔∗ , since gaps never increase and 𝑔∗ < 0.5 𝑔prev . If a cluster with separation exceeding 𝑔∗ had no document in 𝑆, all its documents would be farther than 𝑔∗ from 𝑆. The same argument applies to the union of two clusters, which yields a stronger guarantee. Theorem 5.2 (Group coverage). For two clusters 𝐶𝑖 and 𝐶 𝑗 , if the separation of 𝐶𝑖 ∪ 𝐶 𝑗 is greater than 𝑔∗ , then the sample returned by Algorithm 2 contains at least one document from 𝐶𝑖 or from 𝐶 𝑗 . Theorem 5.1 does not hold when a cluster, say 𝐶𝑖 , has separation at most 𝑔∗ . In this case, let 𝐶 𝑗 be the cluster that is close to 𝐶𝑖 , i.e., min𝑑𝑎 ∈𝐶𝑖 , 𝑑𝑏 ∈𝐶 𝑗 dis𝑎,𝑏 ≤ 𝑔∗ . By Theorem 5.2, if 𝐶𝑖 ∪ 𝐶 𝑗 is far from the rest, i.e., the separation of 𝐶𝑖 ∪𝐶 𝑗 is greater than 𝑔∗ , then 𝐶𝑖 and 𝐶 𝑗 cannot both be missed. This indicates that when Theorem 5.1 does not hold, at least one document in 𝐶 𝑗 that is similar to those in 𝐶𝑖 will be sampled, so that documents far from all others are not left unrepresented, ensuring a representative sample. One condition on the clusters complements Theorem 5.1 (proof below). Let 𝛿 intra be the largest distance between two documents in the same cluster, i.e., 𝛿 intra = max1≤ 𝑗 ≤𝑘 max𝑑𝑎 ,𝑑𝑏 ∈𝐶 𝑗 dis𝑎,𝑏 , and let 𝛿 inter = min1≤ 𝑗 ≤𝑘 𝛿 𝑗 be the smallest separation; the clusters are wellseparated if 𝛿 inter > 2 𝛿 intra . For well-separated clusters, the sample contains at most one document from each cluster; together with Theorem 5.1, the sample then contains exactly one document from each cluster whose separation exceeds 𝑔∗ . Theorem 5.1 does not bound the sample size: Algorithm 2 may admit several documents from the same cluster. This is permissible since it does not leave any cluster unrepresented. We therefore cap the sample size at min(|𝑆 |, 0.1 |D |), where |𝑆 | is the sample size Algorithm 2 returns. The cap keeps the cost of rule generation low and is empirically effective, as observed in Section 6. We now prove Theorems 5.1 and 5.2. We work in the defined distance space, where each document 𝑑𝑖 is the point 𝑉𝑖 and distances are the cosine distance dis𝑖,𝑗 . Write 𝑝 1, . . . , 𝑝𝑇 for the documents Algorithm 2 admits, in order (𝑝 1 the seed), and 𝑔𝑡 (2 ≤ 𝑡 ≤ 𝑇 ) for the gap of 𝑝𝑡 at its admission (Line 5); when Algorithm 2 stops at Line 7, the condition there gives 𝑔∗ < 0.5 𝑔𝑇 ; if the condition never holds, the loop ends with 𝑆 = D and both theorems hold trivially. The argument never invokes the triangle inequality, which the cosine distance does not satisfy. Step 1: gaps are non-increasing, 𝑔2 ≥ 𝑔3 ≥ · · · ≥ 𝑔𝑇 ≥ 𝑔∗ . Admitting a document can only reduce the distance of every remaining

5.2

Rule Application Strategy

While Scout generates a sample to reduce overfitting, the selected rules may still fail on unsampled documents. We now present a rule application strategy to further improve Scout’s robustness. It uses a cheap proxy to detect when a refined rule is unlikely to reproduce the oracle answer, and then falls back to the rule set returned by the agent during rule generation. It also picks a subset of the refined rules to further reduce cost. Recall that rule generation produces a rule set 𝑅, and rule refinement (Algorithm 1) selects a subset 𝑅 ′ ⊆ 𝑅, where 𝑅 ′ = {𝑟 1, . . . , 𝑟𝑘 }. Algorithm 1 adds these rules to 𝑅 ′ one at a time, each time choosing the rule of highest cost-effectiveness: the number of sampled documents it is correct on that no rule already in 𝑅 ′ is correct on, divided by its cost ratio cr (𝑟, 𝐷𝑠 ) (Line 6). We thus treat 𝑅 ′ as the ordered list [𝑟 1, . . . , 𝑟𝑘 ] in that order. We now present a cascade rule application with a fallback. Given an unsampled document 𝑑𝑖 , Scout scans 𝑅 ′ in the increasing order of the index. After scanning the first 𝑗 rules, it applies 9

Dataset Scout-Proxy-Verification-Prompt: You are given a question [Question] and a span of text [Text] retrieved from a document. Decide whether [Text] contains enough information to answer [Question]. Output: Return true if the text is sufficient to answer the question, and false otherwise.

Court FinanceBench NoPV OfficeQA Product Tropic

Figure 8: The proxy-verification prompt. [Question] and [Text] are placeholders for the task 𝑄 and the union of retrieved spans.

Ð𝑗 𝑙 them to 𝑑𝑖 and forms the union of their returned spans, 𝑈 𝑗 = 𝑙=1 𝑑𝑖 . It then asks a cheap proxy 𝑃 (e.g., GPT-5.4 mini) whether 𝑈 𝑗 can answer 𝑄, using the prompt in Figure 8. If 𝑃 returns true, Scout stops and calls the oracle 𝑂 on 𝑈 𝑗 to produce the answer 𝐴𝑖 ; otherwise it adds the next rule and repeats. If no prefix passes the proxy after all 𝑘 rules have been tried, Scout falls back to the rule set 𝑅 Ð and runs the oracle on the union 𝑟𝑙 ∈𝑅 𝑑𝑖𝑙 of all its spans. Falling back to 𝑅 is reasonable because 𝑅 is accurate (matching the accuracy of the golden baseline in Table 3) at a modest cost (a cost ratio of 0.07 to 0.39). Using a cheap model as the proxy 𝑃 is effective. First, the proxy is far cheaper than the oracle, so verifying at each step adds little cost. Second, the task is simple: the refined rules in 𝑅 ′ are cost-effective, so the span they return is short, and deciding whether a short, focused span answers 𝑄 is far simpler than answering 𝑄 itself.

6

Avg tokens

# Queries

294 100 242 200 200 200

11,760 60,539 3,293 110,604 34,970 9,789

13 12 12 16 13 14

Table 4: Datasets used in the experiments. # Docs is the number of documents, Avg tokens the average number of tokens per document, and # Queries the number of extraction queries per dataset.

vanilla LLM call, both powered by top-of-the-line LLM Claude Opus 4.7, given the complete document as input. We manually verify the answers on which the two labelers disagree.

6.1.2 Baselines and Ablations. We evaluate Scout against two groups of methods: baselines and ablations that replace Scout’s components with an agent. Baselines. For document extraction, agentic question answering is the state of the art, outperforming retrieval-augmented (RAG) and long-context baselines by up to 16 points on long-document QA benchmarks [20, 28, 44, 51]. We instantiate the agent as Codex [37], powered by GPT-5.4, and give it all the tools Codex provides. A few tools retrieve spans by keyword and regex matching or by embedding similarity, and reason over them. The agent then answers a query iteratively: at each step it issues a tool call, observes the result, and chooses the next call, until it has gathered enough evidence to answer. Note that RAG can be viewed as a special case of the agent, retrieving once based on embedding and then answering. Using this step, we adopt varied agent-based methods as our baselines. The per-document agent runs this agent on one query and one full document at a time, while the batched agent instead presents one query together with all documents at once and lets the agent answer the query per document. Finally, Evaporate [8] uses an LLM to synthesize Python programs for data extraction directly, invoking no LLM within the programs; we consider two variants: Evaporate-Code synthesizes a single program based on sampled documents, while Evaporate-Code+ synthesizes many and ensembles their extractions with weak supervision. Ablations. Scout runs a four-step pipeline: sampling, rule generation, rule refinement, and rule application. To isolate the contribution of each of Scout’s components, we compare it against ablations that hand some steps to an agent while keeping the rest of the pipeline fixed (Table 5). Rule application is always performed by Scout, and each ablation delegates a different part of the pipeline to the agent. Scout-AgentRef delegates rule refinement to the agent, under the same accuracy and cost objective as Problem 1 (i.e., to minimize the cost of rules while enforcing that their accuracy matches that of the rule set returned by Scout). Scout-AgentGen delegates both rule generation and refinement: the agent instead learns rules directly from the sampled documents, under that same objective. Scout-AgentE2E delegates the entire offline pipeline (steps 1 to 3), where the agent learns the rules end-to-end from all the data and effectively samples on its own. Comparing these variants reveals whether Scout’s specialized components outperform a general

Experiments

We evaluate Scout on six real-world datasets, describing the setup in Section 6.1 and presenting the results in Section 6.2.

6.1

# Docs

Experimental Setup

6.1.1 Datasets. We evaluate Scout on six datasets from distinct real-world domains (Table 4): Court [1] (U.S. federal appeal opinions), FinanceBench [23] (SEC 10-K/10-Q filings), NoPV [3] (PHMSA notices of probable violation), OfficeQA [38] (U.S. Treasury Bulletins), Product [2] (EMA drug product information), and Tropic [4] (NHC tropical cyclone reports). Queries target each domain’s structured values, such as case metadata and dispositions, financial figures, cited CFR sections, fiscal indicators, drug attributes, and storm intensity and casualties. The datasets vary widely in scale: documents average from roughly 3,300 to 110,000 tokens, and we include 12 to 16 queries per collection. Although each collection is relatively small, Scout already yields substantial savings as shown later. Its cost savings grow with collection size, and we further extrapolate its cost to 1,000-document collections (Section 6.2). The query workload spans five types: single-hop lookup (e.g., one stated value), multi-hop lookup (e.g., several named facts), enumeration (e.g., all members of a set), aggregation (e.g., a set reduced to a scalar), and classification (e.g., a label from a closed set). Single-hop lookups form 35% (Court) to 76% (Product) of the queries, 56% on average; the other types often require reasoning over multiple spans across the document. Here, we consider a single query over a collection, while jointly handling multiple queries is left to future work, where semantically related queries may share rules and open further optimization opportunities. For FinanceBench and OfficeQA, we use the ground truth from existing benchmarks [23, 38]. For the remaining datasets, we label the answers with two independent LLM labelers, an agent and a 10

Figure 9: Accuracy versus amortized cost ratio across the six datasets. Up and to the left is better (higher accuracy, lower cost). agent performing the same steps. For the agents used in these ablations, we provide tools that compute the accuracy and cost of any rule set, as defined in Section 2.2, to let the agent evaluate a rule set. We describe each ablation and give its prompt below. Each replaces one or more of Scout’s engineered stages with a generalpurpose coding agent (Codex, backed by GPT-5.4) that is given the repository tools and left to solve the same sub-problem on its own. All three are handed the same accuracy and cost-ratio definitions as Scout (Section 2.2), exposed as callable tools; in the prompts below these tool interfaces appear as placeholders (e.g., [Accuracy specification], [Cost ratio specification]). Scout-AgentGen delegates both rule generation and refinement. The agent is prompted as a document rule engineer and given the task [Question], the enriched sampled documents [Documents], and their oracle answers [Answers]; it uses the repository tools to load documents, measure accuracy and cost, and iterate toward a small, cost-optimized rule set, where [Accuracy specification] and [Cost ratio specification] are the metric tools of Section 2.2.

(target below 0.1), tightening high-cost rules once accuracy is met, with accuracy always winning. Metrics (tools): [Accuracy specification] and [Cost ratio specification], where accuracy runs the oracle on the union of the returned spans and checks it against the answer, and cost ratio is the fraction of the document’s tokens retrieved. A fast substring proxy may be used to iterate cheaply before the final oracle check. Workflow: study where the answer sits in each sampled document; write the broadest rule first and test its coverage and cost; diagnose uncovered documents and add a targeted rule only when it covers at least two of them; verify merge accuracy with the oracle and repeat until the target is met; finally tighten any high-cost rule without losing accuracy. Requirements: each rule is self-contained (imports inside the body), must never raise, and returns an empty list when nothing matches; prefer a few extra spans over missing the answer. Locate the answer using physical location (page), semantic location (section header or path), keyword proximity, table cells, typography, structural position, and any other recurring pattern.

Scout-AgentRef delegates rule refinement. The agent is given the task [Question] and the pre-generated rule pool [Rules], and selects a small subset with the repository tools; [Budget] bounds the paid verify_accuracy calls, and [Accuracy specification], [Cost ratio specification], and [Coverage specification] are the metric tool interfaces of Section 2.2.

Scout-AgentGen-Prompt: You are a document rule engineer working in the project repository. Given a question [Question], the enriched sampled documents [Documents], and their oracle answers [Answers], generate and refine a small set of Python span-retrieval rules def rule_name(doc) that return the answer-bearing spans of any unseen document from the same collection. Use every tool available (read and write files, execute Python, run shell commands, and search) to load documents, measure cost and accuracy, and iterate; do not reason in isolation. Objectives (in priority order): (1) reach merge accuracy at least 0.95 on the sampled documents; (2) minimize the average cost ratio

Scout-AgentRef-Prompt: You are given a question [Question] and a pre-generated rule pool [Rules]. Select a small subset of rules that preserves the merge accuracy of the full pool on the sampled documents while keeping total cost low and per-rule coverage high. Invoke the repository tools below (one per call); you may write small helper scripts. 11

Strategy Scout Scout-AgentRef Scout-AgentGen Scout-AgentE2E

Sample Scout Scout Scout

Generate Refine Scout Scout Scout Agent Agent Agent

Apply Scout Scout Scout Scout

zero. By default we set 𝛼 = 0.05 (Problem 1), so the refined rules’ accuracy falls at most 5% below the full pool’s. Given 𝑄, when measuring accuracy, we measure whether the span 𝑑 𝑖𝑗 returned by a rule 𝑟𝑖 on a document 𝑑 𝑗 can reproduce the oracle answer (i.e., the ground truth), i.e., 𝑂 (𝑑 𝑖𝑗 , 𝑄) = 𝑂 (𝑑 𝑗 , 𝑄). Here, we use an LLM-as-a-judge [22, 52] to decide whether 𝑂 (𝑑 𝑖𝑗 , 𝑄) is equivalent to the ground truth, allowing small syntactic variations, and GPT-5.4 is used as the judge. In particular, let 𝐼 (𝑂 (𝑑 𝑖𝑗 , 𝑄), 𝑂 (𝑑 𝑗 , 𝑄)) be an indicator function that returns True if 𝑂 (𝑑 𝑖𝑗 , 𝑄) and 𝑂 (𝑑 𝑗 , 𝑄) are lexically identical or semantically equivalent. This approach effectively handles equivalent but non-identical responses.

Table 5: Scout and its agentic ablations Hard constraint: the merge accuracy of your subset must equal that of the full pool on every sampled document the full pool answers correctly. Soft targets (traded against each other): minimize the summed cost ratio of the subset; maximize the minimum per-rule coverage (broad rules generalize better); keep the subset small. Tools: list_rules (pool with one-line descriptions); compute_cost [Cost ratio specification]; compute_coverage [Coverage specification]; inspect_rule; and the paid verify_accuracy [Accuracy specification], limited to [Budget] calls. The free tools use no oracle; verify_accuracy runs the oracle on the sampled documents. Loop: snapshot the pool with cost and coverage; propose an initial subset by coverage-per-cost, preferring rules with broad descriptions over layout-specific ones; verify accuracy; for any missed document, inspect and add the most promising covering rule, then re-verify; once the hard constraint holds, drop-test the most expensive rule and remove it if accuracy is preserved; stop when the soft targets are reasonable or the budget is exhausted.

6.2

Experimental Results

Experiment 1: Scout vs. baselines. Figure 9 reports the accuracy (𝑦-axis) and the amortized cost ratio cost (𝑄) (𝑥-axis, log scale), one panel per dataset. A point in the top-left corner is ideal: high accuracy at low cost. Agent baselines. Scoutmatches the accuracy of the per-document agent, the strongest but most expensive baseline, while spending far less. Averaged over the six datasets, Scout reaches 0.9 accuracy against 0.89 for the per-document agent, leading on Court, NoPV, and Tropic, and trailing by at most 1.6 points elsewhere, yet its amortized cost is one to two orders of magnitude lower (22× to 552×). This is because the per-document agent reads each full document and issues many tool calls in multiple iterations, so its cost ratio exceeds 1, consuming more than the whole document, whereas Scout applies cost-effective rules and invokes the oracle only on a small span. The batched agent is cheaper but only 0.85 accurate on average, since packing all documents into one context dilutes the model’s attention, and it remains 3× to 88× more expensive than Scout. Code-rule baseline. Against Evaporate-Code+, the strongest version of Evaporate variant, Scout is 61 points more accurate (0.90 vs. 0.29) at a comparable amortized cost. This is because Evaporate instructs LLMs to generate programs that emit answers directly with no final oracle pass, so it succeeds only when the answer is a substring of the document; queries that otherwise require synthesizing from the context fail, dropping its accuracy below 0.3 on every dataset. Experiment 2: Scout vs. its ablations. We now ask whether each of Scout’s own components is necessary. Rule refinement. Scout-AgentRef differs from Scout only in refinement, so comparing the two isolates the contribution of Scout’s refinement algorithm. At a comparable cost ratio, Scout is more accurate on all six datasets (Figure 9), by 5 points on average. When Scout-AgentRef reaches a slightly lower cost ratio, it pays with a large accuracy drop, as on Tropic, while on Court Scout is both more accurate and cheaper. The reason is that rule refinement is NP-hard (Theorem 4.2): the agent searches a large space of rule subsets heuristically without guarantees, whereas Scout solves it with a greedy algorithm that is provably near-optimal. Rule generation. Scout is more accurate and cheaper than Scout-AgentGen. On average Scout is 6 points more accurate, and the gap widens to 14 points on the most heterogeneous dataset, Tropic. This is because Scout generates a large rule set that prioritizes accuracy over cost in the rule generation step, and then

Scout-AgentE2E delegates the entire offline pipeline (sampling, generation, and refinement) over the raw corpus. The agent is given the task [Question] and the plain-text corpus [Documents], and samples, generates, and refines rules end to end; [Budget] bounds the paid verify-accuracy calls, and [Accuracy specification] and [Cost ratio specification] are the metric tool interfaces of Section 2.2. Scout-AgentE2E-Prompt: You are given a question [Question] and a corpus of plain-text documents [Documents]. Working end to end, sample documents, generate Python retrieval rules def rule_name(doc), and refine them into a small rule set that answers the question at low cost. Use the repository tools below and keep all writes inside the rules directory. Tools: list-docs and read-doc (inspect a seed sample); compute-cost [Cost ratio specification]; inspect-rule; and the paid verify-accuracy [Accuracy specification], limited to [Budget] calls. Documents are plain text, exposed as pages, paragraphs, and lines. Rule contract: one file per rule, each defining a single def rule_name(doc) that returns a list of span dicts (each with a text field) and wraps its body in try/except returning an empty list. Workflow: inspect a small seed sample; write one to three broad rules; measure cost and verify accuracy on the working sample; expand the sample only to diagnose failures; stop when the rules are stable or further tightening hurts coverage.

6.1.3 Metrics. We report three metrics per dataset: accuracy, endto-end latency, and cost of each strategy. For an extraction query 𝑄 over a document collection D, we measure each metric per document and average it over the documents, then over all extraction queries. Some strategies run in two stages: an offline stage that learns the rules, with optional sampling and rule refinement (as in Scout and its ablations), and an online stage that applies them. Let cost off (𝑄) and cost on (𝑄, 𝑑 𝑗 ) be the offline cost for 𝑄 and the cost of applying the rules to document 𝑑 𝑗 . The reported average cost amortizes the one-time offline cost across all 𝑛 = |D| docuÍ cost off (𝑄 ) ments: cost (𝑄) = 𝑛1 𝑑 𝑗 ∈ D cost on (𝑄, 𝑑 𝑗 ) + . The average 𝑛 latency lat (𝑄) is defined analogously, with lat off and lat on in place of the costs. Baselines have no offline stage, so their second term is 12

Figure 10: Total cost as the document collection grows. Only strategies within 5% of the per-document agent’s accuracy are shown. reduces cost while preserving accuracy through rule refinement. When the refined rules don’t contain the answers, Scout falls back to the initial rule set, and thus generalizes well to unseen documents. In contrast, Scout-AgentGen directly instructs an agent to generate an optimized rule set with high accuracy and low cost based on the samples, which may overfit. In terms of the cost of rule generation, Scout is cheaper because its agent generates this rule set in a few iterations, whereas Scout-AgentGen solves a harder optimization problem, maximizing accuracy while constraining the cost of the generated rules, and thus incurs significantly more iterations, increasing the cost of both program synthesis and verification. Even so, the rules returned by Scout are more effective: at matched accuracy (e.g., 0.925 on Court), Scout’s cost ratio is about an order of magnitude lower. Sampling. Scout-AgentE2E delegates sampling, generation, and refinement, and is the weakest variant: it is both less accurate and more expensive than Scout on all six datasets, e.g., on Court it scores 0.81 at cost ratio 0.31 against 0.93 at 0.015 for Scout, because a general agent fails to sample representatively. Its consistent shortfall confirms that Scout’s offline components, and its representative sampling in particular, are effective. Experiment 3: Scalability. Figure 10 reports the total cost in dollars (log-scale 𝑦-axis) of answering a query as the document collection grows, from the measured collection size up to 1,000 documents (solid lines measured, dotted lines extrapolated), for Scout, its ablations, and the baselines. To make the cost comparison fair, we include only strategies within 5% of the strategy with the best accuracy, i.e., the per-document agent. As the collection

grows, Scout’s total cost stays nearly flat while the baselines grow linearly. Cost at scale. At 1,000 documents, Scout answers the query for a few dollars on every dataset ($0.20 to $3.43), whereas the perdocument agent costs hundreds to thousands of dollars ($206 to $2,338), making Scout 61× to over 1000× cheaper at that scale, e.g., $0.20 vs. $206 on Court and $2.66 vs. $2,338 on OfficeQA. The batched agent is cheaper than the per-document agent but its cost still grows linearly, reaching $11 to $57 at 1,000 documents, one to two orders of magnitude above Scout. This is because Scout spends only a one-time offline cost and then a tiny online cost per document, thanks to the small spans returned by the rules. The agent baselines instead read each full document (possibly in multiple passes), so their total cost rises linearly and quickly dominates Scout’s fixed offline cost. Moreover, among the strategies that are cheap at scale, Scout is also the most accurate: on Tropic, Scout and Scout-AgentRef both cost only a few dollars at 1,000 documents ($3.43 and $1.16), yet Scout is 6 points more accurate. Cost breakdown of Scout. Scout’s cost splits into a fixed onetime offline cost to learn the rules and a small per-document online cost to apply them. Applying the rules to one document is cheap, only about $0.0016 on average. At the measured collection sizes the offline cost is 53% to 83% of the total, but since it is fixed, its fraction shrinks as the collection grows: at 1,000 documents it falls to 18% to 37%, and the online cost dominates. Experiment 4: Overfitting analysis. Scout learns rules from a small sample, so we test whether they overfit it. Table 6 reports the accuracy of Scout and its ablations on the sampled (sAcc) and held-out (uAcc) documents, and their gap 𝛿 = sAcc − uAcc. A larger 13

Court

FinanceBench

NoPV

OfficeQA

Product

Tropic

Strategy

sAcc

uAcc

𝛿

sAcc

uAcc

𝛿

sAcc

uAcc

𝛿

sAcc

uAcc

𝛿

sAcc

uAcc

𝛿

sAcc

uAcc

𝛿

Scout

0.965

0.922

+0.043

0.960

0.959

+0.001

0.939

0.928

+0.011

0.880

0.826

+0.054

0.877

0.886

−0.009 0.877

0.873

+0.004

Scout-AgentRef

0.973

0.904

+0.069

0.950

0.904

+0.046

0.942

0.845

+0.097

0.840

0.746

+0.094

0.892

0.836

+0.057 0.907

0.801

+0.106

Scout-AgentGen

0.965

0.922

+0.044

0.960

0.903

+0.057

0.942

0.845

+0.097

0.830

0.773

+0.057

0.881

0.840

+0.041 0.761

0.725

+0.035

Table 6: Overfitting of the Scout-family strategies. All values are averaged over each dataset’s queries.

Dataset

Court FinanceBench NoPV Product Tropic

Embed (s/doc)

Sampling (s)

Rule gen. (s)

Refine (s)

Offline (s/query)

Online (s/doc)

0.29 0.35 0.22 0.39 0.26

85.3 35.0 53.2 78.0 52.0

40.5 35.9 49.9 38.1 52.8

188 219 192 134 244

313.8 289.9 295.1 250.1 348.8

3.78 2.19 2.13 2.12 2.30

Scout does not pose restrictions on such rigid document structure or markups and learns where answers recur automatically. Program-based extraction is another alternative. Evaporate [8] assumes each answer is a substring of the input and synthesizes a program to return them directly, and it fails when the answer must be inferred from context. Scout instead uses programs only to locate the answer for an LLM to read, with guarantees on the accuracy and cost of the programs it generates, and is over 61 points more accurate. Finally, the rest work on training an LLM for document extraction focuses on accuracy rather than cost, such as AWS Textract [6], Azure Document Intelligence [34], and vision LLMs such as GPT-4 Vision [36]. Applying such models on large document collections does not scale. In contrast, machine-learningbased extractors [5, 39, 41, 46, 49] either need human input (e.g., labels) or do not transfer across domains. Scout needs neither: given only a natural-language query, it discovers where answers recur automatically and returns a small document span to the LLM, extracting at scale with low cost. LLM-powered data systems. A growing line of systems use LLMs to answer semantic queries over unstructured data. LOTUS [40] adds LLM-defined semantic operators (e.g., filters, joins, aggregations) to the relational model. DocETL [42] rewrites documentprocessing pipelines with an agentic framework for higher accuracy; Palimpzest [32] compiles declarative AI analytics into plans trading off cost, runtime, and quality. QUEST [45] reduces extraction cost via index-based retrieval; AOP [48] optimizes operator pipelines online for multi-hop queries over data lakes; ThalamusDB [24] answers SQL with natural-language predicates over multi-modal data, such as image, audio, and text, via approximate query processing with error bounds. Despite their differences, these systems share one step: to evaluate a semantic operator, they call an LLM to synthesize the data it needs from the source, which amounts to extracting structured data on the fly. Scout is complementary, and can be viewed to be optimized physical operators for such systems, e.g., supporting a map operation over documents. Cost-optimized LLM-powered processing. Another line of work reduces the cost of LLM-powered data processing. Model cascades and routers send each input to the cheapest capable model: FrugalGPT [13] chains models and stops once an answer is confident; Hybrid LLM [19] routes each query to a small or large model by predicted difficulty; and RouteLLM [35] learns such routers from preference data. BARGAIN [50] instead runs cheap models with adaptive sampling and statistical estimation to cut cost while bounding the accuracy loss relative to an oracle. A related line answers AI queries (e.g., a SQL query with AI predicates) with lightweight proxy models over embeddings [15], but targets classification tasks rather than data extraction. These techniques choose cheaper models when accuracy is not sacrificed, but still send the full input data

Table 7: Latency breakdown of Scout. Embed is the per-document embedding time within sampling. All times are in seconds.

positive 𝛿 means worse generalization. We omit Scout-AgentE2E, which samples, generates, and refines rules in a single agent call: it does not expose which documents it sampled, and forcing it to do so explicitly in the prompt might change the method. Scout overfits the least: its average gap is 0.017, against 0.055 for Scout-AgentGen and 0.078 for Scout-AgentRef, the smallest on every dataset, while its ablations have gaps up to 0.097 and 0.106. Scout-AgentGen tends to overfit as it instructs agents to generate optimized rules (with high accuracy and low cost) based on the sample, whereas Scout generates a large pool of rules prioritizing accuracy, which is used as the fallback when the refined rules don’t contain answers. Rules returned by Scout additionally prioritize high coverage in the rule refinement, which alleviates overfitting. Experiment 5: Latency breakdown of Scout. Table 7 reports the latency breakdown of Scout. The three offline steps (sampling, rule generation, and refinement) run once per query, and Offline is their sum. Online is the time to apply the rules to a single document. Scout’s offline latency is a few hundred seconds per query. This time is spent only once and reused across the collection. The online latency is about 2 to 4 seconds per document. This is several times faster than the per-document agent, which takes 8 to 19 seconds per document. Embedding the documents during sampling is the other one-time cost: at 0.2 to 0.4 seconds per document, it adds up to 35 to 85 seconds.

7

Related Work

We review work relevant to Scout: document extraction, LLMpowered data systems, and cost-optimized LLM data processing. Document extraction. A rich line of work extracts structured values from documents; prior methods differ in what they assume or require. Many assume documents share a rigid structure: TWIX [29] recovers tables from a tabular template, ZenDB [30] and SHED [33] query documents that follow a hierarchical template, while Doctopus [12] extracts tables under a budget, and InstrucTE [10] maps heterogeneous tables into a target schema. Work on web extraction from a decade ago relies on the HTML markup of templategenerated pages [7, 11, 14, 17, 27]. Such approaches fail when documents do not have a consistent template or markup, whereas 14

to an LLM, and tend to escalate to the expensive oracle on long inputs where cheap models degrade. Scout reduces cost orthogonally: its rules exploit data similarity so that an LLM reads only a small, relevant span of each document.

8

Conclusion

We presented Scout, a scalable document-extraction system that generates effective rules to locate answers with accuracy and cost guarantees. Scout samples a few representative documents; an agent then generates a set of rules that together recover almost all answers, and Scout selects a subset that preserves this accuracy at a fraction of the cost, a selection problem we prove to be NP-hard and solve greedily within a logarithmic factor of optimal. To reduce overfitting of rules learned on the sample, Scout applies the refined rules to an unseen document one at a time, checks with a cheap model whether the retrieved text suffices, and falls back to the full rule set when it does not. On real-world datasets, Scout matches the accuracy of a frontier agent while being orders of magnitude cheaper, and far outperforms prior program-based systems.

15

References

[24] Saehan Jo and Immanuel Trummer. 2024. ThalamusDB: Approximate Query Processing on Multi-Modal Data. Proc. ACM Manag. Data 2, 3, Article 186 (2024). [25] Alistair E. W. Johnson, Lucas Bulgarelli, Lu Shen, Alvin Gayles, Ayad Shammout, Steven Horng, Tom J. Pollard, Sicheng Hao, Benjamin Moody, Brian Gow, Li wei H. Lehman, Leo A. Celi, and Roger G. Mark. 2023. MIMIC-IV, a freely accessible electronic health record dataset. Scientific Data 10, 1 (2023), 1. doi:10.1038/s41597022-01899-x [26] Richard M. Karp. 1972. Reducibility among Combinatorial Problems. In Complexity of Computer Computations. Plenum Press, New York, 85–103. [27] Mohammed Kayed and Chia-Hui Chang. 2010. FiVaTech: Page-Level Web Data Extraction from Template Pages. IEEE Transactions on Knowledge and Data Engineering 22, 2 (2010), 249–263. [28] Shilong Li, Yancheng He, Hangyu Guo, Xingyuan Bu, Ge Bai, Jie Liu, Jiaheng Liu, Xingwei Qu, Yangguang Li, Wanli Ouyang, et al. 2024. GraphReader: Building Graph-based Agent to Enhance Long-Context Abilities of Large Language Models. In Findings of the Association for Computational Linguistics: EMNLP 2024. 12758– 12786. [29] Yiming Lin, Mawil Hasan, Rohan Kosalge, Alvin Cheung, and Aditya G Parameswaran. 2025. Visual template inference for data extraction from documents. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–27. [30] Yiming Lin, Madelon Hulsebos, Ruiying Ma, Shreya Shankar, Sepanta Zeighami, Aditya G. Parameswaran, and Eugene Wu. 2025. Querying Templatized Document Collections with Large Language Models. In 41st IEEE International Conference on Data Engineering (ICDE). IEEE, 2422–2435. [31] Yiming Lin, Sepanta Zeighami, and Aditya G. Parameswaran. 2025. Bolt-on, Verifiable Provenance for LLM-Powered Data Processing. https://drive.google. com/file/d/16thcosiFUVvwiMr3pgzZRHNejOV52lNp/view. [32] Chunwei Liu, Matthew Russo, Michael J. Cafarella, Lei Cao, Peter Baile Chen, Zui Chen, Michael J. Franklin, Tim Kraska, Samuel Madden, Rana Shahout, and Gerardo Vitagliano. 2025. Palimpzest: Optimizing AI-Powered Analytics with Declarative Query Processing. In 15th Conference on Innovative Data Systems Research (CIDR). [33] Ruiying Ma, Yiming Lin, and Aditya G. Parameswaran. 2025. Robust Hierarchical Structures for Document Analytics. https://people.eecs.berkeley.edu/~adityagp/ papers/shed-tr.pdf. Technical report. [34] Microsoft. [n. d.]. Azure AI Document Intelligence. https://azure.microsoft.com/ en-us/products/ai-services/ai-document-intelligence. 2026. [35] Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, M Waleed Kadous, and Ion Stoica. 2025. RouteLLM: Learning to route LLMs from preference data. In The Thirteenth International Conference on Learning Representations. [36] OpenAI. [n. d.]. GPT-4 Vision (GPT-4V). https://developers.openai.com/api/docs/ guides/images-vision. 2026. [37] OpenAI. 2025. Codex. https://openai.com/codex/. [38] Krista Opsahl-Ong, Arnav Singhvi, Jasmine Collins, Ivan Zhou, Cindy Wang, Ashutosh Baheti, Owen Oertell, Jacob Portes, Sam Havens, Erich Elsen, et al. 2026. Officeqa pro: An enterprise benchmark for end-to-end grounded reasoning. arXiv preprint arXiv:2603.08655 (2026). [39] Suresh Parthasarathy, Lincy Pattanaik, Anirudh Khatry, Arun Iyer, Arjun Radhakrishna, Sriram K Rajamani, and Mohammad Raza. 2022. Landmarks and regions: a robust approach to data extraction. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 993–1009. [40] Liana Patel, Siddharth Jha, Melissa Pan, Harshit Gupta, Parth Asawa, Carlos Guestrin, and Matei Zaharia. 2025. Semantic operators and their optimization: Enabling llm-based data processing with accuracy guarantees in lotus. Proceedings of the VLDB Endowment 18, 11 (2025), 4171–4184. [41] Ritesh Sarkhel and Arnab Nandi. 2021. Improving Information Extraction from Visually Rich Documents using Visual Span Representations. Proceedings of the VLDB Endowment 14, 5 (2021), 822–834. [42] Shreya Shankar, Tristan Chambers, Tarak Shah, Aditya G. Parameswaran, and Eugene Wu. 2025. DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing. Proc. VLDB Endow. 18, 9 (2025), 3035–3048. [43] Petr Slavík. 1997. Improved Performance of the Greedy Algorithm for Partial Cover. Inform. Process. Lett. 64, 5 (1997), 251–254. [44] Li Sun, Liu He, Shuyue Jia, Yangfan He, and Chenyu You. 2025. Docagent: An agentic framework for multi-modal long-context document understanding. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 17712–17727. [45] Zhaoze Sun, Chengliang Chai, Qiyan Deng, Kaisen Jin, Xinyu Guo, Han Han, Ye Yuan, Guoren Wang, and Lei Cao. 2025. QUEST: Query Optimization in Unstructured Document Analysis. Proc. VLDB Endow. 18, 11 (2025), 4560–4573. [46] Sandeep Tata, Navneet Potti, James B. Wendt, Lauro Beltr ao Costa, Marc Najork, and Beliz Gunel. 2021. Glean: Structured Extractions from Templatic Documents. Proceedings of the VLDB Endowment 14, 6 (2021), 997–1005. [47] Vijay V. Vazirani. 2001. Approximation Algorithms. Springer, Berlin, Heidelberg. [48] Jiayi Wang and Guoliang Li. 2025. AOP: Automated and Interactive LLM Pipeline Orchestration for Answering Complex Queries. In 15th Conference on Innovative

[1] 2026. CourtListener: U.S. Federal Court Opinions. https://www.courtlistener.com. Free Law Project. 2026.. [2] 2026. Medicines: European Public Assessment Reports (EPAR). https://www. ema.europa.eu/en/medicines. European Medicines Agency. 2026.. [3] 2026. PHMSA Pipeline Safety Enforcement: Notices of Probable Violation. https: //primis.phmsa.dot.gov/comm/reports/enforce/. U.S. Pipeline and Hazardous Materials Safety Administration. 2026.. [4] 2026. Tropical Cyclone Reports. https://www.nhc.noaa.gov/data/tcr/. U.S. National Hurricane Center, NOAA. 2026.. [5] Milan Aggarwal, Hiresh Gupta, Mausoom Sarkar, and Balaji Krishnamurthy. 2020. Form2Seq: A Framework for Higher-Order Form Structure Extraction. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). 3830–3840. [6] Amazon Web Services. [n. d.]. Amazon Textract. https://aws.amazon.com/ textract/. 2026. [7] Arvind Arasu and Hector Garcia-Molina. 2003. Extracting Structured Data from Web Pages. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. ACM, 337–348. [8] Simran Arora, Brandon Yang, Sabri Eyuboglu, Avanika Narayan, Andrew Hojel, Immanuel Trummer, and Christopher Ré. 2023. Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakes. Proc. VLDB Endow. 17, 2 (2023), 92–105. [9] Christoph Auer, Maksym Lysak, Ahmed S. Nassar, Michele Dolfi, Nikolaos Livathinos, Panos Vagenas, Cesar Berrospi Ramis, Matteo Omenetti, Fabian Lindlbauer, Kasper Dinkla, Lokesh Mishra, Yusik Kim, Shubham Gupta, Rafael Teixeira de Lima, Valéry Weber, Lucas Morin, Ingmar Meijer, Viktor Kuropiatnyk, and Peter W. J. Staar. 2024. Docling Technical Report. arXiv preprint arXiv:2408.09869. arXiv:2408.09869 [cs.CL] [10] Fan Bai, Junmo Kang, Gabriel Stanovsky, Dayne Freitag, Mark Dredze, and Alan Ritter. 2024. Schema-Driven Information Extraction from Heterogeneous Tables. In Findings of the Association for Computational Linguistics: EMNLP. 10252–10273. [11] Robert Baumgartner, Sergio Flesca, and Georg Gottlob. 2001. Visual Web Information Extraction with Lixto. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 119–128. [12] Chengliang Chai, Jiajun Li, Yuhao Deng, Yuanhao Zhong, Ye Yuan, Guoren Wang, and Lei Cao. 2025. Doctopus: Budget-aware Structural Table Extraction from Unstructured Documents. Proc. VLDB Endow. 18, 11 (2025), 3695–3707. [13] Lingjiao Chen, Matei Zaharia, and James Zou. 2024. FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance. Trans. Mach. Learn. Res. (TMLR) (2024). [14] Zhijia Chen, Weiyi Meng, and Eduard C. Dragut. 2022. Web Record Extraction with Invariants. Proceedings of the VLDB Endowment 16, 4 (2022), 959–972. [15] Yeounoh Chung, Rushabh Desai, Jian He, Yu Xiao, Thibaud Hottelier, YvesLaurent Kom Samo, Pushkar Khadilkar, Xianshun Chen, Sam Idicula, Fatma Ozcan, et al. 2026. 100x Cost & Latency Reduction: Performance Analysis of AI Query Approximation using Lightweight Proxy Models:[Experiments & Analysis]. Proceedings of the ACM on Management of Data 4, 3 (SIGMOD (2026), 1–23. [16] V. Chvátal. 1979. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research 4, 3 (1979), 233–235. [17] Valter Crescenzi, Giansalvatore Mecca, and Paolo Merialdo. 2001. RoadRunner: Towards Automatic Data Extraction from Large Web Sites. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 109–118. [18] Pradeep Dasigi, Kyle Lo, Iz Beltagy, Arman Cohan, Noah A Smith, and Matt Gardner. 2021. A dataset of information-seeking questions and answers anchored in research papers. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 4599–4610. [19] Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Rühle, Laks V. S. Lakshmanan, and Ahmed Hassan Awadallah. 2024. Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing. In The Twelfth International Conference on Learning Representations (ICLR). [20] Mingxuan Du, Benfeng Xu, Chiwei Zhu, Shaohan Wang, Pengyu Wang, Xiaorui Wang, and Zhendong Mao. 2026. A-RAG: Scaling Agentic Retrieval-Augmented Generation via Hierarchical Retrieval Interfaces. arXiv preprint arXiv:2602.03442. arXiv:2602.03442 [cs.CL] [21] Teofilo F. Gonzalez. 1985. Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science 38 (1985), 293–306. [22] Jiawei Gu, Xuhui Jiang, Zhichao Shi, Hexiang Tan, Xuehao Zhai, Chengjin Xu, Wei Li, Yinghan Shen, Shengjie Ma, Honghao Liu, et al. 2026. A survey on llm-as-a-judge. The Innovation 7, 6 (2026). [23] Pranab Islam, Anand Kannappan, Douwe Kiela, Rebecca Qian, Nino Scherrer, and Bertie Vidgen. 2023. Financebench: A new benchmark for financial question answering. arXiv preprint arXiv:2311.11944 (2023).

16

[51] Jun Zhao, Can Zu, Xu Hao, Yi Lu, Wei He, Yiwen Ding, Tao Gui, Qi Zhang, and Xuan-Jing Huang. 2024. LONGAGENT: Achieving Question Answering for 128k-Token-Long Documents through Multi-Agent Collaboration. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 16310–16324. [52] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. 2023. Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena. Advances in Neural Information Processing Systems 36 (2023), 46595–46623.

Data Systems Research (CIDR). [49] Yiheng Xu, Minghao Li, Lei Cui, Shaohan Huang, Furu Wei, and Ming Zhou. 2020. LayoutLM: Pre-training of Text and Layout for Document Image Understanding. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). ACM, 1192–1200. [50] Sepanta Zeighami, Shreya Shankar, and Aditya Parameswaran. 2025. Cut costs, not accuracy: Llm-powered data processing with guarantees. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–26.

17

Related documents

• Extraction and Utilisation of Metadata from Non-machine-actionable Documents to Improve Data Curation and Discovery, 2024-2025#655206
• Bridging the Omics Divide: A Modular Relational Approach to Multi-Layer Biological Data Management#1169664
• Bridging the Omics Divide: A Modular Relational Approach to Multi-Layer Biological Data Management#1156754
• DeepFake Forensics AI: A Multi-Modal Detection and Blockchain-Anchored Evidence Management Platform#238524
• MARS - a Message Archiving and Retrieval Service#208899