{"id":"b02bc2df-9107-4c3b-8a64-cfe7a31fd354","arxiv_id":"2608.08261","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Scout generates and refines LLM-written span-locating rules to match full-document agent accuracy on document extraction at orders-of-magnitude lower cost.","lead":"Scout is a system that turns a large set of documents into a small set of reusable Python rules that tell an LLM where in each document to look for an answer, so the LLM reads only a tiny span instead of the whole file. On six real-world document collections it claims to match the accuracy of a frontier LLM agent that reads everything, while costing 61x to over 1000x less at 1000 documents.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3's logarithmic guarantee is against the sum of per-rule costs, not the union-cost objective of Problem 1; the claimed 'provable approximation guarantee' for the stated problem is not established.","rationale":"Read in good faith, the empirical central claim—Scout matching a full-document agent's accuracy at one to three orders of magnitude lower cost—is supported by the protocol and tables; the measured comparisons do not obviously depend on the disputed theorem. The stress-test concern is therefore aimed at the theoretical contribution that the paper leans on: rule refinement is introduced as NP-hard with a provably near-optimal greedy, and the proof's objective does not match Problem 1. The reader identified monotonicity as the weakest assumption; that is a real limitation, but it is hedged by the 94% empirical citation and the graceful-degradation argument. The theorem-objective mismatch is sharper, because it affects the stated formal guarantee rather than an empirical assumption. Since the reader's CONDITIONAL verdict already accounts for this problem and the fix is a corrected theorem statement rather than new experiments, I recommend leaving the verdict at CONDITIONAL (i.e., UNCHANGED). No evidence here supports rejection of the practical claim.","tokens_in":26927,"tokens_out":19486,"duration_ms":205608,"concrete_test":"Analytic re-derivation: take the proof of Theorem 4.3 and replace the right-hand side Σ_{r∈R*} cr(r,D_s) by cr(R*,D_s) wherever the paper claims an approximation to Problem 1. Verify whether any step in the proof establishes cr(R',D_s) ≤ H_n·cr(R*,D_s). A minimal witness for the gap is a two-document sample with R* = {r1,r2}, where r1 is needed only on d1, r2 only on d2, and both rules return a common large span on both documents; for this instance Σ_{r∈R*} cr(r,D_s) = 2·cr(R*,D_s), so the theorem's bound is not a bound on the Problem 1 ratio. If the proof cannot be repaired with marginal union costs, revise the theorem to state the surrogate-sum guarantee and mark the approximation factor for Problem 1 as open.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Problem 1 defines the objective cr(R', D_s) as the average over documents of the token fraction in the union of the selected rules' spans. Algorithm 1 instead treats every rule r as a set with weight cr(r, D_s), its average individual cost, and runs weighted set cover. The proof of Theorem 4.3 uses the valid chain cr(R',D_s) ≤ Σ_{r∈R'} cr(r,D_s) ≤ H_n Σ_{r∈R*} cr(r,D_s). The first inequality is true, and the second is a correct application of Chvátal to the surrogate sum-cost objective. But the right-hand side is not the optimum of Problem 1: Σ_{r∈R*} cr(r,D_s) can be larger than cr(R*,D_s), since overlapping rules contribute each rule's individual cost while the objective charges only the union. Only the trivial relation Σ_{r∈R*} cr(r,D_s) ≤ |R*|·cr(R*,D_s) follows. Thus Theorem 4.3 does not establish that greedy is within a logarithmic factor of the optimal union-cost subset; it bounds the greedy result in terms of a different, potentially larger quantity. The abstract's and conclusion's 'provable approximation guarantee' / 'within a logarithmic factor of optimal' are therefore overstated for the problem as stated. This does not invalidate the empirical accuracy/cost comparison, but it removes the main theoretical support for rule refinement. The correct fix is either to state the guarantee for the sum-cost surrogate explicitly, or to change Algorithm 1 to use marginal union costs and analyze it as submodular cover. Property 1's monotonicity is a separate limitation and is explicitly hedged by the cited 94% figure.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"Scout is a document-extraction system that exploits inter-document similarity to make LLM-based extraction over large collections affordable. Given a query and a collection, Scout (i) samples a small representative subset via embedding-based farthest-point sampling (Algorithm 2); (ii) uses an LLM agent to generate a pool of 'rules'—Python programs that return candidate answer-bearing spans (Section 3); (iii) greedily selects a cheap, accurate subset of rules, a problem it proves NP-hard (Section 4); and (iv) applies the refined rules to unseen documents using a cheap proxy to verify whether the retrieved span suffices, with fallback to the full rule pool (Section 5.2). Experiments on six real-world datasets report that Scout matches the accuracy of a per-document agent (~0.90 vs ~0.89) while being 61x to over 1000x cheaper at 1,000 documents, and is 61 points more accurate than the program-based Evaporate baseline. The paper also proves cluster-coverage guarantees for the sampling strategy (Theorems 5.1 and 5.2).","tokens_in":27262,"tokens_out":19291,"duration_ms":169883,"significance":"The problem is well chosen and the solution is concrete: if the reported numbers are stable, a matched-accuracy cost reduction of two to three orders of magnitude over per-document agents would be a substantial contribution to the LLM-powered data-systems literature. Strengths of the paper include the evaluation design (six domains, two external benchmarks with existing ground truth, an explicit amortized-cost model, and a stated artifact URL), the clean and correctly argued analysis of farthest-point sampling, which avoids relying on the triangle inequality that cosine distance does not satisfy, and the clear separation of an accuracy-first rule-generation stage from a cost-focused refinement stage. The main reservations are that the stated approximation guarantee for rule refinement (Theorem 4.3) is not established for the union-cost objective of Problem 1, and that the empirical comparison rests on single runs without variance estimates. Neither issue invalidates the empirical accuracy/cost comparison in my reading, and both are addressable in revision.","major_comments":[{"comment":"Theorem 4.3 establishes cr(R', D_s) <= H_n * sum_{r in R*} cr(r, D_s), where the right-hand side evaluates the sum of the per-rule average cost ratios of the optimal subset, not the union-cost objective cr(R*, D_s) that Problem 1 asks to minimize. Since overlapping rules are counted once in cr(R*, D_s) but once per rule in the sum, the sum can exceed cr(R*, D_s) by an arbitrarily large factor (up to |R*|), so the theorem does not show that Algorithm 1 is within a logarithmic factor of the Problem 1 optimum. The 'provable approximation guarantee' in the abstract and the 'within a logarithmic factor of optimal' claim in the conclusion consequently overstate the result. The fix is either to state the guarantee explicitly for the sum-cost surrogate objective, or to change Algorithm 1 to use marginal union costs and analyze it as a submodular cover problem.","section":"Section 4.2, Theorem 4.3"},{"comment":"Every headline number (Table 1, Figures 9 and 10, Table 6) comes from a single run of a pipeline containing stochastic components (GPT-5.4-based rule generation and refinement, and a single draw of the sample), and no variance or repeat information is reported. Because the central claim is that Scout matches the per-document agent's accuracy while being one to three orders of magnitude cheaper, and several dataset-level differences are only a few points (average 0.898 vs 0.895, within 1.6 points on FinanceBench, OfficeQA, and Product), run-to-run variability could in principle change the direction of some of these comparisons. Please report multiple runs with standard deviations, at minimum for rule generation and the sample draw, or provide evidence that the reported numbers are stable.","section":"Section 6.2"},{"comment":"The reduction to set cover and the greedy's coverage bookkeeping require exact accuracy monotonicity: a document is marked covered when any selected rule is correct on it, and the union of individually correct rules is assumed correct. The paper acknowledges that monotonicity holds only on 'over 94% of documents' according to the external study [31], and it does not measure monotonicity on its own six datasets. The stated degradation ('only that document is affected... guarantees degrade by at most the fraction of documents on which monotonicity fails') bounds the direct accuracy effect but not the effect on Algorithm 1's selection: on a failing document, a rule that is correct alone can be incorrect when its span is unioned with another rule's span, which can mislead the coverage labels used in Line 6 on subsequent documents as well. Please measure monotonicity on the six datasets or provide a bound on the resulting selection error.","section":"Section 2.2 (Property 1) and Section 4.2 (Algorithm 1)"},{"comment":"Algorithm 1's per-rule correctness labels a(r, d_j) and the cascade's sufficiency checks (Figure 8) both use an unspecified 'cheap proxy model,' and the paper asserts without measurement that on short spans the proxy matches the oracle's estimate. Because the refined and cascaded rule sets whose costs and accuracies are reported (Table 6, Figure 9) are selected and applied using these proxy decisions, the paper should report per-dataset proxy-vs-oracle agreement on the rule spans and on the proxy-verification task; currently the reliability of the proxy is an unsupported premise of the experimental pipeline.","section":"Section 4.2 (proxy labeling) and Section 5.2 (cascade)"}],"minor_comments":[{"comment":"Table 1 presents the headline accuracy and cost results inside the Introduction, before the experimental setup is described; consider labeling it as a teaser and deferring the full comparison to Section 6.","section":"Section 1, Table 1"},{"comment":"The oracle is introduced as 'a top-of-the-line LLM (e.g., GPT-5.5)' in Section 2.1, but the experiments use GPT-5.4 for the oracle and judge and Claude Opus 4.7 for labeling; please state the exact oracle model in Section 6.1 so the accuracy definition of Section 2.2 can be checked against the evaluation.","section":"Sections 2.1 and 6.1"},{"comment":"In the ablation prompts, the paid verify_accuracy calls are bounded by a '[Budget]' placeholder, but no budget values are reported anywhere in Section 6; without these values, the comparison between Scout and Scout-AgentRef, Scout-AgentGen, and Scout-AgentE2E is under-specified.","section":"Section 6.1.2"},{"comment":"The sample-size cap min(|S|, 0.1|D|) is applied after Algorithm 2 terminates, while Theorems 5.1 and 5.2 are proved for the uncapped sample; please clarify whether the cluster-coverage guarantees survive truncation by the cap.","section":"Section 5.1"},{"comment":"Accuracy is defined as agreement with the oracle's per-document answer O(d_j, Q) in Section 2.2, but Section 6.1.3 measures accuracy against ground-truth labels using an LLM-as-a-judge (GPT-5.4); the paper should state how documents on which the oracle and the labelers disagree are treated, and should acknowledge that using the same model family for oracle and judge may be optimistic.","section":"Sections 2.2 and 6.1.3"},{"comment":"Reference [31], which carries the empirical burden for the monotonicity assumption (Property 1), is cited as a Google Drive link to a technical report rather than a published venue; please provide a stable, citable reference.","section":"Reference [31]"},{"comment":"There are several small typos and spacing errors (e.g., 'consecutivespans' in Section 3.1, the duplicated 'H_n = O(ln n)' near Theorem 4.3, and inconsistent notation d^i_j vs o_ji for rule outputs); a copyediting pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the manuscript is within scope for PVLDB, and the empirical results would be significant if they are stable across repeated runs, but the headline theoretical claim should be corrected before acceptance: Theorem 4.3 is true as literally stated, yet it does not support the 'within a logarithmic factor of optimal' phrasing in the abstract and conclusion, because the guarantee is against the sum of per-rule costs of the optimal subset rather than the union-cost objective of Problem 1. I would note for the review process that reference [31], which carries the empirical burden for the monotonicity assumption (Property 1), is an unpublished technical report from the same research group linked via Google Drive, and that the artifact URL, while provided, could not be verified from the preprint. These concerns are fixable in revision and do not, in my view, warrant rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the good news. Scout's core move — have an agent generate a broad pool of Python rules that locate the answer span, then select a cheap subset and apply it with a cascade and fallback — is a genuine improvement over prior program synthesis like Evaporate, which tries to emit answers directly. The evaluation is convincing across six real datasets: Scout matches the per-document agent's accuracy while cutting amortized cost by roughly one to two orders of magnitude, and beats Evaporate by 61 points. The ablations are well designed, and the sample-vs-held-out accuracy table is a useful overfitting check. Each piece seems to earn its place.\n\nThe soft spot is the theory. Theorem 4.3 claims a logarithmic approximation for rule refinement, but the bound is not against the objective of Problem 1. Problem 1 minimizes cr(R', D_s), the average token fraction of the union of the selected spans. The greedy algorithm is analyzed as weighted set cover where each rule's weight is its individual cost ratio cr(r, D_s). The proof validly shows cr(R', D_s) ≤ H_n * Σ_{r in R*} cr(r, D_s), but the right-hand side is the sum of per-rule costs of the optimal set, which can be much larger than the optimal union cost cr(R*, D_s). That means the paper does not establish the claimed approximation factor for the stated problem. The abstract's 'provable approximation guarantee' and the conclusion's 'within a logarithmic factor of optimal' are overstated. This is a real flaw, but it is local: the empirical system and the greedy heuristic are unaffected. The fix is to either restate the guarantee for the sum-cost surrogate explicitly or redo the analysis with marginal union costs as submodular cover.\n\nMinor issues: the experiments appear to be single runs without variance, and I could not verify the artifacts from the preprint. The monotonicity assumption (Property 1) is hedged with the cited 94% figure, which is acceptable but worth emphasizing when stating guarantees.\n\nRecommendation: send this out. A serious referee should be able to separate the overstated theory from the solid systems work. I would expect a major revision, primarily rewriting the approximation claim and adding reproducibility information.","headline":"A genuinely useful systems result, but the headline approximation guarantee for rule refinement is not a bound against the stated objective and needs a fix before acceptance.","tokens_in":27821,"tokens_out":4199,"would_cite":true,"duration_ms":40394,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A program-learning pipeline matches full-document LLM extraction accuracy while reading only answer-located spans, cutting cost by 61x to over 1000x on a 1,000-document collection.","keywords":["document extraction","large language models","data similarity","rule synthesis","rule refinement","set cover approximation","Pareto-optimal subset selection","cascade fallback"],"falsifier":"Take a yes/no query on a financial filing where the minimal sufficient span is 'management concluded that internal control over financial reporting was effective' (answer: No material weakness). Append a sentence from elsewhere in the document that says 'However, management reported a material weakness in the titanium alloy used in turbine blades' and observe whether a frontier LLM changes its answer. If such span-superset reversals occur on more than about 6% of documents in a real collection, then monotonicity fails more often than the cited study suggests and Scout's accuracy guarantee would be measurably below the golden baseline on that collection.","tokens_in":26720,"feed_emoji":"📄","tokens_out":9322,"duration_ms":81887,"temperature":0.7,"pith_summary":"Scout is built on a simple observation: within a collection of similar documents, the answer to a given query tends to sit in the same kind of location, so an LLM should not need to read every token. The paper's claim is that one can synthesize small Python 'rules' that locate that span on any document, feed only the span to an expensive oracle LLM, and still match the accuracy of an agent that reads the full document, at 61x to over 1000x lower cost on a 1,000-document collection. This claim is supported by a two-stage design: an agent first generates a broad pool of high-recall rules, then a greedy algorithm selects a cheap Pareto-optimal subset, a problem proven NP-hard (by reduction from Set Cover) and approximated within $O(\\ln n)$ of optimal. Scout also handles collections that are only partially similar by sampling documents across clusters with an LLM-free farthest-point strategy, and by applying rules in a cascade with a cheap proxy check and a fallback to the full rule pool. On six real-world datasets the full pipeline averages 0.898 accuracy against the golden baseline's 0.895, and it is 61 points more accurate than the strongest prior program-based extractor.","feed_headline":"LLM extraction cost cut 61x-1000x by reading only answer spans","feed_subtitle":"Real-world documents repeat answer locations; Scout learns the spot once per query and pays pennies per document.","key_machinery":"The load-bearing object is the 'rule': a self-contained Python function synthesized by an LLM agent that maps a document's enriched span representation to a short subsequence thought to contain the answer. Three mechanisms carry the argument: (1) accuracy monotonicity (Property 1) — the assumption that adding text to a sufficient span never destroys the oracle's answer, which makes rule-set correctness monotone; (2) rule refinement, formalized as finding a Pareto-optimal subset (one no other subset beats in both cost and accuracy) within accuracy tolerance $\\alpha$, proven NP-hard by reduction from Set Cover and solved by a greedy cost-effectiveness rule that mimics weighted set cover, with Chvátal's $O(\\ln n)$ approximation bound; (3) farthest-point sampling over a cosine distance between documents' chunked query-similarity vectors, with cluster-coverage guarantees (Theorems 5.1–5.2), followed by a cascade application that uses a cheap proxy model to verify each prefix of refined rules and falls back to the full pool if none suffices.","core_discovery":"The central discovery is that the expensive step in LLM document extraction—reading the whole document—can be replaced by a learned 'rule': a Python program that returns the subsequence where the answer recurs, after which an oracle LLM answers from that short span alone. The paper proves that choosing the cheapest accurate subset of such rules is NP-hard and gives a greedy solution whose cost is within a logarithmic factor of optimal, the same algorithm as weighted set cover. The accuracy of the resulting rule set is protected by a monotonicity assumption (Property 1: if a span suffices, any superset suffices), which lets the pipeline fall back safely to a larger rule pool when a refined rule fails. Experiments on six real-world datasets show that Scout matches or exceeds the accuracy of a frontier per-document agent (0.898 vs 0.895 average) while cutting amortized cost by one to two orders of magnitude at measured sizes and by 61x to over 1000x at 1,000 documents.","pith_inferences":["If monotonicity fails more often than the cited 6%, particularly on yes/no or negation-heavy queries, the accuracy guarantees would degrade proportionally; a stress test on adversarial or contradictory documents would reveal whether the cited bound is conservative.","The reported cost savings are computed at 1,000 documents; because offline costs are fixed, the advantage should widen on larger collections, but this is an extrapolation in the paper, not a measurement, and it assumes the rule pool generalizes without needing more samples.","The rule generation step's diversity hints (page, section, keyword, table cells, typography) suggest that a richer coverage objective over hint categories might reduce fallback rates further; the paper does not test that directly.","The span-retrieval abstraction is general enough that the same rules could be compiled to layout-aware or vision-based locators for scanned documents, but Scout leaves that extension unstated."],"forward_implications":["If the claim holds, large-scale extraction jobs that previously cost hundreds to thousands of dollars per query can run for cents to a few dollars: the one-time rule-generation cost amortizes over the whole collection, so the total cost stays nearly flat as the collection grows.","The $O(\\ln n)$ approximation guarantee means a user can set an accuracy tolerance $\\alpha$ and know that the refined rule set's cost is within a logarithmic factor of the cheapest subset that meets that tolerance, making cost-accuracy tradeoffs predictable.","The cascade fallback means the system degrades gracefully on heterogeneous collections: when refined rules miss the answer on an unseen document, the proxy detects it and the full high-recall rule pool (which alone matches golden-baseline accuracy) is used instead.","Because the full rule pool alone matches the accuracy of reading every document, the paper's numbers imply that answer-location learning, not question-answering ability, is the main bottleneck for scalable extraction."],"supporting_citations":[{"why":"Supplies the program-based extraction baseline (Evaporate) that assumes answers are substrings; Scout contrasts its span-locating rules against it.","marker":"[8]"},{"why":"Chvátal's greedy set-cover analysis provides the $O(\\ln n)$ approximation bound for Scout's rule refinement.","marker":"[16]"},{"why":"Gonzalez's farthest-point traversal analysis underlies the cluster-coverage guarantees of Scout's sampling strategy.","marker":"[21]"},{"why":"FinanceBench, one of the six evaluation datasets, supplies SEC filings and ground-truth answers for extraction queries.","marker":"[23]"},{"why":"Karp's NP-completeness of Set Cover is used in the reduction proving rule refinement NP-hard.","marker":"[26]"},{"why":"Empirical study reporting accuracy monotonicity holds on over 94% of real-world documents, the basis for Property 1.","marker":"[31]"},{"why":"Codex, the agent used both to generate Scout's rules and as the per-document agent baseline in the cost-accuracy comparison.","marker":"[37]"},{"why":"OfficeQA, one of the six evaluation datasets, provides treasury bulletins and query workloads.","marker":"[38]"},{"why":"Vazirani's treatment of weighted set cover is cited alongside Chvátal for the refinement approximation guarantee.","marker":"[47]"}],"fun_headline_variants":["LLM extraction cost cut 61-1000x by reading only answer spans","Scout learns answer locations to cut LLM extraction cost 1000x","Similar docs, similar answers: Scout cuts extraction cost 100x","Answer spans replace full reads: Scout matches LLM at 1/1000 cost","Extraction at scale: Scout uses document similarity to cut cost 61-1000x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire accuracy argument relies on the oracle being monotone: if a span of text is enough to produce the correct answer, any larger span containing it is also enough; the paper cites a study finding this holds on over 94% of real-world documents, so on the remaining documents the greedy refinement and the fallback can silently lose the answer.","fun_headline_variants_meta":{"raw":{"variants":["LLM extraction cost cut 61-1000x by reading only answer spans","Scout learns answer locations to cut LLM extraction cost 1000x","Similar docs, similar answers: Scout cuts extraction cost 100x","Answer spans replace full reads: Scout matches LLM at 1/1000 cost","Extraction at scale: Scout uses document similarity to cut cost 61-1000x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000416,"raw_usage":{"total_tokens":2229,"prompt_tokens":1107,"completion_tokens":1122,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":723,"completion_tokens_details":{"reasoning_tokens":1017}},"tokens_in":723,"tokens_out":1122,"duration_ms":11179,"temperature":1.0,"reasoning_tokens":1017,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:14:37.495065+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a yes/no query on a financial filing where the minimal sufficient span is 'management concluded that internal control over financial reporting was effective' (answer: No material weakness). Append a sentence from elsewhere in the document that says 'However, management reported a material weakness in the titanium alloy used in turbine blades' and observe whether a frontier LLM changes its answer. If such span-superset reversals occur on more than about 6% of documents in a real collection, then monotonicity fails more often than the cited study suggests and Scout's accuracy guarantee would be measurably below the golden baseline on that collection.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the program-based extraction baseline (Evaporate) that assumes answers are substrings; Scout contrasts its span-locating rules against it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Chvátal's greedy set-cover analysis provides the $O(\\ln n)$ approximation bound for Scout's rule refinement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Karp's NP-completeness of Set Cover is used in the reduction proving rule refinement NP-hard."},{"cited_title":"Parameswaran","cited_arxiv_id":null,"evidence_quote":"Empirical study reporting accuracy monotonicity holds on over 94% of real-world documents, the basis for Property 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"OfficeQA, one of the six evaluation datasets, provides treasury bulletins and query workloads."},{"cited_title":"Vazirani","cited_arxiv_id":null,"evidence_quote":"Vazirani's treatment of weighted set cover is cited alongside Chvátal for the refinement approximation guarantee."}],"review_version":1}