Source-linked AI summary
QESChunker: A Single Objective Unifies Overlapping and Non-Overlapping Chunking for RAG
Yifan Zhao, Qianyang Zhao, Xinyu Guan, kai wei, Yuming Deng
TL;DR
Chunk boundaries affect whether RAG retrieves complete evidence, yet most chunkers rely on heuristics rather than an explicit question–evidence objective. QESChunker optimizes a shared supervised utility for non-overlapping and overlapping indices. Across five corpora, both variants rank first in nearly all displayed settings under a fixed hybrid retriever.
Problem
Chunk boundaries influence whether evidence for a question can be retrieved completely, but most existing chunkers are heuristic and do not optimize an explicit question–evidence objective.
Source: §1 · p. 1Method
QESChunker optimizes a shared question–evidence utility, using exact polynomial-time dynamic programming for non-overlapping partitions and benefit–cost greedy for overlapping indices.
Source: §1 · pp. 1–2Results
Across five corpora, non-overlap DP ranks first in 9/10 corpus×tier cells and the overlap method in 10/10 under a fixed hybrid retriever.
Source: §1 · p. 2Takeaways & Limitations
The results support treating chunk construction as supervised, budget-aware static-index design for evidence retrieval.
Source: §8 · p. 9Boundary fitting depends on adequate question–evidence supervision, making the method best suited to repeatedly queried documents with accumulated supervision.
Source: §7 · p. 9
Abstract
from arXiv · showhide
Chunking is a fundamental preprocessing step in retrieval-augmented generation (RAG), yet most existing chunkers rely primarily on heuristics. We introduce the Question--Evidence-Supervised Chunker (QESChunker), to our knowledge the first method for constructing static chunk indices from question--evidence supervision. QESChunker constructs document-specific chunk indices by optimizing over human-annotated or LLM-generated question--evidence pairs, without access to held-out test queries. We formulate non-overlapping and overlapping index construction through a unified question--evidence utility-maximization objective, turning chunking into a supervised combinatorial optimization problem. Under the non-overlap constraint, the objective decomposes over chunks and can be optimized exactly in polynomial time by dynamic programming. When overlap is allowed, the objective becomes monotone submodular; exact optimization is NP-hard, but our greedy achieves a $(1-1/\sqrt{e})$-approximation. Across two self-constructed and three public datasets, both variants outperform existing chunking methods in complete-evidence recall in nearly all evaluated settings, under the same overlap regime and a fixed hybrid retriever. These results recast chunking as supervised, budget-aware index construction for evidence retrieval.
1 INTRODUCTION
QESChunker treats chunking as optimization supervised by question–evidence pairs, rather than relying on heuristics. It applies one objective under different structural constraints, with strong benchmark results and distinct guarantees for non-overlapping and overlapping indices.
1 INTRODUCTION
- Chunk boundaries matter because they determine whether evidence for a question can be retrieved completely, yet evaluated chunkers do not optimize an explicit question–evidence objective.The evaluated alternatives include fixed-length, paragraph, semantic, LLM-based, and hierarchical approaches.Source: §1 · p. 1
- QESChunker uses question–evidence supervision to optimize document-specific chunk boundaries through one objective under two structural constraints.The framework is called the Question–Evidence Supervised Chunker.Source: §1 · p. 1
- For non-overlapping partitions, dynamic programming finds the global optimum in polynomial time; for overlap, benefit–cost greedy achieves a (1 −1/√e) ≈0.393 approximation.Exact optimization with overlap is NP-hard.Source: §1 · p. 2
- Across five corpora, non-overlap DP ranks first in 9/10 corpus×tier cells and the overlap method in 10/10 under a fixed hybrid retriever.Both variants outperform existing chunking methods in nearly all evaluated settings.Source: §1 · p. 2
2 RELATED WORK
The paper situates its work among practical chunking and retrieval alternatives, and distinguishes boundary selection from other segmentation objectives and systems that alter more than chunk boundaries.
2 RELATED WORK
- The evaluated alternatives span fixed-length, paragraph, lexical, embedding-based, LLM-predicted, sentence-window, and hierarchical chunking designs.These cover non-overlapping, overlapping, semantic, LLM-based, and hierarchical approaches.Source: §2 · p. 2
- Classical topic and discourse segmenters optimize segmentation labels rather than RAG evidence recall, while QESChunker targets the latter.The passage names C99 and supervised neural boundary models as examples.Source: §2 · p. 2
- Dense X, Late Chunking, and RAPTOR change more than chunk boundaries, so the paper excludes them from matched comparisons isolating boundary selection.Those systems respectively use generated propositions, contextual embedding computation, and recursive summaries with hierarchical retrieval.Source: §2 · p. 2
3 PROBLEM SETUP AND UNIFIED OBJECTIVE
The setup represents documents and question evidence at the atomic-block level, then scores chunks with hit-gated evidence coverage and a structural prior. The shared objective supports different solvers depending on whether chunks form a partition or may overlap.
3.1 ATOMIC BLOCKS, EVIDENCE, AND HITS
- Documents are split into atomic blocks; each fitting question has gold evidence blocks and a hit set of top-κ blocks a first-stage retriever would surface.Chunks are contiguous intervals over the blocks.Source: §3.1 · pp. 2–3
3.2 HIT-GATED WEIGHTED COVERAGE WITH A TIERED STRUCTURAL PRIOR
- Coverage counts question–evidence pairs only when a chunk contains a hit block; a tiered structural prior favors paragraph endings over sentence, clause, and other boundaries.The structural term is determined by the terminal punctuation of the chunk’s right block.Source: §3.2 · p. 3
3.3 PARTITION DECOMPOSITION
- For partitions, disjoint chunks make the objective additive per chunk, enabling dynamic programming; with overlap, it becomes a set function handled by submodular optimization.Both settings use the same objective and are directly comparable under the stated evaluation convention.Source: §3.3 · p. 3
4 SETTING 1: NON-OVERLAP PARTITION
The non-overlap setting seeks an exact-K contiguous partition that maximizes the shared utility subject to chunk-length rules. A dynamic program exploits the sequential structure, with a whole-paragraph exception for oversized natural paragraphs.
4 SETTING 1: NON-OVERLAP PARTITION
- The non-overlap solver maximizes f(S) over contiguous K-partitions subject to length bounds, allowing a whole-paragraph exception.The exception admits an entire paragraph longer than Lmax but forbids oversized chunks crossing paragraph boundaries.Source: §4 · p. 3
- The DP state stores the maximum utility for a prefix partitioned into exactly k chunks, and back-pointers recover the optimal cut points.Its recurrence considers length-window predecessors plus the whole-paragraph exception.Source: §4 · p. 4
- With W = Lmax − Lmin + 1, the algorithm runs in O(nKW) time and uses O(nK) space for its table and back-pointers.Each state examines at most W feasible predecessors plus one whole-paragraph predecessor.Source: §4 · p. 4
5 SETTING 2: OVERLAP SELECTION
With overlap allowed, the index is a budgeted set of candidate chunks, and its objective is monotone submodular. The section establishes NP-hardness of exact optimization and describes a greedy alternative.
5 SETTING 2: OVERLAP SELECTION
- The overlap index selects from length-bounded candidate intervals under a total indexed-block budget, charging each chunk its length and rewarding paragraph ends.The overlapping candidate family does not use the whole-paragraph exception.Source: §5 · p. 4
5.1 MONOTONE SUBMODULARITY
- The objective is monotone submodular because weighted question-evidence coverage is monotone submodular and the non-negative, per-chunk prior is modular.Each covered question-evidence element contributes its weight only the first time it is covered.Source: §5.1 · pp. 4–5
5.2 EXACT OPTIMIZATION IS NP-HARD
- Exact coverage maximization over contiguous chunks is NP-hard even with singleton evidence and zero prior weights; hardness also holds when every candidate has length L.The decision problem is NP-complete, including when only length-L chunks are allowed.Source: §5.2 · p. 5
- The greedy method chooses chunks by marginal gain per unit cost and uses a singleton safeguard that returns the better of its result and the best feasible single chunk.The paper retains the weaker (1−1/√e) guarantee, while Tang et al. (2021) prove a 0.405 factor for the same modified greedy algorithm.Source: §5.2 · pp. 5–6
- Lazy evaluation makes the greedy practical by using stale marginal-gain densities as upper bounds, requiring only tens of exact re-evaluations per accepted chunk while returning the eager greedy’s set.The paper notes that the empirical gap between the algorithm’s value and the optimum is generally much smaller than the guarantee gap.Source: §5.2 · p. 6
6 EXPERIMENTS
Under the same overlap regime and returned-context convention, the non-overlap DP leads in 9/10 displayed cells and the overlap method in 10/10. Parameter sweeps show sensitivity to structural weighting, broad stability across candidate-length ranges, and stronger optimized-chunking gains at tighter context budgets.
6.1 EXPERIMENTAL SETUP
- Public-document fitting uses n/5 synthetic questions per document, while evaluation uses native public questions and evidence annotations.The self-built corpora use eight-fold cross-validation; all methods share an embedding–BM25 retriever and returned-context budgets.Source: §6.1 · pp. 6–7
6.2.1 STRUCTURAL WEIGHT
- DP coverage rises with small positive structural weights and plateaus around λ = 10^-2, while greedy declines sharply at λ ≥ 10^-2.The reported explanation is that an over-weighted paragraph prior displaces evidence-bearing chunks.Source: §6.2.1 · p. 7, Figure 2 · p. 7
6.2.2 LENGTH GEOMETRY
- Both variants change smoothly as candidate-length intervals contract, with DP nearly flat over broad ranges and greedy stable at @10%.DP degrades only near the fixed-length limit; greedy has a modest decline at @100, and equal-length splitting makes the variants equivalent at the rightmost point.Source: §6.2.2 · p. 7, Figure 3 · p. 7
6.2.3 WHOLE-PARAGRAPH EXCEPTION
- The whole-paragraph exception improves coverage at small returned-context budgets but offers no advantage at large budgets.It is enabled in every non-overlap main experiment for fairness.Source: §6.2.3 · p. 8, Table 2 · p. 8
6.3 MAIN EXPERIMENTS
- The non-overlap DP leads in 9/10 displayed cells, while overlap greedy leads in all 10/10 cells by 0.61–8.11 points over the strongest baseline.The DP’s only loss is PeerQA at @100, by 0.58 points; overlap gains remain positive on PrivacyQA.Source: §6.3 · pp. 8–9, Table 3 · p. 8, Table 4 · p. 8
6.4 BUDGET ANALYSIS
- Coverage rises monotonically with returned budget, but QESChunker separates most at small budgets and stays ahead in both settings.Across the other four datasets, methods converge near saturation on Congress; QASPER and PeerQA retain wider overlap-side gaps at low and medium budgets, while PrivacyQA has clear overlap separation.Source: §6.4 · p. 9, Figure 4 · p. 9
7 LIMITATIONS
The paper’s gains are measured in retrieval-level complete-evidence recall, not end-to-end answer quality. QESChunker is best suited to documents with repeated queries and sufficient question–evidence supervision.
7 LIMITATIONS
- The reported gains concern retrieval-level complete-evidence recall, not a measured improvement in downstream answer quality.The conversion to answer quality remains unknown, so the paper does not claim a fixed or proportional end-to-end improvement.Source: §7 · p. 9
- Any translation of recall gains to answer quality depends on the generator, prompting, context ordering, evidence redundancy, and evaluation criteria.The paper therefore makes no fixed or proportional end-to-end improvement claim.Source: §7 · p. 9
- Boundary fitting is best suited to repeatedly queried documents with sufficient supervision; cold-start or sparsely annotated documents may lack reliable question–evidence pairs.In those cases, performance may be driven mainly by the structural prior and retriever rather than learned boundaries.Source: §7 · p. 9
8 CONCLUSION
QESChunker frames chunk construction as supervised, budget-aware optimization, with complementary solvers for non-overlapping and overlapping indices. Its retrieval-level results support document-specific static indices, while the paper also reports AI-use, ethics, and reproducibility boundaries.
8 CONCLUSION
- Across five corpora, QESChunker’s two variants improve complete-evidence recall in nearly all displayed settings, with the largest gains at tight returned-context budgets.The parameter sweeps also show stability across broad structural-weight and candidate-length ranges.Source: §8 · p. 9
AI USE STATEMENT
- Generative AI generated fitting questions and evidence IDs and judged auxiliary outputs, while public evaluation used human or expert labels.The authors report legality, membership, length, hallucination, and duplication checks, and state that AI was not used for theory or solver implementation.Source: AI USE STATEMENT · p. 10
ETHICS STATEMENT
- The study uses public QA datasets and government policy documents, with no human subjects, private data, or personal identifiers.The authors flag possible annotator-model bias in LLM-annotated self-built evidence and identify human-annotated QASPER and author-annotated PeerQA as their highest-confidence claims.Source: ETHICS STATEMENT · p. 10
REPRODUCIBILITY STATEMENT
- The paper locates its objective, weights, tier ratios, solver algorithms, guarantee, evaluation convention, and sensitivity analyses in specified sections and appendices.It reports brute-force enumeration for DP correctness and a certificate for the greedy algorithm.Source: REPRODUCIBILITY STATEMENT · p. 10
A PROOF OF PROPOSITION 1
The proposition’s proof establishes monotone submodularity by combining a weighted coverage term with a non-negative modular prior. For partitions, disjoint chunks make the objective additive, enabling the dynamic-programming decomposition.
A PROOF OF PROPOSITION 1
- The coverage term is monotone submodular because each weighted question–block element contributes once, when first covered by a selected chunk.As the selected set grows, a chunk’s marginal coverage contribution cannot increase.Source: A PROOF OF PROPOSITION 1 · p. 13
- The structural prior is non-negative and modular because each chunk’s contribution depends only on that chunk.Its increment is independent of the other selected chunks.Source: A PROOF OF PROPOSITION 1 · p. 13
- Adding the coverage and prior terms preserves monotone submodularity, as does the stated non-negative weighted concentration term.The concentration term is expressed as a sum of non-negative weighted maxima over selected chunks.Source: A PROOF OF PROPOSITION 1 · p. 13
- For a partition, disjoint chunks cover disjoint question–block elements, so the objective decomposes into per-chunk values.That additivity is the optimal-substructure used by the dynamic program.Source: A PROOF OF PROPOSITION 1 · p. 13
B FULL PROOF OF THEOREM 1
The proof maps a grid cover to a budget-feasible family of legal chunks and reverses the mapping from any full-coverage family within budget. The size bounds establish that the reduction is polynomial, and the proof also addresses candidates restricted to length L.
B FULL PROOF OF THEOREM 1
- A grid cover with at most k horizontal length-2 segments yields at most k intervals [t, t + 2] covering at least one point from every encoded pair.The proof first discards intervals with no encoded endpoint and shifts the others to their smallest contained encoded point.Source: B FULL PROOF OF THEOREM 1 · p. 14
- Replacing each interval with C_t = [t, t + D + 2] gives legal chunks whose total cost is at most kL and whose coverage is complete.This fits the index budget B_index.Source: B FULL PROOF OF THEOREM 1 · p. 14
- In the reverse direction, budget and coverage imply at most k nonempty-coverage chunks, each extendable to a length-L chunk without losing covered pairs.Their corresponding length-2 intervals cover every encoded pair and map back to a grid cover.Source: B FULL PROOF OF THEOREM 1 · p. 14
- The reduction has polynomial size because D and L are O(m), n is O(m^2), and the candidate family is O(m^3).A selected family is a polynomial-size certificate with polynomially checkable cost and coverage.Source: B FULL PROOF OF THEOREM 1 · p. 14
- Restricting candidates to length exactly L leaves the forward implication unchanged, while the budget limits the reverse direction to at most k chunks.Under that restriction, the short-chunk argument is unnecessary.Source: B FULL PROOF OF THEOREM 1 · p. 14
C ADDITIONAL BUDGET CURVES
The appendix reports full returned-context budget curves for four datasets not shown in Figure 4, using the same left/right non-overlap and overlap convention as the white-paper analysis.
C ADDITIONAL BUDGET CURVES
- Figure 5 shows non-overlap and overlap budget curves for the Party Congress report.Non-overlap is on the left and overlap on the right.Source: Figure 5 · p. 15
- Figure 6 shows non-overlap and overlap budget curves for QASPER.Non-overlap is on the left and overlap on the right.Source: Figure 6 · p. 15
- Figure 7 shows non-overlap and overlap budget curves for PeerQA.Non-overlap is on the left and overlap on the right.Source: Figure 7 · p. 16
- Figure 8 shows non-overlap and overlap budget curves for PrivacyQA.Non-overlap is on the left and overlap on the right.Source: Figure 8 · p. 16